论文部分内容阅读
由于RDF(Resource Description Framework)数据模型的灵活性和可扩展性,越来越多的社区将它们的数据以RDF的格式进行发布。因此,分布式存储和处理RDF数据已经成为一个热点问题。现有的分布式解决方案虽然取得了一定的成效,但大多集中在分布式存储结构的设计和处理流程的优化,在任务负载均衡和通信量最小化方面的研究较少。基于超图模型的并行遍历树划分与分布式处理系统(Par Triple Bit),提出一种高效划分和分布处理超大规模RDF图数据的技术。这种技术根据RDF数据的特性,采用超图模型对数据进行抽象,以超边数据的一部分作为基本划分块,然后采用遍历树划分方法并行的放置路径上的基本划分块,以保证实体间连接关系的完整性。在放置时制定了相应的策略来对计算节点进行选取,以保证各计算节点的数据负载均匀和任务负载均衡,并提出基于启发式的查询任务分解策略,以最简化查询分解。在分布式处理方面,采用MPI消息传输协议提供的异步和非阻塞通信模型来进行数据的交互,借助分块变长整形差值压缩方法和并行流水来减少通信量,提高交互效率。此外,还实现了无锁窃取调度方式来对查询任务进行调度,提高并行度。在中间结果的合并过程中,提出一种批量合并方式来减少合并过程中key值的比对次数,提高合并效率。Par Triple Bit与目前较好的集中式RDF存储系统Triple Bit和RDF-3X,分布式RDF处理系统Hybrid(unone-on、dirtwo和untwo-on)相比:数据划分方面,平均预处理时间快数倍,数据冗余度最低,数据负载最均匀;查询性能方面,超出三个分布式系统40%以上,超出两个集中式系统数倍甚至数十倍;可扩展性方面,随着计算节点数目的增加,查询性能呈线性或超线性提升;随着数据集规模的增大,查询语句的执行时间呈亚线性递增,因而系统的可扩展性较好。