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 にコピーされ、次のリクエストが行われると、次のインデックス位置のエントリがコピーされます。

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

リハッシュ時のハッシュテーブル操作

プログレッシブリハッシュ操作を実行する場合、ディクショナリの削除、検索、更新などの操作は 2 つのハッシュ テーブルで実行されます。たとえば、ディクショナリ内のキーを検索する場合は、まず元のテーブルでクエリを実行し、見つからない場合は新しいテーブルでクエリを実行します。

また、辞書の追加操作は新しいテーブルにのみ保存されます。

プログラミング関連の知識について詳しくは、プログラミング入門をご覧ください。 ！

以上がRedis の辞書、ハッシュ アルゴリズム、ReHash 原理に関する簡単な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。