Snowflake 64-bit IDs, sharding by user or by tweet, and the Redis home timeline cache.
What you will learn
Read Snowflake's 64-bit ID layout, and what "roughly time ordered" means.
Choose a shard key for stored tweets.
Keep home timelines in a capped Redis list per active user.
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). 241 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. Its documentation 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 documentation 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 relationaldatabase. 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 it starts at the head (Swhat its symbols mean is 0) and Nwhat its symbols mean, the number of entries returned, 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 SQLdatabase. That user's first request is slower, which is the price of not holding everyone's timeline in RAM.
Snowflake IDs and the home timeline cache
64-bit structure
Twitter Snowflake 64-bit integer layout
ID: 1856487137080668161
1b
0
Sign
41 bits
ms since the epoch (~69.7 years)
Δ 442621025343 ms
5 bits
DC: 3
0–31
5 bits
Worker: 7
0–31
12 bits
Sequence: 1
4,096/ms
Datacenter:
Worker:
Home timeline cache, a Redis list (timeline:123)
User status:
@alice_devDeploying Raft consensus cluster to Kubernetes...
Snowflake: 1856729104820192257
@bob_systemsLSM-trees vs B-Trees: write amplification benchmarks.
Snowflake: 1856729104820192258
@carol_archConsistent hashing with 256 virtual nodes.
Snowflake: 1856729104820192259
What happened
Home timeline cache ready. Snowflake IDs are unique 64-bit numbers, roughly time ordered.
Write API7× instancesRead API101× instancesID generators(Snowflake)2× instancesTweets database(sharded by user ID)8× instancesObject store (media)1× instanceHome timeline cache15× instancesUser graph (whofollows whom)2× instancesWrite API7× instancesRead API101× instancesID generators(Snowflake)2× instancesTweets database(sharded by user ID)8× instancesObject store (media)1× instanceHome timeline cache15× instancesUser graph (whofollows whom)2× instances
Figure 3
Where the data lives: IDs from Snowflake generators, tweets in a database sharded by user ID, media in an object store, and home timelines in a memory cache.
Follow a new tweet: the Write API takes an ID from an ID generator, with no central counter, stores the tweet on the shard that holds its author’s tweets, and stores its media in the object store. Reading a home timeline is one list read from the timeline cache, which the fan-out of figure 2 fills. For a user away more than 30 days the cache holds no timeline, so the Read API rebuilds it: it asks the user graph who the user follows, reads their tweets from the tweets database and fills the cache. Sharding by user ID keeps each user timeline on one shard, at the price of busy users’ shards.
Write API: 7 × App server
Read API: 101 × App server
ID generators (Snowflake): 2 × App server
Tweets database (sharded by user ID): 8 × Relational database
Object store (media): 1 × Object store
Home timeline cache: 15 × Cache
User graph (who follows whom): 2 × Relational database
Write API sends requests to ID generators (Snowflake)
Write API sends requests to Tweets database (sharded by user ID)
Write API sends requests to Object store (media)
Read API sends requests to Home timeline cache
Read API sends requests to User graph (who follows whom)
Read API sends requests to Tweets database (sharded by user ID)
Key takeaways
Snowflake packs 41 bits of milliseconds, 10 bits of machine and 12 bits of sequence; sorting by ID matches time order to within about a second, not exactly, because clocks differ.
Sharding by user_id keeps a user's timeline on one shard but concentrates busy users; sharding by tweet_id spreads writes but scatters each timeline.
Each home timeline is a capped list of IDs (Twitter kept 800); returning inactive users get a slower first request while their timeline is rebuilt.