Design a URL Shortener

Marlow Books is an online bookshop run by four people, and it exists only in this course. In September its founder printed twenty thousand bookmarks with a QR code on them.

He could have put the shop's own address in the code. He used a short link instead, and the reason had nothing to do with length: he wanted a count of how many people scanned it. The shop's application could not tell him that without somebody writing code, and the shortener put it on a dashboard for nothing.

The artwork went to the printer on Friday 11 September. The bookmarks started going out one per parcel on Thursday 1 October, and at lesson 027's rate of one order every fifty seconds, 1,728 a day, the last of the twenty thousand left on Monday 12 October.

On Wednesday 21 October he rebuilt the Christmas gift guide and its address changed. Repointing the short link took him about forty seconds, which was the other reason he had used one.

On Friday 23 October a customer wrote in to say the bookmark led to a page that did not exist. He scanned his own bookmark and got the same dead page. The row in the shortener had said the new address since Wednesday afternoon.

There was nothing in any log to look at, and the dashboard explained why. The link had been fetched nine times. Ever.

One fetch per city. Lesson 022 counted the shop's customers at nine cities' worth of CDN edges, and the shortener keeps an edge in each of those cities too. The first scan in each place had reached the shortener itself, which answered 301 Moved Permanently with a year of freshness on it. Every scan after that was answered by a cache the shop neither owns nor can see. Moved Permanently is a promise, and it had been kept.

A support ticket at the shortener cleared the nine edges that afternoon, on somebody else's schedule. Every phone that had already scanned the bookmark kept the old answer, and there is no way to count those or reach them.

He had also spent three weeks believing twenty thousand bookmarks were a waste of a print run, on the evidence of a graph that could not have told him anything else.

You are designing that shortener.

The brief, and the two lines nobody puts on it

Two verbs, and that really is the functional specification. Take a long address and give back a short one. Take a short one and send the caller to the long one. Custom codes, click counts, expiry dates, a dashboard: all of that is product, and none of it changes a machine on the diagram.

Then two requirements nobody writes down, which between them decide everything worth deciding here.

A key, once issued, means that one thing for as long as the service runs. Not as a matter of tidiness. A short link gets printed on things, pasted into documents, left in somebody's 2019 email, stuck to a van as a QR sticker. Hand the same key out twice and you have given a stranger the steering wheel on the first owner's poster.

A link has to be revocable. The day you cannot turn one off, you are running a malware delivery service with an uptime guarantee, and no amount of terms of service makes that somebody else's problem.

For volume, call it fifty million new links a month and five billion redirects a month. Those are a mid-sized product's numbers rather than an impressive system's, and I picked them on purpose, because the most useful thing to learn from this design is how small it is.

A hundred reads per write. Sit with that for a second, because it is the opposite of what everyone assumes. Lesson 011 put Marlow's read to write ratio at two hundred to one, a couple of writes a second against four hundred reads at the Christmas peak, and the shop's ordinary Tuesday gives the same ratio because both sides fall by a factor of ten together. A shortener is half as read-heavy as a four person bookshop, because in a shortener every new link is a write and a bookshop's writes are purchases. Stagefront, the ticketing service in this course where two hundred thousand people press the same button at ten in the morning, sits at the far end of that line, and lesson 011 refused it a read replica outright because the only minute that matters there is writes.

Four lines on an envelope

Lesson 025's order, bytes first because they are hardest to argue with and money last because it belongs to somebody else.

Bytes. A row holds the key, the target, who made it and when. The target is the only part worth arguing about, and the thing to notice is that the population of addresses people shorten is not the population of addresses. Nobody shortens a six character domain. They shorten the three hundred character campaign link with six tracking parameters welded to the end of it. Call the average a hundred and fifty bytes, which is generous in a direction I am naming out loud, as lesson 025 asks.

With a nine character key, which the next section argues for, and two eight byte fields, call the whole row a hundred and eighty bytes once Postgres has taken its own overhead. Fifty million a month for five years is three billion rows, which is 540 gigabytes.

The index is the other half and it is the half people leave off. Three billion entries on the key, at about thirty bytes each once you count the tuple header and the room a B-tree leaves itself, is ninety gigabytes. That thirty is my figure rather than a measurement, and it is the first thing I would go and check, because a later section hangs a cliff off it.

So 630 gigabytes: every link anybody made in five years, on one machine, with room. Lesson 031 put Galewatch, which collects a reading every two seconds from each turbine on the wind farms it monitors, at nineteen Postgres machines holding 5.5 terabytes. The entire corpus of this famous system is a ninth of one telemetry company's disk.

