Eine kurze Diskussion über das Wörterbuch, den Hash-Algorithmus und das ReHash-Prinzip in Redis

Dieser Artikel wird Ihnen helfen, das Wörterbuch, den Hash-Algorithmus und das ReHash-Prinzip in Redis zu verstehen. Ich hoffe, er wird Ihnen hilfreich sein!

Wörterbücher in Redis werden häufig zur Implementierung verschiedener Funktionen von Redis verwendet, einschließlich Datenbanken und Hash-Schlüsseln.

Die zugrunde liegende Implementierung des Wörterbuchs ist eine Hash-Tabelle. Jedes Wörterbuch verfügt über zwei Hash-Tabellen, eine wird normalerweise verwendet und die andere wird verwendet, wenn Rehash zum Erweitern des Speicherplatzes verwendet wird. [Verwandte Empfehlungen: Redis-Video-Tutorial]

Definition der Wörterbuchstruktur

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

} dict;

==Bei der Durchführung eines Rehashs sind die Eintragsdaten jedes von rehashidx migrierten Index + 1;==

Daunter die Hash-Tabelle Die Struktur von dicttht ist wie folgt definiert:

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

} dictht;

Unter diesen ist die Tabelle ein Array, jedes Element des Arrays zeigt auf einen Zeiger vom Typ dictEntry und der Typ dictEntry speichert ein Schlüssel-Wert-Paar.

Hier ist auch zu sehen, dass die Knoten der Hash-Tabelle durch verknüpfte Listen verbunden sind, um das Hash-Konfliktproblem zu lösen, bei dem es sich um die Kettenadressmethode handelt.

Hash-Kollision und Hash-Algorithmus

Um einen schnellen Zugriff vom Schlüssel zum Wert zu erreichen, verwendet Redis eine Hash-Tabelle, um alle Schlüssel-Wert-Paare zu speichern. Der Schlüssel entspricht dem von Redis festgelegten Schlüssel, und der Wertentspricht nicht dem Wert selbst, sondern dem Zeiger, der auf den spezifischen Wert zeigt. Der größte Vorteil der Verwendung einer Hash-Tabelle besteht darin, dass Sie schnell Schlüssel-Wert-Paare mit einer Zeitkomplexität von O(1) finden können. Da es sich jedoch um eine Hash-Tabelle handelt, wird es unweigerlich zu einem Problem eines Hash-Konflikts kommen.

Hash-Konflikt bedeutet, dass bei der Berechnung des Hash-Werts zweier Schlüssel und des Hash-Buckets diese zufällig auf denselben Hash-Bucket fallen.

Die Art und Weise, wie Redis Hash-Konflikte löst, ist die Verwendung von Ketten-Hashing, der Zipper-Methode. Wenn mehrere Elemente auf denselben Hash-Bucket verweisen, wird eine verknüpfte Liste verwendet, um die entsprechenden Daten im selben Hash-Bucket zu speichern, und sie werden wiederum mithilfe von Zeigern verbunden.

Hash-Algorithmus

Wenn dem Wörterbuch ein neues Schlüssel-Wert-Paar hinzugefügt wird, muss das Programm zuerst den Hash-Wert und den Indexwert basierend auf dem Schlüssel-Wert-Paar und dann basierend auf dem Indexwert berechnen neuer Schlüssel wird eingefügt. Der Hash-Tabellenknoten des Wertepaares wird am angegebenen Index im Hash-Tabellen-Array platziert.

reHash-Prozess

In der Hash-Tabelle gibt es einen Ladefaktor, um die Anzahl der in der Hash-Tabelle gespeicherten Schlüssel-Wert-Paare zu steuern. Hierzu ist ein erneuter Aufbereitungsvorgang erforderlich. Darunter lautet die Berechnungsformel des Auslastungsfaktors:

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

Die Bedingungen für die Erweiterung und Kontraktion der Hash-Tabelle lauten wie folgt:

