怠惰な Redis は、より良い Redis
Redis がシングルスレッドだということは、誰もが知っています。よく知っている人なら、実際には Redis は「だいたい」シングルスレッドだと説明するでしょう。ディスク上で特定の低速な処理を行うためのスレッドも存在するからです。これまで、スレッドを使う処理は I/O に大きく偏っていたため、別スレッドで非同期タスクを実行するための小さなライブラリには、基本的に Background I/O を意味する bio.c という名前を付けていました。
ところが少し前、私を含め、多くの人が望んでいた新しい Redis の機能、「lazy free」について実装を約束する issue を立てました。元の issue はここです：https://github.com/antirez/redis/issues/1748。
この issue の要点は、Redis の DEL 操作が通常はブロッキングだということです。Redis に DEL mykey を送ったとき、もしそのキーに 5,000 万個のオブジェクトが入っていたら、サーバーは数秒間、何も処理せずに停止してしまいます。歴史的には、これは Redis の設計に伴う副作用としておおむね受け入れられてきました。しかし、用途によっては限界になります。ブロッキングするコマンドは DEL だけではありません。ただ、DEL は特殊な存在です。というのも、通常は「O(1) と O(log_N) のコマンドを使う限り、Redis は非常に高速だ」と説明するからです。O(N) のコマンドを使っても構いませんが、そこは最適化の対象ではないので、レイテンシーの急上昇に備えてください。
これはもっともな話に聞こえます。しかし同時に、高速な操作で作られたオブジェクトであっても、いずれは削除しなければなりません。そしてそのとき、Redis はブロックします。
最初の試み
シングルスレッドのサーバーで処理をノンブロッキングにする簡単な方法は、すべてを停止するのではなく、処理を段階的に進めることです。たとえば、100 万個のアロケーションを解放する必要がある場合、for() ループですべてをブロックする代わりに、1 ミリ秒ごとに 1,000 個ずつ解放できます。使う CPU 時間は同じか、処理が増える分だけ少し多くなります。しかし、ユーザーから見たレイテンシーははるかに改善します。1 ミリ秒に 1,000 個を解放するための CPU サイクルは、そもそも使われていなかったかもしれません。ここで重要なのは、数秒間のブロックを避けることです。Redis 内部では、このように動作している処理がたくさんあります。LRU eviction とキーの有効期限切れは分かりやすい例ですし、ハッシュテーブルのインクリメンタルなリハッシュなど、ほかにもあります。
そこで、まずこれを試しました。新しいタイマー関数を作り、そこで解放処理を行うのです。オブジェクトをリンクリストにキューイングし、タイマー関数が呼び出されるたびに、少しずつ段階的に回収します。うまく動かすには、いくつか工夫が必要です。たとえばハッシュテーブルで実装されたオブジェクトも、Redis の SCAN コマンド内部で使っているのと同じ仕組みを利用して、段階的に回収しました。辞書内のカーソルを取得し、要素を 1 つずつ解放しながら反復するのです。こうすれば、タイマーが呼び出されるたびにハッシュテーブル全体を解放する必要はありません。次にタイマー関数へ戻ってきたとき、カーソルが前回どこまで進んだかを教えてくれます。
適応制御は難しい
これの難しいところが何か分かりますか？ 今回、段階的に行っているのは、非常に特殊な処理だからです。メモリを解放しているのです。メモリを段階的に解放している間に、サーバーのメモリ使用量が急速に増えたら、レイテンシーを守る代わりに、上限のない量のメモリを消費することになりかねません。これは非常にまずいことです。たとえば、次のような処理を考えてみてください。
WHILE 1
SADD myset element1 element2 … many many many elements
DEL myset
ENDバックグラウンドでの myset の削除が、1 回の SADD で大量の要素を追加する速度に追いつかなければ、メモリ使用量は永遠に増え続けます。
しかし、いくつか実験したところ、非常にうまく動かす方法が見つかりました。タイマー関数に、メモリの負荷に適応させるための 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 とは何なのかと尋ねてきました）。では、何をしたのでしょうか。
- クライアントの出力バッファを、
robj構造体ではなく、動的文字列だけを使うように変更しました。返信を作るときには、値は常にコピーされます。 - Redis のすべてのデータ型を、共有された
robj構造体ではなく SDS 文字列を使うように変換しました。簡単そうに聞こえますか？ 数週間にわたって、バグの影響を非常に受けやすいコードを約 800 行変更しました。しかし、今ではすべてのテストに通っています。 - lazyfree をスレッド化するよう書き直しました。
その結果、データ構造の実装から robj 構造体がなくなったため、Redis はメモリをより効率的に使えるようになりました（ただし、コマンドのディスパッチやレプリケーションなど、共有が多く発生するコードパスでは robj は使われています）。スレッド化した lazy free は非常にうまく動き、メモリ回収の速度も段階的な方式より速くなっています。段階的な方式の実装は私がかなり気に入っていましたし、スレッド方式と比べても決してひどいものではありませんでしたが、それでも結果はこうなりました。巨大なキーを削除しても、性能低下はごくわずかです。これは非常に便利です。しかし、最も興味深いのは、これまでテストしたすべての操作で Redis が高速化したことです。間接参照を減らした効果は、本当に大きな勝因でした。クライアントの出力バッファがより単純で高速になったため、関係のないベンチマークでも高速になっています。最終的に私は、このブランチから段階的な lazy free の実装を削除し、スレッド方式だけを残しました。
API について
では、API はどうでしょうか。現在もブロッキングする DEL は残っています。デフォルトの動作も同じです。Redis における DEL は、メモリを今すぐ回収することを意味するからです。私はこの動作を変更したくありませんでした。そこで、値に何が起きるのかをより明確に示す新しいコマンド、UNLINK を追加しました。
UNLINK は賢いコマンドです。オブジェクトの解放コストを計算し、それが非常に小さければ、DEL が本来行うように、オブジェクトを ASAP で解放します。そうでなければ、処理用のバックグラウンドキューへオブジェクトを送ります。それ以外の点では、キー空間の意味論から見た 2 つのコマンドは同一です。
FLUSHALL / FLUSHDB のノンブロッキング版も実装しましたが、まだ API レベルではありません。LAZY オプションを指定すると動作が変わる、という形になる予定です。
lazy free だけではない
集約データ型の値が完全に共有されなくなり、クライアントの出力バッファにも共有オブジェクトが含まれなくなったことで、活用できる余地が大きく広がりました。たとえば、ついに Redis でスレッド化した I/O を実装できるようになります。異なるクライアントを異なるスレッドで処理できるということです。データベースにアクセスするときだけグローバルロックを取得し、クライアントの読み書きのシステムコールや、クライアントが送ってきたコマンドの解析まで、別々のスレッドで実行できるようになります。これは memcached に似た設計で、実装してテストするのを楽しみにしています。
さらに、集約データ型に対する特定の低速な操作を別スレッドで実行し、ほんの一部のキーだけを「ブロック」して、ほかのすべてのクライアントは処理を続けられるようにもなります。これは、現在ブロッキング操作で行っている方法（blocking.c を参照）に加えて、現在どのキーがどのクライアントによって使用中なのかを保存するハッシュテーブルを用意することで、非常によく似た形で実現できます。たとえばクライアントが SMEMBERS のような処理を要求した場合、そのキーだけをロックし、出力バッファを作りながら要求を処理し、その後でキーを再び解放できます。ブロックされているキーにアクセスしようとするクライアントだけがブロックされ、ほかのクライアントは影響を受けません。
これらすべてには、さらに大幅な内部変更が必要です。しかし、ここで重要なのは、タブーが 1 つ減ったことです。オブジェクトのコピーにかかる時間は、キャッシュミスを減らし、集約データ型のメモリフットプリントを小さくすることで埋め合わせられます。これで、共有しない設計のスレッド化 Redis について自由に考えられるようになりました。これは、シングルスレッド版を容易に上回れる唯一の設計です。これまで、スレッド化した Redis といえば、並行アクセスを実装するためにデータ構造やオブジェクトへ大量の mutex を置くという、常に悪いアイデアとして見られていました。しかし幸いなことに、両方の長所を得る方法はあります。必要なら、これまでどおり高速な操作をすべてメインスレッドから処理することもできます。性能面では、得られるものしかないはずです。代償は、ある程度制御された複雑さです。
予定
内部をかなり変更しました。明日から本番で使えるようなものではありません。そこで、現在すでにあるものを 3.2 として unstable に呼び込み、Release Candidate の状態にする作業を行い、このブランチを 3.4 を目標として unstable にマージする計画です。
ただしマージする前に、速度低下がないか非常に綿密なチェックを行う必要があります。まだやるべきことは確実に残っています。
試してみたい場合は、Github の「lazyfree」ブランチを確認してください。ちなみに、現在私はこの作業を非常に活発に進めているので、ある瞬間には完全に壊れているものがあるかもしれないことに注意してください。