Atomic updating of graph database index structures

Patent metadata

Field	Value
Publication number	US-10180992-B2
Application number	US-201615058032-A
Country	US
Kind code	B2
Filing date	Mar 1, 2016
Priority date	Mar 1, 2016
Publication date	Jan 15, 2019
Grant date	Jan 15, 2019

Abstract

The disclosed embodiments provide a system for updating an index structure of a graph database storing a graph. During operation, the system includes, in the index structure, a first compressed edge store containing a first compact representation of edges in the graph at a first virtual time and a first series of updates to the edges after the first virtual time. At a second virtual time, the system creates a second compact representation of the edges from the first compact representation and the first series of updates. The system then appends, to the second compact representation, a second series of updates to the edges after the second virtual time to produce a second compressed edge store. Finally, the system updates the index structure by atomically replacing, in the index structure, a reference to the first compressed edge store with a reference to the second compressed edge store.

First claim

What is claimed is:

1. A method, comprising:
providing, by a computer system, an index structure for use in processing queries of a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates, and wherein the set of nodes and the set of predicates form a set of attributes;
creating, in the index structure, a first compressed edge store comprising a first compact representation of the set of edges at a first virtual time in the graph and a first series of updates to the set of edges after the first virtual time, wherein the first compact representation includes the set of edges, and wherein creating the first compact representation includes:
grouping the set of edges into a set of compact groupings based on the set of attributes, wherein the set of compact groupings includes a first grouping indexed by a first attribute in the set of attributes; and
forming the first grouping by storing a single instance of the first attribute and storing a first subset of edges in the set of edges which shares the first attribute together with the single instance of the first attribute;

creating, at a second virtual time in the graph, a second compact representation of the set of edges from the first compact representation and the first series of updates, wherein the second compact representation includes the set of edges, and wherein creating the second compact representation includes:
updating the first grouping by storing a first subset of updates in the first series of updates which shares the first attribute together with the single instance of the first attribute;

appending, to the second compact representation, a second series of updates to the set of edges after the second virtual time to produce a second compressed edge store; and
updating the index structure with the second compressed edge store by atomically replacing, in the index structure, a first reference to the first compressed edge store with a second reference to the second compressed edge store,
wherein storing the set of edges by grouping the set of edges under a set of shared attributes and storing a single instance of a given shared attribute instead of storing multiple instances of the given shared attribute facilitates reducing storage requirement and improving edge lookup speed.

2. The method of claim 1 , further comprising:
including, in the index structure, a first lock-free hash table comprising a first set of hash buckets and a first set of entries in the first set of hash buckets; and
referencing, by the first set of entries, the set of edges in the first compact representation.

3. The method of claim 2 , further comprising:
creating a second lock-free hash table comprising a second set of hash buckets and a second set of entries in the second set of hash buckets;
referencing, by the second set of entries, the set of edges in the second compact representation; and
updating the index structure with the second lock-free hash table by atomically replacing, in the index structure, a third reference to the first lock-free hash table with a fourth reference to the second lock-free hash table.

4. The method of claim 3 , wherein creating the second lock-free hash table comprises:
selecting a size of the second lock-free hash table based on an attribute associated with the first lock-free hash table.

5. The method of claim 4 , wherein the attribute is at least one of:
a remaining capacity of the first lock-free hash table; and
a number of overflow buckets in the first lock-free hash table.

6. The method of claim 1 , further comprising:
after the first reference is replaced with the second reference in the index structure, maintaining the first compressed edge store until processing of the queries using the first compressed edge store is complete.

7. The method of claim 1 , wherein the first compact representation comprises:
a first sorting of the edges by a first attribute; and
for each value of the first attribute in the first sorting, a second sorting of the edges by a second attribute.

8. The method of claim 7 , wherein the first compact representation further comprises:
for each value of the second attribute in the second sorting, a set of values for one or more additional attributes of the edges.

9. The method of claim 8 , wherein the one or more additional attributes comprise a virtual time in the graph.

10. The method of claim 7 , wherein the first attribute and the second attribute comprise at least one of:
a subject;
a predicate; and
an object.

11. The method of claim 1 , wherein the second series of updates is appended to the second compact representation from a log-based representation of the graph database.

12. An apparatus, comprising:
one or more processors; and
memory storing instructions that, when executed by the one or more processors, cause the apparatus to:
provide an index structure for use in processing queries of a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates, and wherein the set of nodes and the set of predicates form a set of attributes;
create, in the index structure, a first compressed edge store comprising a first compact representation of the set of edges at a first virtual time in the graph and a first series of updates to the set of edges after the first virtual time, wherein the first compact representation includes the set of edges, and wherein creating the first compact representation includes:
grouping the set of edges into a set of compact groupings based on the set of attributes, wherein the set of compact groupings includes a first grouping indexed by a first attribute in the set of attributes; and
forming the first grouping by storing a single instance of the first attribute and storing a first subset of edges in the set of edges which shares the first attribute together with the single instance of the first attribute;

create, at a second virtual time in the graph, a second compact representation of the set of edges from the first compact representation and the first series of updates, wherein the second compact representation includes the set of edges, and wherein creating the second compact representation includes:
updating the first grouping by storing a first subset of updates in the first series of updates which shares the first attribute together with the single instance of the first attribute;

append, to the second compact representation, a second series of updates to the set of edges after the second virtual time to produce a second compressed edge store; and

update the index structure with the second compressed edge store by atomically replacing, in the index structure, a first reference to the first compressed edge store with a second reference to the second compressed edge store,
wherein storing the set of edges by grouping the set of edges under a set of shared attributes and storing a single instance of a given shared attribute instead of storing multiple instances of the given shared attribute facilitates reducing storage requirement and improving edge lookup speed.

13. The apparatus of claim 12 , wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:
include, in the index structure, a first lock-free hash table comprising a first set of hash buckets and a first set of entries in the first set of hash buckets; and
reference, by the first set of entries, the set of edges in the first compact representation.

Assignees

• Linkedin Corp
• Microsoft Technology Licensing Llc

Inventors

• Cho Sungju
• Zhu Jiahong
• Wang Yinyi
• Averbukh Roman A
• Meyer Scott M
• Shankar Shyam
• Niu Qingpeng
• Parikh Karan R

Classifications

• G06F17/30958

  Physics · mapped topic

• G06F17/30587

  Physics · mapped topic

• G06F17/30949 Primary

  Physics · mapped topic

• G06F17/3033

  Physics · mapped topic

• G06F17/30336

  Physics · mapped topic