一种面向大规模社交网络的图数据存储及查询方法
一种面向大规模社交网络的图数据存储及查询方法
【技术领域】
[0001]本发明涉及一种面向大规模社交网络的图数据存储及查询方法，属于软件技术领域。
【背景技术】
[0002]目前，图数据存储的主流做法是将图数据经过预处理，转化为边和顶点的记录，以顺序数据集的形式存储在分布式文件系统的大文件中。访问图数据时，以顺序扫描的方式访问存储图数据的大文件。该组织方式无法为多轮迭代的图计算应用提供有效的数据存储和访问性能，为了提高图数据的访问性能，图数据的内存管理技术成为了一个重要的趋势，如 Trinity，Giraph 等。
[0003]Neo4j是采用Key-Value存储模型的图数据库，最基本的存储单位是顶点和边，当广度遍历BFS时，获取某一顶点邻域操作的性能明显比以顶点邻域作为基本存储单位的系统要低。Neo4j所有的数据存储在磁盘上，采用内存缓存加速数据访问，可以调节内存缓存的大小，获得最佳的性能。
[0004]Trinity是由微软亚洲研宄院设计的基于内存云的图计算引擎。采用基于内存的Key-Value存储，其中key是图顶点的唯一 ID，用以定位寻址cell，cell是包含该顶点邻域内的相邻顶点信息的任意长度的连续内存字节块。图数据的每个顶点对应一个cell，cell存储在trunk中，trunk是大小不超过2GB的连续内存。
[0005]Redis也采用Key-Value存储，但是Redis只能处理集群内存可以容纳下的图数据。
[0006]Neo4j是采用Key-Value存储模型的图数据库，然而当图数据规模显著大于内存缓存的大小时，其性能也随着显著降低；当访问异地数据时，Neo4j采用按需请求的方式，无法充分利用带宽。
[0007]Trinity是由微软亚洲研宄院设计的基于内存云的图计算引擎。当数据频繁更新时，插入和删除等操作会使得cell变大或者缩小。当cell变大之后，现有的存储区域无法容纳，就需要开辟更大的存储空间装载cell，将cell从原来位置移动到新的位置；当cell缩小之后，原来的存储cell的空间中缩小的部分空余出，会产生很多内存碎片。由此可见，cell的增大和缩小会形成大量的内存碎片，从而削弱内存的利用率。Trinity采用内存紧缩和预分配更大内存的方式解决外部碎片的问题。不过无论采用何种方法，数据在内存中的搬运移动是不可避免的，并且该操作是非常耗时的。因此，在图数据频繁更新的场景下，Trinity的性能表现不理想。在Trinity中，当内存无法容纳全部图数据时，部分trunk会位于磁盘上。当请求的cell不在内存时，就需要将目标trunk全部换入内存，由于图数据访问具有随机性，数据访问的局部性很差，多个连续请求的cell有可能不在换入内存的trunk中，因此需要将新的trunk换入。在远程数据访问方面，Trinity采用按需请求的方式。
[0008]Redis也采用Key-Value存储，当图数据的数据量不断增长，超过内存容量时，只能依赖增加机器节点数目方式。当集群规模增加时，需要重新划分数据，并且做数据迀移。Redis的数据划分交由客户端完成，服务端程序无法代理异地图数据的请求。
[0009]由以上研宄工作可知，图计算的数据访问需求以及图数据的自身特点对图数据的存储提出了挑战，传统的数据存储方式比如文件系统或者分布式文件系统和Key-Value存储模型的图数据库难以高效的支持图数据访问和更新，进而不能有效的支持图计算。因此，需要根据图数据的访问特性以及图数据本身的特点设计高效的图数据存储系统。
【发明内容】
[0010]本发明的目的在于针对社交网络数据的海量性、频繁更新、随机访问以及稀疏性等特点，提供一种面向大规模社交网络的图数据存储及查询方法。
[0011]本发明能够满足邻域的随机访问。本发明设计了一种基于邻域的三级图数据存储结构。以顶点邻域为基本存储单位，顶点邻域是由固定大小内存block构成的双向链表，该双向链表中包含该顶点的所有关联边的信息，block可被直接寻址。
[0012]本发明采用零移动的数据更新机制。我们设计了一种适合图数据频繁更新的内存组织方法。图数据更新时，由block池负责block的分配和回收。和回收引起顶点邻域的缩小或者扩增时，我们只是修改双链表的首尾，并且不必紧缩存储空间消除外部碎片，也不必分配更大存储空间，将数据从原来地方搬移到新分配的空间中。此机制不但提高了内存的使用率，而且也解决了其他解决方案所面临的紧缩和移动操作。
[0013]本发明采用感知应用的远程预取策略。图数据的单次数据请求的数据访问量少，引起频繁的远程1操作。使用该策略，在当前的异地数据请求处理时，预测后续计算的所需数据，然后该预测数据与当前请求数据一同返回给客户进程，缓存在其本地。通过该机制能够显著降低1次数，提供数据访问的可预测性和有效性。本发明分析总结常见的图算法，根据每轮更新中需要参考图中的哪些顶点，这些算法可以分为两类，即邻域算法和非邻域算法。在邻域算法中，每一轮迭代更新每个顶点属性值时仅需访问相邻顶点的值。而在非邻域算法中，更新每个顶点属性值还需要访问除邻域外其它顶点的值。
[0014]本发明的技术方案为:
[0015]一种面向大规模社交网络的图数据存储方法，其步骤为:
[0016]I)数据存储管理器对收到的图数据采用Key-Value方式存储，其中以图数据的顶点ID为Key，以顶点邻域为Value ；
[0017]2)对每一顶点邻域的数据存储:将与该顶点邻域对应顶点相连的多条边以时间戳有序存储到固定大小的内存块Block中，并使用链表结构将所占用的内存块Block构成Block双向链表，将该顶点的属性信息和指向该Block双向链表头部和尾部的索引信息存储到一数据结构Vertex中。
[0018]进一步的，所述内存块Block由一负责存储资源分配的Block池管理器进行分配与回收；所述Block双向链表中的内存块Block包括三部分:第一部分为指向Block双向链表中当前内存块Block的前一个内存块Block的指针，第二部分为指向Block双向链表中当前内存块Block的后一个Block的指针，第三部分为当前内存块Block存储的边。
[0019]进一步的，所述步骤2)中，当一顶点有新边需要存储到顶点邻域时，将该新边按时间戳排序，查看Block双向链表头部的Block是否未满，如果未满，则将该新边追加在该Block的头部；如果头部的Block已满，则由Block池管理器分配一新的内存块Block并添加到该Block双向链表的头部，然后将该新边存储到该新内存块Block中。
[0020]进一步的，每一所述内存块Block中设有一数据域，用于保存所存边的时间戳区间；当对顶点领域中的边进行删除时，从Block双向链表尾部的内存块Block开始选取一边，如果该边的时间戳小于尾部内存块Block的时间戳区间下界，则结束删除操作，如果该边的时间戳大于该时间戳区间的上界，则从该Block双向链表末尾移除该内存块Block;如 果该边的时间戳位于该时间戳区间内，则扫描该内存块Block中的边，删除比该边的时间戳早的边。
[0021]进一步的，所述数据存储管理器将存储资源分成两类:粗粒度存储资源和细粒度存储资源，所述数据存储管理器的内存中设置有界缓存窗口 ；其中所述粗粒度存储资源用于存储设定的大文件，并常驻于内存，所述细粒度存储资源用于存储按需分配的小文件；所述数据存储管理器按需将细粒度存储资源载入该有界缓存窗口，当该有界缓存窗口被占满，需要加载新的细粒度存储资源时，采用缓存替换算法将该有界缓存窗口中已有的细粒度存储资源换出，然后载入新的细粒度存储资源。
[0022]进一步的，所述粗粒度存储资源和所述细粒度存储资源均划分成固定大小的所述内存块Block，每一内存块Block拥有唯一的Block ID。
[0023]进一步的，所述数据存储管理器首先分配粗粒度存储资源的内存块Block，当粗粒度存储资源耗尽时，开始按需地动态地分配细粒度存储资源在内存块Block。
[0024]如权利要求5所述的方法，其特征在于，所述数据存储器定期地扫描图数据，将过期的图数据从所述粗粒度存储资源中删除并转存到所述细粒度存储资源中。
[0025]一种图数据查询方法，其特征在于，当数据存储管理器收到访问顶点V的访问请求时，数据存储管理器将该顶点V及其k阶邻域传输给请求者；请求者将返回数据缓存在本地，下次查询时，首先检查本地的缓存，如果不存在查询的顶点，则将访问请求发送给所述数据存储管理器。
[0026]进一步的，所述顶点V的k阶邻域为从该顶点V出发经过最短距离k条边可达的全部顶点构成的集合。
[0027]与现有技术相比，本发明的积极效果为:
[0028](I)能满足动态更新。社交网络用户频繁产生数据，在实际应用中，数据分析对数据的时效性具有很高的要求，用户的行为产生的新数据需要不断的加入。
[0029](2)适合处理数据稀疏的场景。在社交网络中，用户的好友数目的差别很多，少数用户(如大V)，拥有很多好友，而众多普通用户的好友数目稀少，从统计角度看，社交网络数据是平均出度很小的极度稀疏图。
[0030](3)适合随机访问。在访问图数据的过程中，不同于访问顺序数据集，一般先访问某个顶点，然后访问相邻顶点，再次访问相邻顶点的相邻顶点，如此不断地从一个顶点出发，由近及远，最后完成对整个图的遍历。
【附图说明】
[0031]图1本发明方法中的数据存储管理；
[0032]图2为顶点邻域的存储模型；
[0033]图3为本地写实验结果对比图；
[0034]图4为本地读实验结果对比图；
[0035]图5为实际数据和存储资源消耗对比图；
[0036]图6为远程写的实验结果对比图；
[0037]图7为远程读的实验结果对比图；
[0038]图8为数据更新的实验结果对比图；
[0039]图9远程预取和非预取的性能对比图。
【具体实施方式】
[0040]以下结合附图对本发明的原理和特征进行描述，所举实例只用于解释本发明，并非用于限定本发明的范围。
[0041]本发明可以分为三部分:零移动的数据组织策略、自适应数据规模的存储管理策略以及应用感知的异地预取策略。
[0042]零移动的数据组织策略
[0043]图数据增量更新是指将产生的新边插入图中和从图中删除过时的旧边。将社交媒体用户的每时每刻的活动足迹产生新鲜图数据需要予以存储，而图数据中不再具有使用价值的过时图数据予以删除。
[0044]本文采用Key-Value存储，以顶点ID做Key，以顶点邻域做Value。顶点邻域的数据组织特点有:1)采用以时间戳将顶点相邻的边有序的存储到Block双向链表中，便于从链表的头部插入新边，从尾部删除旧边。2)为了降低边在双向链表的存储代价，将与顶点相连的多条边顺序存储在固定大小的内存块Block中，存储同一顶点的边的block块构成Block双向链表。Block由专门负责存储资源分配的Block池管理器负责分配回收。3)顶点邻域由数据结构Vertex和Block链表构成，其中Vertex是用户自定义的C语言的结构，其中包含了顶点的属性信息和指向Block双向链表头部和尾部的索引信息。
[0045]当向顶点邻域插入新边时，将新边按时间戳排序，先查看链表头部的Block是否未满，如果没有满，就追加在该Block的头部；如果头部的Block已满，且依然有待插入的新边，则由Block池管理器分配新的Block，添加到链表的头部，用待插入边填充新Block。重复该过程，直至更新完全部的新边。当删除顶点邻域中的老化边时，从Block双链表尾部的Block开始，为了快速的删除旧边，Block中有专门的数据域保存所存边的时间戳区间。如果想要删除的边的时间戳小于时间戳区间的下界，则结束删除操作；当待删边的时间戳大于时间戳区间的上界，则从链表末尾移除该Block，通过Block管理池回收已删除的Block ;如果当待删除边的时间戳出现在时间戳区间中，则扫描该Block中的边，删除比待删除边的时间戳老的边，并结束操作。
[0046]采用Block双向链表存储以时间戳有序的出边的方式组织顶点邻域，有诸多优点。第一，避免采用单条边存储的小额内存空间的频繁动态分配和存储过多额外的元数据。因为图数据的更新比较频繁，而每条边的数据量比较少，更新操作引起小额内存的频繁动态分配；并且边中的元数据相对于实际数据的比率也加大，导致内存内存的分配效率和利用率降低，而且单挑边的存储也不利于访问顶点邻域。第二，避免了采取顶点的全部出边整体存储的方式不利于图数据动态更新的问题，采用整体的存储，顶点的全部出边存储blob (动态分配的长度不固定的连续内存空间)，新边插入操作会导致原存储空间耗尽，必须开辟足够大的新存储空间，挪动原来的数据，并插入新边。旧边删除到操作会导致存储空间空余数量可观的不可用的内部碎片。通常采用定期紧缩操作，数据移动重新整理图数据，以消除碎片。这种组织方式虽然访问顶点邻域具有很高的性能，但是紧缩操作会显著影响图数据的随机增量跟新的效率。
[0047]在本系统中，充分考虑了图数据的特征以及对图数据的访问特性，设计了一种图数据的顶点邻域存储模型，如图2所示。每个Block由三部分组成，第一部分为指向前一个block的指针，第二部分为指向后一个block的指针，第三部分为该block存储的边。此模型可以有效地支持图数据更新。
[0048]本文提出的图数据存储方法在数据更新方面与业界使用的方式有如下几点不同:
[0049]首先，Redis和Neo4j的数据存储采用连续分配的方式，但随着数据不断地更新，超出已分配存储块时，需要分配更大的连续内存块，然后将原来的数据挪动到新块中，并将新数据插入。频繁的数据更新，会造成数据的频繁挪动。尽管Redis采用了一种预先分配机制，每次分配的内存多于实际需要的内存数目，以应对未来可能的数据扩增。但没有从根本上解决内存数据挪动的问题。而本发明采用链接分配的方式，通 过block管理池管理空闲内存块，已分配的内存块链接成双向链表，数据的更新发生在链表末尾，不用引起数据的挪动和复制。
[0050]其次，在Redis和Neo4j中，图数据的顶点和边分别存储，而本文提出的方法直接存储图的顶点邻域。存储相同规模的图数据，Redis和Neo4j需要启动更多数目的网络I/Oo Redis和Neo4j启动1/0的次数为图顶点数目和边数目之和，而本发明启动1/0的次数为图顶点数目，而在社交媒体图结构中，图的边数目是远远大于图顶点数目。即便可以采用批量数据传输，由于Redis和Neo4j数据访问采用类似SQL的查询语言，需要将写入的数据在客户端转换为批量查询语句，并且在服务器端经过解析执行，转换和解析影响了效率。而本发明本身采用顶点及其邻域作为数据组织单位，在远程访问过程中，客户端采用buffer缓存待写入目标机器的数据，当缓冲区满，或者超时事件发生，才将buffer中的数据批量地发送给目标机器。
[0051]最后，Neo4j每次数据更新，都是事务操作，服务期需要将数据写入同步到磁盘文件中。而Redis采用RDB的机制，通过后台1/0线程将内存中某一时间断面的数据写入到磁盘文件中，每次写入过程会阻塞其他更新。而本发明在更新时，采用mmap接口，在内存区域和磁盘文件之间建立映射，数据写入到内存区域，由操作系统内核负责将数据更新同步到磁盘文件中。
[0052]综合以上不同点，本发明在做数据更新的过程中在设计上有多个优势，可以达到更高的更新性能。
[0053]自适应数据规模的存储管理策略
[0054]图计算的数据访问具有很高的随机性，采用内存组织数据能够提高数据随机访问效率。然后，图数据的数据规模具有海量性，集群的有限内存无法负载大规模图数据。本文提出了自适应数据规模的内存管理策略，优先使用内存组织图数据，当内存资源耗尽时，容许数据溢出到磁盘中。具体的做法是:将图数据管理系统的可以使用的存储资源分成两类，一类是粗粒度存储资源，另一类是细粒度存储资源。
[0055]粗粒度资源对应本地Linux文件系统的预先分配的大文件，文件大小为2GB、4GB甚至更大，前提是不超过集群单个节点可用内存容量。运行时，粗粒度资源被全部加载，并常驻于内存。细粒度资源对于本地Linux文件系统的按需分配的小文件，文件大小为4MB、8MB，而且小文件的数目随着图数据的增加不断变大。运行时，无法将粗粒度资源和全体细粒度资源全部置于内存，因此在内存中开辟有界缓存窗口，按需将细粒度资源载入窗口。当窗口被占满，需要加载新的细粒度资源时，需要根据缓存替换算法，选择窗口中已有的细粒度资源，将其换出，然后载入新的资源。
[0056]两类资源都被划分成固定大小的Block，全体Block拥有唯一的Block ID，可以根据BlockID随机地访问Block。Block是存储资源的基本分配单位，由Block池管理器负责分配和回收Block。当顶点邻域的Block双向链表头部未满时，需要为新插入边分配新的Block作为链表的头部；当删除顶点邻域的旧边时，需要释放和回事空的Block。所有的Block要么处于空闲状态，要么属于某个指定的顶点邻域。
[0057]资源分配时，可以根据数据的规模动态地选择存储资源。首先从粗粒度资源开始分配，目的是尽量采用内存组织数据。当粗粒度资源耗尽时，开始按需地动态地分配细粒度资源，存储溢出内存的数据。顶点邻域中的边以时间戳有序存储，可以定期地扫描图数据，将过期的图数据从粗粒度资源中删除，转存到细粒度资源中，从而是内存中的数据保持新鲜。
[0058]采用自适应数据规模的存储分配策略，既可以尽力使用内存组织数据，从而提高数据访问的随机性，又允许图数据规模增大时，将数据从内存溢出到磁盘中，解决了海量图数据的管理问题。
[0059]应用感知的异地预取策略
[0060]在本发明中，为了加快异地数据访问的效率，提出了一种感知应用特征的异地预取的机制。通过该机制，更够显著地提高异地数据访问的吞吐率。
[0061]图数据的访问，类似于访问顺序存储的数据，具有明显的局部性。图计算的算法一般基于图的遍历算法。以广度优先遍历为例，访问顶点V时，V的k阶邻域(从顶点V出经过最短距离k条边可达的全部顶点构成的集合)的顶点被访问概率随着k增大而降低，因此，处理V的访问请求时，系统根据顶点位置信息可以预测近期最有可能被访问的顶点，将顶点V和近期最有可能被访问的顶点的数据合并在一起，传输给请求者。请求者将预先取得的数据缓存在本地，下次获取异地数据时，先检查本地的缓存，如果存在，直接访问本地即可，否则向异地请求数据。
[0062]很多图计算框架会顺序地读取图数据的子图的全部顶点，此时，可以采用顺序预取的方式。预取方式的选择要符合图计算的数据访问特点，可以提供多种预取的策略，让用户选择从中选择最佳的预取策略。
[0063]实例I数据访问实例
[0064]本发明测试了本发明以及比较系Redis和Neo4j在不同并发量下的写性能，该写性能取了十个数据集下的平均值，其中在测试图3中，本发明使用NYNN表示。
[0065]由图3可知，本发明本地写性能明显优于Redis和Neo4j，元数据的设计和数据传输格式和数据写入的机制影响了写的性能。首先本发明图数据的划分采用连续的等宽顶点区间，能够通过首次数据写入请求，将元数据缓存在本地，此后使用缓存在本地的元数据进行数据寻址，这样减少了寻址的1开销。写入数据的时候，自己写入本地的内存映射文件中。Redis和Neo4j都提供了方便使用的查询命令/语言，先将用户写入数据的请求，封装成查询命令，然后通过本地网络发送给server，由server负责解析命令，完成查询。
[0066]本发明测试了本发明以及比较系Redis和Neo4j在不同并发量下的读性能，该读性能取了十个数据集下的平均值。
[0067]如图4所示，本地读操作，本发明可以达到GB/s量级，而Redis和Neo4j是1MB/s?lOOMB/s，本发明可以直接将图数据通过_ap接口映射到客户进程的地址空间中，进行操作。而Redis和Neo4j采用查询命令向server请求数据。
[0068]为了反应图数据存储系统的存储效率，本发明比较了多个系统的存储膨胀比，即存储同样多的数据，看内存和磁盘的占用膨胀比。
[0069]如图5所示，对比Redi s，Neo4j和本发明的磁盘使用情况，可以明显的观察到，Neo4j作为基于磁盘的存储系统，占用磁盘空间最大，数据存储的时候，需要存储属性值和属性名，而且属性值采用字符串的形式存储。Redis所需的磁盘存储空间最少，Redis的数据持久化之前，将数据进行压缩。而内存的使用中，Redis的内存使用最大，因为Redis将全部数据加载到内存。Neo4j和本发明都可以配置所需内存的大小。
[0070]本发明测试了本发明以及比较系Redis和Neo4j在不同并发量下的远程写性能，该写性能取了十个数据集下的平均值。
[0071]如图6所示，远程写数据，本发明的性能明显高于Neo4j和R edis。本发明的数据交换采用报文的形式传输字节流。而Redis和Neo4j采用查询命令或语言，降低了数据的传输效率。此外本发明的后台数据写入采用多线程处理，提高的效率。Redis采用事件驱动模型的单线出处理。
[0072]本发明测试了本发明以及比较系Redis和Neo4j在不同并发量下的远程读性能，该读性能取了十个数据集下的平均值。
[0073]如图7所示，远程读操作，本发明采用了数据预取机制，能够批量传输有效数据。而Redis和Neo4j都没有采用预取机制。
[0074]实例2数据更新实例
[0075]本文测试了本发明以及比较系Redis和Neo4j的数据更新性能，该性能取了十个数据集下的平均值。
[0076]如图8所示，对于数据的增量更新，本发明采用了链式的分配方式，能够消除数据插入和删除引起的数据频繁挪动问题。而Redis和Neo4j采用了顺序分配的方式，随着数据的更新，需要挪动数据，重定位数据，在这个过程中，无法进行新的查询处理。
[0077]实例3数据远程访问实例
[0078]本文测试了本发明在有预取机制和非预取的情况下的性能差异。本发明提供多种数据预取机制，便于上层应用更加自己的应用背景选择最佳的数据预取方式。本实验采用BFS预取，实验用到的算法是统计图数据集中图的总边数，算法的思路为:将图的顶点划分为η个分片，每个分片指定一个线程处理，所有线程并行访问本发明中的图数据。线程将访问请求中要访问的顶点放入队列，然后处理队列头部的顶点，访问顶点的邻域，统计顶点边数。如果当前边的终点位于线程所属分片，则将该终点放入队列。不断的循环处理队列的首部，直到队列为空。但所有的线程完成顶点的统计，将结果累计，算法结束。该算法为BFS遍历算法，能够很好的利用BFS预取机制，预取数据在后续的访问中，具有很高的命中率。
[0079] 如图9所示，本发明提供了多种数据预取机制，比如顺序预取，BFS预取和DFS预取。上层的计算框架可以选择最佳的预取方式批量的从异地获取图数据，图数据访问过程中，每次读取数据量比较少，虽然相邻时间的数据读取是可以预测的。通过将大批小量数据的访问积攒成大块数据，可以充分利用带宽资源，降低1启动时间，这样我们可以通过较低的并发获得较高的数据吞吐率。
【主权项】
1.一种面向大规模社交网络的图数据存储方法，其步骤为: 1)数据存储管理器对收到的图数据采用Key-Value方式存储，其中以图数据的顶点ID为Key，以顶点邻域为Value ； 2)对每一顶点邻域的数据存储:将与该顶点邻域对应顶点相连的多条边以时间戳有序存储到固定大小的内存块Block中，并使用链表结构将所占用的内存块Block构成Block双向链表，将该顶点的属性信息和指向该Block双向链表头部和尾部的索引信息存储到一数据结构Vertex中。2.如权利要求1所述的方法，其特征在于，所述内存块Block由一负责存储资源分配的Block池管理器进行分配与回收；所述Block双向链表中的内存块Block包括三部分:第一部分为指向Block双向链表中当前内存块Block的前一个内存块Block的指针，第二部分为指向Block双向链表中当前内存块Block的后一个Block的指针，第三部分为当前内存块Block存储的边。3.如权利要求2所述的方法，其特征在于，所述步骤2)中，当一顶点有新边需要存储到顶点邻域时，将该新边按时间戳排序，查看Block双向链表头部的Block是否未满，如果未满，则将该新边追加在该Block的头部；如果头部的Block已满，则由Block池管理器分配一新的内存块Block并添加到该Block双向链表的头部，然后将该新边存储到该新内存块Block 中。4.如权利要求1或2或3所述的方法，其特征在于，每一所述内存块Block中设有一数据域，用于保存所存边的时间戳区间；当对顶点领域中的边进行删除时，从Block双向链表尾部的内存块Block开始选取一边，如果该边的时间戳小于尾部内存块Block的时间戳区间下界，则结束删除操作，如果该边的时间戳大于该时间戳区间的上界，则从该Block双向链表末尾移除该内存块Block;如果该边的时间戳位于该时间戳区间内，则扫描该内存块Block中的边，删除比该边的时间戳早的边。5.如权利要求1所述的方法，其特征在于，所述数据存储管理器将存储资源分成两类:粗粒度存储资源和细粒度存储资源，所述数据存储管理器的内存中设置有界缓存窗口 ；其中所述粗粒度存储资源用于存储设定的大文件，并常驻于内存，所述细粒度存储资源用于存储按需分配的小文件；所述数据存储管理器按需将细粒度存储资源载入该有界缓存窗口，当该有界缓存窗口被占满，需要加载新的细粒度存储资源时，采用缓存替换算法将该有界缓存窗口中已有的细粒度存储资源换出，然后载入新的细粒度存储资源。6.如权利要求5所述的方法，其特征在于，所述粗粒度存储资源和所述细粒度存储资源均划分成固定大小的所述内存块Block，每一内存块Block拥有唯一的Block ID。7.如权利要求5所述的方法，其特征在于，所述数据存储管理器首先分配粗粒度存储资源的内存块Block，当粗粒度存储资源耗尽时，开始按需地动态地分配细粒度存储资源在内存块Block。8.如权利要求5所述的方法，其特征在于，所述数据存储器定期地扫描图数据，将过期的图数据从所述粗粒度存储资源中删除并转存到所述细粒度存储资源中。9.一种基于权利要求1所述方法存储的图数据的图数据查询方法，其特征在于，当数据存储管理器收到访问顶点V的访问请求时，数据存储管理器将该顶点V及其k阶邻域传输给请求者；请求者将返回数据缓存在本地，下次查询时，首先检查本地的缓存，如果不存在查询的顶点，则将访问请求发送给所述数据存储管理器。10.如权利要求9所述的方法，其特征在于，所述顶点V的k阶邻域为从该顶点V出发经过最短距离k条边可达的全部顶点构成的集合。
【专利摘要】本发明公开了一种面向大规模社交网络的图数据存储及查询方法，本发明数据存储管理器对收到的图数据采用Key-Value方式存储，以图数据的顶点ID为Key，以顶点邻域为Value；对每一顶点邻域的数据存储：将与该顶点邻域相连的多条边以时间戳有序存储到固定大小的内存块中，并构成双向链表，将该顶点的属性信息和索引信息存储到一数据结构中。当数据存储管理器收到访问顶点v的访问请求时，数据存储管理器将该顶点v及其k阶邻域传输给请求者；请求者将返回数据缓存在本地，下次查询时，首先检查本地的缓存，如果不存在查询的顶点，则将访问请求发送给所述数据存储管理器。本发明能满足动态更新、适合处理数据稀疏的场景和随机访问。
【IPC分类】G06F12/06
【公开号】CN104899156
【申请号】CN201510229346
【发明人】周薇, 包秀国, 马宏远, 程工, 冉攀峰, 刘春阳, 王卿, 韩冀中, 庞琳, 李雄, 贺敏, 刘玮
【申请人】中国科学院信息工程研究所, 国家计算机网络与信息安全管理中心
【公开日】2015年9月9日
【申请日】2015年5月7日
【技术领域】
[0001]本发明涉及一种面向大规模社交网络的图数据存储及查询方法，属于软件技术领域。
【背景技术】
[0002]目前，图数据存储的主流做法是将图数据经过预处理，转化为边和顶点的记录，以顺序数据集的形式存储在分布式文件系统的大文件中。访问图数据时，以顺序扫描的方式访问存储图数据的大文件。该组织方式无法为多轮迭代的图计算应用提供有效的数据存储和访问性能，为了提高图数据的访问性能，图数据的内存管理技术成为了一个重要的趋势，如 Trinity，Giraph 等。
[0003]Neo4j是采用Key-Value存储模型的图数据库，最基本的存储单位是顶点和边，当广度遍历BFS时，获取某一顶点邻域操作的性能明显比以顶点邻域作为基本存储单位的系统要低。Neo4j所有的数据存储在磁盘上，采用内存缓存加速数据访问，可以调节内存缓存的大小，获得最佳的性能。
[0004]Trinity是由微软亚洲研宄院设计的基于内存云的图计算引擎。采用基于内存的Key-Value存储，其中key是图顶点的唯一 ID，用以定位寻址cell，cell是包含该顶点邻域内的相邻顶点信息的任意长度的连续内存字节块。图数据的每个顶点对应一个cell，cell存储在trunk中，trunk是大小不超过2GB的连续内存。
[0005]Redis也采用Key-Value存储，但是Redis只能处理集群内存可以容纳下的图数据。
[0006]Neo4j是采用Key-Value存储模型的图数据库，然而当图数据规模显著大于内存缓存的大小时，其性能也随着显著降低；当访问异地数据时，Neo4j采用按需请求的方式，无法充分利用带宽。
[0007]Trinity是由微软亚洲研宄院设计的基于内存云的图计算引擎。当数据频繁更新时，插入和删除等操作会使得cell变大或者缩小。当cell变大之后，现有的存储区域无法容纳，就需要开辟更大的存储空间装载cell，将cell从原来位置移动到新的位置；当cell缩小之后，原来的存储cell的空间中缩小的部分空余出，会产生很多内存碎片。由此可见，cell的增大和缩小会形成大量的内存碎片，从而削弱内存的利用率。Trinity采用内存紧缩和预分配更大内存的方式解决外部碎片的问题。不过无论采用何种方法，数据在内存中的搬运移动是不可避免的，并且该操作是非常耗时的。因此，在图数据频繁更新的场景下，Trinity的性能表现不理想。在Trinity中，当内存无法容纳全部图数据时，部分trunk会位于磁盘上。当请求的cell不在内存时，就需要将目标trunk全部换入内存，由于图数据访问具有随机性，数据访问的局部性很差，多个连续请求的cell有可能不在换入内存的trunk中，因此需要将新的trunk换入。在远程数据访问方面，Trinity采用按需请求的方式。
[0008]Redis也采用Key-Value存储，当图数据的数据量不断增长，超过内存容量时，只能依赖增加机器节点数目方式。当集群规模增加时，需要重新划分数据，并且做数据迀移。Redis的数据划分交由客户端完成，服务端程序无法代理异地图数据的请求。
[0009]由以上研宄工作可知，图计算的数据访问需求以及图数据的自身特点对图数据的存储提出了挑战，传统的数据存储方式比如文件系统或者分布式文件系统和Key-Value存储模型的图数据库难以高效的支持图数据访问和更新，进而不能有效的支持图计算。因此，需要根据图数据的访问特性以及图数据本身的特点设计高效的图数据存储系统。
【发明内容】
[0010]本发明的目的在于针对社交网络数据的海量性、频繁更新、随机访问以及稀疏性等特点，提供一种面向大规模社交网络的图数据存储及查询方法。
[0011]本发明能够满足邻域的随机访问。本发明设计了一种基于邻域的三级图数据存储结构。以顶点邻域为基本存储单位，顶点邻域是由固定大小内存block构成的双向链表，该双向链表中包含该顶点的所有关联边的信息，block可被直接寻址。
[0012]本发明采用零移动的数据更新机制。我们设计了一种适合图数据频繁更新的内存组织方法。图数据更新时，由block池负责block的分配和回收。和回收引起顶点邻域的缩小或者扩增时，我们只是修改双链表的首尾，并且不必紧缩存储空间消除外部碎片，也不必分配更大存储空间，将数据从原来地方搬移到新分配的空间中。此机制不但提高了内存的使用率，而且也解决了其他解决方案所面临的紧缩和移动操作。
[0013]本发明采用感知应用的远程预取策略。图数据的单次数据请求的数据访问量少，引起频繁的远程1操作。使用该策略，在当前的异地数据请求处理时，预测后续计算的所需数据，然后该预测数据与当前请求数据一同返回给客户进程，缓存在其本地。通过该机制能够显著降低1次数，提供数据访问的可预测性和有效性。本发明分析总结常见的图算法，根据每轮更新中需要参考图中的哪些顶点，这些算法可以分为两类，即邻域算法和非邻域算法。在邻域算法中，每一轮迭代更新每个顶点属性值时仅需访问相邻顶点的值。而在非邻域算法中，更新每个顶点属性值还需要访问除邻域外其它顶点的值。
[0014]本发明的技术方案为:
[0015]一种面向大规模社交网络的图数据存储方法，其步骤为:
[0016]I)数据存储管理器对收到的图数据采用Key-Value方式存储，其中以图数据的顶点ID为Key，以顶点邻域为Value ；
[0017]2)对每一顶点邻域的数据存储:将与该顶点邻域对应顶点相连的多条边以时间戳有序存储到固定大小的内存块Block中，并使用链表结构将所占用的内存块Block构成Block双向链表，将该顶点的属性信息和指向该Block双向链表头部和尾部的索引信息存储到一数据结构Vertex中。
[0018]进一步的，所述内存块Block由一负责存储资源分配的Block池管理器进行分配与回收；所述Block双向链表中的内存块Block包括三部分:第一部分为指向Block双向链表中当前内存块Block的前一个内存块Block的指针，第二部分为指向Block双向链表中当前内存块Block的后一个Block的指针，第三部分为当前内存块Block存储的边。
[0019]进一步的，所述步骤2)中，当一顶点有新边需要存储到顶点邻域时，将该新边按时间戳排序，查看Block双向链表头部的Block是否未满，如果未满，则将该新边追加在该Block的头部；如果头部的Block已满，则由Block池管理器分配一新的内存块Block并添加到该Block双向链表的头部，然后将该新边存储到该新内存块Block中。
[0020]进一步的，每一所述内存块Block中设有一数据域，用于保存所存边的时间戳区间；当对顶点领域中的边进行删除时，从Block双向链表尾部的内存块Block开始选取一边，如果该边的时间戳小于尾部内存块Block的时间戳区间下界，则结束删除操作，如果该边的时间戳大于该时间戳区间的上界，则从该Block双向链表末尾移除该内存块Block;如 果该边的时间戳位于该时间戳区间内，则扫描该内存块Block中的边，删除比该边的时间戳早的边。
[0021]进一步的，所述数据存储管理器将存储资源分成两类:粗粒度存储资源和细粒度存储资源，所述数据存储管理器的内存中设置有界缓存窗口 ；其中所述粗粒度存储资源用于存储设定的大文件，并常驻于内存，所述细粒度存储资源用于存储按需分配的小文件；所述数据存储管理器按需将细粒度存储资源载入该有界缓存窗口，当该有界缓存窗口被占满，需要加载新的细粒度存储资源时，采用缓存替换算法将该有界缓存窗口中已有的细粒度存储资源换出，然后载入新的细粒度存储资源。
[0022]进一步的，所述粗粒度存储资源和所述细粒度存储资源均划分成固定大小的所述内存块Block，每一内存块Block拥有唯一的Block ID。
[0023]进一步的，所述数据存储管理器首先分配粗粒度存储资源的内存块Block，当粗粒度存储资源耗尽时，开始按需地动态地分配细粒度存储资源在内存块Block。
[0024]如权利要求5所述的方法，其特征在于，所述数据存储器定期地扫描图数据，将过期的图数据从所述粗粒度存储资源中删除并转存到所述细粒度存储资源中。
[0025]一种图数据查询方法，其特征在于，当数据存储管理器收到访问顶点V的访问请求时，数据存储管理器将该顶点V及其k阶邻域传输给请求者；请求者将返回数据缓存在本地，下次查询时，首先检查本地的缓存，如果不存在查询的顶点，则将访问请求发送给所述数据存储管理器。
[0026]进一步的，所述顶点V的k阶邻域为从该顶点V出发经过最短距离k条边可达的全部顶点构成的集合。
[0027]与现有技术相比，本发明的积极效果为:
[0028](I)能满足动态更新。社交网络用户频繁产生数据，在实际应用中，数据分析对数据的时效性具有很高的要求，用户的行为产生的新数据需要不断的加入。
[0029](2)适合处理数据稀疏的场景。在社交网络中，用户的好友数目的差别很多，少数用户(如大V)，拥有很多好友，而众多普通用户的好友数目稀少，从统计角度看，社交网络数据是平均出度很小的极度稀疏图。
[0030](3)适合随机访问。在访问图数据的过程中，不同于访问顺序数据集，一般先访问某个顶点，然后访问相邻顶点，再次访问相邻顶点的相邻顶点，如此不断地从一个顶点出发，由近及远，最后完成对整个图的遍历。
【附图说明】
[0031]图1本发明方法中的数据存储管理；
[0032]图2为顶点邻域的存储模型；
[0033]图3为本地写实验结果对比图；
[0034]图4为本地读实验结果对比图；
[0035]图5为实际数据和存储资源消耗对比图；
[0036]图6为远程写的实验结果对比图；
[0037]图7为远程读的实验结果对比图；
[0038]图8为数据更新的实验结果对比图；
[0039]图9远程预取和非预取的性能对比图。
【具体实施方式】
[0040]以下结合附图对本发明的原理和特征进行描述，所举实例只用于解释本发明，并非用于限定本发明的范围。
[0041]本发明可以分为三部分:零移动的数据组织策略、自适应数据规模的存储管理策略以及应用感知的异地预取策略。
[0042]零移动的数据组织策略
[0043]图数据增量更新是指将产生的新边插入图中和从图中删除过时的旧边。将社交媒体用户的每时每刻的活动足迹产生新鲜图数据需要予以存储，而图数据中不再具有使用价值的过时图数据予以删除。
[0044]本文采用Key-Value存储，以顶点ID做Key，以顶点邻域做Value。顶点邻域的数据组织特点有:1)采用以时间戳将顶点相邻的边有序的存储到Block双向链表中，便于从链表的头部插入新边，从尾部删除旧边。2)为了降低边在双向链表的存储代价，将与顶点相连的多条边顺序存储在固定大小的内存块Block中，存储同一顶点的边的block块构成Block双向链表。Block由专门负责存储资源分配的Block池管理器负责分配回收。3)顶点邻域由数据结构Vertex和Block链表构成，其中Vertex是用户自定义的C语言的结构，其中包含了顶点的属性信息和指向Block双向链表头部和尾部的索引信息。
[0045]当向顶点邻域插入新边时，将新边按时间戳排序，先查看链表头部的Block是否未满，如果没有满，就追加在该Block的头部；如果头部的Block已满，且依然有待插入的新边，则由Block池管理器分配新的Block，添加到链表的头部，用待插入边填充新Block。重复该过程，直至更新完全部的新边。当删除顶点邻域中的老化边时，从Block双链表尾部的Block开始，为了快速的删除旧边，Block中有专门的数据域保存所存边的时间戳区间。如果想要删除的边的时间戳小于时间戳区间的下界，则结束删除操作；当待删边的时间戳大于时间戳区间的上界，则从链表末尾移除该Block，通过Block管理池回收已删除的Block ;如果当待删除边的时间戳出现在时间戳区间中，则扫描该Block中的边，删除比待删除边的时间戳老的边，并结束操作。
[0046]采用Block双向链表存储以时间戳有序的出边的方式组织顶点邻域，有诸多优点。第一，避免采用单条边存储的小额内存空间的频繁动态分配和存储过多额外的元数据。因为图数据的更新比较频繁，而每条边的数据量比较少，更新操作引起小额内存的频繁动态分配；并且边中的元数据相对于实际数据的比率也加大，导致内存内存的分配效率和利用率降低，而且单挑边的存储也不利于访问顶点邻域。第二，避免了采取顶点的全部出边整体存储的方式不利于图数据动态更新的问题，采用整体的存储，顶点的全部出边存储blob (动态分配的长度不固定的连续内存空间)，新边插入操作会导致原存储空间耗尽，必须开辟足够大的新存储空间，挪动原来的数据，并插入新边。旧边删除到操作会导致存储空间空余数量可观的不可用的内部碎片。通常采用定期紧缩操作，数据移动重新整理图数据，以消除碎片。这种组织方式虽然访问顶点邻域具有很高的性能，但是紧缩操作会显著影响图数据的随机增量跟新的效率。
[0047]在本系统中，充分考虑了图数据的特征以及对图数据的访问特性，设计了一种图数据的顶点邻域存储模型，如图2所示。每个Block由三部分组成，第一部分为指向前一个block的指针，第二部分为指向后一个block的指针，第三部分为该block存储的边。此模型可以有效地支持图数据更新。
[0048]本文提出的图数据存储方法在数据更新方面与业界使用的方式有如下几点不同:
[0049]首先，Redis和Neo4j的数据存储采用连续分配的方式，但随着数据不断地更新，超出已分配存储块时，需要分配更大的连续内存块，然后将原来的数据挪动到新块中，并将新数据插入。频繁的数据更新，会造成数据的频繁挪动。尽管Redis采用了一种预先分配机制，每次分配的内存多于实际需要的内存数目，以应对未来可能的数据扩增。但没有从根本上解决内存数据挪动的问题。而本发明采用链接分配的方式，通 过block管理池管理空闲内存块，已分配的内存块链接成双向链表，数据的更新发生在链表末尾，不用引起数据的挪动和复制。
[0050]其次，在Redis和Neo4j中，图数据的顶点和边分别存储，而本文提出的方法直接存储图的顶点邻域。存储相同规模的图数据，Redis和Neo4j需要启动更多数目的网络I/Oo Redis和Neo4j启动1/0的次数为图顶点数目和边数目之和，而本发明启动1/0的次数为图顶点数目，而在社交媒体图结构中，图的边数目是远远大于图顶点数目。即便可以采用批量数据传输，由于Redis和Neo4j数据访问采用类似SQL的查询语言，需要将写入的数据在客户端转换为批量查询语句，并且在服务器端经过解析执行，转换和解析影响了效率。而本发明本身采用顶点及其邻域作为数据组织单位，在远程访问过程中，客户端采用buffer缓存待写入目标机器的数据，当缓冲区满，或者超时事件发生，才将buffer中的数据批量地发送给目标机器。
[0051]最后，Neo4j每次数据更新，都是事务操作，服务期需要将数据写入同步到磁盘文件中。而Redis采用RDB的机制，通过后台1/0线程将内存中某一时间断面的数据写入到磁盘文件中，每次写入过程会阻塞其他更新。而本发明在更新时，采用mmap接口，在内存区域和磁盘文件之间建立映射，数据写入到内存区域，由操作系统内核负责将数据更新同步到磁盘文件中。
[0052]综合以上不同点，本发明在做数据更新的过程中在设计上有多个优势，可以达到更高的更新性能。
[0053]自适应数据规模的存储管理策略
[0054]图计算的数据访问具有很高的随机性，采用内存组织数据能够提高数据随机访问效率。然后，图数据的数据规模具有海量性，集群的有限内存无法负载大规模图数据。本文提出了自适应数据规模的内存管理策略，优先使用内存组织图数据，当内存资源耗尽时，容许数据溢出到磁盘中。具体的做法是:将图数据管理系统的可以使用的存储资源分成两类，一类是粗粒度存储资源，另一类是细粒度存储资源。
[0055]粗粒度资源对应本地Linux文件系统的预先分配的大文件，文件大小为2GB、4GB甚至更大，前提是不超过集群单个节点可用内存容量。运行时，粗粒度资源被全部加载，并常驻于内存。细粒度资源对于本地Linux文件系统的按需分配的小文件，文件大小为4MB、8MB，而且小文件的数目随着图数据的增加不断变大。运行时，无法将粗粒度资源和全体细粒度资源全部置于内存，因此在内存中开辟有界缓存窗口，按需将细粒度资源载入窗口。当窗口被占满，需要加载新的细粒度资源时，需要根据缓存替换算法，选择窗口中已有的细粒度资源，将其换出，然后载入新的资源。
[0056]两类资源都被划分成固定大小的Block，全体Block拥有唯一的Block ID，可以根据BlockID随机地访问Block。Block是存储资源的基本分配单位，由Block池管理器负责分配和回收Block。当顶点邻域的Block双向链表头部未满时，需要为新插入边分配新的Block作为链表的头部；当删除顶点邻域的旧边时，需要释放和回事空的Block。所有的Block要么处于空闲状态，要么属于某个指定的顶点邻域。
[0057]资源分配时，可以根据数据的规模动态地选择存储资源。首先从粗粒度资源开始分配，目的是尽量采用内存组织数据。当粗粒度资源耗尽时，开始按需地动态地分配细粒度资源，存储溢出内存的数据。顶点邻域中的边以时间戳有序存储，可以定期地扫描图数据，将过期的图数据从粗粒度资源中删除，转存到细粒度资源中，从而是内存中的数据保持新鲜。
[0058]采用自适应数据规模的存储分配策略，既可以尽力使用内存组织数据，从而提高数据访问的随机性，又允许图数据规模增大时，将数据从内存溢出到磁盘中，解决了海量图数据的管理问题。
[0059]应用感知的异地预取策略
[0060]在本发明中，为了加快异地数据访问的效率，提出了一种感知应用特征的异地预取的机制。通过该机制，更够显著地提高异地数据访问的吞吐率。
[0061]图数据的访问，类似于访问顺序存储的数据，具有明显的局部性。图计算的算法一般基于图的遍历算法。以广度优先遍历为例，访问顶点V时，V的k阶邻域(从顶点V出经过最短距离k条边可达的全部顶点构成的集合)的顶点被访问概率随着k增大而降低，因此，处理V的访问请求时，系统根据顶点位置信息可以预测近期最有可能被访问的顶点，将顶点V和近期最有可能被访问的顶点的数据合并在一起，传输给请求者。请求者将预先取得的数据缓存在本地，下次获取异地数据时，先检查本地的缓存，如果存在，直接访问本地即可，否则向异地请求数据。
[0062]很多图计算框架会顺序地读取图数据的子图的全部顶点，此时，可以采用顺序预取的方式。预取方式的选择要符合图计算的数据访问特点，可以提供多种预取的策略，让用户选择从中选择最佳的预取策略。
[0063]实例I数据访问实例
[0064]本发明测试了本发明以及比较系Redis和Neo4j在不同并发量下的写性能，该写性能取了十个数据集下的平均值，其中在测试图3中，本发明使用NYNN表示。
[0065]由图3可知，本发明本地写性能明显优于Redis和Neo4j，元数据的设计和数据传输格式和数据写入的机制影响了写的性能。首先本发明图数据的划分采用连续的等宽顶点区间，能够通过首次数据写入请求，将元数据缓存在本地，此后使用缓存在本地的元数据进行数据寻址，这样减少了寻址的1开销。写入数据的时候，自己写入本地的内存映射文件中。Redis和Neo4j都提供了方便使用的查询命令/语言，先将用户写入数据的请求，封装成查询命令，然后通过本地网络发送给server，由server负责解析命令，完成查询。
[0066]本发明测试了本发明以及比较系Redis和Neo4j在不同并发量下的读性能，该读性能取了十个数据集下的平均值。
[0067]如图4所示，本地读操作，本发明可以达到GB/s量级，而Redis和Neo4j是1MB/s?lOOMB/s，本发明可以直接将图数据通过_ap接口映射到客户进程的地址空间中，进行操作。而Redis和Neo4j采用查询命令向server请求数据。
[0068]为了反应图数据存储系统的存储效率，本发明比较了多个系统的存储膨胀比，即存储同样多的数据，看内存和磁盘的占用膨胀比。
[0069]如图5所示，对比Redi s，Neo4j和本发明的磁盘使用情况，可以明显的观察到，Neo4j作为基于磁盘的存储系统，占用磁盘空间最大，数据存储的时候，需要存储属性值和属性名，而且属性值采用字符串的形式存储。Redis所需的磁盘存储空间最少，Redis的数据持久化之前，将数据进行压缩。而内存的使用中，Redis的内存使用最大，因为Redis将全部数据加载到内存。Neo4j和本发明都可以配置所需内存的大小。
[0070]本发明测试了本发明以及比较系Redis和Neo4j在不同并发量下的远程写性能，该写性能取了十个数据集下的平均值。
[0071]如图6所示，远程写数据，本发明的性能明显高于Neo4j和R edis。本发明的数据交换采用报文的形式传输字节流。而Redis和Neo4j采用查询命令或语言，降低了数据的传输效率。此外本发明的后台数据写入采用多线程处理，提高的效率。Redis采用事件驱动模型的单线出处理。
[0072]本发明测试了本发明以及比较系Redis和Neo4j在不同并发量下的远程读性能，该读性能取了十个数据集下的平均值。
[0073]如图7所示，远程读操作，本发明采用了数据预取机制，能够批量传输有效数据。而Redis和Neo4j都没有采用预取机制。
[0074]实例2数据更新实例
[0075]本文测试了本发明以及比较系Redis和Neo4j的数据更新性能，该性能取了十个数据集下的平均值。
[0076]如图8所示，对于数据的增量更新，本发明采用了链式的分配方式，能够消除数据插入和删除引起的数据频繁挪动问题。而Redis和Neo4j采用了顺序分配的方式，随着数据的更新，需要挪动数据，重定位数据，在这个过程中，无法进行新的查询处理。
[0077]实例3数据远程访问实例
[0078]本文测试了本发明在有预取机制和非预取的情况下的性能差异。本发明提供多种数据预取机制，便于上层应用更加自己的应用背景选择最佳的数据预取方式。本实验采用BFS预取，实验用到的算法是统计图数据集中图的总边数，算法的思路为:将图的顶点划分为η个分片，每个分片指定一个线程处理，所有线程并行访问本发明中的图数据。线程将访问请求中要访问的顶点放入队列，然后处理队列头部的顶点，访问顶点的邻域，统计顶点边数。如果当前边的终点位于线程所属分片，则将该终点放入队列。不断的循环处理队列的首部，直到队列为空。但所有的线程完成顶点的统计，将结果累计，算法结束。该算法为BFS遍历算法，能够很好的利用BFS预取机制，预取数据在后续的访问中，具有很高的命中率。
[0079] 如图9所示，本发明提供了多种数据预取机制，比如顺序预取，BFS预取和DFS预取。上层的计算框架可以选择最佳的预取方式批量的从异地获取图数据，图数据访问过程中，每次读取数据量比较少，虽然相邻时间的数据读取是可以预测的。通过将大批小量数据的访问积攒成大块数据，可以充分利用带宽资源，降低1启动时间，这样我们可以通过较低的并发获得较高的数据吞吐率。
【主权项】
1.一种面向大规模社交网络的图数据存储方法，其步骤为: 1)数据存储管理器对收到的图数据采用Key-Value方式存储，其中以图数据的顶点ID为Key，以顶点邻域为Value ； 2)对每一顶点邻域的数据存储:将与该顶点邻域对应顶点相连的多条边以时间戳有序存储到固定大小的内存块Block中，并使用链表结构将所占用的内存块Block构成Block双向链表，将该顶点的属性信息和指向该Block双向链表头部和尾部的索引信息存储到一数据结构Vertex中。2.如权利要求1所述的方法，其特征在于，所述内存块Block由一负责存储资源分配的Block池管理器进行分配与回收；所述Block双向链表中的内存块Block包括三部分:第一部分为指向Block双向链表中当前内存块Block的前一个内存块Block的指针，第二部分为指向Block双向链表中当前内存块Block的后一个Block的指针，第三部分为当前内存块Block存储的边。3.如权利要求2所述的方法，其特征在于，所述步骤2)中，当一顶点有新边需要存储到顶点邻域时，将该新边按时间戳排序，查看Block双向链表头部的Block是否未满，如果未满，则将该新边追加在该Block的头部；如果头部的Block已满，则由Block池管理器分配一新的内存块Block并添加到该Block双向链表的头部，然后将该新边存储到该新内存块Block 中。4.如权利要求1或2或3所述的方法，其特征在于，每一所述内存块Block中设有一数据域，用于保存所存边的时间戳区间；当对顶点领域中的边进行删除时，从Block双向链表尾部的内存块Block开始选取一边，如果该边的时间戳小于尾部内存块Block的时间戳区间下界，则结束删除操作，如果该边的时间戳大于该时间戳区间的上界，则从该Block双向链表末尾移除该内存块Block;如果该边的时间戳位于该时间戳区间内，则扫描该内存块Block中的边，删除比该边的时间戳早的边。5.如权利要求1所述的方法，其特征在于，所述数据存储管理器将存储资源分成两类:粗粒度存储资源和细粒度存储资源，所述数据存储管理器的内存中设置有界缓存窗口 ；其中所述粗粒度存储资源用于存储设定的大文件，并常驻于内存，所述细粒度存储资源用于存储按需分配的小文件；所述数据存储管理器按需将细粒度存储资源载入该有界缓存窗口，当该有界缓存窗口被占满，需要加载新的细粒度存储资源时，采用缓存替换算法将该有界缓存窗口中已有的细粒度存储资源换出，然后载入新的细粒度存储资源。6.如权利要求5所述的方法，其特征在于，所述粗粒度存储资源和所述细粒度存储资源均划分成固定大小的所述内存块Block，每一内存块Block拥有唯一的Block ID。7.如权利要求5所述的方法，其特征在于，所述数据存储管理器首先分配粗粒度存储资源的内存块Block，当粗粒度存储资源耗尽时，开始按需地动态地分配细粒度存储资源在内存块Block。8.如权利要求5所述的方法，其特征在于，所述数据存储器定期地扫描图数据，将过期的图数据从所述粗粒度存储资源中删除并转存到所述细粒度存储资源中。9.一种基于权利要求1所述方法存储的图数据的图数据查询方法，其特征在于，当数据存储管理器收到访问顶点V的访问请求时，数据存储管理器将该顶点V及其k阶邻域传输给请求者；请求者将返回数据缓存在本地，下次查询时，首先检查本地的缓存，如果不存在查询的顶点，则将访问请求发送给所述数据存储管理器。10.如权利要求9所述的方法，其特征在于，所述顶点V的k阶邻域为从该顶点V出发经过最短距离k条边可达的全部顶点构成的集合。
【专利摘要】本发明公开了一种面向大规模社交网络的图数据存储及查询方法，本发明数据存储管理器对收到的图数据采用Key-Value方式存储，以图数据的顶点ID为Key，以顶点邻域为Value；对每一顶点邻域的数据存储：将与该顶点邻域相连的多条边以时间戳有序存储到固定大小的内存块中，并构成双向链表，将该顶点的属性信息和索引信息存储到一数据结构中。当数据存储管理器收到访问顶点v的访问请求时，数据存储管理器将该顶点v及其k阶邻域传输给请求者；请求者将返回数据缓存在本地，下次查询时，首先检查本地的缓存，如果不存在查询的顶点，则将访问请求发送给所述数据存储管理器。本发明能满足动态更新、适合处理数据稀疏的场景和随机访问。
【IPC分类】G06F12/06
【公开号】CN104899156
【申请号】CN201510229346
【发明人】周薇, 包秀国, 马宏远, 程工, 冉攀峰, 刘春阳, 王卿, 韩冀中, 庞琳, 李雄, 贺敏, 刘玮
【申请人】中国科学院信息工程研究所, 国家计算机网络与信息安全管理中心
【公开日】2015年9月9日
【申请日】2015年5月7日
最新回复(0)