A senior engineer’s perspective on building highly available distributed systems Mesa de contenidos Introducción: Por qué Dynamo cambió todo El teorema del trade-off Core Architecture Components Consistent Hashing for Partitioning Replication Strategy (N, R, W) Vector Clocks for Versioning Sloppy Quorum and Hinted Handoff Resolución de conflictos: el problema de la cesta de compras Leer y escribir flujo Los árboles de Merkle para la antientropía Adhesión y detección de fallos Características: Números Reales Evolución de la estrategia de partición Comparación de Dynamo con los sistemas modernos Lo que Dynamo no te da Ejemplo de implementación práctica Lecciones clave para el diseño de sistemas Cuándo no usar sistemas de estilo dinámico Conclusión Apéndice: Problemas de diseño y enfoques Esta es una referencia de forma larga - cada sección está por su cuenta, así que no dude en saltar directamente a lo que sea más relevante para usted. Esta es una referencia de forma larga - cada sección está por su cuenta, así que no dude en saltar directamente a lo que sea más relevante para usted. Introducción: Por qué Dynamo cambió todo Cuando Amazon publicó el artículo Dynamo en 2007, no fue sólo otro ejercicio académico.Fue una solución de batalla a problemas reales a gran escala.Recuerdo cuando leí por primera vez este artículo, cambió fundamentalmente la forma en que pensaba sobre los sistemas distribuidos. Fue diseñado para soportar los servicios de alto tráfico de Amazon como el carrito de compras y los sistemas de gestión de sesiones. No hay índices secundarios, no hay juntas, no hay semántica relacional, sólo claves y valores, con un énfasis extremo en la disponibilidad y la escalabilidad. No ofrece garantías de linealización ni de orden global, incluso en la configuración de quórum más alta. Si su sistema requiere esas propiedades, Dynamo no es la herramienta adecuada. Dynamo is a distributed key-value storage system. El problema principal que enfrentaba Amazon era simple de afirmar pero brutal de resolver: Cuando alguien intenta añadir un elemento a su carrito durante una partición de red o un fallo del servidor, rechazar que escribir no es aceptable. How do you build a storage system that never says “no” to customers? The CAP Theorem Trade-off: Por qué Dynamo elige la disponibilidad Antes de sumergirse en cómo funciona Dynamo, usted necesita entender la restricción fundamental que está diseñado alrededor. ¿Qué es el teorema CAP? El teorema CAP describe un compromiso fundamental en los sistemas distribuidos: cuando se produce una partición de red, debe elegir entre consistencia y disponibilidad. Consistencia (C): Todos los nodos ven los mismos datos al mismo tiempo Disponibilidad (A): Cada solicitud recibe una respuesta (éxito o fracaso) Tolerancia de partición (P): el sistema continúa funcionando a pesar de fallas de red Una abreviatura común es “pick 2 of 3”, pero esto es una simplificación excesiva. En la práctica, las particiones de red son inevitables a escala, por lo que la verdadera decisión es: Esa es la elección de diseño real. when partitions occur (and they will), do you sacrifice consistency or availability? Los cables se cortan, los interruptores fallan, los centros de datos pierden la conectividad. ¿No puedes evitarlos, así que tienes que elegir: Consistencia o Disponibilidad? The harsh reality Las bases de datos tradicionales eligen coherencia : Traditional approach Database: "I can't guarantee all replicas are consistent, so I'll reject your write to be safe." Result: Customer sees error, cart is empty Impact: Lost revenue, poor experience Dynamo selecciona la disponibilidad : Dynamo’s approach Dynamo: "I'll accept your write with the replicas I can reach. The unreachable replica will catch up later." Result: Customer sees success, item in cart Impact: Sale continues, happy customer El comercio se visualiza When a partition occurs: Traditional Database: Choose C over A → Sacrifice Availability - ✓ All replicas always have same data - ✓ No conflicts to resolve - ❌ Rejects writes during failures - ❌ Poor customer experience - ❌ Lost revenue Dynamo: Choose A over C → Sacrifice Strong Consistency - ✓ Accepts writes even during failures - ✓ Excellent customer experience - ✓ No lost revenue - ❌ Replicas might temporarily disagree - ❌ Application must handle conflicts Ejemplo real de Amazon: Cesta de compras del Black Friday Imagina que es el Black Friday. Millones de clientes están haciendo compras. Un cable de red se corta entre los centros de datos. : With traditional database Time: 10:00 AM - Network partition occurs Result: - All shopping cart writes fail - "Service Unavailable" errors - Customers can't checkout - Twitter explodes with complaints - Estimated lost revenue: $100,000+ per minute : With Dynamo Time: 10:00 AM - Network partition occurs Result: - Shopping cart writes continue - Customers see success - Some carts might have conflicts (rare) - Application merges conflicting versions - Estimated lost revenue: $0 - A few edge cases need conflict resolution (acceptable) Por qué esta opción tiene sentido para el comercio electrónico Amazon hizo la matemática: Costo de rechazar una escritura: venta inmediata perdida ($ 50-200) Costo de aceptar una escritura conflictiva: De vez en cuando es necesario fusionar carros de compras (rara vez ocurre, fácilmente reparable) Decisión de negocio: Acepta escritos, maneja conflictos raros : Types of data where Availability > Consistency Carros de compras (fusionar adiciones contradictorias) Datos de sesión (las últimas ganancias de escritura están bien) Preferencias del usuario (eventual coherencia aceptable) Lista de los mejores vendedores (aproximadamente está bien) : Types of data where Consistency > Availability Saldo de cuenta bancaria (no puede tener saldos conflictivos) Cuenta el inventario (no se puede sobrecomprar) Los registros de transacciones (debe ser ordenado) Es por eso que Dynamo no es para todo, pero para los casos de uso de comercio electrónico de Amazon, elegir la disponibilidad sobre la fuerte consistencia fue el comité correcto. Nuancia importante: Si bien Dynamo a menudo se describe como un sistema AP, es más preciso llamarlo un sistema de consistencia ajustable. Dependiendo de su configuración de quórum R y W, puede comportarse más cerca de CP. La etiqueta AP se aplica a su configuración predeterminada / recomendada optimizada para cargas de trabajo de comercio electrónico. Si bien Dynamo a menudo se describe como un sistema AP, es más preciso llamarlo un sistema AP. Dependiendo de su configuración de quórum R y W, puede comportarse más cerca de CP. La etiqueta AP se aplica a su configuración predeterminada/recomendada optimizada para cargas de trabajo de comercio electrónico. Important nuance tunable consistency system Componentes básicos de la arquitectura 1. hashing consistente para particionamiento Déjame explicar esto con un ejemplo concreto, porque el hashing consistente es uno de esos conceptos que parece mágico hasta que lo veas en acción. El problema: el sharding tradicional basado en hash Imagina que tienes 3 servidores y quieres distribuir datos entre ellos. # Traditional approach - DON'T DO THIS def get_server(key, num_servers): hash_value = hash(key) return hash_value % num_servers # Modulo operation # With 3 servers: get_server("user_123", 3) # Returns server 0 get_server("user_456", 3) # Returns server 1 get_server("user_789", 3) # Returns server 2 This works… until you add or remove a server. Let’s see what happens when we go from 3 to 4 servers: # Before (3 servers): "user_123" → hash % 3 = 0 → Server 0 "user_456" → hash % 3 = 1 → Server 1 "user_789" → hash % 3 = 2 → Server 2 # After (4 servers): "user_123" → hash % 4 = 0 → Server 0 ✓ (stayed) "user_456" → hash % 4 = 1 → Server 1 ✓ (stayed) "user_789" → hash % 4 = 2 → Server 2 ✓ (stayed) # But wait - this is lucky! In reality, most keys MOVE: "product_ABC" → hash % 3 = 2 → Server 2 "product_ABC" → hash % 4 = 3 → Server 3 ✗ (MOVED!) : Cuando cambie el número de servidores, casi TODOS sus datos necesitan ser redistribuidos. Imagínese mover terabytes de datos solo para agregar un servidor! The disaster La solución: hashing consistente El hashing consistente resuelve esto tratando el espacio hash como un círculo (0 a 2^32 - 1, envuelto alrededor). Step 1: Place servers on the ring A cada servidor se le asigna una posición aleatoria en el anillo (llamado un "token").Piensa en esto como colocar marcadores en una pista circular. Step 2: Place data on the ring Cuando desea almacenar datos, usted: Hash la clave para obtener una posición en el anillo Caminar en sentido horario desde esa posición Almacena los datos en el primer servidor que encuentres Ejemplo visual: Anillo completo Aquí está el anillo colocado en orden. Las claves van en dirección del reloj al siguiente servidor: Una llave va en dirección del reloj hasta que llega a un servidor, y ese servidor posee la llave. Simple rule : Examples user_123 a 30° → camina a 45° → El servidor A lo posee user_456 a 150° → camina a 200° → El servidor C lo posee cart_789 a 250° → camina a 280° → Server D lo posee producto_ABC a 300° → pasa de 360°, envuelve a 0°, continúa a 45° → El servidor A lo posee Who owns what range? Servidor A (45°): posee todo de 281° a 45° (envuelve alrededor) Servidor B (120°): posee todo de 46° a 120° Servidor C (200°): posee todo desde 121° hasta 200° Servidor D (280°): posee todo desde 201° hasta 280° La magia: agregar un servidor Ahora veamos por qué esto es brillante. agregamos Server E en la posición 160°: BEFORE: Server A (45°) → owns 281°-45° Server B (120°) → owns 46°-120° Server C (200°) → owns 121°-200° ← THIS RANGE WILL SPLIT Server D (280°) → owns 201°-280° AFTER: Server A (45°) → owns 281°-45° ← NO CHANGE Server B (120°) → owns 46°-120° ← NO CHANGE Server E (160°) → owns 121°-160° ← NEW! Takes part of C's range Server C (200°) → owns 161°-200° ← SMALLER range Server D (280°) → owns 201°-280° ← NO CHANGE : Sólo las claves en el rango de 121°-160° necesitan moverse (de C a E). los servidores A, B y D no están completamente afectados! Result Optimización de Nodos Virtuales Hay un problema crítico con el enfoque básico de hashing consistente: . random distribution can be extremely uneven The Problem in Detail: Cuando asigna aleatoriamente una posición por servidor, básicamente está lanzando dardos en una tabla circular. A veces los dardos se agrupan juntos, a veces se dispersan. Te mostramos un ejemplo concreto: Scenario: 4 servers with single random tokens Server A: 10° } Server B: 25° } ← Only 75° apart! Tiny ranges Server C: 100° } Server D: 280° ← 180° away from C! Huge range Range sizes: - Server A owns: 281° to 10° = 89° (25% of ring) - Server B owns: 11° to 25° = 14° (4% of ring) ← Underutilized! - Server C owns: 26° to 100° = 74° (21% of ring) - Server D owns: 101° to 280° = 179° (50% of ring) ← Overloaded! Real-world consequences: Carga desigual: Server D maneja el 50% de todos los datos, mientras que Server B sólo maneja el 4%. La CPU, el disco y la red del servidor D se maximizan El servidor B es en su mayoría inútil (capacidad desperdiciada) La latencia del porcentaje 99.9 está dominada por la sobrecarga del servidor D Hotspot Cascading: Cuando el servidor D se vuelve lento o falla: Todos sus 50% de carga se desplazan a Server A (el siguiente en sentido horario) El servidor A se vuelve sobrecargado El rendimiento del sistema se deteriora catastróficamente Escalado ineficiente: la adición de servidores no ayuda uniformemente porque los nuevos servidores podrían aterrizar en rangos ya pequeños Visualizing the problem: : Each physical server gets multiple virtual positions (tokens). Dynamo’s solution En lugar de un lanzamiento de dardos por servidor, lanza muchos dardos.Cuanto más lanzamientos, más se hace la distribución (ley de los grandes números). How Virtual Nodes Fix the Problem: Tomemos los mismos 4 servidores, pero ahora cada servidor recibe 3 nodos virtuales (tokens) en lugar de 1: Physical Server A gets 3 tokens: 10°, 95°, 270° Physical Server B gets 3 tokens: 25°, 180°, 310° Physical Server C gets 3 tokens: 55°, 150°, 320° Physical Server D gets 3 tokens: 75°, 200°, 340° Now the ring looks like: 10° A, 25° B, 55° C, 75° D, 95° A, 150° C, 180° B, 200° D, 270° A, 310° B, 320° C, 340° D Range sizes (approximately): - Server A total: 15° + 55° + 40° = 110° (31% of ring) - Server B total: 30° + 20° + 30° = 80° (22% of ring) - Server C total: 20° + 30° + 20° = 70° (19% of ring) - Server D total: 20° + 70° + 20° = 110° (31% of ring) La carga varía del 19% al 31% en lugar del 4% al 50%. Much better! Why this works: : With more samples (tokens), the random distribution averages out. This is the law of large numbers in action. Statistics : When a server fails, its load is distributed across many servers, not just one neighbor: Granular load distribution Server A fails: - Its token at 10° → load shifts to Server B's token at 25° - Its token at 95° → load shifts to Server C's token at 150° - Its token at 270° → load shifts to Server B's token at 310° Result: The load is spread across multiple servers! : When adding a new server with 3 tokens, it steals small amounts from many servers instead of a huge chunk from one server. Smooth scaling Real Dynamo configurations: El artículo menciona diferentes estrategias evolucionadas a lo largo del tiempo. en la producción: Versiones anteriores: 100-200 nodos virtuales por servidor físico Later optimized to: Q/S tokens per node (where Q = total partitions, S = number of servers) Configuración típica: Cada servidor físico podría tener 128-256 nodos virtuales The Trade-off: Balance vs Overhead Más nodos virtuales significa una mejor distribución de la carga, pero hay un coste. What you gain with more virtual nodes: With 1 token per server (4 servers): Load variance: 4% to 50% (±46% difference) ❌ With 3 tokens per server (12 virtual nodes): Load variance: 19% to 31% (±12% difference) ✓ With 128 tokens per server (512 virtual nodes): Load variance: 24% to 26% (±2% difference) ✓✓ What it costs: Tamaño de metadatos: Cada nodo mantiene la información de enrutamiento 1 token por servidor: Track 4 entradas 128 tokens por servidor: rastrear 512 entradas Gossip overhead: Nodes intercambian información de membresía periódicamente Más tokens = más datos para sincronizar entre nodos Every second, nodes gossip their view of the ring Complejidad de reequilibrio: cuando los nodos se unen/salen Más nodos virtuales = más transferencias de particiones para coordinar Pero cada transferencia es más pequeña (lo que es realmente bueno para el bootstrapping) Dynamo’s evolution: The paper describes how Amazon optimized this over time: Strategy 1 (Initial): - 100-200 random tokens per server - Problem: Huge metadata (multiple MB per node) - Problem: Slow bootstrapping (had to scan for specific key ranges) Strategy 3 (Current): - Q/S tokens per server (Q=total partitions, S=number of servers) - Equal-sized partitions - Example: 1024 partitions / 8 servers = 128 tokens per server - Benefit: Metadata reduced to KB - Benefit: Fast bootstrapping (transfer whole partition files) Real production sweet spot: La mayoría de las implementaciones de Dynamo utilizan 128-256 nodos virtuales por servidor físico. Distribución de la carga dentro de la varianza del 10-15% (bastante buena) Metadata overhead under 100KB per node (negligible) Recuperación rápida de fallos (la carga se extiende a través de muchos nodos) De 128 a 512 tokens sólo mejora el balance de carga en 2-3%, pero duplica el tamaño de los metadatos y el tráfico de chatarra. Why not more? Los servidores físicos (en la parte superior) mapean varias posiciones virtuales (en la parte inferior) en el anillo, lo que distribuye la carga de cada servidor en diferentes partes del espacio hash. Key concept : Benefits Más de distribución de carga Cuando un servidor falla, su carga se distribuye a través de muchos servidores (no sólo un vecino) Cuando un servidor se une, roba una pequeña cantidad de muchos servidores Real-World Impact Comparison Let’s see the difference with real numbers: Traditional Hashing (3 servers → 4 servers): - Keys that need to move: ~75% (3 out of 4) - Example: 1 million keys → 750,000 keys must migrate Consistent Hashing (3 servers → 4 servers): - Keys that need to move: ~25% (1 out of 4) - Example: 1 million keys → 250,000 keys must migrate With Virtual Nodes (150 vnodes total → 200 vnodes): - Keys that need to move: ~12.5% (spread evenly) - Example: 1 million keys → 125,000 keys must migrate - Load is balanced across all servers The “Aha!” Moment La idea clave es esta: Consistent hashing decouples the hash space from the number of servers. Tradicional: servidor = hash(key) % num_servers ← num_servers está en la fórmula! Consistent: ← num_servers isn’t in the formula! server = ring.findNextClockwise(hash(key)) Los valores de hash no cambian, sólo el servidor que "tiene" el rango cambia, y sólo localmente. Piense en ello como en una pista circular con estaciones de agua (servidores).Si agregas una nueva estación de agua, los corredores sólo cambian de estación si están entre la estación antigua más cercana y la nueva. 2. Replication Strategy (N, R, W) El problema: la disponibilidad vs la coherencia Imagine you’re building Amazon’s shopping cart. A customer adds an item to their cart, but at that exact moment: One server is being rebooted for maintenance Otro servidor tiene un hiccup de red A third server is perfectly fine (La consistencia es muy fuerte): Traditional database approach Client: "Add this item to my cart" Database: "I need ALL replicas to confirm before I say yes" Server 1: ✗ (rebooting) Server 2: ✗ (network issue) Server 3: ✓ (healthy) Result: "Sorry, service unavailable. Try again later." “¿No puedo añadir artículos a mi carrito durante el Black Friday?” Customer experience This is unacceptable for e-commerce. Every rejected write is lost revenue. Dynamo’s Solution: Tunable Quorums Dynamo le da tres botones para ajustar el compromiso exacto que desea: : Number of replicas (how many copies of the data) N R: Quorum de lectura (cuántas replicas deben responder para una lectura exitosa) W: Escribir quorum (cuántas réplicas deben reconocer para una escritura exitosa) • Cuando , usted garantiza la superposición de quorum, lo que significa que al menos un nodo que recibió la escritura será consultado durante cualquier lectura. Esta superposición permite la detección de la última versión, siempre que la lógica de reconciliación identifique correctamente el reloj vectorial más alto. The magic formula R + W > N Let me show you why this matters with real scenarios: Scenario 1: Shopping Cart (Prioritize Availability) N = 3 # Three replicas for durability R = 1 # Read from any single healthy node W = 1 # Write to any single healthy node # Trade-off analysis: # ✓ Writes succeed even if 2 out of 3 nodes are down # ✓ Reads succeed even if 2 out of 3 nodes are down # ✓ Maximum availability - never reject customer actions # ✗ Might read stale data # ✗ Higher chance of conflicts (but we can merge shopping carts) What happens during failure: Client: "Add item to cart" Coordinator tries N=3 nodes: - Node 1: ✗ Down - Node 2: ✓ ACK (W=1 satisfied!) - Node 3: Still waiting... Result: SUCCESS returned to client immediately Node 3 eventually gets the update (eventual consistency) Escenario 2: Estado de la sesión (enfoque equilibrado) N = 3 R = 2 # Must read from 2 nodes W = 2 # Must write to 2 nodes # Trade-off analysis: # ✓ R + W = 4 > N = 3 → Read-your-writes guaranteed # ✓ Tolerates 1 node failure # ✓ Good balance of consistency and availability # ✗ Write fails if 2 nodes are down # ✗ Read fails if 2 nodes are down Why R + W > N enables read-your-writes: Write to W=2 nodes: [A, B] Later, read from R=2 nodes: [B, C] Because W + R = 4 > N = 3, there's guaranteed overlap! At least one node (B in this case) will have the latest data. The coordinator detects the newest version by comparing vector clocks. This guarantees seeing the latest write as long as reconciliation picks the causally most-recent version correctly. Escenario 3: Datos financieros (priorizar la coherencia) N = 3 R = 3 # Must read from ALL nodes W = 3 # Must write to ALL nodes # Trade-off analysis: # ✓ Full replica quorum — reduces likelihood of divergent versions # ✓ Any read will overlap every write quorum # ✗ Write fails if ANY node is down # ✗ Read fails if ANY node is down # ✗ Poor availability during failures Systems requiring strict transactional guarantees typically choose CP systems instead. This configuration is technically supported by Dynamo but sacrifices the availability properties that motivate using it in the first place. Configuration Comparison Table Config N R W Availability Consistency Use Case High Availability 3 1 1 ⭐⭐⭐⭐⭐ ⭐⭐ Shopping cart, wish list Balanced 3 2 2 ⭐⭐⭐⭐ ⭐⭐⭐⭐ Session state, user preferences Full Quorum 3 3 3 ⭐⭐ ⭐⭐⭐⭐⭐ High-stakes reads (not linearizable) Read-Heavy 3 1 3 ⭐⭐⭐ (reads) ⭐⭐⭐⭐ Product catalog, CDN metadata Write-Heavy 3 3 1 ⭐⭐⭐ (writes) ⭐⭐⭐ Click tracking, metrics High Availability 3 1 1 ⭐⭐ Cartón de compras, lista de deseos Balanced 3 2 2 Session state, user preferences Full Quorum 3 3 3 ⭐⭐ ⭐⭐⭐⭐⭐ High-stakes reads (not linearizable) Read-Heavy 3 1 3 Product catalog, CDN metadata Write-Heavy 3 3 1 ⭐⭐⭐ Clic para rastrear, métricas : Systems requiring strong transactional guarantees (e.g., bank account balances) typically shouldn’t use Dynamo. That said, some financial systems do build on Dynamo-style storage for their persistence layer while enforcing stronger semantics at the application or business logic layer. Note on financial systems Los sistemas que requieren fuertes garantías de transacciones (por ejemplo, saldos de cuentas bancarias) normalmente no deben usar Dynamo.Algunos sistemas financieros se basan en el almacenamiento de estilo Dynamo para su capa de persistencia, al tiempo que imponen una semántica más fuerte en la capa de aplicación o lógica empresarial. Note on financial systems The Key Insight La mayoría de los sistemas utilizan porque : N=3, R=2, W=2 : Can tolerate up to 2 replica failures before permanent data loss (assuming independent failures and no correlated outages). Durability : Tolerates 1 node failure for both reads and writes Availability Consistencia: R + W > N garantiza que los quórums de lectura y escritura se sobrepasan, permitiendo el comportamiento de lectura-escribir en ausencia de escritos simultáneos. : Don’t wait for the slowest node (only need 2 out of 3) Performance Real production numbers from the paper: Amazon’s shopping cart service during peak (holiday season): Configuración: N = 3, R = 2, W = 2 Handled tens of millions of requests Más de 3 millones de cheques en un solo día No hay tiempo de inactividad, incluso con fallas del servidor Este enfoque ajustable es lo que ha hecho que Dynamo sea revolucionario.No estás atrapado con un tamaño que se ajusta a todo, lo ajustes en función de tus requisitos empresariales reales. Relojes vectoriales para versiones El problema: detectar la causalidad en los sistemas distribuidos Cuando varios nodos pueden aceptar escritos de forma independiente, debe responder a una pregunta crítica: Are these two versions of the same data related, or were they created concurrently? Why timestamps don’t work: Scenario: Two users edit the same shopping cart simultaneously User 1 at 10:00:01.500 AM: Adds item A → Writes to Node X User 2 at 10:00:01.501 AM: Adds item B → Writes to Node Y Physical timestamp says: User 2's version is "newer" Reality: These are concurrent! Both should be kept! Problem: - Clocks on different servers are NEVER perfectly synchronized - Clock skew can be seconds or even minutes - Network delays are unpredictable - Physical time doesn't capture causality What we really need to know: Version A happened before Version B? → B can overwrite A Version A and B are concurrent? → Keep both, merge later Version A came from reading Version B? → We can track this! La solución: relojes vectoriales Un reloj vectorial es una estructura de datos simple: una lista de pairs that tracks which nodes have seen which versions. (node_id, counter) The rules: Cuando un nodo escribe datos, incrementa su propio contador Cuando un nodo lee datos, obtiene el reloj vectorial When comparing two vector clocks: Si todos los contadores en A ≤ contadores en B → A es un antepasado de B (B es más reciente) Si algunos contadores en A > B y algunos B > A → A y B son simultáneos (conflicto!) Ejemplo paso a paso Let’s trace a shopping cart through multiple updates: Breaking down the conflict: D3: [Sx:2, Sy:1] vs D4: [Sx:2, Sz:1] Comparing: - Sx: 2 == 2 ✓ (equal) - Sy: 1 vs missing in D4 → D3 has something D4 doesn't - Sz: missing in D3 vs 1 → D4 has something D3 doesn't Conclusion: CONCURRENT! Neither is an ancestor of the other. Both versions must be kept and merged. Características del mundo real El artículo de Dynamo informa de la siguiente distribución de conflictos medida a lo largo de las 24 horas de tráfico de carrito de compras de la producción de Amazon. Estos números reflejan la carga de trabajo específica de Amazon - alta relación lectura / escritura, principalmente sesiones de usuario único - y no debe asumirse generalizar a todas las implementaciones de Dynamo: 99.94% - Single version (no conflict) 0.00057% - 2 versions 0.00047% - 3 versions 0.00009% - 4 versions ¡Los conflictos son raros en la práctica! Key insight Why conflicts happen: No suele ser debido a fallas de red Mostly from concurrent writers (often automated processes/bots) Los usuarios humanos rara vez crean conflictos porque son lentos en comparación con la velocidad de la red The Size Problem Vector clocks can grow unbounded if many nodes coordinate writes. Dynamo’s solution: cuando el reloj supera un umbral de tamaño. truncate the oldest entries // When vector clock exceeds threshold (e.g., 10 entries) // Remove the oldest entry based on wall-clock timestamp vectorClock = { 'Sx': {counter: 5, timestamp: 1609459200}, 'Sy': {counter: 3, timestamp: 1609459800}, 'Sz': {counter: 2, timestamp: 1609460400}, // ... 10 more entries } // If size > 10, remove entry with oldest timestamp // ⚠ Risk: Dropping an entry collapses causality information. // Two versions that were causally related may now appear // concurrent, forcing the application to resolve a conflict // that didn't actually exist. In practice, Amazon reports // this has not been a significant problem — but it is a // real theoretical risk in high-churn write environments // with many distinct coordinators. Sloppy Quorum y Hinted Handoff El problema: los quórums estrictos matan la disponibilidad Los sistemas de quórum tradicionales son rígidos e imperdonables. Traditional strict quorum: Your data is stored on nodes: A, B, C (preference list) Write requirement: W = 2 Scenario: Node B is down for maintenance Coordinator: "I need to write to 2 nodes from {A, B, C}" Tries: A ✓, B ✗ (down), C ✓ Result: SUCCESS (got 2 out of 3) Scenario: Nodes B AND C are down Coordinator: "I need to write to 2 nodes from {A, B, C}" Tries: A ✓, B ✗ (down), C ✗ (down) Result: FAILURE (only got 1 out of 3) Customer: "Why can't I add items to my cart?!" 😡 The problem: Si esos nodos específicos están abajo, el sistema se vuelve indisponible. Strict quorums require specific nodes Real scenario at Amazon: Black Friday, 2:00 PM - Datacenter 1: 20% of nodes being rebooted (rolling deployment) - Datacenter 2: Network hiccup (1-2% packet loss) - Traffic: 10x normal load With strict quorum: - 15% of write requests fail - Customer support phones explode - Revenue impact: Millions per hour La solución: Sloppy Quorum Dynamo relaja el requisito de quórum: “Write to the first N healthy nodes in the preference list, walking further down the ring if needed.” Preference list for key K: A, B, C But B is down... Sloppy Quorum says: "Don't give up! Walk further down the ring: A, B, C, D, E, F, ..." Coordinator walks until N=3 healthy nodes are found: A, C, D (D is a temporary substitute for B) How Hinted Handoff Works When a node temporarily substitutes for a failed node, it stores a “hint” with the data. Proceso Handoff detallado Step 1: Detect failure and substitute def write_with_hinted_handoff(key, value, N, W): preference_list = get_preference_list(key) # [A, B, C] healthy_nodes = [] for node in preference_list: if is_healthy(node): healthy_nodes.append((node, is_hint=False)) # If we don't have N healthy nodes, expand the list if len(healthy_nodes) < N: extended_list = get_extended_preference_list(key) for node in extended_list: if node not in preference_list and is_healthy(node): healthy_nodes.append((node, is_hint=True)) if len(healthy_nodes) >= N: break # Write to first N healthy nodes acks = 0 for node, is_hint in healthy_nodes[:N]: if is_hint: # Store with hint metadata intended_node = find_intended_node(preference_list, node) success = node.write_hinted(key, value, hint=intended_node) else: success = node.write(key, value) if success: acks += 1 if acks >= W: return SUCCESS return FAILURE Step 2: Background hint transfer # Runs periodically on each node (e.g., every 10 seconds) def transfer_hints(): hints_db = get_hinted_replicas() for hint in hints_db: intended_node = hint.intended_for if is_healthy(intended_node): try: intended_node.write(hint.key, hint.value) hints_db.delete(hint) log(f"Successfully transferred hint to {intended_node}") except: log(f"Will retry later for {intended_node}") Why This Is Brilliant Durability maintained: Even though B is down: - We still have N=3 copies: A, C, D - Data won't be lost even if another node fails - System maintains durability guarantee Availability maximized: Client perspective: - Write succeeds immediately - No error message - No retry needed - Customer happy Traditional quorum would have failed: - Only 2 nodes available (A, C) - Need 3 for N=3 - Write rejected - Customer sees error Eventual consistency: Timeline: T=0: Write succeeds (A, C, D with hint) T=0-5min: B is down, but system works fine T=5min: B recovers T=5min+10sec: D detects B is back, transfers hint T=5min+11sec: B has the data, D deletes hint Result: Eventually, all correct replicas have the data Ejemplo de configuración // High availability configuration const config = { N: 3, // Want 3 replicas W: 2, // Only need 2 ACKs to succeed R: 2, // Read from 2 nodes // Sloppy quorum allows expanding preference list sloppy_quorum: true, // How far to expand when looking for healthy nodes max_extended_preference_list: 10, // How often to check for hint transfers hint_transfer_interval: 10_seconds, // How long to keep trying to transfer hints hint_retention: 7_days }; Impacto en el mundo real De la experiencia de producción de Amazon: During normal operation: Handoff rara vez desencadenado Most writes go to preferred nodes La base de datos de Hints es en su mayoría vacía During failures: Scenario: 5% of nodes failing at any time (normal at Amazon's scale) Without hinted handoff: - Write success rate: 85% - Customer impact: 15% of cart additions fail With hinted handoff: - Write success rate: 99.9%+ - Customer impact: Nearly zero During datacenter failure: Scenario: Entire datacenter unreachable (33% of nodes) Without hinted handoff: - Many keys would lose entire preference list - Massive write failures - System effectively down With hinted handoff: - Writes redirect to other datacenters - Hints accumulate temporarily - When datacenter recovers, hints transfer - Zero customer-visible failures El trade-off Benefits: ✓ Maximum write availability ✓ Durabilidad mantenida durante fallos Recuperación automática cuando los nodos vuelven Sin necesidad de intervención manual Costs: Incoherencia temporal (datos no en los nodos “correctos”) ✗ Extra storage for hints database Ancho de banda de fondo para transferencias de pistas Un código un poco más complejo Handoff indicado proporciona durabilidad temporal, no replicación permanente.Si un nodo de reemplazo (como D) falla antes de que pueda transferir su indicio de vuelta a B, el número de réplicas verdaderas cae por debajo de N hasta que la situación se resuelva. The availability benefits far outweigh the costs for e-commerce workloads. Amazon’s verdict: Resolución de conflictos: el problema de la cesta de compras Let’s talk about the most famous example from the paper: the shopping cart. This is where rubber meets road. ¿Qué es un conflicto (y por qué ocurre)? A ocurre cuando dos escritos ocurren a la misma clave en nodos diferentes, sin que ni uno escriba "conocendo" al otro. ¡Esto sólo es posible porque Dynamo acepta escritos incluso cuando los nodos no pueden comunicarse, ¡lo cual es todo el punto! conflict Here’s a concrete sequence of events that creates a conflict: Timeline: T=0: Customer logs in. Cart has {shoes} on all 3 nodes. T=1: Network partition: Node1 can't talk to Node2. T=2: Customer adds {jacket} on their laptop → goes to Node1. Cart on Node1: {shoes, jacket} ← Vector clock: [N1:2] T=3: Customer adds {hat} on their phone → goes to Node2. Cart on Node2: {shoes, hat} ← Vector clock: [N2:2] T=4: Network heals. Node1 and Node2 compare notes. Node1 says: "I have version [N1:2]" Node2 says: "I have version [N2:2]" Neither clock dominates the other → CONFLICT! Ninguna de las versiones es “errónea” —ambas representan acciones reales que el cliente tomó.El trabajo de Dynamo es detectar esta situación (a través de relojes vectoriales) y la superficie para que la solicitud pueda decidir qué hacer. both versions ¿Qué hace la aplicación con un conflicto? Esta es la parte crucial que el documento le delega: Dynamo te da todas las versiones simultáneas; tu código decide cómo fusionarlas. the application must resolve conflicts using business logic For the shopping cart, Amazon chose a La razón es simple: perder un artículo de la cesta de un cliente (perder una venta) es peor que mostrar ocasionalmente un artículo estancado que ya han eliminado. union merge Conflict versions: Version A (from Node1): {shoes, jacket} Version B (from Node2): {shoes, hat} Merge strategy: union Merged cart: {shoes, jacket, hat} ← All items preserved Here’s the actual reconciliation code: from __future__ import annotations from dataclasses import dataclass, field class VectorClock: def __init__(self, clock: dict[str, int] | None = None): self.clock: dict[str, int] = clock.copy() if clock else {} def merge(self, other: "VectorClock") -> "VectorClock": """Merged clock = max of each node's counter across both versions.""" all_keys = set(self.clock) | set(other.clock) merged = {k: max(self.clock.get(k, 0), other.clock.get(k, 0)) for k in all_keys} return VectorClock(merged) def __repr__(self): return f"VectorClock({self.clock})" @dataclass class ShoppingCart: items: list[str] = field(default_factory=list) vector_clock: VectorClock = field(default_factory=VectorClock) @staticmethod def reconcile(carts: list["ShoppingCart"]) -> "ShoppingCart": if len(carts) == 1: return carts[0] # No conflict, nothing to do # Merge strategy: union of all items (never lose additions). # This is Amazon's choice for shopping carts. # A different application might choose last-write-wins or something else. all_items: set[str] = set() merged_clock = VectorClock() for cart in carts: all_items.update(cart.items) # Union: keep everything merged_clock = merged_clock.merge(cart.vector_clock) return ShoppingCart(items=sorted(all_items), vector_clock=merged_clock) # Example conflict scenario cart1 = ShoppingCart(items=["shoes", "jacket"], vector_clock=VectorClock({"N1": 2})) cart2 = ShoppingCart(items=["shoes", "hat"], vector_clock=VectorClock({"N2": 2})) # Dynamo detected a conflict and passes both versions to our reconcile() reconciled = ShoppingCart.reconcile([cart1, cart2]) print(reconciled.items) # ['hat', 'jacket', 'shoes'] — union! The Deletion Problem (Why This Gets Tricky) La estrategia de la Unión tiene un caso desagradable: . deleted items can come back from the dead T=0: Cart: {shoes, hat} T=1: Customer removes hat → Cart: {shoes} Clock: [N1:3] T=2: Network partition — Node2 still has old state T=3: Some concurrent write to Node2 Clock: [N2:3] T=4: Network heals → conflict detected T=5: Union merge: {shoes} ∪ {shoes, hat} = {shoes, hat} Result: Hat is BACK! Customer removed it, but it reappeared. Amazon acepta explícitamente este compromiso.Un elemento “ghost” en una cesta es una molestia menor.Perder una venta de cesta durante una venta de Black Friday es una pérdida de ingresos. Nota de profundidad de ingeniería: La lógica de fusión debe ser específica para el dominio y cuidadosamente diseñada. La adición de elementos es conmutativa (orden no importa) y fácil de fusionar. La eliminación de elementos no es - una eliminación en una rama simultánea puede ser ignorada en silencio durante una fusión basada en la unión. Esto es un compromiso intencional en el diseño de Dynamo, pero significa que la aplicación debe razonar cuidadosamente sobre la semántica de añadir vs. eliminar. Si sus datos no respaldan naturalmente las fusiones de la unión (por ejemplo, un contador, la dirección de un usuario), necesita una estrategia diferente -como CRDTs, ganancias de última escritura con timestamps, o simplemente rechazando escritos simultáneos para ese tipo de datos. Nota de profundidad de ingeniería: La lógica de fusión debe ser específica para el dominio y cuidadosamente diseñada. La adición de elementos es conmutativa (orden no importa) y fácil de fusionar. La eliminación de elementos no es - una eliminación en una rama simultánea puede ser ignorada en silencio durante una fusión basada en la unión. Esto es un compromiso intencional en el diseño de Dynamo, pero significa que la aplicación debe razonar cuidadosamente sobre la semántica de añadir vs. eliminar. Si sus datos no respaldan naturalmente las fusiones de la unión (por ejemplo, un contador, la dirección de un usuario), necesita una estrategia diferente -como CRDTs, ganancias de última escritura con timestamps, o simplemente rechazando escritos simultáneos para ese tipo de datos. Leer y escribir flujo Los diagramas anteriores muestran el flujo de alto nivel, pero caminemos por lo que realmente sucede paso a paso durante una lectura y una escritura. Escribe el camino Step-by-step narration of a PUT request: El cliente envía la solicitud a cualquier nodo (a través de un balanceador de carga) o directamente al coordinador. Se determina el coordinador: este es el primer nodo de la lista de preferencias para la posición de hash de la clave en el anillo. El reloj vectorial se actualiza: el coordinador incrementa su propio contador en el reloj vectorial, creando una nueva versión. El coordinador escribe localmente, luego los fans envían la escritura a los otros nodos N-1 en la lista de preferencias simultáneamente. El coordinador espera el reconocimiento de W. No espera a que todos los N — sólo el primer W para responder. Los nodos restantes que aún no han respondido recibirán la escritura al final (o a través de handoff indicado si están abajo). to the client. From the client’s perspective, the write is done. Once W ACKs arrive, the coordinator returns 200 OK : The client gets a success response as soon as W nodes confirm. The other (N – W) nodes will receive the write asynchronously. This is why the system is “eventually consistent”—all nodes tener los datos, simplemente no necesariamente al mismo tiempo. Key insight about the write path Will Leer el camino Step-by-step narration of a GET request: El cliente envía la solicitud al coordinador para esa clave. El coordinador envía solicitudes de lectura a todos los nodos N en la lista de preferencias simultáneamente (no solo R). El coordinador vuelve tan pronto como los nodos R hayan respondido, sin esperar a los más lentos. The coordinator checks all the vector clocks: Compare the versions returned. If all versions are identical → return the single version immediately. If one version’s clock dominates the others (it’s causally “newer”) → return that version. If versions are concurrent (neither clock dominates) → return to the client, which must merge them. all versions La reparación de lectura ocurre en el fondo: si el coordinador notó que cualquier nodo devolvió una versión estancada, envía la versión más reciente a ese nodo para actualizarla. Because Dynamo is a general-purpose storage engine. It doesn’t know whether you’re storing a shopping cart, a user profile, or a session token. Only knows how to merge two conflicting versions in a way that makes business sense. The coordinator hands you the raw concurrent versions along with the vector clock context, and you do the right thing for your use case. Why does the client receive the conflict instead of the coordinator resolving it? Su aplicación : cuando el cliente escribe la versión fusionada de nuevo, debe incluir el contexto (el reloj vector fusionado). Esto dice a Dynamo que la nueva escritura ha "visto" todas las versiones simultáneas, por lo que el conflicto se resuelve. concurrent write on top of the still-unresolved conflict. The vector clock context is the key to closing the loop otro Merkle Trees for Anti-Entropy El problema: ¿Cómo sabes cuándo las réplicas están fuera de sincronización? After a node recovers from a failure, it may have missed some writes. After a network partition heals, two replicas might diverge. How does Dynamo detect and fix these differences? El enfoque de fuerza bruta sería: “Cada hora, compare cada llave en Node A contra Node B, y sincronice cualquier cosa que sea diferente.” pero a escala de Amazon, un solo nodo podría almacenar cientos de millones de llaves. La idea principal: en lugar de comparar las claves individuales, comparar Si el hash coincide, ese grupo entero es idéntico: salta hacia abajo. Dynamo uses Merkle trees to solve this efficiently. Haces de grupos de claves Importante: la sincronización del árbol de Merkle es un mecanismo antientropía de fondo. No está en el camino de lectura / escritura caliente. Las lecturas y las escrituras normales usan relojes vectoriales y quórums para la versión. Los árboles de Merkle son para el proceso de reparación que se ejecuta periódicamente en el fondo para capturar cualquier inconsistencia que haya salido. Merkle tree sync es una No está en el camino de lectura / escritura caliente. Las lecturas y escrituras normales usan relojes vectoriales y quórums para la versión. árboles de Merkle son para el proceso de reparación que se ejecuta periódicamente en el fondo para capturar cualquier inconsistencia que haya escapado. Important background anti-entropy Cómo se construye un árbol de Merkle Each node builds a Merkle tree over its data, organized by key ranges: Los nodos de hoja contienen el hash de un pequeño rango de claves de datos reales (por ejemplo, el hash de todos los valores de las claves k1, k2, k3). Los nodos internos contienen el hash de los hash de sus hijos. is a single hash representing the data on the node. The root all Cómo dos nodos se sincronizan usando árboles de Merkle When Node A and Node B want to check if they’re in sync: : Compara las hashes de raíz. Si son las mismas, todo es idéntico. ¡Hacido! (No hay tráfico de red para los propios datos.) Step 1 : Si las raíces difieren, compare a sus hijos izquierdistas. Step 2 : Keep descending only into subtrees where hashes differ, until you reach the leaf nodes. Step 3 : Sync only the specific keys in the differing leaf nodes. Step 4 Example: Comparing two nodes Node A root: abc789 ← differs from Node B! Node B root: abc788 Compare left subtrees: Node A left: xyz123 Node B left: xyz123 ← same! Skip entire left half. Compare right subtrees: Node A right: def456 Node B right: def457 ← differs! Go deeper. Compare right-left subtree: Node A right-left: ghi111 Node B right-left: ghi111 ← same! Skip. Compare right-right subtree: Node A right-right: jkl222 Node B right-right: jkl333 ← differs! These are leaves. → Sync only the keys in the right-right leaf range (e.g., k10, k11, k12) Instead of comparing all 1 million keys, we compared 6 hashes and synced only 3 keys! : Synchronization process in code def sync_replicas(node_a, node_b, key_range): """ Efficiently sync two nodes using Merkle trees. Instead of comparing all keys, we compare hashes top-down. Only the ranges where hashes differ need actual key-level sync. """ tree_a = node_a.get_merkle_tree(key_range) tree_b = node_b.get_merkle_tree(key_range) # Step 1: Compare root hashes first. # If they match, every key in this range is identical — nothing to do! if tree_a.root_hash == tree_b.root_hash: return # Zero data transferred — full match! # Step 2: Recursively find differences by traversing top-down. # Only descend into subtrees where hashes differ. differences = [] stack = [(tree_a.root, tree_b.root)] while stack: node_a_subtree, node_b_subtree = stack.pop() if node_a_subtree.hash == node_b_subtree.hash: continue # This whole subtree matches — skip it! if node_a_subtree.is_leaf: # Found a differing leaf — these keys need syncing differences.extend(node_a_subtree.keys) else: # Not a leaf yet — recurse into children for child_a, child_b in zip(node_a_subtree.children, node_b_subtree.children): stack.append((child_a, child_b)) # Step 3: Sync only the specific keys that differed at leaf level. # This might be a handful of keys, not millions. for key in differences: sync_key(node_a, node_b, key) Why This Is Efficient El poder de los árboles de Merkle es que el número de comparaciones de hash que necesitas escala con la (logarithmic in the number of keys), not the number of keys themselves. La profundidad del árbol Node with 1,000,000 keys: Naive approach: Compare 1,000,000 keys individually Cost: 1,000,000 comparisons Merkle tree: Compare O(log N) hashes top-down Tree depth ≈ 20 levels Cost: 20 comparisons to find differences Then sync only the differing leaves (~few keys) Speedup: ~50,000x fewer comparisons! Y críticamente, si dos nodos son (que casi siempre es cierto en un clúster sano), las hashes de raíz a menudo coinciden completamente y los datos cero necesitan ser transferidos. mostly in sync Adhesión y detección de fallos Dynamo utiliza un protocolo de chatarra para la gestión de la afiliación. Cada nodo intercambia periódicamente información de afiliación con compañeros aleatorios. No hay nodo principal - toda la coordinación es completamente descentralizada. Miembros basados en Gossip Puntos clave de diseño Cada nodo mantiene su propia vista de la afiliación al clúster. No hay registro central, por lo que no hay un único punto de fallo para los datos de afiliación. No single coordinator Dynamo utiliza un detector de fallos basado en la acumulación (similar a Phi Accrual). En lugar de un juicio binario “vivo/muerto”, los nodos mantienen una que aumenta cuanto más tiempo un compañero no responde. Esto evita falsos positivos de los hiccups transitorios de la red. Failure suspicion vs. detection Nivel de sospecha Node A's view of Node B: - Last heartbeat: 3 seconds ago → Suspicion low → Healthy - Last heartbeat: 15 seconds ago → Suspicion rising → Likely slow/degraded - Last heartbeat: 60 seconds ago → Suspicion high → Treat as failed Nuevos nodos contactan con un nodo de semilla para unirse, luego el rumor propaga su presencia al resto del clúster.La membresía del anillo es eventualmente consistente - los diferentes nodos pueden tener vistas ligeramente diferentes del anillo momentáneamente, lo que es aceptable. Decentralized bootstrapping Características: Números Reales The paper provides fascinating performance data. Let me break it down: Distribución de la latencia Metric | Average | 99.9th Percentile --------------------|---------|------------------ Read latency | ~10ms | ~200ms Write latency | ~15ms | ~200ms Key insight: 99.9th percentile is ~20x the average! El porcentaje 99.9 es afectado por: Why the huge gap? Garbage collection pauses Disk I/O variations Red Jitter Desequilibrio de carga Es por eso que los SLA de Amazon se especifican en el porcentaje 99.9, no en el promedio. Versiones de conflicto A partir de las 24 horas de tráfico de carrozas de la producción de Amazon (por el papel de Dynamo).Toma en cuenta que estas reflejan las características específicas de la carga de trabajo de Amazon, no una base universal: 99.94% - Saw exactly one version (no conflict) 0.00057% - Saw 2 versions 0.00047% - Saw 3 versions 0.00009% - Saw 4 versions Los conflictos son raros en la práctica; a menudo son causados por escritores simultáneos (robots), no por fracasos. Takeaway Evolución de la estrategia de partición Dynamo evolucionó a través de tres estrategias de partición.Esta evolución nos enseña lecciones importantes: Strategy 1: Random Tokens (Initial) Problem: Random token assignment → uneven load Problem: Adding nodes → expensive data scans Problem: Can't easily snapshot the system : La asignación aleatoria de token suena elegante, pero es una pesadilla en la práctica. Cada nodo obtiene una posición aleatoria en el anillo, lo que significa rangos de propiedad de datos muy diferentes y distribución de carga desigual. Operational lesson Estrategia 2: Particiones de tamaño igual + Tokens aleatorios Improvement: Decouples partitioning from placement Problem: Still has load balancing issues Estrategia 3: Tokens Q/S por nodo – particiones de tamaño igual + colocación determinista (current) What Q and S mean: Q = el número total de particiones fijas en las que se divide el anillo (por ejemplo, 1024).Piensa en estas como piezas de tamaño igual, pre-cortadas del espacio hash que nunca cambian de forma. S = el número de servidores físicos actualmente en el clúster (por ejemplo, 8). Q/S = cuántas de esas particiones fijas es responsable cada servidor (por ejemplo, 1024 / 8 = 128 particiones por servidor). El cambio clave de las estrategias anteriores: el anillo se divide ahora en particiones Q fijas de tamaño igual Los servidores ya no reciben posiciones aleatorias - cada uno de ellos posee exactamente las particiones Q/S, distribuidas uniformemente alrededor del anillo. Primero Example: Q=12 partitions, S=3 servers Ring divided into 12 equal slices (each covers 30° of the 360° ring): Partition 1: 0°– 30° → Server A Partition 2: 30°– 60° → Server B Partition 3: 60°– 90° → Server C Partition 4: 90°–120° → Server A Partition 5: 120°–150° → Server B Partition 6: 150°–180° → Server C ...and so on, round-robin Each server owns exactly Q/S = 12/3 = 4 partitions → perfectly balanced. When a 4th server joins (S becomes 4): New Q/S = 12/4 = 3 partitions per server. Each existing server hands off 1 partition to the new server. Only 3 out of 12 partitions move — the rest are untouched. Esta evolución, desde tokens aleatorios a particiones fijas de tamaño igual con propiedad equilibrada, es uno de los aprendizajes operativos más instructivos de Dynamo.El enfoque temprano priorizó la simplicidad de la implementación; el enfoque posterior priorizó la simplicidad operativa y la predictibilidad. Comparing Dynamo to Modern Systems System Consistency Model Use Case Dynamo Influence Cassandra Tunable (N, R, W) Time-series, analytics Direct descendant — heavily inspired by Dynamo, uses same consistent hashing and quorum concepts Riak Tunable, vector clocks Key-value store Closest faithful Dynamo implementation Amazon DynamoDB Eventually consistent by default Managed NoSQL DynamoDB is a completely different system internally, with no vector clocks and much simpler conflict resolution. Shares the name and high-level inspiration only. ⚠️ Not the same as Dynamo! Voldemort Tunable LinkedIn's data store Open-source Dynamo implementation Google Spanner Linearizable Global SQL Opposite choice to Dynamo — prioritizes CP via TrueTime clock synchronization Redis Cluster Eventually consistent Caching, sessions Uses consistent hashing; much simpler conflict resolution Cassandra Conexión (N, R, W) Time-series, analytics Direct descendant — heavily inspired by Dynamo, uses same consistent hashing and quorum concepts Riak El reloj vectorial, el reloj vectorial Tienda de valor clave La implementación más fiel de Dynamo Amazon DynamoDB Consistente por defecto Gestión de NoSQL DynamoDB es un sistema completamente diferente internamente, sin relojes vectoriales y resolución de conflictos mucho más simple. ⚠️ Not the same as Dynamo! Voldemort Túnel Tienda de datos de LinkedIn Implementación de Dynamo de código abierto Google Spanner linealidad SQL global Opción opuesta a Dynamo: prioriza CP a través de la sincronización de relojes TrueTime Redis Cluster Al fin y al cabo coherente Caching, sesiones Utiliza hashing consistente; resolución de conflictos mucho más simple La confusión de DynamoDB: Muchos ingenieros confunden Amazon DynamoDB con el papel de Dynamo. Son muy diferentes. DynamoDB es un servicio gestionado optimizado para la simplicidad operativa. No expone relojes vectoriales, no utiliza el mismo esquema de partición, y utiliza un modelo de consistencia propietario. El documento se trata del motor de almacenamiento interno de Dynamo que precede a DynamoDB. La confusión de DynamoDB: Muchos ingenieros confunden Amazon DynamoDB con el papel de Dynamo. Son muy diferentes. DynamoDB es un servicio gestionado optimizado para la simplicidad operativa. No expone relojes vectoriales, no utiliza el mismo esquema de partición, y utiliza un modelo de consistencia propietario. El documento se trata del motor de almacenamiento interno de Dynamo que precede a DynamoDB. Lo que Dynamo no te da Every senior engineer blog should be honest about limitations. Here’s what Dynamo explicitly trades away: No hay transacciones: las operaciones son solo con una llave, no se pueden actualizar varias claves de forma atómica. No hay índices secundarios: sólo puede buscar datos por su clave primaria (al menos en el diseño original). No se agrega: Es una tienda de valor clave. No hay lenguaje de consulta. No hay orden global: los eventos entre diferentes claves no tienen orden garantizado. No linearizabilidad: Incluso en R=W=N, Dynamo no proporciona lecturas linearizables. No hay resolución automática de conflictos: el sistema detecta los conflictos y los presenta a la aplicación.La aplicación debe resolverlos.Si sus ingenieros no entienden esto, tendrás errores de datos sutiles. Coste de reparación a escala: El proceso de antientropía (reconciliación de árboles de Merkel) no es gratuito. Crecimiento del reloj vectorial: En entornos de escritura de alto grado con muchos coordinadores, los relojes vectoriales pueden crecer lo suficientemente grandes como para requerir truncamiento, lo que introduce una posible pérdida de causalidad. Comprender estas limitaciones es crucial para el funcionamiento exitoso de los sistemas de estilo Dynamo en la producción. Ejemplo de implementación práctica A continuación se muestra una implementación de Python autosuficiente de los conceptos básicos de Dynamo. Se simplifica intencionalmente -no hay red real, no hay persistencia- pero modela fielmente cómo interactúan los relojes vectoriales, el anillo de hash consistente, las lecturas/escrituras de quórum y la detección de conflictos. Capítulo 1: El reloj vectorial El clase es la base del seguimiento de versiones. es sólo un mapeo de diccionario Dos operaciones clave: VectorClock node_id → counter — bump our own counter when we write increment(node) — check if one clock is causally “after” another; if neither dominates, the writes were concurrent (conflict) dominates(other) from __future__ import annotations from dataclasses import dataclass, field from typing import Optional class VectorClock: """ Tracks causality across distributed writes. A clock like {"nodeA": 2, "nodeB": 1} means: - nodeA has coordinated 2 writes - nodeB has coordinated 1 write - Any version with these counters has "seen" those writes """ def __init__(self, clock: dict[str, int] | None = None): self.clock: dict[str, int] = clock.copy() if clock else {} def increment(self, node_id: str) -> "VectorClock": """Return a new clock with node_id's counter bumped by 1.""" new_clock = self.clock.copy() new_clock[node_id] = new_clock.get(node_id, 0) + 1 return VectorClock(new_clock) def dominates(self, other: "VectorClock") -> bool: """ Returns True if self is causally AFTER other. self dominates other when: - Every counter in self is >= the same counter in other, AND - At least one counter in self is strictly greater. Meaning: self has seen everything other has seen, plus more. """ all_keys = set(self.clock) | set(other.clock) at_least_one_greater = False for key in all_keys: self_val = self.clock.get(key, 0) other_val = other.clock.get(key, 0) if self_val < other_val: return False # self is missing something other has seen if self_val > other_val: at_least_one_greater = True return at_least_one_greater def merge(self, other: "VectorClock") -> "VectorClock": """ Merge two clocks by taking the max of each counter. Used after resolving a conflict to produce a new clock that has "seen" everything both conflicting versions saw. """ all_keys = set(self.clock) | set(other.clock) merged = {k: max(self.clock.get(k, 0), other.clock.get(k, 0)) for k in all_keys} return VectorClock(merged) def __repr__(self): return f"VectorClock({self.clock})" Parte 2: Valor de la versión Cada valor almacenado en Dynamo está envuelto con su reloj vectorial. Este apareamiento es lo que permite al coordinador comparar versiones durante las lecturas y detectar conflictos. @dataclass class VersionedValue: """ A value paired with its causal history (vector clock). When a client reads, they get back a VersionedValue. When they write an update, they must include the context (the vector clock they read) so Dynamo knows what version they're building on top of. """ value: object vector_clock: VectorClock def __repr__(self): return f"VersionedValue(value={self.value!r}, clock={self.vector_clock})" Parte 3: Nodo simulado En real Dynamo cada nodo es un proceso separado. Aquí los simulamos como objetos en memoria. El detalle clave: cada nodo tiene su propio local Los nodos pueden ser marcados como Simulación de fracasos. storage down class DynamoNode: """ Simulates a single Dynamo storage node. In production this would be a separate server with disk storage. Here it's an in-memory dict so we can demo the logic without networking. """ def __init__(self, node_id: str, token: int): self.node_id = node_id self.token = token # Position on the consistent hash ring self.storage: dict[str, list[VersionedValue]] = {} self.down = False # Toggle to simulate node failures def write(self, key: str, versioned_value: VersionedValue) -> bool: """ Store a versioned value. Returns False if the node is down. We store a LIST of versions per key, because a node might hold multiple concurrent (conflicting) versions until they are resolved by the application. """ if self.down: return False # In a real node this would be written to disk (e.g. BerkeleyDB) self.storage[key] = [versioned_value] return True def read(self, key: str) -> list[VersionedValue] | None: """ Return all versions of a key. Returns None if the node is down. A healthy node with no data for the key returns an empty list. """ if self.down: return None return self.storage.get(key, []) def __repr__(self): status = "DOWN" if self.down else f"token={self.token}" return f"DynamoNode({self.node_id}, {status})" Parte 4: Anillo hash consistente El anillo mapea las claves a los nodos. ordenamos los nodos por su token (posición) y usamos un paseo en dirección al reloj para encontrar el coordinador y la lista de preferencias para cualquier clave. import hashlib class ConsistentHashRing: """ Maps any key to an ordered list of N nodes (the preference list). Nodes are placed at fixed positions (tokens) on a conceptual ring from 0 to 2^32. A key hashes to a position, then walks clockwise to find its nodes. This means adding/removing one node only rebalances ~1/N of keys, rather than reshuffling everything like modulo hashing would. """ def __init__(self, nodes: list[DynamoNode]): # Sort nodes by token so we can do clockwise lookup efficiently self.nodes = sorted(nodes, key=lambda n: n.token) def _hash(self, key: str) -> int: """Consistent hash of a key into the ring's token space.""" # Use MD5 for a simple, evenly distributed hash. # Real Dynamo uses a more sophisticated hash (e.g., SHA-1). digest = hashlib.md5(key.encode()).hexdigest() return int(digest, 16) % (2**32) def get_preference_list(self, key: str, n: int) -> list[DynamoNode]: """ Return the first N nodes clockwise from key's hash position. These are the nodes responsible for storing this key. The first node in the list is the coordinator — it receives the client request and fans out to the others. """ if not self.nodes: return [] key_hash = self._hash(key) # Find the first node whose token is >= key's hash (clockwise) start_idx = 0 for i, node in enumerate(self.nodes): if node.token >= key_hash: start_idx = i break # If key_hash is greater than all tokens, wrap around to node 0 else: start_idx = 0 # Walk clockwise, collecting N unique nodes preference_list = [] for i in range(len(self.nodes)): idx = (start_idx + i) % len(self.nodes) preference_list.append(self.nodes[idx]) if len(preference_list) == n: break return preference_list Parte 5: El coordinador Dynamo Este es el corazón del sistema: la lógica que maneja las solicitudes de los clientes, los fans a las réplicas, espera el quórum y detecta los conflictos. class SimplifiedDynamo: """ Coordinates reads and writes across a cluster of DynamoNodes. Any node can act as coordinator for any request — there's no dedicated master. The coordinator is simply whichever node receives the client request (or the first node in the preference list, if using partition-aware routing). Configuration: N = total replicas per key R = minimum nodes that must respond to a read (read quorum) W = minimum nodes that must acknowledge a write (write quorum) """ def __init__(self, nodes: list[DynamoNode], N: int = 3, R: int = 2, W: int = 2): self.N = N self.R = R self.W = W self.ring = ConsistentHashRing(nodes) # ------------------------------------------------------------------ # # WRITE # # ------------------------------------------------------------------ # def put(self, key: str, value: object, context: VectorClock | None = None) -> VectorClock: """ Write a key-value pair to N replicas, wait for W ACKs. The 'context' is the vector clock from a previous read. Always pass context when updating an existing key — it tells Dynamo which version you're building on top of, so it can detect whether your write is concurrent with anything else. Returns the new vector clock, which the caller should store and pass back on future writes to this key. Raises: RuntimeError if fewer than W nodes acknowledged. """ preference_list = self.ring.get_preference_list(key, self.N) if not preference_list: raise RuntimeError("No nodes available") # The coordinator is always the first node in the preference list. coordinator = preference_list[0] # Increment the coordinator's counter in the vector clock. # If no context was provided (brand new key), start a fresh clock. base_clock = context if context is not None else VectorClock() new_clock = base_clock.increment(coordinator.node_id) versioned = VersionedValue(value=value, vector_clock=new_clock) # Fan out to all N replicas. # In a real system these would be concurrent RPC calls. # Here we call them sequentially for simplicity. ack_count = 0 for node in preference_list: success = node.write(key, versioned) if success: ack_count += 1 # Only need W ACKs to declare success. # The remaining replicas are updated asynchronously (or via # hinted handoff if they were down). if ack_count < self.W: raise RuntimeError( f"Write quorum not met: got {ack_count} ACKs, needed {self.W}" ) print(f"[PUT] key={key!r} value={value!r} clock={new_clock} " f"({ack_count}/{self.N} nodes wrote)") return new_clock # ------------------------------------------------------------------ # # READ # # ------------------------------------------------------------------ # def get(self, key: str) -> list[VersionedValue]: """ Read a key from N replicas, wait for R responses, reconcile. Returns a LIST of VersionedValues: - Length 1 → clean read, no conflict - Length >1 → concurrent versions detected; application must merge After reading, the caller should: 1. If no conflict: use the single value normally. 2. If conflict: merge the values using application logic, then call put() with the merged value and the merged vector clock as context. This "closes" the conflict. Read repair happens in the background: any replica that returned a stale version is silently updated with the latest version. """ preference_list = self.ring.get_preference_list(key, self.N) # Collect responses from all N nodes all_versions: list[VersionedValue] = [] responding_nodes: list[tuple[DynamoNode, list[VersionedValue]]] = [] for node in preference_list: result = node.read(key) if result is not None: # None means the node is down all_versions.extend(result) responding_nodes.append((node, result)) if len(responding_nodes) < self.R: raise RuntimeError( f"Read quorum not met: got {len(responding_nodes)} responses, needed {self.R}" ) # Reconcile: discard any version that is strictly dominated # (i.e., is a causal ancestor of) another version. # What remains is the set of concurrent versions. reconciled = self._reconcile(all_versions) # Background read repair: if any node returned something older # than the reconciled result, send it the latest version. # (Simplified: only meaningful when there's a single winner.) if len(reconciled) == 1: latest = reconciled[0] for node, versions in responding_nodes: if not versions or versions[0].vector_clock != latest.vector_clock: node.write(key, latest) # Repair silently in background status = "clean" if len(reconciled) == 1 else f"CONFLICT ({len(reconciled)} versions)" print(f"[GET] key={key!r} status={status} " f"({len(responding_nodes)}/{self.N} nodes responded)") return reconciled # ------------------------------------------------------------------ # # INTERNAL: VERSION RECONCILIATION # # ------------------------------------------------------------------ # def _reconcile(self, versions: list[VersionedValue]) -> list[VersionedValue]: """ Remove any version that is a causal ancestor of another version. If version A's clock is dominated by version B's clock, then B is strictly newer — A adds no new information and can be dropped. Whatever remains after pruning are CONCURRENT versions: writes that happened without either "knowing about" the other. The application must merge these using domain-specific logic. Example: versions = [clock={A:1}, clock={A:2}, clock={B:1}] {A:2} dominates {A:1} → drop {A:1} {A:2} and {B:1} are concurrent → both survive result = [{A:2}, {B:1}] ← conflict! application must merge """ dominated = set() for i, v1 in enumerate(versions): for j, v2 in enumerate(versions): if i != j and v2.vector_clock.dominates(v1.vector_clock): dominated.add(i) # v1 is an ancestor of v2, discard v1 survivors = [v for i, v in enumerate(versions) if i not in dominated] # De-duplicate: identical clocks from different replicas are the same version seen_clocks: list[VectorClock] = [] unique: list[VersionedValue] = [] for v in survivors: if not any(v.vector_clock.clock == s.clock for s in seen_clocks): unique.append(v) seen_clocks.append(v.vector_clock) return unique if unique else versions Parte 6: Putting It All Together - Una demostración Vamos a correr a través de un escenario completo: escribir / leer normal, luego un conflicto simulado donde dos nodos divergirán y la aplicación debe fusionarlos. def demo(): # ── Setup ────────────────────────────────────────────────────────── # # Five nodes placed at evenly spaced positions on the hash ring. # In a real cluster these would span multiple datacenters. nodes = [ DynamoNode("node-A", token=100), DynamoNode("node-B", token=300), DynamoNode("node-C", token=500), DynamoNode("node-D", token=700), DynamoNode("node-E", token=900), ] dynamo = SimplifiedDynamo(nodes, N=3, R=2, W=2) print("=" * 55) print("SCENARIO 1: Normal write and read (no conflict)") print("=" * 55) # Write the initial shopping cart ctx = dynamo.put("cart:user-42", {"items": ["shoes"]}) # Read it back — should be a clean single version versions = dynamo.get("cart:user-42") print(f"Read result: {versions[0].value}\n") # Update the cart, passing the context from our earlier read. # The context tells Dynamo "this write builds on top of clock ctx". ctx = dynamo.put("cart:user-42", {"items": ["shoes", "jacket"]}, context=ctx) versions = dynamo.get("cart:user-42") print(f"After update: {versions[0].value}\n") print("=" * 55) print("SCENARIO 2: Simulated conflict — two concurrent writes") print("=" * 55) # Write the base version base_ctx = dynamo.put("cart:user-99", {"items": ["hat"]}) # Now simulate a network partition: # node-A and node-B can't talk to each other. # We model this by writing directly to individual nodes. pref_list = dynamo.ring.get_preference_list("cart:user-99", 3) node_1, node_2, node_3 = pref_list[0], pref_list[1], pref_list[2] # Write 1: customer adds "scarf" via node_1 (e.g., their laptop) clock_1 = base_ctx.increment(node_1.node_id) node_1.write("cart:user-99", VersionedValue({"items": ["hat", "scarf"]}, clock_1)) # Write 2: customer adds "gloves" via node_2 (e.g., their phone) # This write also descends from base_ctx, not from clock_1. # Neither write knows about the other → they are concurrent. clock_2 = base_ctx.increment(node_2.node_id) node_2.write("cart:user-99", VersionedValue({"items": ["hat", "gloves"]}, clock_2)) # Read — coordinator sees two concurrent versions and surfaces the conflict versions = dynamo.get("cart:user-99") if len(versions) > 1: print(f"\nConflict detected! {len(versions)} concurrent versions:") for i, v in enumerate(versions): print(f" Version {i+1}: {v.value} clock={v.vector_clock}") # Application-level resolution: union merge (Amazon's shopping cart strategy) # Merge items: take the union so no addition is lost all_items = set() merged_clock = versions[0].vector_clock for v in versions: all_items.update(v.value["items"]) merged_clock = merged_clock.merge(v.vector_clock) merged_value = {"items": sorted(all_items)} print(f"\nMerged result: {merged_value}") # Write the resolved version back with the merged clock as context. # This "closes" the conflict — future reads will see a single version. final_ctx = dynamo.put("cart:user-99", merged_value, context=merged_clock) versions = dynamo.get("cart:user-99") print(f"\nAfter resolution: {versions[0].value}") assert len(versions) == 1, "Should be a single version after merge" if __name__ == "__main__": demo() Expected output: ======================================================= SCENARIO 1: Normal write and read (no conflict) ======================================================= [PUT] key='cart:user-42' value={'items': ['shoes']} clock=VectorClock({'node-A': 1}) (3/3 nodes wrote) [GET] key='cart:user-42' status=clean (3/3 nodes responded) Read result: {'items': ['shoes']} [PUT] key='cart:user-42' value={'items': ['shoes', 'jacket']} clock=VectorClock({'node-A': 2}) (3/3 nodes wrote) [GET] key='cart:user-42' status=clean (3/3 nodes responded) After update: {'items': ['shoes', 'jacket']} ======================================================= SCENARIO 2: Simulated conflict — two concurrent writes ======================================================= [PUT] key='cart:user-99' value={'items': ['hat']} clock=VectorClock({'node-A': 1}) (3/3 nodes wrote) [GET] key='cart:user-99' status=CONFLICT (2 versions) (3/3 nodes responded) Conflict detected! 2 concurrent versions: Version 1: {'items': ['hat', 'scarf']} clock=VectorClock({'node-A': 2}) Version 2: {'items': ['hat', 'gloves']} clock=VectorClock({'node-A': 1, 'node-B': 1}) Merged result: {'items': ['gloves', 'hat', 'scarf']} [PUT] key='cart:user-99' value={'items': ['gloves', 'hat', 'scarf']} ... (3/3 nodes wrote) [GET] key='cart:user-99' status=clean (3/3 nodes responded) After resolution: {'items': ['gloves', 'hat', 'scarf']} En el punto 2, el coordinador identifica correctamente que y No son iguales ni en una relación de dominación -ni es un antepasado del otro - por lo que ambos se superponen como simultáneos. la aplicación luego asume la responsabilidad de fusionarlos y escribir de nuevo una versión resuelta con el reloj fusionado. What to notice: {'node-A': 2} {'node-A': 1, 'node-B': 1} Lecciones clave para el diseño de sistemas Después de trabajar con los sistemas inspirados en Dynamo durante años, aquí están mis claves: 1. Always-On Beats Strongly-Consistent Para las aplicaciones orientadas al usuario, la disponibilidad casi siempre gana.Los usuarios tolerarán ver datos ligeramente estancados. 2. Application-Level Reconciliation is Powerful No tengas miedo de impulsar la resolución de conflictos a la aplicación.La aplicación entiende la lógica empresarial y puede tomar decisiones más inteligentes que la base de datos jamás podría. 3. Tunable Consistency is Essential Las adiciones de carrito de compras necesitan una alta disponibilidad (W=1). Las transacciones financieras necesitan garantías más fuertes (W=N).La capacidad de ajustar esta operación es increíblemente valiosa. 4. The 99.9th Percentile Matters More Than Average Concentre sus esfuerzos de optimización en las latencias de cola. Eso es lo que los usuarios realmente experimentan durante los tiempos de pico. 5. Gossip Protocols Scale Beautifully La coordinación descentralizada a través de los rumores elimina los puntos de fracaso y las escalas a miles de nodos. Cuándo no usar sistemas de estilo dinámico Sea honesto acerca de los compromisos. No utilice este enfoque cuando: Se requiere una fuerte coherencia (transacciones financieras, gestión de inventarios) Se necesitan consultas complejas (informes, análisis, juntas) Las transacciones abarcan varios artículos (Dynamo es solo operaciones de clave única) Tu equipo no puede manejar la coherencia eventual (si los desarrolladores no entienden los relojes vectoriales y la resolución de conflictos, tendrás problemas) Conclusión Dynamo represents a fundamental shift in how we think about distributed systems. By embracing eventual consistency and providing tunable trade-offs, it enables building systems that scale to massive sizes while maintaining high availability. Las lecciones del artículo han influenciado a toda una generación de bases de datos distribuidas. Ya sea que esté utilizando Cassandra, Riak o DynamoDB, se está beneficiando de las ideas publicadas por primera vez en este artículo. Como ingenieros, nuestro trabajo es comprender profundamente estos compromisos y aplicarlos adecuadamente. Dynamo nos da una herramienta poderosa, pero como cualquier herramienta, es tan buena como nuestra comprensión de cuándo y cómo usarla. Leer más Archivo de la etiqueta: SOSP 2007 Blog de Werner Vogels: Todas las cosas distribuidas Documentación Cassandra: Entender cómo se implementan estos conceptos “Diseño de aplicaciones intensivas en datos” de Martin Kleppmann – Capítulo 5 sobre la replicación Apéndice: Problemas de diseño y enfoques Tres problemas abiertos que surgen en entrevistas de diseño de sistemas y trabajo de ingeniería real. Problema 1: Resolución de conflictos para un editor de documentos colaborativo : Estás construyendo algo como Google Docs respaldado por una tienda de estilo Dynamo. Dos usuarios editan el mismo párrafo simultáneamente. The problem La estrategia de carrito de compras (unión de todos los artículos) sólo es segura porque la adición de elementos es conmutativa. Si Usuario A elimina una frase y Usuario B edita la mitad de ella, la unión de sus cambios es sin sentido o contradictoria. Why shopping cart union doesn’t work here {A} ∪ {B} = {B} ∪ {A} The right approach: Operational Transformation (OT) or CRDTs La solución de la industria es representar el documento no como un blob de texto, sino como una secuencia de operaciones, y transformar las operaciones simultáneas para que ambas puedan aplicarse sin conflictos: User A's operation: delete(position=50, length=20) User B's operation: insert(position=60, text="new sentence") Without OT: B's insert position (60) is now wrong because A deleted 20 chars. With OT: Transform B's operation against A's: B's insert position shifts to 40 (60 - 20). Both operations now apply cleanly. La estrategia de resolución de conflictos para la capa Dynamo sería: Almacenar operaciones (no snapshots de documentos completos) como el valor para cada clave. En conflicto, recoge todas las listas de operaciones simultáneas de cada versión. Aplique OT para fusionarlos en un solo registro de operaciones consistente. Escribe el registro fusionado con el reloj vectorial fusionado como contexto. : El registro de operaciones por segmento de documento, no el texto renderizado. Esto hace que las fusiones sean deterministas y sin pérdidas. What to store in Dynamo : This is essentially how Google Docs, Notion, and Figma work. Their storage layers use either OT or a variant of CRDTs (Conflict-free Replicated Data Types), which are data structures mathematically guaranteed to merge without conflicts regardless of operation ordering. Real-world reference Problema 2: Elegir N, R, W para diferentes casos de uso : ¿Qué configuración elegirías para (a) una tienda de sesión, (b) un catálogo de productos, (c) perfiles de usuario? The problem La forma correcta de pensar sobre esto: identificar el modo de error que cuesta más - una escritura perdida (pérdida de datos) o una escritura rechazada (indisponibilidad). Session store — prioritize availability Las sesiones son temporales y específicas para el usuario.Si la sesión de un usuario está estancada o se pierde brevemente, se logran y vuelven a iniciar sesión. Eso es molesto pero no catastrófico. N=3, R=1, W=1 Rationale: - W=1: Accept session writes even during heavy failures. A user can't log in if their session write is rejected. - R=1: Read from any single node. Stale session data is harmless. - N=3: Still replicate to 3 nodes for basic durability. Trade-off accepted: Stale session reads are possible but inconsequential. Product catalog — prioritize read performance and consistency Los datos del producto se escriben raramente (por equipos de operaciones), pero se leen millones de veces al día.Los precios o las descripciones estables son problemáticas. N=3, R=2, W=3 Rationale: - W=3: All replicas must confirm a catalog update before it's live. A price change half-published is worse than a brief write delay. - R=2: Read quorum overlap with W=3 guarantees fresh data. Acceptable: catalog writes are rare, so write latency doesn't matter. - N=3: Standard replication for durability. Trade-off accepted: Writes are slow and fail if any node is down. Acceptable because catalog updates are infrequent. User profiles — balanced Los datos de perfil (nombre, correo electrónico, preferencias) son moderadamente importantes. Un perfil estancado es molesto pero no peligroso. Una actualización rechazada (por ejemplo, el usuario no puede actualizar su correo electrónico) es un problema real. N=3, R=2, W=2 Rationale: - The classic balanced configuration. - R + W = 4 > N = 3, so quorums overlap: reads will see the latest write. - Tolerates 1 node failure for both reads and writes. - Appropriate for data that matters but doesn't require strict consistency. Trade-off accepted: A second simultaneous node failure will cause errors. Acceptable for non-critical user data. Decision framework summary: Priority R W When to use Max availability 1 1 Sessions, ephemeral state, click tracking Balanced 2 2 User profiles, preferences, soft state Consistent reads 2 3 Catalogs, config, rarely-written reference data Highest consistency 3 3 Anywhere you need R+W > N with zero tolerance for stale reads (still not linearizable) Max Disponibilidad 1 1 Sesións, estado efímero, seguimiento de clic Balanced 2 2 Perfil de usuario, preferencias, estado suave Consistentes lecturas 2 3 Catálogos, config, datos de referencia raramente escritos La mayor consistencia 3 3 Dondequiera que necesite R+W > N con tolerancia cero para lecturas estables (aún no linearizable) Problema 3: Prueba de un sistema de estilo dinámico bajo escenarios de partición : ¿Cómo verifica que su sistema realmente se comporta correctamente cuando fallan los nodos y ocurren particiones? The problem Este es uno de los problemas más difíciles en las pruebas de sistemas distribuidos porque los errores sólo aparecen en interleaves específicas de eventos simultáneos que son difíciles de reproducir deterministicamente. Layer 1: Unit tests for the logic in isolation Antes de probar el comportamiento distribuido, verifique los bloques de construcción de forma independiente.La lógica de comparación de relojes vectoriales, la detección de conflictos y las funciones de reconciliación se pueden probar con pruebas de unidades puras, sin necesidad de redes. def test_concurrent_clocks_detected_as_conflict(): clock_a = VectorClock({"node-A": 2}) clock_b = VectorClock({"node-B": 2}) assert not clock_a.dominates(clock_b) assert not clock_b.dominates(clock_a) # Both survive reconciliation → conflict correctly detected def test_ancestor_clock_is_discarded(): old_clock = VectorClock({"node-A": 1}) new_clock = VectorClock({"node-A": 3}) assert new_clock.dominates(old_clock) # old_clock should be pruned during reconciliation Layer 2: Deterministic fault injection En lugar de esperar que los fallos ocurran en el orden correcto durante la prueba de carga, inyectarlos deliberadamente y repetidamente. una versión simple de esto. En los sistemas de producción, las bibliotecas como o Y eso a nivel de infraestructura. node.down = True Japón El mono del caos Escenarios clave para la prueba: Scenario A: Write succeeds with W=2, third replica is down. → Verify: the data is readable after the down node recovers. → Verify: no data loss occurred. Scenario B: Two nodes accept concurrent writes to the same key. → Verify: the next read surfaces exactly 2 conflicting versions. → Verify: after the application writes a merged version, the next read is clean. Scenario C: Node goes down mid-write (wrote to W-1 nodes). → Verify: the write is correctly rejected (RuntimeError). → Verify: no partial writes are visible to readers. Scenario D: All N nodes recover after a full partition. → Verify: no data was lost across the cluster. → Verify: vector clocks are still meaningful (no spurious conflicts). Layer 3: Property-based testing En lugar de escribir casos de prueba individuales, define que siempre debe mantener y generar miles de secuencias de operaciones aleatorias para tratar de violarlas: invariantes # Invariant: after any sequence of writes and merges, a final get() # should always return exactly one version (no unresolved conflicts). # Invariant: a value written with a context derived from a previous read # should never produce a conflict with that read's version # (it should dominate it). # Invariant: if R + W > N, a value written successfully should always # be visible in the next read (read-your-writes, absent concurrent writes). Herramientas como (Python) te permite expresar estas invariantes y encontrar automáticamente contraexemplos. hipótesis Layer 4: Linearizability checkers Para la máxima confianza, grabe la hora de inicio, la hora de finalización y el resultado de cada operación durante una prueba de inyección de fallos, luego alimenta el historial a un verificador de linearización como Le dirá si cualquier historial observado es consistente con una ejecución secuencial correcta - incluso para un sistema eventualmente consistente que opera dentro de sus garantías declaradas. Knossos Escrito a partir de las trincheras de los sistemas distribuidos. insights probados por la batalla, cero ondas de mano. NoticiasLINK NoticiasLINK
