Inicio / Artículos / De módulo a anillo de hash: Escalando una flota de cachés Node.js sin enfrentar tormentas imprevistas

Node.jsSystem DesignCachingDistributed SystemsRedisPerformance

De módulo a anillo de hash: Escalando una flota de cachés Node.js sin enfrentar tormentas imprevistas

Aprenda por qué el sharding hash-mod-N hace que las bases de datos fallen cuando cambian los nodos, cómo se comparan el hashing por encuentro, salto y anillo, y cómo crear un anillo ponderado equilibrado en Node.js.

4407 palabras

Un clúster de caché que ha funcionado sin problemas durante meses puede dejar inaccesible la base de datos en cuestión de minutos tras un cambio rutinario: agregar un nodo. La causa suele ser una sola línea de código del cliente que elige un servidor mediante hash(key) % N. Esta guía explica con exactitud por qué esa línea falla, compara las cuatro alternativas serias, crea un anillo de hash consistente de calidad para producción en Node.js y enumera las trampas operativas de las que el algoritmo en sí no podrá protegerlo.

El patrón de interrupciones

Imagínese una flota saludable de cuatro nodos de caché con un porcentaje de aciertos del 94 %. El tráfico está aumentando antes de un pico estacional, por lo que un ingeniero agrega un quinto nodo. Se trata de un cambio de configuración de dos líneas, implementado con cuidado en medio de una jornada laboral. Un minuto y medio después, la base de datos alcanza el 100 % de uso del CPU y el sitio deja de estar disponible.

Nadie actuó de forma descuidada. El cliente simplemente redirigió las claves como siempre lo había hecho:

const node = nodes[hash(key) % nodes.length];

Esa expresión distribuye las claves de manera muy uniforme, por lo que parece correcta. El problema surge en el instante en que nodes.length cambia, y ahí comienza el resto de esta guía. La discusión aborda cuatro problemas distintos, evalúa las alternativas reales y luego crea y mide un anillo en Node.js.

Cuatro problemas ocultos detrás de una misma idea

El hashing consistente suele presentarse como un único truco. En la práctica, resuelve cuatro problemas diferentes, y una implementación que solo maneje el primero seguirá fallando en producción debido a los otros tres.

Problema 1: cambiar N mueve casi todas las claves

Con hash(key) % N, cambiar N no solo reubica unas pocas claves, sino que reubica casi todas ellas.

Es útil analizar los números. Una clave con hash 1,000,003 se asocia al nodo 3 mediante % 4, y casualmente también se asocia al nodo 3 mediante % 5. Una clave con hash 1,000,004 se asocia al nodo 0 bajo % 4 y al nodo 4 bajo % 5. Estas dos asociaciones no tienen relación entre sí, por lo que una clave permanece donde estaba únicamente por casualidad, con una probabilidad de aproximadamente 1 entre N.

Al analizar un millón de claves, el patrón es claro: al pasar de 8 a 9 nodos, el 88.93% de las claves se mueven, y en un clúster de cien nodos, agregar un nodo invalida aproximadamente el 99% de la caché.

Fíjese hacia dónde apunta esa tendencia. Cuanto más crece su sistema, más destructivo se vuelve cada paso de escalado. Se trata de un fallo que permanece oculto hasta que el negocio comienza a tener éxito.

Cada clave reubicada representa un error de búsqueda, y cada error genera una consulta a la base de datos; todas estas consultas llegan en cuestión de segundos. Una base de datos diseñada para atender el 6% de las búsquedas que normalmente fallan recibe de repente casi todas ellas.

Problema 2: el mismo reorganización, sin planificación

Al menos el primer problema ocurre cuando se decide escalar. El segundo es el mismo evento desencadenado por una falla, en el momento menos oportuno.

Un nodo agota su memoria, un host es terminado o una partición de red oculta a un nodo del resto de la red. El número de nodos disminuye de 8 a 7, y cada cliente, actuando por su cuenta, vuelve a asignar aproximadamente el 87% de sus claves a los nodos restantes.

