En este artículo, consideraremos la arquitectura del almacenamiento KV simple y eficiente mediante la replicación en cadena, que se investiga activamente y se utiliza con éxito en varios sistemas.

Esta es la primera mitad de un artículo de replicación en cadena. La segunda parte está aquí . Al principio habrá una pequeña teoría, luego algunos ejemplos de uso con varias modificaciones.

El objetivo es la declaración del problema y la comparación con el protocolo primario / de respaldo.
La replicación en cadena es un enfoque básico.
Replicación en cadena: solicitudes distribuidas.
FAWN: una matriz rápida de nodos débiles.

1. Introducción

1.1 Propósito

Supongamos que queremos diseñar una tienda simple de valor-clave. El repositorio tendrá una interfaz muy mínima:

escribir (clave, objeto): guardar / actualizar el valor del valor por clave clave.
leer (clave): devuelve el valor almacenado por clave clave.

También sabemos que el tamaño de los datos es relativamente pequeño (todo cabe en un servidor, no hay necesidad de fragmentación), pero puede haber muchas solicitudes de escritura / lectura.

Nuestro objetivo es soportar una gran cantidad de solicitudes ( alto rendimiento, HT ), tener alta disponibilidad ( HA ) y una consistencia estricta ( SC ).

En muchos sistemas, SC se sacrifica por HA + HT, porque el cumplimiento de las tres propiedades es una tarea no trivial. Amazon Dynamo fue un gran salto adelante y generó varias bases de datos de estilo Dynamo, como Cassandra, Riak, Voldemort, etc.

1.2 Primario / Copia de seguridad

Uno de los enfoques más comunes y simples para construir un sistema de almacenamiento de este tipo es utilizar la replicación primaria / de respaldo.
Tenemos 1 servidor primario, varios servidores de respaldo, las operaciones de escritura / lectura van solo a través del servidor primario.

Aquí, la imagen muestra uno de los posibles protocolos de interacción (el principal espera un reconocimiento de todas las copias de seguridad antes de enviar un reconocimiento al cliente), hay otras opciones (no mutuamente excluyentes), por ejemplo:

Primary organiza estrictamente las solicitudes de escritura.
El primario envía un reconocimiento tan pronto como uno de los respaldos responde con reconocimiento.
Quórum descuidado y entrega insinuada.
Etc.

También se necesita un proceso separado que monitorea el estado del clúster (distribuye la configuración a los participantes) y, cuando el servidor host falla, hace (inicia) la elección de uno nuevo, y también determina qué hacer en caso de un cerebro dividido. Nuevamente, dependiendo de los requisitos, parte de esta lógica se puede ejecutar como parte del algoritmo de replicación, parte como una aplicación de terceros (por ejemplo, un cuidador del zoológico para almacenar la configuración), etc.

Obviamente, tarde o temprano, el rendimiento de la replicación primaria / de respaldo estará limitado por dos cuellos de botella:

Rendimiento del servidor primario.
Número de servidores de respaldo.

Cuantos más requisitos de confiabilidad / consistencia se presenten a un clúster, más rápido llegará este momento.

¿Hay otras formas de lograr nuestro objetivo?

1.3 replicación de cadena

En general, la replicación en cadena consiste en una secuencia (cadena) de servidores, con roles especiales HEAD (el servidor con el que se comunica el cliente) y TAIL (final de la cadena, garantía SC). Una cadena tiene al menos las siguientes propiedades:

Resiste la caída a n - 1 servidores.
La velocidad de escritura no es significativamente diferente de la velocidad de SC Primary / Backup.
La reconfiguración del clúster en caso de un bloqueo de HEAD ocurre mucho más rápido que el primario, el resto de los servidores son comparativamente o más rápidos que en el primario / respaldo.

Un punto pequeño pero significativo: se requiere una conexión FIFO confiable entre servidores.

Examinemos más detalladamente los diversos métodos para construir la replicación de la cadena.

2. El enfoque básico

2.1 Algoritmo operacional

Los clientes envían solicitudes de escritura al nodo principal y las solicitudes de lectura se envían al nodo de cola. La respuesta siempre viene de la cola. Head, después de recibir una solicitud de cambio, calcula el cambio de estado necesario, lo aplica y lo envía al siguiente nodo. Tan pronto como la cola lo procesa, se envía una respuesta ACK de vuelta a la cadena. Obviamente, si una solicitud de lectura devuelve algún valor de x, se almacena en todos los nodos.

