基于非易失性内存的知识图谱系统优化研究

doi:10.3778/j.issn.1002-8331.2305-0370

摘要/Abstract

摘要： 分布式系统的高扩展性和高可用性使得在其上构建大规模知识图谱已经成为产业发展趋势。新兴的分布式图数据库更推崇采用NoSQL等数据模型，如键值存储作为其存储引擎，以进一步提高其可扩展性和实用性。在这种情况下，上层的图查询语言的语句会被翻译成一组混合的键值操作。为了加速查询翻译生成的键值操作，提出了基于非易失性内存查询性能加速（knowledge graph booster，KGB）的知识图谱系统。KGB主要包含面向邻域查询加速的NVM辅助索引，用于降低键值存储的读取成本；快速响应的改进Raft算法，用于实现高效的键值存取操作；以及面向键值存储引擎的调优机制，为知识图谱存储系统获得额外的性能提升。通过实验表明，KGB能有效降低知识图谱系统的平均延迟和尾延迟的影响，实现更高的性能提升。

关键词: 知识图谱, 键值存储, 非易失性内存

Abstract: Deploying large-scale knowledge graphs on distributed systems has become an industry trend for their high scalability and availability. There are some distributed graph databases that prefer to adopt the NoSQL data models like the key-value store as their storage engines for its scalability and practicability. Therefore, an upper-level graph query language (GQL) statement will be translated into a group of the native and hybrid kinds of key-value (KV) operations. To accelerate the KV operations generated from upper-level knowledge graph queries, a high-performance knowledge graph system with a non-volatile memory-based queries booster (KGB) is proposed. KGB mainly contains a neighbor queries auxiliary index for reducing KVs searching cost, a fast Raft algorithm for efficient KVs operations, and a KV tuning mechanism to acquire extra performance promotion for knowledge graph application scenarios. Experiments show that KGB can effectively reduce the average and the tail latency, achieving higher performance promotion for the knowledge graph system.

Key words: knowledge graph, key-value stores, non-volatile memory (NVM)

柴艳峰, 李加姝, 李雨航, 柴云鹏, 张蔷, 张睿, 潘理虎. 基于非易失性内存的知识图谱系统优化研究[J]. 计算机工程与应用, 2024, 60(15): 270-276.

CHAI Yanfeng, LI Jiashu, LI Yuhang, CHAI Yunpeng, ZHANG Qiang, ZHANG Rui, PAN Lihu. Research on Optimizing Knowledge Graph System with Non-Volatile Memory[J]. Computer Engineering and Applications, 2024, 60(15): 270-276.

参考文献

