Typeahead-Systemdesign: So funktioniert Such-Autovervollständigung im großen Maßstab

Tipp „how to“ in ein Suchfeld, und Vorschläge erscheinen, bevor du das nächste Wort beendet hast. Diese Funktion beantwortet bei fast jedem Tastendruck eine Anfrage, für jeden Nutzer, und sie muss sich sofort anfühlen: Forschung zu Antwortzeiten, die Jahrzehnte zurückreicht, setzt die Grenze für „das System reagiert unmittelbar“ bei etwa 0,1 Sekunden an. Nichts an der Autovervollständigung ist für sich genommen schwer. Die Herausforderung besteht darin, einfache Dinge in einem engen Latenzbudget bei sehr hoher Anfragerate zu erledigen und die Vorschläge dabei frisch und frei von allem zu halten, was du nie zeigen willst.

Dieser Beitrag entwirft einen Typeahead-Service: Anforderungen und Kapazität, den Top-k-Präfixindex, Serving und Sharding, die Offline-Build-Pipeline, Trend-Suchanfragen, Caching, Personalisierung und Filterung, mit einem Diagramm beider Hälften.

Anforderungen

Funktional:

• Für ein Präfix die besten 5 bis 10 Vervollständigungen liefern, überwiegend nach Beliebtheit sortiert.
• Neue Trends innerhalb von Minuten abbilden, nicht erst nach Tagen.
• Nie Vorschläge zeigen, die gegen deine Richtlinien verstoßen.

Nicht funktional:

• Etwa 100 ms Ende zu Ende, was dem Backend nach der Netzwerkzeit ein Budget von einigen zehn Millisekunden lässt.
• Hohe Verfügbarkeit: Wenn Vorschläge ausfallen, funktioniert die Suche trotzdem, also elegant degradieren.
• Günstig: Das läuft bei jedem Tastendruck.

Kapazität

Nimm 50 Millionen tägliche Nutzer an, die jeweils 10-mal am Tag suchen, mit etwa 6 Vorschlagsanfragen pro Suche, nachdem der Client nicht mehr für jedes Zeichen eine schickt:

Zwei Beobachtungen prägen das Design. Kurze Präfixe wiederholen sich extrem: Jeder, der „w“ tippt, stellt dieselbe Frage. Und die Antwort auf ein Präfix ändert sich langsam, also lässt sie sich vorab berechnen.

Der Client erledigt die Hälfte der Arbeit

• Debounce. Warte nach dem letzten Tastendruck 100 bis 200 ms, bevor du eine Anfrage schickst, damit schnelle Tipper nicht eine Anfrage pro Zeichen auslösen.
• Veraltete Anfragen abbrechen. Wenn ein neues Präfix rausgeht, brich das vorherige ab und ignoriere verspätete Antworten für ein älteres Präfix.
• Lokal cachen. Hat „how t“ zehn Ergebnisse geliefert, die alle mit „how to“ beginnen, kann der Client sie ohne Anfrage für „how to“ filtern.
• Still zurückfallen. Schlägt der Suggest-Aufruf fehl oder ist er langsam, zeig nichts an; die Suche muss trotzdem funktionieren.

Der Top-k-Präfixindex

Die klassische Struktur ist ein Trie, in dem jeder Knoten ein Präfix ist und seine Kinder es um ein Zeichen verlängern. Zur Anfragezeit den Trie abzulaufen und den ganzen Teilbaum nach den beliebtesten Anfragen zu durchsuchen, ist für beliebte Präfixe zu langsam. Berechne die Antwort stattdessen vorab: Speichere an jedem Präfixknoten die Top-k-Vervollständigungen, bereits sortiert. Ein Lookup wird zu einem einzigen Lesevorgang.

Viele Implementierungen verzichten ganz auf den zeigerbasierten Trie und speichern eine flache Abbildung vom Präfix auf seine Top-k-Liste, begrenzt auf eine maximale Präfixlänge, weil sehr lange Präfixe selten sind und auf einen langsameren Pfad ausweichen können. Eine solche aus aggregierten Zählungen zu bauen, ist kurz:

import heapq
from collections import defaultdict

