Distributed cache for graph data
View Patent ↗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.
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.