RedisにおけるRehashメカニズムの概要
5744 ワード
https://blog.csdn.net/cqk0100/article/details/80400811
周知のように、redisは複数のデータ構造をサポートし、dictは使用頻度がかなり高く、非常に実用的な構造である.redisの具体的な実装では,dictのスケーリング効率を向上させるために漸進的ハッシュというメカニズムが用いられており,この部分のソースコードを見ると,本当に優雅である.実は漸進的なハッシュに関する文章は少なくありませんが、自分で書くことにしました.考えを整理する一方で、印象を深めることができます.rehashの関数ボディを見る前に、dictのデータ構造がどのように定義されているかを見てみましょう.
dictの構造はほぼ上記のようになっています.次に、最も重要なデータ・メンバーを分析します.
dictht::table:ハッシュテーブル内部のtable構造はチェーンアドレス法を使ってハッシュ競合を解決していますが、最初見たときは不思議でしたが、これはどうして2次元配列なのでしょうか.これは実際には配列を指すポインタであり、配列の各項目はentryチェーンテーブルのヘッダノードである.dictht ht[2]:dictの内部で、2枚のハッシュテーブルを維持し、作用は1対のスクロール配列に等しく、1枚のテーブルは古いテーブルであり、1枚のテーブルは新しいテーブルであり、hashtableの大きさが動的に変化する必要がある場合、古いテーブルの要素は新しく開かれた新しいテーブルに移行し、次に大きさを変更し、現在の新しいテーブルはまた古いテーブルになり、これによって資源の多重化と効率の向上を達成する.rehashidx:漸進的なハッシュであり、データの移行は一歩では完了しないため、現在のrehashの進捗を示すインデックスが必要です.rehashidxが−1の場合、ハッシュ操作がないことを表す.次に、rehashのマスターセクション(githubの最新バージョンから直接取得)を見てみましょう.
関数の機能を理解するには、そのコメントが一番いいです.私たちは大体理解することができます.
rehashはbucket(バケツ)を基本単位として漸進的なデータ移行を行い、すべてのデータ移行が完了するまで各ステップで1つのbucketの移行を完了します.1つのbucketは、ハッシュテーブル配列のentryチェーンテーブルに対応します.新しいバージョンのdictRehash()には、最大アクセスバケツ数(empty_visits)の制限も追加され、ブロックを引き起こす可能性のある時間をさらに短縮します.
次に,この関数の具体的な実装を深く検討する.
dictがrehashingしているかどうかを判断し、そうでなければ、ハッシュプロセスを終了し、直接戻ります.次に、nステップに分けて進行する漸進的ハッシュ本体部分(nは関数パラメータから伝達される)についてwhileの条件に対を加える.used古いテーブルの残りの要素の数の観察は、セキュリティを増加させます.runtimeの断言は、漸進的なハッシュのインデックスが境界を越えていないことを保証します.次の小さなwhileは、空きバケツをスキップしながら、残りのアクセス可能な空きバケツの数を更新するためです.empty_visitsという変数の役割は前に述べた.現在のbucketに来て、次のwhile(de)でその中のすべての要素をht[1]に移行し、インデックス値はハッシュテーブルのサイズマスク計算を補助し、境界を越えないことを保証します.2つのテーブルの現在の要素の数を同時に更新しました.rehashが終了するたびに、インデックス値を増やし、古いテーブルで移行済みのbucketを空のポインタにします.最後に、古いテーブルがすべて移行したかどうかを判断します.もし、スペースを回収し、古いテーブルをリセットし、漸進的なハッシュのインデックスをリセットします.そうしないと、呼び出し元に戻り値で伝えます.dict内にはまだデータが移行していません.
プログレッシブハッシュの本質は、データの移行が一度に完了するのではなく、dictRehash()という関数によって段階的に計画され、呼び出し側がプログレッシブハッシュ操作を継続する必要があるかどうかをタイムリーに知ることができることにある.dictデータ構造に大量のデータが格納されている場合、一度の移行はredis性能の低下をもたらすに違いない.redisは単一スレッドモデルであり、リアルタイム性が要求されるシーンでは致命的であることを忘れないでください.プログレッシブハッシュは、dictが挿入、削除、更新されたときにdictRehash()を実行し、データ移行のコストを最小限に抑えることができるように、このコストを制御的に割り当てることができます.移行の過程で、データが新しいテーブルであるか古いテーブルであるかは非常に急迫した需要ではありません.移行の過程でデータが失われることはありません.古いテーブルで新しいテーブルを見つけることができなければ、新しいテーブルを探すことができません.だから後ろのdict関連の関数では、大量に見られます.
このようなコード.
最後に、「Redis設計と実装」のcopyからの図解です.incremental rehash全体のプロセスをよりイメージ的に理解するのに役立ちます.
redisの高性能の保障を総括していろいろな措置を取って、多くの優雅で驚くべき工事の技巧があって、とても私たちが学ぶ価値があります.ソースコードを読んでいるうちに、redisがメモリの管理が細かくなったのも、pure cのプロジェクトを久しぶりに見たのかもしれませんが、収穫は豊富です.みんなと一緒に進歩してほしい.
周知のように、redisは複数のデータ構造をサポートし、dictは使用頻度がかなり高く、非常に実用的な構造である.redisの具体的な実装では,dictのスケーリング効率を向上させるために漸進的ハッシュというメカニズムが用いられており,この部分のソースコードを見ると,本当に優雅である.実は漸進的なハッシュに関する文章は少なくありませんが、自分で書くことにしました.考えを整理する一方で、印象を深めることができます.rehashの関数ボディを見る前に、dictのデータ構造がどのように定義されているかを見てみましょう.
/* */
typedef struct dictEntry {
//
void *key;
//
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// ，
struct dictEntry *next;
} dictEntry;
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
/*
* ， rehash 。
*/
typedef struct dictht {
//
// ： ， entry （ ）
dictEntry **table;
//
unsigned long size;
// ，
// size - 1
unsigned long sizemask;
//
unsigned long used;
} dictht;
/* */
typedef struct dict {
//
dictType *type;
//
void *privdata;
//
dictht ht[2];
// rehash
// rehash ， -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
//
int iterators; /* number of iterators currently running */
} dict;dictの構造はほぼ上記のようになっています.次に、最も重要なデータ・メンバーを分析します.
dictht::table:ハッシュテーブル内部のtable構造はチェーンアドレス法を使ってハッシュ競合を解決していますが、最初見たときは不思議でしたが、これはどうして2次元配列なのでしょうか.これは実際には配列を指すポインタであり、配列の各項目はentryチェーンテーブルのヘッダノードである.dictht ht[2]:dictの内部で、2枚のハッシュテーブルを維持し、作用は1対のスクロール配列に等しく、1枚のテーブルは古いテーブルであり、1枚のテーブルは新しいテーブルであり、hashtableの大きさが動的に変化する必要がある場合、古いテーブルの要素は新しく開かれた新しいテーブルに移行し、次に大きさを変更し、現在の新しいテーブルはまた古いテーブルになり、これによって資源の多重化と効率の向上を達成する.rehashidx:漸進的なハッシュであり、データの移行は一歩では完了しないため、現在のrehashの進捗を示すインデックスが必要です.rehashidxが−1の場合、ハッシュ操作がないことを表す.次に、rehashのマスターセクション(githubの最新バージョンから直接取得)を見てみましょう.
/* Performs N steps of incremental rehashing. Returns 1 if there are still
* keys to move from the old to the new hash table, otherwise 0 is returned.
*
* Note that a rehashing step consists in moving a bucket (that may have more
* than one key as we use chaining) from the old to the new hash table, however
* since part of the hash table may be composed of empty spaces, it is not
* guaranteed that this function will rehash even a single bucket, since it
* will visit at max N*10 empty buckets in total, otherwise the amount of
* work it does would be unbound and the function may block for a long time. */
int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* Max number of empty buckets to visit. */
if (!dictIsRehashing(d)) return 0;
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht[0].used != 0 */
assert(d->ht[0].size > (unsigned long)d->rehashidx);
while(d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
de = d->ht[0].table[d->rehashidx];
/* Move all the keys in this bucket from the old to the new hash HT */
while(de) {
uint64_t h;
nextde = de->next;
/* Get the index in the new hash table */
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
/* Check if we already rehashed the whole table... */
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}
/* More to rehash... */
return 1;
}関数の機能を理解するには、そのコメントが一番いいです.私たちは大体理解することができます.
rehashはbucket(バケツ)を基本単位として漸進的なデータ移行を行い、すべてのデータ移行が完了するまで各ステップで1つのbucketの移行を完了します.1つのbucketは、ハッシュテーブル配列のentryチェーンテーブルに対応します.新しいバージョンのdictRehash()には、最大アクセスバケツ数(empty_visits)の制限も追加され、ブロックを引き起こす可能性のある時間をさらに短縮します.
次に,この関数の具体的な実装を深く検討する.
dictがrehashingしているかどうかを判断し、そうでなければ、ハッシュプロセスを終了し、直接戻ります.次に、nステップに分けて進行する漸進的ハッシュ本体部分(nは関数パラメータから伝達される)についてwhileの条件に対を加える.used古いテーブルの残りの要素の数の観察は、セキュリティを増加させます.runtimeの断言は、漸進的なハッシュのインデックスが境界を越えていないことを保証します.次の小さなwhileは、空きバケツをスキップしながら、残りのアクセス可能な空きバケツの数を更新するためです.empty_visitsという変数の役割は前に述べた.現在のbucketに来て、次のwhile(de)でその中のすべての要素をht[1]に移行し、インデックス値はハッシュテーブルのサイズマスク計算を補助し、境界を越えないことを保証します.2つのテーブルの現在の要素の数を同時に更新しました.rehashが終了するたびに、インデックス値を増やし、古いテーブルで移行済みのbucketを空のポインタにします.最後に、古いテーブルがすべて移行したかどうかを判断します.もし、スペースを回収し、古いテーブルをリセットし、漸進的なハッシュのインデックスをリセットします.そうしないと、呼び出し元に戻り値で伝えます.dict内にはまだデータが移行していません.
プログレッシブハッシュの本質は、データの移行が一度に完了するのではなく、dictRehash()という関数によって段階的に計画され、呼び出し側がプログレッシブハッシュ操作を継続する必要があるかどうかをタイムリーに知ることができることにある.dictデータ構造に大量のデータが格納されている場合、一度の移行はredis性能の低下をもたらすに違いない.redisは単一スレッドモデルであり、リアルタイム性が要求されるシーンでは致命的であることを忘れないでください.プログレッシブハッシュは、dictが挿入、削除、更新されたときにdictRehash()を実行し、データ移行のコストを最小限に抑えることができるように、このコストを制御的に割り当てることができます.移行の過程で、データが新しいテーブルであるか古いテーブルであるかは非常に急迫した需要ではありません.移行の過程でデータが失われることはありません.古いテーブルで新しいテーブルを見つけることができなければ、新しいテーブルを探すことができません.だから後ろのdict関連の関数では、大量に見られます.
if(dictIsRehashing(d))
_dictRehashStep(d); // rehashこのようなコード.
最後に、「Redis設計と実装」のcopyからの図解です.incremental rehash全体のプロセスをよりイメージ的に理解するのに役立ちます.
redisの高性能の保障を総括していろいろな措置を取って、多くの優雅で驚くべき工事の技巧があって、とても私たちが学ぶ価値があります.ソースコードを読んでいるうちに、redisがメモリの管理が細かくなったのも、pure cのプロジェクトを久しぶりに見たのかもしれませんが、収穫は豊富です.みんなと一緒に進歩してほしい.