Distributed cache for graph data

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 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 leader cache clusters that each comprise one or more leader cache nodes and a plurality of follower cache clusters that each comprise one or more follower cache nodes, wherein each leader cache cluster includes a plug-in operative to translate graph information about graph nodes and graph edges stored in the cache layer to a command for the database, wherein the command includes one or more flat files, each leader cache node being operative to:

communicate graph information between the follower cache clusters and the database, wherein each follower cache cluster maintains at least a portion of the graph;

receive a request from one of the follower cache nodes to store graph information in the database;

update the database storing the graph responsive to the request; and

update one or more of the follower cache nodes storing the portion of the graph associated with the request.

2. The system of claim 1 , wherein the database is a relational database.

3. The system of claim 1 , wherein the database utilizes MySQL.

4. They system of claim 1 , wherein each leader cache node is further operative to:

receive a query associated with graph information stored in the leader cache node; and

respond to the query at least in part by accessing the portion of the graph maintained in the leader cache node.

5. The system of claim 4 , wherein the query is passed through to the database for execution.

6. The system of claim 1 , wherein each leader cache cluster is allocated a subset of a plurality of data shards, the plurality of data shards each comprising one or more shard IDs, wherein each shard ID corresponds to a particular graph node of the graph.

7. The system of claim 6 , where each leader cache node is further operative to:

receive a second request from one of the follower cache nodes requesting information associated with the graph, wherein the second request includes the shard ID of the graph node;

retrieve the requested information based on the shard ID; and

send the requested information to the follow cache node that requested the information.

8. The system of claim 7 , further comprising:

send the second request to the database when the requested information is not cached within the leader cache node;

retrieve the requested information from the database;

update the particular shard ID in the leader cache node to store the retrieved data; and

send the requested information to the follow cache node that requested the information.

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

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;

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.

10. The system of claim 9 , wherein the leader 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.

11. 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 associated with the social-networking system.

12. 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 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 leader cache clusters that each comprise one or more leader cache nodes and a plurality of follower cache clusters that each comprise one or more follower cache nodes, wherein each leader cache cluster includes a plug-in operative to translate graph information about graph nodes and graph edges stored in the cache layer to a command for the database, wherein the command includes one or more flat files, each leader cache node being operative to:

communicating graph information between the follower cache clusters and the database, wherein each follower cache clusters maintains at least a portion of the graph;

receiving a request from one of the follower cache nodes to store graph information in the database;

updating the database storing the graph responsive to the request; and

updating one or more of the follower cache nodes storing the portion of the graph associated with the request.

13. The method of claim 12 , wherein each leader cache cluster is allocated a subset of a plurality of data shards, the plurality of data shards each comprising one or more shard IDs, wherein each shard ID corresponds to a particular graph node of the graph.

14. The method of claim 13 , where each leader cache node is further operative to:

receiving a second request from one of the follower cache nodes requesting information associated with the graph, wherein the second request includes the shard ID of the graph node;

retrieving the requested information based on the shard ID; and

sending the requested information to the follow cache node that requested the information.

15. The method of claim 14 , further comprising:

sending the second request to the database when the requested information is not cached within the leader cache node;

retrieving the requested information from the database;

updating the particular shard ID in the leader cache node to store the retrieved data; and

sending the requested information to the follow cache node that requested the information.

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

provide, by one or more first computing devices, 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 associated with a social-networking system and having a unique graph-node identifier; and

provide, by a plurality of second computing devices coupled to the one or more first computing devices, a cache layer between the persistent-storage database and a plurality of client servers, the cache layer comprising a plurality of leader cache clusters that each comprise one or more leader cache nodes and a plurality of follower cache clusters that each comprise one or more follower cache nodes, wherein each leader cache cluster includes a plug-in operative to translate graph information about graph nodes and graph edges stored in the cache layer to a command for the database, wherein the command includes one or more flat files, each leader cache node being operative to:

communicate graph information between the follower cache clusters and the database, wherein each follower cache cluster maintains at least a portion of the graph;

receive a request from one of the follower cache nodes to store graph information in the database;

update the database storing the graph responsive to the request; and

update one or more of the follower cache nodes storing the portion of the graph associated with the request.

17. The media of claim 16 , wherein each leader cache cluster is allocated a subset of a plurality of data shards, the plurality of data shards each comprising one or more shard IDs, wherein each shard ID corresponds to a particular graph node of the graph.

18. The media of claim 17 , where each leader cache node is further operative to:

receive a second request from one of the follower cache nodes requesting information associated with the graph, wherein the second request includes the shard ID of the graph node;

retrieve the requested information based on the shard ID; and

send the requested information to the follow cache node that requested the information.