¿Cómo implementar un anillo de hash consistente con nodos virtuales?

Pregunta y alcance

Implementa un anillo para enrutar claves de tipo string a nodos físicos. La API es addNode(nodeId, weight), removeNode(nodeId) y getNode(key). Un nodo recibe weight × V tokens virtuales, donde V es un recuento base configurado. Utiliza una abstracción de hash determinista de 64 bits, maneja las colisiones de forma segura y devuelve el primer token activo en sentido horario a partir de la clave. Si el anillo está vacío, getNode no devuelve ningún nodo.

Este es un problema de codificación, no un servicio completo de membresía o replicación. Se asume que las actualizaciones de membresía son serializadas por quien realiza la llamada. La solución debe explicar por qué la incorporación o eliminación de un nodo solo modifica los intervalos de claves cercanos, y dónde deja de ser útil esa propiedad, como ante una clave caliente (hot key) o un hash mal elegido.

Qué evalúa el entrevistador

PracHub registra esto como una pregunta de filtro técnico para Ingeniero de Software en DoorDash con addNode, removeNode y getNode, balanceo por nodos virtuales, manejo de colisiones y análisis de complejidad. Un registro público reciente de entrevistas de DoorDash también describe arreglar un balanceador de carga round-robin e implementar hashing consistente.

La señal que se busca es un diseño de estructura de datos ejecutable: búsqueda ordenada, identidad de token estable, actualizaciones seguras ante duplicados, un invariante claro y pruebas para el wrap-around y cambios de membresía. El artículo original del MIT define las propiedades útiles como balance y monotonicidad: las asignaciones deben mantenerse razonablemente uniformes y agregar un bucket no debe reasignar claves que pueden permanecer en su bucket anterior.

Preguntas aclaratorias antes de responder

1. ¿Son los IDs de los nodos únicos y estables entre reinicios? Se requieren IDs estables para eliminar exactamente los tokens que pertenecen a un nodo físico.
2. ¿Es weight un entero? Esta respuesta asume un entero positivo; una capacidad fraccionaria necesita un presupuesto de tokens normalizado.
3. ¿Son las actualizaciones de membresía concurrentes con las búsquedas? En caso afirmativo, publica una instantánea (snapshot) inmutable o agrega un bloqueo de lectura/escritura; el código a continuación asume actualizaciones serializadas.
4. ¿Se requiere replicación? La API básica devuelve un único propietario. Devolver R sucesores distintos es una pregunta de seguimiento con reglas para fallos y tokens duplicados.
5. ¿Qué función de hash está disponible? Considérala determinista y uniforme para el ejercicio; las opciones de producción requieren revisión de colisiones y entradas adversarias.

Marco de respuesta de 30 segundos

“Almaceno registros (token, virtualNodeId, physicalNodeId) en orden secuencial. Agregar un nodo inserta weight × V tokens deterministas; eliminarlo borra exactamente esos tokens. La búsqueda calcula el hash de la clave, realiza una búsqueda binaria del primer token igual o posterior a ella y hace wrap-around al índice cero. El invariante es que cada token se asigna a un nodo físico activo y cada clave es propiedad del primer token en sentido horario. La búsqueda es O(log M), las actualizaciones son O(V·weight·log M), y pruebo colisiones, wrap-around, actualizaciones duplicadas, eliminación, anillos vacíos y reasignación de claves.”

Respuesta profunda paso a paso

1. Elegir la representación y el invariante

Sea M el número de tokens virtuales. Mantén un arreglo ordenado de registros y un mapa desde el ID del nodo físico a sus registros de tokens generados. El arreglo ordenado hace que la búsqueda sea una búsqueda de límite inferior (lower-bound search); el mapa inverso hace que la eliminación sea precisa en lugar de escanear en busca de un prefijo coincidente.

El invariante es:

1. Los tokens están ordenados por (hash, tokenId).
2. Cada token hace referencia a un nodo físico registrado.
3. Una clave se asigna al primer token en sentido horario, haciendo wrap-around en el límite del anillo.
4. El conjunto de tokens de un nodo físico se genera únicamente a partir de su ID estable, su índice y el recuento configurado.

El criterio de desempate secundario tokenId hace que los valores de hash iguales sean deterministas. No pretende que las colisiones sean imposibles.

2. Generar tokens virtuales de forma determinista

Para el nodo n y el índice virtual i, calcula el hash de los bytes de n + "#" + i. Genera índices de weight × V. Por lo tanto, un peso mayor posee más intervalos en expectativa. Utiliza una implementación de hash fija y persiste la política de V y pesos junto con la instantánea del anillo; cambiarlos silenciosamente reasigna las claves.

Una implementación puede usar un árbol balanceado para inserción y eliminación en O(log M). Un arreglo ordenado, muy adecuado para entrevistas, mantiene visible el invariante; las actualizaciones de membresía por lotes pueden reconstruir el arreglo una sola vez en lugar de desplazarlo repetidamente.

3. Implementar búsqueda y actualizaciones

from bisect import bisect_left

