El hashing consistente es una técnica de hashing que funciona muy bien cuando se opera en un entorno dinámico en el que el sistema distribuido aumenta y disminuye con frecuencia. El concepto central del hashing consistente fue introducido en el artículo Consistent Hashing and RandomTrees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, pero ganó popularidad tras el famoso artículo de presentación de DynamoDB – Dynamo: El almacén de valores clave de alta disponibilidad de Amazon. Desde entonces, el hashing consistente ha ganado tracción y ha encontrado un montón de casos de uso en el diseño y el escalado de sistemas distribuidos de manera eficiente. Los dos ejemplos famosos que utilizan exhaustivamente esta técnica son Bit Torrent, para sus redes peer-to-peer y Akamai, para sus cachés web. En este artículo nos adentraremos en la necesidad del Hashing Consistente, su funcionamiento interno y, lo que es más importante, lo implementaremos utilizando arrays y Binary Search.

Antes de adentrarnos en el núcleo de la técnica del Hashing Consistente, primero debemos aclarar algunas cosas, una de las cuales son las Funciones Hash. Las funciones Hash son cualquier función que mapea un valor de un dominio de tamaño arbitrario a otro de tamaño fijo, normalmente llamado espacio Hash. Por ejemplo, mapear URLs a enteros de 32 bits o contenido HTML de páginas web a una cadena de 256 bytes. Los valores generados como salida de estas funciones hash se utilizan normalmente como claves para permitir búsquedas eficientes de la entidad original.

Un ejemplo de función hash simple es una función que mapea un entero de 32 bits en un espacio hash de enteros de 8 bits. La función podría implementarse utilizando el operador aritmético modulo y podemos conseguirlo tomando un modulo 256 que arroje números en el rango ocupando 8 bits para su representación. Una función hash, que mapea claves a dicho dominio de enteros, suele aplicar el modulo N para restringir los valores, o el espacio hash, a un rango .

Una buena función hash tiene las siguientes propiedades

• La función es computacionalmente eficiente y los valores generados son fáciles de buscar
• La función, para la mayoría de los casos de uso general, se comporta como un generador pseudoaleatorio que reparte los datos uniformemente sin ninguna correlación notable

Ahora que hemos visto lo que es una función hash, echamos un vistazo a cómo podríamos utilizarlas y construir un sistema distribuido algo escalable.

Construyendo un sistema de almacenamiento distribuido

Supongamos que estamos construyendo un sistema de almacenamiento distribuido en el que los usuarios pueden subir archivos y acceder a ellos bajo demanda. El servicio expone las siguientes APIs a los usuarios

• upload para subir el archivo
• fetch para obtener el archivo y devolver su contenido

En el fondo el sistema tiene Nodos de Almacenamiento en los que se almacenan los archivos y se accede a ellos. Estos nodos exponen las funciones put_file y fetch_file que ponen y obtienen el contenido del archivo a/desde el disco y envían la respuesta al servidor principal de la API que a su vez lo devuelve al usuario.

Para sostener la carga inicial, el sistema tiene 5 Nodos de Almacenamiento que almacenan los archivos subidos de forma distribuida. El hecho de tener varios nodos asegura que el sistema, en su conjunto, no se vea desbordado y el almacenamiento se distribuya de forma casi uniforme.

Cuando el usuario invoca la función upload con la ruta del archivo, el sistema necesita primero identificar el nodo de almacenamiento que se encargará de guardar el archivo y esto lo hacemos aplicando una función hash a la ruta y obteniendo a su vez el índice del nodo de almacenamiento. Una vez que obtenemos el nodo de almacenamiento, leemos el contenido del archivo y ponemos ese archivo en el nodo invocando la función put_file del nodo.

# storage_nodes holding instances of actual storage node objectsstorage_nodes = def hash_fn(key): """The function sums the bytes present in the `key` and then take a mod with 5. This hash function thus generates output in the range . """ return sum(bytearray(key.encode('utf-8'))) % 5def upload(path): # we use the hash function to get the index of the storage node # that would hold the file index = hash_fn(path) # we get the StorageNode instance node = storage_nodes # we put the file on the node and return return node.put_file(path)def fetch(path): # we use the hash function to get the index of the storage node # that would hold the file index = hash_fn(path) # we get the StorageNode instance node = storage_nodes # we fetch the file from the node and return return node.fetch_file(path)

