GraphOnE: 解决图形数据存储设计问题及实时图形分析的高性能文件

ACM Transactions on Storage，Vol.号154、第二十九条。出版日期：2020年1月×××× × ××GraphOnE：一个用于演化图PRADEEP KUMAR，计算机科学系，威廉和玛丽H. HOWIE HUANG，乔治华盛顿大学电气与计算机工程系越来越需要在不断发展的图表上执行各种实时分析（批处理和流分析），以向用户提供大数据的价值这些应用程序的关键需求是拥有一个数据存储来有效地支持其多样化的数据访问，同时以高速度并行地进行细粒度不幸的是，当前的图形系统，无论是图形数据库还是分析引擎，都不是为了实现两种操作的高性能而设计的;相反，它们在一个领域中表现出色，即以专门的方式保持私有数据存储，以只支持它们的操作为了应对这一挑战，我们设计并开发了一种图形数据存储，它将图形数据存储从专门的系统中抽象出来，以解决与数据存储设计相关的基础研究问题它结合了两种互补的图形存储格式（边列表和邻接列表），并使用双重版本控制来将图形计算与更新解耦。重要的是，它提出了一个新的数据抽象，GraphView，使数据访问在两个不同的粒度的数据输入（称为数据可见性）的并发执行的不同类的实时图形分析只有一个小的数据重复。实验结果表明，GOnE是能够提供11.40和5.36的平均加速摄取率对LLAMA和毒刺，两个国家的最先进的动态图形系统，分别。此外，它们的平均加速比为对于BFS和PageRank分析（批量版本），LLAMA分别为8.75和4.14，Stinger分别为12.80和3.18GOnE还获得了超过2，000的加速比Kickstarter，这是一个最先进的流分析引擎，在将前半部分视为基本快照并将其余部分视为合成图中的流边缘时，可以捕获流边缘并执行流BFSG OnE还实现了比图形数据库高两到三个数量级的摄取率最后，我们证明了可以从同一数据存储运行并发流分析CCS概念：·信息系统→数据管理系统;主存引擎;信息存储系统;其他关键词和短语：图形系统，图形数据管理，统一图形数据存储，批处理分析，流分析本文是Kumar等人的FAST'19会议论文的扩展。会议论文中增加了大量内容，包括关于并发分析执行的演示，以及与两个新系统的比较：基于快照的批处理图分析系统和流图分析系统。我们还结合了原始文本数据的各种新结果，GraphView上的开销评估，设计参数的许多新评估，以及使用新图表和表格进行扩展的讨论，以提高整篇文章的可读性。这项工作得到了国家科学基金会职业奖1350766和补助金1618706和1717774的部分支持作者pkumar@wm.eduH.黄，电气和计算机工程系，乔治华盛顿大学，800第22街西北，华盛顿特区，20052;电子邮件：howie@gwu.edu。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。本作品的版权归ACM以外的其他人所有，必须予以尊重。允许使用学分进行摘要。以其他方式复制、重新发布、在服务器上发布或重新分发到列表中，需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2020计算机协会。1553-3077/2020/01-ART29 $15.00https://doi.org/10.1145/336418029ACM Transactions on Storage，Vol.号154、第二十九条。出版日期：2020年1月二十九P. Kumar和H.H. 黄ACM参考格式：Pradeep Kumar和H.黄浩威2020. G OnE：一个用于演化图实时分析的数据存储。 ACM Trans. 存储15，4，第29条（2020年1月），40页。https://doi.org/10.1145/33641801介绍在我们生活的世界中，信息网络已成为我们日常生活不可分割的一部分大量的研究已经研究了这种网络中的关系，例如，生物网络[35]、社交网络[22，43，49]和网络[9，33]。在这些应用程序中，图形查询和分析被用来从数据中获得有价值的见解，这些见解可以分为两大类：批量分析（例如，PageRank [69]，图遍历[11，54，56]）分析数据的静态快照，以及流分析（例如，异常检测[8]、主题检测[73]），其研究在感兴趣的时间窗口上的传入数据。一般来说，批量分析更喜欢基础（数据）存储，它可以提供对图的非时间属性（例如边缘的源顶点）的索引访问，而流分析需要一个流（数据）存储，其中数据可以快速存储，并且可以通过它们的到达顺序进行索引以进行时间分析。越来越多的人需要在不断发展的图上同时执行批处理和流处理[10，77，78，93]。这里的关键要求是保持高速的大量细粒度更新，同时为各种实时分析和查询支持提供高性能的数据访问。这种趋势对底层存储和数据管理系统提出了许多挑战首先，批处理和流分析执行不同类型的数据访问，即前者访问整个图，而后者关注时间窗口内的数据其次，每个分析都有不同的实时概念，也就是说，数据在不同的数据摄取（更新）粒度上对分析可见例如，诸如PageRank之类的迭代算法可以在以粗粒度更新的图上运行，但是输出最新最短路径的图查询需要更细粒度的数据可见性第三，这样的系统还应该能够处理高到达率的更新，并在运行并发批处理和流处理任务时保持数据一致性不幸的是，当前的图系统既不能提供多样的数据访问，也不能在存在高数据到达率的情况下以不同的数据摄取粒度提供数据访问，如表1所示。许多动态图系统[50，59]仅支持批量更新，还有一些[23，79]提供了精细更新粒度的数据可见性，但具有弱一致性保证（原子读取一致性），因此可能导致分析迭代在不同的数据版本上运行并产生不期望的结果。关系和图形数据库，如Neo4j [66]可以处理细粒度的更新，但为了保证强一致性，摄取率很差[62]。而且，这样的系统没有被设计成支持在时间窗口上的高性能流数据访问。然而，图形流引擎[34，65，76，85]将增量计算与数据摄取交织，即，图形更新是分批的，并且直到迭代结束才应用。简而言之，现有系统以有利于其专业分析的方式管理私有数据存储。原则上，可以并排利用这些专用图系统来为动态图提供数据管理功能，并支持广泛的分析和查询，如图1（a）所然而，这种方法是次优的[93]，因为它只与最弱的组件一样好更糟糕的是，这种方法还可能导致过多的数据重复，因为每个子系统都将以自己的格式存储相同基础数据的副本。GRA pH OnE：一个用于演化图实时分析的数据存储二十九ACM Transactions on Storage，Vol.号154、第二十九条。出版日期：2020年1月表1. 各种图数据管理系统的简化分类描述每个图系统仅支持一种类型的数据摄取和访问模式图形系统提供的摄入类型提供的数据访问类型图形数据库细粒度（例如，Neo4j [66]）整个数据动态图系统细粒度（例如，[23]第二十三话整个数据粗粒度（例如，[50]第五十话流图系统粗粒度（例如，Naiad [65]）整体数据粗粒度（例如，GraphTau [34]）从时间窗口进行图1.一、展示了图形分析系统的高级概述不断演化的图数据一次到达一条边，或者从数据源（如ApacheKafka、数据库更改日志等）分批到达当前的图分析系统中的每一个都具有针对与数据源接口的一类用例优化的私有数据存储Grap p H On E将数据存储从分析系统中抽象出来，以解决与通用图形数据存储相关的问题，并使用GraphView实例从同一数据存储中执行不同类别的分析。在这项工作中，我们已经设计了GOnE，一个从专门的图形系统中抽象出来的统一图形数据存储，如图1（b）所示，以解决这种数据存储设计和管理的基本问题G OnE为各种实时分析提供了两种粒度级别的数据摄取的多样化数据访问，因此可以从同一数据存储执行许多类别的分析，同时支持高到达率的数据摄取。图2提供了一个高级概览。它利用一个混合图存储来组合一个小的圆形边缘日志（以下简称边缘日志）和一个邻接存储，以实现它们的互补优势。具体而言，边缘日志使用日志记录阶段以边缘列表格式保存最新更新，并旨在加速数据摄取。同时，邻接存储以邻接列表格式保存较旧数据的快照，这些快照使用归档阶段定期从边缘日志中移动，并针对批处理和流分析进行了优化。重要的是要注意，图形数据不会以两种格式重复，尽管允许少量重叠以保持版本的原始组成不变。二十九P. Kumar和H.H. 黄ACM Transactions on Storage，Vol.号154、第二十九条。出版日期：2020年1月××图二、GRA pH OnE的高级架构。实线和虚线箭头分别显示数据管理和访问流程。G OnE在日志记录阶段使用边缘日志的时间性质来执行数据排序，并在归档阶段使用新颖的边缘分片来保持邻接存储中的每个顶点边缘到达顺序不变双版本化技术然后利用边缘列表格式的细粒度版本化和邻接列表格式的粗粒度版本化来创建实时版本以提供快照隔离数据一致性。此外，GOnE允许独立执行与数据管理并行运行的分析，并可以在 在流分析的情况下结束其自身的增量计算步骤。这与当前的流图系统不同，在流图系统中，批量更新的大小通常由最重的计算确定，这损害了其他并发执行分析的及时性。此外，我们提供了两个优化技术，高速缓存大小的内存分配和特殊处理的幂律图的高度顶点，以减少版本邻接存储的内存需求。G OnE通过在混合存储之上呈现新的数据抽象GraphView来简化多样化的数据访问。支持两种类型的GraphView，如图2所示：（1）静态视图为批量分析提供最新数据的实时版本控制，（2）流视图支持最新更新的流分析。这些视图在两个粒度级别上为分析提供了数据更新的可见性，其中边缘日志用于在边缘级别提供数据更新，而邻接存储则以粗略的更新粒度提供数据更新。因此，GOnE为高级应用程序提供了选择数据可见性粒度以实现所需性能的灵活性。换句话说，如果需要细粒度的数据可见性，可以访问边缘日志，这是可以调优的（第7.4节）。我们已经实现了GOnE作为内存中的图形数据存储，在外部非易失性存储器快速固态驱动器（NVMe SSD）上具有有限的耐久性保证。为了进行比较，我们已经针对许多类别的内存图形系统对其进行了评估：LLAMA [59]，作为基于快照的粗粒度图形批量分析系统;Stinger [23]，细粒度动态图形系统; Neo4j和SQLite，两个图形数据管理系统;以及Kickstarter[85]，作为图形流分析。实验结果表明，GOnE可以支持较高的数据摄取速率，具体来说，它在摄取速率上比LLAMA平均提高了11.40比Stinger高5.36的摄取率，并且比图形数据库高两到三个数量级的摄取率。此外，在BFS和PageRank分析（批量版本）方面，GOnE分别比LLAMA高出8.75倍和4.14倍，比Stinger高出12.80倍和3.18倍G OnE还获得了GRA pH OnE：一个用于演化图实时分析的数据存储二十九ACM Transactions on Storage，Vol.号154、第二十九条。出版日期：2020年1月×图3.第三章。在已知感染用户和感染节点的情况下，图遍历可以使用实时认证图定位可能的感染节点在合成图中，当将前半部分视为基础快照而将其余部分视为流边缘时，在整合流边缘和执行流BFS方面，GOnE中的流处理与数据归档阶段（更新到相邻存储）并行运行，与当前顺序运行这两个阶段的做法相比，其摄取率高出28.58%。由于此功能，GOnE还支持来自相同动态邻接存储的并发流分析，这在先前的图形流分析引擎中大多不存在概括起来，G. OonE做出了三个贡献：通过双版本控制、智能数据管理和内存优化技术提供批处理和流分析通过GraphView和数据可见性抽象，支持多种数据访问，以便并发执行各种用例。文章的其余部分组织如下。我们在第2节中介绍了一个用例，在第3节中介绍了机会和G++概述，在第4节中介绍了混合存储，在第5节中介绍了数据管理内部和优化，在第6节中介绍了GraphView数据抽象，在第7节中介绍了评估，在第8节中介绍了相关工作，在第9节中介绍了结论。2用例：网络分析图形分析是企业网络上数据分析的自然选择图3（a）显示了一个简单计算机网络的图形表示这样的网络可以通过计算直径[52]和介数中心度[13]来整体分析，以识别铰接点。这种批量分析对于网络基础设施管理非常有用同时，由于网络内的动态流捕获用户和机器的实时行为，因此流分析用于识别安全风险，例如，拒绝服务和横向移动，这可以以流图上的路径查询、并行路径和树查询的形式表示[18，40]。洛斯阿拉莫斯国家实验室（LANL）最近发布了一个全面的数据集，它捕获了广泛的网络信息，包括认证事件，进程事件，DNS查找和网络流量。LANL数据覆盖了超过15亿个事件、12，000个用户和17，000台计算机，并且持续了58天。例如，网络认证数据捕获用户登录到网络机器以及从该机器登录到其他机器的登录信息。当网络防御系统识别出一个恶意用户和节点时，它需要找到所有可能已经被感染的节点。人们可以在实时认证图上快速运行路径遍历查询，而不是分析网络···二十九P. Kumar和H.H. 黄ACM Transactions on Storage，Vol.号154、第二十九条。出版日期：2020年1月图四、示例图及其各种存储格式。 G RA p H On E集中于边表格式和邻接表格式的互补性质。识别可能的受感染节点，也就是说，找到其登录源自从第一台受感染机器登录的节点链的所有节点[40]，如图3（b）所示总之，捕获网络中的动态数据、与用户和机器信息以及网络拓扑相结合的高性能图形存储有利于了解网络的健康状况、加速网络服务并保护其免受各种攻击。这清楚地阐明了需要有一个数据存储，可以有效地摄取传入数据，并使其以各种分析和查询引擎喜欢的形式进行分析，以便分析作者可以专注于实际用例，而不是考虑如何管理传入数据并提供正确的数据一致性以及证明各种数据访问类型。为此，G OnE提出了一种图形数据存储和管理基础设施，该基础设施将数据存储从分析引擎中抽象出来，以解决基本的数据访问问题与这种多样化的实时分析相关。3机会和概述一个图可以定义为G=（V，E，W），其中V是顶点集，E是边集，W是边权重集。每个顶点也可以具有标签。在本节中，我们将描述与GOnE相关的图形格式及其特性，然后我们将介绍其高级概述。3.1图表表示：机会图4显示了示例图的三种最流行的数据格式首先，边列表是边的集合，即一对顶点，并按其到达顺序捕获传入数据第二，压缩稀疏行（CSR）将顶点的边分组到边数组中。有一个Meta数据结构，顶点数组，它包含每个顶点的第一条边的索引第三，邻接列表管理每个顶点的邻居在单独的每个顶点的边数组，顶点数组存储计数（称为度）和指针，以分别指示相应的边数组的长度和位置这种格式比CSR更适用于inggraph更新，因为它一次只影响一个边数组在边列表中，每个顶点的邻居都是分散的，所以这不是许多图查询和批处理分析的最佳选择，其中更倾向于快速获得顶点的相邻边[12，31，32，36]，等等。然而，边列表为快速更新提供了自然的支持，因为每次更新只需附加到列表的末尾。然而，邻接列表格式失去了时间顺序，因为传入的更新分散在边缘数组上;因此，这不直接适合流分析。此外，在邻接列表上创建细粒度快照并不容易，因此先前的工作仅尝试GRA pH OnE：一个用于演化图实时分析的数据存储二十九ACM Transactions on Storage，Vol.号154、第二十九条。出版日期：2020年1月图五、建筑的GRA pH OnE. 与相同数据结构相关的操作在存档阶段已变灰。未显示压实阶段创建粗粒度版本化[28，59]。Stinger [23]直接更新邻接列表格式，但只能提供读提交，数据一致性较弱，不提供任何快照功能。因此，分析中的不同步骤将在不同版本的数据上运行，从而在不断演变的图表中产生未知的结果。考虑到它们的优点和缺点，这两种格式都不适合支持批处理和流分析以及高数据摄取。我们现在确定这项工作的两个机会：机会#1：在混合存储中同时利用边缘列表和邻接列表。边缘列表格式保留了数据到达顺序，并为快速更新提供了良好的支持，因为每个更新都简单地附加到只需要顺序写入的列表的末尾。然而，邻接列表保持由源顶点索引的顶点的所有邻居，这为图分析提供了有效的数据访问。因此，它允许GOnE实现高性能图计算，同时支持细粒度更新。机会2：使用边缘列表格式创建细粒度快照。图形分析和查询需要在执行期间对最新数据进行不可变的快照。边缘列表格式提供了对细粒度快照创建的自然支持，而无需创建物理快照（由于其时间性质），因为跟踪快照只是记住边缘列表中的偏移因此，邻接列表格式可以使用边列表的细粒度快照功能来补充其粗粒度快照功能[28，59]，以创建图形数据的实时版本。3.2概述G OnE使用混合图数据存储（在第4节中讨论），由一个小的圆形边缘日志和邻接存储组成。图5显示了GARPONE架构的高级概述混合存储分几个阶段进行管理（见第5节）。具体地，在日志记录阶段期间，边缘日志以边缘列表格式以其到达顺序原子地记录传入更新，并且支持高摄取率。我们将未归档的边定义为边日志中尚未移动到邻接存储的边。当它们的数量超过归档阈值时，并行归档阶段开始，其将最新的边合并到邻接存储以创建新的邻接列表快照。这个持续时间被称为一个时期。在持久化阶段，边缘日志以异步方式写入磁盘，需要支持二十九P. Kumar和H.H. 黄ACM Transactions on Storage，Vol.号154、第二十九条。出版日期：2020年1月用于完全恢复。在本文中，我们使用数据摄取来表示新到达的边已经被存储到邻接存储中。因此，GOnE是一种内存中的图形数据存储，具有较弱的持久性保证，并将快照隔离作为其数据一致性，这比支持事务的完全可串行化略弱，但比NoSQL数据存储提供的读提交隔离级别更强，如Stinger [23]或Trinity [79，90]。由于日志记录阶段，未归档的边批量移动到邻接存储，这使得许多优化能够提高归档阶段的性能（第5.1.2节），并减少邻接存储的内存消耗（第5.2节）。这些技术结合在一起，使GSDONE的性能非常接近静态图形引擎。为了有效地创建和管理不可变图版本，以便在存在传入更新的情况下进行实时数据分析，我们提供了一组GraphView API（在第6节中讨论），用于不同类别的分析数据访问具体来说，静态视图API用于批处理，而流视图API用于流处理。在内部，视图利用双版本化技术，其中两种格式的版本化能力被利用，以便以非常低的成本更快地创建当前数据的快照。例如，通过使用邻接存储的最新粗粒度版本和未存档边缘的最新细粒度版本，可以容易地组成实时静态视图。数据重叠技术允许GSDONE保持所创建视图的原始组成不变，从而保证其数据访问而不干扰数据管理操作。重要的是要注意，GraphView还为分析提供了灵活性，可以权衡传入更新的数据可见性粒度以获得更好的分析性能，即，分析人员可以选择其感兴趣的数据摄取类型。例如，偏好仅在批量更新上运行的分析将访问最新的邻接存储，并且因此避免与从未被源顶点索引的非存档边访问最新边相关联的成本。尽管其简单性，但数据可见性的抽象是非常强大的，因为它允许高性能细粒度摄取，但向那些对细粒度摄取不感兴趣的分析者提供批量更新的性能。换句话说，GOnE将细粒度摄取的成本从数据写入路径移到那些真正对细粒度摄取感兴趣的分析的数据读取路径。所有其他数据读取路径提供了一个批量更新系统的perfor-曼斯。3.3重大分歧G+ OnE在一些主要方面与数据库、图形批处理分析、图形流分析和键值存储在本小节中，我们将概述这些差异。在数据库中，可以提供类似于邻接列表图形格式的功能。例如，数据库可以创建一个简单的模式，以将包含源顶点和目的地顶点的图形边存储在边表中。边缘表的数据类似于边缘列表格式。在边表的源顶点中创建索引会产生类似于邻接列表的结构在这种情况下，数据库更新边缘列表日志结构（用于日志记录目的），并在同一线程上下文中更新索引结构（归档到邻接存储）Stinger [23]没有任何日志结构，只维护一个索引结构，但工作方式相同，即，更新索引结构发生在更新线程的线程上下文中然而，G OnE在单独的线程上下文中更新它们两者，同时延迟索引结构的更新，以优化边缘，从而实现更好的整体摄取吞吐量。G OnE与基于快照的图形批量分析的主要区别在于，G OnE能够创建动态图[17]，LLAMA [59]等GRA pH OnE：一个用于演化图实时分析的数据存储二十九ACM Transactions on Storage，Vol.号154、第二十九条。出版日期：2020年1月细粒度快照，并通过使用数据可见性抽象的分析控制这些快照的数据访问。数据库和基于快照的图形批处理分析和G OnE都在与数据摄取不同的线程上下文中运行分析对于图流分析，日志结构的更新与分析分开进行在流引擎和先前的流引擎中。主要区别在于索引结构更新（归档阶段）的上下文中。先前的图流引擎在以下中执行归档阶段：使用map、join和group-by等操作符的流分析上下文（如Naiad [64]，GraphTau [34]等）或者使用特定的实现（如Kickstarter [85]，GraphBolt [61]等），然后是实际的流计算。然而，GOnE将归档阶段移出了分析管道，即，归档与实际的流计算并行发生，这导致总体上更好的性能。由于归档和计算的重叠性质，GSPONE成为有史以来第一个可以从同一索引结构启用并发流分析的系统。即使是基于快照的流分析系统，如Kinerograph [17]也不能同时执行两类流分析：那些需要访问整个数据的流分析，以及那些需要窗口访问的流分析，如Kinerograph，提出了一种不同的快照技术，作为数据窗口访问的未来工作（参见文章[17]中的第6.3节）。现有的流分析可以决定部署同一流分析引擎的多个实例来运行并发流分析，但也会产生单独的邻接存储。键值存储本机只提供三个基本操作：PUT、GET和NULL。然而，APPEND操作是图形系统支持图形数据摄取的必备要求新的边插入可能意味着在源顶点（键）的邻居列表（值）中附加一个类似地，删除边需要从源顶点的邻居列表中删除一个许多现有的图分析系统（诸如Kineograph、Trinity等）另外在键值存储之上实现图形层以支持该APPEND操作。在Trinity中，键值存储顶部的附加操作使用写时复制：边添加需要从内存中复制源顶点（键）的先前邻居列表（值），然后将新邻居附加到邻居列表，最后将整个邻居列表写入新的内存位置。然后，他们提供了一些优化，以减少每次追加时的迁移。显然，键值存储本身并不适合存储不断变化的图形数据。然而，GRA-PHOnE提供了邻接列表的本地实现，内置了对AP- PEND操作的支持，而不使用写时复制方法。最后，G OnE数据存储将所有不同类别的分析引入单个系统，允许使用GraphView接口从同一数据存储中同时执行这些分析在本文中，我们专注于数据存储设计和优化，并通过讨论和实验证明其数据存储抽象和优化技术可以集成到许多类别的分析引擎中，以提高性能。为此，我们将尽可能多地实施先前工作中建议的实际分析，以进行公平比较，同时以我们的方式进行数据管理。4混合存储和版本化在本节中，我们首先介绍混合存储的内部结构，然后讨论版本控制。4.1混合商店图6所示的混合存储设计由一个小的圆形边缘日志组成，用于以边缘列表格式记录最新更新对于删除的情况，我们使用墓碑，特别是二十九P. Kumar和H.H. 黄ACM Transactions on Storage，Vol.号154、第二十九条。出版日期：2020年1月–图六、 从时间t0到t9到达的数据的混合存储：顶点数组包含指向每个边数组的第一个和最后一个块的指针，而度数组包含删除和添加的边计数。然而，为了简洁起见，只显示了指向顶点数组中第一个块的指针和度数组中的总计数。边日志添加新条目，但是边的源顶点ID的最高有效位（MSB）被设置为表示其删除，如图6所示，用于在时间t7删除边（2，4）。邻接存储以邻接列表格式保存较旧的数据。邻接存储由顶点数组、逐顶点边数组和多版本度数组组成。顶点数组包含每个顶点的标志和指向边数组的第一个和最后一个块的指针添加一个新的顶点是通过在每顶点标志中设置一个特殊位来完成的。顶点删除在同一标志中设置另一位，并将其所有边作为删除边添加到边日志中。这些位帮助G_ n e垃圾收集删除的顶点ID。边数组包含邻接列表的每个顶点的边。它可以包含许多小的边缘块，每个边缘块包含块中边缘的计数和指向下一个块的内存指针。边缘块的连接被称为链接。边添加总是发生在每个顶点的边数组的末尾，这可能需要分配一个链接到最后一个块的新边块。图6示出了ID为1到2的顶点的链式边阵列。4用于在t4到t7之间到达的数据更新。邻接列表将边删除视为添加，但边数组中删除的边条目保留原始边的负位置，而实际数据根本不修改，如edge（ 2，4）所示。因此，删除永远不会破坏先前计算的收敛，因为它不会修改计算的数据集。度数组包含每个顶点的相邻边的计数，并且是支持邻接列表的多版本化的最重要的数据结构，因为来自较旧的邻接存储快照的度数组甚至可以从最新的边数组中识别要访问的边，这是由于后者的仅附加属性。我们利用这个属性，并自定义度结构，提供快照功能，即使在存在的数据删除。因此，GOnE中的度数组是多版本的，以支持邻接存储快照。它保留每个顶点的总添加和删除边计数。这两个计数都有助于有效地获得有效的相邻边，因为客户端可以进行精确的内存分配（请参阅表3中的get-nebrs-*（）API）。当为顶点添加或删除一条边时，在每个历元中都会为该顶点在度数组中添加一个新条目。图6中显示了两个时期t0t3和t4t7的度数组的两个不同版本S 0和S 1。可以注意到，如果顶点中没有后续活动，则度节点在历元之间共享。例如，ID为5和6的顶点的相同度节点对于中的两个时期都有效。GRA pH OnE：一个用于演化图实时分析的数据存储二十九ACM Transactions on Storage，Vol.号154、第二十九条。出版日期：2020年1月图6. 当对应的邻接存储快照引退时，旧版本的度数组节点被垃圾收集不被任何分析活动地使用，并且通过全局快照列表使用引用计数机制来跟踪，这将很快讨论。例如，如果快照S 0被引退，则具有ID 1-4的顶点的快照S 0的度节点可以由稍后的快照（例如，S2）的情况下。度节点的垃圾收集是归档阶段的一部分（见5.1.2节）。顶点阵列与度阵列分离，以更容易实现邻接列表的多版本化，因为当对应的快照引退时，对应于较旧快照的度阵列节点将被释放并回收，而不影响其他数据结构，诸如由分析主动访问的边缘阵列全局快照列表是快照对象的链接列表，用于管理每个时期的边缘日志和邻接存储之间的关系每个节点都包含到创建邻接列表快照的边缘日志的绝对偏移量，以及使用此邻接列表快照捕获视图数量的引用计数全局快照列表中的新条目在每个时期之后被创建，并且这意味着最后时期的边缘日志数据已经被原子地移动到邻接存储，并且现在对世界可见加权图。边权重通常与目的地顶点ID一起嵌入在边数组中。一些图具有静态权重，例如，企业网络中的边权重可以表示两个节点之间的网络速度。然后将权重变化内部地视为边删除，然后是边添加。然而，如果边权重是动态的，诸如网络拥塞，则如果保持可配置的时间窗口，则这样的权重变化适合于各种流分析，例如，网络流中的异常检测。在这种情况下，GW0nE被配置为将权重变化视为新的边缘以帮助这种分析。因此，流图将不使用我们在本小节开始时讨论的墓碑。数据流的一个例子。图6中给出了G_（？）从时间t0到t9有10条边的添加和删除，并且创建邻接列表的两个快照。从时间t0到t3，所有进入的边都被记录在边日志中。在t4时，归档开始将这些边缘日志数据移动到邻接列表，与日志记录并行在t4到t7期间，新的边被记录在边日志中。G OnE再次开始将最后四个更新移动到邻接列表中，而新到达的更新则从t8开始记录在边缘日志中。在t9结束时，边日志包含两个尚未移动到邻接存储的边。4.2双重版本控制和数据重叠G OnE使用双重版本控制来创建即时只读图形视图（快照隔离），以通过利用边缘日志的细粒度版本控制属性和邻接列表格式的粗粒度应该注意的是，邻接列表每个时期提供一个版本，而边日志每个时期支持多个版本，与在时期期间到达的边的数量一样多。因此，双重版本控制在一个时期内提供了许多版本，这是静态视图的基础，不应与邻接列表快照混淆。在图6中，时间t6处的静态视图将是邻接列表快照S0加上从t4到t6的边。两个存储之间的少量数据重叠保持视图的组成完整，并且即使当边缘日志数据被移动到邻接存储以创建新的邻接列表版本时，也可以访问视图因此，两个存储都具有相同数据的几个时期的副本对于一个或多个长期运行的迭代分析，我们可以使用持久的边缘日志或非归档边缘的私有副本来提供数据重叠，以便分析可以避免干扰边缘日志的数据管理操作。二十九P. Kumar和H.H. 黄ACM Transactions on Storage，Vol.号154、第二十九条。出版日期：2020年1月图7.第一次会议。圆形边缘日志设计显示各种偏移或标记。 持久阶段的标记与存档类似，被省略。5数据管理和优化数据管理面临的关键问题是最小化非归档边缘的大小，提供原子更新，数据排序和清理旧快照。顶点和边的添加和删除以及边权重修改都被认为是原子更新。5.1数据管理阶段图5描述了数据管理操作的内部结构它由四个阶段组成：日志记录、归档、持久性和压缩。客户端线程发送更新，并且在同一线程上下文中同步记录到边缘日志。归档阶段使用许多工作线程将未归档的边移动到邻接存储，其中一个工作线程承担主线程的角色;这称为归档线程。持久阶段发生在一个单独的线程中，而压缩是多线程的，但发生得更晚。当未存档的边的数量超过阈值（称为存档阈值）时，客户端线程唤醒存档线程和持久线程以开始存档和持久阶段。日志记录阶段照常与它们并行进行。此外，存档线程和持久线程在每个阶段结束时检查是否存在任何未存档的边，以重复其过程或等待超时工作。边缘日志有一个独特的偏移量或标记，即head，用于记录，每次摄取一个边缘时，它都会增加，如图7所示。对于存档，G OnE管理一对标记，即，存档操作从尾部存档标记到头部存档标记发生，因为头部将由于新的更新而保持移动持久阶段也有一对标记可供使用。标记总是递增，并与模运算符一起使用5.1.1记录阶段。如果需要，传入的更新将转换为数字标识符，并获取边缘列表格式。顶点标签到顶点ID之间的映射使用散列表管理。将顶点ID映射到顶点名称的反向映射在内部管理很多时候，传入数据可能直接包含边中的一对唯一顶点ID在这种情况下，用户可以配置GOnE直接使用现有的ID空间。在任一种情况下，通过头部的原子增量在边缘日志内声明唯一点，并且将边缘写入使用头部上的模运算计算的点。源顶点还存储操作符（第4节），添加或删除，以及边。更新的原子性通过头部的原子增量和将边缘日志倒回计数的最低有效位写入目的地顶点ID的最高有效位来确保。这在写入源顶点之后写入，并且每次边缘日志倒回时在0和1之间交替。因此，边缘日志的读取器可以弄清楚它是否正在读取最新数据、旧数据或部分更新。因此，对于边日志中的每条边，源顶点的MSB包含删除信息，而目的顶点的MSB包含倒带信息，并且以该顺序写入。GRA pH OnE：一个用于演化图实时分析的数据存储二十九ACM Transactions on Storage，Vol.号154、第二十九条。出版日期：2020年1月图8.第八条。 边分片将未归档的边根据它们的源顶点ID分成许多缓冲区，以便每个顶点的边数组可以保持边日志到达顺序并启用非原子归档。边缘日志由于其循环性质而在日志记录阶段中被自动重用，被更新的更新覆盖。因此，如果整个缓冲区被填满，日志记录可能偶尔会被阻塞，因为存档或持久性阶段可能无法跟上。我们保持足够大的边缘日志，以避免频繁的阻塞。在阻塞客户端线程的情况下，当归档或持久阶段完成时，它们将被唤醒。5.1.2第二阶段。该阶段将未归档的边从边日志移动到ad- jacency存储。这个阶段有许多阶段，下面将进行讨论。边缘分片。简单的多线程归档，其中每个工作者可以直接在非归档边缘的一部分上工作，可能无法保持数据顺序不变。如果删除发生在同一时期内添加边之后，则该边在边阵列中可能会根据两个数据点的存档顺序而变为活动或死亡为了避免这种排序问题，我们提出了一个边缘分片技术。归档阶段（图8）中的边分片阶段根据边日志到达来维护每个顶点的边，以解决排序问题。它基于其源顶点ID的范围将未存档的边分片到多个本地缓冲区，即，每个局部缓冲器包含属于几个特定源顶点的边我们的实现确保本地缓冲区中的每个顶点的边与边日志的到达顺序相同这通过扫描边缘日志两次来实现在第一次扫描中，每个工作线程计算其对所有本地边缘缓冲区的贡献，并且在第二次扫描中，工作线程将边缘复制到那些本地缓冲区中的对应槽对于无向图，本地缓冲区中的总边计数是非存档边计数的两倍，因为反向边的排序也被管理。对于有向边，两个方向都有自己的本地缓冲区。因此，每个边被存储两次，一次在正向方向上，另一次在反向方向上。然而，GOnE提供了一种避免两次存储边的方法，在本文中称为unigraph非原子核边缘分片具有避免使用原子指令来填充边缘阵列的附加优点，即，每个本地缓冲器中的边被并行存档而不使用任何原子指令。工作负载分配需要一个启发式算法，因为在线程之间不可能平均分配，因此最后一个线程可能会分配更多的工作。为了处理工作线程之间的工作负载不平衡，我们创建了更多的本地缓冲区，其顶点范围比可用线程小，并为每个线程分配不同数量的本地缓冲区，以便每个线程获得近似相等数量的边进行存档。这里的想法是给每个线程分配稍多于相等的工作，这样所有线程都是平衡的，而最后一个线程要么是平衡的，要么是轻负载的。二十九P. Kumar和H.H. 黄ACM Transactions on Storage，Vol.号154、第二十九条。出版日期：2020年1月此阶段分配新的度节点，或者可以重用旧度数组版本中的相同节点（如果它们未被任何分析使用）我们遵循这些规则来重用旧版本中的度数组。我们通过分析使用每个epoch的引用计数来跟踪度数组的使用情况[42]，如果在该epoch内创建的所有静态视图都已过期，则可以重复使用，即，引用被降为零（不被任何正在运行的分析使用）。它还确保新创建的视图使用最新的邻接列表快照，而该快照永远不会被释放。然后，该阶段填充度数组，并在填充链接的边缘块之前为这些块分配内存如果参与顶点的前一个边数组存在，则新的边块链接到它;否则，在顶点数组中为新的边块创建一个新条目然后，我们创建一个新的快照对象，用相关的细节填充它，并将其原子地添加到全局快照列表中。在归档阶段结束时，归档线程将尾归档标记原子地设置为头归档标记的值，并唤醒任何被阻塞的客户端线程。5.1.3持久阶段和恢复。 边缘日志数据定期附加到单独线程上下文中的持久文件，而不是立即记录到磁盘，以避免每次边缘到达期间IO系统调用的开销。此外，除非调用fsync（），否则这将不能保证持久性。日志记录使用缓冲的顺序写入，并且如果边缘日志被覆盖，则允许缓冲区高速缓存用作用于访问未归档边缘的持久的边缘日志是整个摄取数据的前缀，因此在计划外关闭的情况下，GOnE可能会丢失一些恢复依赖于上游备份，该备份将最新数据保留一段时间，例如Kafka [44]，并对丢失的数据进行重放，并在整个数据上创建邻接列表。恢复比在边缘级别构建数据结构更快，因为只有归档阶段涉及处理大量数据。或者，可以将持久存储器用于边缘日志，以在每次更新时提供耐久性[47]。持久阶段还从旧的时间窗口执行邻接存储数据的增量检查点，并释放与之相关联的内存这对于诸如LANL网络流之类的流数据很有用，其中旧的邻接数据可以在磁盘中设置检查点，因为最新时间窗口内的内存中邻接存储足以进行流分析。默认情况下，它是不启用的，因为它会在批量分析或流分析完全访问的