目印を9割減らしたら、世界中のサーバーから100TBが空いた
Cloudflareが、社内の振り分けサーバーで使う「一貫性ハッシュ」の目印を、統計で確かめながら9割削減。データの持ち方も8バイトから6バイトに詰めて、世界中で100TBぶんのメモリを取り戻した。
ことね：ひかり、ちょっと考えてみて。この部室に棚が100個あって、みんなのプリントをそこに振り分けるとするでしょう。どのプリントをどの棚に入れるか、あなたならどうやって決める?
ひかり：えっ、簡単だよっ! 名前のあいうえお順っ! あ行の人はこの棚、か行の人は隣、ってっ!
ことね：いい答えね。……でも、棚が1個こわれて99個になった瞬間、全部並べ直しになるの。それを避ける仕組みが「一貫性ハッシュ」。……プリントの名前も棚の名前も、まず計算で数字に変えるのよ。長い数直線の上に、棚と、プリントを、その数字の場所に置く。プリントは「自分より左にある、いちばん近い棚」が担当。そう決めておけば、棚が1個いなくなっても、動くのはその棚が持っていたぶんだけ。ほかは全員そのままでいられるの。Cloudflareは、どのサーバーがどのファイルを預かるかを、これで決めているわ。……ただ、これだけだと問題があってね。
みずき：…で?
ことね：数直線の上の置き場所は、計算の結果だからほとんどでたらめなの。だから「隣の棚まで遠い棚」と「すぐ隣に棚がある棚」ができて、担当の量が偏るのよ。サーバー100台に目印を1個ずつだと、ばらつきは約99%。ほぼ当てにならない。そこで、1台のサーバーに目印をたくさん打って、数直線のあちこちに散らすの。100台に160個ずつ置くと、ばらつきは約8%まで落ちるわ。NGINXが既定で160個にしていて、Pingoraも同じ値を使っているの。……さらにCloudflareは、ディスクの大きいサーバーに多めに働いてもらいたいから、容量に応じて目印の数を変えているのよ。「ケタマ」という方式ね。そのうえ、どのサーバーでも受けられる仕事ばかりじゃないでしょう。法令や機能の都合で、担当できる組み合わせごとに数直線をまるごと別に用意する必要があるの。……そうやって、目印の数が膨らんでいったわ。
ひかり：うわっ、目印を増やす→重みで増やす→数直線ごと増やす、で三段重ねっ! そんなに膨らんだの、どうやって減らしたのっ?
ことね：二か所よ。ひとつは、目印1個の持ち方。目印は「計算した数字」と「どのサーバーか」の番号を並べて8バイト。でも番号のほうは4バイトも要らないの。4バイトだと42億台まで数えられるけれど、2バイトでも6万5千台。そんなにサーバーは並ばないわ。……ところがRustには、部品のいちばん大きいものに合わせて隙間を詰めるルールがあって、素直に縮めても8バイトのままなの。だから6バイトの生のバイト列として持って、読み出すときに取り出す関数を付けた。これで25%減。……もうひとつが本命ね。目印の数を9割減らしても、ばらつきはほとんど増えない、と計算で確かめたの。しかも数字は32ビットだから、目印を増やしすぎると別々の目印がたまたま同じ場所に重なって、かえって誤差が増えることまで分かったそうよ。結果、世界中で100テラバイトぶんのメモリが空いたわ。先月DNSのチームが減らした100テラバイトとは、別にね。
みずき：…2バイト削るために、Rustをだまして生のバイト列を手で読む。それで四分の一。……残りは「実は要りませんでした」って計算で示しただけ。いちばん効いたの、コードじゃないじゃん。
ことね：そこが面白いところなのよ。書いた人も最後に「Rustで全部は解決できないかもしれないけれど、数学はどこでも通じる」と締めているわ。……ただし、怖いのは切り替えのほう。目印を減らすと数直線の担当割りが変わるでしょう。つまり、どのサーバーがどのファイルを預かるかが変わるの。世界中で一斉にやったら、そこらじゅうのキャッシュが同時に空振りして、元のサーバーに問い合わせが雪崩れ込む。……だから新旧ふたつの数直線を同時にメモリに載せて、リクエストごとにどちらで決めるかを選べるようにして、小さなデータセンターから順ににじり寄ったの。全部が新しいほうに移りきってから、古いほうを消したわ。
ひなた：ふぁ〜……お引っ越しのあいだだけ、お家を2軒借りるのです。……メモリを減らすお話なのに、途中はいちばん散らかっていたのですね。
まとめ：削ったのは2バイトと、なくても困らなかった目印。効いたのは、それを確かめた計算のほう。