Distribution cache for graph data

Patent metadata

Field	Value
Publication number	US-8954675-B2
Application number	US-201314080573-A
Country	US
Kind code	B2
Filing date	Nov 14, 2013
Priority date	Dec 30, 2010
Publication date	Feb 10, 2015
Grant date	Feb 10, 2015

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.

First claim

What is claimed is:

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 socia

Assignees

• Facebook Inc

Inventors

• Venkataramani Venkateshwaran
• Cabrera Iii George
• Chakkabala Venkatasiva Prasad
• Marchukov Mark

Classifications

• G06F2212/463

  File · CPC title

• G06F16/27 Primary

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title

• G06F16/955

  using information identifiers, e.g. uniform resource locators [URL] · CPC title

• G06F16/2379

  Updates performed during online database operations; commit processing · CPC title

• G06F16/2255

  Hash tables · CPC title