El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Particionado de Datos y Hashing Consistente

Siguiente ►
►

El Módulo 3 terminó con una frase que conviene releer: todo lo que sabemos sobre replicar, coordinar y compensar "trata los datos como si ya estuvieran en algún sitio". Esta lección abre el Módulo 4 respondiendo a la pregunta previa: cuando los pedidos de Kilómetro Cero, las posiciones de furgoneta-3 o los eventos de pedidos.eventos son demasiados para un solo nodo, ¿cómo se reparten entre muchos? Replicar copia los mismos datos en varios nodos para sobrevivir a fallos; particionar (o sharding) reparte datos distintos entre nodos para que ninguno tenga que guardarlo o servirlo todo. Veremos las estrategias de reparto (por rango, por hash, compuestas), el problema que aparece cuando el número de nodos cambia, la solución clásica del hashing consistente con nodos virtuales, su pariente rendezvous hashing, y cómo una petición encuentra el nodo correcto. Todo ello es la base sobre la que se construyen HDFS, Cassandra y Redis Cluster, que veremos en el resto del módulo, y es también una decisión de diseño que Kilómetro Cero tiene que tomar hoy: la clave de partición de sus pedidos y de su stock.

Contenido

  1. Particionar frente a replicar, y cómo se combinan
  2. Particionado por rango de clave y los puntos calientes
  3. Particionado por hash de clave y particionado compuesto
  4. Índices secundarios particionados: local frente a global
  5. El problema del hash módulo N
  6. Hashing consistente: el anillo y los nodos virtuales
  7. Rendezvous hashing
  8. Reequilibrado de particiones
  9. Enrutamiento de peticiones y descubrimiento de particiones
  10. Elegir la clave de partición en Kilómetro Cero
  11. Errores Comunes y Consejos
  12. Ejercicios
  13. Conclusión

  1. Particionar frente a replicar, y cómo se combinan

Los dos mecanismos responden a problemas diferentes y se confunden a menudo porque en la práctica aparecen juntos:

Aspecto Replicación (03-04) Particionado (esta lección)
Qué copia Los mismos datos en varios nodos Datos distintos en cada nodo
Problema que resuelve Disponibilidad, tolerancia a fallos, lecturas cercanas Volumen y rendimiento: ningún nodo aguanta todo el conjunto
Si cae un nodo Otro nodo tiene una copia Se pierde su partición… salvo que esté replicada
Coste principal Consistencia entre copias Reparto desigual, consultas que cruzan particiones
Pregunta clave ¿Cuántas copias y con qué garantías? ¿Qué dato va a qué nodo?

En un sistema real cada partición se replica: el conjunto de datos se divide en particiones P1…Pn, y cada partición tiene un líder y varios seguidores (o un quórum sin líder). Un nodo físico suele ser líder de algunas particiones y seguidor de otras, de modo que la carga y el riesgo se reparten:

flowchart LR
    subgraph Nodo A
        A1[P1 líder]
        A2[P2 seguidor]
        A3[P4 seguidor]
    end
    subgraph Nodo B
        B1[P2 líder]
        B2[P3 seguidor]
        B3[P1 seguidor]
    end
    subgraph Nodo C
        C1[P3 líder]
        C2[P4 líder]
        C3[P2 seguidor]
    end
    subgraph Nodo D
        D1[P4 seguidor]
        D2[P1 seguidor]
        D3[P3 seguidor]
    end

El objetivo del particionado es que los datos y la carga se repartan de forma uniforme. Si el reparto es desigual, algunas particiones reciben mucha más carga que otras: son los puntos calientes (hot spots), y una partición caliente convierte a un sistema de 10 nodos en un sistema con la capacidad de 1. Todo lo que sigue gira en torno a dos preguntas: cómo asignar claves a particiones para evitar puntos calientes, y cómo asignar particiones a nodos para que añadir o quitar máquinas no obligue a mover todos los datos.

  1. Particionado por rango de clave y los puntos calientes

La estrategia más intuitiva es ordenar las claves y asignar a cada partición un rango contiguo, como los tomos de una enciclopedia (A–C, D–F…). Los límites no tienen por qué ser regulares: se adaptan a la densidad de datos para que cada partición tenga un tamaño parecido.

Ventaja: las consultas por rango son eficientes, porque las claves vecinas están en el mismo nodo. Si la clave de los pedidos es la fecha, "todos los pedidos de la semana pasada" se resuelve en una o dos particiones.

Inconveniente: los rangos concentran carga cuando el patrón de acceso se concentra en una zona de claves. Kilómetro Cero lo vivió en la "Semana de la Vendimia": con los pedidos particionados por fecha_creacion, todas las escrituras del día van a la misma partición (la del rango que contiene "hoy"), mientras las particiones de días anteriores están ociosas. Diez nodos y solo uno escribiendo.

Clave de rango Consulta que favorece Punto caliente
fecha_creacion Pedidos por periodo Escrituras siempre en la partición de "hoy"
cliente_id alfabético Pedidos de un cliente Clientes con nombre que empiece por letras frecuentes
producto_slug Pedidos de un producto vino-crianza en la Semana de la Vendimia

