Redis の辞書、ハッシュアルゴリズム、ReHash 原理に関する簡単な説明-Redis-php.cn

Redis の辞書、ハッシュアルゴリズム、ReHash 原理に関する簡単な説明

青灯夜游

リリース： 2021-11-05 10:31:56

転載

2560 人が閲覧しました

この記事では、Redis の辞書、ハッシュアルゴリズム、ReHash 原理について紹介します。

Redis の辞書、ハッシュアルゴリズム、ReHash 原理に関する簡単な説明

Redis のディクショナリは、データベースやハッシュキーなど、Redis のさまざまな機能を実装するために広く使用されています。

ディクショナリの基礎となる実装はハッシュテーブルです。各ディクショナリには 2 つのハッシュテーブルがあり、1 つは通常に使用され、もう 1 つは領域を拡張するためにリハッシュが使用されるときに使用されます。 [関連する推奨事項: Redis ビデオチュートリアル ]

ディクショナリ構造の定義

typedef struct dict {
	
	// 类型特定函数
	dictType *type;
	
	// 私有数据
	void *privdata;
	
	// 哈希表，两个元素
	dictht ht[2]
	
	// rehash时记录的索引下标，当没有rehash时，值为-1
	int rehashidx;

} dict;

ログイン後にコピー

==再ハッシュが実行されると、rehanadx は各インデックスを移行します。エントリデータは 1;==

このうち、ハッシュテーブル dicttht の構造は次のように定義されます。

typedef struct dictht {
	
	// 哈希表数组
	dictEntry **table;
	
	// 哈希表大小
	unsigned long size;
	
	// 哈希表大小掩码，用于计算索引值
	unsigned long sizenask;
	
	// 该哈希表已有节点的数量
	unsigned long uesd;

} dictht;

ログイン後にコピー

このうち、table は配列であり、配列の各要素はdictEntry 型のポインター。dictEntry 型には、キーと値のペアが格納されます。

ここでは、ハッシュ競合の問題を解決するために、ハッシュテーブルのノードがリンクリストによって接続されている、つまりチェーンアドレス方式であることもわかります。

ハッシュ競合とハッシュアルゴリズム

キーから値への高速アクセスを実現するために、Redis はハッシュテーブルを使用してすべてのキーと値のペアを保存します。 Key は Redis によって設定されたキーに対応し、value は値そのものではなく、特定の値を指すポインターに対応します。ハッシュテーブルを使用する最大の利点は、O(1) の時間計算量でキーと値のペアをすばやく見つけることができることです。しかし、これはハッシュテーブルであるため、必然的に ハッシュ競合 問題が発生します。

ハッシュの競合とは、2 つのキーのハッシュ値とハッシュバケットが計算されるときに、それらが偶然同じハッシュバケットに該当することを意味します。

Redis がハッシュの競合を解決する方法は、チェーンハッシュ、つまり zipper メソッド を使用することです。複数の要素が同じハッシュバケットを指す場合、リンクリストを使用して対応するデータを同じハッシュバケットに保存し、ポインタを使用して順番に接続します。

ハッシュアルゴリズム

新しいキーと値のペアが辞書に追加されると、プログラムはまずキーと値に基づいてハッシュ値とインデックスを計算する必要があります。値を指定し、新しいキーと値のペアを含むハッシュテーブルノードを、インデックス値に基づいてハッシュテーブル配列の指定されたインデックスに配置します。

reHash プロセス

ハッシュテーブルには、ハッシュテーブルに保存されるキーと値のペアの数を制御するための負荷係数があります。これを完了するには再ハッシュ操作が必要です。このうち、負荷率の計算式は次のとおりです。

// 负载因子 = 哈希表已保存的节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size

ログイン後にコピー

ハッシュテーブルの拡張および縮小の条件は次のとおりです。

サーバーは現在 BGSAVE コマンドを実行していないか、またはBGREWRITEAOF コマンド、およびハッシュテーブルの負荷係数は 1 以上です;
サーバーは現在 BGSAVE コマンドまたは BGREWRITEAOF コマンドを実行中であり、ハッシュテーブルの負荷係数は 1 以上です。 5 に等しい;

上記の条件のいずれかが満たされた場合、再ハッシュ処理が実行されます。

サーバーが BGSAVE または BGREWRITEAOF を実行している場合、Redis は現在のサーバープロセスの子プロセスを作成します。

リハッシュプロセスは、大きく 3 つのステップに分かれています。

より大きなスペースをハッシュテーブル 2 に割り当てます (たとえば、ハッシュテーブル 1 の現在のサイズの 2 倍);
ハッシュテーブル 1 のデータを再マップし、それをハッシュ In Table にコピーします。 2;
ハッシュテーブル 1 のスペースを解放します。

最初のステップで割り当てられたスペースのサイズは、現在の再ハッシュによって決まります。操作タイプと、現在のハッシュテーブル内のキーと値のペアの数によって決まります。

拡張操作が実行される場合、割り当てられる領域サイズは、(ハッシュテーブル内のキーと値のペアの数 * 以上の最初の 2^n 値です) 2);

現在のキーと値のペアの数が 4 であると仮定すると、8 は 2^3 に正確に等しいため、4 * 2 = 8 となります。これは、最初の値 2 に正確に等しいためです。 ^n なので、拡張スペースは 8 です。
縮小操作が実行される場合、割り当てられるスペースサイズは、(数値以上の最初の 2^n の値になります)ハッシュテーブル内のキーと値のペアの数);

Progressive reHash

多数のハッシュテーブルがある場合、すべてのハッシュテーブルがデータを一度にコピーすると、サーバーに影響を与える可能性があります。したがって、Redis は再ハッシュを複数回実行します。これがプログレッシブ再ハッシュです。

簡単に言うと、2 番目のステップでも、Redis はクライアントリクエストを通常どおり処理します。リクエストを処理するとき、ハッシュテーブル 1 の最初のインデックス位置から開始し、途中でこのインデックスを移動します。すべてのエントリ要素その位置のエントリがハッシュテーブル 2 にコピーされ、次のリクエストが行われると、次のインデックス位置のエントリがコピーされます。

これにより、一度に大量のコピーのコストが複数のリクエストを処理するプロセスに巧みに割り当てられ、時間のかかる操作が回避され、データへの高速アクセスが保証されます。