p99 0ms*のオートコンプリートを2億4000万ドメインで実現した方法
P99 0 ms* autocomplete for 240M domain names
Wirewiki.comの作者が、2億4000万のドメイン名に対してp99レイテンシ0ms*のオートコンプリートを実現した方法を解説。キー押下中のプリフェッチとキャッシュ、インメモリのトライ木（Trancoリスト）とSSD上のメモリマップドブロックインデックス（CZDSデータ）を組み合わせたAPI設計、負荷テストの結果、そして地理的制約と今後の展望について述べる。
p99 0msとは、99%のケースで、ユーザーがキーを離す前に結果が準備できていることを意味します。
HNでの議論
86- skybrian
このオートコンプリートは存在しないドメインを提案します。ただガラクタを入力するだけで何かを提案しますが、そこに行くとレコードがありません。オートコンプリートボックスの目的の一つはタイプミスを避けることなので、これではあまり役に立ちません。
- chrismorgan
keyupを使うのは意味がなく、ユーザーの期待と矛盾しています。アクションをトリガーするため（通常のタイピングを含む）には、常にkeydownだけを使うべきです。（まあ、私にはよくわからない例外が一つあります：スペースバーでボタンをアクティブにする場合です。これはクリックがリリース時に行われるようにkeyupでトリガーされますが、Enterはkeydownでトリガーされます。）keyupは、ゲームでよくあるように、キーの状態に常に反応するようなものに限定されます。これは機能にも影響します。実際、keydownの代わりにkeyupを使うことでレイテンシーを導入しています。気分が悪いです。
- ViscountPenguin
残念ながら、このアプローチはオーストラリアではあまり良く感じられません。間違いなくレイテンシーの影響です。これを最適化問題として捉えることで、もっと良くできると思います。完全なアルファベット辞書を使い、人気度で重み付けされた残りのドメイン名ツリーをできるだけカバーするような残差予測を追加するのです。このツリーは事前に構築して同じシステムに保存できます。これならオーストラリアでもp99 0msを達成できるでしょう。
- oersted
なぜいつものようにkeyDownでfetchをトリガーして、レスポンスが来たらすぐに表示しないのですか？キーを押すのにかかる時間はAPIレイテンシーの目標として妥当だと思いますが、それでも恣意的な目標です。APIが速い場合、keyUpまで表示を待つのはレイテンシーを増やすだけです。keyUpに同期しても、私にはより即時的に感じられません。
- kevmo314
ネットワークレイテンシーをさらに減らしたいなら、各トライノードをファイルとして保存し、そのノードへのプレフィックスパスをファイル名にすると便利です。そして、数億のファイルをR2にダンプします。これでトラバーサルは完全にCDNルックアップで行えます！