2.2 Protocolo de replicación

Numeramos los servidores de principio a fin, luego en cada nodo

i

$i$ También almacenaremos:

$Pendiente_i$ - una lista de solicitudes recibidas por el nodo que aún no se han procesado por cola.
$Sent_i$ - una lista de solicitudes enviadas por el servidor a su sucesor que aún no se han procesado por cola.
$History_i (clave)$ - el historial de cambios en el valor clave (puede almacenar tanto el historial como solo el valor total). Tenga en cuenta que:
$H i s t o r y_{j} (c l a v e) s u b s e t e q H i s t o r y_{i} (c l a v e), f o r a l l j > i$
$History_j (clave) \ subseteq History_i (clave), \ forall j> i$
Y también:
$S e n t_{i} s u b s e t e q P e n d i n g_{i} H i s t o r y_{i} (k e y) = H i s t o r y_{i + 1} (k e y) c u p S e n t_{i}$
$Sent_i \ subseteq Pending_i \\ History_i (key) = History_ {i + 1} (key) \ cup Sent_i$

2.3 Conmutación por error del servidor

Como se mencionó en la introducción, necesitamos algún tipo de proceso maestro que:

Identifica un servidor fallido.
Notifica a su predecesor y sucesor de cambios en el circuito.
Si el servidor es cola o cabeza, notifica a los clientes de su cambio.

Creemos que el proceso maestro es estable y nunca se bloquea. La elección de dicho proceso está más allá del alcance de este artículo.

La segunda suposición muy importante es que asumimos que los servidores son a prueba de fallas:

En caso de falla (interna), el servidor deja de funcionar y no da un resultado incorrecto.
La falla del servidor siempre está determinada por el proceso maestro.

Veamos cómo se agrega un nuevo servidor:
Teóricamente, se puede agregar un nuevo servidor a cualquier lugar de la cadena, agregar a la cola parece ser el menos difícil: solo necesita copiar el estado de la cola actual al nuevo servidor, notificar al asistente sobre el cambio en la cadena y notificar a la cola anterior que las solicitudes ahora deben enviarse más.

Finalmente, considere tres posibles escenarios de falla:

2.3.1 Caída de cabeza
Simplemente quite el servidor de la cadena y asigne el siguiente nuevo encabezado. Solo la pérdida de esas solicitudes de

P e n d i e n t e_{c a b e z a}

$Pendiente_ {cabeza}$ que no fueron enviados más lejos

P e n d i e n t e_{c a b e z a} s e t m i n u s E n v i a d o_{c a b e z a}

$Pendiente_ {cabeza} \ setminus Enviado_ {cabeza}$

2.3.2 Cola de caída
Eliminamos el servidor de la cadena y asignamos el anterior a la nueva cola, antes de eso

E n v i a d o_{c o l a - 1}

$Enviado_ {cola - 1}$ despejado (todas estas operaciones están marcadas como cola procesada), respectivamente

P e n d i e n t e_{c o l a - 1}

$Pendiente_ {cola - 1}$ disminuye

2.3.3 Nodo intermedio descendente

k

$k$
El asistente informa a los nodos.

k - 1

$k-1$ y

k + 1

$k + 1$ sobre reordenar en una cadena.
Posible pérdida

E n v i a d o_{k - 1}

$Enviado_ {k-1}$ si el nodo

k

$k$ No pude enviarlos más a mi sucesor, por lo tanto, después de eliminar el nodo

k

$k$ desde la cadena lo primero se vuelve a enviar

E n v i a d o_{k - 1}

$Enviado_ {k - 1}$ y solo después de ese nudo

k - 1

$k - 1$ continúa procesando nuevas solicitudes.

2.4 Comparación con el protocolo de respaldo / primario

En la replicación en cadena, solo un servidor (cola) está involucrado en la ejecución de las solicitudes de lectura, y da una respuesta inmediata, mientras que en P / B primario puede esperar la confirmación de la finalización de las solicitudes de escritura.
En ambos enfoques, la solicitud de escritura se ejecuta en todos los servidores, P / B lo hace más rápido debido a la ejecución en paralelo.

