1.1.1.1のDNSキャッシュ最適化により100テラバイトのメモリを節約

Big Pineapple、すなわち1.1.1.1、Gateway DNS、DNS Firewall、AS112、およびその他のいくつかのCloudflare DNSサービスを支えるプラットフォームは、常に2500億以上のDNSキャッシュエントリを保持しています。その規模では、エントリあたり1バイトの無駄遣いでも、私たちのフリート全体で250ギガバイト以上のメモリを消費します。 メモリ内でのキャッシュエントリの格納方法に対する5回の successive な変更により、エントリあたりのフットプリントが50%以上削減されました。フリート全体で、これらの変更により約100テラバイトのメモリが解放され、これはGen 13サーバー130台分のRAMに相当します。キャッシュはより高速にもなりました。挿入スループットは43%増加し、ルックアップレイテンシは19%低下しました。これは、アロケーションの減少とメモリの局所性の向上により、速度とスペースのトレードオフが発生しなかったためです。 キャッシュする内容 コールドスタート時、Big Pineappleは空のキャッシュから始まります。DNSクエリが到着するにつれて、キャッシュは最大エントリ数に達するまで満たされ、その時点で古いまたは人気のないアイテムを追い出してスペースを確保します。 正確なキャッシュサイズはデータセンターによって異なります。EDNS Client Subnet (ECS) が使用されている場合、権威サーバーはクライアントのネットワークに応じて異なる応答を返すため、同じクエリの複数のバージョンをキャッシュします。これにより、エントリ数と各エントリが消費するメモリの両方が増加するため、この投稿の最適化はECSが多い場所で特に効果的です。 キャッシュ内の各アイテムはキー・バリューペアです。キーはクエリされたものを識別します。 pub struct CacheKey { qname: Name, qtype: Rtype, authenticated: bool, tag: Vec<u8>, } 値はDNS応答自体を格納します。回答、権威、および追加のレコードセクション、作成時間、ヒットカウンター、Time-to-Live (TTL) などのメタデータが含まれます。 pub struct CacheEntry { timestamp: UnixTimeStamp, pub inception: Instant, pub ttl: Ttl, pub hits: u32, pub answers: Vec<Record>, pub authority: Vec<Record>, pub additional: Vec<Record>, pub errors: Vec<ExtendedError>, ... } 両方の構造体には改善の余地があります。いくつかのフィールドは、エントリが格納された後に不要になるオーバーヘッドを持つ型を使用しています。 メモリ使用量のベンチマーク 各変更の影響を測定するために、本番環境で見られるトラフィック分布（Aレコード56%、AAAA 25%、TXT 19%）を大まかに近似するランダムに生成されたエントリでキャッシュを埋めることでベンチマークを行います。各エントリには1つから4つのレコードが含まれます。 TXTレコードは、ベンチマークにおけるすべての非A/AAAAレコードタイプの代わりとして機能します。それらのサイズは64バイトから224バイトの間でランダム化され、可変長レコードタイプの平均応答サイズに近い値です。 私たちは、RustのSystemアロケータをラップし、キャッシュエントリあたりのアロケーションの数とサイズを記録するカスタムアロケータを使用してメモリ使用量を追跡します。メモリと並行して、メモリ節約がパフォーマンスの犠牲にならないように、フルキャッシュフロー全体で挿入スループットとルックアップレイテンシを測定します。 これらの入力は、本番環境を正確に再現するのではなく、近似します。プロセスメモリは、トラフィックミックス、キャッシュ占有率、アロケータの状態、およびキャッシュ外で使用されるメモリにも依存します。そのため、ロールアウト中に本番インスタンス全体の常駐メモリを測定しました。 キャパシティのコスト Vec<T>は、ヒープに割り当てられたデータへのポインタ、現在の長さ、および合計キャパシティの3つのフィールドを格納します。アイテムをプッシュすると、Vecは長さがキャパシティを超えるかどうかを確認し、必要に応じて再割り当てします。空きがあれば、アイテムを追加して長さをインクリメントします。 しかし、DNS応答をキャッシュに格納した後、それを再度変更することはありません。キャパシティフィールドは役に立ちませんが、Vecあたり8バイトを消費します。Vecが8つのアイテムのキャパシティを持ちながら5つしか格納していない場合、ヒープ上に3つのスロットが未使用のままになり、過剰に割り当てられたヒープスペースも無駄になります。 Box<[T]>を使用すると、両方の問題が解決します。作成後に成長できないため、キャパシティフィールドや将来の要素のための予約スペースを必要としません。Stringも同様で、キャパシティフィールドを持ちます。Box<str>はそれをドロップします。 各キャッシュエントリは8つのVecおよびStringフィールドを格納します。それらをBox<[T]>およびBox<str>に置き換えることで、フィールドあたり8バイト、エントリあたり64バイトが節約されます。また、Vecが将来の成長のために予約する余分なヒープメモリも排除されます。合計で2500億以上のキャッシュエントリで、15テラバイト以上の節約になります。 リストの削減、ポインタの削減 回答、権威、および追加のセクションを別々のリストに格納する代わりに、各セクションの開始位置へのオフセットを持つ単一のリストを格納できます。各セクションのDNSレコード数はu16に収まるため、各オフセットにu16（2バイト）を使用できます。これは、個別のBox<[T]>ごとに必要な8バイトのポインタと8バイトの長さに比べて節約になります。 これにより、8バイトのポインタと8バイトの長さを持つ2つのリストが削除され、2バイトのオフセット2つに置き換えられ、エントリあたり28バイトが節約されます。 これらの節約は、個々のフィールドから削除されたバイト数に直接対応するとは限りません。Rustはアラインメント要件を満たすためにパディングを挿入し、構造体のサイズをアラインメントの倍数に切り上げます。そのため、小さなフィールドを削除すると、追加のパディングが排除される可能性があります。例えば、複数のブールフィールドを単一のビットフラグにパックしました。これにより、周囲のパディングが減少し、構造体は個々のブール値のサイズよりも大きく縮小しました。 オーナーのドロップ 各DNSレコードには、レコードが属するドメインであるオーナーがあります。多くの場合、このオーナーはクエリされたドメインと同じです。例えば、example.com Aクエリは、同じオーナーを持つ2つのレコードを返します。 $ dig example.com A ;; ANSWER SECTION: example.com. 300 IN A 198.51.100.1 example.com. 300 IN A 198.51.100.2 しかし、CNAMEが関与している場合、例えば、レコードオーナーはクエリされたドメインと異なる場合があります。 $ dig example.com A ;; ANSWER SECTION: example.com. 300 IN CNAME cdn.example.com. cdn.example.com. 300 IN A 198.51.100.1 cdn.example.com. 300 IN A 198.51.100.2 DNSワイヤフォーマットは、RFC 1035で定義されているように、名前圧縮を使用して繰り返しオーナーを処理します。同じドメインを2回エンコードする代わりに、後続の出現では最初の出現への2バイトポインタを格納します。www.example.comのようなドメインは、メッセージ内で既にexample.comが登場した場所へのポインタに続くwwwのみをエンコードできます。 これはワイヤ上ではうまく機能しますが、キャッシュ内では各レコードの横に完全なオーナー名を格納します。キャッシュルックアップ中に圧縮ポインタをたどるのはホットパスでは高コストなので、速度のためにメモリをトレードオフします。 しかし、ほとんどのレコードは、クエリされたドメインとオーナーが同一です。それらの場合、オーナーを完全にドロップし、読み取り時に推測できます。CNAMEの背後にあるAレコードのようにオーナーが異なる場合は、完全な名前を格納します。 pub struct Record { owner: Option<Box<Name>>, class: Class, ttl: Ttl, rtype: Rtype, data: RecordData, } ownerがNoneの場合、応答構築はキャッシュキーからクエリされたドメインを復元し、ヒープアロケーションを回避します。これは、レコードがもはや自己完結型ではないことを意味しますが、キャッシュキーはすべてのルックアップ中に既に利用可能です。オーナーが異なる場合、Someはヒープ上の完全な名前へのポインタを格納します。 実際には、キャッシュされたレコードのほとんどはクエリされたドメインとオーナーが同一であるため、大多数はオーナーフィールドのヒープアロケーションを必要としません。 Enumのサイジング Rustのenumは合計型です。各バリアントは異なるデータを保持できますが、enumは常にその最大のバリアントのサイズになります。 pub enum Option<T> { Some(T), None, } Optionは、値を持つSomeか、何も持たないNoneのいずれかです。両方のバリアントは同じ量のメモリを消費します。enumはアクティブなバリアントを示すタグを格納し、その後に最大のバリアントのデータに十分なスペースが続きます。バリアントがNoneの場合、そのスペースは未使用です。 レコードデータの場合、各DNSレコードタイプをenumバリアントとして格納するのが自然に思えます。 pub enum RecordData { A(Ipv4Addr), Aaaa(Ipv6Addr), Txt(Txt), Naptr(Naptr), Svcb(Svcb), // ... } しかし、enumは常にその最大のバリアントと同じ大きさになります。この場合、それは136バイトのNAPTRです。3つの可変長テキストフィールド、ドメイン名、および2つの整数を格納します。その結果、バリアントタグとパディングを含む完全なenumは144バイトになります。 Aレコードは4バイトしか必要とせず、AAAAレコードは16バイトしか必要としません。Aと