p99 0 ms* Autocomplete für 240 Millionen Domainnamen
P99 0 ms* autocomplete for 240M domain names
Der Entwickler von Wirewiki.com zeigt, wie er eine Autovervollständigung für 240 Millionen Domainnamen mit einer p99-Latenz von 0 ms erreicht. Durch Prefetching bei Tastendruck und eine Kombination aus In-Memory-Trie und SSD-gestütztem Blockindex werden Vorschläge praktisch sofort angezeigt. Der Artikel erklärt die Architektur, die Latenzbudgets und die Ergebnisse von Belastungstests, die zeigen, dass die API selbst bei hoher Last schnell bleibt. Die Herausforderung liegt in der geografischen Verteilung, da ein einzelner Server in Europa für Nutzer in den USA nicht schnell genug ist.
Das gibt uns ein Zeitbudget von `keyPress1Duration + gap between key presses + keyPress2Duration`.
- skybrian
Diese Autovervollständigung schlägt Domains vor, die es nicht gibt. Du kannst einfach Müll eingeben und es wird etwas vorschlagen, aber wenn du dann dorthin gehst, gibt es keine Einträge. Es scheint, dass ein Zweck einer Autovervollständigungsbox darin besteht, Tippfehler zu vermeiden, was das weniger nützlich macht.
- chrismorgan
Die Verwendung von keyup ergibt keinen Sinn und ist inkonsistent mit den Erwartungen der Benutzer. Für das Auslösen von Aktionen (was normales Tippen einschließt) verwendet man ausschließlich keydown. (Nun, es gibt eine Ausnahme aus Gründen, die mir unklar sind: das Aktivieren eines Buttons durch Drücken der Leertaste. Das löst bei keyup aus, so wie Klicks beim Loslassen ausgelöst werden, während Enter bei keydown auslöst.) Keyup ist auf Dinge beschränkt, bei denen man ständig auf den Zustand einer Taste reagiert, wie es in Spielen üblich ist. Das betrifft auch die Funktionalität. Tatsächlich führt die Verwendung von keyup anstelle von keydown zu Latenz. Fühlt sich schlecht an.
- ViscountPenguin
Leider fühlt sich dieser Ansatz hier in Australien nicht so gut an, definitiv eine Funktion der Latenz. Ich denke, man könnte viel näher herankommen, wenn man dies als Optimierungsproblem betrachtet, bei dem man das vollständige Alphabet-Wörterbuch verwendet, aber eine Restvorhersage hinzufügt, die darauf abzielt, so viel wie möglich vom verbleibenden Domainnamen-Baum abzudecken, gewichtet nach Popularität. Dieser Baum könnte dann vorgebacken und mit demselben System gespeichert werden. Das würde wahrscheinlich p99 0ms auch in Australien erreichen.
- oersted
Warum nicht einfach den Fetch bei keyDown auslösen und anzeigen, sobald die Antwort eintrifft, wie üblich? Die Zeit, die zum Drücken einer Taste benötigt wird, ist ein vernünftiges Ziel für die API-Latenz, nehme ich an, aber es ist immer noch ein willkürliches Ziel. Bis zum keyUp zu warten, fügt nur mehr Latenz hinzu, wenn deine API schneller ist. Dass es mit keyUp synchronisiert ist, fühlt sich für mich nicht unmittelbarer an.
- kevmo314
Wenn du die Netzwerklatenz weiter reduzieren möchtest, kannst du jeden Trie-Knoten als Datei speichern und sie praktischerweise nach dem Präfixpfad zu diesem Knoten benennen. Dann lädst du die paar hundert Millionen Dateien auf R2 hoch. Jetzt kann die Traversierung komplett über CDN-Lookups erfolgen!