Redis ハッシュ テーブル スキャンの説明:メカニズムの内部

エフド・タミル著

ソフトウェア開発者としての私にとって大きな課題の 1 つは、他の人のコードを読むことです。この記事では、これまで知らなかった興味深い C コードを読みましたので、それを紹介したいと思います。これから説明するコードはRedis の一部です。 データベースはここにあります。

Redis はキーと値のデータベースです。データベース内のすべてのエントリは、キーから値へのマッピングです。値にはいくつかのタイプがあります。整数、リスト、ハッシュ テーブルなどがあります。舞台裏では、データベース自体もハッシュ テーブルです。この投稿では、Redis の SCAN コマンドについて説明します。

_By © ユーザー:Colin / ウィキメディア コモンズ、CC BY-SA 4.0、 [https://commons.wikimedia.org/w/index.php?curid=30343877](https://commons.wikimedia.org/w/index.php?curid=30343877" rel="noopener" target="blank" title=")

Redis スキャン

SCAN はカーソルベースの反復コマンドであり、クライアントがテーブル内のすべての要素を調べることができます。このカーソルベースのスキャナは、 整数のカーソルを受け入れます。 呼び出しごとに、アイテムのバッチを返します。 とカーソル値 SCAN への次の呼び出しで使用されます。初期のカーソル値は 0 で、SCAN が次のカーソル値として 0 を返した場合、スキャンが完了し、すべての要素がクライアントに認識されたことを意味します。

SCAN コマンドには、いくつかの興味深いプロパティがあります。

<オル>

テーブル内に存在するすべての項目が少なくとも 1 回返されることが保証されます。 .

ステートレスです 。テーブルには、アクティブなスキャナに関するデータは保存されません。これは、スキャンによってデータベースがロックされないことも意味します。

テーブルのサイズ変更に強いです。 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 ハッシュ テーブルは増分的に再ハッシュします。 これは、テーブル全体を一度に再ハッシュするのではなく、少しずつ再ハッシュすることを意味します。テーブルに対して実行される追加、削除、検索などのすべての操作では、再ハッシュ ステップも実行されます。これにより、再ハッシュ中にテーブルを操作に使用できる状態に保つことができます。再ハッシュの実装方法により、再ハッシュ中の関数の動作が異なります。まず、テーブルが再ハッシュされていないときに何が起こるかを見ていきます。

ハッシュ テーブルへのポインタはローカル変数 t0 に保存されます。 とそのサイズマスクについて。 m0 に保存されます 。 マスクのサイズ: dict.c ハッシュ テーブルは常に 2^n です。 サイズ的には。特定のテーブル サイズの場合、サイズ マスクは 2^n-1 です。 、n を持つ 2 進数です。 最下位ビットは 1 に設定されます。たとえば、n=4; 2^n-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 は、table. v & のインデックス付け可能な範囲外にある可能性があります。 m0 はサイズ マスクを使用して、las のみを保持します。 t n 桁 o f v を返し、テーブルへの有効なインデックスを生成します。

bucketfn が何かはもうお分かりいただけたかもしれません のためのものです。 bucketfn 呼び出し元によって提供され、要素の各バケットに適用されます。 privdata も渡されます。 、これは dictScan() に渡される任意のデータです。 発信者によって。同様に、fn バケット内のすべてのエントリに 1 つずつ適用されます。バケットが空の場合もあり、その場合の値は NULL であることに注意してください。 .

OK、要素のバケツを反復処理しました。次は何でしょうか？次の呼び出しのカーソル値を 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 に設定します 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 に感謝します。

無料でコーディングを学びましょう。 freeCodeCamp のオープンソース カリキュラムは、40,000 人以上の人々が開発者としての職に就くのに役立ちました。始めましょう