Graph partitioning and the TAO cache

Where to put each person

With hash partitioning, $\text{hash}(\text{user\_id}) \bmod N$, people spread evenly over $N$ shards. But a person's friends land on shards at random. Fetching all $f$ friends of someone touches up to $\min(f, N)$ shards, and friends-of-friends touch more.

The primer suggests sharding Person Servers by location, "as friends generally live closer to each other", so more friend lookups stay on one server. More generally, a graph partitioner can place tightly connected groups together. METIS, for example, is a multilevel tool for partitioning graphs. Facebook used its own method, Balanced Label Propagation (Ugander and Backstrom, WSDM 2013), to maximize the share of edges kept on the same shard.

There is a limit, in TAO's words: "The social graph is tightly interconnected; it is not possible to group users so that cross-partition requests are rare." Good placement reduces cross-shard traffic but does not remove it, so the system must still handle many remote lookups cheaply, which is what the cache tier does.

The visual shows both on a tiny graph: hash placement splits most friendships across shards, while grouping keeps them together.

TAO's two-level cache

TAO places a cache between the application and MySQL:

• Sharding: each object belongs to a shard, and an association is stored on the shard of its id1. Shards are mapped onto cache servers "using consistent hashing".
• Leaders and followers: "Each shard is hosted by one leader, and all writes to the shard go through that leader." Follower tiers serve reads and forward read misses and writes to the leader. Splitting the cache this way keeps each tier small, because large tiers "are more prone to hot spots".
• The leader protects the database. Because one leader mediates all requests for an id1, it can avoid concurrent overlapping queries ("thundering herds") and limit pending queries per shard.
• Eventual consistency: the leader asynchronously sends invalidation or refill messages to followers, and TAO "guarantees the eventual delivery of an invalidation or refill to all tiers". Replication lag is "usually less than one second".
• Across regions: followers forward writes to the leader in the region with the master database, and serve reads locally, at the risk of slightly stale data.
• Hot objects: a shard that is read heavily is cloned across several followers, and very hot items are cached in the client.

Read misses at followers were "25 times as frequent as writes" in TAO's workload. That is why the design puts so much effort into serving reads locally.