Storage, sharding and the timeline cache

IDs: Twitter's Snowflake

Tweets need unique IDs generated on many machines without a central counter. Twitter's requirements for Snowflake (2010): IDs that are "roughly time ordered", that fit in 64 bits, and a generator at least as available as the services that use it.

The layout, from Snowflake's source:

| 1 bit: unused (sign) | 41 bits: ms since a custom epoch | 5 bits: datacenter | 5 bits: worker | 12 bits: sequence |

• Time: 41 bits of milliseconds since Twitter's epoch, 1288834974657 (4 November 2010). $2^{41}$ ms is about 69.7 years.
• Machine: 5 bits of datacenter and 5 of worker, 1,024 generators in all.
• Sequence: 12 bits, so 4,096 IDs per millisecond per generator. The README says it "rolls over every 4096 per machine (with protection to avoid rollover in the same ms)".

Because time is in the high bits, sorting by ID is roughly sorting by time. The README promises "k-sorted" IDs within about a second, not exact order: two generators' clocks differ slightly. It also depends on clocks not running backwards. Snowflake "will refuse to generate ids" until the clock passes the last time it used.

Where tweets live

The primer stores each user's own tweets (the user timeline) in a relational database. At this write volume, a single primary "would overwhelm a single SQL Write Master-Slave". The primer points to federation, sharding, denormalization and SQL tuning, or moving some data to NoSQL. It also suggests keeping only a month of tweets in the Tweet Info Service.

If you shard, the key decides which queries stay on one shard:

• By user_id: a user's own timeline is a single-shard read. But a very active or very popular user concentrates load on one shard.
• By tweet_id: writes spread evenly. But a user's timeline then needs a secondary index or a query to every shard.

Media goes to an object store.

The home timeline cache

The primer's Redis list per user holds 17-byte entries (tweet ID, user ID, metadata):

LPUSH timeline:123 <tweet id>     # O(1) per element added
LTRIM timeline:123 0 799          # O(N), N = entries removed (usually 1 here)
LRANGE timeline:123 0 19          # O(S+N): S = offset from the head, N = entries returned

Reading the first page is cheap because $S = 0$ and $N$ is the page size. Twitter capped each home timeline at 800 entries.

Keep timelines only for active users. If someone returns after 30 days away, rebuild from the user graph and the SQL database. That user's first request is slower, which is the price of not holding everyone's timeline in RAM.