Facebook keeps its social graph in memory, as an adjacency list, so that lookups are fast.
Memcached is a mature piece of technology at Facebook. Facebook was one of the first companies with a massive graph network, and graph databases are not common.
A graph is represented as an adjacency matrix or an adjacency list. The number of users is very large and the matrix is very sparse, so the graph is kept as an adjacency list:
- A map. The key is a person and the value is the list of that person's friends. Get key Gaurav returns his friends.
- A map inside it. Checking whether Harsha and Gaurav are friends goes through the list. Stored as a map, the check is order one.
A request for a news feed, or for friends having birthdays, goes through the friend list. These queries are made in memory.
The objectives are low latency, high availability and ease of use. Very high consistency is not needed. A cache used by one or two teams limits its optimizations to one team.