论文部分内容阅读
随着web和社交网络的兴起,图计算相关的应用已经成为计算机领域的一个热点。为图计算提供数据存储服务和查询服务的图数据存储系统,在面对社交网络这种大规模数据集时,也正遭遇着前所未有的挑战。本文分析现有图数据存储系统中存在的问题,并提出相应的解决方案,最后在此基础上实现一个面向图计算的分布式存储系统。 现有图计算系统中普遍采用分布式文件系统或者NoSQL数据库来管理图数据,除此之外也有专门的图数据库,比如Neo4j,GraphDB等。这些系统在各自擅长的应用背景下工作的很好,基本上满足了图计算的存储需求,但是图数据存储管理依然存在三个突出的问题:1)现有的图数据存储系统缺乏一种高效的数据组织方式来支持图数据的读写操作,像Neo4j这种知名的图数据库,底层虽然也是采用图数据模型存储,但是其以顶点和边为中心的结构使得读写效率不高;2)现有的图数据存储系统都采用通用的缓存机制,比如LRU,并没有结合图数据自身的特征,从而使得缓存命中率不高;3)现有的图数据存储系统缺乏一种任务调度机制,对任务集都是采取顺序执行的方式,没有考虑到任务之间的相关性,从而产生了大量重复的磁盘IO,降低了系统的性能。 针对以上问题,本文提出了三项关于分布式图数据存储系统的关键技术。并在实际应用场景中设计和实现了分布式图数据存储系统Panda。本文的主要研究内容如下: 1.设计了一种以顶点为中心,顶点邻域索引化的数据组织机制。边作为顶点的属性进行存储,并对边数多的顶点自动建立轻量级索引,使得图数据存储系统能够高效地处理有关图的操作。 2.设计了一种感知顶点度数的LRU缓存策略。顶点度数越多的顶点,下次被访问的概率越大,结合这个特征设计的LRU缓存策略减少了磁盘与内存的换入换出次数,从而提高系统的性能。 3.设计了一种具有合并操作功能的任务调度机制。对接收到的任务集首先进行调度,把相关的任务调度到一起执行,并且把多个相似的任务合并成一个任务,很大程度上减少了任务的数目,从而提高图数据存储系统的吞吐率,降低客户端的通信延迟。 本文通过分析现有图数据存储技术中的不足,并针对这些问题提出了解决方案,最终设计并实现出了一个分布式图数据存储系统,该系统具有良好的可扩展性,高效地读写性能,能满足社交网络这种大规模数据集带来的挑战。