Retrasos en la replicación de la cadena de fallas:

Encabezado: la ejecución de las solicitudes de lectura no se interrumpe, las solicitudes de escritura se retrasan en 2 mensajes: del maestro a todos los servidores sobre el nuevo encabezado y del maestro a todos los clientes sobre el nuevo encabezado.
Servidor intermedio: las solicitudes de lectura no se interrumpen. Las solicitudes de grabación pueden retrasarse en tiempo de ejecución $Sent_i$ No hay pérdidas de actualización.
Cola: Retraso de las solicitudes de lectura y escritura de dos mensajes: notificación $cola - 1$ sobre la nueva cola y alertar a los clientes sobre la nueva cola.

Falla P / B Retrasos:

Primario: 5 mensajes de retraso para seleccionar un nuevo estado primario y sincronizar.
Copia de seguridad: no hay retrasos de lectura si no hay solicitudes de escritura. Cuando aparece una solicitud de grabación, es posible un retraso de 1 mensaje.

Como puede ver, la peor falla de cola para la replicación de la cadena es más rápida que la peor para P / B (Primaria).

Los autores de este enfoque realizaron pruebas de carga, que mostraron un rendimiento comparable con el protocolo P / B.

3. Consultas distribuidas (replicación en cadena con consultas distribuidas - CRAQ)

El enfoque básico tiene una debilidad obvia: la cola, que maneja todas las solicitudes de lectura. Esto puede conducir a dos problemas:

La cola se convierte en punto de acceso, es decir Un servidor que maneja muchas más solicitudes que cualquier otro nodo.
Al colocar una cadena en varios centros de datos, la cola puede estar muy lejos, lo que ralentizará las solicitudes de escritura.

La idea de CRAQ es bastante simple: deje que las solicitudes de lectura lleguen a todos los servidores, excepto a tail, y para garantizar la coherencia, almacenaremos el vector de las versiones de objetos para las solicitudes de escritura, y en caso de ambigüedad, los nodos harán una solicitud de tail para obtener la última versión fija.

3.1 CRAQ

Formalizamos la arquitectura CRAQ:
Cada nodo, excepto la cola, procesa las solicitudes de lectura y devuelve una respuesta, y la cabeza devuelve una respuesta de las solicitudes de escritura (compárese con el enfoque básico).

En cada nodo que no sea de cola se pueden almacenar varias versiones del mismo objeto, y las versiones forman una secuencia estrictamente monótonamente creciente. Para cada versión, se agrega un atributo adicional "limpio" o "sucio". Inicialmente, todas las versiones son limpias.

Tan pronto como el nodo recibe una solicitud de escritura, agrega la versión recibida a la lista de versiones y luego:

Si el nodo es de cola, entonces marca la versión como limpia, en este momento la versión se considera fija y envía una confirmación por la cadena.
De lo contrario, marca la versión como sucia y envía la solicitud más abajo en la cadena.

Tan pronto como el nodo recibe la confirmación del sucesor, marca la versión como limpia y elimina todas las versiones anteriores.

Tan pronto como el nodo reciba una solicitud de lectura:

Si la última versión del objeto conocida por el nodo es limpia, entonces la devuelve.
De lo contrario, solicita una cola para obtener la última versión fija del objeto, que devuelve al cliente. (Por construcción, tal versión siempre estará en el nodo).

Para aplicaciones con predominio de solicitudes de lectura, el rendimiento de CRAQ crece linealmente con el crecimiento de nodos , en el caso de un predominio de solicitudes de escritura, el rendimiento no será peor que el enfoque básico.

CRAQ puede ubicarse tanto en uno como en varios centros de datos. Esto permite a los clientes seleccionar los nodos más cercanos para aumentar la velocidad de las solicitudes de lectura.

3.2 Consistencia en CRAQ

CRAQ proporciona una fuerte consistencia, excepto en un caso: cuando el nodo recibe la última versión confirmada de tail, tail puede confirmar la nueva versión antes de que el nodo responda al cliente. En esta situación, CRAQ proporciona una lectura monótona (las solicitudes de lectura secuencial no serán cosa del pasado, pero pueden devolver datos antiguos) en toda la cadena .

La consistencia débil también es posible:

Consistencia eventual: el nodo no solicitará la última versión confirmada de tail. Esto interrumpirá la lectura monótona en toda la cadena, pero mantendrá la lectura monótona en el mismo nodo . Además, puede soportar la tolerancia de particionamiento de red .
Consistencia eventual limitada: devuelve una versión sucia solo hasta cierto punto. Por ejemplo, la diferencia entre las versiones sucias y limpias no debe exceder N revisiones. O un límite de tiempo.

3.3 Conmutación por error del servidor

Similar al enfoque básico.

3.4 Opcional

CRAQ tiene una característica interesante: puede usar la multidifusión durante la operación de grabación. Supongamos que head envía el cambio con una multidifusión y envía a la cadena solo algún identificador para este evento. Si la actualización en sí no llegó al nodo, puede esperar y recibirla del siguiente nodo cuando Tail envía una confirmación del cambio. Del mismo modo, la cola puede enviar confirmación de fijación con multidifusión.

4. FAWN: una matriz rápida de nodos débiles

Un estudio muy interesante, no directamente relacionado con el tema de este artículo, pero sirve como un ejemplo del uso de la replicación en cadena.

Los almacenamientos de valores clave de alto rendimiento (Dynamo, memcached, Voldemort) tienen características comunes: requieren E / S, un mínimo de computación, acceso independiente paralelo a claves aleatorias en grandes cantidades y valores de clave pequeños de hasta 1Kb.

Los servidores con HDD no son adecuados para tales clústeres debido a la operación de búsqueda prolongada (tiempo de acceso aleatorio), y los servidores con una gran cantidad de DRAM consumen una cantidad sorprendentemente grande de energía: 2 GB de DRAM es equivalente a 1Tb HDD.

La construcción de un clúster efectivo (ancho de banda) con un consumo mínimo de energía es el objetivo del estudio original. El 50% del costo del servidor durante tres años es el costo de la electricidad, y los modos modernos de ahorro de energía no son tan efectivos como se anuncian: en las pruebas con una carga del 20%, el consumo de CPU se mantuvo en el 50%, además de que otros componentes del servidor no tienen modos de ahorro de energía ( DRAM, por ejemplo, ya funciona como mínimo). Es importante tener en cuenta que en tales grupos la brecha entre la CPU y la E / S se amplía: una CPU potente se ve obligada a esperar a que se complete la operación de E / S.

4.1 Arquitectura

El clúster FAWN está construido en servidores antiguos por $ 250 (precios de 2009), con una CPU integrada de 500MHz, 512Mb RAM, SSD de 32Gb. Si está familiarizado con la arquitectura Amazon Dynamo o el hashing consistente, entonces estará familiarizado con la arquitectura FAWN:

Cada servidor físico contiene varios nodos virtuales, cada uno tiene su propio VID.
Los VID forman un anillo, cada VID es responsable del rango "detrás de sí mismo" (por ejemplo, A1 es responsable de las claves en el rango R1).
Para aumentar la confiabilidad, los datos se replican en R de los siguientes nodos en sentido horario. (por ejemplo, con R = 2, la clave en A1 se replica a B1 y C1), por lo que obtenemos la replicación en cadena (enfoque básico).
Las solicitudes de lectura van a la cadena de cola, es decir Leer la clave de A1 irá a C1.
Las solicitudes de escritura van a la cadena principal y pasan hasta el final.

El mapa del servidor se almacena en un grupo de servidores frontend, cada uno de los cuales es responsable de su lista de VID específica, y puede redirigir la solicitud a otro servidor frontend.

4.2 Resultados de la prueba

En las pruebas de resistencia, el FAWN alcanza un QPS (consultas por segundo) del 90% del QPS en una unidad flash de lectura aleatoria.

La siguiente tabla compara el Costo total de propiedad (TCO) de varias configuraciones, donde la base de Traditional es un servidor de $ 1000 con un consumo de 200W (precios de 2009):

Por lo tanto, si:

Big data, pocas consultas: FAWN + 2Tb 7200 RPM
Una pequeña cantidad de datos, muchas solicitudes: FAWN + 2GB DRAM
Valores promedio: FAWN + 32GB SSD

Replicación en cadena: construir un repositorio KV efectivo (parte 1/2)