Sesión 62: CTCI Cap. 9 (Diseño de Sistemas) — Escalabilidad Distribuida: Consistent Hashing y Token Bucket Rate Limiting#

Tiempo estimado: 75-85 minutos. Nivel: De Junior/Trainee a Staff Specialist. Herramientas obligatorias: Hoja cuadriculada, lápiz, regla y bolígrafos de dos colores.

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

Consulta rápida: Glosario Maestro | Guía de Diagramas

Consistent Hashing (Hashing Consistente — Karger et al., 1997)#

• (a) En palabras simples (intuición): Imagina que repartes cartas entre 4 jugadores sentados en círculo. Con el método ingenuo tradicional, si un jugador va al baño, tienes que recoger todas las cartas de la mesa y volver a repartirlas desde cero a los 3 que quedan (un caos total). Con Hashing Consistente, las cartas se tiran a un aro gigante y cada quien toma las cartas que caen más cerca de su mano en sentido horario. Si un jugador se levanta, solo sus cartas pasan al vecino de al lado; los demás jugadores conservan exactamente las cartas que ya tenían.
• (b) Definición técnica paso a paso: Esquema de enrutamiento y partición de datos distribuido que mapea tanto las claves como los nodos de almacenamiento en un espacio de claves circular uniforme (anillo de enteros [0, 2⁶⁴-1]):
• Una clave se asigna al primer nodo físico cuyo hash sea mayor o igual al hash de la clave en sentido horario.
• Al añadir o eliminar un servidor, el número promedio de claves que deben migrarse es únicamente (K) / (N) (donde K es el total de claves y N es el número de servidores), a diferencia de ≈ K (N) / (N+1) en el hashing módulo tradicional.
• (c) Cómo funciona en Rust (memoria y tipos): El anillo se almacena en un árbol rojo-negro balanceado en el Heap mediante std::collections::BTreeMap<u64, String>. La búsqueda en sentido horario se ejecuta en O(log V) con el método .range(hash..).next().
• (d) Error típico de Junior: Usar hash(key) % N para balancear peticiones entre N servidores de caché (Redis/Memcached); al cambiar N (por caída de un nodo o escalado automático), el 99% de las claves cambian de servidor a la vez, provocando una tormenta de caídas de caché (Cache Stampede) que tumba las bases de datos relacionales.

Nodos Virtuales (Vnodes)#

