jonnify·redis /redis-patterns/production-operations/pinterest-task-queue/functional-partitioning

R8.03.1 · Pinterest: task queues & partitioning — dive 1

Functional partitioning: let the identity decide placement.

Pinterest put each kind of data on the store that fit how it was read, and built a row’s shard into its id — so a read finds its location by arithmetic, with no lookup table.

Grounding: the Pinterest case study (Sharding Pinterest) · the BCS echo — the {q} hashtag + CRC16 slot in echo_mq/keyspace.ex · the branded-id placement in echo_data/branded_id.ex. Valkey is the BCS engine; Pinterest’s Redis/MySQL/memcache is the case study.

Read a 64-bit Pinterest id. Three fields packed into one integer; select a field to see its bit range and what it tells a reader — the shard field alone names where the row lives.
64-bit id — high bits left, low bits right shard id bits 46–61 · 16b type id bits 36–45 · 10b local id bits 0–35 · 36b the shard field alone names the shard — no lookup shard 0 shard 1 shard 2 shard 3 … up to 2¹⁶ shards
readout · Select a field. The id packs three numbers; the shard field in the high bits tells a reader which shard holds the row, found by a right shift, never by a lookup table.

The scheme (verbatim) — ID = (shard ID << 46) | (type ID << 36) | (local ID<<0). A new Pin is assigned to the same shard id as the board it is inserted into, so a board and its pins co-locate.

§1

Polyglot by access pattern

Sharding Pinterest · functional partitioning

By September 2011 every piece of Pinterest’s infrastructure was over capacity. The sharding work they launched in early 2012 — “still the system we use today” — carried 50 billion Pins across one billion boards. Part of that design was refusing to force every kind of data into one engine.

The split they describe is verbatim: “We keep pin_id → pin object cache in a memcache cluster, but we keep board_id → pin_ids in a redis cluster.” Two kinds of data, two stores, chosen by how each is read. A pin object is a value fetched by key — a cache read, served well by memcache. A board’s list of pin ids is an ordered collection that grows and is scanned — a list, served well by Redis.

This is functional partitioning: divide the system by function — by what a piece of data is for and how it is touched — not by carving one homogeneous store into ranges. The data did not pick the engine; the access pattern did. The store that fits the read is the store the data goes on.

a value fetched by key

pin_id → pin object in a memcache cluster — a cache read, no scan, no ordering.

an ordered collection that grows

board_id → pin_ids in a redis cluster — a list that is appended to and scanned.

Two kinds of read, two engines. The split is by access pattern, not by data type forced into a single store — the first half of letting the system grow on the right substrate.

§2

The shard in the id

Sharding Pinterest · the id scheme

The second move is sharper. Pinterest gave every id its location. The scheme is verbatim a 64-bit id:

# the id scheme, verbatim from Sharding Pinterest
ID = (shard ID << 46) | (type ID << 36) | (local ID<<0)

The shard id is 16 bits in the high part — which shard this row lives on. The type id is 10 bits — which kind of object (a pin, a board, a comment). The local id is 36 bits — the row’s id within that type on that shard.

A new Pin is assigned “to the same shard ID as the board it’s inserted into,” so a board and the pins on it land on one shard, and the id alone tells a reader where the row is. There is no lookup table mapping id to location: the location is read straight out of the high bits with a shift.

That is the property that lets the fleet grow. A read goes to one shard, found by arithmetic on the id, with no directory in the path. Pinterest paired it with a move-cost rule — “We hated moving data around, especially item by item… If we had to move data, it was better to move an entire virtual node to a different physical node” — so re-balancing moves a whole virtual node, never a row at a time.

shard id (16b)
The high bits. Read with id >> 46 — the row’s shard, no lookup.
type id (10b)
Which kind of object. A pin and a board on one shard differ here.
local id (36b)
The id within the type on the shard.
co-location
A pin takes its board’s shard id, so the board and its pins share a shard.

The shard is not stored beside the id in a directory; it is the id’s high bits. A read computes its destination, so adding shards never forces a lookup table into the hot path.

§3

The BCS echo — placement computed from identity