Writes. Nineteen a second on average. The peak here is a marketing campaign rather than Christmas, which is a flatter shape than Marlow's tenfold December, so call it five times and round up: about a hundred a second. That five is mine and nothing downstream turns on it.

Reads. Five billion a month is 1,930 a second, and a redirect is one primary key row read and nothing else. Lesson 007 measured that at 0.2 milliseconds on the session lookup, and lessons 009, 010 and 011 have been spending the figure ever since. Borrow it carefully, because 007 measured it on a table small enough to live entirely in memory and 540 gigabytes of rows is not that: the index leaf is resident, the heap page under it is not. Lesson 002 prices an SSD random read at a hundred microseconds, so a resident index entry plus one trip to the disk lands about where 007 landed. What breaks that figure later is the index going non-resident, not the row.

So 1,930 times 0.0002 is 0.386 seconds of database work every second.

Lesson 010 measured Marlow's entire Christmas peak at 1.04 seconds of database work a second, which lesson 011 called six and a half percent of a sixteen core machine.

Read those two numbers against each other. Five billion redirects a month is thirty seven percent of a four person bookshop's Christmas. Take the read peak at three times average, 5,800 a second, and you get 1.16 seconds a second, which is Marlow's Christmas plus a bit, seven percent of sixteen cores. Lesson 013's verdict on the shop's database transfers without editing: by any reading, asleep.

Which settles the line item the memorised answer always includes. There is no Redis here. Lesson 047's rule is that a level is worth its staleness only when the level below it is the bottleneck, and the level below here is a machine at seven percent. The hot set would fit in a cache, and it already fits in Postgres's own buffers, which is a cache nobody chose, nobody bills separately, and lesson 046 would recognise on sight, because the reader writes it.

Money. Lesson 056's three shapes, and all three behave oddly here. The rent is two application boxes, a database machine and a replica, all of them lesson 005's sixteen core box at $500 a month, plus lesson 006's twenty dollar balancer, so $2,020. That is already a quarter more than Marlow's entire monthly bill, for a system doing five billion of anything.

The meter is the CDN, and lesson 025 says the output of an envelope is which term dominates. At three hundred bytes a redirect, five billion of them is 1,500 gigabytes a month, which is $150 on lesson 016's ten cents a gigabyte. Trivial. The per-call fee is the line this course has never published a figure for, and at five billion calls a month it is the whole bill. So the envelope has done its job and told me the one number to go and get, and that number is not on the diagram.

The afternoon is the abuse mailbox. Somebody reads reports and decides. That line scales with nothing you control and it never gets approved, which is lesson 056's point about afternoons and lesson 060's about why the substitutes never get built.

The key space is the only thing here you can never take back

The memorised answer is a counter rendered in base 62, seven characters, and the arithmetic is right: 62 to the seventh is 3,521,614,606,208. Three and a half trillion slots against three billion links is a thousand times more room than the business needs, and everybody can do this part.

It also publishes your entire corpus.

Issue ids in order and every link anybody ever made sits at a key you can count to. Three billion keys at ten thousand requests a second, which is one machine and a cheap one, is 300,000 seconds. Three and a half days to hold a complete copy of every address your customers ever shortened. And people do not only shorten public pages. They shorten a document, a photo album, an invoice, a calendar invitation. A short link is a bearer credential whose entire security is that nobody guessed it, which drags lesson 029's problem onto a path that cannot have authentication on it, because the whole point is that a stranger holding the link can follow it.

So, random keys. Now the arithmetic almost nobody does.

Three billion links in three and a half trillion slots is one occupied key in 1,174. Guess blindly at ten thousand a second and you land 8.5 times a second, which is 736,000 real links a day, indefinitely.

Random keys did not solve the problem. They converted the whole corpus in three and a half days into three quarters of a million a day and no end.

It also gets worse by itself, because density is a ratio and you are the one raising it. Every link you mint makes the next guess likelier to land. The key space is the only resource here you cannot buy more of, and it is the only one that gets scarcer as you succeed. What makes it scarce is the business going well.

The dial is one character.

Spoken, since the audio skips tables: each extra character divides the harvest by sixty two. Seven characters give an attacker three quarters of a million links a day, eight give twelve thousand, nine give a hundred and ninety one.

A character costs one byte in the row and one in the index, so this design mints nine of them: two past the memorised seven, twelve gigabytes of the 630, two percent of the disk, and 736,000 harvested links a day becomes a hundred and ninety one. Two percent of your disk divides everything an attacker gets by nearly four thousand, and I have never once heard that traded out loud, because base 62 is the part of this question that got memorised and the density is the part that did not.

