大规模动态演化图的存储与分析系统研究

大规模动态演化图的存储与分析系统研究图数据通过顶点和边的结构表达实体间的相互联系。图数据的分析计算技术,也称图挖掘技术,是通过分析实体间联系,获得关于实体的性质、特征等重要信息的一项技术,正广泛地应用于信息检索、社交分析、生物计算等多个领域。本文所述的图存储分析系统是支持图分析计算的平台系统。它利用抽象的编程接口支持图分析算法的高效实现,利用优化的系统设计提供高效的算法执行,从而实现超大规模的图数据分析。在大数据时代的今天,大规模图存储与分析系统及其相关技术已经成为一个重要的研究方向。而近年来,随着社交网络媒体、移动互联网等新型应用的普及,信息的组织方式、传播方式等,正发生着新的变化——信息呈现出更为明显的动态化特征。随着这一变化,捕捉了数据时序特征的动态演化图,其数据挖掘分析的价值正受到更多的重视,并随着演化图数据分析理论研究的同步深入,逐渐成为一个新的发展趋势。然而现有的图存储与分析平台系统针对的是静态图,并不适合动态演化图。因此,本文研究问题的重点,就在于：如何针对动态演化图分析这一类新的应用,设计并实现高效的大规模存储分析系统。我们通过分析,将动态演化图相关的应用主要总结为：(1)分析动态演化图准实时状态和(2)分析动态演化图长期变化趋势两类。前者着重于分析动态演化图的最新状态,而后者着重于分析动态演化图的长期历史变化过程。在文中,我们为这两类应用算法,设计并实现了动态演化图存储、分析系统。该系统以图数据的实时变化作为输入,产生具有全局一致性的图数据更新,并用于动态演化图准实时状态分析；同时,它会将接收到的时序数据存储下来,重新组织并用于动态演化图长期变化趋势分析。在系统的设计实现中,我们将针对动态演化图准实时状态分析和动态演化图长期变化趋势分析的两部分功能分别抽象成以下两个子问题加以解决：一、动态演化图在线分析的系统问题。在该问题中,大量新的图数据高速产生,应用需要不断地对最新的图数据进行在线处理,从而得到准实时的分析结果。然而实现准实时分析,数据的处理延迟需要足够低。此外,在分布式环境下,还需保持动态数据访问的全局一致性,从而保证分析结果的正确性。为此,我们设计了动态演化图在线分析子系统。该子系统的架构的设计考虑了处理流程的耦合关系,对图数据存储和分析计算进行了解耦。它选用了一个“时段提交”技术来处理图更新,并为系统的计算部分提出了全新的增量计算模型,大大降低分析计算的延迟。我们完成了该系统的工程实现,并在1亿条真实推特文本数据上进行了包括争议话题探测、近似最短路径计算、用户排序等多种应用的测试。利用40台机器组成的集群,我们获得了10万每秒的推文处理速率,并保持2.5分钟以内的数据延迟,满足了我们最初设定的“远超推文的产生速率”的性能要求。二、动态演化图离线分析的系统问题。在该问题中,系统需要保存动态演化图的长期历史数据,并支持动态演化图长期变化趋势的离线分析。相对于静态图分析处理的是单一的静态图,长时间跨度动态演化图分析面对的是多个时间点对应的一系列静态图。更大的数据量带来更高的处理开销,因而系统分析计算的性能非常重要。此外,系统还需要为动态演化图复杂多变的存取模式提供高效的访问性能,为分析性能提供保障。为此我们在文中提出了动态演化图离线分析子系统。它的副本相异数据排布技术利用数据中心多个数据备份的特点,为动态演化图不同类型的访问提供不同针对性的数据组织方式,从而在复杂多变的存取访问中获得更好的数据存取性能;利用全新的局部性感知分批调度技术——局部性分批调度,我们提高了分析计算中高速缓存的利用率并减少了数据同步的开销,极大地改善了长时间跨度动态演化图分析的整体性能。在实际大规模动态演化图进行的多项应用测试结果表明,该系统能够提供相对于目前数据库系