echo_mq/keyspace.ex · echo_data/branded_id.ex

The BCS bus reaches the same property by a different mechanism, and the difference is the lesson. EchoMQ does not embed a shard in the high bits of an id and read it back out. It does two computed things.

A queue’s keys are co-located by a hashtag. Every key of one queue is built as emq:{q}:<type> — the queue name sits inside the braces. EchoMQ.Keyspace computes the cluster slot client-side, with no server round trip:

# echo/apps/echo_mq/lib/echo_mq/keyspace.ex
def slot(key) when is_binary(key), do: rem(crc16(hashtag(key), 0), 16384)

hashtag/1 takes the substring inside the first {...}, crc16/2 is CRC16-XMODEM, and the result is taken modulo 16384 — the cluster specification’s algorithm. Because the slot is a function of the braced substring, every key of one queue lands on the same slot (the module’s own words). The known vector on disk is slot("123456789") == 12739. The queue name decides the location; nothing is looked up.

A branded id is hashed to a placement. The id itself carries placement too — not by reading a field, but by hashing the whole id to a bucket:

echo/apps/echo_data/lib/echo_data/branded_id.ex · the contract vectorfrozen
iex> EchoData.BrandedId.encode!("USR", 274557032793636864)
"USR0KHTOWnGLuC"
iex> EchoData.BrandedId.hash32(274557032793636864)
234878118

placement("USR0KHTOWnGLuC") → 234878118: decode the id to its snowflake, hash the snowflake to 32 bits, and that number is the consistent-hash bucket. The placement is derived from the identity, computed the same way on any node, with no registry.

The honest parallel is the principle, not the mechanism. Pinterest embeds the shard in the id’s high bits and bit-extracts it; echo hashes the id to a placement and co-locates a queue with the {q} hashtag. Both make placement a property of the identity — found by computation, never by a directory lookup. The branded snowflake’s node field is the minting node, the machine that created the id — not a storage shard; the placement comes from the hash and the hashtag, not from that field.

the application · identity carries location

The hashtag that co-locates a queue

A queue’s keys all share the braced tag, so they hash to one slot — the same property Pinterest got from the shard bits, here computed from the queue name, verbatim from the keyspace:

echo/apps/echo_mq/lib/echo_mq/keyspace.ex · co-location by hashtagfrozen
# every key of one queue lands on one slot
def queue_key(queue, type), do: ["emq:{", queue, "}:", type]

# the slot is a function of the braced substring — no registry
def slot(key), do: rem(crc16(hashtag(key), 0), 16384)

Notes on ValkeyValkey divides the keyspace into 16384 hash slots; a key’s slot is CRC16(key) mod 16384, and a {...} hashtag pins every key sharing the tag to the same slot — the rule the keyspace computes client-side so a queue’s keys co-locate. The algorithm and the hashtag rule are the engine’s own: valkey.io/topics/cluster-spec.

the pattern

Put data on the store that fits its access pattern, and make placement a function of the id — ID = (shard ID << 46) | … — so a read finds its shard by arithmetic, no lookup table.

its EchoMQ application

A queue’s keys are emq:{q}:<type>; slot/1 sends them all to one of 16384 slots, and a branded id hashes to a placement (placement("USR0KHTOWnGLuC") → 234878118). Computed client-side, no registry.

Pinterest put the shard in the id and the data on the store that fit it; echo computes a slot from the queue’s hashtag and a placement from the branded id. Different mechanisms, one principle: identity carries location, so a read never has to ask where a row lives.

§4

Recap — location is a function of identity

next → R8.03.2

Functional partitioning is two moves with one root. Put each kind of data on the store that fits its read — pin_id in memcache, board_id → pin_ids in Redis — and make a row’s location a function of its id, so a read computes its shard instead of consulting a directory. Pinterest does it by packing the shard into the id’s high bits; EchoMQ does it by the {q} hashtag and a hash of the branded id. The next dive keeps the claimed job safe between receive and acknowledge — the list-based reliable queue, and the server-clock lease that reaches the same guarantee.

§5

References

sources · related

Sources

Related in this course