Continuamos considerando ejemplos del uso de la replicación en cadena. Las definiciones y arquitecturas básicas se dieron en la primera parte , le recomiendo que se familiarice con ellas antes de leer la segunda parte.

En este artículo, estudiaremos los siguientes sistemas:

• Hibari es un repositorio tolerante a fallos distribuido escrito en erlang.
• HyperDex: almacenamiento distribuido de valores clave con soporte para búsqueda rápida por atributos secundarios y búsqueda por rango.
• ChainReaction - Causal + consistencia y geo-replicación.
• Creación de un sistema distribuido sin utilizar procesos externos adicionales de monitoreo / reconfiguración.

5. Hibari

Hibari es un repositorio KV tolerante a fallas distribuido escrito en erlang. Utiliza la replicación de cadena (enfoque básico), es decir logra una consistencia estricta. En las pruebas, Hibari muestra un alto rendimiento: se logran varios miles de actualizaciones por segundo en servidores de dos unidades (solicitudes de 1Kb)

5.1 Arquitectura

El hashing constante se utiliza para colocar datos. La base del almacenamiento son los bloques físicos y lógicos. El ladrillo físico es un servidor con Linux, tal vez una instancia EC2 y, en general, la VM en su conjunto. Un ladrillo lógico es una instancia de almacenamiento con la que funcionan los procesos principales del clúster, y cada bloque es un nodo en cualquier cadena. En el siguiente ejemplo, el clúster está configurado con 2 bloques lógicos en cada bloque físico y con una longitud de cadena de 2. Tenga en cuenta que los nodos de la cadena están "untados" sobre los bloques físicos para aumentar la confiabilidad.

El proceso maestro (consulte la definición en la primera parte) se denomina servidor de administración .

Los datos se almacenan en "tablas", que simplemente se dividen en espacios de nombres, cada tabla se almacena en al menos una cadena, y cada cadena almacena datos en una sola tabla.

El cliente Hibari recibe actualizaciones del servidor de administración con una lista de todos los encabezados y cola de todas las cadenas (y todas las tablas). Por lo tanto, los clientes saben de inmediato a qué nodo lógico enviar la solicitud.

5.2 Hashing

Hibari usa un par $$$\ {T, K \}$ para determinar el nombre de la cadena que almacena la clave $$$K$ en la mesa $$$T$ : clave $$$K$ mapeado al intervalo $$$[0.1, 1.0)$ (usando MD5), que se divide en secciones de las cuales una cadena es responsable. Las secciones pueden ser de diferentes anchos, dependiendo del "peso" de la cadena, por ejemplo:



Por lo tanto, si algunos bloques físicos son muy poderosos, entonces las cadenas ubicadas en él pueden tener secciones más anchas (entonces caerán más llaves sobre ellas).

6. HyperDex

El objetivo de este proyecto era construir un repositorio distribuido de valores clave, que, a diferencia de otras soluciones populares (BigTable, Cassandra, Dynamo), admitirá una búsqueda rápida de atributos secundarios y pueda realizar rápidamente una búsqueda de rango. Por ejemplo, en los sistemas considerados anteriormente, para buscar todos los valores en un cierto rango, debe pasar por todos los servidores, lo que, obviamente, es inaceptable. HyperDex resuelve este problema utilizando Hyperspace Hashing .

6.1 Arquitectura

La idea del hash hiperespacial es construir $$$n$ -dimensional espacio donde cada atributo corresponde a un eje de coordenadas. Por ejemplo, para los objetos (nombre, apellido, número de teléfono), el espacio podría verse así:



El hiperplano gris pasa a través de todas las teclas, donde apellido = Smith, amarillo - a través de todas las teclas, donde nombre = John. La intersección de estos planos forma una respuesta a los números de teléfono de búsqueda de personas con el nombre de John y el apellido Smith. Entonces la solicitud de $$$k$ atributos devuelve $$$(n-k)$ -espacio tridimensional.

El espacio de búsqueda se divide en $$$n$ tridimensionales disjuntas, y cada región se asigna a un único servidor. Un objeto con coordenadas de una región se almacena en el servidor de esta región. Por lo tanto, se crea un hash entre objetos y servidores.

Una consulta de búsqueda (por rango) determinará las regiones incluidas en el hiperplano resultante y, por lo tanto, reducirá al mínimo el número de servidores encuestados.

Hay un problema con este enfoque: la cantidad de servidores necesarios crece exponencialmente a partir de la cantidad de atributos, es decir, si atributos $$$k$ entonces necesitas $$$O (2 ^ k)$ servidores Para resolver este problema, HyperDex aplica una partición del hiperespacio en subespacios (con una dimensión inferior) con, respectivamente, un subconjunto de atributos:

