2億4000万件のドメイン名に対するP99 0ms* オートコンプリート

アスタリスクについては後述します。 私はWirewiki.comを運営しています。これはドメイン名のようなインターネットインフラストラクチャを検査するためのウェブサイトです。DNSレコード（履歴を含む）、DNS委譲、メール配信設定などをチェックするのに役立ちます。 このようなサイトは数多く存在します（vibeコーディングのおかげで増え続けています）ので、際立つ方法が必要です。私はツールの品質/有用性とUXを選びました。Wirewikiのナビゲーションの主な手段はオートコンプリートなので、できるだけ完全で、正確で、高速であるべきです。私はそれをインスタントにしたいと思っています。つまり、次のフレームで表示されるくらいに。 私はそれをほとんど達成しました。 自分で試してみてください： DNS root Your IP Tab Cycle tabs Navigate Open 仕組みはこうです。 キーが押されたとき（ユーザーがキーを押し始めたとき）、入力された文字とそれに続く文字の候補をプリフェッチします。そしてキーが離されたとき（ユーザーがキーを離したとき）、候補を描画します。 GET /autocomplete?q=wi { "results": ["wikipedia.org", "windowsupdate.com", "windows.net", "windows.com", "wixsite.com", "wikimedia.org", "wiley.com", "wildberries.ru"], "next": { "-": ["wi-fi.ru", "wi-fi.org", "wi-fi.click", "wi-tribe.ph", "wi-cat.ru", "wi-fi.link", "wi-power.com", "wi-fi.com"], ".": ["wi.gov", "wi.us", "wi.infomart.co.jp", "wi.net", "wi.likebtn.com", "wi.accountants", "wi.agency", "wi.amsterdam"], "0": ["wi0.buzz", "wi0.com", "wi0.mobi", "wi0.site", "wi0.tech", "wi0.top", "wi0.xyz", "wi00.com"], … "9": ["wi9-h.com", "wi9.casino", "wi9.com", "wi9.lol", "wi9.mobi", "wi9.org", "wi9.top", "wi9.xyz"], "a": ["wiadomosci.wp.pl", "wiadomosci.onet.pl", "wiadomosci.gazeta.pl", "wialon.com", "wialon.host", "wiair.com", "wiara.pl", "wiadomosci.radiozet.pl"], … "k": ["wikipedia.org", "wikimedia.org", "wiktionary.org", "wikihow.com", "wikia.com", "wikisource.org", "wikibooks.org", "wikidot.com"], … "z": ["wizzair.com", "wizards.com", "wiz.world", "wiz.biz", "wiz.io", "wiz.cn", "wizardingworld.com", "wizaz.pl"] } } これにより、キープレス1の期間 + キープレス間のギャップ + キープレス2の期間という時間予算が得られます。APIが2回目のキープレス終了前に応答すれば、結果は間に合って準備されます。（60Hzのディスプレイは16.7ミリ秒ごとにレンダリングするため、p50では技術的に8.33ミリ秒の追加時間予算がありますが、p99ではほぼ0ミリ秒です。） キーが離される キーが押される w i k GET /autocomplete?q=wi 'wik' の候補を描画 APIの時間予算 APIの往復時間 'wi' のリクエストは 'i' が押された瞬間に発行され、その応答が 'k' が離される前に到着すれば、'wik' の候補は知覚できないレイテンシで描画されます。 したがって、この記事の目的では、レイテンシをキーアップから描画可能な状態になるまでの時間と定義します。 P99 0ミリ秒とは、99%の時間で、ユーザーがキーを離す前に結果が準備されていることを意味します。 これを実現するには、次の2つのものが必要です。 クライアントサイドでの候補のプリフェッチとキャッシュ。 十分な速度を持つAPI。 予算はどれくらいか？ 2回のキープレスの期間とギャップの期間を使用できることがわかりましたが、それはミリ秒単位でどれくらいでしょうか？ 私は比較的速く100個のドメイン名をタイプしながら測定し、p99は私にとって121ミリ秒になることがわかりました。 私の結果は以下の通りです。あなた自身の測定を開始するには、タイプしてみてください。 レイテンシ予算の測定 これは、あるキープレスから次のキープレスまでの時間を測定します。 スライダーは、指定されたAPIレイテンシで次のフレームでレンダリングされるキーストロークの割合を示します。 121 ms — 121 ms のレイテンシで次のフレーム レイテンシ vs 次フレームの割合。垂直線 = スライダー。 キーストロークあたりの予算（ミリ秒）。線の左側のバーは、現在のレイテンシで失敗します。 入力してドメインをいくつか入力してデータを蓄積してください。 リセット APIをどれだけ速くできるか？ さて、レイテンシの目標は121ミリ秒です。しかし、APIをどれだけ速くできるでしょうか？ 私はこのAPIのために、上位100万件の最も人気のあるドメインのTrancoリストを使用しています。これらは最初に提案されるべきであり、現在使用されている他の任意のドメイン名で補完されます。 CZDSは、ほとんどのgTLD（.com、.net、.orgなど）のすべてのドメインのリストを提供しています。残念ながら、ccTLD（.uk、.de、.frなど）は利用できません。しかし、それらのドメインのうち、意味のあるトラフィックがあるものは、いずれにしてもTrancoリストに含まれています。 証明書透明性ログやArchive.orgのような他のソースもありますが、まだ統合していません。 私はAPIを、まずTranco（ヘッド）を検索し、必要に応じてCZDS（テール）を検索するように設計しました。結果はランク順に返されるため、最初の8件が最も人気があります。 ヘッド：インメモリ文字トライ。トライ（プレフィックスツリー）は、すべてのプレフィックスに対して事前に計算された上位8件の候補を格納します。プレフィックスのルックアップは、いくつかのポインタをたどるだけです。最悪ケースの時間計算量：入力した文字の長さのO（length of what you typed）。 テール：SSDバックメモリマップドブロックインデックス。CZDSドメインはソートされ、デルタ圧縮されて固定サイズのブロックになり、小さなインメモリディレクトリがあります。ルックアップはディレクトリ（27MB）をバイナリ検索し、その後256個の名前のブロックを線形スキャンします。2億4000万件のドメイン名は、約2.5GBのディスクスペースを占めます。ホットページはOSによってメモリにキャッシュされます。最悪ケースの時間計算量：入力した文字の長さ * ドメイン数の対数 のO（length of what you typed * log(number of domains))。 ドメイン数とクエリ長の長さはどちらも制限されているため、両方のデータ構造の最悪ケースは実質的にO(1)となり、P99レイテンシを低く保つはずです。見てみましょう。 ブラウザ wik| Cloudflare グローバルエッジキャッシュ Wirewikiサーバー nginx TLS · プロキシ API Autocomplete 各キーストロークは、ブラウザ → Cloudflare → nginx → API と移動し、応答は同じパスを戻ってきます。 私はLLMに本番サーバーのストレステストを実行させました。6万個のドメイン名をタイプすることをシミュレートして72万回のキーストローククエリを生成し、オープンループ（応答速度に関係なく固定ターゲットレートで発火する）で再生しました。API単体、Nginx経由、エンドツーエンドでAPIをテストしました。 ロードテスト結果 異なるリクエストレートでのレイテンシパーセンタイル。両方の軸は対数スケールです。 APIのみ オリジンパス（nginx + API） エンドツーエンド（Cloudflare + nginx + API） req/s p50 p90 p99 max errors ほとんどのリクエストはAPIによって2ミリ秒以内に応答されます。1.6k req/sでも、NginxとAPIは99%の時間で15ミリ秒以内に応答します。 数ミリ秒を削ることもできると思いますが、これで満足しています。APIをさらに最適化しても意味がありません。ネットワークがレイテンシを支配しているからです。 実際には、オートコンプリートのレイテンシは、ブラウザからサーバーへのCloudflare経由の往復時間 + 10ミリ秒とほぼ同じです。 Cloudflareを介した往復はかなりのレイテンシを追加しますが、頻繁なリクエストを吸収する役割も果たします。私のテストでは、そのエンドツーエンドのレイテンシは予算内に収まっています。たとえ1000人が同時にタイプしている場合でもです。 問題は、私がヨーロッパに単一のサーバーを稼働させているだけだということです。そのため、遠方からのトラフィックはP99で予算を超えるでしょう。例えば、アメリカからのトラフィックは100〜200ミリ秒を追加するでしょう。 ホットパスのCDNキャッシュと、Nielsenの0.1秒の「インスタント」しきい値がこれを大幅に補いますが、ターゲットに到達するには十分ではありません。 複数のサーバーをセットアップしてトラフィックを地理的にロードバランスすることもできます。そうすれば、P99 0ミリ秒*のレイテンシが得られるでしょう。しかし、それは少しやりすぎです。私にとってもです。 これを製品にするならそうするでしょう。しかし、これはビジネスにするにはニッチすぎると思います。しかし、このAPIへのアクセスに料金を支払うなら、私にメールしてください。考えが変わるかもしれません。 ああ、そしてこれはWirewikiでのUXのために私が設定した基準です。改善できる点があれば、お知らせください。