240万ドメイン名の高速オートコンプリート、p99レイテンシ0ms*を実現

240 million ドメイン名に対応したオートコンプリート API が、ハイブリッドデータ構造とプリフェッチ戦略により p99 レイテンシ 0 ms* を達成した。

Ruurtjan Pul 氏は Wirewiki.com 向けにオートコンプリート API を設計し、DNS レコードや DNS デリゲーション、メール配信設定の確認を可能にした。同 API は keyDown イベント時に候補をプリフェッチし、keyUp イベント時にレンダリングする仕組みにより、超低レイテンシを実現している。

システムアーキテクチャ

システムは「ヘッド」と「テール」の2層構造を採用している。ヘッドは Tranco リストの上位 1 million ドメインをメモリ上のキャラクタトライに格納し、各プレフィックスごとに 8 個の候補を事前計算している。テールは SSD 背面のメモリマップブロックインデックスで、2.5 GB のディスク領域を使用して全 240 million ドメイン名をインデックス化している。メモリ内ディレクトリは 27 MB に抑えられており、線形スキャンのための固定サイズブロック長は 256 names である。

パフォーマンス測定

著者が 100 個のドメイン名を入力した際の p99 レイテンシ予算は 121 ms に達した。ほとんどの API リクエストは 2 ms 以内に応答し、1.6k req/s のピークリクエストレートでも Nginx + API の組み合わせで p99 時間は 15 ms である。LLM ストレステストは 60k 個の入力ドメイン名をシミュレートし、720k キーストローククエリを生成した。

著者は現在、ヨーロッパの単一サーバーで運用しており、「『即座に。次のフレーム感覚で実現したい』」と述べている。USA からのトラフィックは 100～200 ms の追加レイテンシが発生すると予想されている。

筆者の見立て

• 複数サーバーの構築と地理的ロードバランシングにより、p99 0 ms* レイテンシが実現する可能性があると論じている
• USA からのトラフィックにより 100～200 ms の追加レイテンシが発生すると予想している
• このオートコンプリートソリューションはニッチすぎてビジネス化は難しいと考えている
• 本ソリューションを製品化する場合、複数サーバーの構築を実施すると述べている
• ネットワークレイテンシが支配的であるため、API をさらに最適化することは意味を持たないと解釈している

この記事は元記事の事実のみに基づいて自動生成されました。

出典

Ruurtjan Pul, "p99 0 ms* autocomplete for 240 million domain names", https://ruurtjan.com/articles/p99-0ms-autocomplete-for-240-million-domain-names