Un remedio habitual es anteponer a la clave algo que disperse: por ejemplo, mercado + fecha (Girona, Lleida, Tarragona, Valencia reparten las escrituras de hoy en cuatro particiones). Sigue habiendo cuatro puntos calientes, pero repartidos; y la consulta "pedidos de esta semana en Valencia" sigue siendo un rango. Esto anticipa el particionado compuesto del apartado siguiente.

  1. Particionado por hash de clave y particionado compuesto

Para eliminar los puntos calientes por proximidad de claves, se aplica una función hash a la clave y se particiona por el resultado. Un buen hash (MD5, SHA-1, MurmurHash, xxHash; no hace falta que sea criptográfico, sí que sea uniforme y estable entre lenguajes y versiones) convierte claves parecidas (P-2026-000123 y P-2026-000124) en valores muy alejados, de modo que los pedidos consecutivos de la Semana de la Vendimia caen en particiones distintas.

import hashlib

def hash_clave(clave: str) -> int:
    """Hash estable de 64 bits de una clave de texto (los primeros 8 bytes de MD5)."""
    return int.from_bytes(hashlib.md5(clave.encode()).digest()[:8], "big")

for pedido in ["P-2026-000123", "P-2026-000124", "P-2026-000125", "P-2026-000126"]:
    print(pedido, hash_clave(pedido) % 4)

Cada línea muestra el pedido y la partición (0–3) que le toca: pedidos correlativos acaban dispersos. Es importante no usar hash() de Python para esto: desde Python 3.3 está aleatorizado por proceso para cadenas, así que dos servicios distintos obtendrían particiones distintas para la misma clave. Por eso usamos hashlib.

El precio del hash es perder las consultas por rango: "pedidos entre el 10 y el 14 de septiembre" ya no está en ninguna partición concreta, hay que preguntar a todas (scatter/gather, apartado 4).

El particionado compuesto combina ambos: una parte de la clave se hashea para elegir la partición, y el resto se usa para ordenar dentro de la partición. Cassandra lo hace explícito con la partition key y las clustering columns (04-04), pero la idea es general:

  • Clave de partición: hash(cliente_id) → todos los pedidos de Ana están en la misma partición.
  • Clave de ordenación: fecha_creacion DESC → dentro de esa partición están ordenados, así que "los últimos 20 pedidos de Ana" es una lectura secuencial en un solo nodo.

La consulta "pedidos de Ana entre dos fechas" es eficiente; "pedidos de todos los clientes de ayer" no lo es. Esto es lo esencial del modelado orientado a consultas: la clave de partición se elige según la consulta que más importa, no según el modelo de dominio.

  1. Índices secundarios particionados: local frente a global

Los pedidos se particionan por cliente_id, pero el equipo de reparto necesita "todos los pedidos pendientes de entrega en Girona", que no menciona ningún cliente. Hace falta un índice secundario (por mercado y estado), y un índice en un sistema particionado también hay que particionarlo. Hay dos maneras:

Índice local (por documento) Índice global (por término)
Dónde vive Cada partición indexa sus propios datos El índice se particiona por el valor indexado (mercado = Girona vive en una partición concreta)
Escritura Solo toca la partición del dato: rápida, atómica con el dato Toca la partición del dato y la del índice: más lenta, a menudo asíncrona (eventual)
Lectura por el índice Hay que preguntar a todas las particiones y unir resultados: scatter/gather Una sola partición responde
Latencia de lectura La de la partición más lenta (tail latency) Baja y predecible
Ejemplos Cassandra (índices secundarios locales), Elasticsearch por defecto DynamoDB GSI, vistas materializadas de Cassandra

El scatter/gather merece atención: si hay 12 particiones, la consulta lanza 12 subconsultas en paralelo y espera a la más lenta. Con una probabilidad del 1 % de que una partición tarde más de 500 ms, la probabilidad de que la consulta completa supere ese tiempo es 1 − 0,99¹² ≈ 11 %. Este es el mismo fenómeno que hizo tan importantes los percentiles altos en 01-03.

Para reparto, Kilómetro Cero elige un índice global asíncrono, materializado a partir de los eventos pedido.creado y pago.confirmado del tópico pedidos.eventos (02-05): una tabla pedidos_por_mercado particionada por mercado, que puede ir unos milisegundos por detrás. La asignación de repartidores tolera ese retraso; la creación del pedido, no toleraría una escritura sincrónica en dos particiones.

  1. El problema del hash módulo N

Con el hash en la mano, la asignación más obvia de claves a nodos es nodo = hash(clave) % N. Funciona perfectamente hasta el día en que N cambia. Al pasar de 4 a 5 nodos, hash % 4 y hash % 5 coinciden solo para las claves cuyo hash da el mismo resto en ambos, y eso ocurre aproximadamente en 1 de cada 5 claves: el 80 % de los datos cambian de nodo. En un almacén con terabytes eso significa horas de tráfico de red, cachés frías y, si es una caché, una avalancha sobre la base de datos.

Lo medimos con simulaciones/hash_modulo.py, que genera 100 000 identificadores de pedido con el formato de Kilómetro Cero:

# km0/simulaciones/hash_modulo.py
"""¿Cuántas claves de pedido cambian de nodo al pasar de 4 a 5 nodos con hash % N?"""
import hashlib