def build_prefix_index(query_counts, k=10, max_prefix=12):
    index = defaultdict(list)  # prefix -> min-heap of (count, query)
    for query, count in query_counts.items():
        for n in range(1, min(len(query), max_prefix) + 1):
            heap = index[query[:n]]
            if len(heap) < k:
                heapq.heappush(heap, (count, query))
            elif count > heap[0][0]:
                heapq.heapreplace(heap, (count, query))
    return {p: [q for _, q in sorted(h, reverse=True)] for p, h in index.items()}

Das Ergebnis ist schreibgeschützt und wird auf jedem Serving-Knoten in den Speicher geladen. Wenn du ohnehin Elasticsearch betreibst, bietet dessen Completion Suggester dieselbe Idee als Feature: Die Dokumentation beschreibt Datenstrukturen, die schnelle Lookups ermöglichen, aber teuer zu bauen sind und im Speicher liegen, und genau diesen Kompromiss geht dieses Design ein.

Serving und Sharding

Der Suggest-Service normalisiert das Präfix (Kleinschreibung, Trimmen, Unicode-Normalisierung), liest die Top-k-Liste aus dem Index, mischt Trend- und persönliche Ergebnisse hinzu, filtert und antwortet. Alles, was er liest, liegt im Speicher.

Wird der Index zu groß für eine Maschine, sharde ihn. Nach dem Anfangsbuchstaben zu sharden, wirkt natürlich, ist aber stark ungleich: Weit mehr Anfragen beginnen mit „s“ als mit „x“. Hashe stattdessen das Präfix oder teile nach Bereichen des gemessenen Traffics, und repliziere jeden Shard, damit ein Knotenausfall nur Kapazität kostet. Da der Index offline neu gebaut wird, müssen sich Repliken nie über Schreibvorgänge einigen; jede lädt denselben Snapshot.

Die Offline-Build-Pipeline

1. Sammeln. Such-Frontends loggen jede abgeschlossene Anfrage in einen Stream wie Kafka.
2. Aggregieren. Ein Batch-Job zählt Anfragen über ein Fenster, etwa die letzten 30 Tage, gewichtet jüngere Tage stärker und verwirft seltene Anfragen unter einer Schwelle, um die Privatsphäre zu schützen und Rauschen zu entfernen.
3. Filtern. Wende Sperrlisten und Richtlinien-Klassifikatoren an, bevor irgendetwas zum Vorschlag wird.
4. Bauen. Berechne den Präfixindex wie oben und schreib ihn als versionierten Snapshot in den Objektspeicher.
5. Ausrollen. Serving-Knoten laden den neuen Snapshot parallel zum alten, schalten atomar um und behalten die vorige Version für einen schnellen Rollback.

Stündliche oder tägliche Neubauten halten den Hauptindex für die meisten Anfragen frisch genug.

Trend-Suchanfragen

Eine Eilmeldung erzeugt innerhalb von Minuten eine neue beliebte Anfrage, lange vor dem nächsten Batch-Build. Ergänze eine kleine Echtzeitschicht: Ein Stream-Prozessor zählt Anfragen in gleitenden Fenstern, erkennt solche, die viel schneller steigen als ihre Grundlinie, und schreibt sie, nach Präfix geschlüsselt, in einen schnellen Speicher wie Redis. Der Suggest-Service mischt sie mit den Batch-Ergebnissen. Halte diese Schicht klein und filtere sie aggressiv; hier würde ein koordinierter Angriff versuchen, Vorschläge zu platzieren.

Caching auf jeder Schicht

Kurze Präfixe sind die heißesten und am besten cachebaren, weil sie für alle gleich sind. Personalisierte Ergebnisse lassen sich nicht im CDN cachen, ein Grund, die Personalisierung leicht zu halten.

Personalisierung, Tippfehler und Filterung

• Persönlicher Verlauf. Die eigenen jüngsten Anfragen eines Nutzers mit globalen Vorschlägen zu mischen, hilft sehr und ist günstig, wenn die jüngsten Anfragen auf dem Gerät oder in einem kleinen Speicher pro Nutzer liegen.
• Tippfehler. Fuzzy Matching innerhalb einer Änderung vom Präfix rettet „pyhton“. Das ist teurer, also probieren viele Systeme zuerst exakte Präfixe und fallen nur dann auf Fuzzy Matching zurück, wenn die Ergebnisse dünn sind.
• Filterung greift zweimal: offline, bevor eine Anfrage in den Index kommt, und online gegen eine schnelle Sperrliste, die sich ohne Neubau innerhalb von Minuten aktualisieren lässt.

Das Typeahead-Diagramm

So liest du es:

