Splitting the Writes, and the Number That Decides How Many Pieces

Last timeWhere the Reads Go

Why the shard count for a link shortener comes from the stored bytes rather than the write rate, how the key gets chosen, and what a popular key and a cross shard question each cost to repair.

The brief is a link shortener with click analytics, and the estimates are

already settled. There are 100,000,000 new links a day, which is 1,157 a second

and gets called 1,200 writes a second, and the peak is three times the mean, so

3,600. One machine of the kind priced earlier accepts 5,000 writes a second to

a disk based store and holds 1 TB of usable disk. The write rate fits on one

machine. The data does not. That one asymmetry decides what the split is for,

and it is worth saying out loud before any box is drawn.

The write rate was never the problem

At the peak the link store takes 3,600 writes a second against the 5,000 one

machine accepts, which is 72 per cent of the ceiling. Dividing the other way,

$5{,}000 / 3{,}600 = 1.39$ , so the write rate could grow by 39 per cent before

one machine ran out. That is thin but it is not a reason to buy a second

machine, and it is a very different position from the read side, where 360,000

peak reads against the 10,000 a second one machine serves from memory is 36

times over.

So nothing about writes a second forces anything here. The split is coming, and

it is coming for the bytes.

The shard count comes out of the bytes

A link row is 500 bytes, so 100,000,000 of them a day is

$100{,}000{,}000 \times 500 = 50$ GB a day, and

$50 \times 365 = 18{,}250$ GB, which is 18 TB a year. Against 1 TB of usable

disk per machine that is eighteen machines for the first year on its own.

The lesson stops here

8 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

Read alongside

paperDynamo: Amazon's Highly Available Key-value StoreDeCandia, Hastorun, Jampani, Kakulapati and others, 2007Assigning a record to a piece by hashing its key, with many more pieces than machines, which is the arrangement that makes the record to piece mapping permanent and the piece to machine mapping cheap to change.allthingsdistributed.com

bookDesigning Data-Intensive ApplicationsKleppmann, 2017Chapter 6 on partitioning sets out hashed against ranged keys, why a time ordered key concentrates the writes, what relieves a skewed workload, and why a query that does not name the key becomes a scatter and gather.dataintensive.net

paperThe Tail at ScaleDean and Barroso, 2013Measures how a request fanned out to many machines inherits the slowest of them, and how quickly a rare slow response becomes the common case as the fan out widens, which is the cost of the cross shard question here.dl.acm.org

paperEfficiently Updating Materialized ViewsBlakeley, Larson and Tompa, 1986The original treatment of keeping a derived answer current as the underlying rows change rather than recomputing it when asked, which is the standard repair for a total that would otherwise need every shard.doi.org