誰もが知っているように、Redisはシングルスレッドだ。より詳しい人なら、実際には“ほぼ”シングルスレッドなのだと教えてくれるだろう。ディスク上の遅い処理を実行するためにスレッドが存在するからだ。これまでスレッドで行われる処理はI/Oに特化していたため、別スレッドで非同期タスクを実行するための小さなライブラリは、端的に言えばbio.c、すなわちBackground I/Oと呼ばれていた。

しかし少し前、私は多くの人が、私自身も含めて望んでいた「lazy free」と呼ばれるRedisの新機能を約束するissueを立てた。元のissueはこちらだ。https://github.com/antirez/redis/issues/1748。

このissueの要点は、RedisのDEL操作は通常ブロッキングするという点だ。仮に「DEL mykey」を送ったときに、そのキーに5000万個ものオブジェクトが含まれていたら、サーバーは何秒もの間ブロックし、その間一切の処理をしなくなる。歴史的にこれはRedisの設計上の副作用としてほぼ受け入れられてきたが、特定のユースケースでは制約となる。DELだけがブロッキングするコマンドというわけではないが、特別な存在だ。というのも、通常はこう言われているからだ――RedisはO(1)やO(log_N)のコマンドを使っている限り非常に高速だ。O(N)コマンドを使うのも自由だが、それは我々が最適化の対象としているケースではないので、レイテンシのスパイクを覚悟してほしい、と。

これはもっともに聞こえるが、一方で、高速な操作で作られたオブジェクトでさえ、いずれ削除する必要がある。そしてその際にRedisはブロックしてしまうのだ。

最初の試み

シングルスレッドのサーバーで操作をノンブロッキングにする手っ取り早い方法は、世界を止めるのではなく、処理を少しずつ段階的に行うことだ。たとえば100万件のアロケーションを解放する必要がある場合、for()ループですべてをブロックする代わりに、1ミリ秒ごとに1000要素ずつ解放するといった具合だ。消費するCPU時間は同じか、ロジックが増える分だけ少し多くなるが、ユーザーから見たレイテンシは格段に改善する。1ミリ秒あたり1000要素を解放するためのサイクル自体、そもそも使われていなかった可能性もある。何秒もブロックすることを避けるのが、ここでの鍵だ。Redis内部の多くの仕組みはこのように動いている。LRUによる追い出しやキーの期限切れはわかりやすい例だが、ハッシュテーブルのインクリメンタルなリハッシュなど、ほかにもある。

そこで私が最初に試したのが、新しいタイマー関数を作り、そこで解放処理を行う方法だった。オブジェクトは単に連結リストにキューイングされ、タイマー関数が呼ばれるたびに少しずつ段階的に回収されていく。これをうまく機能させるにはちょっとした工夫が必要だ。たとえばハッシュテーブルで実装されたオブジェクトは、RedisのSCANコマンド内部で使われているのと同じ仕組み――辞書内にカーソルを取り、要素を一つずつ解放しながらイテレートしていく――を使って段階的に回収された。こうすることで、タイマー呼び出しごとにハッシュテーブル全体を解放する必要がなくなる。次にタイマー関数に再入したときにどこまで進んだかは、カーソルが教えてくれるのだ。

アダプティブにするのは難しい

この手法で難しいのは何だか分かるだろうか？ 今回、段階的に行っているのは非常に特殊なタスク――メモリの解放だということだ。だから、段階的にメモリを解放している間にサーバーのメモリ使用量が急速に増加すると、レイテンシを優先するあまり、際限なくメモリを消費してしまう可能性がある。これは非常にまずい。たとえば次のようなケースを想像してみてほしい。

WHILE 1
    SADD myset element1 element2 … many many many elements
    DEL myset
END

もしバックグラウンドでのmysetの削除が、1回あたり大量の要素を追加するSADD呼び出しに比べて遅ければ、メモリ使用量は際限なく増え続けてしまう。

しかし何度か実験を重ねるうちに、これを非常によく機能させる方法を見つけた。タイマー関数は、メモリ圧迫に適応するために2つのアイデアを使っていた。

1. メモリの傾向をチェックする。増えているのか減っているのかを見て、どれだけ積極的に解放するかを調整する。
2. さらに「1」に基づいてタイマー自体の頻度も調整する。解放すべきものが少ないときにイベントループを継続的に中断してCPU時間を無駄にしないようにするためだ。同時に、本当に必要なときにはタイマーは約300 HZまで到達することもあった。

このアイデアを実装していた、今はもう存在しない関数からのコードの断片を少し紹介しよう。

/* Compute the memory trend, biased towards thinking memory is raising
 * for a few calls every time previous and current memory raise. */