6.2 Replicación

Para garantizar una consistencia estricta, los autores desarrollaron un enfoque especial basado en la replicación de la cadena: encadenamiento dependiente del valor , donde cada nodo posterior se determina mediante el hash del atributo correspondiente. Por ejemplo, la clave $$$("John", "Smith")$ primero será desplazado hacia el espacio clave (obtenemos la cadena de la cabeza, también llamada punto líder ), luego el hash de$$ $ en línea $ "John" $ en línea $ a la coordenada en el eje correspondiente y así sucesivamente. (Consulte la imagen a continuación para ver un ejemplo de actualización. $$$u_1$ )

Todas las actualizaciones pasan a través de un líder de puntos, que ordena las solicitudes (linealización).



Si la actualización produce un cambio en la región, primero se escribe la nueva versión inmediatamente después de la anterior (ver actualización $$$u_2$ ), y después de recibir el ACK de la cola, se cambiará el enlace a la versión anterior del servidor anterior. A solicitudes concurrentes (p. Ej. $$$u_2$ y $$$u_3$ ) no violó el punto de coherencia, el líder agrega versiones y otra información meta al servidor, si se recibe $$$u_3$ antes $$$u_2$ podría determinar que el pedido está roto y que necesita esperar $$$u_2$ .

7. Reacción en cadena

Se utiliza un modelo causal + de convergencia, que agrega la condición para la convergencia libre de conflicto a la convergencia causal (causal). Para cumplir con la convergencia causal, se agregan metadatos a cada solicitud, lo que indica las versiones de todas las claves causalmente dependientes. ChainReaction le permite hacer una replicación geográfica en varios centros de datos y es un desarrollo adicional de la idea de CRAQ.

7.1 Arquitectura