Random keys do need a uniqueness check, which is what people raise as the cost of giving up the counter. At one in 4.5 million it is a unique index and a retry loop whose second iteration will almost never run, and the check is free anyway, for a reason the next section explains: the insert has to visit that leaf page already.

Which raises the obvious objection: rate limit the guessing. Lesson 021 answers it and the answer is no. A limiter per address is a limiter per office, and its real threshold is a coincidence count rather than a rate. Ten thousand requests a second spread over ten thousand addresses is one each, comfortably under any threshold you would dare set on a public redirect that a QR code on a van depends on.

What lesson 021 does hand you is better than a valve. The refusal rate is the sensor. On a healthy shortener nearly every request hits, because the keys in circulation are the keys people were given. A miss rate above a percent or two is somebody walking the space, and it is the one signal the attacker cannot disguise, because generating misses is the whole method. Lesson 021 said a limiter is sized by the traffic it refuses. Here the traffic you refuse is the only intrusion detector you own, and nobody builds it, because 404s look like noise.

One more bill the key space quietly presents, and it changes what idempotency is for. Lesson 019 defines an idempotency key as a unique string the caller makes up to name an action it intends to perform, and its fifth check question asks you to argue about deduplicating by hashing the request instead. In a shortener that argument has a cost nobody mentions. A retry that mints a second key for the same target is harmless to the customer and the key is still gone. Lesson 020's phone app tries three times, and if every mint took all three your corpus triples: three billion keys become nine billion, density falls from one in 1,174 to one in 391, and the harvest climbs from 736,000 a day to 2.2 million. You will not pay all of that, because lesson 020's expected attempts are one plus p plus p squared and p is small. Take the ceiling anyway, because it is the generous version of the argument.

A factor of three, against a character's factor of sixty two. So keep the idempotency key, because lesson 019 is right about retries, and do not let anybody call it a security control. Spend the byte instead.

The worst order you can give a B-tree, on purpose

Lesson 043's finding is that what has to fit in memory is not the index, it is the set of pages you are writing into. Galewatch's sixty turbine farm is comfortable because sixty leaves stay open and take two hundred and sixty entries each. A shortener does the exact opposite, deliberately, because the section above just finished proving its keys have to be random.

Ninety gigabytes of index at eight kilobytes a page is eleven million leaf pages, and every insert picks one of them at random. Lesson 005's box has sixty four gigabytes of memory, so call fifty of it available for caching pages, which is generous. While the index fits inside that fifty, an insert touches a resident page and writes it back. Once it does not, every insert reads from disk before it can write.

Fifty gigabytes at thirty bytes an entry is 1.67 billion rows. At fifty million a month, that is month thirty three.

So the ceiling on this design is 1.67 billion links, it arrives in the third year, and it is set by the memory in one machine rather than by anything you drew. That is lesson 055's question answered: the first thing the tier multiplies that it does not own is the residency of an index whose size is a function of its own success. Lesson 001's hockey stick turns out to live inside the storage engine too, because an insert is cheap while its leaf is resident and costs a seek the moment it is not, with nothing gradual in the middle.

The measurement that sees it coming is not disk free space, which will report 630 gigabytes of 2,000 and nothing useful for years. It is the buffer cache hit rate on that one index, plotted monthly, with the row count beside it.

None of this costs anything yet. Lesson 043 prices a B-tree's write amplification at anywhere from one to two hundred and ninety times, depending on your keys and your memory and reported nowhere, against a steady thirty to fifty for an LSM whatever you do. Two hundred and ninety times a hundred small inserts a second is a few megabytes, which any SSD yawns at. The amplification is real and it is 290 times almost nothing.

What makes it the decision is that it never improves. A B-tree charges by key order, and this key order is adversarially random by design and will be random for as long as the product exists. Lesson 043's price for an LSM is a bloom filter on every point read and a merge on every range scan, and a shortener does nothing but point reads. No range scans to pay for. One update per revoked link and nothing else. And no key order to lose, because there was never any to begin with.

The storage engine here is picked by a decision taken for a security reason. I would take lesson 043's LSM for a shortener and would not take it at Galewatch, whose keys arrive in time order and whose leaves stay open. A design review will not see the connection, because the engine is a box on the diagram and the key length is a column type.

Moved Permanently is a promise

Four status codes, and the differences are not stylistic. A 301 Moved Permanently is cacheable by default with no expiry required, which means the expiry belongs to the client and always has. A 302 Found is not cacheable unless you explicitly say so. A 307 Temporary Redirect is a 302 that preserves the request method, and a 308 Permanent Redirect is a 301 that preserves it. Everything a shortener serves is a GET, so the method-preserving pair buys nothing here and the first distinction is the only one that matters.