La situación ahora es crítica: se ha perdido el 12,5% de la capacidad del caché, la base de datos enfrenta una ola de fallos del 87%, y los siete nodos sobrevivientes deben manejar el tráfico del nodo perdido al mismo tiempo que se vuelven a llenar con casi todas las claves. Un resultado frecuente es que otro nodo colapse, lo que obliga a realizar un nuevo mapeo completo, lo cual a su vez hace caer a un tercer nodo.

El módulo de enrutamiento convierte la falla de un nodo en una falla correlacionada en todo el clúster que se autoalimenta. Esa cascada, y no un caché inactivo, es el verdadero peligro.

Problema 3: un anillo ingenuo está gravemente desequilibrado

La solución obvia para el problema 1 es colocar los nodos y las claves en un mismo espacio numérico y asignar cada clave al nodo que sigue en sentido horario. Esa es la esencia del hashing consistente, y efectivamente elimina el reorganización masiva.

No obstante, al implementarlo de forma ingenua, el equilibrio de la carga es deficiente. Los nodos se ubican dondequiera que caigan sus hashes, por lo que los espacios entre ellos son aleatorios, y rara vez son iguales. Al asignar un hash a cada uno de los cuatro nodos, en una medición un único nodo poseyó el 45% del espacio de claves, mientras que otro solo tuvo el 13%, lo que representa una diferencia de 3.4 veces sin ningún error en el código.

El desequilibrio también es persistente. Proviene de los propios nombres de los nodos; así, el mismo nodo, por ejemplo cache-04, sigue siendo muy activo hasta que se le cambia el nombre, y cualquiera que lo investigue encuentra código que funciona exactamente como está escrito.

A mayor escala, la situación empeora. Con un punto de anillo por nodo en un total de 8 nodos, el nodo más ocupado cargó con el 434% de su cuota justa, mientras que el menos ocupado solo cargó con el 3.7%. Eso equivale efectivamente a un servidor sobrecargado y siete inactivos.

Problema 4: todos los clientes deben estar de acuerdo

El problema menos evidente se refiere a la autoridad. Algo tiene que asociar una clave con un nodo, y debe dar la misma respuesta en cada máquina que lo solicite.

Una opción es utilizar un servicio de coordinación que almacene el mapa autoritativo. En ese caso, o bien cada búsqueda requiere un viaje de ida y vuelta por la red, o bien los clientes almacenan en caché el mapa, lo que exige un método para invalidarlo. Si dos clientes tienen versiones diferentes del mapa, aunque sea por un momento, uno podría escribir user:42 en el nodo A mientras otro lo lee del nodo B. Nada se pierde, lo cual es quizás peor: ahora existen dos valores plausibles.

Lo que se desea es un mapeo que sea una función pura de la clave y de la lista actual de miembros. Sin coordinador, sin servicio de búsqueda, sin estado compartido: cada cliente realiza las mismas operaciones aritméticas y llega al mismo resultado. El hashing consistente proporciona exactamente eso, y por eso prevalece sobre una tabla de búsqueda a pesar de la mayor flexibilidad de esta última.

Un escenario concreto y las opciones

Para hacer la comparación más concreta, considere este sistema.

El sistema. Una API de comercio electrónico almacena en caché los datos de sesiones y perfiles en un grupo de nodos Redis. La carga máxima es de aproximadamente 40,000 búsquedas por segundo en 25 millones de claves, con una tasa de éxito del 94 %. La base de datos solo sigue funcionando porque maneja el 6 % de búsquedas que fallan. (Para repasar los patrones de caché en sí, consulte Fundamentos del caché en Redis.)