La función hash utilizada aquí simplemente suma los bytes y toma el módulo por 5 (ya que hay 5 nodos de almacenamiento en el sistema) y así genera la salida en el espacio hash . Este valor de salida representa ahora el índice del motor de almacenamiento que se encargará de albergar el fichero.

Si tenemos 5 ficheros ‘f1.txt’, ‘f2.txt’, ‘f3.txt’, ‘f4.txt’, ‘f5.txt’ si aplicamos la función hash a estos encontramos que están almacenados en los nodos de almacenamiento E, A, B, C y D respectivamente.

Las cosas se ponen interesantes cuando el sistema gana algo de tracción y necesita ser escalado a 7 nodos, lo que significa que ahora la función hash debe hacer mod 7 en lugar de un mod 5. Cambiar la función hash implica cambiar el mapeo y la asociación de los archivos con los nodos de almacenamiento. Primero tenemos que administrar las nuevas asociaciones y ver qué ficheros hay que mover de un nodo a otro.

Con la nueva función hash los mismos 5 ficheros ‘f1.txt’, ‘f2.txt’, ‘f3.txt’, ‘f4.txt’, ‘f5.txt’ estarán ahora asociados a los nodos de almacenamiento D, E, F, G, A. Aquí vemos que el cambio de la función hash requiere que movamos cada uno de los 5 archivos a un nodo diferente.

Si tenemos que cambiar la función hash cada vez que aumentamos o disminuimos la escala y si esto requiere que movamos no todos sino incluso la mitad de los datos, el proceso se vuelve súper caro y a largo plazo inviable. Así que necesitamos una forma de minimizar el movimiento de datos requerido durante los aumentos o disminuciones de escala, y aquí es donde encaja el Hashing Consistente y minimiza la transferencia de datos requerida.

Hashing Consistente

El mayor punto de dolor del sistema anterior es que es propenso a eventos como aumentos y disminuciones de escala ya que requiere una gran cantidad de alteraciones en las asociaciones. Estas asociaciones son puramente impulsadas por la función Hash subyacente y, por lo tanto, si de alguna manera pudiéramos hacer esta función hash independiente del número de nodos de almacenamiento en el sistema, resolveríamos este defecto.

Consistent Hashing aborda esta situación manteniendo el espacio Hash enorme y constante, en algún lugar del orden de y el nodo de almacenamiento y los objetos se asignan a una de las ranuras en este enorme espacio Hash. Al contrario que en el sistema tradicional, en el que el archivo se asociaba con el nodo de almacenamiento en el índice en el que se hacía el hash, en este sistema las posibilidades de colisión entre un archivo y un nodo de almacenamiento son infinitamente pequeñas y, por lo tanto, necesitamos una forma diferente de definir esta asociación.

En lugar de utilizar un enfoque basado en la colisión, definimos la asociación como – el archivo se asociará con el nodo de almacenamiento que esté presente a la derecha inmediata de su ubicación hash. Definir la asociación de esta manera nos ayuda a

• mantener la función hash independiente del número de nodos de almacenamiento
• mantener las asociaciones relativas y no impulsadas por colisiones absolutas

El Hashing Consistente en promedio requiere sólo k/n unidades de datos para ser migrados durante la ampliación y reducción de la escala; donde k es el número total de claves y n es el número de nodos del sistema.

Una forma muy ingenua de implementar esto es asignando un array de tamaño igual al Hash Space y poniendo los archivos y el nodo de almacenamiento literalmente en el array en la ubicación del hash. Para obtener la asociación iteramos desde la ubicación hash del ítem hacia la derecha y encontramos el primer Nodo de Almacenamiento. Si llegamos al final del array y no encontramos ningún Nodo de Almacenamiento, volvemos al índice 0 y continuamos la búsqueda. El enfoque es muy fácil de implementar, pero sufre de las siguientes limitaciones

• requiere una gran cantidad de memoria para mantener una matriz tan grande
• encontrar la asociación iterando cada vez hacia la derecha es O(hash_space)

