Redisのハッシュテーブルスキャン徹底解説――内部メカニズムをソースコードで読み解く

執筆：Ehud Tamir

ソフトウェア開発者にとって大きな課題の一つが「他人のコードを読むこと」です。本記事では、私がこれまで知らなかった興味深いC言語のコードを読み解き、その内容を皆さんに紹介します。取り上げるのはRedisデータベースの一部として実装されているコードです。

Redisはキーバリュー型データベースであり、データベース内のすべてのエントリはキーから値へのマッピングになっています。値には整数、リスト、ハッシュテーブルなど複数の型があります。そして実は、データベース本体も内部的にはハッシュテーブルで構成されています。この記事では、RedisのSCANコマンドについて掘り下げていきます。

RedisのSCANコマンドとは

SCANはカーソルベースのイテレーションコマンドで、クライアントがテーブル内のすべての要素を走査できるようにするものです。このカーソルベースのスキャナは、呼び出しごとに整数のカーソルを受け取り、要素のバッチと、次回のSCAN呼び出しで使用するカーソル値を返します。初期カーソル値は0で、SCANが次のカーソル値として0を返した場合、スキャンが完了し、すべての要素がクライアントに返されたことを意味します。

SCANコマンドには、いくつかの興味深い特性があります。

1. テーブルに存在するすべての要素が少なくとも1回は返されることが保証されています。
2. ステートレス（状態を持たない）であること。テーブル側はアクティブなスキャナに関する情報を一切保存しません。これはまた、スキャンがデータベースをロックしないことも意味します。
3. テーブルのリサイズに対して耐性があること。O(1)のアクセス時間を維持するため、ハッシュテーブルは一定の負荷率（ロードファクター）を保ちます。負荷率は、ある時点でテーブルがどれほど「満杯」かを測る指標です。負荷率が大きすぎたり小さすぎたりすると、テーブルはリサイズされます。SCANは、テーブルのリサイズ中に呼び出された場合でも、これらの保証を維持します。

実装の詳細

SCANはdict.cの中のdictScan()関数として実装されています。以下がその関数シグネチャと、冒頭の前処理部分です。