[1] MILLER J J. Graph database applications and concepts with Neo4j[C]//Proceedings of the Southern Association for Information Systems Conference, Atlanta, GA, USA, 2013.
[2] Tencent Cloud Team. Graph database performance comparison: Neo4j vs NebulaGraph vs JanusGraph[EB/OL]. (2020). https://www.nebula-graph.io/posts/performance-comparison-neo4j-janusgraph-nebula-graph.
[3] MONTEIRO J, Sá F, BERNARDINO J. Experimental evaluation of graph databases: JanusGraph, Nebula Graph, Neo4j, and TigerGraph[J]. Applied Sciences, 2023, 13(9): 5770.
[4] URBANI J, JACOBS C. Adaptive low-level storage of very large knowledge graphs[C]//Proceedings of The Web Conference, 2020: 1761-1772.
[5] LI S, CHEN W, LIU B, et al. OntoSP: ontology-based semantic-aware partitioning on RDF graphs[C]//Proceedings of the 22nd International Conference on Web Information Systems Engineering (WISE 2021), Melbourne, VIC, Australia, October 26-29, 2021. [S.l.]: Springer International Publishing, 2021: 258-273.
[6] MATSUNOBU Y, DONG S, LEE H. MyRocks: LSM-tree database storage engine serving facebook’s social graph[J]. Proceedings of the VLDB Endowment, 2020, 13(12): 3217-3230.
[7] Under the hood: building and open-sourcing rocksdb[EB/OL]. (2017-05-11) [2023-07-13]. http://goo.gl/9xulVB.
[8] DAGEVILLE B, CRUANES T, ZUKOWSKI M, et al. The snowflake elastic data warehouse[C]//Proceedings of the 2016 International Conference on Management of Data, 2016: 215-226.
[9] BURAGOHAIN C, RISVIK K M, BRETT P, et al. A1: a distributed in-memory graph database[C]//Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, 2020: 329-344.
[10] HUANG X, YANG Y, WANG Y, et al. Dgraph: a large-scale financial dataset for graph anomaly detection[C]//Advances in Neural Information Processing Systems, 2022: 22765-22777.
[11] Sbadger: A fast key-value store written natively in go[CP/OL]. (2020-09-12) [2023-07-11]. https://github.com/dgraph-io/badger.
[12] DONG S, CALLAGHAN M, GALANIS L, et al. Optimizing space amplification in RocksDB[C]//Conference on Innovative Data Systems Research, 2017.
[13] CAO Z, DONG S. Characterizing, modeling, and benchmarking RocksDB key-value workloads at Facebook[C]//18th USENIX Conference on File and Storage Technologies (FAST’20), 2020.
[14] WANG Y, CHAI Y. vRaft: accelerating the distributed consensus under virtualized environments[C]//Proceedings of 26th International Conference on Database Systems for Advanced Applications (DASFAA 2021), Taipei, China, April 11-14, 2021. [S.l.]: Springer International Publishing, 2021: 53-70.
[15] WANG Y, WANG Z, CHAI Y, et al. Rethink the linearizability constraints of raft for distributed key-value stores[C]//2021 IEEE 37th International Conference on Data Engineering (ICDE), 2021: 1877-1882.
[16] GAO S, ZHAN B, LIU D, et al. Formal verification of consensus in the taurus distributed database[C]//Proceedings of 24th International Symposium on Formal Methods (FM 2021), Virtual Event, November 20-26, 2021. [S.l.]: Springer International Publishing, 2021: 741-751.
[17] BALMAU O, DINU F, ZWAENEPOEL W, et al. SILK: preventing latency spikes in log-structured merge key-value stores[C]//USENIX Annual Technical Conference, 2019: 753-766.
[18] CHAI Y P, CHAI Y F, WANG X, et al. LDC: a lower-level driven compaction method to optimize SSD-oriented key-value stores[C]//2019 IEEE 35th International Conference on Data Engineering (ICDE), 2019: 722-733.
[19] CHAI Y P, CHAI Y F, WANG X, et al. Adaptive lower-level driven compaction to optimize LSM-tree key-value stores[J]. IEEE Transactions on Knowledge and Data Engineering, 2020, 34(6): 2595-2609.
[20] KARGAR S, NAWAB F. Hamming tree: the case for energy-aware indexing for NVMs[J]. Proceedings of the ACM on Management of Data, 2023, 1(2): 1-27.
[21] WU F, YANG M H, ZHANG B, et al. AC-key: adaptive caching for LSM-based key-value stores[C]//Proceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference, 2020: 603-615.
[22] SARKAR S, PAPON T I, STARATZIS D, et al. Lethe: a tunable delete-aware LSM engine[C]//Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, 2020: 893-908.
[23] RUTA N J. CuttleTree: adaptive tuning for optimized log-structured merge trees[D]. Harvard University, 2018.
[24] YU J, NOH S H, CHOI Y, et al. ADOC: automatically harmonizing dataflow between components in log-structured key-value stores for improved performance[C]//21st USENIX Conference on File and Storage Technologies (FAST 23), 2023: 65-80.
[25] SHENG Y, CAO X, FANG Y, et al. WISK: a workload-aware learned index for spatial keyword queries[J]. Proceedings of the ACM on Management of Data, 2023, 1(2): 1-27.
[26] ZHOU X, LI G, FENG J, et al. Grep: a graph learning based database partitioning system[J]. Proceedings of the ACM on Management of Data, 2023, 1(1): 1-24.
[27] LevelDB-a fast and lightweight key/value database library by google[EB/OL]. (2017-08-07) [2023-07-13]. http://code.google.com/p/leveldb.