if (prev_mem < mem) mem_trend = 1;
mem_trend *= 0.9; /* Make it slowly forget. */
int mem_is_raising = mem_trend > .1;

/* Free a few items. */
size_t workdone = lazyfreeStep(LAZYFREE_STEP_SLOW);

/* Adjust this timer call frequency according to the current state. */
if (workdone) {
    if (timer_period == 1000) timer_period = 20;
    if (mem_is_raising && timer_period > 3)
        timer_period--; /* Raise call frequency. */
    else if (!mem_is_raising && timer_period < 20)
        timer_period++; /* Lower call frequency. */
} else {
    timer_period = 1000;    /* 1 HZ */
}

これはうまいトリックで、非常によく機能した。だが、それでもこの処理をシングルスレッドでやらなければならないのは、どこか物悲しかった。うまく処理するためのロジックも大量に必要だったし、いずれにせよlazy freeのサイクルが非常に忙しいときは、1秒あたりの操作数が通常の約65%まで落ち込んだ。

オブジェクトの解放を別スレッドで行えば、ずっとシンプルになる。解放だけに専念するスレッドがいれば、解放はデータセットに新しい値を追加するよりもほぼ常に高速だからだ。もちろん、メインスレッドがアロケータを呼び出すのとlazy freeスレッドが同じことをする間では多少の競合はあるが、Redisがアロケーションに費やす時間はわずかで、はるかに多くの時間をI/Oやコマンドのディスパッチ、キャッシュミスなどに費やしている。

しかし、スレッド化されたlazy freeを実装する上では大きな問題があった。Redis自体だ。内部設計はオブジェクトを共有することに完全に偏っていた。なにしろオブジェクトは参照カウントされているのだから、できる限り共有しない手はない、メモリも時間も節約できる、というわけだ。いくつか例を挙げよう。SUNIONSTOREを実行すると、結果のセットには共有されたオブジェクトが入ることになる。同様に、クライアントの出力バッファはソケットに返信として送るオブジェクトのリストを持っているため、SMEMBERSのような呼び出しの間は、セットの全メンバーが出力バッファのリスト内で共有されることになりかねない。だからオブジェクトの共有は、とても有用で、素晴らしく、驚くほど、とてつもなくクールに思えるのだ。

だが、ちょっと待ってほしい、ここにはもう一ひねりある。SUNIONSTOREの後にデータベースをリロードすると、オブジェクトは共有されなくなるため、メモリ使用量が突然それまでより跳ね上がる可能性がある。あまり良くない。さらに、クライアントに返信を送るときに何が起きているか。実際には、オブジェクトが小さい場合、単純なバッファに“貼り合わせて”しまっている。そうしないと大量のwrite()呼び出しは効率が悪いからだ！（おまけのヒントだが、writev()も役に立たない）。つまり我々はすでにほとんどコピーしているのだ。そしてプログラミングにおいて、有用でもないのに存在しているものは、たいてい問題になる。

そして実際、集合型データ型を含むキーの内部で値にアクセスするたびに、次のような経路をたどらなければならなかった。

key -> value_obj -> hash table -> robj -> sds_string

では、“robj”構造体を完全に排除して、集合型の値をSDS文字列のハッシュテーブル（あるいはスキップリスト）だけで構成するようにしたらどうだろう？（SDSはRedis内部で文字列に使っているライブラリだ）。これには問題がある。たとえばSADD myset myvalueのようなコマンドを想像してほしい。client->argv[2]をそのまま取ってきて、セットを実装するハッシュテーブル内で参照するわけにはいかない。値を重複して持つ必要がある場合があり、コマンド解析時に作られたクライアント引数ベクターにすでに存在するものを再利用できないのだ。しかしRedisのパフォーマンスはキャッシュミスに支配されているため、間接参照を1つ減らすことで、このコストを相殺できるかもしれない。

そこで私はこの新しいlazyfreeブランチに取り組み始め、何の文脈もなくTwitterでそのことをつぶやいた。おかげでみんな私が絶望しているか頭がおかしくなったと思ったようだ（何人かは結局、このlazyfreeなるものは一体何なのかと尋ねてきた）。では私は何をしたのか？

1. クライアントの出力バッファを、robj構造体の代わりに単なる動的文字列を使うように変更した。返信を作る際には値は常にコピーされる。
2. すべてのRedisデータ型を、共有されたrobj構造体の代わりにSDS文字列を使うように変換した。些細なことのように聞こえるだろうか？ 数週間にわたって、バグに極めて敏感な約800行が変更された。だが今ではすべてのテストが通っている。
3. lazyfreeをスレッド化するように書き直した。

