このドキュメントでは、Redisの仮想メモリサブシステムの内部の詳細を説明します。このドキュメントはユーザのためのものではなく、仮想メモリ実装を理解したい人や、手を加えたいプログラマーのためのものです。
VMサブシステムの目標は、Redisのオブジェクトをメモリからディスクに移すことによって、メモリを空けることにあります。Redisは値のオブジェクトのみを転送します。この概念を理解しやすくするために、 DEBUG コマンドを使用して、Redisの内部では、どのようにキーと値がひもづけられているのかを確認してみましょう。
redis> set foo bar
OK
redis> debug object foo
Key at:0x100101d00 refcount:1, value at:0x100101ce0 refcount:1 encoding:raw serializedlength:4
上記の出力例から分かるように、Redisのトップレベルのハッシュテーブルは、Redisオブジェクト(キー)から、他のRedisオブジェクト(値)への対応表となっています。仮想メモリは、値のオブジェクトだけをディスクにスワップし、キーのオブジェクトはメモリ内に保持します。これは、VMが無効状態のRedisと、VMが有効になっているRedisで、良く使われるデータセットがメモリに収まっている場合は同じぐらいのパフォーマンスを発揮するようにするという設計の主な目標を達成する仕様になっています。
オブジェクトがスワップされる時は、次のようなことが発生します。
これだけを見ると、キーに関連した値の情報はどこに格納されているのか疑問に思うでしょう。それは、キーオブジェクトの中に格納されます。
Redisオブジェクト構造体のrobjは次のような実装になっています。
/* Redisオブジェクトの実体 */
typedef struct redisObject {
void *ptr;
unsigned char type;
unsigned char encoding;
unsigned char storage; /* もしこのオブジェクトがキーなら、値がどこにあるのか？
* REDIS_VM_MEMORY, REDIS_VM_SWAPPED, ... */
unsigned char vtype; /* もしこのオブジェクトがキーでスワップされている場合、,
* スワップされたたオブジェクトの種類を表す */
int refcount;
/* VM属性。これはVM機能が有効な時だけ割り当てられられる。
* そうでない時は、オブジェクトの割り当て関数は、
* ``sizeof(redisObjct) - sizeof(redisObjectVM)sizeof(redisObjct)`` の分のメモリ
* しか確保しないため、VMが無効の場合は常に他のオブジェクトに上書きされる。 */
struct redisObjectVM vm;
} robj;
この中には、VMに関する属性がいくつかあります。この中で最も重要なのは、 storage です。
REDIS_VM_MEMORY
関連する値はメモリの中にある。
REDIS_VM_SWAPPED
関連する値はスワップされていて、ハッシュテーブルの値のエントリーには NULL が設定されている。
REDIS_VM_LOADING
値はディスクにスワップされてエントリーは NULL であるが、現在メモリにスワップされたオブジェクトをロードするジョブが実行中。このフィールドはスレッド対応仮想メモリが有効な場合にのみ使用される。
REDIS_VM_SWAPPING
値はメモリにあり、このポインタは実際にRedisオブジェクトを指しているが、この値をスワップファイルに転送するI/Oジョブが稼働中。
オブジェクトがディスクにスワップされている(REDIS_VM_SWAPPED あるいは REDIS_VM_LOADING)場合、どこに格納されているのかを知るにはどうすればいいのでしょうか？また、その値のタイプはなんでしょうか？これはとてもシンプルです。スワップされたオリジナルのRedisオブジェクトのタイプは、 vtype 属性に格納されています。また、格納されている場所も、 redisObjectVM 構造体型の vm 属性の中に保持されています。この構造体には追加の属性が定義されています。
/* 仮想メモリオブジェクトの構造体 */
struct redisObjectVM {
off_t page; /* オブジェクトが格納されているディスク上のページ */
off_t usedpages; /* ディスクで使用しているページ数*/
time_t atime; /* 最後にアクセスした時間 */
} vm;
この構造体には、スワップファイルの中のどこにオブジェクトが格納されているかというページの場所の情報と、使用しているページ数、また、最後にアクセスした時間の情報が書かれています。この時間情報は、アクセスの少ないオブジェクトをスワップするときに、候補を選択するアルゴリズムから使用されます。
このコードを見ての通り、以前のRedisオブジェクトの構造体の他のすべての属性は使われても(メモリのアラインで空白領域はできるかもしれませんが)、この新しい vm 属性によって、追加のメモリが使用されます。このメモリのコストはVMが無効な時は払う必要はありません。次のコードはRedisオブジェクトを作るときのコードになります。
... some code ...
if (server.vm_enabled) {
pthread_mutex_unlock(&server.obj_freelist_mutex);
o = zmalloc(sizeof(*o));
} else {
o = zmalloc(sizeof(*o)-sizeof(struct redisObjectVM));
}
... some code ...
仮想メモリが無効な場合には、 sizeof(*o)-sizeof(struct redisObjectVM) 分しかメモリを確保していません。 vm 属性は構造体の最後にあるため、他のオブジェクトとメモリ空間がオーバーラップしても問題はなく、仮想メモリを使用しない場合にはメモリのオーバーヘッドは発生しません。
VMサブシステムを理解するための次のステップとして、オブジェクトがスワップファイルに格納される仕組みを見て行きます。スワップファイルで使っているフォーマットは特別なものではなく、 SAVE コマンドを使った時にRedisが通常作成しているダンプファイルに、 .rdb ファイル内にオブジェクトが格納される時に使われるのと同じフォーマットです。
スワップファイルは指定されたサイズ(バイト数)と、指定されたページ数を持つように作られます。これらのパラメータは redis.conf の中で変えることができます。実際に格納するデータのサイズによって、適切なサイズは変わってくるでしょう。下の設定がデフォルト値です。
vm-page-size 32
vm-pages 134217728
Redisは「ビットマップ」をメモリ中に保持しています。これは、連続したビット列で、ゼロかイチが格納されます。それぞれのビットは、スワップファイル中のページを表します。もし、1がセットされていれば、そのページは既に仕様されていて、Redisのオブジェクトが格納されています。ゼロがセットされている場合は、そのページは利用可能であることを表しています。
このビットマップ(ページテーブルと呼ばれます)をメモリ中に持つことで、パフォーマンスの面で優れていると同時に、メモリ使用量も押さえられた実装になっています。ページごとに1ビットしか必要でないため、デフォルトの32ビット、1.3億ページ(4GBのスワップ)が確保された場合でも、ページテーブルは16MBしかありません。
オブジェクトをメモリからディスクにスワップする場合は、次のステップで行われます。なお、この説明はブロック処理がシンプルな、スレッドを使わない仮想メモリを想定しています。
最後に、決まった位置にオブジェクトをディスクに書きこみます。これを行うのは vmWriteObjectOnSwap です。
オブジェクトがスワップファイルに正しく書き込まれると、メモリは解放されます。関連するキーの storage 属性には REDIS_VM_SWAPPED が設定され、 usedpages にはページテーブル内のページが書き込まれます。
スワップファイルからメモリにオブジェクトをロードする仕組みはシンプルです。スワップファイルのどこに、何ページ分保存されているかということは既にわかっています。また、オブジェクトの種類(ディスク上にはこの情報は保存されていないため、ロードする関数はこれを知っている必要がある)を知る必要がありますが、これも上記の構造体の vtype 属性に保存されています。
key オブジェクトを渡して vmLoadObject 関数を呼べば、ロードは完了します。この関数の中では、保存場所の情報の修正をしたり(REDIS_VM_MEMORY になる)、ページテーブルを解放したりします。
この関数の返り値はロードされたRedisオブジェクトそのものであり、スワップされたときに NULL に設定されたメインのハッシュテーブルに設定しなければなりません。
これまでのところで、仮想メモリの動作のブロッキングに必要な材料がそろいました。まず最初に設定の重要なところを紹介します。仮想メモリのブロッキングを有効にするには、Redisサーバの vm_max_threads をゼロに設定する必要があります。スレッド対応の仮想メモリの時に、どのようにこの最大スレッド数の設定が使用されるかは、この後で説明します。この値をゼロにすることで、完全なブロッキングを行う仮想メモリとして動作します。
もうひとつの重要な仮想メモリの属性として、 vm_max_memory があります。このパラメータはスワップのトリガーを設定するために重要となります。Redisは、このメモリの設定値を超えたメモリを使用した場合にのみ、スワップを行おうとします。この値に到達しない場合は、スワップの必要はないものとして動作します。
メモリからディスクへのスワップは、 cron 関数の中で行われます。現在のバージョンではこの関数は毎秒呼び出されますし、git上の最新バージョンでは100ミリ秒(1秒に10回)呼ばれます。この関数の中で、メモリ使用量の限界(vm-max-memory の設定値)を超えたことが検知されると、ループの中で vmSwapOneObect を呼び出して、ディスクへの移動を行います。この関数は1つ引き数を取りますが、もし0を渡すと、ブロッキングした状態でスワップを行います。1が設定されると、I/Oスレッドがしようされます。このブロッキング仮想メモリの説明の中では、0が渡されたものとして話を進めます。
vmSwapOneObject は次のように動作します。
この関数は次の状態になるまで繰り返し呼ばれます。
スワップする候補を選ぶロジックの理解は難しくありません。いくつかのオブジェクトをランダムでサンプリングし、それぞれの swappability 値を次のように計算します。
swappability = age*log(size_in_memory)
age は最後にアクセスされてからの秒数です。 size_in_memory はオブジェクトが利用している、メモリのバイト数です。アクセスされる頻度が少なく、大きいオブジェクトほど、スワップされやすくなります。ただし、logをとっているため、大きさの重みは小さくなっています。サイズの大きなオブジェクトを読み書きすることは、I/OやCPUに負荷をかけるので、あまり転送したくはないためです。
スワップされたオブジェクトを持つキーに対する命令が発行された場合、どのようなことが行われるのでしょうか？例えば、次のような操作が行われる可能性があります。
GET foo
foo キーの値オブジェクトがスワップされている場合、操作を実行する前に、メモリにロードし直す必要があります。Redisのキー探索の処理は、 lookupKeyRead と、 lookupKeyWrite の2つの関数に集約されています。これらの関数は、キー空間にアクセスするすべてのRedisコマンドの実装の中から使用されています。そのため、スワップファイルからメモリにロードする処理も、この場所で行われます。
次のようなことが行われます。
この場合は極めて素直な処理になっていますが、スレッドが絡んでくると、もっと動きが楽しくなってきます。ブロッキング仮想メモリの観点で見ると、 BGSAVE や、 BGREWRITEAOF コマンドなどにより、データセットが別のプロセスから保存されることだけが注意すべきことになります。
Redisはデフォルトでは、子プロセスを使って、ディスク上に .rdb ファイルを作って、保存をします。Redis()は fork システムコールを呼び出して子プロセスを作ります。このとき、プログラムのメモリ空間が複製されます。(実際には、copy on writeと呼ばれる技術により、親プロセスと子プロセスの間ではメモリが共有されるため、forkが使用するメモリは2倍にはなりません。)
子プロセスでは、forkされたタイミングでのデータセットのコピーを持っています。クライアントから何かコマンドを受け取って、親プロセスが処理を行ったとしても、子のデータは変更されません。
子プロセスはすべてのデータセットを、 dump.rdb ファイルにダンプして終了します。もし仮想メモリがアクティブになっている場合、何が起きるのでしょうか？値がスワップされているため、すべてのデータがメモリに格納されているわけではありません。そのため、スワップされた値を読み込むためには、スワップファイルにアクセスしなければなりません。
同じスワップファイルに同時にアクセスする問題を避けるために、Redisではバックグラウンドセーブを行っているあいだは、親プロセスが値をスワップアウトすることを許可しない、というシンプルな方法を採用しています。この場合、両方のプロセスは、読み込み専用でのアクセスすることになります。このアプローチでは、子プロセスが保存をしているあいだは、親プロセスが一時的に最大メモリ使用量のパラメータ以上のメモリを使用してしまう可能性がある、という問題があります。ですが、バックグラウンドのセーブは短時間で終了されるため、あまり問題になりませんし、スワップが必要であれば、すぐにスワップが行われるでしょう。
追記専用ファイルモードを有効にしていると、 BGREWRITEAOF コマンドを実行して、ログの再書き込みをしている場合にのみ、この問題が起きる可能性があります。
ブロッキング仮想メモリの問題は・・・ブロッキングすることです :) これは、Redisをバッチプロセスに対して使用している場合には問題になりませんが、遅延時間が少ないことが要求される場面で、リアルタイムにどんどん処理を行うようなRedisサーバを運用している場合は、問題となるでしょう。ブロッキング仮想メモリは、クライアントがスワップされた値にアクセスする命令が送ったり、Redisが値をスワップする必要がある場合、他のクライアントに対するサービスが止まるため、非常に処理が遅くなります。
スワップはバックグラウンドで行われるべきです。また、スワップされた値にアクセスされている時に、他のクライアントからメモリ上にある値へのアクセスが行われても、仮想メモリがオフになっているときと同じぐらい高速で行われるべきです。スワップされたキーに対するアクセスがあったときの遅延だけが許されます。
このような制約をすべて回避したいですよね？ ノンブロッキング仮想メモリ実装の出番です。
ブロッキング仮想メモリを、ノンブロッキング仮想メモリにするには、主に次の3通りの方法があります。
スレッド化された仮想メモリは、次のような目標を掲げて設計されました。重要度順になっています。
このような目標を目指して実装したところ、Redisのメインスレッドと、I/Oスレッドがキューと、1つのミューテックスを使ってジョブのやりとりをする、という実装になりました。基本的には、メインスレッドが、バックグラウンドのI/Oスレッドにお願いしたい仕事を持った場合、I/Oジョブ構造体を、 server.io_newjobs キュー(単なるリンクドリスト)に積みます。アクティブなI/Oスレッドがなければ、スレッドを起動します。この時に、I/OスレッドがI/Oジョブを処理して、 server.io_processed キューに結果を積みます。I/Oスレッドは、UNIXパイプにデータを送ることによって、メインスレッドに対して新しいジョブが実行され、処理が終わったことを通知します。
iojob 構造体は次のような実装になっています。
typedef struct iojob {
int type; /* リクエストタイプ, REDIS_IOJOB_* */
redisDb *db;/* Redisデータベース*/
robj *key; /* どのキーをスワップするI/Oリクエストか？ */
robj *val; /* REDIS_IOREQ_*_SWAPコマンドによって処理される値オブジェクト。
* もしくは、REDIS_IOREQ_LOADの処理を行うI/Oスレッド
* がこの変数に値を設定する。 */
off_t page; /* オブジェクトの読み/書きを行うページ番号 */
off_t pages; /* オブジェクトを保存するのに必要なページ数。PREPARE_SWAPの返り値 */
int canceled; /* ブロッキング仮想メモリが処理をキャンセルしたいときに、
* 値を設定する。 */
pthread_t thread; /* このエントリーを処理する、スレッドのID */
} iojob;
I/Oスレッドによって実行可能なジョブは、次の3種類あります。これは type 属性で設定されます。
メインスレッドは、上記の3つのタスクだけを委譲します。スワップファイルの格納する場所を探したり、スワップするオブジェクトを決定したり、Redisオブジェクトの storage 属性の値に、現在の状態を反映したりといった残りの処理はすべてメインスレッド自身が行います。
ここまでのところで、処理の重い仮想メモリの操作を、バックグラウンドジョブとして処理できるようになりました。どのようにして、メインスレッドで行う他の処理と歩調を合わせて行くのでしょうか？ブロッキング仮想メモリの場合、検索している時にオブジェクトがスワップアウトされていることに気づきますが、これでは遅すぎます。C言語では、コルーチンや継続がないため、コマンド処理の途中でバックグラウンドのジョブを起動して、関数の実行を中断し、I/Oスレッドの処理が終わったタイミングで中断したポイントから処理を再開するということは簡単ではありません。
再話、もっと簡単な方法がありました。私たちはシンプルな方が好きです。仮想メモリの実装は、基本的にブロッキング仮想メモリと考えますが、ブロッキングが発生していないように見えるように最適化します。
行っていることは次の通りです。
スワップされた値を使うコマンドが発生すると、値がロードされるまではクライアントの動作が一時停止するため、正しいキーがメモリ上置かれているブロッキング仮想メモリとほぼ同じように考えることができます。
どの引き数がキーかを調べる関数が失敗しても問題はありません。ルックアップの関数は与えられたキーの値がスワップされていることを気づいて、ブロックしてそれをロードしにいきます。そのため、利用しようとしたキーが利用できない場合には、ブロッキング仮想メモリに戻ります。
たとえば、 GET や BY オプション付きの SORT コマンドの場合、どのキーが必要となるかを事前に把握することが困難なため、少なくとも最初の実装では、 SORT BY/GET の実行はブロッキング仮想メモリとして実行されます。
どのようにクライアントをブロックしているのでしょうか？サーバ上のイベントループで、クライアントを一時停止させるのはとても簡単です。読み込みハンドラをキャンセルします。例えば、 BLPOP のようなコマンドの場合は、これとは異なり、新しいデータを処理(新しいデータを入力バッファ積む)するのではなく、単にブロックしているとクライアントにマークを付けるだけの場合もあります。
ブロッキング仮想メモリと、ノンブロッキング仮想メモリの間でインタラクションすることは、簡単ではありません。ノンブロッキング命令と、ブロッキング命令が同じキーに対して同時に発生すると何が起きるでしょうか？
例えば、 SORT BY が実行されていると、いくつかのキーは SORT コマンドの流儀に従って、ブロッキング仮想メモリの仕組みをつかってロードされます。これと同時に、同じキーに対して、値をスワップからロードする場合にI/Oジョブを作って行う GET コマンドが他のクライアントから呼ばれたとします。
この問題を解決する唯一シンプルな方法は、メインスレッドからI/Oジョブをkillできるようにすることです。もしブロッキング仮想メモリキーをロードしたり、スワップしたい場合には、 REDIS_VM_LOADING や REDIS_VM_SWAPPING といったフラグを設定します。ここで、このキーに関するI/Oジョブをkillして、実行したいブロッキング操作を行います。
これは言うほど簡単ではありません。これを行おうとした瞬間、I/Oジョブは次の3つのうち、どれかの状態になります。
I/Oジョブは、 vmCancelThreadedIOJob を使ってkillすることができます。