Transcript
00:00:001バイトでいったいどれほどのコストがかかるでしょうか？
00:00:02Cloudflareの規模であれば、エントリごとに1バイトを無駄にするだけで、
00:00:04全システムのメモリ換算で250ギガバイト以上が
00:00:06コストとして消えていきます。
00:00:08しかし最近、彼らはそのエントリあたりのメモリをなんと半分に削減し、
00:00:11100テラバイトものメモリを解放しました。
00:00:13今のこのご時世において、それは莫大な金額です。
00:00:15彼らはキャッシュシステムに対して、非常にシンプルな
00:00:175つの変更を行うことでこれを実現し、
00:00:18同時にDNSの高速化も果たしました。
00:00:21それでは、その仕組みを見ていきましょう。
00:00:27皆さんも「1.1.1.1」については聞いたことがあるかもしれません。
00:00:30これはCloudflareのパブリックDNSリゾルバであり、
00:00:32betterstack.comのようなアクセスしたいドメインを受け取り、
00:00:34それがどの実際のIPに紐づいているかを
00:00:35調べてくれるという仕組みになっています。
00:00:39そして実際にこの処理を行っているのが、
00:00:40Rustで書かれた「Big Pineapple」というソフトウェアです。
00:00:42想像できる通り、
00:00:43常に猛烈な処理をこなしているシステムであり、
00:00:46常時2500億件を超えるDNSキャッシュエントリを保存しています。
00:00:50これにより、誰かがbetterstack.comにアクセスした直後に
00:00:52別の誰かがアクセスした場合でも、
00:00:53DNS階層全体をもう一度辿る必要がなくなります。
00:00:56メモリ上に回答を保持し、即座に返すことができるのです。
00:00:59しかし冒頭でも述べたように、
00:01:012,500億件のエントリがあるということは、1バイトの無駄が
00:01:04250ギガバイトのRAM消費に直結します。
00:01:07だからこそ、これら5つの変更が極めて大きな効果をもたらしたのです。
00:01:10まず最初は、容量のコストについてです。
00:01:12以前のキャッシュエントリはこのような構造でした。
00:01:14タイムスタンプ、TTL（有効期限）、ヒットカウンター、
00:01:16そして多数のベクターです。
00:01:17回答レコードのベクター、
00:01:18権威レコードのベクター、
00:01:20追加レコードのベクター、
00:01:21エラーのベクター、
00:01:22さらに多くの要素がありました。
00:01:23Rustに馴染みがない方のために説明すると、
00:01:25ベクターはサイズ可変のリストによく使われるデータ型であり、
00:01:27メモリ上では3つの要素で構成されています。
00:01:29ポインタ、長さ、そして容量です。
00:01:31将来の拡張のためにどれだけの領域が予約されているかを示し、
00:01:32要素を追加するたびに再割り当てを行わずに済むようにしています。
00:01:35実際にデータが増加する場合は非常に便利な仕組みです。
00:01:38しかし、実際のDNSキャッシュエントリを調査したところ、
00:01:40データはキャッシュに書き込まれた後は二度と変更されず、
00:01:42触れられていないことが判明しました。
00:01:44読み取り専用だったため、
00:01:45これらのベクターが成長することは実際になかったのです。
00:01:47つまり、ヒープ領域が過剰に確保されたまま、
00:01:49無駄に放置されていたことになります。
00:01:50例えば8項目分の容量を持つベクターであっても、
00:01:525つしか格納されていなければ、
00:01:533つのスロットが未使用のままとなり、
00:01:55容量を表すフィールド自体がusize型であるため、
00:01:578バイトのメモリを消費します。
00:01:58彼らにとってこれは全く必要のないものでした。
00:02:00この問題の解決策は信じられないほどシンプルでした。
00:02:02ベクターをBoxに置き換えるだけです。
00:02:04Boxのサイズは作成時の大きさに固定されるため、
00:02:07容量を保持するフィールドを必要としません。
00:02:08また、そこにあるデータのみを正確に格納するため、
00:02:10将来のための予備容量を割り当てる必要もありません。
00:02:13さらに彼らは、文字列フィールドに対しても
00:02:15全く同じ節約を適用できることに気づきました。
00:02:16文字列は本質的にu8のベクターのようなものだからです。
00:02:18テキストを伸縮させる必要がないのであれば、
00:02:20変更されない文字列であることを示す、
00:02:21ボックス化された文字列スライス（Box）を
00:02:23代わりに使うことができます。
00:02:26結果として、1つのキャッシュエントリあたり
00:02:278つのベクターおよび文字列フィールドが存在していたため、
00:02:29それらをBoxに置き換えることで1フィールドにつき8バイト、
00:02:311エントリあたり64バイトを節約できました。
00:02:33また、ベクターが将来の拡張のために確保していた
00:02:35不要なヒープ領域もなくすことができました。
00:02:36これを2,500億件のキャッシュエントリに換算すると、
00:02:392,500억 개의 캐시 항목으로 환산하면 15테라바이트가 넘는
00:02:42データ型の変更という単純なアプローチだけで、これだけの成果が得られたのです。
00:02:45続く2つ目の変更として、
00:02:46彼らはそれらのリストの一部に目を向け、
00:02:48「そもそもこれらは本当に必要なのか？」と疑問を持ちました。
00:02:50DNSの応答には3つのエントリ、すなわち
00:02:52回答（Answer）、権威（Authority）、追加（Additional）が含まれており、
00:02:54先ほど見たように、
00:02:55これらは到着した順に3つの別々のリストとして
00:02:57キャッシュされていました。
00:02:581つ目の変更で容量フィールドを削除したとはいえ、
00:03:01各リストには依然としてポインタと長さが存在しています。
00:03:03つまり、（8バイト＋8バイト）×3で、
00:03:05合計48バイトと、
00:03:073つの独立したヒープ割り当てが必要でした。
00:03:09しかし、これらのリストが実際にはどのように使われているかを
00:03:10詳細に分析したところ、
00:03:12それらは常に同時に読み出され、
00:03:13同時に書き込まれ、
00:03:14しかも常に全く同じ順序であることが分かりました。
00:03:16そこで3つのリストにする代わりに、
00:03:172つの区切り線を持つ1つのリストとして扱うことにしたのです。
00:03:203つのリストを、レコードの単一リストと、
00:03:22「回答はここで終わり、権威はここで終わる」を示す
00:03:252つの小さなオフセットに置き換えました。
00:03:26DNSの応答に40億件ものレコードが含まれることはまずないため、
00:03:29オフセットには16ビット符号なし整数で十分であり、
00:03:33それぞれわずか2バイトで済みます。
00:03:34これにより全体として、
00:03:3516バイトの完全なヘッダ2つを2バイトの数値2つに置き換えることができ、
00:03:391エントリあたり28バイトの削減となりました。
00:03:41さらに、これによりRustがフィールド間の余分なパディング（隙間）も省けるようになり、
00:03:44削除されたフィールド自体のサイズ以上に構造体を小さくすることができました。
00:03:47彼らはこの発想をさらに推し進め、
00:03:49複数のブール（真偽値）フィールドを1つのビットフラグに統合しました。
00:03:523つ目の変更に移りましょう。
00:03:53「同じ名前を二度言わないようにするにはどうすればよいか？」という点です。
00:03:55すべてのDNSレコードには所有者（オーナー）が保持されていますが、
00:03:57これは単にそのレコードが属するドメイン名のことです。
00:04:00つまり、betterstack.comをクエリしてレコードを取得すると、
00:04:03それぞれのレコードにbetterstack.comという名前が書き込まれています。
00:04:05しかし、その情報はやや冗長です。
00:04:08質問をしたのは自分自身なのですから、
00:04:09システムはすでにドメイン名を把握しています。
00:04:11そしてCloudflareは、すでにそのクエリドメインをキャッシュキーとして保存していたため、
00:04:14オーナーとしてもう一度保存する必要はあるのでしょうか？
00:04:17もちろん、ありません。
00:04:17そこでCloudflareは、このフィールドをオプショナルなボックス名に変更しました。
00:04:20オーナーがクエリと一致する場合は何も保存せず、
00:04:22Noneとし、
00:04:23CNAMEチェーンなどの一部のケースのように
00:04:24本当に異なる場合のみ、
00:04:27これまで通りオーナーを保存するようにしました。
00:04:29これにより、両者が一致する通常のケースでは、
00:04:32レコードごとにヒープ割り当てを丸ごと1回分削減できました。
00:04:34この削減は、キャッシュ内にあるデータを精査し、
00:04:37重複している値が存在することに気づいたことから生まれたものです。
00:04:394つ目の削減は、144バイトもあるIPアドレスに関するものです。
00:04:43レコードデータは、Aレコード、AAAAレコード、TXT、
00:04:47SVCB、NAPTRをまとめたRustのenum（列挙型）になっており、1つの型でこれらすべてをカバーしていました。
00:04:51しかし、ここにはenum特有の問題があります。
00:04:52enumのサイズは、常にその中で最も大きいバリアントに合わせて大きくなるという点です。
00:04:54その型のすべての値は、必要かどうかにかかわらず、
00:04:57常に同じ量のスペースを占有します。
00:04:58その場合、NAPTRが最大の型で136バイトを占め、
00:05:03タグとパディングをenumに追加すると、合計144バイトになります。
00:05:07これを単純なIPv4アドレスであるAレコードの要件と比較すると、
00:05:12必要なのはわずか4バイトです。
00:05:13つまり、キャッシュ内のすべてのAレコードが144バイトのボックスに入れられ、
00:05:17そのうちの4バイトしか使っていないのです。
00:05:19そして、AおよびAAAAレコードが実際のトラフィックの大部分を占めています。
00:05:22Cloudflareのベンチマーク構成では、Aレコードが56%、AAAAが25%であり、キャッシュの大部分がパディングでした。
00:05:29これに対する修正策は、信頼のおけるボックス化です。
00:05:32大きめのバリアントをボックス化し、小さくて頻繁に使われるAおよびAAAAはインラインに残しました。
00:05:36これで、TXT、SVCB、NAPTRはポインタの背後に置かれるため、
00:05:40enumのサイズは、残った中で最大の16バイトのIPv6アドレスの大きさに合わせるだけで済みます。
00:05:45結果として、AまたはAAAAレコード1つにつき、それぞれ120バイトの削減になりました。
00:05:50しかし、この変更にはトレードオフがあります。
00:05:52バリアントをボックス化すると、そのデータはキャッシュエントリの内部から移動し、
00:05:55ヒープのまったく別の領域に格納されるようになります。
00:05:58それにより、2つの新たなコストが生じます。
00:06:001つ目はアロケータです。
00:06:02Cloudflareは jemalloc を使用しており、jemallocは要求された正確なバイト数を返すのではなく、
00:06:06割り当てを固定サイズのビンにグループ化し、最も近いサイズに切り上げます。
00:06:10そのため、32バイトを要求するTXTレコードは32バイトのビンに収まり無駄はありませんが、
00:06:15MXレコードは40バイトを要求して48バイトに切り上げられ、8バイトが無駄に失われます。
00:06:212つ目のコストは局所性です。
00:06:22ボックス化の前は、エントリのすべてのレコードデータがメモリの連続した1つのブロックに収まっていましたが、
00:06:27ボックス化の後はそれぞれが別の場所に存在し、読み取るにはポインタをたどる必要があります。
00:06:31そのポインタがエントリの他の部分から離れた場所を指している場合、
00:06:34CPUは読み取りのためだけに全く新しいキャッシュラインを取得しに行かなければなりません。
00:06:37このように、ボックス化はパディングの問題を解決した一方で新たな問題を生み出しました。
00:06:41そこでCloudflareは、「Rustの型として保存しなければいいのではないか？」と考えました。
00:06:45それが5つ目の変更です。
00:06:46Cloudflareはこれを中間的なアプローチとして説明しています。キャッシュエントリの残りの部分は通常の構造化された
00:06:50フィールドとして維持しつつ、レコードデータ自体は生バイトとして保存します。
00:06:54つまり、レコードごとにenumやボックスを使うのではなく、エントリ全体で1つの `Vec<u8>` 配列を持ち、
00:07:00各レコードは2バイトの長さを表すプレフィックスとそのデータとして書き込まれます。
00:07:03これにより、先ほど述べた2つのコストの両方が解消されます。
00:07:06個別のボックス化された割り当てが、すべてのレコードデータに対する1つの割り当てに統合されるため、
00:07:10レコードごとにjemallocのビンへ切り上げられることがなくなり、
00:07:13再び連続してパッキングされるため、ボックス化によって失われたキャッシュの局所性が取り戻されます。
00:07:18おまけのメリットとして、ルックアップも高速化されます。
00:07:21以前は、キャッシュのヒットごとにメモリ上にパースされたレコードが存在し、
00:07:25どこかに送信する前にフィールド単位でDNSワイヤーフォーマットにシリアライズし直す必要がありました。
00:07:30しかし現在では、すでにDNSワイヤーフォーマットになっているため、ほとんどのレコードタイプはバッファから直接
00:07:35送信メッセージにコピーされます。
00:07:37まだパースが必要なのは、ドメイン名を含むレコード（CNAME、NS、MX、SOAなど）のみで、
00:07:40CNAME、NS、MX、SOAであり、
00:07:43それはDNS名圧縮の仕様上、いずれにせよそれらの名前を書き換える必要があるためだけです。
00:07:47この最後の変更により、メモリが削減され、ホットパス上の多くの処理が削除されます。
00:07:51これがキャッシュに対する5つの低レベルの変更であり、
00:07:54これらを組み合わせることで、1エントリあたりのフットプリントが953バイトから420バイトへと
00:08:0056%小型化され、エントリごとに実際に割り当てられるメモリは1.1キロバイトから461バイトへと、
00:08:0558%削減されました。
00:08:09それに加え、挿入のスループットも43%向上し、
00:08:12毎秒62万5,000エントリから89万3,000エントリになりました。
00:08:17また、ルックアップも19%高速化し、828ナノ秒から670ナノ秒に短縮されました。
00:08:23彼らは今年、これらの変更を本番環境に展開しました。
00:08:25その結果、P99常時メモリは9.3ギガバイトから5.3ギガバイトへと、
00:08:29実際のトラフィックで43%の削減となりました。
00:08:32これはフリート全体で約100テラバイトのメモリが解放されたことになり、
00:08:35第13世代サーバー130台分のRAMに相当します。
00:08:38現在、彼らはその空きスペースを利用してキャッシュをさらに拡大し、
00:08:41処理を一層高速化する計画です。
00:08:43私がこのブログ記事をとても気に入っているのは、私たちが直面せざるを得ないある決断を浮き彫りにしているからです。
00:08:46何かを構築する前に腰を据えてすべての最適化を検討すべきだったのか、
00:08:50あるいはそれは時期尚早な最適化だったのでしょうか？
00:08:52これが構築された2018年当時を想像すると、
00:08:55CloudflareにとってのRAMのコストは現在ほど重要ではなかったのでしょう。
00:08:59元記事は素晴らしい内容ですので、下部にリンクを残しておきます。
00:09:02これについてどう思われるか、コメント欄で教えてください。
00:09:03ついでにチャンネル登録もお願いします。
00:09:04それではいつものように、次の動画でお会いしましょう。
00:09:05また次回お会いしましょう。
Community Posts
No posts yet. Be the first to write about this video!
Write about this video