Los requisitos:

  1. Aumentar de 8 a 12 nodos antes de una venta sin provocar una ola de fallos
  2. Sobrevivir a la pérdida de un nodo con un radio de afectación limitado y tolerable
  3. Mantener la carga equilibrada, sin que ningún nodo supere aproximadamente el 120 % de su cuota justa
  4. Asegurarse de que ningún coordinador esté en el camino de las lecturas
  5. Tener en cuenta hardware mixto: algunos nodos tienen 64 GB y otros 16 GB, y no deben soportar la misma carga

Varios algoritmos pueden satisfacer algunos o todos estos requisitos. Se diferencian de maneras significativas, y una mala elección tiene consecuencias costosas.

Opción A: hash modular

hash(key) % N ofrece un equilibrio perfecto, requiere una sola instrucción y no utiliza memoria.

Falla rotundamente en los requisitos 1 y 2. Merece ser mencionado porque es lo que todos escriben primero, y funciona perfectamente hasta el día en que deja de hacerlo.

Elija esta opción cuando N realmente nunca cambie, como al dividir un trabajo por lotes entre una cantidad fija de procesadores o al realizar sharding dentro de un único proceso.

Opción B: un coordinador y una tabla de búsqueda

Mantenga una asignación explícita de rangos de claves a nodos en un almacenamiento como etcd o ZooKeeper. Sistemas como Vitess y HBase funcionan más o menos de esta manera.

La ventaja es real: control total. Puede reubicar un único fragmento sensible, reequilibrar un rango a la vez mientras monitorea las métricas, o asignar un inquilino específico a hardware concreto. Ningún enfoque basado en hash ofrece nada de esto, y al superar cierta escala lo necesitará.

El precio también es real: un sistema de consenso que debe ejecutarse, la dificultad de mantener actualizadas todas las copias en caché del mapa, y una dependencia obligatoria de la ruta de lectura.

Elija este método cuando esté moviendo datos duraderos en lugar de entradas de caché desechables, y necesite controlar la migración en lugar de dejar que todo cambie de golpe.

Opción C: hashing de encuentro (HRW)

El hashing con mayor peso aleatorio asigna una puntuación a cada clave frente a cada nodo y elige al ganador:

function rendezvous(key, nodes) {
  let best = null, bestScore = -1;
  for (const node of nodes) {
    const score = mix(hash(key), hash(node));
    if (score > bestScore) { bestScore = score; best = node; }
  }
  return best;
}

Ese es el algoritmo completo. No hay anillo, ni nodos virtuales, ni estructura ordenada, y no hay nada que reconstruir cuando cambia la pertenencia a un nodo.

En las dos métricas más importantes también supera al anillo. Al pasar de 8 a 9 nodos, se movieron el 11,09% de las claves, frente a un mínimo teórico del 11,11%, y el equilibrio fue casi perfecto sin necesidad de ajustes.

La desventaja es que cada búsqueda requiere un trabajo de O(N), ya que cada clave se hashea contra cada nodo, y ese costo aumenta rápidamente a medida que crece el conjunto de nodos.

Elija este método cuando tenga menos de unos 30 nodos. Muchos equipos utilizan alrededor de ocho nodos de caché y estarían mejor servidos con el hashing por encuentro: es más sencillo de escribir y comprender, además de lograr un mejor equilibrio. El anillo es la solución más conocida, pero no necesariamente la mejor.

Opción D: hash consistente por saltos

Este algoritmo, publicado por Google en 2014, cabe en unas diez líneas, no necesita memoria, equilibra casi perfectamente y mueve la menor cantidad posible de claves.

Su límite es estructural. Asigna una clave a un número de bucket en [0, N) y no tiene concepto alguno de la identidad del nodo. Los buckets solo pueden añadirse o eliminarse en el final del rango; no existe forma de sacar el nodo 3 del medio manteniendo estable todo lo demás.

Elija este algoritmo cuando los buckets sean intercambiables y solo cambie su cantidad, como al dividir un conjunto de datos entre un grupo de procesadores reconfigurables. No es adecuado cuando se unen y se separan servidores con nombres específicos, que es precisamente cómo actúan los nodos de caché.