Una mejor manera de implementar esto es mediante el uso de dos arrays: uno para mantener los Nodos de Almacenamiento, llamado nodes y otro para mantener las posiciones de los Nodos de Almacenamiento en el espacio hash, llamado keys. Hay una correspondencia uno a uno entre las dos matrices – el Nodo de Almacenamiento nodes está presente en la posición keys en el espacio hash. Ambas matrices se mantienen ordenadas según la matriz keys.

Función Hash en Consistentes Hashing

Definimos total_slots como el tamaño de todo este espacio hash, típicamente del orden 2^256 y la función hash podría implementarse tomando SHA-256 seguido de un mod total_slots. Dado que total_slots es enorme y una constante, la siguiente implementación de la función hash es independiente del número real de Nodos de Almacenamiento presentes en el sistema y, por lo tanto, no se ve afectada por eventos como aumentos y disminuciones de escala.

def hash_fn(key: str, total_slots: int) -> int: """hash_fn creates an integer equivalent of a SHA256 hash and takes a modulo with the total number of slots in hash space. """ hsh = hashlib.sha256() # converting data into bytes and passing it to hash function hsh.update(bytes(key.encode('utf-8'))) # converting the HEX digest into equivalent integer value return int(hsh.hexdigest(), 16) % total_slots

Añadir un nuevo nodo en el sistema

Cuando hay una necesidad de escalar y añadir un nuevo nodo en el sistema, en nuestro caso un nuevo Nodo de Almacenamiento, buscamos

• la posición del nodo donde reside en el Hash Space
• poblar el nuevo nodo con los datos que debe servir
• añadir el nodo en el Hash Space

Cuando se añade un nuevo nodo en el sistema sólo afecta a los ficheros que tienen hash en la ubicación a la izquierda y asociados al nodo a la derecha, de la posición en la que encajará el nuevo nodo. Todos los demás archivos y asociaciones no se ven afectados, por lo que se minimiza la cantidad de datos que hay que migrar y el mapeo que hay que cambiar.

Desde la ilustración anterior, vemos que cuando se añade un nuevo nodo K entre los nodos B y E, se cambian las asociaciones de los ficheros presentes en el segmento B-K y se asignan al nodo K. Los datos pertenecientes al segmento B-K podrían encontrarse en el nodo E al que estaban previamente asociados. Así, los únicos ficheros afectados y que necesitan ser migrados están en el segmento B-K; y su asociación cambia del nodo E al nodo K.

Para implementar esto a bajo nivel utilizando el array nodes y keys, primero obtenemos la posición del nuevo nodo en el Hash Space utilizando la función hash. Luego encontramos el índice de la clave más pequeña mayor que la posición en el array keys ordenado utilizando la búsqueda binaria. Este índice será el lugar donde la clave y el nuevo nodo de almacenamiento se colocarán en el array keys y nodes respectivamente.

def add_node(self, node: StorageNode) -> int: """add_node function adds a new node in the system and returns the key from the hash space where it was placed """ # handling error when hash space is full. if len(self._keys) == self.total_slots: raise Exception("hash space is full") key = hash_fn(node.host, self.total_slots) # find the index where the key should be inserted in the keys array # this will be the index where the Storage Node will be added in the # nodes array. index = bisect(self._keys, key) # if we have already seen the key i.e. node already is present # for the same key, we raise Collision Exception if index > 0 and self._keys == key: raise Exception("collision occurred") # Perform data migration # insert the node_id and the key at the same `index` location. # this insertion will keep nodes and keys sorted w.r.t keys. self.nodes.insert(index, node) self._keys.insert(index, key) return key

Eliminar un nuevo nodo del sistema

Cuando existe la necesidad de reducir la escala y eliminar un nodo existente del sistema, buscamos

• la posición del nodo que hay que eliminar del Hash Space
• publicamos el nodo a la derecha con los datos que estaban asociados al nodo que hay que eliminar
• removemos el nodo del Hash Space

Cuando se elimina un nodo del sistema sólo afecta a los archivos asociados al propio nodo. Todos los demás archivos y asociaciones no se ven afectados, por lo que se minimiza la cantidad de datos que hay que migrar y el mapeo que hay que cambiar.

