[Hashing consistente] Go implementa hash consistente basado en nodos virtuales.

El algoritmo de hash consistente se utiliza principalmente en sistemas distribuidos, especialmente cachés, para resolver problemas como equilibrio de carga, puntos de acceso y sesgo de datos.

El nodo del servidor se asigna a un anillo más largo. Al buscar datos, los datos clave del nodo del servidor adyacente se buscan en el sentido de las agujas del reloj en el anillo y, finalmente, los datos de origen se encuentran en el nodo del servidor. .

1. Coge un anillo como anillo de hachís.

La longitud suele ser 2 elevado a 32 (4.294.967.296), que es el rango de valores de int32.

2. Después de configurar la regla hash, el rango de valores del resultado hash debe coincidir con la longitud del anillo hash. Por ejemplo, si la longitud del anillo hash es 2 elevado a la 32.ª potencia, se utiliza la regla CRC32; el número de ranuras de Redis-Cluster es 2 elevado a la 14.ª potencia (16384), se utiliza la regla CRC16.

3. Utilice reglas de hash para aplicar hash al nodo del servidor Node. Por ejemplo, CRC32 aplica un hash a la IP, el nombre de host, etc. del nodo del servidor.

4. El resultado de la operación hash, la longitud del anillo hash de la parte restante de la operación y luego la parte restante se asigna al anillo hash.

5. Realice un hash CRC32 en la clave para encontrar los datos, realice una operación de resto de hash en la longitud del anillo hash y luego busque nodos adyacentes en el sentido de las agujas del reloj. (Palabras clave como ID de usuario en la tabla de usuarios)

Si el número de nodos es relativamente pequeño, la suposición extrema es que hay dos nodos, uno de los cuales tiene el valor hash del nodo A y es 0 y el valor hash del otro nodo B. El valor es 10 y la longitud general del anillo hash es generalmente bastante larga (como el rango int32). El resultado es que A carga el valor máximo de 11 ~ int32. pero solo carga 1 ~ 10.

Si agrega un nuevo nodo C con un valor hash de 3000000000, entonces el número de nodos correspondientes a 11 ~ 3000000000 es muy grande, por lo que el número de nodos en el mismo rango es el número de nodos. 000.000.000 corresponde a una cantidad tan grande de datos que se migrarán de A a C.

Si agrega un nuevo nodo C con valor hash

, el nuevo nodo solo compartirá la carga de un nodo, no de todos los demás.

Cuantos más nodos haya, más uniforme será la distribución.

Cuanto más cerca esté la carga del equilibrio, menor será la desviación en los datos.

Si no hay nodos reales, puedes añadir nodos virtuales.

Como resultado, surgió un hash consistente basado en nodos virtuales.

De acuerdo con el principio de Dimmler, la siguiente interfaz se abstrae

El nodo real Nodo, como tipo de valor.

Un nodo virtual se asociará con un nodo real mediante un mapa. El índice del segmento RingIndexs es el ID del nodo virtual.

Hashing consistente basado en nodos virtuales.

Debido a que el rango de hash del algoritmo es el rango de longitud del anillo, no equilibra math.MaxInt32.

Algoritmo de clasificación rápida, complejidad temporal: O (NlogN), N es el número de nodos virtuales

Cuando se agrega un nuevo nodo, se creará automáticamente un nodo virtual; se elimina Cuando se conecta un nodo, todos los nodos virtuales correspondientes al nodo se desconectarán automáticamente.

Y después de modificar el nodo, reorganiza los valores hash de todos los nodos virtuales.

Utilice el algoritmo de reducción a la mitad para encontrar nodos.

Verifique si la adquisición de nodos es correcta y si las operaciones de agregar y eliminar nodos son correctas.

No parece haber ningún problema con ordenar, agregar nodos, eliminar nodos y obtener nodos.