Distributed cache for graph data

• US 8,832,111 B2
• Filed: 09/07/2011
• Issued: 09/09/2014
• 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, Cabrera, George III, Chakkabala, Venkatasiva Prasad, Marchukov, Mark, Petrov, Dmitri
• Primary Examiner(s): Mahmoudi, Tony
• Assistant Examiner(s): NGUYEN, MERILYN P
• Application Number:
  US13/227,393
• Publication Number:
  US 20120173541A1
• Time in Patent Office: 1,098 Days
• Field of Search: 707/747, 707/737, 707/741, 707/752, 707/798, 707/830
• US Class Current: 707/741
• 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:

one or more first computing devices providing a persistent-storage database operative to maintain a graph comprising graph nodes and graph edges connecting the graph nodes, a graph edge connecting two graph nodes indicating an association between the two graph nodes, each graph node corresponding to a profile page associated with a social-networking system and having a unique graph-node identifier; and

a plurality of second computing devices coupled to the one or more first computing devices and providing a cache layer between the persistent-storage database and a plurality of client servers, the cache layer comprising a plurality of follower cache clusters that each comprise one or more follower cache nodes that each comprise at least one individual computing system, each follower cache node being operative to;

maintain in a memory of the at least one individual computing system at least a portion of the graph;

receive a query for associations between nodes in the graph from a client server;

respond to the query for associations between nodes in the graph at least in part by accessing the least a portion of the graph maintained in the memory of the at least one individual computing system; and

maintain in the memory, for each association set corresponding to a first graph node of a plurality of graph nodes and an association type of a plurality of association types, a first index and a second index, the first index comprising an ordered array of entries, each entry comprising a graph-node identifier of a second graph node that is associated with the first node and a sorting attribute, the second index comprising a hash table comprising entries corresponding to the node identifiers of respective second nodes that are associated with the first node.

2. The system of claim 1, wherein the follower cache node is operative to respond to the query by:

storing, updating, deleting, or retrieving information associated with at least one graph node or graph edge in the at least a portion of the graph in the memory of the at least one individual computing system based on the query;

modifying the query for processing by the persistent-storage database; and

forwarding the query as modified to the persistent-storage database for processing.

3. The system of claim 1, wherein each follower cache cluster is allocated a subset of a plurality of data shards.

4. The system of claim 1, wherein the cache layer further comprises a leader cache cluster comprising a plurality of leader cache nodes.

5. The system of claim 1, wherein the follower cache node is further operative to:

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; and

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 follower cache node is further 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:

by one or more first computing devices, providing a persistent-storage database operative to maintain a graph comprising graph nodes and graph edges connecting the graph nodes, a graph edge connecting two graph nodes indicating an association between the two graph nodes, each graph node corresponding to a profile page associated with a social-networking system and having a unique graph-node identifier; and

by a plurality of second computing devices coupled to the one or more first computing devices, providing a cache layer between the persistent-storage database and a plurality of client servers, the cache layer comprising a plurality of follower cache clusters that each comprise one or more follower cache nodes that each comprise at least one individual computing system, each follower cache node;

maintaining in a memory of the at least one individual computing system at least a portion of the graph;

receiving a query for associations between nodes in the graph from a client server;

responding to the query for associations between nodes in the graph at least in part by accessing the least a portion of the graph maintained in the memory of the at least one individual computing system; and

maintain in the memory, for each association set corresponding to a first graph node of a plurality of graph nodes and an association type of a plurality of association types, a first index and a second index, the first index comprising an ordered array of entries, each entry comprising a graph-node identifier of a second graph node that is associated with the first node and a sorting attribute, the second index comprising a hash table comprising entries corresponding to the node identifiers of respective second nodes that are associated with the first node.

8. The method of claim 7, wherein responding to a query comprises:

storing, updating, deleting, or retrieving information associated with at least one node or edge in the at least a portion of the graph in the memory of the at least one individual computing system based on the query;

modifying the query for processing by the persistent-storage database; and

forwarding the query as modified to the persistent-storage database for processing.

9. The method of claim 7, wherein each follower cache cluster is allocated a subset of a plurality of data shards.

10. The method of claim 9, wherein the cache layer further comprises a leader cache cluster comprising a plurality of leader cache nodes.

11. The method of claim 7, wherein each of the follower cache nodes is operative to:

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; and

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.

12. The method of claim 11, wherein each of the follower cache nodes is further 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.

13. A plurality of non-transitory computer-readable storage media embodying software that is operative when executed to:

provide a persistent-storage database operative to maintain a graph comprising graph nodes and graph edges connecting the graph nodes, a graph edge connecting two graph nodes indicating an association between the two graph nodes, each graph node corresponding to a profile page associated with a social-networking system and having a unique graph-node identifier; and

provide a cache layer between the persistent-storage database and a plurality of client servers, the cache layer comprising a plurality of follower cache clusters that each comprise one or more follower cache nodes that each comprise at least one individual computing system, each follower cache node being operative to;

maintain in a memory of the at least one individual computing system at least a portion of the graph;

receive a query for associations between nodes in the graph from a client server;

respond to the query for associations between nodes in the graph at least in part by accessing the least a portion of the graph maintained in the memory of the at least one individual computing system; and

maintain in the memory, for each association set corresponding to a first graph node of a plurality of graph nodes and an association type of a plurality of association types, a first index and a second index, the first index comprising an ordered array of entries, each entry comprising a graph-node identifier of a second graph node that is associated with the first node and a sorting attribute, the second index comprising a hash table comprising entries corresponding to the node identifiers of respective second nodes that are associated with the first node.

14. The media of claim 13, wherein the follower cache node is operative to respond to the query by:

storing, updating, deleting, or retrieving information associated with at least one graph node or graph edge in the at least a portion of the graph in the memory of the at least one individual computing system based on the query;

modifying the query for processing by the persistent-storage database; and

forwarding the query as modified to the persistent-storage database for processing.

15. The media of claim 13, wherein each follower cache cluster is allocated a subset of a plurality of data shards.

16. The media of claim 13, wherein the cache layer further comprises a leader cache cluster comprising a plurality of leader cache nodes.

17. The media of claim 13, wherein the follower cache node is further operative to:

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; and

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 media of claim 17, wherein the follower cache node is further 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.

19. The system of claim 1, wherein:

at least a portion of the graph is a social graph of the social-networking system;

at least some of the nodes correspond to users of the social-networking system; and

at least some of the nodes correspond to concepts.

20. The method of claim 7, wherein:

at least a portion of the graph is a social graph of the social-networking system;

at least some of the nodes correspond to users of the social-networking system; and

at least some of the nodes correspond to concepts.