結果として、Redisはよりメモリ効率が良くなった。データ構造の実装にrobj構造体がなくなったからだ（ただし、コマンドのディスパッチやレプリケーションなど、共有が多く発生するコードパスでは依然として使われている）。スレッド化されたlazy freeは素晴らしく機能し、メモリの回収においてインクリメンタルな方式よりも高速だ。インクリメンタルな実装も私がとても気に入っているもので、スレッド化されたものと比べてもそれほどひどいわけではなかったのだが。それでも今では、巨大なキーを削除してもパフォーマンスの低下は無視できるほどで、これは非常に有用だ。しかし最も興味深いのは、これまでにテストしたすべての操作でRedisが高速になったことだ。間接参照が減ったことが本当に効いたのだ。クライアントの出力バッファがよりシンプルで高速になったおかげで、直接関係のないベンチマークでも高速化している。最終的に私はブランチからインクリメンタルなlazy freeingの実装を削除し、スレッド化されたものだけを残した。

APIについての補足

ではAPIはどうなるのか？ 依然としてブロッキングするDELは残る。デフォルトの挙動は変わらない。RedisにおけるDELは「今すぐメモリを回収する」ことを意味するからだ。私はそれを変更する気にはなれなかった。そこで新たにUNLINKというコマンドが用意された。これは値に何が起きているかをより明確に示している。

UNLINKは賢いコマンドだ。オブジェクトの解放コストを計算し、非常に小さい場合はDEL本来の動作通り、できるだけ早くオブジェクトを解放する。そうでなければオブジェクトはバックグラウンドキューに送られて処理される。それ以外では、キー空間のセマンティクスという観点からは2つのコマンドは同一だ。

FLUSHALL / FLUSHDBのノンブロッキング版も実装されたが、まだAPIレベルではない。LAZYオプションを付けると挙動が変わるようになる予定だ。

lazy freeingだけではない

集合型データ型の値が完全に非共有になり、クライアントの出力バッファも共有オブジェクトを含まなくなった今、活用できることは多い。たとえば、Redisでついにスレッド化されたI/Oを実装することが可能になった。異なるクライアントを異なるスレッドが担当するのだ。つまり、データベースにアクセスするときだけグローバルロックが必要になるが、クライアントのread/writeシステムコールや、クライアントが送ってくるコマンドのパースさえも、別スレッドで実行できる。これはmemcachedに似た設計で、ぜひ実装してテストしてみたいと思っているものだ。

さらに、集合型データ型に対する特定の遅い操作を別スレッドで実装し、少数のキーのみを“ブロック”しつつ、他のすべてのクライアントは処理を継続できるようにすることも可能になった。これは現在ブロッキング操作で行っていること（blocking.cを参照）と非常に似た方法に、現在どのキーがどのクライアントによってビジー状態にあるかを保持するハッシュテーブルを加えることで実現できる。たとえばクライアントがSMEMBERSのようなものを要求した場合、該当するキーだけをロックし、出力バッファを生成してリクエストを処理し、後で再びキーを解放することが可能だ。キーがブロックされている場合にブロックされるのは、同じキーにアクセスしようとするクライアントだけだ。

これらすべてにはさらに抜本的な内部変更が必要だが、要するに、タブーが一つ減ったということだ。オブジェクトのコピーにかかる時間を、キャッシュミスの削減と集合型データ型のメモリフットプリント縮小で相殺できるため、share-nothing設計のスレッド化されたRedisという観点で自由に考えられるようになった。これこそが、シングルスレッドのRedisを容易に上回ることができる唯一の設計だ。かつてスレッド化されたRedisは、データ構造やオブジェクトにミューテックスを仕込んで並行アクセスを実現するものとして考えられれば、常に悪手と見なされてきた。しかし幸いなことに、両方の世界の良いとこ取りをする代替手段がある。そして望むなら、これまで通りすべての高速な操作をメインスレッドで処理し続ける選択肢もある。ある程度の複雑さという代償はあるものの、パフォーマンスの面では得しかないはずだ。

ETA

私は内部をかなりいじったので、これは明日すぐに本番投入されるようなものではない。だから私の計画は、すでにunstableにあるものを3.2と呼び、リリース候補の状態にする作業を進め、このブランチについては3.4をターゲットにunstableへマージすることだ。

ただしマージする前に、速度の退行がないか非常に綿密なチェックを行うべきだ。やるべきことはまだ確実に残っている。

試してみたい方は、GitHub上の“lazyfree”ブランチをチェックしてほしい。ちなみに、現在私はこれに非常に活発に取り組んでいるため、時によっては一部が完全に壊れている可能性もあることは留意してほしい。