# US 2015/0106359 A1 · Distributed Cache for Graph Data

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0106359 A1
- Document ID: US20150106359A1
- Status: Published application
- Kind: A1
- Application number: 14/577,190
- Filed: 2014-12-19
- Published: 2015-04-16
- Earliest claimed: 2010-12-30
- Assignees: Facebook, Inc.
- Applicants: Facebook, Inc.
- Inventors: Venkateshwaran Venkataramani; George Cabrera, III; Venkatasiva Prasad Chakkabala; Mark Marchukov
- Web page: https://patentgrep.com/patent/US20150106359A1

## CPC

- G06F 16/24552: {Database cache management}
- G06F 12/0844: Multiple simultaneous or quasi-simultaneous cache accessing
- G06F 16/2255: {Hash tables}
- G06F 16/2379: {Updates performed during online database operations; commit processing}
- G06F 16/245: Query processing
- G06F 16/24539: {using cached or materialised query results}
- G06F 16/248: Presentation of query results
- G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
- G06F 16/284: {Relational databases}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 16/955: using information identifiers, e.g. uniform resource locators [URL]
- G06F 16/9574: {of access to content, e.g. by caching}
- H04L 67/568: Storing data temporarily at an intermediate stage, e.g. caching
- G06F 16/172: Caching, prefetching or hoarding of files
- G06F 2212/463: File
- G06F 2212/60: Details of cache memory
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

In one embodiment, a system includes a database operative to maintain a social graph; and a cache layer comprising a plurality of data shards, the data shards being divided among a plurality of cache nodes of a cache layer, wherein each data shard is operative to: maintain at least a portion of the social graph; receive a request to store associations between a first graph node and a second graph node of the social graph, wherein the first and second graph nodes are identified by a first and second unique identifier, respectively, the first and second graph nodes each corresponding to a particular data shard of the plurality of data shards; and update, responsive to the request, the data shard corresponding to the first graph node and the data shard corresponding to the second graph node.

## Claims

### Claim 1

A system comprising: a database operative to maintain a social graph; and a cache layer comprising a plurality of data shards, the plurality of data shards being divided among a plurality of cache nodes of the cache layer, wherein each data shard is operative to:
maintain at least a portion of the social graph, the social graph comprising a plurality of graph nodes and a plurality of graph edges connecting the graph nodes, each graph edge connecting two graph nodes indicating an association between the two graph nodes;
receive a request to store associations between a first graph node and a second graph node, wherein the first and second graph nodes are identified by a first and second unique node identifier (node ID), respectively, the first and second graph nodes each corresponding to a particular data shard of the plurality of data shards; and
update, responsive to the request, the data shard corresponding to the first graph node and the data shard corresponding to the second graph node.

### Claim 2 (depends on 1)

The system of claim 1, wherein the first graph node and second graph node correspond to the same data shard.

### Claim 3 (depends on 1)

The system of claim 1, wherein each of the cache nodes stores a plurality of data shards.

### Claim 4 (depends on 1)

The system of claim 1, wherein each data shard is further operative to forward a request to the database to update associations between the first graph node and the second graph node.

### Claim 5 (depends on 1)

The system of claim 1, wherein each data shard is assigned a range of unique node IDs.

### Claim 6 (depends on 1)

The system of claim 1, wherein the first node corresponds to a first data shard and the second graph node corresponding to a second data shard.

### Claim 7 (depends on 6)

The system of claim 6, wherein the first and second data shards are in different cache clusters of the cache layer.

### Claim 8 (depends on 1)

The system of claim 1 wherein the plurality of graph nodes is assigned a plurality of unique nodes IDs, respectively, each unique node ID of a graph node being assigned to a particular data shard of the plurality of data shards.

### Claim 9 (depends on 1)

The system of claim 1, wherein the cache layer further comprises a plurality of cache clusters, each of the one or more cache clusters comprising a subset of cache nodes from the plurality of cache nodes.

### Claim 10 (depends on 9)

The system of claim 9, wherein the plurality of data shards is assigned a plurality of unique shard identifiers (shard IDs), respectively, each unique shard ID being assigned to a particular cache node of the plurality of cache nodes.

### Claim 11 (depends on 10)

The system of claim 10, wherein each cache cluster is assigned a range of unique shard IDs.

### Claim 12 (depends on 11)

The system of claim 11, wherein the range of unique shard IDs assigned to each cache cluster varies dynamically.

### Claim 13 (depends on 11)

The system of claim 11, wherein the range of unique shard IDs assigned to each cache cluster varies statically.

### Claim 14 (depends on 10)

The system of claim 10, wherein data objects stored in the data shards of each follow cache cluster are also stored in the data shards of the leader cache cluster assigned to the follower cache cluster.

### Claim 15 (depends on 9)

The system of claim 9, wherein the plurality of cache clusters comprise one or more leader cache clusters and a plurality of follower cache clusters, each follower cache cluster being assigned to one of the leader cache clusters, wherein a portion of the plurality of data shards is divided among each leader cache cluster and its assigned follower cache clusters.

### Claim 16 (depends on 15)

The system of claim 15, wherein the plurality of data shards maintains the same information stored within the leader and follower cache clusters.

### Claim 17

A method comprising, by one or more data shards of a cache layer, the plurality of data shards being divided among a plurality of cache nodes of the cache layer:
maintaining at least a portion of a social graph, the social graph being maintained in a database and comprising a plurality of graph nodes and a plurality of graph edges connecting the graph nodes, each graph edge connecting two graph nodes indicating an association between the two graph nodes;
receiving a request to store associations between a first graph node and a second graph node, wherein the first and second graph nodes are identified by a first and second unique node identifier (node ID), respectively, the first and second graph nodes each corresponding to a particular data shard of the plurality of data shards; and
updating, responsive to the request, the data shard corresponding to the first graph node and the data shard corresponding to the second graph node.

### Claim 18

A non-transitory storage medium storing computer-readable instructions, the instructions, when executed, operative to cause one or more processors of a data shard of a plurality of data shards divided among a plurality of cache nodes of a cache layer to:
maintain at least a portion of the social graph, the social graph being maintained in a database and comprising a plurality of graph nodes and a plurality of graph edges connecting the graph nodes, each graph edge connecting two graph nodes indicating an association between the two graph nodes;
receive a request to store associations between a first graph node and a second graph node, wherein the first and second graph nodes are identified by a first and second unique node identifier (node ID), respectively, the first and second graph nodes each corresponding to a particular data shard of the plurality of data shards; and
update, responsive to the request, the data shard corresponding to the first graph node and the data shard corresponding to the second graph node.
