Replicación, sharding y CAP
En resumen: La replicación guarda copias de los datos en varios servidores, el sharding reparte los datos entre ellos, y el teorema CAP dice a qué renuncias cuando la red se parte.
Problema
Un servidor para toda la tienda
La tienda crece. El viernes por la tarde el catálogo se abre 20 000 veces por minuto, y casi todo son lecturas: productos, precios, stock. La base de datos está en un servidor, y su procesador está al 100 %. En la noche del sábado falla su disco, y la tienda está caída hasta la mañana.
Una máquina es a la vez el techo de la velocidad y el único punto donde todo puede detenerse. Necesitas más máquinas con copias de los datos.
La idea
Líder y seguidores
Replicación significa guardar los mismos datos en varios servidores (nodos). El esquema más común tiene un líder (en PostgreSQL, el primary): solo él acepta escrituras. Los demás nodos son seguidores (réplicas). Reciben cada escritura del líder y la aplican por su lado. Una lectura puede ir a cualquier nodo, así que tres nodos aguantan el triple de lecturas.
El campo es un simulador de un clúster de tres nodos, y el líder es A. El stock de queso blanco (producto 7) es 18 y está en los tres. El tiempo en el simulador está parado: una escritura sale del líder y llega a los seguidores en el siguiente tick. Cada valor tiene una versión (v1, v2), para que veas qué copia es más nueva. Bajo la salida está el dibujo: los nodos, sus copias y lo que aún va de camino.
write en A devuelve OK enseguida: el líder ha escrito por su lado y no espera a nadie. Esto es replicación asíncrona. Mientras la escritura viaja, B todavía dice 18. Ese retraso es el retraso de replicación (replication lag). Suele ser de milisegundos, y bajo carga llega a segundos.
Más precisamente, para curiosos
Los comandos write, read, tick y los demás de esta lección son del simulador, no de una base de datos concreta. tick adelanta su reloj un ciclo, mientras que en una base de datos real la replicación funciona todo el tiempo. PostgreSQL hace lo mismo con la replicación en streaming: el líder envía a los seguidores su registro de cambios (el WAL), y ellos lo aplican en orden. MySQL envía su registro binario. En ambos la replicación es asíncrona por defecto, y los seguidores solo aceptan lecturas.
Pruébalo
Cambié mi ciudad y la página muestra la antigua
Simona (cliente 17) se muda de Ruse a Plovdiv. Guarda la ciudad nueva en su perfil, y la página que se abre a continuación todavía dice Ruse:
La escritura se hizo, pero la página leyó de B, y B aún no la tiene. Otros clientes verán la ciudad nueva un instante después, y para ellos no hay diferencia. Para Simona parece que el cambio se perdió, y lo vuelve a escribir. Aquí hace falta la garantía read-your-writes: quien escribió ve su propia escritura. La solución habitual es que durante un tiempo después de un cambio (digamos, un minuto) las lecturas de ese cliente vayan al líder. La misma copia obsoleta la viste con la caché en la lección sobre clave-valor.
Guarda la ciudad nueva de Simona y léela enseguida para que vea Plovdiv.
Solución
write customer:17:city = Plovdiv on A
read customer:17:city from A
read customer:17:city from A: el líder tiene todas las escrituras confirmadas. Un tick y luego una lectura de B también muestra Plovdiv, pero en una base de datos real no sabes cuánto esperar. Una lectura de B o C justo después de la escritura da Ruse.
La idea
Replicación síncrona y su precio
Si el líder se cae antes de que la escritura llegue a los seguidores, la escritura está solo en el líder. Así que puedes hacerlo esperar. Con replicación síncrona el líder dice OK solo cuando los seguidores confirman que tienen la escritura. Entonces la escritura confirmada está en todos los nodos.
El precio es doble. Cada escritura espera al seguidor más lento, y entre dos centros de datos eso significa milisegundos en cada escritura. Y un seguidor muerto detiene todas las escrituras, porque el líder no tiene de quién recibir una confirmación. Por eso en la práctica se mezclan: un seguidor es síncrono y los demás asíncronos. Si el síncrono se cae, otro ocupa su lugar.
Más precisamente, para curiosos
En PostgreSQL los seguidores síncronos se definen con synchronous_standby_names. FIRST 1 (b, c) espera al primer disponible de la lista, y ANY 1 (b, c) espera a cualquiera de los dos. Si nadie puede confirmar, la transacción se queda colgada hasta que aparece un seguidor o cambia el ajuste. El simulador no se cuelga: rechaza la escritura enseguida y dice por qué. MySQL tiene replicación semisíncrona: el líder espera a que al menos un seguidor confirme que ha recibido la escritura.
Míralo
El líder se cae
La replicación es asíncrona. Un cliente compra queso blanco, A baja el stock a 17 y dice OK. Un instante después A se detiene, antes de que la escritura salga:
B y C son seguidores y no aceptan escrituras, así que la tienda se queda atascada hasta que haya un líder nuevo. elect elige, entre los nodos que se ven entre sí, el que tiene los datos más nuevos. Hacen falta al menos dos de los tres, una mayoría. Cada elección tiene un número (el mandato, term). El líder nuevo tiene el mandato 2, y cuando vuelve el antiguo se entera de que ya no es el líder. El cambio de líder se llama failover.
Pero B nunca recibió el 17. La venta confirmada desaparece: A la descarta cuando vuelve, porque el líder nuevo no la tiene. Esta es la trampa de la replicación asíncrona: en un failover pueden perderse las últimas escrituras confirmadas. Con replicación síncrona B la habría tenido.
Más precisamente, para curiosos
MongoDB cambia el líder (el primary) por sí mismo: si los seguidores no tienen noticias suyas durante 10 segundos (por defecto), votan, y gana un nodo con la mayoría de los votos. Las escrituras del antiguo primary que no llegaron a la mayoría se deshacen cuando vuelve a unirse. Por eso las escrituras importantes se envían con writeConcern: { w: "majority" }: solo se confirman cuando la mayoría las tiene. PostgreSQL no cambia el líder por sí mismo. Lo hacen herramientas externas como Patroni, y a mano un seguidor pasa a ser líder con pg_promote(). En el simulador la elección también es manual (elect).
La idea
La red se parte: CAP y quórums
Un servidor muerto al menos se reconoce. Es más complicado cuando todo funciona pero los nodos no se ven entre sí, por ejemplo cuando se rompe el enlace entre dos centros de datos. Esto es una partición de red. El nodo del otro lado no sabe si los demás se han caído o si simplemente no los oye.
Aquí ayuda un esquema distinto, uno sin líder. Cada nodo acepta escrituras y las envía a los demás. Una escritura espera W confirmaciones, y una lectura pregunta a R nodos y toma la versión más nueva. Si hay N nodos y W + R > N, toda lectura pregunta al menos a un nodo que tiene la última escritura. Esto es un quórum. Con N = 3, W = 2 y R = 2 una escritura y una lectura siempre se encuentran en al menos un nodo:
Con W = 1 y R = 1 la lectura de C pregunta solo a C, y C todavía no tiene la escritura nueva. Con W = 2 y R = 2 C pregunta también a A y toma v3.
Ahora el corte: C queda aislado de A y B.
A y B son una mayoría y siguen. C no llega a dos nodos y rechaza tanto la lectura como la escritura: ninguna respuesta es mejor que una equivocada. Con W = 1 y R = 1 C responde, pero dice 18, mientras que la verdad es 17.
Esto es CAP, dicho con precisión. Mientras la red está partida (P, partition), el nodo elige. O se niega, para no devolver un valor antiguo ni aceptar una escritura que los demás no conocen (consistencia, C). O responde con lo que tiene (disponibilidad, A). No puede hacer las dos cosas a la vez. CAP no significa «elige dos de tres»: la partición no se elige, ocurre. Sin partición la elección es otra, y lo dice PACELC: else (E) la base de datos elige entre latencia (L) y consistencia (C), porque la replicación síncrona y los quórums esperan en cada escritura.
Más precisamente, para curiosos
La idea de los quórums viene del artículo Dynamo de Amazon (2007). Cassandra la sigue: cada consulta dice cuántos nodos necesita (ONE, QUORUM, ALL). Las versiones allí son marcas de tiempo, y en un conflicto gana la escritura más nueva (last write wins). El simulador cuenta las versiones con un contador. Las lecturas de DynamoDB son por defecto eventualmente consistentes, así que pueden devolver un valor antiguo, y con ConsistentRead son consistentes. La consistencia de CAP no es la C de ACID. En CAP significa que toda lectura ve la última escritura confirmada, como si hubiera una sola copia. En ACID significa que se cumplen las reglas de la base de datos. CAP lo formuló Eric Brewer en 2000 y lo demostraron Gilbert y Lynch en 2002.
La idea
Sharding: cada nodo con su propia parte
La replicación multiplica las lecturas, pero cada escritura sigue llegando a todos los nodos, y cada nodo lo guarda todo. Cuando los datos o las escrituras no caben en una máquina, los divides: cada nodo guarda su propia parte. La parte se llama shard, y la división sharding. A qué shard va cada fila lo decide la clave de shard, normalmente una columna como el número de cliente.
Por rango: los clientes del 1 al 7 en A, del 8 al 14 en B, del 15 en adelante en C. where dice en qué nodo está un cliente, y query a qué shards tiene que preguntar una consulta:
Una consulta sobre números vecinos pregunta solo a dos shards. Pero cada cliente nuevo tiene un número más alto y va a C. Todos los registros de hoy caen en un nodo, mientras A y B descansan. Esto es un punto caliente (hot spot).
Por hash: de la clave se calcula un número, y él dice el shard. En el simulador el hash es el resto de dividir entre 3:
Los clientes nuevos van por turno a A, B y C. El precio es que una consulta sobre un rango ahora pregunta a todos los shards, porque los números vecinos están dispersos.
¿Y si la clave es la ciudad? La consulta «los clientes de Sofía» preguntará a un shard. Pero todos los de Sofía están en un mismo sitio:
A tiene 9 de los 20 clientes: los seis de Sofía, la ciudad más grande, más Burgas y el cliente sin ciudad. Sus pedidos y la carga se van con los clientes. El shard tampoco se puede dividir: todos los de Sofía tienen la misma clave. Y una consulta por número ahora pregunta a todos los shards. Una buena clave tiene muchos valores distintos y reparte por igual tanto los datos como la carga.
Una cosa más: una tabla dividida en shards ya no está en un solo lugar. Un JOIN de un cliente con sus pedidos solo es rápido si están en el mismo shard. Por eso los pedidos suelen repartirse por el número de cliente, como el cliente. Una transacción que escribe en dos shards necesita una transacción distribuida (two-phase commit). Es más lenta, y si su coordinador se cae a medias, los shards esperan.
Más precisamente, para curiosos
En el simulador los tres nodos son o copias o shards. En una base de datos real cada shard es su propio grupo de copias. En MongoDB cada shard es un replica set, y un router (mongos) envía la consulta al shard según la clave. MongoDB reparte por rango o por hash, y un trozo de los datos con un único valor de la clave que se hace demasiado grande no se puede dividir (un jumbo chunk). Cassandra pasa la clave por Murmur3 y coloca los nodos en un anillo (consistent hashing): un nodo nuevo se hace cargo de parte de las claves sin mover todas. El resto de dividir entre 3 del simulador no es así: con un cuarto nodo casi todos los clientes cambiarían de shard. El «hash» de una ciudad en el simulador es el número de la ciudad en una lista. Para PostgreSQL el sharding viene con la extensión Citus, y para MySQL con Vitess.
Ejercicio
Un fallo, un quórum y clientes nuevos
1. El stock de queso blanco es 18 y está en los tres nodos. El líder A se cae, y hay que cambiar su disco.
A no volverá pronto. Haz que el clúster vuelva a aceptar escrituras, y escribe el nuevo stock de queso blanco: 17.
Solución
elect
write stock:7 = 17 on B
elect, luego write stock:7 = 17 on B. B y C tienen los mismos datos, y en caso de empate el simulador elige el primero por nombre. Sin elección B rechaza la escritura, porque es un seguidor. start A no es salida: A no volverá.
2. El clúster no tiene líder y tiene tres nodos.
Elige W y R de modo que una lectura de cualquier nodo justo después de una escritura vea el valor nuevo, y que las escrituras sigan pasando cuando un nodo esté caído.
Solución
quorum write 2 read 2
quorum write 2 read 2. 2 + 2 > 3, así que una lectura siempre se encuentra con un nodo que tiene la última escritura. Cuando un nodo está caído, quedan dos, suficientes para W y para R. Con W = 3 las escrituras se detienen con el primer nodo muerto. Con W + R ≤ 3 una lectura puede perderse la escritura nueva, y con R = 3 las lecturas se detienen.
3. La tienda lanza un anuncio y espera cientos de clientes nuevos con los números 21, 22, 23 y siguientes.
Elige la clave de shard de los clientes de modo que los clientes nuevos se repartan entre los tres nodos en vez de ir a uno.
Solución
shard customers by id hash
shard customers by id hash. Por rango todos los números nuevos están por encima de 15 y van a C. Por ciudad los clientes nuevos de Sofía seguirían yendo a un shard, y el simulador ni siquiera conoce sus ciudades.
La idea
Qué usar y cuándo
- La replicación hace falta casi siempre: una copia en otra máquina protege de un fallo, y los seguidores aguantan las lecturas. Lo asíncrono es lo habitual. Si perder las últimas escrituras no es aceptable (pagos), al menos un seguidor es síncrono.
- Leer de un seguidor es bueno para el catálogo, los informes y la búsqueda. No es bueno para lo que el cliente acaba de cambiar: entonces lee el líder.
- El sharding es el último paso, no el primero. Una máquina más grande, índices, una caché como Redis y réplicas de lectura bastan para la mayoría de las tiendas. El sharding complica cada consulta y transacción que cruza shards.
- CAP se decide para cada operación por separado. El stock y el pago quieren consistencia. El carrito y «vistos recientemente» pueden seguir disponibles y estar un poco desactualizados.
Más precisamente, para curiosos
Tres nodos son el clúster más pequeño que cambia de líder por sí mismo: con dos nodos, un nodo que se queda solo no es una mayoría. Por eso MongoDB recomienda un número impar de miembros con voto en un replica set. Google Spanner y CockroachDB ejecutan transacciones entre shards con algoritmos de consenso (Paxos en Spanner, Raft en CockroachDB). El precio es la latencia en cada escritura, que es PACELC en la práctica.
Test