• Der Server führt derzeit nicht den Befehl BGSAVE oder BGREWRITEAOF aus und der Auslastungsfaktor des Hash Tabelle ist größer oder gleich 1;
• Server Der BGSAVE-Befehl oder der BGREWRITEAOF-Befehl wird gerade ausgeführt und der Auslastungsfaktor der Hash-Tabelle ist größer oder gleich 5;

Wenn eine der oben genannten Bedingungen zutrifft erfüllt, wird der Rehash-Prozess ausgeführt.

Wenn der Server BGSAVE oder BGREWRITEAOF ausführt, erstellt Redis einen untergeordneten Prozess des aktuellen Serverprozesses.

Der Rehash-Prozess ist grob in drei Schritte unterteilt:

• Weisen Sie der Hash-Tabelle 2 größeren Speicherplatz zu, z aktuelle Hash-Tabelle Doppelt so groß wie Hash-Tabelle 1;

• Die Daten in Hash-Tabelle 1 neu zuordnen und in Hash-Tabelle 2 kopieren; Die Größe des Schrittzuordnungsraums wird durch den aktuellen Rehash-Operationstyp und die Anzahl der Schlüssel-Wert-Paare in der aktuellen Hash-Tabelle bestimmt.

• Wenn eine Erweiterungsoperation ausgeführt wird, ist die zugewiesene Speicherplatzgröße der erste 2^n-Wert, der größer oder gleich ist (die Anzahl der Schlüssel-Wert-Paare in der Hash-Tabelle * 2);

Angenommen, die Die aktuelle Anzahl der Schlüssel-Wert-Paare beträgt 4, dann ist 4 * 2 = 8, weil 8 genau gleich 2^3 ist, was genau gleich dem ersten Wert gleich 2^n ist, also ist der Erweiterungsraum 8;

Wenn eine Verkleinerungsoperation ausgeführt wird, ist die Größe des zugewiesenen Speicherplatzes der erste 2^n-Wert, der größer oder gleich ist (die Anzahl der Schlüssel-Wert-Paare in der Hash-Tabelle);

• Progressiver ReHash

• Wenn die Anzahl der Hash-Tabellen groß ist und alle Daten auf einmal kopiert werden, ist es sehr wahrscheinlich, dass dies Auswirkungen auf den Server hat. Daher führt Redis die Aufbereitung mehrmals durch, also eine progressive Aufbereitung. Einfach ausgedrückt: Im zweiten Schritt verarbeitet Redis die Client-Anfrage immer noch normal, beginnend mit der ersten Indexposition in der Hash-Tabelle 1. Das Eintragselement wird bei der nächsten Anfrage in die Hash-Tabelle 2 kopiert vorgenommen, werden die Einträge an der nächsten Indexposition kopiert. Auf diese Weise wird der Overhead einer großen Anzahl von Kopien auf einmal geschickt kopiert, der auf den Prozess mehrerer Verarbeitungsanforderungen angewendet wird, wodurch zeitaufwändige Vorgänge vermieden und ein schneller Zugriff auf Daten gewährleistet wird.

  Hash-Tabellenoperationen während der Aufbereitungsphase

  Während der progressiven Aufbereitungsoperation werden Wörterbuchlöschung, Suche, Aktualisierung und andere Vorgänge in zwei Hash-Tabellen durchgeführt. Wenn Sie beispielsweise einen Schlüssel im Wörterbuch finden möchten, fragen Sie ihn zunächst in der Originaltabelle ab. Wenn er nicht gefunden wird, fragen Sie ihn in der neuen Tabelle ab. Das Hinzufügen des Wörterbuchs bleibt nur in der neuen Tabelle erhalten.

  Weitere Kenntnisse zum Thema Programmierung finden Sie unter:

  Einführung in die Programmierung

  ! !

Das obige ist der detaillierte Inhalt vonEine kurze Diskussion über das Wörterbuch, den Hash-Algorithmus und das ReHash-Prinzip in Redis. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!