Opción E: un anillo hash con nodos virtuales

Este es el diseño clásico. Los nodos y las claves comparten un mismo espacio de direcciones circular, y una clave pertenece al primer nodo que se encuentra en sentido horario a partir de ella.

Elija este diseño cuando la flota sea lo suficientemente grande como para que el costo lineal de las búsquedas de encuentro se vuelva excesivo, y también necesite nodos ponderados y la posibilidad de eliminar cualquier nodo.

Elegir uno para el escenario

Al medirlo en un cambio de 8 a 9 nodos entre un millón de claves, las alternativas distintas al método módulo se acercan mucho al mínimo teórico, y el equilibrio del anillo depende en gran medida de cuántos nodos virtuales recibe cada servidor. Para este sistema de comercio electrónico, con hardware mixto, nodos con nombre que pueden fallar y una flota prevista de 30 nodos, el anillo es la elección adecuada. El resto de esta guía explica cómo implementarlo correctamente.

Cómo funciona el anillo

Olvídense de los arreglos y los restos. Imaginen un círculo numerado del 0 al 2³² − 1 que se repite en la parte superior.

El algoritmo completo se compone de dos reglas:

  1. Hash cada nombre de nodo en el círculo, de modo que cache-01 quede donde lo indique su hash.
  2. Hash cada clave en el mismo círculo y luego avancen en sentido horario. El primer nodo al que lleguen es el dueño de la clave.

La idea clave es que los nodos y las claves comparten un espacio de direcciones. Todo lo demás se deriva de eso, incluyendo por qué agregar un nodo no es costoso.

Por qué los cambios en la pertenencia permanecen locales

Al colocar un nuevo nodo en el círculo, este queda entre dos nodos existentes. Solo se hace cargo del arco que va desde él hasta su vecino en sentido antihorario.

Las claves que se encuentran fuera de ese arco no se ven afectadas y llegan a su propietario anterior tal como antes. El recién llegado ocupa en promedio 1/(N+1) del círculo, por lo que esa parte de las claves se traslada. Al medirlo en un cambio de 8 a 9, la cifra fue de 11.06%, con un mínimo del 11.11%, en comparación con el 88.93% obtenido con el método modulo para el mismo cambio y conjunto de claves.

La eliminación funciona de forma inversa: el arco del nodo que se retira pasa a su sucesor en sentido horario. Al reducirse de 8 a 7 nodos, se trasladó 12.60% de las claves, cerca del valor teórico del 12.50%. El impacto es limitado y manejable, y los otros seis nodos permanecen intactos.

Los nodos virtuales corrigen el desequilibrio

Volviendo al problema 3: cuatro nodos en cuatro posiciones aleatorias generan arcos muy desiguales.

La solución es sorprendentemente sencilla: No coloque cada nodo solo una vez. Colóquelo 160 veces bajo 160 nombres derivados como cache-01#0 y cache-01#1. Cada nombre derivado se ubica en un lugar diferente, de modo que cada nodo físico posee 160 arcos pequeños dispersos en lugar de uno grande, y la ley de los grandes números equilibra las cosas.

Al medirlo en un millón de claves distribuidas en 8 nodos, el equilibrio mejora de manera constante a medida que aumenta la cantidad de réplicas. 160 es el valor predeterminado habitual porque es aproximadamente donde se plana la curva de mejora, aunque 500 sigue siendo notablemente mejor. Un punto del anillo necesita aproximadamente 12 bytes (4 bytes para la posición más 8 bytes para la referencia del propietario), por lo que ocho nodos con 500 réplicas ocupan menos de 50 KB. Si el equilibrio le importa más que esa cantidad de memoria, aumente la cifra; es un cálculo que pocas equipos se toman la molestia de realizar.