Desde la ilustración anterior, vemos que cuando se elimina el nodo K del sistema, cambiamos las asociaciones de los archivos asociados al nodo K al nodo que se encuentra a su derecha inmediata, es decir, el nodo E.Es decir, el nodo E. Por lo tanto, los únicos archivos afectados y que necesitan ser migrados son los asociados al nodo K.

Para implementar esto a bajo nivel utilizando el array nodes y keys, obtenemos el índice donde se encuentra el nodo K en el array keys utilizando la búsqueda binaria. Una vez que tenemos el índice eliminamos la clave del array keys y el Nodo de Almacenamiento del array nodes presente en ese índice.

def remove_node(self, node: StorageNode) -> int: """remove_node removes the node and returns the key from the hash space on which the node was placed. """ # handling error when space is empty if len(self._keys) == 0: raise Exception("hash space is empty") key = hash_fn(node.host, self.total_slots) # we find the index where the key would reside in the keys index = bisect_left(self._keys, key) # if key does not exist in the array we raise Exception if index >= len(self._keys) or self._keys != key: raise Exception("node does not exist") # Perform data migration # now that all sanity checks are done we popping the # keys and nodes at the index and thus removing the presence of the node. self._keys.pop(index) self.nodes.pop(index) return key

Asociar un ítem a un nodo

Ahora que hemos visto cómo el hashing consistente ayuda a mantener la migración de datos, durante los escalamientos y los descensos, al mínimo; es el momento de ver cómo podemos encontrar eficientemente el «nodo a la derecha» para un ítem dado. La operación para encontrar la asociación tiene que ser súper rápida y eficiente ya que es algo que se invocará para cada lectura y escritura que ocurra en el sistema.

Para implementar esto a bajo nivel volvemos a aprovechar la búsqueda binaria y realizamos esta operación en O(log(n)). Primero pasamos el elemento a la función hash y obtenemos la posición en la que se encuentra el elemento en el espacio hash. Esta posición se busca de forma binaria en la matriz keys para obtener el índice de la primera clave que sea mayor que la posición (obtenida de la función hash). si no hay claves mayores que la posición, en la matriz keys, damos la vuelta y devolvemos el índice 0. El índice así obtenido será el índice del nodo de almacenamiento en el array nodes asociado a la posición.

def assign(self, item: str) -> str: """Given an item, the function returns the node it is associated with. """ key = hash_fn(item, self.total_slots) # we find the first node to the right of this key # if bisect_right returns index which is out of bounds then # we circle back to the first in the array in a circular fashion. index = bisect_right(self._keys, key) % len(self._keys) # return the node present at the index return self.nodes

El código fuente con la implementación de Consistent Hashing en Python se puede encontrar en github.com/arpitbbhayani/consistent-hashing.

Conclusión

Consistent Hashing es uno de los algoritmos más importantes para ayudarnos a escalar y gestionar horizontalmente cualquier sistema distribuido. El algoritmo no sólo funciona en sistemas sharded, sino que también encuentra su aplicación en el balanceo de carga, la partición de datos, la gestión de sesiones pegajosas basadas en el servidor, los algoritmos de enrutamiento, y muchos más. Muchas bases de datos deben su escala, rendimiento y capacidad para manejar la enorme carga a Consistent Hashing.

• Funciones Hash – Wikipedia
• Consistent Hashing – Wikipedia
• Consistent Hashing – Stanford
• Consistent Hashing and RandomTrees
• Dynamo: Highly Available Key-value Store de Amazon

Otros artículos que te pueden gustar:

• Python almacena en caché números enteros
• Fractional Cascading – Acelerar las búsquedas binarias
• Semántica de copia en escritura
• Qué hace que la caché LRU de MySQL sea resistente
• Construir máquinas de estado finito con coroutines de Python

Este artículo fue publicado originalmente en mi blog – Consistent Hashing.

Si te ha gustado lo que has leído, suscríbete a mi boletín de noticias y recibe el post directamente en tu bandeja de entrada y dame un saludo @arpit_bhayani.