unsigned long dictScan(dict *d,
 unsigned long v,
 dictScanFunction *fn,
 dictScanBucketFunction* bucketfn,
 void *privdata)
{
 dictht *t0, *t1;
 const dictEntry *de, *next;
 unsigned long m0, m1;
 if (dictSize(d) == 0) return 0;
 // ...

注目すべきポイントは以下の通りです。

• 関数は5つの引数を受け取ります。スキャン対象の辞書dict *d、カーソルunsigned long v、そして後ほど説明するその他3つのパラメータです。
• 戻り値は、次回この関数を呼び出す際に使用するカーソル値です。0が返された場合はスキャン完了を意味します。
• if (dictSize(d) == 0) return 0; ―― 辞書が空の場合、スキャン完了を示すために0を返します。

1. 通常時のスキャン処理

以下のコードが、一連の要素をスキャンする部分です。

if (!dictIsRehashing(d)) {
 t0 = &(d->ht[0]);
 m0 = t0->sizemask;
 /* Emit entries at cursor */
 if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
 de = t0->table[v & m0];
 while (de) {
 next = de->next;
 fn(privdata, de);
 de = next;
 }
 /* Set unmasked bits so incrementing the reversed cursor
 * operates on the masked bits */
 v |= ~m0;
 /* Increment the reverse cursor */
 v = rev(v);
 v++;
 v = rev(v);
} else {
 // ...

順を追って見ていきましょう。まずは冒頭の数行からです。

if (!dictIsRehashing(d)) {
 t0 = &(d->ht[0]);
 m0 = t0->sizemask;

リハッシュとは、テーブルがリサイズされた後に要素を均等に再配置する処理のことです。dict.cのハッシュテーブルはインクリメンタル（漸進的）にリハッシュを行います。つまり、テーブル全体を一度に再ハッシュするのではなく、少しずつ進めていくのです。追加・削除・検索など、テーブルに対するすべての操作のたびに、リハッシュのステップも1つ進められます。これにより、リハッシュ中もテーブルを通常どおり操作できる状態が保たれます。リハッシュの実装方法の都合上、この関数はリハッシュ中とそうでないときで挙動が異なります。まずは、リハッシュが行われていない場合の動作から見ていきます。

ハッシュテーブルへのポインタがローカル変数t0に格納され、そのサイズマスクがm0に保存されます。

サイズマスクについて：dict.cのハッシュテーブルは常に2^nのサイズを持ちます。テーブルサイズが与えられたとき、サイズマスクは2^n-1となり、これは下位nビットがすべて1のバイナリ数です。例えばn=4なら、2^4-1 = 00001111となります。あるキーのハッシュテーブル上の位置は、そのキーのハッシュ値の下位nビットによって決まります。この動作はすぐ後で実際に確認します。

dict.cのハッシュテーブルはチェイン法（オープンハッシング）を採用しています。テーブル内の各エントリは、同じハッシュ値を持つ要素をつないだ連結リストになっており、これをバケットと呼びます。次の部分では、要素のバケットをスキャンしています。

/* Emit entries at cursor */
if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
de = t0->table[v & m0];
while (de) {
 next = de->next;
 fn(privdata, de);
 de = next;
}

サイズマスクの使い方に注目してください：t0->table[v & m0]。カーソルvはテーブルのインデックス範囲外の値になる可能性があります。v & m0はサイズマスクを使ってvの下位nビットだけを残し、テーブルの有効なインデックスを導き出します。

もうお察しかもしれませんが、bucketfnは各バケットに対して適用されるコールバック関数で、呼び出し元から提供されます。同時に、呼び出し元がdictScan()に渡す任意のデータprivdataも渡されます。同様に、fnはバケット内のすべてのエントリに1件ずつ適用されます。なお、バケットは空の場合があり、その値はNULLになります。

さて、バケット内の要素を走査しました。次は何をするのでしょうか？　次回のdictScan()呼び出し用のカーソル値を返します。これは現在のカーソルvをインクリメントすることで行われますが、ここにひと工夫があります！　カーソルはまず反転され、次にインクリメントされ、そして再度反転されるのです。

 /* Set unmasked bits so incrementing the reversed cursor
 * operates on the masked bits */
 v |= ~m0;
 /* Increment the reverse cursor */
 v = rev(v);
 v++;
 v = rev(v);

まず、v |= ~m0によって、vのマスクされていないビット（上位ビット）がすべて1にセットされます。こうすることで、vを反転してインクリメントする際に、これらのビットが実質的に無視されるようになります。その後、vは反転→インクリメント→再反転されます。具体例を見てみましょう。

Table size = 16 (n = 4, m0 = 16-1 = 00001111)
v = 00001000 (Current cursor)
v |= ~m0; // v == 11111000 (~m0 = 11110000)
v = rev(v); // v == 00011111
v++; // v == 00100000
v = rev(v); // v == 00000100

このビット演算の魔法のあと、vが返されます。

なぜカーソルを反転してからインクリメントするのか？　それは、イテレーションの合間にテーブルが拡張される可能性があるためです。この手法により、カーソルの有効性が保証されます。テーブルが成長すると、サイズマスクには左側から新しいビットが追加されます。反転した数値をインクリメントすることで、小さいテーブルのインデックスを、より大きいテーブルのインデックスへと展開できるのです。

例を挙げましょう。旧テーブルのサイズが16（サイズマスク00001111）で、カーソルが00001000だったとします。テーブルが32要素に成長すると、サイズマスクは00011111になります。以前00001000スロットにあったすべての要素は、新テーブルでは00001000または00011000のいずれかにマッピングされます。つまり、これらのカーソルは小さいテーブルにも大きいテーブルにも両対応しているのです！

2. リハッシュ中のスキャン処理

最後に理解すべきは、テーブルがリハッシュ中のときにスキャンがどう動作するかです。インクリメンタルリハッシュは、dict.cでは2つのテーブルを同時にアクティブに保つことで実現されています。ハッシュテーブルがリサイズされると第2のテーブルが作成され、新しいアイテムは新テーブルに追加されます。リハッシュのステップごとに、旧テーブルから新テーブルへ要素が移動され、旧テーブルが空になった時点で削除されます。

スキャンを実行する際は、小さい方のテーブルから順に、新旧両方のテーブルが走査されます。小さいテーブルの要素をスキャンした後、大きいテーブルから対応する補完的な要素がスキャンされます。こうすることで、カーソルvがカバーするすべての要素が走査されるのです。コード全体を見てみましょう。以下で分解して説明します。

 } else { // dictIsRehashing(d)
 t0 = &d->ht[0];
 t1 = &d->ht[1];
 /* Make sure t0 is the smaller and t1 is the bigger table */
 if (t0->size > t1->size) {
 t0 = &d->ht[1];
 t1 = &d->ht[0];
 }
 m0 = t0->sizemask;
 m1 = t1->sizemask;
 /* Emit entries at cursor */
 if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
 de = t0->table[v & m0];
 while (de) {
 next = de->next;
 fn(privdata, de);
 de = next;
 }
 /* Iterate over indices in larger table that are the expansion
 * of the index pointed to by the cursor in the smaller table */
 do {
 /* Emit entries at cursor */
 if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
 de = t1->table[v & m1];
 while (de) {
 next = de->next;
 fn(privdata, de);
 de = next;
 }
 /* Increment the reverse cursor not covered by the smaller mask.*/
 v |= ~m1;
 v = rev(v);
 v++;
 v = rev(v);
 /* Continue while bits covered by mask difference is non-zero */
 } while (v & (m0 ^ m1));
 }

まず、t0とt1にそれぞれ小さい方と大きい方のテーブルが格納され、m0とm1にそれぞれのサイズマスクが設定されます。そして、先ほど見たのと同じ要領で小さいテーブルがスキャンされます。

次に、カーソルを使って大きいサイズマスクm1で大きいテーブルにインデックスアクセスします：de = t1->table[v & m1]。内側のループでは、カーソルをインクリメントしながら、小さいテーブルのインデックスのすべての展開形をカバーしていきます。

例えば、小さいテーブルでのバケットのインデックスが0100で、大きいテーブルが2倍のサイズだった場合、このループでカバーされるインデックスは00100と10100になります。do-whileの条件式while (v & (m0 ^ m1));は、カーソルが小さいテーブルのバケットがカバーする範囲を超えて進まないように防いでいます。この最後の仕組みの理解は、読者の皆さんへの宿題として残しておきますね :)

以上です！　ハッシュテーブルスキャン関数の全体を解説しました。残る謎はrev(v)の実装だけです。これは数値のビットを反転させる汎用関数ですが、dict.cで使われている実装はO(log n)の実行時間を達成しており、特に興味深いものです。これについては将来の記事で取り上げるかもしれません。

お読みいただきありがとうございました！　インスピレーションとサポートをくださったDvir Volkに心より感謝します。また、記事の誤りを修正するのに役立つフィードバックをくださったJason Liにも感謝します。