Distributed Cache for Graph Data

• US 20120173541A1
• Filed: 09/07/2011
• Published: 07/05/2012
• Est. Priority Date: 12/30/2010
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Venkataramani, Venkateshwaran
• Granted Patent: US 8,832,111 B2
• Time in Patent Office: Days
• US Class Current: 707/747
• CPC Class Codes: G06F 12/0844 Multiple simultaneous or quasi-simultaneous cache accessing
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: G06F 2212/463 File
• CPC Class Codes: G06F 2212/60 Details of cache memory
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

A distributed caching system for storing and serving information modeled as a graph that includes nodes and edges that define associations or relationships between nodes that the edges connect in the graph.

Claims

1. A system comprising:

a database; and

a cache layer comprising one or more cache nodes, the one or more cache nodes operative to

maintain in a memory one or more data structures storing association information describing associations between nodes in a graph a plurality of distributed cache clusters for storing information in the form of a graph, the graph comprising a plurality of nodes, each uniquely identified by a node identifier, and edge information indicating associations between nodes;

respond to queries for associations between nodes in the graph by accessing the memory;

forwarding other queries to the database for processing.

2. The system of claim 1 wherein the one or more cache nodes are operative to

receive a request to change the association information in the memory;

change the association in the memory;

modifying the request for implementation by the database and forwarding the modifying request to the database for processing.

3. The system of claim 1 wherein the cache layer comprises a plurality of distributed cache clusters, each cache cluster comprising a plurality of cache nodes, each cache cluster allocated one or more data shards, each of the cache nodes of a cache cluster storing association information for nodes corresponding to the allocated data shards.

4. The system of claim 3 wherein the plurality of cache clusters comprise:

a leader cache cluster comprising a plurality of leader nodes; and

one or more follower cache clusters each comprising a plurality of follower cache nodes.

5. The system of claim 1 wherein the one or more cache nodes are operative to

maintain in a memory, for each association set corresponding to a first node of a plurality of nodes and an association type of a plurality of association types, a first index and a second index;

wherein the first index comprises an ordered array of entries, each entry including a node identifier of a second node that is associated with the first node and a sorting attribute;

wherein the second index comprises a hash table comprising entries corresponding to the node identifiers of respective second nodes that are associated with the first node;

receive a command to add an association of a first association type between a first node and a second node, the command including a first node identifier and a second node identifier;

access the memory against the first association type and the first node identifier to add the second node identifier to a first index and a second index corresponding to the first association type and the first node identifier.

6. The system of claim 5 wherein the one or more cache nodes are operative to

maintain a count value for each association set;

increment count values in response to commands to add an association corresponding to respective association sets; and

decrement count values in response to commands to delete an association corresponding to respective association sets.

7. A method comprising:

a cache layer comprising one or more cache nodes, each cache node;

maintaining in a memory one or more data structures storing association information describing associations between nodes in a graph a plurality of distributed cache clusters for storing information in the form of a graph, the graph comprising a plurality of nodes, each uniquely identified by a node identifier, and edge information indicating associations between nodes;

responding to queries for associations between nodes in the graph by accessing the memory;

forwarding other queries to a database for processing.

8. The method of claim 7 further comprising:

each cache node

receiving a request to change the association information in the memory;

changing the association in the memory;

modifying the request for implementation by the database and forwarding the modifying request to the database for processing.

9. The method of claim 7 wherein the cache layer comprises a plurality of distributed cache clusters, each cache cluster comprising a plurality of cache nodes, each cache cluster allocated one or more data shards, each of the cache nodes of a cache cluster storing association information for nodes corresponding to the allocated data shards.

10. The method of claim 9 wherein the plurality of cache clusters comprise:

a leader cache cluster comprising a plurality of leader nodes; and

one or more follower cache clusters each comprising a plurality of follower cache nodes.

11. The method of claim 7 further comprising:

each cache node

maintaining in a memory, for each association set corresponding to a first node of a plurality of nodes and an association type of a plurality of association types, a first index and a second index;

wherein the first index comprises an ordered array of entries, each entry including a node identifier of a second node that is associated with the first node and a sorting attribute;

wherein the second index comprises a hash table comprising entries corresponding to the node identifiers of respective second nodes that are associated with the first node;

receiving a command to add an association of a first association type between a first node and a second node, the command including a first node identifier and a second node identifier;

accessing the memory against the first association type and the first node identifier to add the second node identifier to a first index and a second index corresponding to the first association type and the first node identifier.

12. The method of claim 11 further comprising:

each cache node

maintaining a count value for each association set;

incrementing count values in response to commands to add an association corresponding to respective association sets; and

decrementing count values in response to commands to delete an association corresponding to respective association sets.

13. A non-transitory storage medium storing computer-readable instructions, the instructions, when executed, operative to cause one or more processors to:

operate as a cache node in a cache layer comprising one or more cache nodes, the one or more cache nodes operative to

maintain in a memory one or more data structures storing association information describing associations between nodes in a graph a plurality of distributed cache clusters for storing information in the form of a graph, the graph comprising a plurality of nodes, each uniquely identified by a node identifier, and edge information indicating associations between nodes;

respond to queries for associations between nodes in the graph by accessing the memory;

forwarding other queries to the database for processing.

14. The storage medium of claim 13 wherein the one or more cache nodes are operative to

receive a request to change the association information in the memory;

change the association in the memory;

modifying the request for implementation by the database and forwarding the modifying request to the database for processing.

15. The storage medium of claim 13 wherein the cache layer comprises a plurality of distributed cache clusters, each cache cluster comprising a plurality of cache nodes, each cache cluster allocated one or more data shards, each of the cache nodes of a cache cluster storing association information for nodes corresponding to the allocated data shards.

16. The storage medium of claim 13 wherein the plurality of cache clusters comprise:

a leader cache cluster comprising a plurality of leader nodes; and

one or more follower cache clusters each comprising a plurality of follower cache nodes.

17. The storage medium of claim 13 wherein the one or more cache nodes are operative to

maintain in a memory, for each association set corresponding to a first node of a plurality of nodes and an association type of a plurality of association types, a first index and a second index;

wherein the first index comprises an ordered array of entries, each entry including a node identifier of a second node that is associated with the first node and a sorting attribute;

wherein the second index comprises a hash table comprising entries corresponding to the node identifiers of respective second nodes that are associated with the first node;

receive a command to add an association of a first association type between a first node and a second node, the command including a first node identifier and a second node identifier;

access the memory against the first association type and the first node identifier to add the second node identifier to a first index and a second index corresponding to the first association type and the first node identifier.

18. The storage medium of claim 13 wherein the one or more cache nodes are operative to

maintain a count value for each association set;

increment count values in response to commands to add an association corresponding to respective association sets; and

decrement count values in response to commands to delete an association corresponding to respective association sets.