• Der Online-Rahmen ist der Pfad pro Tastendruck: Browser, CDN-Cache, API-Gateway und Suggest-Service.
• Der Suggest-Service liest zwei In-Memory-Präfix-Shards und den Redis-Trend-Speicher, führt die Ergebnisse zusammen und filtert sie.
• Der Offline-Rahmen ist der Build-Pfad: Query-Logs aus Kafka, der Aggregationsjob und versionierte Index-Snapshots im Objektspeicher.
• Die gestrichelte Kante vom Objektspeicher zu den Shards ist das Laden des Snapshots, die einzige Verbindung zwischen den beiden Hälften.
• Der Markdown-Block zeigt Latenzbudget und Kapazitätszahlen.

Leselastige Systeme klar zeichnen

• Trenne online und offline. Die beiden Hälften haben unterschiedliche Latenzbudgets, Fehlerbilder und Verantwortliche, und das Diagramm sollte das auf einen Blick zeigen.
• Zeig jede Cache-Schicht mit ihrer Ablaufzeit. In einem leselastigen System sind Caches der größte Teil der Architektur.
• Zeichne die einzige Verbindung zwischen den Hälften: hier ein versionierter Snapshot. Sie erklärt, wie Updates die Nutzer erreichen und wie Rollback funktioniert.
• Schreib das Latenzbudget an den Online-Pfad.

Den allgemeinen Ansatz zeigt das System-Design-Diagramm-Beispiel. Das Diagramm der Caching-Strategien behandelt Cache-Schichten ausführlicher, und die Log-Aggregation folgt den Mustern im Architekturdiagramm für Datenpipelines.

In Archboard nachbauen

1. Melde dich mit Google oder GitHub an und leg ein Diagramm an.
2. Füge zwei Rahmen-Nodes aus dem Basis-Pack hinzu: Online, per keystroke, und Offline, hourly build.
3. Füge im Online-Rahmen einen Gerät-Node aus dem Netzwerk-Pack für den Browser hinzu, ein CDN und ein API-Gateway aus dem Cloud-Pack, einen Recheninstanz-Node für den Suggest-Service, zwei Redis-Nodes aus dem Daten-Pack für die Präfix-Shards und einen weiteren Redis-Node für Trend-Suchanfragen.
4. Füge im Offline-Rahmen einen Kafka-Node aus dem Daten-Pack für Query-Logs hinzu, einen Recheninstanz-Node aus dem Cloud-Pack für den Aggregationsjob und eine Objektablage aus dem Daten-Pack für Index-Snapshots.
5. Zeichne den Anfragepfad von links nach rechts, den Build-Pfad darunter und eine gestrichelte Kante von den Snapshots zu den Shards.
6. Füge einen Markdown-Block aus dem Basis-Pack mit Latenzbudget und Kapazität hinzu.

Das Beispiel nutzt 13 Diagramm-Nodes und bleibt damit im Free-Plan.

FAQ

Welche Datenstruktur nutzt man für Autovervollständigung? Einen Trie oder eine flache Abbildung vom Präfix auf Ergebnisse, mit den an jedem Präfix vorberechneten Top-k-Vervollständigungen. Die Vorberechnung macht jeden Lookup zu einem einzigen Lesevorgang im Speicher.

Wie schnell muss Autovervollständigung sein? Rund 100 ms vom Tastendruck bis zu den Vorschlägen fühlen sich sofort an. Nach der Netzwerkzeit bleiben dem Backend einige zehn Millisekunden, deshalb liegt der Index im Speicher.

Wie bleiben Vorschläge aktuell? Eine Batch-Pipeline baut den Index stündlich oder täglich aus Query-Logs neu, und eine Echtzeitschicht ergänzt schnell steigende Anfragen innerhalb von Minuten.

Sollten Autovervollständigungsanfragen bei jedem Tastendruck rausgehen? Nein. Debounce im Client für 100 bis 200 ms, brich veraltete Anfragen ab und nutze gecachte Ergebnisse für längere Präfixe wieder. Das senkt das Anfragevolumen deutlich.

Wie hält man anstößige Vorschläge fern? Filtere offline, bevor Anfragen in den Index kommen, setze Mindestschwellen für die Beliebtheit an und prüfe Ergebnisse online gegen eine Sperrliste, die du schnell aktualisieren kannst.

Kostenlos starten — ein Seat, keine Kreditkarte.