Así que imaginemos. 5 gatos están encerrados en la habitación, y para poder despertar al dueño, deben ponerse de acuerdo todos juntos en esto, porque solo pueden abrir la puerta apoyándose en ella con cinco de ellos. Si uno de los gatos es el gato de Schrödinger y los otros gatos desconocen su decisión, surge la pregunta: "¿Cómo pueden hacer esto?"
En este artículo, le contaré en términos simples sobre el componente teórico del mundo de los sistemas distribuidos y los principios de su trabajo. Y también considerar superficialmente la idea principal que subyace a Paxos'a.
Cuando los desarrolladores utilizan infraestructuras en la nube, varias bases de datos, trabajan en clústeres de una gran cantidad de nodos, confían en que los datos serán consistentes, seguros y estarán siempre disponibles. Pero, ¿dónde están las garantías?
De hecho, las garantías que tenemos son garantías de proveedores. Están descritos en la documentación de la siguiente manera: "Este servicio es bastante confiable, tiene un SLA dado, no te preocupes, todo funcionará distribuido como esperas".
Tendemos a creer en lo mejor, porque los tíos listos de las grandes empresas nos aseguran que todo saldrá bien. No hacemos la pregunta: ¿por qué, de hecho, puede funcionar esto? ¿Existe alguna justificación formal para el correcto funcionamiento de dichos sistemas?
Hace poco fui a y estaba muy inspirado por este tema. Las conferencias en la escuela se parecían más a clases de análisis matemático que a algo relacionado con los sistemas informáticos. Pero así es exactamente como se probaron en su momento los algoritmos más importantes que usamos todos los días, sin sospecharlo.
La mayoría de los sistemas distribuidos modernos utilizan el algoritmo de consenso de Paxos y sus diversas modificaciones. Lo mejor es que la validez y, en principio, la posibilidad misma de la existencia de este algoritmo se puede probar simplemente con lápiz y papel. Al mismo tiempo, en la práctica, el algoritmo se usa en grandes sistemas que operan en una gran cantidad de nodos en las nubes.
Ilustración ligera de lo que se discutirá a continuación: el problema de dos generalesEchemos un vistazo al calentamiento. .
Tenemos dos ejércitos: rojo y blanco. Las tropas blancas tienen su base en la ciudad sitiada. Las tropas rojas dirigidas por los generales A1 y A2 están ubicadas en dos lados de la ciudad. La tarea de los pelirrojos es atacar la ciudad blanca y ganar. Sin embargo, el ejército de cada general rojo individualmente es más pequeño que el ejército de blancos.
Condiciones de victoria de los pelirrojos: ambos generales deben atacar a la vez para tener ventaja numérica sobre los blancos. Para hacer esto, los generales A1 y A2 deben estar de acuerdo entre sí. Si todos atacan por separado, los pelirrojos perderán.
Para negociar, los generales A1 y A2 pueden enviar mensajeros entre sí a través del territorio de la ciudad blanca. El mensajero puede llegar con éxito a un general aliado o puede ser interceptado por el enemigo. Pregunta: ¿existe tal secuencia de comunicaciones entre los generales pelirrojos (la secuencia de envío de mensajeros de A1 a A2 y viceversa de A2 a A1), en la que se garantiza que acordarán un ataque en la hora X? Aquí, por garantías se entiende que ambos generales tendrán confirmación inequívoca de que un aliado (otro general) atacará exactamente en el momento señalado X.
Supongamos que A1 envía un mensajero a A2 con el mensaje: "¡Ataquemos hoy a la medianoche!". El General A1 no puede atacar sin la confirmación del General A2. Si el mensajero de A1 ha llegado, entonces el general A2 envía una confirmación con el mensaje: "Sí, llenemos los blancos hoy". Pero ahora el General A2 no sabe si su mensajero ha llegado o no, no tiene garantías de que el ataque sea simultáneo. Ahora General A2 nuevamente necesita confirmación.
Si describimos más su comunicación, resulta lo siguiente: no importa cuántos ciclos de intercambio de mensajes haya, no hay forma de garantizar que ambos generales hayan recibido sus mensajes (suponiendo que cualquiera de los mensajeros pueda ser interceptado).
El problema de los dos generales es una gran ilustración de un sistema distribuido muy simple donde hay dos nodos con comunicación poco confiable. Así que no tenemos una garantía del 100% de que estén sincronizados. Sobre problemas similares solo en una escala mayor más adelante en el artículo.
Introducción al concepto de sistemas distribuidos
Un sistema distribuido es un grupo de computadoras (en lo sucesivo, nodos) que pueden intercambiar mensajes. Cada nodo individual es una entidad autónoma. Un nodo puede procesar tareas por sí mismo, pero para poder comunicarse con otros nodos, necesita enviar y recibir mensajes.
Cómo se implementan específicamente los mensajes, qué protocolos se utilizan: esto no nos interesa en este contexto. Es importante que los nodos de un sistema distribuido puedan intercambiar datos entre sí mediante el envío de mensajes.
La definición en sí no parece muy complicada, pero tenga en cuenta que un sistema distribuido tiene una serie de atributos que serán importantes para nosotros.
Atributos de los sistemas distribuidos
- Concurrencia – la posibilidad de ocurrencia de eventos simultáneos o competitivos en el sistema. Además, consideraremos que los eventos que ocurrieron en dos nodos diferentes son potencialmente concurrentes hasta que tengamos un orden claro en el que ocurren estos eventos. Y normalmente no lo hacemos.
- Sin reloj mundial. No tenemos un orden claro de eventos debido a la falta de un reloj global. En el mundo ordinario de las personas, estamos acostumbrados al hecho de que tenemos horas y tiempo absolutamente. Todo cambia cuando se trata de sistemas distribuidos. Incluso los relojes atómicos ultraprecisos tienen deriva, y hay situaciones en las que no podemos saber cuál de los dos eventos ocurrió primero. Por lo tanto, tampoco podemos confiar en el tiempo.
- Fallo independiente de los nodos del sistema.. Hay otro problema: algo puede salir mal simplemente porque nuestros nodos no son eternos. El disco duro puede fallar, la máquina virtual en la nube puede reiniciarse, la red puede parpadear y los mensajes se perderán. Además, hay situaciones en las que los nodos funcionan, pero al mismo tiempo funcionan en contra del sistema. La última clase de problemas incluso recibió un nombre separado: el problema . El ejemplo más popular de un sistema distribuido con tal problema es Blockchain. Pero hoy no consideraremos esta clase especial de problemas. Nos interesarán las situaciones en las que solo uno o más nodos pueden fallar.
- Modelos de comunicación (modelos de mensajería) entre nodos. Ya hemos descubierto que los nodos se comunican intercambiando mensajes. Hay dos modelos de mensajería bien conocidos: síncrono y asíncrono.
Modelos de comunicación entre nodos en sistemas distribuidos
modelo síncrono - sabemos con certeza que hay un delta de tiempo finito conocido durante el cual se garantiza que el mensaje llegue de un nodo a otro. Si se acabó este tiempo y el mensaje no ha llegado, podemos decir con seguridad que el nodo ha fallado. En tal modelo, tenemos un tiempo de espera predecible.
modelo asíncrono – en modelos asíncronos, asumimos que el tiempo de espera es finito, pero no hay tiempo delta después del cual se puede garantizar que el nodo ha fallado. Aquellos. el tiempo de espera de un mensaje de un nodo puede ser arbitrariamente largo. Esta es una definición importante, y hablaremos de ella más adelante.
El concepto de consenso en sistemas distribuidos
Antes de definir formalmente el concepto de consenso, considere un ejemplo de una situación en la que lo necesitamos, a saber: Replicación de máquinas de estado.
Tenemos algo de registro distribuido. Nos gustaría que fuera coherente y que contuviera datos idénticos en todos los nodos de un sistema distribuido. Cuando uno de los nodos aprende un nuevo valor que va a escribir en el registro, su tarea es ofrecer este valor a todos los demás nodos para que el registro se actualice en todos los nodos y el sistema cambie a un nuevo estado consistente. Al mismo tiempo, es importante que los nodos estén de acuerdo entre ellos: todos los nodos están de acuerdo en que el nuevo valor propuesto es correcto, todos los nodos aceptan este valor y solo en este caso todos pueden registrar un nuevo valor.
En otras palabras: ninguno de los nodos objetó que tenían información más actualizada y el valor propuesto era incorrecto. Un acuerdo entre nodos y acuerdo sobre un único valor aceptado correcto es el consenso en un sistema distribuido. A continuación, hablaremos de algoritmos que permiten que un sistema distribuido llegue a un consenso con garantía.
Más formalmente, podemos definir un algoritmo de consenso (o simplemente un algoritmo de consenso) como alguna función que lleva un sistema distribuido del estado A al estado B. Además, este estado es aceptado por todos los nodos y todos los nodos pueden confirmarlo. Resulta que esta tarea no es tan trivial como parece a primera vista.
Propiedades del algoritmo de consenso
El algoritmo de consenso debe tener tres propiedades para que el sistema continúe existiendo y tenga algún progreso en la transición de un estado a otro:
- Agreement – todos los nodos que funcionen correctamente deben tomar el mismo valor (en los artículos esta propiedad también se encuentra como propiedad de seguridad). Todos los nodos que ahora están funcionando (que no estén fuera de servicio y que no hayan perdido el contacto con el resto) deben llegar a un acuerdo y aceptar algún valor común final.
Es importante entender aquí que los nodos en el sistema distribuido que estamos considerando quieren estar de acuerdo. Es decir, ahora estamos hablando de sistemas en los que algo puede fallar simplemente (por ejemplo, algún nodo falla), pero en este sistema definitivamente no hay nodos que trabajen deliberadamente contra otros (la tarea de los generales bizantinos). Debido a esta propiedad, el sistema permanece consistente.
- Integridad - si todos los nodos que funcionan correctamente ofrecen el mismo valor v, por lo que cada nodo que funcione correctamente debe aceptar este valor v.
- Terminación - todos los nodos que funcionan correctamente eventualmente tomarán algún valor (propiedad de vida), lo que permite que el algoritmo progrese en el sistema. Cada nodo individual que funcione correctamente debe, tarde o temprano, aceptar el valor final y confirmarlo: "Para mí, este valor es verdadero, estoy de acuerdo con todo el sistema".
Un ejemplo de cómo funciona el algoritmo de consenso
Si bien las propiedades del algoritmo pueden no estar del todo claras. Por lo tanto, ilustraremos con un ejemplo por qué etapas pasa el algoritmo de consenso más simple en un sistema con un modelo de mensajería síncrona, en el que todos los nodos funcionan como se espera, los mensajes no se pierden y nada se rompe (¿esto realmente sucede?).
- Todo comienza con una propuesta de matrimonio (Proponer). Supongamos que un cliente se conecta a un nodo llamado "Nodo 1" e inicia una transacción, pasando un nuevo valor al nodo - O. De ahora en adelante, llamaremos "Nodo 1" proponer. Como el proponente "Nodo 1" ahora tiene que notificar a todo el sistema que tiene datos nuevos, y envía mensajes a todos los demás nodos: "¡Mira! ¡Recibí el valor "O" y quiero anotarlo! Confirme que también registrará "O" en su registro".
- La siguiente etapa es votar por el valor propuesto (Votación). ¿Para qué sirve? Puede suceder que otros nodos hayan recibido información más reciente y tengan datos sobre la misma transacción.
Cuando el nodo "Nodo 1" envía su propuesta, los otros nodos verifican sus registros en busca de datos sobre este evento. Si no hay conflicto, los nodos anuncian: “Sí, no tengo otros datos para este evento. El valor 'O' es la información más actualizada que merecemos".En cualquier otro caso, los nodos pueden responder al "Nodo 1": "¡Escucha! Tengo datos más recientes sobre esta transacción. No "Oh", sino algo mejor".
En la etapa de votación, los nodos toman una decisión: o todos aceptan el mismo valor, o uno de ellos vota en contra, denotando que tiene datos más recientes.
- Si la ronda de votación fue exitosa y todos estuvieron a favor, entonces el sistema pasa a una nueva etapa: aceptación del valor (Aceptar). El "Nodo 1" recopila todas las respuestas de otros nodos e informa: "¡Todos estuvieron de acuerdo con el valor 'O'! Ahora declaro oficialmente que "O" es nuestro nuevo significado, ¡el mismo para todos! Anótalo en tu cuaderno, no lo olvides. ¡Escriba en su registro!"
- El resto de nodos envían confirmación (Aceptado) de que han anotado el valor “O” para ellos mismos, no se ha recibido nada nuevo durante este tiempo (una especie de commit en dos fases). Después de este evento trascendental, consideramos que la transacción distribuida se ha completado.
Así, el algoritmo de consenso en un caso simple consta de cuatro pasos: proponer, votar (voting), aceptación (accept), confirmación de aceptación (acepted).
Si en algún paso no pudimos llegar a un acuerdo, entonces se reinicia el algoritmo, teniendo en cuenta la información proporcionada por los nodos que se negaron a confirmar el valor propuesto.
Algoritmo de consenso en sistema asíncrono
Antes de eso, todo iba bien, porque se trataba del modelo de mensajería síncrona. Pero sabemos que en el mundo moderno estamos acostumbrados a hacer todo de forma asíncrona. ¿Cómo funciona un algoritmo similar en un sistema con un modelo de mensajería asincrónica, donde creemos que el tiempo de espera para una respuesta de un nodo puede ser arbitrariamente largo (por cierto, la falla de un nodo también se puede considerar como un ejemplo cuando un nodo puede responder arbitrariamente largo).
Ahora que sabemos cómo funciona en principio el algoritmo de consenso, la pregunta es para aquellos lectores curiosos que han llegado a este punto: ¿cuántos nodos de un sistema de N nodos con un modelo de mensaje asíncrono pueden caer para que el sistema aún pueda alcanzar el consenso? ?
La respuesta correcta y la razón detrás del spoiler.La respuesta correcta es: 0. Si incluso un nodo en un sistema asíncrono deja de funcionar, el sistema no podrá llegar a un consenso. Esta afirmación se demuestra en el conocido teorema FLP (1985, Fischer, Lynch, Paterson, enlace al original al final del artículo): “La imposibilidad de alcanzar un consenso distribuido si al menos un nodo falla”.
Chicos, entonces tenemos un problema, estamos acostumbrados a que todo sea asíncrono con nosotros. Y aquí está. ¿Cómo seguir viviendo?
Acabamos de hablar de teoría, de matemáticas. ¿Qué significa "no se puede llegar a un consenso", traduciendo del lenguaje matemático al nuestro: la ingeniería? Esto significa que "no siempre se puede lograr", es decir, hay un caso en el que el consenso no es alcanzable. ¿Y cuál es este caso?
Esta es exactamente la violación de la propiedad de vitalidad descrita anteriormente. No tenemos un acuerdo común, y el sistema no puede avanzar (no puede terminar en un tiempo finito) en el caso de que no tengamos respuesta de todos los nodos. Porque en un sistema asíncrono no tenemos un tiempo de respuesta predecible y no podemos saber si un nodo está inactivo o simplemente tarda mucho en responder.
Pero en la práctica, podemos encontrar una solución. Deje que nuestro algoritmo pueda ejecutarse durante mucho tiempo en caso de fallas (potencialmente puede ejecutarse indefinidamente). Pero en la mayoría de las situaciones, cuando la mayoría de los nodos estén funcionando correctamente, tendremos progreso en el sistema.
En la práctica, estamos tratando con modelos de comunicación parcialmente síncronos. El sincronismo parcial se entiende de la siguiente manera: en el caso general, tenemos un modelo asíncrono, pero se introduce formalmente un cierto concepto de “tiempo de estabilización global” de un determinado punto en el tiempo.
Este momento en el tiempo puede no llegar hasta dentro de un tiempo arbitrariamente largo, pero un día debe llegar. El despertador virtual sonará, ya partir de ese momento podremos predecir el delta de tiempo en el que llegarán los mensajes. A partir de este momento, el sistema pasa de asincrónico a síncrono. En la práctica, nos ocupamos de tales sistemas.
El algoritmo de Paxos resuelve problemas de consenso
es una familia de algoritmos que resuelven el problema de consenso para sistemas parcialmente síncronos, siempre que algunos nodos puedan fallar. El autor de Paxos es . Propuso una prueba formal de la existencia y corrección del algoritmo en 1989.
Pero la prueba resultó ser de ninguna manera trivial. La primera publicación fue lanzada solo en 1998 (33 páginas) que describe el algoritmo. Al final resultó que, era extremadamente difícil de entender, y en 2001 se publicó una explicación para el artículo, que ocupaba 14 páginas. Los volúmenes de publicaciones se dan para mostrar que, de hecho, el problema del consenso no es nada simple, y detrás de tales algoritmos hay un gran trabajo de las personas más inteligentes.
Es interesante que el mismo Leslie Lampor en su conferencia señaló que en el segundo artículo-explicación hay una declaración, una línea (no especificó cuál), que puede interpretarse de diferentes maneras. Y debido a esto, una gran cantidad de implementaciones modernas de Paxos no funcionan del todo correctamente.
Un análisis detallado del trabajo de Paxos llevará más de un artículo, por lo que intentaré transmitir la idea principal del algoritmo muy brevemente. En los enlaces al final de mi artículo, encontrará materiales para profundizar en este tema.
Funciones en Paxos
El algoritmo de Paxos tiene un concepto de roles. Considere tres principales (hay modificaciones con roles adicionales):
- Proponentes (también puede haber términos: líderes o coordinadores). Estos son los tipos que aprenden sobre un nuevo significado del usuario y asumen el papel de líder. Su tarea es lanzar una ronda de propuestas para un nuevo valor y coordinar futuras acciones de los nodos. Además, Paxos permite la presencia de varios líderes en determinadas situaciones.
- Aceptadores (votantes). Estos son los nodos que votan para aceptar o rechazar un valor particular. Su papel es muy importante, porque de ellos depende la decisión: a qué estado irá (o no irá) el sistema después de la siguiente etapa del algoritmo de consenso.
- Estudiantes. Nodos que simplemente aceptan y escriben el nuevo valor aceptado cuando el estado del sistema ha cambiado. No toman decisiones, solo reciben datos y pueden dárselos al usuario final.
Un nodo puede combinar varios roles en diferentes situaciones.
El concepto de quórum
Suponemos que tenemos un sistema de N nodos y la mayoría de ellos F los nodos pueden fallar. Si los nodos F fallan, deberíamos tener al menos 2F+1 nodos aceptores.
Esto es necesario para que siempre, incluso en la peor situación, los nodos "buenos" que funcionan correctamente tengan una mayoría. Eso es F+1 Nodos "buenos" que acordaron, y se aceptará el valor final. De lo contrario, puede haber una situación en la que diferentes grupos locales adquieran significados diferentes y no puedan ponerse de acuerdo entre ellos. Entonces necesitamos una mayoría absoluta para ganar la votación.
Idea general del algoritmo de consenso de Paxos
El algoritmo de Paxos asume dos grandes fases, que a su vez se dividen en dos pasos cada una:
- Fase 1a: Preparar. Durante la etapa de preparación, el líder (proponente) informa a todos los nodos: “Estamos iniciando una nueva etapa de votación. Tenemos una nueva ronda. El número de esta ronda es n. Comenzaremos a votar ahora". Hasta ahora, solo informa el inicio de un nuevo ciclo, pero no informa el nuevo valor. La tarea de esta etapa es iniciar una nueva ronda e informar a todos de su número único. El número redondo es importante, debe ser mayor que todos los números de votación anteriores de todos los líderes anteriores. Ya que es gracias al número redondo que otros nodos en el sistema entenderán qué tan frescos son los datos del líder. Probablemente otros nodos ya tengan resultados de votaciones de rondas posteriores y simplemente le dirán al líder que está atrasado.
- Fase 1b: Promesa. Cuando los nodos aceptantes han recibido el número de la nueva etapa de votación, son posibles dos resultados:
- El número n de la nueva votación es mayor que el número de cualquiera de las votaciones anteriores en las que participó el aceptante. Luego, el aceptante envía una promesa al líder de que ya no participará en ningún voto con un número menor que n. Si el aceptante ya ha votado por algo (es decir, ya ha aceptado algún valor en la segunda fase), entonces añade a su promesa el valor aceptado y el número de la votación en la que participó.
- De lo contrario, si el aceptador ya conoce el voto con número alto, simplemente puede ignorar el paso de preparación y no responder al líder.
- Fase 2a: Aceptar. El líder debe esperar una respuesta del quórum (la mayoría de los nodos del sistema) y, si se recibe la cantidad de respuestas requerida, entonces tiene dos opciones para el desarrollo de eventos:
- Algunos de los aceptantes han presentado valores por los que ya votaron. En este caso, el líder elige el valor de la votación con el número más alto. Llamemos a este valor x y enviemos un mensaje como este a todos los nodos: "Aceptar (n, x)", donde el primer valor es el número de votación de su propio paso Proponer, y el segundo valor es para lo que todos se reunieron, es decir valor por el que, de hecho, votamos.
- Si ninguno de los aceptantes envió ningún valor, sino que simplemente prometieron votar en esta ronda, el líder puede invitarlos a votar por su valor, el valor por el cual se convirtió en líder. Llamémoslo y. Envía a todos los nodos un mensaje de la forma: "Aceptar (n, y)", por analogía con el resultado anterior.
- Fase 2b: Aceptada. Además, los nodos aceptantes, al recibir el mensaje "Aceptar (...)", del líder están de acuerdo (enviar confirmación a todos los nodos de que están de acuerdo con el nuevo valor) solo si no han prometido a algunos (otros) el líder para participar en la votación con el número de la ronda n' > nde lo contrario, ignoran el aviso de confirmación.
Si la mayoría de los nodos respondieron al líder y todos confirmaron el nuevo valor, entonces el nuevo valor se considera aceptado. ¡Hurra! Si no se alcanza la mayoría o hay nodos que se negaron a aceptar el nuevo valor, todo vuelve a empezar.
Así es como funciona el algoritmo de Paxos. Cada una de estas etapas tiene muchas sutilezas, prácticamente no consideramos varios tipos de fallas, problemas de múltiples líderes y mucho más, pero el propósito de este artículo es solo introducir al lector al mundo de la computación distribuida al más alto nivel.
También vale la pena señalar que Paxos no es el único de su tipo, existen otros algoritmos, por ejemplo, , pero este es un tema para otro artículo.
Enlaces a materiales para estudios adicionales
Nivel principiante:
- , Preethi Kasireddy, artículo de blog en Medium
- , Adi Kancherla, artículo de blog en Medium
- Blog de Ittai Abraham
- , Ittai Abraham, artículo de blog
Leslie Lamport Nivel:
- Fischer, Lynch y Paterson, artículo de investigación, 1985
- , Leslie Lamport, artículo de investigación, 1998
- , Leslie Lamport, artículo de investigación, 2001
Fuente: habr.com