def hash_clave(clave: str) -> int:
    return int.from_bytes(hashlib.md5(clave.encode()).digest()[:8], "big")

def nodo_modulo(clave: str, n_nodos: int) -> int:
    return hash_clave(clave) % n_nodos

def medir_movimiento(claves, antes: int, despues: int) -> float:
    """Fracción de claves cuyo nodo cambia al pasar de `antes` a `despues` nodos."""
    movidas = sum(1 for c in claves if nodo_modulo(c, antes) != nodo_modulo(c, despues))
    return movidas / len(claves)

if __name__ == "__main__":
    claves = [f"P-2026-{i:06d}" for i in range(1, 100_001)]
    for antes, despues in [(4, 5), (5, 6), (10, 11), (4, 8)]:
        pct = medir_movimiento(claves, antes, despues) * 100
        print(f"{antes:>2} -> {despues:>2} nodos: se mueven el {pct:5.1f} % de las claves")

Explicación paso a paso:

  • hash_clave es la misma función estable del apartado 3.
  • nodo_modulo es la asignación ingenua: el resto de dividir el hash entre el número de nodos.
  • medir_movimiento compara, clave a clave, el nodo antes y después, y cuenta las que cambian.
  • El bloque principal prueba varios cambios de tamaño del clúster.

Salida típica:

 4 ->  5 nodos: se mueven el  80.0 % de las claves
 5 ->  6 nodos: se mueven el  83.3 % de las claves
10 -> 11 nodos: se mueven el  91.0 % de las claves
 4 ->  8 nodos: se mueven el  49.7 % de las claves

Lo ideal sería mover únicamente lo imprescindible: al añadir el quinto nodo a cuatro, solo 1/5 de las claves (las que van a parar al nuevo). Fíjate en el caso 4 → 8: duplicar el número de nodos mueve "solo" la mitad porque hash % 8 conserva el bit bajo de hash % 4; es un truco que usan algunos sistemas (crecer por duplicación), pero es rígido y sigue moviendo más de lo necesario.

  1. Hashing consistente: el anillo y los nodos virtuales

El hashing consistente (Karger et al., 1997, pensado originalmente para cachés web distribuidas) resuelve el problema desacoplando la asignación del número de nodos. La idea:

  1. El espacio de salida del hash (por ejemplo 0…2⁶⁴−1) se imagina como un anillo: el valor máximo va seguido del 0.
  2. Cada nodo también se hashea (por su nombre o dirección) y ocupa una posición en el anillo.
  3. Una clave se asigna al primer nodo que se encuentra recorriendo el anillo en el sentido de las agujas del reloj desde la posición de la clave.
flowchart TB
    subgraph Anillo["Anillo de hash (0 … 2^64−1, en el sentido horario)"]
        direction LR
        N1(("inv-bcn<br/>pos 0x1A…"))
        N2(("inv-vlc<br/>pos 0x6F…"))
        N3(("inv-gir<br/>pos 0xB3…"))
        N1 --> N2 --> N3 --> N1
    end
    K1["queso-curado<br/>hash 0x4C… → inv-vlc"] -.-> N2
    K2["tomate-rosa<br/>hash 0x9E… → inv-gir"] -.-> N3
    K3["vino-crianza<br/>hash 0xE1… → inv-bcn (da la vuelta)"] -.-> N1

Al añadir un nodo en una posición del anillo, solo las claves entre su predecesor y él cambian de dueño (pasan del sucesor al nuevo nodo). Al quitar un nodo, sus claves pasan a su sucesor y nada más se mueve. Con N nodos, añadir uno mueve en promedio 1/(N+1) de las claves: exactamente el mínimo.