Los nodos virtuales también hacen que el ponderado sea prácticamente gratuito. Un nodo con el doble de memoria obtiene el doble de puntos y, por lo tanto, aproximadamente el doble de tráfico. Con ponderaciones de 4:4:1:1, la distribución medida fue del 40.6%, 41.1%, 9.4% y 9.0%, frente a un ideal de 40/40/10/10.

Implementación del anillo en Node.js

La implementación se reduce a cuatro pasos: hashear los nombres de los nodos virtuales, colocarlos, ordenarlos y utilizar búsqueda binaria para encontrar al propietario de una clave. La clase a continuación mantiene la pertenencia en un Map, reconstruye los arrays ordenados cuando cambia la pertenencia y expone get(key) para búsquedas.

export class ConsistentHashRing {
  #positions = new Uint32Array(0); // sorted ring positions
  #owners = []; // owners[i] owns #positions[i]
  #nodes = new Map(); // id -> { weight, points }

  constructor({ replicas = 160, hash = defaultHash } = {}) {
    if (replicas < 1) throw new RangeError("replicas must be >= 1");
    this.replicas = replicas;
    this.hash = hash;
  }

  addNode(id, weight = 1) {
    if (typeof id !== "string" || id.length === 0)
      throw new TypeError("node id must be a non-empty string");
    if (weight <= 0) throw new RangeError("weight must be > 0");
    if (this.#nodes.has(id)) return this;
    this.#nodes.set(id, {
      weight,
      points: Math.max(1, Math.round(this.replicas * weight)),
    });
    this.#rebuild();
    return this;
  }

  removeNode(id) {
    if (this.#nodes.delete(id)) this.#rebuild();
    return this;
  }

  #rebuild() {
    const pairs = [];
    for (const [id, { points }] of this.#nodes) {
      for (let i = 0; i < points; i++)
        pairs.push([this.hash(`${id}#${i}`), id]);
    }
    pairs.sort((a, b) => a[0] - b[0]);
    this.#positions = Uint32Array.from(pairs, (p) => p[0]);
    this.#owners = pairs.map((p) => p[1]);
  }

  /** Index of the first ring point >= h, wrapping to 0. */
  #successor(h) {
    const pos = this.#positions;
    let lo = 0,
      hi = pos.length;
    while (lo < hi) {
      const mid = (lo + hi) >>> 1;
      if (pos[mid] < h) lo = mid + 1;
      else hi = mid;
    }
    return lo === pos.length ? 0 : lo;
  }

  get(key) {
    if (this.#positions.length === 0) return null;
    return this.#owners[this.#successor(this.hash(key))];
  }
}

Tres decisiones de diseño merecen atención.

Arreglos paralelos en lugar de un arreglo de objetos. Al almacenar las posiciones en un Uint32Array, la búsqueda binaria funciona sobre memoria compacta y contigua que permanece en la caché de la CPU. Con 8 nodos y 160 réplicas hay 1,280 puntos, aproximadamente 5 KB, y una búsqueda requiere alrededor de 11 comparaciones.

El bucle en lo === pos.length ? 0 : lo. Una clave cuyo hash supera el último punto pertenece al primer nodo del círculo. Omitir esa condición es el error más común en los anillos hechos por uno mismo: el resultado es correcto para casi todas las claves, pero inexplicablemente incorrecto para las pocas cercanas al extremo superior del rango.

Volver a construir ante cambios en la pertenencia, no al realizar búsquedas. Los cambios en la pertenencia ocurren raramente, mientras que las búsquedas se realizan decenas de miles de veces por segundo; por lo tanto, ordenar 1,280 entradas de vez en cuando no tiene costo significativo.

La replicación, es decir, encontrar los próximos propietarios de una clave, consiste en un recorrido en el sentido de las agujas del reloj que recoge nodos físicos distintos. La palabra “distintos” es importante, ya que los puntos adyacentes en el anillo suelen pertenecer al mismo servidor:

getReplicas(key, count = 1) {
  const n = this.#positions.length;
  if (n === 0) return [];
  const wanted = Math.min(count, this.#nodes.size);
  const out = [];
  const start = this.#successor(this.hash(key));
  for (let step = 0; step < n && out.length < wanted; step++) {
    const owner = this.#owners[(start + step) % n];
    if (!out.includes(owner)) out.push(owner);
  }
  return out;
}

Obsérvese que wanted está limitado al número de nodos físicos, por lo que solicitar más réplicas de las que hay servidores impide que el proceso continúe indefinidamente, y el recorrido se detiene después de una vuelta completa en cualquier caso.

Elegir cuidadosamente la función de hash

Muchos tutoriales omiten esta parte, pero es la que ofrece los resultados más instructivos de todo el ejercicio.

La mayoría de las implementaciones de anillos usan por defecto MD5. Funciona, pero es lento: un anillo que lo utiliza solo alcanzó 423,000 búsquedas por segundo, y los análisis mostraron que casi todo el tiempo se dedicó a procesar MD5.

Al reemplazarlo por FNV-1a, un hash no criptográfico rápido, el rendimiento aumentó aproximadamente 15 veces. Sin embargo, el equilibrio se derrumbó: la desviación estándar de la carga por nodo pasó del 10,4 % al 30,7 %.

Al analizar las posiciones calculadas para algunos nodos virtuales se descubre la causa:

cache-01#0 → 4037809751
cache-01#1 → 4021032132
cache-01#2 → 4071364989
cache-01#3 → 4054587370
cache-01#4 → 3970699275

Todas estas valores se concentran en una banda estrecha alrededor de 4.0 mil millones. FNV-1a presenta un débil comportamiento de avalancha, lo que significa que entradas similares producen salidas similares. Los nombres de los nodos virtuales difieren solo por un sufijo, por lo que en lugar de dispersar 160 puntos por todo el círculo, cada nodo los agrupa en un único grupo compacto. La optimización por velocidad trajo de vuelta silenciosamente el problema 3.

La solución consiste en pasar la salida de FNV por un finalizador de mezcla de bits, que es el paso final de MurmurHash3:

function fnv1a(str) {
  let h = 0x811c9dc5;
  for (let i = 0; i < str.length; i++) {
    h ^= str.charCodeAt(i);
    h = Math.imul(h, 0x01000193);
  }
  return h >>> 0;
}

// Scrambles the bits so near-identical inputs land far apart.
function fmix32(h) {
  h ^= h >>> 16;
  h = Math.imul(h, 0x85ebca6b);
  h ^= h >>> 13;
  h = Math.imul(h, 0xc2b2ae35);
  h ^= h >>> 16;
  return h >>> 0;
}

export const defaultHash = (str) => fmix32(fnv1a(str));

fmix32 alterna desplazamientos, operaciones XOR y multiplicaciones de modo que un cambio en cualquier bit de entrada se propaga a todos los bits de salida. Math.imul realiza una verdadera multiplicación de enteros de 32 bits, y >>> 0 convierte el resultado de nuevo en un número sin signo de 32 bits que cabe en Uint32Array. A pesar de requerir unas diez operaciones adicionales, el hash resultante es más equilibrado que MD5 y funciona aproximadamente 13 veces más rápido.

La lección general es aplicable mucho más allá del hashing: cuando reemplazas un componente por uno más rápido, debes medir la propiedad que no estabas optimizando. FNV-1a es un hash perfectamente aceptable; simplemente no es el adecuado para esta tarea, y su descripción no incluye ninguna advertencia al respecto.

Conviirtiendo el anillo en un cliente de caché

Un anillo por sí solo no es un cliente de caché. El código de producción debe hacer frente a fallos, y el anillo ofrece una estrategia clara: pasar al siguiente nodo en sentido horario.

El wrapper que se muestra a continuación toma un mapa de clientes con nombre, construye el anillo a partir de ellos y, en cada llamada a get, prueba primero a los failoverDepth propietarios en orden. Un nodo que genera un error se marca como inactivo durante downtimeMs y se elimina del anillo, para luego volver a agregarse una vez que finaliza su período de penalización.

export class ShardedCache {
  #ring; #clients; #down = new Map();

  constructor(clients, { replicas = 160, failoverDepth = 2, downtimeMs = 10_000 } = {}) {
    this.#clients = new Map(Object.entries(clients));
    this.#ring = new ConsistentHashRing({ replicas });
    for (const id of this.#clients.keys()) this.#ring.addNode(id);
    this.failoverDepth = failoverDepth;
    this.downtimeMs = downtimeMs;
  }

  #markDown(id) {
    this.#down.set(id, Date.now() + this.downtimeMs);
    this.#ring.removeNode(id);
  }

  #reviveExpired() {
    const now = Date.now();
    for (const [id, until] of this.#down) {
      if (now >= until) { this.#down.delete(id); this.#ring.addNode(id); }
    }
  }

  async get(key) {
    this.#reviveExpired();
    for (const id of this.#ring.getReplicas(key, this.failoverDepth)) {
      try {
        return { value: await this.#clients.get(id).get(key), node: id };
      } catch {
        this.#markDown(id);
      }
    }
    return { value: null, node: null, allDown: true };
  }
}

Al ejecutar esto con cuatro nodos simulados que albergaban 10,000 claves y luego eliminar uno de ellos, se obtuvo lo siguiente:

Keys per node:  cache-01 2213 | cache-02 2462 | cache-03 2923 | cache-04 2402

Killing cache-02...
  served from cache: 7538
  cache misses:      2462
  hard failures:     0
  healthy nodes:     cache-01, cache-03, cache-04

  24.6% of traffic became a miss.

Esa cifra representa tu plan de capacidad. En una flota de cuatro nodos, una falla hace que un 24.6% adicional de las lecturas recaigan en la base de datos, mientras que en una flota de ocho nodos esa cifra se reduce al 12.5%. Si la base de datos no puede soportar 1/N de tu carga de lecturas llegando todas a la vez, el verdadero problema es la capacidad de la base de datos, no el caché, y el hashing consistente ha convertido ese problema de fatal a visible. Tenga también en cuenta que no hubo fallas graves: las solicitudes para las claves del nodo inactivo fueron redirigidas al siguiente nodo y se convirtieron en fallos normales.

Riesgos en producción que el algoritmo no aborda

Varios problemas están fuera del alcance del algoritmo y, de todos modos, te causarán problemas.

Desequilibrio en las versiones del anillo

El anillo solo es útil si todos los clientes calculan la misma respuesta. Implemente el cambio en la membresía de forma gradual: durante unos minutos, la mitad de la flota verá 8 nodos mientras que la otra mitad verá 9. Las dos mitades estarán en desacuerdo respecto a aproximadamente el 11 % de las claves. En un caché, eso significa una ligera disminución en la tasa de aciertos; en cualquier sistema que acepte escrituras, significa datos divergentes. Versione el conjunto de membresías, distribúyalo a través de un único canal e informe la versión en sus métricas, para que pueda observar el desfase en lugar de tener que adivinarlo.

Expulsar nodos con demasiada prisa

No se debe eliminar un nodo después de un solo tiempo de espera. Un nodo que entra y sale constantemente provoca una tormenta de cambios, ya que cada transición mueve 1/N de las claves. Es necesario que haya varios fallos consecutivos dentro de un período determinado antes de expulsarlo, y se debe volver a admitir con cautela. El ejemplo anterior utiliza una penalización fija de diez segundos; el código en producción debería emplear un retroceso exponencial y una verificación de estado antes de permitir que un nodo vuelva a entrar.

Las claves activas no están equilibradas

El hashing consistente distribuye las claves de manera uniforme, pero no dice nada sobre las solicitudes. Cuando un producto en particular se vuelve repentinamente muy popular, su entrada queda en un servidor único, y ese servidor se sobrecalienta a pesar de que el anillo está funcionando correctamente. Existen dos soluciones: un pequeño caché dentro del proceso frente al anillo para las claves más utilizadas, o la variante de cargas limitadas del hashing consistente desarrollada por investigadores de Google, que limita la cantidad que puede procesar cada nodo y envía el exceso en dirección horaria.

El remapeo no es migración

Todo lo anterior supone que perder una clave solo conlleva un error de caché. Si el anillo enruta datos duraderos*, “11 % de las claves movidas” significa que el 11 % de los datos debe copiarse físicamente a su nuevo nodo antes de poderse leer allí, generalmente con lecturas o escrituras dirigidas a ambas ubicaciones hasta que finalice la copia. El anillo identifica qué debe moverse; no hace nada para moverlo. Esa es precisamente la razón por la cual sistemas como Vitess dependen de un coordinador: necesitan controlar la migración, no solo calcularla.

El número de réplicas es efectivamente permanente

Cambiar replicas de 160 a 500 modifica cada posición del anillo y reorganiza casi todas las claves, lo cual es tan disruptivo como un cambio de módulo. Considérelo una decisión de diseño única tomada antes de tener datos en tiempo real, y si no está seguro, elija un valor más alto.

Cuando el anillo no es la herramienta adecuada

Parte del juicio de ingeniería consiste en reconocer cuándo la solución impresionante es la incorrecta.

  • utilice el hashing por encuentro. Requiere menos código, se equilibra mejor y no hay cantidad de réplicas que ajustar. La única ventaja del anillo es la búsqueda O(log N), que resulta académica con ese tamaño.
  • Contenedores intercambiables donde solo cambia la cuenta: utilice el hash por salto, con diez líneas de código y sin consumo de memoria.
  • Datos duraderos que necesitan movimiento controlado: utilice un coordinador. Solo un mapa explícito le permite mover un único shard mientras se monitorea su impacto, algo que el hashing no puede ofrecer.
  • N que realmente nunca cambia: % N es suficiente. No construya mecanismos para un cambio que no ocurrirá.

Un anillo se hace necesario cuando los nodos tienen nombres, son heterogéneos, numerosos y propensos a fallar. Eso describe de forma casi perfecta a una flota de cachés, por lo que tantos cachés distribuidos se construyen sobre este modelo.

Puntos clave

  • La idea central es sencilla: colocar las claves y los servidores en un mismo espacio de direcciones, de modo que un cambio en la membresía afecte solo a una zona cercana y no a todo.
  • El enrutamiento modular convierte cada evento de escalado y cada fallo de nodo en un vaciado casi total del caché, y el daño aumenta con el tamaño del clúster.
  • El hashing de encuentro suele ser la mejor opción para flotas pequeñas; opta por el anillo cuando el tamaño, el ponderamiento y la eliminación arbitraria son factores importantes.
  • Sin nodos virtuales, un servidor puede manejar varias veces su cuota justa. Elige de antemano la cantidad de réplicas, ya que cambiarla posteriormente reorganiza todo.
  • Un hash rápido con una eficacia de avalancha débil puede reintroducir silenciosamente el desequilibrio; siempre debe medirse la distribución, no solo la velocidad.
  • La pérdida de un nodo hace que aproximadamente 1/N de las lecturas se dirijan a la base de datos. Diseñe la base de datos en consecuencia, gestione los cambios en la membresía de las versiones, elimine los nodos de forma conservadora y trate las claves activas por separado.

    • El anillo en sí consta solo de unas pocas docenas de líneas de código. La ingeniería que garantiza su fiabilidad en producción es todo lo que lo rodea.

    Lecturas relacionadas

    Todos los artículosEnviar el brief