Lesson 047 put the rule in general terms: a level you cannot invalidate is a level whose TTL is your real correctness bound. A CDN edge is a level you can invalidate by asking somebody. A browser cache is a level nobody on your side of the wire can invalidate, and a 301 is how your answer gets into it.

So lesson 023's dial, how far from the truth a reader may be and for how long, has no number for this row. Build lesson 030's copy table for a shortener and that is the whole finding.

Spoken: two of the three rows have a last column that cannot hold a number, and the third is not a copy at all. Lesson 030 said a row with no limit in that column is either a fact nobody writes or a bug nobody has had yet. Here it is a third thing, which is a fact you write all day and cannot unwrite.

A redirect's cacheability and a link's revocability are one dial pointed in opposite directions. Take the 301 and the edges and the browsers serve nearly all your traffic for nothing, and in exchange you have sold a promise you cannot break on the day you must. You will have to. The abuse mailbox is a certainty, and the first time somebody shortens a phishing page you need that link dead in minutes.

So what does refusing the 301 cost? That is the number everyone skips.

Take a 302 with a sixty second max-age. What the origin then sees is lesson 022's question exactly, and lesson 022 answered it: an edge cache's hit rate is your traffic's concentration divided by the number of edges, and neither of those terms is a setting in your building.

Suppose the busiest thousand links carry half the clicks, over lesson 022's nine edges, which is a bookshop's CDN footprint standing in for a shortener's. Both of those are my assumptions and the first things to go and measure. Those thousand, at nine edges and a sixty second expiry, cost nine thousand origin fetches a minute, which is a hundred and fifty a second. The other half, 965 a second, lands on links nobody asks for twice inside a minute, so nearly all of it misses.

Call it 1,115 origin requests a second against 1,930 clicks: a forty two percent hit rate. Worse than the sixty two percent lesson 022 measured on book covers, for the same structural reason, on a response a six hundredth of the size.

And 1,115 primary key reads a second at 0.2 milliseconds is 0.22 seconds of database work a second. A fifth of Marlow's Christmas.

The entire price of being able to revoke every link you ever issued is a fifth of a four person bookshop's Christmas database load. Nobody who worked that out would hesitate. The memorised answer takes the 301 anyway, to protect a bill it never computed.

And the verdict does not need my thousand links or my nine edges. Take the case where the cache does nothing whatever: all 1,930 clicks reach the origin, 0.386 seconds of work a second, thirty seven percent of a bookshop's Christmas. That is the ceiling on refusing the 301, and it is built from the brief alone.

Which gives the design its first entry in lesson 061's format, one per refusal, with the measurement that would reverse it.

We do not serve 301 for a short link.
Because a browser cache cannot be purged, so a 301 makes a
  link permanent in a way the abuse process cannot undo, and
  it deletes the click count the customer is paying for.
Costs about 1,115 origin requests a second at our volume,
  which is 0.22 seconds of database work on one machine.
Reverses if the cost of a miss at the origin rises above the
  cost of one unrevokable link, or if the abuse queue goes to
  zero, which it will not.

Deleting a link does not free the key

Revocation sets a flag. It does not give you the key back.

If a row has to go entirely, because a customer closes an account or a court asks, the key still cannot be reissued, so the delete leaves a tombstone: the key, and a byte saying what became of it. At one percent of three billion links over five years, that is thirty million tombstones at sixteen bytes, which is 480 megabytes. In bytes, the thing that makes the promise keepable is the cheapest line in the design.

What it answers with is a status code this course has not needed until now. A 410 Gone says the thing was here and is not coming back. A 404 says only that there is nothing there now, and declines to say whether there ever was. A crawler treats those differently and so does a person, and the difference is exactly the fact your tombstone holds, so answering 404 throws away in the response the thing you paid to keep in the table. Lesson 028's argument about contracts, arriving at a three digit number.

Lesson 059's sentence reads across inverted. You cannot make a record unchangeable, only make a change detectable; you cannot make a key reusable at all, so the tombstone is there to stop a future version of you from trying.

The two famous problems, both free

Sharding first. Lesson 014 says a shard key is a promise about what stays together, and a shortener has nothing that needs to stay with anything: every link is independent and every read carries the exact key. The key is also uniform by construction, because you made it random for a reason that had nothing to do with distribution, so lesson 031's ring takes it without an argument. The hardest decision in lessons 013 and 014 was taken for you by the security argument above.

You still do not shard yet, and the refusal has a measurement under it rather than a feeling: 630 gigabytes and 1.16 seconds of work a second is one machine and a replica, until the index stops being resident in month thirty three.

Hot keys next, where lesson 047's warning holds and its arithmetic does not bite. Sharding spreads keys and a hot key is one key, so a single link on a popular post is one slot taking the whole burst and no rebalancing divides it. Lesson 047 priced Stagefront's seat map at 3,333 requests a second for a one megabyte value, which is 26.7 gigabits offered to a ten gigabit card. A shortener's value is three hundred bytes. The same link at fifty thousand requests a second is fifteen megabytes a second, a hundred and twenty megabits, one and a fifth percent of that card if it all landed on one. It does not: nine edges split it to thirteen megabits each, and the 302's sixty seconds turn the whole burst into nine fetches a minute at the origin.

A hot key is priced in bytes, not in operations, which is lesson 047's own sentence, and it is why the failure that took a week to find inside a ticketing company's cache cannot touch this one. The two scaling hazards this design gets drawn with are the two it does not have. The two that will cost it money are a key space it spends without noticing and a promise it makes by default.

Marlow's bookmark was one row in that copy table with every copy in the wrong state at once: an edge holding an answer from the first week of October, a browser cache the shop cannot reach, and a click count that was a sample of nine. None of it was a bug. It was the default, chosen by somebody optimising a bill instead of keeping a promise, and the shop found out because one customer could be bothered to write in.

Recap

A key is issued once and means that one thing forever, so the key space is the only resource here you cannot buy more of and the only one that gets scarcer as you succeed. Every link you mint raises the density and nothing lowers it, because you cannot take a key back off a poster.

A counter is the clean design and it publishes your corpus. Sequential ids put every link anybody ever made at an address you can count to: three billion of them at ten thousand requests a second is three and a half days. Random keys buy a factor of 1,174, which is 736,000 harvested links a day rather than all of them by Thursday.

The sparsity of the key space is the security property, and one character is the only dial on it. Each character divides the harvest by sixty two for one byte a row, which is why this design mints nine and spends two percent of its disk there. Lesson 021's limiter will not help, because ten thousand requests from ten thousand addresses is one each. Lesson 021's refusals will: the miss rate is the one signal somebody walking the space cannot hide.

Random keys are the worst order a B-tree can be handed, and you have to hand it over anyway. So a shortener pays lesson 043's whole LSM price list except the range scan, and the range scan was the expensive line. The ceiling is the index going non-resident at 1.67 billion rows, month thirty three, and the instrument is a cache hit rate rather than a disk gauge.

A redirect's cacheability and a link's revocability are one dial pointed in opposite directions. A browser cache is a level nobody on your side can invalidate, so a 301's correctness bound is not a number, and two rows of this system's copy table have a last column that cannot hold one. Refusing the 301 costs about 1,115 origin requests a second, 0.22 seconds of database work, a fifth of a bookshop's Christmas. Deleting a link never frees the key either, so a delete leaves a tombstone answering 410 rather than 404, and thirty million of those is 480 megabytes.

Five billion redirects a month peaks at seven percent of one machine. The famous answer to this question is sized for a system nobody has, which is why it spends its forty five minutes on base 62 and none on the two decisions that cannot be reversed.

Check your understanding

1. Your shortener has been live for two years and somebody proposes shipping six character keys for a new "vanity" tier, on the argument that the space is still about ninety eight percent empty. Work out the harvest rate at six characters against your current corpus, then say what you would do, and what you would write down if you refused.

2. A customer asks for links that expire after thirty days so their campaign codes stop working. Describe what you would build, say what happens to each expired key, and say which of this lesson's two unwritten requirements your answer is closest to breaking.

3. You are at month twenty nine. The index residency graph is falling faster than the row count predicts. Give two explanations that are not "more links than forecast", say how you would tell them apart, and say which one would change the storage engine decision rather than just the machine.

4. Somebody on your team wants to serve 301 for links created by paying customers only, since those customers have agreed to terms that let you refuse abuse claims. Give the strongest version of their argument, then the case it fails, then say whether a shorter max-age on a 302 is a real compromise or a way of agreeing with them quietly.

5. Marlow's founder wants his nine scans explained and then wants a real count. Say what you would change at the shortener to give him one, what it costs in the units of this lesson, and what he could do at the bookshop today instead that costs you nothing.

6. Lesson 061 called a shortener the smallest system in this course that still has to answer every question, and said a review's product is one entry per refusal with the measurement that would reverse it. Write this design's entry for its key length, then say honestly whether the measurement you put under it is a measurement or a belief, and what you would do about that.

Next lesson

063 Design a Distributed Rate Limiter. Today leaned on lesson 021's refusal path twice, once as the defence that does not work and once as the sensor nobody builds, and never said how you would count across more than one machine.