El problema del anillo básico es que, con pocos nodos, sus posiciones aleatorias reparten muy mal el espacio: un nodo puede quedarse con el 50 % del anillo y otro con el 5 %. Y al quitar un nodo, toda su carga cae sobre un único sucesor. La solución son los nodos virtuales (vnodes o tokens): cada nodo físico se coloca en el anillo K veces (inv-bcn#0, inv-bcn#1, …, inv-bcn#149), con posiciones distintas. Con 100–200 vnodes por nodo, los arcos se promedian, el reparto se acerca al uniforme, y la carga de un nodo que cae se reparte entre muchos sucesores diferentes. Además, permiten dar más vnodes a las máquinas más potentes (pesos).

simulaciones/anillo_consistente.py lo implementa y lo mide:

# km0/simulaciones/anillo_consistente.py
"""Anillo de hashing consistente con nodos virtuales."""
import bisect
import hashlib
import statistics
from collections import Counter

def hash_clave(clave: str) -> int:
    return int.from_bytes(hashlib.md5(clave.encode()).digest()[:8], "big")

class AnilloConsistente:
    def __init__(self, nodos=(), vnodes: int = 150):
        self.vnodes = vnodes
        self._posiciones: list[int] = []        # posiciones ordenadas en el anillo
        self._dueño: dict[int, str] = {}        # posición -> nombre de nodo físico
        for n in nodos:
            self.añadir_nodo(n)

    def añadir_nodo(self, nodo: str) -> None:
        for i in range(self.vnodes):
            pos = hash_clave(f"{nodo}#{i}")
            if pos in self._dueño:              # colisión rarísima: se ignora el vnode
                continue
            bisect.insort(self._posiciones, pos)
            self._dueño[pos] = nodo

    def quitar_nodo(self, nodo: str) -> None:
        for i in range(self.vnodes):
            pos = hash_clave(f"{nodo}#{i}")
            if self._dueño.get(pos) == nodo:
                del self._dueño[pos]
                self._posiciones.remove(pos)

    def nodo_para(self, clave: str) -> str:
        if not self._posiciones:
            raise RuntimeError("anillo vacío")
        h = hash_clave(clave)
        idx = bisect.bisect_right(self._posiciones, h)   # primer vnode a la derecha
        if idx == len(self._posiciones):                  # pasado el final: da la vuelta
            idx = 0
        return self._dueño[self._posiciones[idx]]

def distribucion(anillo: AnilloConsistente, claves) -> Counter:
    return Counter(anillo.nodo_para(c) for c in claves)

def desviacion_relativa(conteo: Counter) -> float:
    """Desviación típica del número de claves por nodo, relativa a la media (en %)."""
    valores = list(conteo.values())
    return statistics.pstdev(valores) / statistics.mean(valores) * 100

def fraccion_movida(antes: AnilloConsistente, despues: AnilloConsistente, claves) -> float:
    return sum(1 for c in claves if antes.nodo_para(c) != despues.nodo_para(c)) / len(claves)

if __name__ == "__main__":
    claves = [f"P-2026-{i:06d}" for i in range(1, 100_001)]
    nodos = ["inv-bcn", "inv-vlc", "inv-gir", "inv-lle"]

    for vn in (1, 10, 150):
        anillo = AnilloConsistente(nodos, vnodes=vn)
        conteo = distribucion(anillo, claves)
        print(f"vnodes={vn:>3}: {dict(conteo)}  desviación={desviacion_relativa(conteo):.1f} %")

    antes = AnilloConsistente(nodos, vnodes=150)
    despues = AnilloConsistente(nodos + ["inv-tar"], vnodes=150)
    print(f"añadir inv-tar (4->5): se mueve el {fraccion_movida(antes, despues, claves)*100:.1f} %")

    sin_vlc = AnilloConsistente(nodos, vnodes=150)
    sin_vlc.quitar_nodo("inv-vlc")
    print(f"quitar inv-vlc (4->3): se mueve el {fraccion_movida(antes, sin_vlc, claves)*100:.1f} %")
    print("reparto tras quitar inv-vlc:", dict(distribucion(sin_vlc, claves)))

Cómo funciona, línea a línea:

  • _posiciones es una lista ordenada de enteros (las posiciones de todos los vnodes) y _dueño dice a qué nodo físico pertenece cada posición. Mantener la lista ordenada con bisect.insort permite buscar el sucesor en O(log V).
  • añadir_nodo genera K posiciones hasheando nombre#i; los vnodes de un mismo nodo quedan dispersos por todo el anillo.
  • quitar_nodo elimina exactamente esas posiciones; no toca nada más, así que las claves de los demás nodos no se ven afectadas.
  • nodo_para hashea la clave, busca con bisect_right la primera posición mayor que el hash (el vecino "a la derecha") y si se sale por el final vuelve a la posición 0: ese es el anillo.
  • desviacion_relativa resume cuán uniforme es el reparto: 0 % sería perfecto.

Salida representativa (los valores exactos dependen de los hashes):

vnodes=  1: {'inv-lle': 70171, 'inv-gir': 13875, 'inv-bcn': 14486, 'inv-vlc': 1468}  desviación=106.4 %
vnodes= 10: {'inv-bcn': 32315, 'inv-gir': 32959, 'inv-vlc': 10845, 'inv-lle': 23881}  desviación=35.7 %
vnodes=150: {'inv-bcn': 24275, 'inv-gir': 27571, 'inv-vlc': 24835, 'inv-lle': 23319}  desviación=6.3 %
añadir inv-tar (4->5): se mueve el 19.2 %
quitar inv-vlc (4->3): se mueve el 24.8 %
reparto tras quitar inv-vlc: {'inv-bcn': 32671, 'inv-gir': 37988, 'inv-lle': 29341}

Tres conclusiones. Primera: sin vnodes, inv-lle se lleva el 70 % de las claves e inv-vlc el 1,5 % (un reparto inservible, y cada ejecución con otros nombres de nodo daría otro reparto igual de arbitrario); con 10 vnodes mejora y con 150 la desviación baja a un 6 %, que sigue reduciéndose con más vnodes (con 500, un 4,6 %; con 1000, un 2,3 %: la desviación cae aproximadamente con la raíz cuadrada del número de vnodes, y por eso Cassandra usó durante años 256 por nodo). Segunda: añadir el quinto nodo mueve el 19 % de las claves (frente al 80 % del módulo), el mínimo teórico de 1/5. Tercera: quitar uno de cuatro mueve exactamente sus claves (25 %), y esas claves se reparten entre los tres supervivientes, no caen sobre uno solo, gracias a que los 150 vnodes de inv-vlc tenían sucesores distintos.

Este anillo, con vnodes y con réplicas en los siguientes nodos del anillo, es el que usan Dynamo, Cassandra, Riak y el enrutamiento de muchos clientes de Memcached. Lo veremos aplicado en 04-04.

  1. Rendezvous hashing

Existe una alternativa al anillo, más sencilla de implementar y sin problemas de reparto: el rendezvous hashing o highest random weight (HRW). Para cada clave se calcula peso(nodo, clave) = hash(nodo + clave) para todos los nodos y se elige el de mayor peso. Propiedades:

  • Al quitar un nodo, solo las claves que lo tenían como ganador cambian (van a su segundo mejor): movimiento mínimo, igual que el anillo.
  • Al añadir uno, solo se mueven las claves para las que el nuevo gana: 1/(N+1) en promedio.
  • Sin vnodes: el reparto es uniforme por construcción, porque cada clave "sortea" entre todos los nodos.
  • Da gratis una lista ordenada de nodos por preferencia, útil para elegir las R réplicas (los R mejores).
  • Coste O(N) por búsqueda, frente a O(log V) del anillo: perfecto para decenas de nodos, peor para miles.
def nodo_rendezvous(clave: str, nodos: list[str]) -> str:
    return max(nodos, key=lambda n: hash_clave(f"{n}|{clave}"))

Lo usan, entre otros, el particionado de algunos balanceadores y sistemas de caché. Para Kilómetro Cero, con menos de una veintena de nodos por servicio, sería una opción perfectamente válida; el anillo es más común porque es lo que traen las bases de datos que vamos a usar.

  1. Reequilibrado de particiones

Hasta ahora hemos asignado claves directamente a nodos. Los sistemas reales suelen introducir un nivel intermedio: las claves se asignan a particiones y las particiones a nodos. Mover particiones enteras entre nodos (reequilibrado, rebalancing) es más manejable que mover claves sueltas. Hay tres esquemas:

Esquema Cómo funciona Ventajas Inconvenientes Quién lo usa
Número fijo de particiones Se crean muchas más particiones que nodos (p. ej. 1024 para 10 nodos); al añadir un nodo, este "roba" unas cuantas particiones enteras de cada nodo existente Sencillo; solo se mueven particiones completas; permite pesos Hay que acertar el número al principio: demasiadas = sobrecarga; pocas = límite de crecimiento Riak, Elasticsearch, Couchbase, Redis Cluster (16384 slots, 04-05)
Particionado dinámico Una partición que supera un tamaño (p. ej. 10 GB) se divide en dos; una que se vacía se fusiona con su vecina Se adapta al volumen; funciona con rango y con hash Un conjunto de datos nuevo empieza con 1 partición (un solo nodo trabaja): se mitiga con pre-splitting HBase, MongoDB, CockroachDB
Proporcional a los nodos Cada nodo tiene un número fijo de particiones (vnodes); añadir un nodo divide aleatoriamente particiones existentes El tamaño de partición se mantiene estable al crecer Divisiones aleatorias, requiere hash Cassandra, Ketama

Dos reglas de operación:

  • El reequilibrado debe ser gradual y limitado en ancho de banda: mover particiones satura la red y los discos de los nodos implicados, justo cuando además siguen sirviendo tráfico.
  • El reequilibrado automático es cómodo pero peligroso combinado con la detección de fallos: un nodo lento (no muerto) puede ser declarado caído, el sistema empieza a mover sus particiones, la carga extra hace que otros nodos parezcan lentos… una cascada. Muchos operadores prefieren que el sistema proponga el reequilibrio y un humano lo apruebe.

  1. Enrutamiento de peticiones y descubrimiento de particiones

Si catalogo quiere leer el stock de queso-curado, ¿a qué nodo se conecta? Es el problema de descubrimiento de servicio aplicado a particiones, y tiene tres respuestas:

flowchart LR
    subgraph a["(a) Cualquier nodo"]
        C1[Cliente] --> N1a[Nodo 2]
        N1a -- reenvía --> N2a[Nodo 4<br/>dueño]
    end
    subgraph b["(b) Capa de enrutamiento"]
        C2[Cliente] --> R[Router / proxy]
        R --> N2b[Nodo 4<br/>dueño]
    end
    subgraph c["(c) Cliente informado"]
        C3[Cliente<br/>conoce el mapa] --> N2c[Nodo 4<br/>dueño]
    end
Opción Quién conoce el mapa de particiones Ejemplo Comentario
(a) Cualquier nodo Todos los nodos (protocolo gossip) Cassandra, Riak El cliente es simple; un salto extra de red en el peor caso
(b) Capa de enrutamiento El router (a menudo con ayuda de un coordinador) mongos en MongoDB, moxi en Couchbase, proxies de Redis El router puede convertirse en cuello de botella; hay que replicarlo
(c) Cliente informado La biblioteca cliente (descarga el mapa y lo cachea) Redis Cluster (MOVED), HBase, clientes de Kafka Máximo rendimiento; el cliente debe manejar mapas obsoletos

En todos los casos el problema de fondo es el mismo: todos los participantes deben estar de acuerdo sobre qué partición vive en qué nodo, y ese acuerdo debe sobrevivir a fallos. Es exactamente el problema de consenso de 03-03, y por eso muchos sistemas delegan el mapa en un servicio de coordinación: ZooKeeper (HBase, Kafka clásico, SolrCloud) o etcd (Kubernetes, CockroachDB). Los nodos se registran en ZooKeeper/etcd, la capa de enrutamiento se suscribe a los cambios, y cuando una partición cambia de nodo el router se entera en milisegundos. Otros sistemas (Cassandra, Riak) evitan la dependencia externa y difunden el mapa por gossip, aceptando que durante unos segundos algunos nodos tengan una vista antigua.

Para Kilómetro Cero, que ya usa etcd para elegir el líder del relay outbox (relay_lider.py de 03-03), la opción natural para sus propias particiones (las réplicas de inventario inv-bcn e inv-vlc, y las que vengan) es guardar el mapa en etcd bajo /km0/inventario/particiones/ y que los clientes gRPC lo lean y se suscriban con watch. Un esbozo:

# km0/servicios/inventario/mapa_particiones.py
import etcd3, json

cliente = etcd3.client(host="etcd", port=2379)
PREFIJO = "/km0/inventario/particiones/"

def publicar(particion: str, nodo: str, lease_ttl: int = 15):
    lease = cliente.lease(lease_ttl)                     # si el nodo muere, la entrada caduca
    cliente.put(f"{PREFIJO}{particion}", json.dumps({"nodo": nodo}), lease=lease)
    return lease                                          # el nodo debe llamar a lease.refresh() periódicamente

def cargar_mapa() -> dict[str, str]:
    return {meta.key.decode().removeprefix(PREFIJO): json.loads(v)["nodo"]
            for v, meta in cliente.get_prefix(PREFIJO)}

def vigilar(al_cambiar):
    """Llama a `al_cambiar(mapa)` cada vez que una partición cambia de nodo."""
    for _ in cliente.watch_prefix(PREFIJO)[0]:
        al_cambiar(cargar_mapa())

El lease es el mismo mecanismo de 03-03: si inv-vlc deja de renovarlo, su entrada desaparece y los clientes saben que la partición no tiene dueño, sin necesidad de un detector de fallos aparte.

  1. Elegir la clave de partición en Kilómetro Cero

Con todo lo anterior, tomamos las dos decisiones que el equipo tiene pendientes. Recuerda que la clave de partición se elige por las consultas dominantes y por la distribución de la carga, y que se puede complementar con índices globales asíncronos para las consultas secundarias.

Pedidos (km0_pedidos, 40 000 pedidos/día en campaña, lectura dominante: "mis pedidos" en la app, y "pedido por id" en la confirmación):

Candidata A favor En contra Veredicto
fecha_creacion (rango) Consultas por periodo para analitica Punto caliente permanente en "hoy" (Semana de la Vendimia) Descartada
pedido_id (hash) Reparto perfecto; "pedido por id" en un salto "Mis pedidos" es scatter/gather sobre todas las particiones Solo para la tabla pedidos_por_id
cliente_id (hash) + fecha DESC (orden) "Mis pedidos" en un nodo, ya ordenados; reparto uniforme (miles de clientes) Un cliente con muchísimos pedidos (un restaurante) crea una partición grande; "pedido por id" necesita conocer el cliente Elegida como clave principal
mercado (hash) Consultas de reparto por ciudad Solo 4 valores: 4 particiones como máximo, Valencia el doble de grande Descartada como clave; sí como índice global asíncrono pedidos_por_mercado
productor_id Panel del productor Muy desigual (Huerta La Vega tiene 30 veces más pedidos que Bodega Roble Alto) Índice global asíncrono

Decisión: la clave de partición de los pedidos es cliente_id, con clustering por fecha DESC; se mantiene una segunda tabla pedidos_por_id (el patrón "una tabla por consulta" que desarrollaremos en 04-04) alimentada en la misma escritura, y los índices por mercado y por productor se materializan desde pedidos.eventos. Para el caso del cliente con demasiados pedidos se añade a la clave un cubo temporal (cliente_id + año-mes), de modo que ninguna partición crece sin límite: es el particionado compuesto del apartado 3 llevado a la clave de partición.

Stock (km0_inventario, réplicas inv-bcn/inv-vlc, contadores que se decrementan con stock.reservado):

Candidata A favor En contra Veredicto
producto_slug (hash) Cada contador en un solo nodo: decrementos atómicos sin coordinación entre nodos queso-curado en la Semana del Queso Artesano es una clave caliente Elegida; la clave caliente se trata con colas y con caché (04-05), no cambiando la partición
productor_id Un productor actualiza todo su stock en un nodo Huerta La Vega concentra el 40 % del catálogo en una partición Descartada
mercado Stock por ciudad para la web El stock es del productor, no del mercado: duplicaría contadores y exigiría transacciones entre particiones Descartada

Aquí la lección importante es que un contador que debe ser consistente (CP, 03-02) debe vivir entero en una partición: decrementar stock que está repartido entre dos nodos exigiría 2PC (03-05) en cada reserva. Por eso producto_slug gana aunque tenga claves calientes.

Errores Comunes y Consejos

  • Usar hash() de Python (o el hashCode por defecto de otros lenguajes) como hash de partición. Está aleatorizado por proceso o depende de la implementación. Usa un hash explícito y documentado (MD5, MurmurHash3, xxHash) y fija su versión.
  • Confundir particionar con replicar. Particionar sin replicar reduce la disponibilidad: cada nodo que cae se lleva su parte de los datos. Cada partición necesita su factor de replicación (04-04).
  • Elegir la clave de partición por el modelo de dominio y no por las consultas. "Los pedidos tienen id, luego la clave es pedido_id" produce un scatter/gather en la consulta más frecuente. Empieza por listar las consultas y su frecuencia.
  • Claves con pocos valores distintos (mercado, estado, tipo). Limitan el número de particiones y crean desequilibrios. Cardinalidad alta primero.
  • Ignorar las particiones que crecen sin límite (el cliente con un millón de pedidos, la flota de reparto con 2,4 millones de posiciones al día). Añade un cubo temporal a la clave.
  • Hashing consistente sin nodos virtuales. Reparto desigual y, al caer un nodo, toda su carga sobre un solo sucesor. Usa 100–200 vnodes, o rendezvous hashing.
  • Reequilibrado automático agresivo. Puede desencadenar cascadas cuando un nodo solo está lento. Limita el ancho de banda y considera aprobación manual.
  • Olvidar que el mapa de particiones es estado distribuido. Necesita consenso (ZooKeeper/etcd) o gossip, y los clientes deben tolerar mapas obsoletos (reintentar tras un MOVED o equivalente).

Consejo final: cuando dudes entre rango y hash, pregúntate si la consulta por rango es realmente necesaria en la ruta caliente o si puede servirla un índice global o el lago de datos (04-02) fuera de línea. Casi siempre es lo segundo.

Ejercicios

Ejercicio 1. Modifica anillo_consistente.py para soportar pesos: añadir_nodo(nodo, peso=1.0) debe crear int(vnodes * peso) nodos virtuales. Construye un anillo con inv-bcn (peso 2,0), inv-vlc (1,0) e inv-gir (1,0), reparte las 100 000 claves y comprueba que inv-bcn recibe aproximadamente el 50 %. ¿Qué pasa con quitar_nodo si no guardas el peso?

Ejercicio 2. Las posiciones de los repartidores (140 furgonetas como furgoneta-3, 2,4 millones de posiciones al día entre todas) se quieren guardar particionadas. Las consultas son: (a) "última posición del repartidor R" (miles por minuto, desde la web del cliente), (b) "recorrido del repartidor R entre dos horas de hoy" (soporte), (c) "todos los repartidores ahora mismo en Valencia" (panel de operaciones). Propón la clave de partición (y de ordenación si procede), indica qué consulta queda como scatter/gather o índice global, y explica por qué repartidor_id a secas genera una partición sin límite y cómo lo corriges.

Ejercicio 3. Implementa nodo_rendezvous(clave, nodos) y una función replicas_rendezvous(clave, nodos, r) que devuelva los r nodos de mayor peso. Con 5 nodos y 100 000 claves, mide (a) la desviación relativa del reparto, (b) la fracción de claves cuyo nodo principal cambia al añadir un sexto nodo, y (c) la fracción de claves cuyo conjunto de 3 réplicas cambia. Compara (b) con el resultado del anillo.

Soluciones

Solución 1:

class AnilloConsistentePonderado(AnilloConsistente):
    def __init__(self, vnodes: int = 150):
        super().__init__(vnodes=vnodes)
        self._pesos: dict[str, int] = {}          # nodo -> número real de vnodes creados

    def añadir_nodo(self, nodo: str, peso: float = 1.0) -> None:
        n = max(1, int(self.vnodes * peso))
        self._pesos[nodo] = n
        for i in range(n):
            pos = hash_clave(f"{nodo}#{i}")
            if pos not in self._dueño:
                bisect.insort(self._posiciones, pos)
                self._dueño[pos] = nodo

    def quitar_nodo(self, nodo: str) -> None:
        for i in range(self._pesos.pop(nodo, 0)):
            pos = hash_clave(f"{nodo}#{i}")
            if self._dueño.get(pos) == nodo:
                del self._dueño[pos]
                self._posiciones.remove(pos)

anillo = AnilloConsistentePonderado()
anillo.añadir_nodo("inv-bcn", 2.0); anillo.añadir_nodo("inv-vlc"); anillo.añadir_nodo("inv-gir")
print(distribucion(anillo, claves))   # inv-bcn ≈ 50 000, los otros ≈ 25 000 cada uno

Si quitar_nodo recalcula con self.vnodes en lugar del número real, para inv-bcn solo eliminaría 150 de sus 300 vnodes y dejaría en el anillo 150 posiciones que apuntan a un nodo muerto: las claves que caen en ellas irían a un nodo inexistente. Por eso hay que guardar cuántos vnodes se crearon por nodo (o recorrerlos desde _dueño).

Solución 2:

Clave de partición repartidor_id + día (por ejemplo furgoneta-3|2026-09-14), con clave de ordenación ts DESC. (a) "Última posición" es la primera fila de la partición de hoy: un nodo, lectura mínima. (b) "Recorrido entre dos horas" es un rango dentro de la misma partición, ordenado por tiempo. (c) "Todos los repartidores en Valencia ahora" no menciona repartidor: scatter/gather sobre 140 particiones sería aceptable (140 lecturas pequeñas) pero es mejor un índice global asíncrono ultima_posicion_por_mercado, actualizado con cada posición (o cada N segundos), particionado por mercado, que es lo que el panel realmente muestra. Con repartidor_id a secas, furgoneta-3 acumularía unas 17 000 posiciones diarias sin límite (más de 6 millones al año en una sola partición, que en Cassandra empezaría a degradar lecturas y compactaciones); el cubo diario acota la partición y además hace trivial el borrado de datos antiguos (se elimina la partición del día completa). Este dato era AP en la tabla de 03-02, y nada de lo anterior lo cambia: con W=1 la posición se acepta aunque falten réplicas.

Solución 3:

def nodo_rendezvous(clave, nodos):
    return max(nodos, key=lambda n: hash_clave(f"{n}|{clave}"))

def replicas_rendezvous(clave, nodos, r):
    return sorted(nodos, key=lambda n: hash_clave(f"{n}|{clave}"), reverse=True)[:r]

nodos5 = ["n1", "n2", "n3", "n4", "n5"]; nodos6 = nodos5 + ["n6"]
conteo = Counter(nodo_rendezvous(c, nodos5) for c in claves)
print("desviación:", round(desviacion_relativa(conteo), 2), "%")            # ≈ 0,3-0,6 % sin vnodes
mov = sum(nodo_rendezvous(c, nodos5) != nodo_rendezvous(c, nodos6) for c in claves) / len(claves)
print("principal cambia:", round(mov * 100, 1), "%")                         # ≈ 16,7 % (= 1/6)
mov_r = sum(set(replicas_rendezvous(c, nodos5, 3)) != set(replicas_rendezvous(c, nodos6, 3))
            for c in claves) / len(claves)
print("conjunto de réplicas cambia:", round(mov_r * 100, 1), "%")            # ≈ 50 % (= 3/6)

(a) La desviación queda en torno al 0,3 %, sin necesidad de nodos virtuales y mejor que el 6 % del anillo con 150 vnodes, porque cada clave elige entre todos los nodos de forma independiente (el anillo, en cambio, depende de lo bien repartidas que caigan las posiciones de los vnodes). (b) El nodo principal cambia para 1/6 de las claves, igual que el anillo con vnodes (el mínimo teórico) y muy lejos del 83 % del módulo. (c) Con 3 réplicas, el conjunto cambia en aproximadamente la mitad de las claves (3/6): el nuevo nodo entra entre los tres mejores con probabilidad 3/6, y en cada caso se mueve una réplica, no las tres; el volumen de datos movido sigue siendo mínimo (cada clave mueve como mucho una copia), aunque la fracción de conjuntos afectados sea mayor.

Conclusión

Particionar es repartir datos distintos entre nodos, y replicar es copiar los mismos; los sistemas reales hacen ambas cosas, replicando cada partición. Hemos visto que el reparto por rango preserva las consultas por intervalo pero concentra la carga (los pedidos de la Semana de la Vendimia escribiendo todos en la partición de "hoy"), que el reparto por hash dispersa las claves a costa de esos rangos, y que el particionado compuesto (hash del cliente, orden por fecha) recupera lo mejor de ambos dentro de cada partición. Los índices secundarios obligan a elegir entre índices locales con scatter/gather e índices globales asíncronos, y Kilómetro Cero ha elegido los segundos para reparto alimentándolos desde pedidos.eventos. La asignación ingenua hash % N mueve el 80 % de los datos al pasar de 4 a 5 nodos, como ha medido hash_modulo.py; el hashing consistente lo reduce al 20 % mínimo, y los nodos virtuales de AnilloConsistente bajan la desviación del reparto de más del 100 % a en torno al 6 % (y menos cuantos más vnodes) y reparten la carga de un nodo caído entre todos los demás. El rendezvous hashing consigue un reparto aún más uniforme sin anillo ni vnodes. Por encima de las claves, los sistemas mueven particiones enteras (fijas, dinámicas o proporcionales a los nodos) y publican el mapa de particiones a través de gossip o de un coordinador como ZooKeeper o etcd, que ya conocíamos por la elección de líder de 03-03. Y hemos fijado dos decisiones de Kilómetro Cero: pedidos particionados por cliente_id (con cubo mensual y tabla secundaria pedidos_por_id) y stock particionado por producto_slug, porque un contador CP debe vivir entero en una partición.

Con las claves repartidas, toca ver los sistemas que las guardan. Los tres próximos temas son tres formas distintas de almacenar bytes a escala: ficheros, objetos y registros de base de datos. Empezamos por la más antigua y la que más se parece a lo que ya conoces, los sistemas de archivos distribuidos, con NFS, HDFS y Ceph, y con HDFS como el lago de datos donde Kilómetro Cero guardará los eventos de pedidos.eventos que el Módulo 5 procesará en masa.

◄ Anterior
◄
Siguiente ►
►

Curso de Arquitecturas Distribuidas

Módulo 1: Introducción a los Sistemas Distribuidos

Módulo 2: Comunicación en Sistemas Distribuidos

Módulo 3: Consistencia y Replicación

Módulo 4: Almacenamiento Distribuido

Módulo 5: Computación Distribuida

Módulo 6: Seguridad en Sistemas Distribuidos

Módulo 7: Monitoreo y Mantenimiento

Módulo 8: Casos de Estudio y Aplicaciones

El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados