Tu servicio de carrito escribe en cada clic y en diciembre no puede rechazar ni un solo añadido al carrito. Durante el pico fallará un disco, un switch de rack oscilará, quizá un centro de datos se caiga de la red. Una única base de datos primaria convierte cada uno de esos fallos en una caída del servicio.
El artículo de Dynamo de Amazon, de 2007, describió un store que sigue aceptando escrituras pese a todo eso; Cassandra y Riak KV tomaron prestadas la mayoría de sus ideas de clustering. Esta entrada diseña un store al estilo Dynamo desde la API hasta el motor de almacenamiento, compara sistemas reales y dibuja el resultado.
Requisitos y API
La interfaz de Dynamo tiene dos operaciones:
get(key) -> [value, ...], context
put(key, context, value) -> ok
get puede devolver versiones en conflicto más un contexto opaco; el siguiente put lo devuelve para indicar qué versiones reemplaza. Los requisitos:
- Siempre escribible, incluso con nodos o enlaces caídos.
- Latencia de cola predecible. El SLA de ejemplo del artículo es de 300 ms para el 99,9 % de las peticiones con un pico de 500 peticiones por segundo.
- Valores pequeños, claves individuales: objetos normalmente de menos de 1 MB, sin operaciones sobre varias claves.
- Escalado incremental, un nodo cada vez.
Dimensionado, suponiendo valores de 1 KB y discos medio llenos para dejar margen a la compactación: 1000 millones de claves son 1 TB, 3 TB con tres copias, así que seis nodos de 1 TB, como el anillo del diagrama. Con 30 000 escrituras por segundo, tres copias suponen 90 000 escrituras de réplica, o 15 000 por nodo.
CAP y PACELC en breve
CAP dice que durante una partición de red un store debe rechazar algunas peticiones o arriesgarse a lecturas obsoletas; Dynamo sigue disponible. El PACELC de Daniel Abadi (2012) añade que, sin partición, aun así se intercambia latencia por consistencia; clasifica las configuraciones por defecto de Dynamo, Cassandra y Riak como PA/EL.
Particionado con un anillo hash y nodos virtuales
Dynamo aplica MD5 a cada clave para obtener una posición de 128 bits en un anillo, y la clave pertenece al primer nodo en sentido horario. Cuando un nodo entra o sale, solo se mueven los rangos vecinos, en lugar de casi todas las claves como con hash(key) % N; el diagrama de consistent hashing muestra cómo.
Una sola posición por nodo reparte los datos de forma desigual, así que cada nodo toma muchas, llamadas nodos virtuales o tokens. Cassandra 5.0 viene con 16 tokens por nodo; el anillo de Riak tiene 64 particiones por defecto. Renuncias a los escaneos por rango: las claves vecinas acaban en nodos distintos, como explica el diagrama de sharding de bases de datos.
Replicación y listas de preferencia
Cada clave vive en N nodos: el coordinador (el primer nodo en sentido horario) y los N − 1 nodos físicos distintos siguientes. La lista de preferencia de la clave continúa más allá, de modo que hay sustitutos cuando una réplica está caída. Reparte las réplicas entre dominios de fallo: Dynamo repartía cada lista entre centros de datos, y la NetworkTopologyStrategy de Cassandra las reparte entre racks. Todas las réplicas aceptan escrituras, a diferencia de las configuraciones con líder del diagrama de replicación de bases de datos.
Quórums: R + W > N
El coordinador envía cada escritura a las N réplicas y responde tras W confirmaciones; una lectura responde tras R respuestas. Si R + W > N, cualquier conjunto de lectura y cualquier conjunto de escritura confirmada comparten al menos un nodo.
| N, R, W | R + W > N | Qué obtienes | Qué pagas |
|---|---|---|---|
| 3, 2, 2 | Sí | Las lecturas ven la última escritura confirmada; una réplica puede fallar | Cada petición espera la segunda respuesta más rápida |
| 3, 1, 3 | Sí | Lecturas rápidas desde cualquier réplica | Las escrituras esperan a las tres |
| 3, 1, 1 | No | Latencia mínima, disponibilidad máxima | Las lecturas pueden ser obsoletas |
| 5, 3, 3 | Sí | Dos réplicas pueden fallar | Cinco copias de cada valor |
La configuración habitual del artículo de Dynamo era (3, 2, 2), y los servicios con muchas lecturas, como el catálogo de productos, usaban R = 1, W = N. Cassandra fija un nivel de consistencia por petición, de ONE a ALL; QUORUM en lecturas y escrituras da R + W > N.
El solapamiento no es linealizabilidad. Una escritura que llega a una réplica y luego falla puede aparecer en una lectura y desaparecer en la siguiente; el read repair bloqueante por defecto de Cassandra lo evita en las lecturas con quórum. Compare-and-set necesita consenso, como en las lightweight transactions de Cassandra o en un store basado en Raft.
Conflictos: last write wins, vector clocks o CRDTs
Las escrituras concurrentes a través de réplicas distintas dejan dos versiones. Tres salidas:
| Estrategia | Cómo resuelve | ¿Puede perder actualizaciones? | Usada por |
|---|---|---|---|
| Last write wins | Gana el timestamp más alto | Sí, en silencio; el desfase de reloj elige al ganador | Cassandra, DynamoDB global tables, Riak si se configura |
| Vector clocks | Conserva las versiones concurrentes; el cliente las fusiona | No, pero todos los clientes deben fusionar | Dynamo, Riak (dotted version vectors) |
| CRDTs | Tipos de datos cuyas fusiones siempre convergen | No, para los tipos soportados | Contadores, sets y maps de Riak |
Un vector clock es una lista de pares (nodo, contador). Una versión cuyos contadores son todos menores o iguales que los de otra es un ancestro y puede descartarse; en caso contrario se conservan ambas. El servicio de carrito fusionaba los carritos en conflicto, así que los artículos añadidos nunca se perdían, aunque los eliminados podían reaparecer. Los conflictos eran raros: en 24 horas, el 99,94 % de las peticiones del carrito vio exactamente una versión. Los CRDT trasladan la fusión al propio tipo de datos; los editores colaborativos basados en CRDT aplican la misma idea al texto compartido.
Gestión de fallos: hinted handoff, repair y gossip
Sloppy quorum y hinted handoff. Dynamo usa los primeros N nodos sanos de la lista de preferencia: si C está caído, D toma la copia de C con una pista y la devuelve cuando C se recupera. Las escrituras siguen funcionando, pero una lectura de B y del C recuperado puede perderse una escritura que solo confirmaron A y D. Cassandra mantiene los quórums estrictos: los hints cuentan para el nivel de consistencia solo con ANY y se detienen cuando un nodo lleva 3 horas caído (max_hint_window).
Read repair y anti-entropy. Cuando las respuestas discrepan, el coordinador reescribe la versión más reciente en las réplicas obsoletas. Para datos fríos, las réplicas comparan árboles de Merkle por rango de claves y sincronizan solo los rangos que difieren. La documentación de Cassandra recomienda ejecutar nodetool repair en cada nodo al menos cada 7 días: los tombstones se purgan tras gc_grace_seconds (10 días por defecto), y una réplica sin reparar puede traer de vuelta datos eliminados.
Gossip y detección de fallos. Cada segundo, cada nodo intercambia el estado de pertenencia y de tokens con un par aleatorio; los nodos seed conocidos por todos evitan que el anillo se divida. El detector phi accrual de Cassandra marca un par como caído cuando la sospecha supera phi_convict_threshold (8 por defecto).
El camino de escritura: commit log, memtable, SSTables
El motor de almacenamiento de Cassandra es un árbol log-structured merge (LSM) optimizado para escrituras:
- Añadir la escritura al commit log. Por defecto (
periodic), Cassandra confirma de inmediato y sincroniza cada 10 segundos, así que un fallo puede perder esa ventana. - Insertarla en la memtable, una estructura ordenada en memoria.
- Volcar una memtable llena a una SSTable inmutable y ordenada en disco.
- Compactar las SSTables en segundo plano, conservando las versiones más recientes y descartando los tombstones caducados.
Las lecturas consultan la memtable y luego las SSTables, y un filtro de Bloom por SSTable salta los archivos que no pueden contener la clave: con 10 bits por clave y 7 funciones hash, la tasa de falsos positivos es (1 − e^(−0,7))^7, alrededor del 0,8 %. La size-tiered compaction es la opción por defecto; Cassandra 5.0 recomienda su estrategia unified para cargas nuevas.
Sistemas reales frente al artículo
| Dynamo (2007) | Amazon DynamoDB | Cassandra 5.0 | Riak KV | |
|---|---|---|---|---|
| Particionado | Anillo MD5, particiones iguales | Rangos que se dividen por tamaño o tráfico | Anillo Murmur3, 16 tokens por nodo | Anillo de 160 bits, 64 particiones |
| Replicación | Sin líder, N por clave | 3 réplicas entre AZ, líder Multi-Paxos | Sin líder, por centro de datos | Sin líder, n_val 3 |
| Consistencia | Sloppy quorum | Eventual por defecto; lecturas fuertes desde el líder | Nivel de consistencia por petición | Sloppy quorum, pr y pw |
| Conflictos | Vector clocks | El líder ordena las escrituras; last writer wins entre Regiones | Last write wins | Siblings o CRDTs |
| Almacenamiento | Berkeley DB, MySQL | B-tree más write-ahead log | LSM tree | Bitcask, LevelDB |
DynamoDB comparte el nombre, no el diseño: según su artículo de USENIX de 2022, el líder de la partición confirma una escritura cuando dos de las tres réplicas la han registrado. Las global tables usan por defecto last writer wins entre Regiones; en el momento de escribir esto (noviembre de 2026) también ofrecen consistencia fuerte multirregión en exactamente tres Regiones.
El diagrama del key-value store estilo Dynamo
Contenido del diagrama
- Node B
- Node A
- Node C
- Node F
- Node D
- Node E
- Cart service
- Inside every node: LSM write path
- Commit log
- Memtable
- SSTables
- put(k, ctx, v)
- replica 2: ack
- replica 3: no reply
- hinted write for C: ack
- hand off when C recovers
- then insert
- flush when full
- gossip
Cómo leerlo:
- El anillo. Recorriendo el sentido horario desde hash(k), el punto, se obtiene la lista de preferencia de A a F.
- La escritura. El servicio de carrito envía put(k, ctx, v) al coordinador A, que replica en B y C.
- El fallo. C está caído, así que D toma la copia de C con una pista (discontinua, ámbar) y la devuelve después. Con W = 2, el put vuelve cuando A y B lo tienen.
- El gossip (punteado) circula entre pares aleatorios de nodos.
- Los paneles listan N, R, W y el camino de escritura de cada nodo.
Cómo dibujar con claridad diagramas de key-value store
- Sigue una sola clave. Marca su hash, escribe su lista de preferencia y pon N, R y W a su lado; un anillo sin clave no explica nada.
- Dibuja el fallo. Un nodo rojo y una arista de reserva discontinua explican un sloppy quorum más rápido que el texto.
- Muestra los dominios de fallo: colorea las réplicas por rack o zona para que los revisores comprueben que no hay dos copias en el mismo.
- Deja el interior de los nodos para un único recuadro. Primero va el clúster.
Un error común: flechas del cliente a cada réplica y ningún coordinador, lo que oculta quién decide que una escritura tuvo éxito. El método paso a paso de diseño de sistemas trata la disposición y las cifras.
Constrúyelo en Archboard
- Inicia sesión con Google o GitHub y crea un diagrama.
- Añade una Elipse grande y gris del paquete Básico para el anillo de tokens.
- Coloca seis nodos Servidor del paquete Red en el anillo, de Node A a Node F en sentido horario. Colorea A y B de verde, C de rojo y D de ámbar, y etiqueta sus roles con notas de Texto de Básico.
- Añade una Elipse pequeña en el anillo justo antes de Node A para hash(k), con una etiqueta de Texto.
- Añade un Contenedor del paquete Modelo C4 para el servicio de carrito, con una arista put(k, ctx, v) hacia Node A.
- Dibuja las aristas: A a B continua verde, A a C discontinua roja con punta de flecha en cruz, A a D y D a C discontinuas ámbar (escritura con pista, luego handoff) y una arista de gossip punteada entre F y E con una nota de Texto.
- Añade un bloque Markdown del paquete Básico con N, R, W y el escenario.
- Añade un Marco del paquete Básico con tres nodos Componente del paquete Modelo C4, Commit log, Memtable y SSTables, enlazados de arriba abajo, y una nota de Texto sobre los filtros de Bloom.
El ejemplo usa 14 nodos de diagrama, dentro del plan Free.
Preguntas frecuentes
¿Cómo se diseña un key-value store distribuido? Particiona con consistent hashing, replica cada clave en N nodos, ajusta R y W, elige una estrategia de conflictos, añade hinted handoff y reparación anti-entropy, y ejecuta un LSM tree por nodo.
¿Qué significa R + W > N? De N réplicas, una escritura espera a W y una lectura a R. Si R + W supera N, toda lectura llega al menos a una réplica que tiene la última escritura confirmada.
¿DynamoDB se basa en el artículo de Dynamo? Solo en parte: cada partición tiene tres réplicas con un líder Multi-Paxos y almacenamiento B-tree, no sloppy quorums ni vector clocks.
¿Qué es el hinted handoff? Otro nodo guarda la escritura de una réplica inalcanzable con una pista y la entrega cuando la réplica vuelve. Cassandra deja por defecto de guardar hints para un nodo tras 3 horas de caída.
¿Debo usar last write wins o vector clocks? Last write wins sirve para datos donde perder una actualización concurrente es aceptable, como las sesiones. Usa vector clocks o CRDTs cuando cada actualización importa, como en carritos y contadores.