Granted Patent B2

US 12,248,517 · App. 18/658,765 · Granted Mar 11, 2025

Inventors: Shuai Zhang (Beijing, CN); Yingqian Hu (Beijing, CN); Chao Chen (Beijing, CN); Zhenjie Zhang (Singapore, SG); Hongzhi Chen (Beijing, CN)

Assignee: BEIJING VOLCANO ENGINE TECHNOLOGY CO. LTD.

G06F16/9024G06F16/9027

Abstract

Claims (57)

1. A data processing method for a graph database, wherein the method comprises:

receiving a writing request for first target graph data, wherein the first target graph data comprises nodes and edges, and edge types of the edges are used for characterizing relationship types between nodes associated with the edges;

determining a balanced B-tree corresponding to each node in the first target graph data, storing graph data of at least one edge type corresponding to each node into a leaf node of a B-tree, and storing index information of the leaf node into an internal node corresponding to the leaf node in the B-tree, wherein index information of the B-tree is stored at a root node of the B-tree, and the index information of the B-tree is determined based on a node identifier of the node corresponding to the B-tree and the at least one edge type corresponding to the B-tree; and

determining, in a key-value store system, a key-value pair corresponding to each node in the B-tree, persistently storing an index key in the index information of each node into a key of the corresponding key-value pair, and persistently storing the graph data or the index information stored in each node into a key of the corresponding key-value pair, wherein the key-value store system is configured to persistently store the graph data;

wherein before determining a B-tree corresponding to each node in the first target graph data, the method further comprises:

generating log information corresponding to the writing request wherein the log information is used for recording operation information of the writing request;

storing the log information corresponding to the writing request into the key-value store system; and

in response to determine that a B-tree corresponding to the log information meets a preset first playback condition and/or an idle state of a current system meets a preset second playback condition, obtaining the log information from the key-value store system; and

determining a B-tree corresponding to each node in the first target graph data respectively comprises:

determining, based on the operation information of the writing request that is recorded in the log information, the B-tree corresponding to each node in the first target graph data corresponding to the operation information.

2. The method of claim 1 , wherein storing the log information corresponding to the writing request into the key-value store system comprises:

storing the log information corresponding to the writing request into log streams of the B-trees corresponding to the first target graph data in the key-value store system in the form of key-value pairs, wherein the key-value store system stores log streams having mapping relationships with the various B-trees respectively.

3. The method of claim 1 , wherein after generating log information corresponding to the writing request, the method further comprises:

recording the index information of the B-trees corresponding to the first target graph data in a preset dirty linked list in a cache, wherein the preset dirty linked list is used for maintaining the index information of B-trees with unplayed log information; and

in response to the index information of the B-trees corresponding to the first target graph data is obtained from the preset dirty linked list, determining that the B-tree corresponding to the log information meets a preset first playback condition and/or an idle state of a current system meets a preset second playback condition.

4. The method of claim 1 , wherein a plurality of data shards corresponding to a complete set of graph data stored in the key-value store system are respectively stored in caches of different devices; the plurality of data shards is obtained by partitioning the complete set of graph data based on a preset partitioning strategy; and the preset partitioning strategy is determined based on a feature of an application scenario of the complete set of graph data.

5. The method of claim 1 , wherein a storage capacity of the leaf node of the B-tree is pre-configured based on reading and writing feature information of the graph data stored in the leaf node, and the reading and writing feature information is used for characterizing a requirement of the graph data for data read and write amplification.

6. The method of claim 1 , wherein the method further comprises:

receiving a reading request for second target graph data through a graph query engine layer, and transmitting the reading request into a graph storage engine layer;

determining, by using the graph storage engine layer, B-trees corresponding to the reading request based on node identifiers and edge types of various nodes in the second target graph data, executing the reading request based on the B-trees to obtain a reading result, and returning the reading result to the graph query engine layer.

7. A non-transitory computer-readable storage medium, having instructions stored therein, wherein the instructions, when performed by a terminal device, cause the terminal device to implement a method, comprising:

receiving a writing request for first target graph data, wherein the first target graph data comprises nodes and edges, and edge types of the edges are used for characterizing relationship types between nodes associated with the edges;

determining a balanced B-tree corresponding to each node in the first target graph data, storing graph data of at least one edge type corresponding to each node into a leaf node of a B-tree, and storing index information of the leaf node into an internal node corresponding to the leaf node in the B-tree, wherein the index information of the B-tree is stored at a root node of the B-tree, and the index information of the B-tree is determined based on a node identifier of the node corresponding to the B-tree and the at least one edge type corresponding to the B-tree; and

determining, in a key-value store system, a key-value pair corresponding to each node in the B-tree, persistently storing an index key in the index information of each node into a key of the corresponding key-value pair, and persistently storing the graph data or the index information stored in each node into a key of the corresponding key-value pair, wherein the key-value store system is configured to persistently store the graph data;

wherein before determining a B-tree corresponding to each node in the first target graph data, the method further comprises:

generating log information corresponding to the writing request, wherein the log information is used for recording operation information of the writing request;

storing the log information corresponding to the writing request into the key-value store system; and

in response to determine that a B-tree corresponding to the log information meets a preset first playback condition and/or an idle state of a current system meets a preset second playback condition, obtaining the log information from the key-value store system; and

determining a B-tree corresponding to each node in the first target graph data respectively comprises:

determining, based on the operation information of the writing request that is recorded in the log information, the B-tree corresponding to each node in the first target graph data corresponding to the operation information.

8. The non-transitory computer-readable storage medium of claim 7 , wherein storing the log information corresponding to the writing request into the key-value store system comprises:

storing the log information corresponding to the writing request into log streams of the B-trees corresponding to the first target graph data in the key-value store system in the form of key-value pairs, wherein the key-value store system stores log streams having mapping relationships with the various B-trees respectively.

9. The non-transitory computer-readable storage medium of claim 7 , wherein after generating log information corresponding to the writing request, the method further comprises:

recording the index information of the B-trees corresponding to the first target graph data in a preset dirty linked list in a cache, wherein the preset dirty linked list is used for maintaining the index information of B-trees with unplayed log information; and

in response to the index information of the B-trees corresponding to the first target graph data is obtained from the preset dirty linked list, determining that the B-tree corresponding to the log information meets a preset first playback condition and/or an idle state of a current system meets a preset second playback condition.

10. The non-transitory computer-readable storage medium of claim 7 , wherein a plurality of data shards corresponding to a complete set of graph data stored in the key-value store system are respectively stored in caches of different devices; the plurality of data shards is obtained by partitioning the complete set of graph data based on a preset partitioning strategy; and the preset partitioning strategy is determined based on a feature of an application scenario of the complete set of graph data.

11. The non-transitory computer-readable storage medium of claim 7 , wherein a storage capacity of the leaf node of the B-tree is pre-configured based on reading and writing feature information of the graph data stored in the leaf node, and the reading and writing feature information is used for characterizing a requirement of the graph data for data read and write amplification.

12. The non-transitory computer-readable storage medium of claim 7 , wherein the method further comprises:

receiving a reading request for second target graph data through a graph query engine layer, and transmitting the reading request into a graph storage engine layer;

determining, by using the graph storage engine layer, B-trees corresponding to the reading request based on node identifiers and edge types of various nodes in the second target graph data, executing the reading request based on the B-trees to obtain a reading result, and returning the reading result to the graph query engine layer.

13. A data processing device for a graph database, comprising a memory, a processor, and a computer program stored on the memory and runnable on the processor, wherein the processor, when perform the computer program, implements a method comprising:

receiving a writing request for first target graph data, wherein the first target graph data comprises nodes and edges, and edge types of the edges are used for characterizing relationship types between nodes associated with the edges;

determining a balanced B-tree corresponding to each node in the first target graph data, storing graph data of at least one edge type corresponding to each node into a leaf node of a B-tree, and storing index information of the leaf node into an internal node corresponding to the leaf node in the B-tree, wherein index information of the B-tree is stored at a root node of the B-tree, and the index information of the B-tree is determined based on a node identifier of the node corresponding to the B-tree and the at least one edge type corresponding to the B-tree; and

determining, in a key-value store system, a key-value pair corresponding to each node in the B-tree, persistently storing an index key in the index information of each node into a key of the corresponding key-value pair, and persistently storing the graph data or the index information stored in each node into a key of the corresponding key-value pair, wherein the key-value store system is configured to persistently store the graph data;

wherein before determining a B-tree corresponding to each node in the first target graph data, the method further comprises:

generating log information corresponding to the writing request, wherein the log information is used for recording operation information of the writing request;

storing the log information corresponding to the writing request into the key-value store system; and

in response to determine that a B-tree corresponding to the log information meets a preset first playback condition and/or an idle state of a current system meets a preset second playback condition, obtaining the log information from the key-value store system; and

determining a B-tree corresponding to each node in the first target graph data respectively comprises:

determining based on the operation information of the writing request that is recorded in the log information, the B-tree corresponding to each node in the first target graph data corresponding to the operation information.

14. The device of claim 13 , wherein storing the log information corresponding to the writing request into the key-value store system comprises:

storing the log information corresponding to the writing request into log streams of the B-trees corresponding to the first target graph data in the key-value store system in the form of key-value pairs, wherein the key-value store system stores log streams having mapping relationships with the various B-trees respectively.

15. The device of claim 13 , wherein after generating log information corresponding to the writing request, the method further comprises:

recording the index information of the B-trees corresponding to the first target graph data in a preset dirty linked list in a cache, wherein the preset dirty linked list is used for maintaining the index information of B-trees with unplayed log information; and

in response to the index information of the B-trees corresponding to the first target graph data is obtained from the preset dirty linked list, determining that the B-tree corresponding to the log information meets a preset first playback condition and/or an idle state of a current system meets a preset second playback condition.

16. The device of claim 13 , wherein a plurality of data shards corresponding to a complete set of graph data stored in the key-value store system are respectively stored in caches of different devices; the plurality of data shards is obtained by partitioning the complete set of graph data based on a preset partitioning strategy; and the preset partitioning strategy is determined based on a feature of an application scenario of the complete set of graph data.

17. The device of claim 13 , wherein a storage capacity of the leaf node of the B-tree is pre-configured based on reading and writing feature information of the graph data stored in the leaf node, and the reading and writing feature information is used for characterizing a requirement of the graph data for data read and write amplification.

Assignments (8)

Priority Claims (1)

Continuity (1)

References Cited (9)