class ConsistentHashRing:
    def __init__(self, virtuals_per_weight, hash64):
        self.v = virtuals_per_weight
        self.hash64 = hash64
        self.tokens = []  # (hash, token_id, node_id)
        self.by_node = {}

    def add_node(self, node_id, weight=1):
        if weight <= 0 or node_id in self.by_node:
            raise ValueError("invalid or duplicate node")
        owned = []
        for i in range(weight * self.v):
            token_id = f"{node_id}#{i}"
            owned.append((self.hash64(token_id), token_id, node_id))
        self.by_node[node_id] = owned
        self.tokens.extend(owned)
        self.tokens.sort()

    def remove_node(self, node_id):
        owned = self.by_node.pop(node_id, None)
        if owned is None:
            return False
        owned_ids = {token_id for _, token_id, _ in owned}
        self.tokens = [t for t in self.tokens if t[1] not in owned_ids]
        return True

    def get_node(self, key):
        if not self.tokens:
            return None
        h = self.hash64(key)
        i = bisect_left(self.tokens, (h, "", ""))
        return self.tokens[i if i < len(self.tokens) else 0][2]

El código trata un nodo duplicado como un error del invocador y la eliminación de un nodo ausente como un no-op. En producción, las actualizaciones generalmente construirían una nueva instantánea y la publicarían atómicamente para que los lectores nunca observen un anillo actualizado a medias.

4. Deducir la complejidad y el comportamiento de reasignación

Con M = V × sum(weight), la búsqueda es O(log M) y O(1) de espacio adicional por llamada. La inserción y eliminación en la implementación de arreglo son O(M + K log M) debido a la ordenación y filtrado, donde K es el recuento de tokens del nodo modificado; un árbol balanceado reduce las actualizaciones a O(K log M). La memoria es O(M).

Cuando se agrega un nodo, solo las claves en los intervalos inmediatamente anteriores a sus tokens virtuales se mueven a él. Cuando se elimina un nodo, esos intervalos se mueven a sus siguientes propietarios en sentido horario. Esta es la ventaja de monotonicidad sobre el hashing con módulo, donde cambiar N reasigna la mayoría de las claves. Los nodos virtuales reducen la varianza, pero no pueden solucionar una única clave caliente o una carga de trabajo sesgada.

Ejemplo de respuesta de alta calidad

“Represento el anillo como registros ordenados (hash, tokenId, nodeId) más un mapa desde el ID del nodo a sus registros. addNode crea weight × V tokens virtuales deterministas; removeNode elimina exactamente esos registros. getNode utiliza una búsqueda de límite inferior y hace wrap-around. El invariante es que cada clave pertenece al primer token activo en sentido horario, con (hash, tokenId) resolviendo colisiones de manera determinista. La búsqueda es O(log M); un arreglo ordenado hace que las actualizaciones sean O(M + K log M), mientras que un árbol puede hacerlas O(K log M). Probaría anillos vacíos y de un solo nodo, wrap-around, IDs duplicados, colisiones, eliminación, distribución ponderada y la fracción de claves reasignadas tras cambios en la membresía.”

Errores comunes

• Usar hash(key) % N → cambiar el recuento de nodos reasigna la mayoría de las claves → busca el siguiente token en sentido horario.
• Asumir que las colisiones no pueden ocurrir → hashes iguales producen una propiedad inestable → desempatar mediante un ID de token determinista.
• Generar tokens aleatorios en cada reinicio → todas las claves se mueven inesperadamente → derivar los tokens a partir de un ID de nodo estable y su índice.
• Eliminar únicamente por prefijo de nombre de nodo → IDs similares pueden eliminar registros incorrectos → mantener un mapa inverso explícito y los IDs de los tokens.
• Afirmar que los nodos virtuales eliminan los hotspots → una sola clave popular seguirá apuntando a un único propietario → agregar replicación, enrutamiento consciente de la carga o tratamiento de hot-keys como un requisito separado.
• Ignorar casos vacíos y duplicados → los invariantes de búsqueda o actualización fallan en los límites → definir el comportamiento de retorno y errores antes de codificar.

Preguntas de seguimiento y respuestas

¿Cómo devolverías tres réplicas?

Avanza en sentido horario desde el propietario y recopila IDs de nodos físicos distintos hasta encontrar tres. Omite tokens virtuales adicionales que pertenezcan a un nodo ya seleccionado; si existen menos de tres nodos activos, devuelve el conjunto disponible y un déficit explícito.

¿Cómo pruebas la distribución en lugar de un solo ejemplo?

Genera un corpus fijo de claves, mide la cuota de cada nodo y la proporción máxima a mínima, luego repite tras agregar y eliminar un nodo. Mantén fija la semilla de hash para que las regresiones sean reproducibles.

¿Qué pasa si cambia la capacidad de un nodo?

Elimina su conjunto de tokens antiguo, agrega un nuevo conjunto utilizando el nuevo peso y publica una sola instantánea. Espera que solo se muevan los intervalos adyacentes a los tokens modificados, pero monitorea la carga durante la transición.

¿Cuándo es más simple el hashing con módulo?

Si la membresía es fija o un rebalanceo completo es aceptable, el hashing con módulo es más corto y a menudo más rápido. El hashing consistente justifica su complejidad cuando la membresía cambia y el costo de reasignación es importante.