• (a) En palabras simples (intuición): Si colocas solo 3 servidores en el aro gigante, por simple mala suerte del azar dos de ellos podrían quedar muy juntos y el tercero tendría que cargar con el 80% de todo el aro. Para solucionarlo, cada servidor físico se "disfraza" de 100 servidores virtuales distribuidos homogéneamente por todo el aro.
• (b) Definición técnica paso a paso: Técnica de replicación lógica donde cada servidor físico S se asocia con V identificadores distintos (por ejemplo: S#0, S#1, ..., S#(V-1)), insertando V puntos en el anillo. Esto fragmenta el espacio en arcos pequeños, reduciendo la varianza en la cantidad de claves asignadas a cada servidor de O(1) a O(1 / √(V)) según la Ley de los Grandes Números.
• (c) Cómo funciona en Rust (memoria y tipos): Se formatean cadenas de texto con format!("{}#{}", node, v) y se calculan sus hashes independientes para poblar el BTreeMap.
• (d) Error típico de Junior: Asignar solo 1 o 2 vnodes por servidor en producción, dejando puntos calientes (hotspots) donde un servidor consume el 90% de su CPU mientras los demás están inactivos.

Algoritmo de Control de Tasa Token Bucket#

• (a) En palabras simples (intuición): Imagina un balde con capacidad para 10 monedas. Cada segundo, una máquina arroja automáticamente 2 monedas nuevas dentro del balde. Cuando un usuario hace una petición a la API, debe sacar una moneda del balde. Si el balde tiene monedas, la petición pasa de inmediato; si el balde está vacío, la petición se rechaza con error 429 ("Demasiadas Peticiones"). Si el usuario no hace peticiones durante mucho tiempo, el balde se llena hasta su tope de 10 monedas, permitiéndole hacer una ráfaga rápida de 10 peticiones seguidas cuando regrese.
• (b) Definición técnica paso a paso: Algoritmo de regulación de tráfico (Traffic Shaping) que permite procesar ráfagas de tráfico (bursts) hasta una capacidad máxima C, mientras garantiza una tasa media sostenida de R operaciones por segundo.
• (c) Cómo funciona en Rust (memoria y tipos): Se modela con una estructura en el Stack que almacena números de punto flotante f64 para los tokens y marcas de tiempo (capacity, tokens, refill_rate_per_sec, last_refill_timestamp).
• (d) Error típico de Junior: Intentar crear un hilo de fondo (std::thread::sleep o temporizador cron) que despierte cada 10 milisegundos para sumar tokens; en servidores con millones de usuarios concurrentes, esto generaría millones de hilos y saturaría el planificador del sistema operativo.

Reposición Perezosa (Lazy Refill)#

• (a) En palabras simples (intuición): En lugar de tener a alguien vigilando el balde segundo tras segundo para echar agua, dejas el balde solo y anotas en un papel la hora exacta de la última visita. Cuando un cliente llega a pedir agua, miras tu reloj, calculas cuántos segundos han pasado desde la última vez y le agregas de golpe toda el agua que se debió haber acumulado en ese tiempo.
• (b) Definición técnica paso a paso: Técnica de optimización que computa el reabastecimiento bajo demanda exclusivamente en el momento en que se invoca allow_request:

Costo computacional: exactamente O(1) operaciones aritméticas, con cero consumo de CPU cuando no hay peticiones activas.

• (c) Cómo funciona en Rust (memoria y tipos): No requiere sincronización de hilos en modelos de actor y se calcula en nanosegundos mediante aritmética IEEE-754.
• (d) Error típico de Junior: Olvidar truncar los tokens con .min(capacity), permitiendo que un cliente acumule millones de tokens tras horas de inactividad y luego destruya el backend con un ataque DoS.

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

La Matemática de la Reasignación: Módulo vs Anillo Consistente#

Supongamos K = 1,000,000 de claves y N = 10 servidores de caché.

1. Hashing Módulo Tradicional:#

Cada clave se envía a:

Si añadimos un nuevo servidor (N_{nuevo} = 11):

¿Cuántas claves conservan su servidor original? Solo aquellas donde hash ±od{10} == hash ±od{11}, lo cual ocurre con probabilidad (1) / (10 × 11) × 10 = (1) / (11) ≈ 9.09%.

• Claves que se desubican y deben migrarse:

• Consecuencia: El 90% de los usuarios sufren caídas de sesión simultáneas y las bases de datos colapsan bajo la carga repentina.

2. Consistent Hashing con Anillo:#

El espacio total del anillo es 2⁶⁴. Al insertar el servidor número 11, este nuevo nodo se coloca en una posición del anillo y solo le arrebata una porción de claves a su vecino inmediato en sentido antihorario.

• Fracción esperada de claves reasignadas:

• El 90.91% de las claves permanecen intactas en sus servidores originales sin moverse.

3. Visualización de Arquitectura y Memoria en Rust#

Diagrama Arquitectónico de Flujo#

Consulta el diagrama vectorial:

flowchart LR
    REQ["Petición entrante key: 'user_99'"] --> HASH["hash(key) -> u64"]
    HASH --> RING["BTreeMap.range(hash..).next()"]
    RING --> NODE["Servidor Físico Asignado<br/>(Cache Node)"]
    NODE --> TB{"TokenBucket.allow_request()"}
    TB -->|Tokens >= 1| ALLOW["Procesar petición<br/>tokens -= 1"]
    TB -->|Tokens < 1| REJECT["Rechazar HTTP 429<br/>Too Many Requests"]

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

ESTADO DEL ANILLO CON 2 NODOS Y 2 VNODES CADA UNO:
Servidores: "srvA", "srvB"
Hashes de Vnodes:
  srvA#0 -> 100
  srvB#0 -> 300
  srvA#1 -> 600
  srvB#1 -> 850

Stack:
  ring: ConsistentHashRing {
    vnodes_per_node: 2,
    ring: BTreeMap { root: [ptr], len: 4 }
  }

Heap (BTreeMap Nodes):
  100: "srvA"
  300: "srvB"
  600: "srvA"
  850: "srvB"

CONSULTA: get_node("order_45")
1. hash("order_45") = 450.
2. ring.range(450..).next():
   - Compara con claves del árbol >= 450.
   - La primera coincidencia es 600 -> "srvA".
3. Clave "order_45" asignada a "srvA".

WRAP-AROUND: get_node("data_99")
1. hash("data_99") = 920.
2. ring.range(920..).next() -> None (llegó al final del rango u64).
3. ring.iter().next() -> 100 -> "srvA" (da la vuelta al inicio del anillo).

4. Implementación Canónica en Rust (Compilable con rustc --test)#

Archivo de referencia: practica-rust/dia_62.rs

use std::collections::hash_map::DefaultHasher;
use std::collections::BTreeMap;
use std::hash::{Hash, Hasher};

pub struct ConsistentHashRing {
    ring: BTreeMap<u64, String>,
    vnodes_per_node: usize,
}

impl ConsistentHashRing {
    pub fn new(vnodes_per_node: usize) -> Self {
        assert!(vnodes_per_node > 0);
        Self {
            ring: BTreeMap::new(),
            vnodes_per_node,
        }
    }

    fn hash_key<T: Hash + ?Sized>(key: &T) -> u64 {
        let mut hasher = DefaultHasher::new();
        key.hash(&mut hasher);
        hasher.finish()
    }

    pub fn add_node(&mut self, node: &str) {
        for v in 0..self.vnodes_per_node {
            let vnode_key = format!("{}#{}", node, v);
            let hash = Self::hash_key(&vnode_key);
            self.ring.insert(hash, node.to_string());
        }
    }

    pub fn remove_node(&mut self, node: &str) {
        for v in 0..self.vnodes_per_node {
            let vnode_key = format!("{}#{}", node, v);
            let hash = Self::hash_key(&vnode_key);
            self.ring.remove(&hash);
        }
    }

    pub fn get_node(&self, key: &str) -> Option<String> {
        if self.ring.is_empty() {
            return None;
        }
        let hash = Self::hash_key(key);
        if let Some((_, physical_node)) = self.ring.range(hash..).next() {
            Some(physical_node.clone())
        } else {
            self.ring.iter().next().map(|(_, node)| node.clone())
        }
    }
}

pub struct TokenBucket {
    capacity: f64,
    tokens: f64,
    refill_rate_per_sec: f64,
    last_refill_timestamp: f64,
}

impl TokenBucket {
    pub fn new(capacity: usize, refill_rate_per_sec: f64, start_time: f64) -> Self {
        let cap = capacity as f64;
        Self {
            capacity: cap,
            tokens: cap,
            refill_rate_per_sec,
            last_refill_timestamp: start_time,
        }
    }

    fn refill(&mut self, now: f64) {
        if now <= self.last_refill_timestamp {
            return;
        }
        let elapsed = now - self.last_refill_timestamp;
        let new_tokens = elapsed * self.refill_rate_per_sec;
        self.tokens = (self.tokens + new_tokens).min(self.capacity);
        self.last_refill_timestamp = now;
    }

    pub fn allow_request(&mut self, now: f64, tokens_to_consume: f64) -> bool {
        self.refill(now);
        if self.tokens >= tokens_to_consume {
            self.tokens -= tokens_to_consume;
            true
        } else {
            false
        }
    }
}

Implementación de Referencia en Python Tipado#

import bisect
import hashlib
import time
from typing import Dict, List, Optional


class ConsistentHashRingPython:
    def __init__(self, vnodes: int = 100) -> None:
        self.vnodes = vnodes
        self.ring: List[int] = []
        self.vnode_to_node: Dict[int, str] = {}

    def _hash(self, key: str) -> int:
        return int(hashlib.md5(key.encode("utf-8")).hexdigest(), 16)

    def add_node(self, node: str) -> None:
        for v in range(self.vnodes):
            h = self._hash(f"{node}#{v}")
            bisect.insort(self.ring, h)
            self.vnode_to_node[h] = node

    def get_node(self, key: str) -> Optional[str]:
        if not self.ring:
            return None
        h = self._hash(key)
        idx = bisect.bisect_right(self.ring, h)
        if idx == len(self.ring):
            idx = 0
        return self.vnode_to_node[self.ring[idx]]


class TokenBucketPython:
    def __init__(self, capacity: int, refill_rate: float) -> None:
        self.capacity = float(capacity)
        self.tokens = float(capacity)
        self.refill_rate = refill_rate
        self.last_refill = time.time()

    def allow_request(self, tokens: float = 1.0) -> bool:
        now = time.time()
        elapsed = now - self.last_refill
        self.tokens = min(self.capacity, self.tokens + (elapsed * self.refill_rate))
        self.last_refill = now

        if self.tokens >= tokens:
            self.tokens -= tokens
            return True
        return False

5. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

6. Navegación#

• ← Sesión 61: Knuth TAOCP Cap. 1 — Euclides Extendido y Diffie-Hellman
• Sesión 63: CTCI Cap. 6 — Super Egg Drop y Examen de Consolidación →
• Mapa del Curso
• Glosario Maestro
• Guía de Diagramas de Arquitectura