Einen URL-Kürzer entwerfen: Der Kurzcode ist der einfache Teil

Bitte jemanden, einen URL-Kürzer zu entwerfen, und die erste Antwort kommt in Sekunden: code → url speichern, den Code nachschlagen, weiterleiten. Diese Antwort ist richtig – und zugleich der kleinste Teil des Designs. Ein URL-Kürzer ist gerade deshalb eine gute Übung, weil sein Kern trivial ist: Jede Entscheidung, die zählt, betrifft das, was um ihn herum passiert – welcher Pfad schnell sein muss, welche Arbeit warten kann und welcher Ausfall bis zu der Person durchschlagen darf, die geklickt hat.

Dieser Beitrag baut eine Architektur in vier Schritten auf. Jeder Schritt beginnt mit einem Problem, das der vorherige nicht lösen kann, ergänzt nur das, was dieses Problem erfordert, und sagt, was es kostet. Wenn du dich in dem Gebiet schon auskennst, spring direkt zur finalen Architektur. Wenn du hier bist, um zu lernen, lies der Reihe nach: Das finale Diagramm ist erst dann offensichtlich, wenn du gesehen hast, warum jeder Kasten dazugekommen ist.

Die Annahmen

Zahlen entscheiden über die Architektur, deshalb hier die, von denen dieses Design ausgeht. Es sind Annahmen für die Übung, bewusst gerundet – keine Messwerte eines echten Dienstes:

• 50 Millionen neue Links pro Monat, im Schnitt etwa 20 Erstellungen pro Sekunde.
• 100 Weiterleitungen pro erstelltem Link: im Schnitt rund 2.000 Weiterleitungen pro Sekunde, mit Spitzen, die zehnmal höher liegen, wenn sich ein Link verbreitet.
• Etwa 500 Byte pro Link (die lange URL, der Code, ein Eigentümer, Zeitstempel): rund 25 GB neue Daten pro Monat, 300 GB pro Jahr.
• Ein Klick-Event pro Weiterleitung, aufbewahrt für Analytics.

Zwei Dinge fallen schon auf. Schreibvorgänge sind winzig: 20 pro Sekunde sind für jede Datenbank ein Klacks. Und die Weiterleitung ist das Produkt: Sie ist der Request, auf den echte Menschen warten, tausendfach pro Sekunde, und sie steht zwischen ihnen und der Seite, die sie eigentlich wollten. Das Erstellen eines Links darf ein paar hundert Millisekunden dauern, ohne dass es jemand merkt; eine ebenso langsame Weiterleitung lässt jeden Link kaputt wirken.

Das ausgearbeitete Design in Learn geht von einem kleineren Dienst mit anderen Zahlen aus. Die Form der Antwort ist dieselbe, und genau darum geht es: Die Schätzung ändert die Größen, nicht die Argumentation.

Schritt 1: Es zum Laufen bringen

Fang mit dem Kleinsten an, das korrekt ist. Ein Client spricht mit einem zustandslosen Dienst, und der Dienst speichert Links in einer relationalen Datenbank. Es gibt zwei Operationen: POST /links speichert eine lange URL und gibt einen Code zurück, und GET /{code} schlägt den Code nach und antwortet mit einer Weiterleitung.

Schon diese erste Version betreibt mindestens zwei Instanzen des Dienstes hinter einem Load Balancer. Das hat nichts mit Skalierung zu tun – eine Instanz könnte diesen Traffic bedienen –, es ist das Minimum für Verfügbarkeit: Mit einer einzigen Instanz ist jedes Deployment und jeder Absturz ein Ausfall. Der Dienst hält keinen eigenen Zustand, also kann jede Instanz jeden Request beantworten, und weitere Instanzen hinzuzufügen ist später eine Konfigurationsänderung statt eines Redesigns.

Mehr erfahrenDurcherarbeiteter Entwurf: ein Link-VerkürzerLastverteilung und horizontale SkalierungErzeugung eindeutiger IDs

Der Kurzcode selbst

Das Datenmodell ist eine einzige Tabelle – Code, lange URL, Eigentümer, Erstellungszeitpunkt – mit dem Code als Primärschlüssel. Die einzige echte Entscheidung ist, wie Codes erzeugt werden, und dafür gibt es zwei vernünftige Antworten.

Zufällige Codes. Zieh sieben Zeichen aus einem Alphabet mit 62 Zeichen (base62: 26 Kleinbuchstaben, 26 Großbuchstaben und 10 Ziffern), füge die Zeile ein und versuch es erneut, wenn der Unique-Constraint sie ablehnt. Sieben Zeichen ergeben etwa 3,5 Billionen Kombinationen, sodass selbst nach einem Jahr mit diesem Traffic eine Kollision selten ist und der erneute Versuch kaum je läuft. Zufällige Codes sind außerdem praktisch nicht zu erraten, und das ist wichtiger, als es scheint: Bei fortlaufenden Codes kann jeder, der einen Link hat, die benachbarten Codes ausprobieren – und Leute kürzen oft Links, die sie nie veröffentlichen wollten.

Zählerbasierte Codes. Nimm die nächste Zahl aus einer Sequenz, die die Datenbank ohnehin bereitstellt, und kodiere sie in base62 – keine Kollisionen, keine Wiederholungsversuche. Der Preis ist Vorhersagbarkeit, denn aufeinanderfolgende Zahlen ergeben aufeinanderfolgende Codes. Die übliche Abhilfe ist, die Zahl vor dem Kodieren durch eine umkehrbare Verwürfelung zu schicken, eine Permutation mit Schlüssel: Die Codes bleiben eindeutig, sind aber nicht mehr geordnet.

Dieses Design nutzt den verwürfelten Zähler: Eindeutigkeit per Konstruktion, Codes, die niemand durchzählen kann, und keine neue Komponente, weil die Zahl aus der Datenbank kommt, die wir schon haben, in derselben Transaktion wie das Insert. Zufällige Codes wären genauso vertretbar. Entscheidend ist, dass die Wahl klein, abgegrenzt und später leicht zu ändern ist.

Schritt 2: Die Weiterleitung wird zum Hot Path

Bei 2.000 Weiterleitungen pro Sekunde reicht der erste Schritt völlig. In der Spitze – 20.000 pro Sekunde, während ein Link überall kursiert – ist jede Weiterleitung immer noch eine Datenbankabfrage, und die Datenbank muss für die schlimmste Minute des Monats dimensioniert sein. Das ist ein teurer Weg, einen Lesezugriff zu bedienen, der sich fast nie ändert.

Das Ziel eines Links wird einmal geschrieben und tausendfach gelesen – der Lehrbuchfall für einen Cache. Der Dienst nutzt Cache-Aside: Bei einer Weiterleitung schlägt er den Code zuerst im Cache nach. Bei einem Treffer antwortet er sofort; bei einem Fehltreffer liest er aus der Datenbank, legt das Ergebnis mit einer Time-to-live (TTL) im Cache ab und antwortet.

Der Dienst fragt zuerst den Cache; die Datenbank beantwortet nur die Fehltreffer.

Mehr erfahrenCaching-SchichtenHeiße Keys und Cache-Stampedes

Drei Details entscheiden, ob dieser Cache hilft oder schadet:

• Die Datenbank bleibt die Source of Truth. Das Erstellen eines Links schreibt in die Datenbank und kehrt erst nach dem Commit zurück; der Cache wird beim ersten Lesen befüllt. Wäre der Cache weg, gäbe es trotzdem noch jeden Link – die Weiterleitungen wären nur langsamer.
• Die TTL ist eine Aussage über Veränderung. Links ändern sich selten, also ist eine lange TTL – Stunden oder Tage – unbedenklich. Wird ein Link gelöscht oder sein Ziel bearbeitet, löscht der Dienst auch den Cache-Eintrag, und die TTL begrenzt, wie lange eine verpasste Löschung überleben kann.
• Auch unbekannte Codes bekommen eine Antwort aus dem Cache. Scanner fragen ständig zufällige Codes ab. „Nicht gefunden“ eine Minute lang zu cachen, hält sie von der Datenbank fern. Nur ein echtes „nicht gefunden“ wird so gecacht – niemals ein Datenbankfehler –, und das Erstellen eines Links löscht jeden „nicht gefunden“-Eintrag für seinen Code.

Der Cache verändert auch, wie das System ausfällt. Fällt er aus, laufen die Weiterleitungen bis zur Datenbank durch – weiterhin korrekt, aber langsamer –, und die Datenbank bekommt plötzlich die volle Last ab, die bisher der Cache abgefangen hat. Entweder ist die Datenbank so dimensioniert, dass sie das übersteht, oder der Dienst wirft Last ab (beantwortet einige Requests sofort mit einem Fehler, statt sie einzureihen), bis der Cache wieder da ist. Popularität bringt ein zweites Risiko: Ein viraler Link ist ein einzelner Hot Key, und wenn sein Eintrag im ungünstigsten Moment abläuft, verfehlt eine ganze Menge Requests gleichzeitig den Cache, und jeder einzelne davon geht für dieselbe Zeile an die Datenbank. Diesem Ausfall ist ein eigener Beitrag in diesem Blog gewidmet, verlinkt am Ende.

Schritt 3: Klicks zählen, ohne die Weiterleitungen zu bremsen

Jetzt will das Produkt Analytics: wie oft jeder Link geklickt wurde, von wo und wann. Die naheliegende Implementierung schreibt bei jeder Weiterleitung eine Zeile. Sie ist auch die falsche, denn sie legt einen Schreibvorgang – langsamer als der gecachte Lesezugriff direkt daneben – auf den Latenzpfad jedes einzelnen Klicks.

Die Lektion dieses Schritts passt in einen Satz: Den Leser weiterzuleiten und den Klick zu erfassen braucht nicht denselben Latenzvertrag. Der Leser braucht eine Weiterleitung in Millisekunden. Analytics braucht den Klick irgendwann, korrekt gezählt. Also veröffentlicht der Dienst ein kleines Klick-Event in eine Queue und beantwortet die Weiterleitung, ohne auf irgendetwas anderes zu warten. Ein Worker konsumiert die Queue und schreibt die Events in Batches in einen Speicher, der für Analytics gebaut ist.

Mehr erfahrenNachrichtenwarteschlangen und asynchrone WorkerIdempotenz und Exactly-once-Illusionen

Die Annahmen erklären, warum Klicks einen eigenen Speicher bekommen. Links wachsen um 25 GB pro Monat. Klicks kommen mit 2.000 pro Sekunde an – etwa 170 Millionen Events pro Tag –, und bei rund 100 Byte pro Event sind das etwa 500 GB pro Monat, zwanzigmal so viel wie die Links. Der größte Datenbestand eines URL-Kürzers sind nicht die Links, und die Datenbank, die Weiterleitungen beantwortet, sollte nicht auch diejenige sein, die Klicks pro Land für die letzte Woche zählt.

Die asynchrone Grenze hat ihre Kosten, und es lohnt sich, sie klar zu benennen:

• Die Zustellung erfolgt mindestens einmal. Ein Worker, der nach dem Schreiben eines Batches, aber vor dessen Bestätigung abstürzt, bekommt diesen Batch noch einmal. Jedes Event trägt eine ID, und die Analytics-Seite ignoriert IDs, die sie schon gesehen hat; der Consumer ist also idempotent, und ein erneuter Versuch kann keine Zählung verdoppeln.
• Zählungen hinken hinterher. Ein Klick erscheint Sekunden nach der Weiterleitung in den Analytics, oder später, wenn der Worker in Rückstand gerät. Für Analytics ist das in Ordnung, und es ist eine Entscheidung, kein Zufall.
• Die Queue kann ausfallen. Schlägt das Veröffentlichen fehl, gelingt die Weiterleitung trotzdem: Der Dienst kann ein paar Sekunden an Events lokal vorhalten und den Rest verwerfen. Während eines Ausfalls eine Handvoll Klicks zu verlieren, ist der Preis, den dieses Design zahlt, damit ein Analytics-Problem nie zu einem Weiterleitungsproblem wird.

Schritt 4: Wenn die Datenbank der Single Point of Failure ist

Schau dir an, was noch allein dasteht. Der Dienst läuft in mehreren Instanzen. Der Cache kann verschwinden, ohne dass Daten verloren gehen. Die Queue fängt einen langsamen oder kaputten Worker ab. Die Datenbank ist eine einzige Maschine mit der einzigen Kopie jedes Links: Fällt sie aus, stoppt das Erstellen, jeder Cache-Fehltreffer schlägt fehl, und eine verlorene Festplatte nimmt alles mit, was seit dem letzten Backup geschrieben wurde.

Die Lösung ist ein Standby-Replikat, das kurz nach jedem Commit eine Kopie jedes Schreibvorgangs erhält und zur neuen Primärdatenbank hochgestuft werden kann. Achte darauf, wofür es da ist: Verfügbarkeit und Dauerhaftigkeit, nicht Lesekapazität. Der Cache hat der Datenbank die Leselast bereits abgenommen, ein „für Lesezugriffe“ hinzugefügtes Replikat würde also meist untätig herumstehen. Ein Replikat und ein Cache beantworten unterschiedliche Fragen, und ein anderer Beitrag in diesem Blog erklärt diesen Unterschied.

Mehr erfahrenReplikation und Read-ReplicasSharding und Partitionierung

Die Replikation ist hier asynchron, was ein eigener Kompromiss ist: Die Primärdatenbank bestätigt einen Schreibvorgang, ohne auf das Replikat zu warten. Fällt sie aus, erreichen die Schreibvorgänge der letzten Momente das Replikat womöglich nie, sodass ein Link, der eine Sekunde vor dem Ausfall erstellt wurde, verloren gehen könnte. Synchrone Replikation schließt diese Lücke, um den Preis langsamerer Schreibvorgänge und eines Erstellungspfads, der von zwei Maschinen abhängt. Bei 20 Erstellungen pro Sekunde ist beides bezahlbar; die Wahl hängt davon ab, ob „dein neuer Link ist verschwunden“ alle Jubeljahre einmal akzeptabel ist.

Was dieser Schritt bewusst nicht hinzufügt, ist Sharding. Die Links auf mehrere Datenbanken zu verteilen, löst ein anderes Problem – mehr Daten oder mehr Schreibvorgänge, als eine Primärdatenbank bewältigen kann –, und bei 300 GB pro Jahr und 20 Schreibvorgängen pro Sekunde liegt dieses Problem Jahre in der Zukunft. Wenn es kommt, ist der Partitionsschlüssel schon klar: Jeder Lookup erfolgt über den Code, also sorgt eine Partitionierung nach einem Hash des Codes dafür, dass jede Weiterleitung genau eine Partition berührt. Würde man stattdessen nach Bereichen der rohen Sequenznummer partitionieren, landete jeder neue Link in derselben, neuesten Partition; erst das Hashen des Schlüssels verteilt die Schreibvorgänge.

Die finale Architektur, gelesen über ihre Ausfälle

Vier Schritte und neun Kästen, jeder aus einem Grund da, den die Schritte geliefert haben. Am nützlichsten liest man das finale Diagramm über die Ausfälle – was kaputtgeht und wer es merkt:

• Eine Instanz des Dienstes stirbt → der Load Balancer schickt ihr keinen Traffic mehr. Niemand merkt etwas.
• Der Load Balancer fällt aus → alles fällt aus. Er ist als ein einzelner Kasten gezeichnet, weil er meist ein verwalteter, redundanter Dienst ist und keine Maschine, die du selbst betreibst; ist er doch eine Maschine, die du selbst betreibst, muss er doppelt vorhanden sein.
• Der Cache ist down → Weiterleitungen werden aus der Datenbank bedient, langsamer, solange die Datenbank die Last tragen kann. Nichts wird falsch.
• Die Queue oder der Worker ist down → Weiterleitungen sind nicht betroffen; Klicks werden gepuffert, verzögert oder bei einem langen Ausfall teilweise verloren.
• Der Analytics-Speicher ist langsam → der Worker gerät in Rückstand, und die Zählungen hinken hinterher. Den Weiterleitungen ist das egal.
• Die Primärdatenbank fällt aus → das Erstellen von Links stoppt, bis das Standby-Replikat hochgestuft ist. Beliebte Links werden weiterhin aus dem Cache weitergeleitet; der Rest schlägt fehl, bis die Hochstufung abgeschlossen ist.

Diese Liste ist das eigentliche Design. Die Kästen sind die Mittel; die Entscheidungen betreffen, welchen Pfad jeder Ausfall erreichen darf. Die Weiterleitung hängt von so wenig wie möglich ab – dem Load Balancer, dem Dienst, dem Cache und der Datenbank nur bei Fehltreffern –, und alles andere hängt asynchron an ihr.

Was dieses Design offenlässt

Manche Entscheidungen gehören zum Produkt, nicht zur Architektur, und ein Design-Review sollte sie benennen, statt so zu tun, als wären sie gelöst:

• Missbrauch. Ein URL-Kürzer verschleiert, wohin ein Link führt, und ist deshalb attraktiv für Phishing und Malware. Echte Dienste prüfen Ziele beim Erstellen eines Links und begrenzen per Rate Limit, wer Links erstellen darf.
• Eigene Aliase. Wenn Leute ihren eigenen Code wählen dürfen, wird er zu einem vom Nutzer gelieferten eindeutigen Schlüssel – samt reservierter Wörter und Squatting, um die man sich kümmern muss.
• Ablauf und Löschung. Links, die ablaufen, brauchen einen Aufräumjob und einen Cache, der sie rechtzeitig vergisst.
• Regionen. Leser auf mehreren Kontinenten hätten den Cache und vielleicht sogar die Weiterleitung selbst gern näher bei sich. Der Traffic in dieser Übung braucht das noch nicht.

Der Kurzcode hat zwei Absätze gebraucht. Alles andere – der Hot Path, die asynchrone Grenze, die Source of Truth, der Ausfall, den jeder Kasten verursachen darf – ist das eigentliche Design, und es ist der Teil, der sich auf jedes andere System übertragen lässt, das du zeichnen wirst.