Multi-tenant distribution of graph database caches

Patent metadata

Field	Value
Publication number	US-10445321-B2
Application number	US-201715438194-A
Country	US
Kind code	B2
Filing date	Feb 21, 2017
Priority date	Feb 21, 2017
Publication date	Oct 15, 2019
Grant date	Oct 15, 2019

Abstract

The disclosed embodiments provide a system for performing multi-tenancy distribution of a graph database cache. During operation, the system obtains a cache of a set of records in a graph database storing a graph, wherein the graph includes a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates. Next, the system identifies one or more records in the cache that fail a validation test. The system then merges a remainder of the cache with online updates to the subset of records to produce a merged version of the cache. Finally, the system distributes the merged version to one or more instances of the graph database for use in processing queries of the graph database.

First claim

What is claimed is:

1. A method, comprising:
obtaining a cache of a set of records in 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;
identifying, by one or more computer systems, a subset of the records in the cache that fails a validation test;
merging, by the one or more computer systems, a remainder of the cache that lacks the subset of the records with online updates to the subset of records to produce a merged version of the cache; and
distributing the merged version to one or more instances of the graph database for use in processing queries of the graph database.

2. The method of claim 1 , wherein obtaining the cache comprises:
obtaining the set of records from a set of input sources; and
using the set of records to generate the cache.

3. The method of claim 2 , wherein using the set of records to generate the cache comprises:
generating an index of the graph database from the set of records.

4. The method of claim 1 , wherein identifying the subset of records in the cache that fails the validation test comprises:
applying a set of rules in the validation test to the cache to identify the subset of records as failing the validation test.

5. The method of claim 4 , wherein the subset of records comprises at least one of:
a duplicate record;
a lack of a bidirectional connection; and
a lack of up-to-date data in the graph database.

6. The method of claim 1 , wherein merging the remainder of the cache that lacks the subset of records with online updates to the subset of records to produce the merged version of the cache comprises:
adding, to a whitelist, one or more data sets in the remainder of the cache; and
using the whitelist to merge the one or more data sets with a snapshot of the graph database created from the online updates.

7. The method of claim 6 , wherein using the whitelist to merge the one or more data sets with the snapshot comprises:
for each node in the set of nodes, merging a first set of edges associated with the node from the one or more data sets with a second set of edges associated with the node from the snapshot.

8. The method of claim 6 , wherein each data set in the one or more data sets is associated with an edge type in the graph database.

9. The method of claim 1 , wherein processing queries of the graph database comprises:
using the merged version and additional online updates to the graph database to process queries of the graph database.

10. The method of claim 1 , wherein the set of predicates is associated with at least one of:
a connection;
an employment;
a group membership;
an endorsement;
a following of a company;
a following of a member;
a skill of the member;
a title of the member;
an education of the member at a school; and
a location of the member.

11. The method of claim 1 , wherein the cache comprises:
a node identifier;
a node type associated the node identifier;
a list of edge types associated with the node identifier; and
a set of edges associated with the edge types.

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:
obtain a cache of a set of records in 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;
identify a subset of the records in the cache that fails a validation test;
merge a remainder of the cache that lacks the subset of the records with online updates to the subset of records to produce a merged version of the cache; and
distribute the merged version to one or more instances of the graph database for use in processing queries of the graph database.

13. The apparatus of claim 12 , wherein obtaining the cache comprises:
obtaining the set of records from a set of input sources; and
using the set of records to generate the cache.

14. The apparatus of claim 13 , wherein using the set of records to generate the cache comprises:
generating an index of the graph database from the set of records.

15. The apparatus of claim 12 , wherein the subset of records comprises at least one of:
a duplicate record;
a lack of a bidirectional connection; and
a lack of up-to-date data in the graph database.

16. The apparatus of claim 15 , wherein merging the remainder of the cache that lacks the subset of records with online updates to the subset of records to produce the merged version of the cache comprises:
adding, to a whitelist, one or more data sets in the remainder of the cache; and
using the whitelist to merge the one or more data sets with a snapshot of the graph database created from the online updates.

17. The apparatus of claim 16 , wherein using the whitelist to merge the one or more data sets with the snapshot comprises:
for each node in the set of nodes, merging a first set of edges associated with the node from the one or more data sets with a second set of edges associated with the node from the snapshot.

18. The apparatus of claim 12 , wherein processing queries of the graph database comprises:
using the merged version and additional online updates to the graph database to process queries of the graph database.

19. A system, comprising:
one or more processors;
staging module comprising a non-transitory computer-readable medium comprising instructions that, when executed by the one or more processors, cause the system to:
obtain a cache of a set of records in 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;
identify a subset of the records in the cache that fails a validation test; and
merge a remainder of the cache that lacks the subset of the records with online updates to the subset of records to produce a merged version of the cache; and

a seeding module comprising a non-transitory computer-readable medium comprising instructions that, when executed by the one or more processors, cause the system to distribute the merged version to one or more instances of the graph database for use in processing queries of the graph database.

20. The system of claim 19 , wherein merging the remainder of the cache that lacks the subset of records with online updates to the subset of records to produce the merged version of the cache comprises:
adding, to a whitelist, one or more data sets in the remainder of the cache; and
using the whitelist to merge the one or more data sets with a snapshot of the graph database created from the online updates.

Assignees

• Linkedin Corp
• Microsoft Technology Licensing Llc

Inventors

• Song Yongling
• Jan Jane Alam
• Miller Brent D
• Li Tianqiang

Classifications

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/282

  Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes · CPC title

• G06F16/24552 Primary

  Database cache management · CPC title