La arquitectura de FAWN se usa con cambios menores: cada DC consta de servidores de datos (backends (almacenamiento de datos, replicación, formar un anillo DHT) y proxies de cliente (front-end) (envíe una solicitud a un nodo específico). Cada clave se replica en R nodos consecutivos, formando una cadena. Las solicitudes de lectura se procesan por cola y las de cabeza.

7.2 Un centro de datos

Observamos una propiedad importante que surge de la replicación de la cadena, si el nodo $$$k$ causal-consistente con algunas operaciones del cliente, luego todos los nodos anteriores también. Entonces si la operación $$$Op$ fue visto por última vez por nosotros en el sitio $$$j$ , entonces todos dependientes de la causalidad (de $$$Op$ ) las operaciones de lectura solo se pueden realizar en nodos desde la cabeza hasta $$$j$ . Tan pronto como $$$Op$ se ejecutará en la cola, no habrá restricciones de lectura. Denote las operaciones de escritura que se realizaron por tail en DC $$$d$ como DC-Write-Stable (d) .

Cada cliente almacena una lista (metadatos) de todas las claves solicitadas por el cliente en el formato (clave, versión, chainIndex), donde chainIndex es la posición del nodo en la cadena que respondió a la última solicitud de clave. Los metadatos se almacenan solo para las claves que el cliente no sabe si es DC-Write-Stable (d) o no .

7.2.1 Operación de escritura

Tenga en cuenta que una vez que la operación se ha convertido en DC-Write-Stable (d), ninguna solicitud de lectura puede leer versiones anteriores.

Para cada solicitud de escritura, una lista de todas las teclas en las que se realizaron operaciones de lectura antes de agregar la última operación de escritura. Tan pronto como el proxy del cliente recibe la solicitud, realiza lecturas de bloqueo en las colas de todas las claves de los metadatos (estamos esperando la confirmación de la disponibilidad de la misma versión o una más nueva, en otras palabras, cumplimos la condición de coherencia causal). Tan pronto como se reciben las confirmaciones, la solicitud de escritura se envía al jefe de la cadena correspondiente.



Una vez que el nuevo valor se almacena en $$$k$ nodos de la cadena, se envía una notificación al cliente (con el índice del último nodo). El cliente actualiza el chainIndex y elimina los metadatos de las claves enviadas, como se supo de ellos que son DC-Write-Stable (d). En paralelo, la grabación continúa aún más: propagación diferida . Por lo tanto, se da prioridad a las operaciones de escritura en el primer $$$k$ nodos Tan pronto como tail almacena la nueva versión de la clave, se envía una notificación al cliente y se transmite a todos los nodos de la cadena para que marquen la clave como estable.

7.2.2 Operación de lectura

El proxy del cliente envía una solicitud de lectura a $$$index: = rand (1, chainIndex)$ nodo en el circuito, mientras distribuye la carga. En respuesta, el nodo envía el valor y la versión de este valor. La respuesta se envía al cliente, mientras que:

• Si la versión es estable, entonces el nuevo chainIndex es igual al tamaño de la cadena.
• Si la versión es más nueva, entonces el nuevo chainIndex = index.
• De lo contrario, chainIndex no cambia.

7.2.3 Conmutación por error del nodo

Es casi completamente idéntico al enfoque básico, con algunas diferencias en el hecho de que en algunos casos el chainIndex del cliente deja de ser válido; esto se determina fácilmente cuando se ejecutan solicitudes (no hay clave con esta versión) y la solicitud se redirige al jefe de la cadena para buscar el nodo con la versión deseada.

7.3 Varios ( $$$N$ ) centros de datos (replicación geográfica)

Tomamos como base algoritmos de una arquitectura de servidor único y los adaptamos al mínimo. Para empezar, en los metadatos, en lugar de solo los valores version y chainIndex, necesitamos vectores versionados de N dimensiones.

Definimos Global-Write-Stable de manera similar con DC-Write-Stable (d): la operación de escritura se considera Global-Write-Stable si se realizó en forma de cruz en todos los DC.

Aparece un nuevo componente en cada DC: remote_proxy , su tarea es recibir / enviar actualizaciones de otros DC.

7.3.1 Realizar una operación de escritura (en el servidor $$$i$ )

El comienzo es similar a una arquitectura de servidor único: realizamos lecturas de bloqueo, escribimos en el primero $$$k$ nudos de una cadena. En este punto, el proxy del cliente envía al cliente un nuevo vector chainIndex, donde los ceros están en todas partes, excepto la posición $$$i$ - hay un significado $$$k$ . Siguiente, como siempre. Una operación adicional al final: la actualización se envía a remote_proxy, que acumula varias solicitudes y luego envía todo.

Aquí surgen dos problemas:

• ¿Cómo asegurar dependencias entre diferentes actualizaciones provenientes de diferentes DC?
  
  Cada remote_proxy almacena un vector de versión local $$$rvp$ dimensiones $$$N$ , que almacena el número de actualizaciones enviadas y recibidas, y lo envía en cada actualización. Por lo tanto, al recibir una actualización de otro DC, remote_proxy verifica los contadores, y si el contador local es menor, la operación se bloquea hasta que se reciba la actualización correspondiente.
• ¿Cómo proporcionar dependencias para esta operación en otros DC?
  
  Esto se logra utilizando un filtro Bloom. Al realizar operaciones de escritura / lectura desde el proxy del cliente, además de los metadatos, también se envía un filtro de floración para cada clave (llamados filtros de respuesta). Estos filtros se almacenan en la lista AccessedObjects y, cuando se solicitan operaciones de escritura / lectura, los metadatos también envían filtros OR a las claves enviadas (denominado filtro de dependencia). Del mismo modo, después de la operación de escritura, se eliminan los filtros correspondientes. Al enviar una operación de escritura a otro DC, también se envían un filtro de dependencia y un filtro de respuesta para esta solicitud.
  
  Además, el DC remoto, después de haber recibido toda esta información, verifica que si los bits establecidos del filtro de respuesta coinciden con los bits establecidos de varios filtros de consulta, entonces tales operaciones son potencialmente dependientes casuales. Potencialmente, porque un filtro de floración.

7.3.2 Operación de lectura

De manera similar a una arquitectura de servidor único, ajustada para usar el vector chainIndex en lugar de un escalar y la posibilidad de que falte una clave en el DC (porque las actualizaciones son asíncronas), espere o redirija la solicitud a otro DC.

7.3.3 Resolución de conflictos

Gracias a los metadatos, las operaciones causales dependientes siempre se realizan en el orden correcto (a veces hay que bloquear el proceso para esto). Pero los cambios competitivos en diferentes países en desarrollo pueden generar conflictos. Para resolver tales situaciones, se utiliza Last Write Wins, para el cual hay un par presente en cada operación de actualización $$$(reloj, s)$ donde $$$c$ - horas en proxy, y $$$s$ - Identificación de DC.

7.3.4 Manejo de fallas de nodo

Similar a la arquitectura de servidor único.

8. Aprovechamiento de fragmentación en el diseño de protocolos de replicación escalables

El objetivo del estudio es construir un sistema distribuido con fragmentos y con replicación sin utilizar un proceso maestro externo para reconfigurar / monitorear el clúster.

En los principales enfoques actuales, los autores ven las siguientes desventajas:

Replicación:

• Primaria / Copia de seguridad: conduce a una discrepancia en el estado si Primaria se identificó erróneamente como fallida.
• Intersección del quórum: puede provocar una discrepancia de estado durante la reconfiguración del clúster.

Consistencia estricta:

• Los protocolos se basan en algoritmos de votación mayoritaria (por ejemplo, Paxos) cuando sea necesario $$$2 * N + 1$ nudos $$$N$ nodos

Detección de fallas de nodos:

• P / B y CR implican la presencia de detección ideal de nodos fallidos con un modelo de detención de fallos, que es inalcanzable en la práctica y debe elegir un intervalo de exploración adecuado.
• ZooKeeper está sujeto a los mismos problemas: con una gran cantidad de clientes, se requiere una cantidad de tiempo considerable (> 1 segundo) para que actualicen la configuración.

El enfoque propuesto por los autores, llamado replicación elástica , carece de estas deficiencias y tiene las siguientes características:

• Consistencia estricta.
• Para soportar la caída $$$N$ los nodos deben tener $$$N + 1$ nudo
• Reconfiguración sin pérdida de consistencia.
• No hay necesidad de protocolos de consenso basados ​​en un voto mayoritario.

Placa resumen:

8.1 Organización de réplicas

Cada fragmento define una secuencia de configuraciones $$$\ mathcal {C} = C_1 :: C_2 :: C_3 \ dots$ por ejemplo, la nueva configuración no contiene algún tipo de réplica caída $$$\ mathcal {C} = \ mathcal {C}: :( Réplicas \ setminus R_j)$

Cada elemento de la secuencia de configuración consta de:

• réplicas: un conjunto de réplicas.
• orderer : identificación de una réplica con un rol especial (ver más abajo).

Cada fragmento está representado por un conjunto de réplicas (por construcción - $$$N$ ), es decir no dividimos los roles de "fragmento" y "réplica".

Cada réplica almacena los siguientes datos:

• conf - id de la configuración a la que pertenece esta réplica.
• orden: qué réplica es la orden de esta configuración.
• modo - modo réplica, uno de tres: $$$PENDIENTE$ (todas las réplicas de $$$C_1$ ), $$$ACTIVO$ (todas las réplicas de $$$C_1$ ), $$$INMUTABLE$ .
• historial: secuencia de operaciones en los datos de réplica reales $$$op_1 :: op_2 :: \ dots$ (o solo una condición).
• estable: la longitud máxima del prefijo del historial que fija esta réplica. Obviamente $$$0 <= estable <= longitud (historial)$ .

El objetivo principal de un pedido de réplica es enviar solicitudes al resto de las réplicas y mantener el prefijo de historial más grande:

8.2 Organización de fragmentos

Los fragmentos se combinan en anillos llamados bandas elásticas . Cada fragmento pertenece a un solo anillo. El precursor de cada fragmento $$$X$ realiza un papel especial: él es un secuenciador para él. El trabajo del secuenciador es dar a su sucesor una nueva configuración en caso de fallas de réplica.


Se requieren dos condiciones:

• Cada banda elástica tiene al menos un fragmento y una réplica de trabajo.
• Cada banda elástica tiene al menos un fragmento, en el que funcionan todas las réplicas.

La segunda condición parece demasiado estricta, pero es equivalente a la condición "tradicional" de que el proceso maestro nunca cae.

8.3 Uso de la replicación en cadena

Como habrás adivinado, las réplicas están organizadas como una cadena (enfoque básico): el encargado será el responsable, con ligeras diferencias:

• En caso de falla en CR, el nodo es arrojado fuera de la cadena (y reemplazado por uno nuevo), en ER - se crea una nueva cadena.
• Las solicitudes de lectura en CR se procesan por cola, en ER, pasan por toda la cadena de la misma manera que las solicitudes de escritura.

8.5 Reconfiguración en caso de falla

• Las réplicas son monitoreadas tanto por las réplicas de su fragmento como por las réplicas de un fragmento secuenciador.
• Tan pronto como se detecta una falla, las réplicas envían un comando al respecto.
• Sequencer envía una nueva configuración (sin una réplica fallida).
• Se crea una nueva réplica que sincroniza su estado con la banda elástica.
• Después de eso, el secuenciador envía la nueva configuración con la réplica agregada.

Referencias

• Hibari
• hyperdex.orgerdex.org
• HyperDex: un almacén de valores clave distribuido y con capacidad de búsqueda
• Reacción en cadena
• Aprovechamiento de fragmentación en el diseño de protocolos de replicación escalables