Hash versus locality-aware placement, why cross-shard lookups never disappear, and TAO’s leader and follower cache tiers.
What you will learn
Compare hash placement with placement that keeps friends together.
Explain TAO's leader and follower cache tiers.
Say how TAO stays consistent and handles hot objects and other regions.
Where to put each person
With hash partitioning, hash(user_id)modNwhat its symbols mean, people spread evenly over Nshards. But a person's friends land on shards at random. Fetching all fwhat its symbols mean friends of someone touches up to min(f,N)what its symbols mean 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 set of programs for partitioning graphs. Facebook used its own method, Balanced Label Propagation (Ugander and Backstrom, 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.
Where friends land on shards
Eight people in two tight groups. Compare hash(user_id) mod 4 with putting each group on its own shard, and count the friend lookups that leave the user's shard.
Shard 0
David, Hanna
Shard 1
Carin, Gunnar
Shard 2
Birger, Frida
Shard 3
Astrid, Erik
Friendships split across shards
12 of 13
Friends and friends-of-friends
4 + 3
Lookups on another shard
6
Shards touched
4
Real social graphs are not this tidy. Facebook's TAO paper says that "it is not possible to group users so that cross-partition requests are rare", so grouping reduces cross-shard lookups but cannot remove them.
TAO in one region: clients talk to a follower tier, followers send misses and writes to the leader tier, and only leaders use the sharded database.
Follow a read. The client asks a cache server in its follower tier, which answers from its cache or forwards the miss to the leader for that shard; the leader answers from its own cache or reads the database. A write takes the same way to the leader, which writes the database and then tells the followers asynchronously, with invalidation or refill messages. Each tier holds every shard, mapped onto its servers by consistent hashing, so either follower tier can answer any request. The paper gives no server counts: each tier is drawn with three cache servers, to show that a tier is several servers, and the database as a leader with a standby. Other regions have their own tiers and database replicas, and send their writes to this region’s leaders.
Web servers (TAO clients): 1 × Users
Follower tier 1: 3 × Cache
Follower tier 2: 3 × Cache
Leader tier: 3 × Cache
Sharded database (MySQL): 2 × Relational database
Web servers (TAO clients) sends requests to Follower tier 1
Web servers (TAO clients) sends requests to Follower tier 2
Follower tier 1 sends requests to Leader tier
Follower tier 2 sends requests to Leader tier
Leader tier sends requests to Sharded database (MySQL)
Key takeaways
Hashing spreads people evenly but scatters friends, so one friend list can touch many shards; grouping by location or community keeps more lookups local, but cross-shard lookups stay common.
In TAO every write to a shard goes through its leader cache, which also stops thundering herds reaching MySQL; followers serve the reads.
Leaders invalidate or refill followers asynchronously, so reads are eventually consistent; other regions read locally and send writes to the master region.
Hot shards are cloned across followers, and very hot items are cached in the client.