Distribution cache for graph data

• US 8,954,675 B2
• Filed: 11/14/2013
• Issued: 02/10/2015
• 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
• Primary Examiner(s): NGUYEN, HIEP T
• Application Number:
  US14/080,573
• Publication Number:
  US 20140074876A1
• Time in Patent Office: 453 Days
• Field of Search: 707/747
• US Class Current: 711/124
• 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

In one embodiment, a system includes 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; and forward other queries to the database for processing.

Claims

1. A system comprising:

a database; and

a cache layer comprising one or more cache clusters, each of the one or more cache clusters operative to;

maintain, in a memory of one or more cache nodes of the cache cluster, at least a portion of a social graph, the social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each node being uniquely identified by a node identifier, and each edge indicating associations between nodes;

process one or more queries received from one or more client systems of users of a social network environment, the processing of each query comprising;

if the query is for associations between nodes in the portion of the social graph stored in the cache cluster, then respond to the query by searching the portion of the social graph stored in the memory of the cache cluster; and

if the query is not for associations between nodes in the portion of the social graph stored in the cache cluster, then forward the query to the database for processing; and

send, to the one or more client systems for display, search results responsive to the received queries.

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

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

change the association in the memory;

modify the request for implementation by the database; and

forward the modified 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 further 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; 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 one or more cache nodes are 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 each of one or more cache clusters in a cache layer:

maintaining, in a memory of one or more cache nodes of the cache cluster, at least a portion of a social graph, the social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each node being uniquely identified by a node identifier, and each edge indicating associations between nodes;

processing one or more queries received from one or more client systems of users of a social network environment, the processing of each query comprising;

if the query is for associations between nodes in the portion of the social graph stored in the cache cluster, then respond to the query by searching the portion of the social graph stored in the memory of the cache cluster; and

if the query is not for associations between nodes in the portion of the social graph stored in the cache cluster, then forward the query to the database for processing; and

sending, to the one or more client systems for display, search results responsive to the received queries.

8. The method of claim 7 further comprising, by each cache node:

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

changing the association in the memory; and

modifying the request for implementation by the database; and

forwarding the modified 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, by 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; and

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, by 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 cluster in a cache layer comprising one or more cache clusters, each of the one or more cache clusters operative to:

maintain, in a memory of one or more cache nodes of the cache cluster, at least a portion of a social graph, the social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each node being uniquely identified by a node identifier, and each edge indicating associations between nodes;

process one or more queries received from one or more client systems of users of a social network environment, the processing of each query comprising;

if the query is for associations between nodes in the portion of the social graph stored in the cache layer, then respond to the query by searching the portion of the social graph stored in the memory of the cache cluster; and

if the query is not for associations between nodes in the portion of the social graph stored in the cache cluster, then forward the query to the database for processing; and

send, to the one or more client systems for display, search results responsive to the received queries.

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

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

change the association in the memory;

modify the request for implementation by the database; and

forward the modified 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 further 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; 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 storage medium of claim 13 wherein the one or more cache nodes are 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.