Entón, imaxinémonos. Hai 5 gatos pechados na habitación, e para ir espertar ao dono, todos teñen que poñerse de acordo entre eles, porque só poden abrir a porta con cinco deles apoiados nela. Se un dos gatos é o gato de Schrödinger e os outros gatos non saben da súa decisión, xorde a pregunta: "Como poden facelo?"
Neste artigo falarei en termos sinxelos sobre o compoñente teórico do mundo dos sistemas distribuídos e os principios do seu funcionamento. Tamén examinarei superficialmente a idea principal que subxace a Paxos.
Cando os desenvolvedores usan infraestruturas na nube, varias bases de datos e traballan en clústeres dun gran número de nodos, confían en que os datos estarán completos, seguros e sempre dispoñibles. Pero onde están as garantías?
En esencia, as garantías que temos son garantías de provedores. Descríbense na documentación do seguinte xeito: "Este servizo é bastante fiable, ten un SLA determinado, non te preocupes, todo funcionará distribuído como esperas".
Tendemos a crer no mellor, porque os mozos intelixentes das grandes empresas aseguráronnos que todo estará ben. Non facemos a pregunta: por que, de feito, isto pode funcionar? Existe algunha xustificación formal para o correcto funcionamento destes sistemas?
Hai pouco fun a e inspirouse moito neste tema. As conferencias na escola eran máis como clases de cálculo que algo relacionado con sistemas informáticos. Pero así é exactamente como se probaron nun tempo os algoritmos máis importantes que usamos todos os días, sen sabelo.
A maioría dos sistemas distribuídos modernos usan o algoritmo de consenso de Paxos e as súas diversas modificacións. O máis chulo é que a validez e, en principio, a propia posibilidade da existencia deste algoritmo pódese probar simplemente cun bolígrafo e papel. Na práctica, o algoritmo úsase en grandes sistemas que se executan nun gran número de nodos nas nubes.
Unha lixeira ilustración do que se comentará a continuación: a tarefa de dous xeneraisBotámoslle un ollo para quentar .
Temos dous exércitos: vermello e branco. As tropas brancas están baseadas na cidade asediada. As tropas vermellas dirixidas polos xenerais A1 e A2 están situadas a dous lados da cidade. A tarefa dos pelirrojos é atacar a cidade branca e gañar. Non obstante, o exército de cada xeneral vermello individualmente é menor que o exército branco.
Condicións de vitoria dos vermellos: as dúas xerais deben atacar ao mesmo tempo para ter vantaxe numérica sobre as brancas. Para iso, os xenerais A1 e A2 deben chegar a un acordo entre eles. Se todos atacan por separado, os pelirrojos perderán.
Para chegar a un acordo, os xenerais A1 e A2 poden enviar mensaxeiros a través do territorio da cidade branca. O mensaxeiro pode chegar con éxito a un xeneral aliado ou pode ser interceptado polo inimigo. Pregunta: existe tal secuencia de comunicacións entre os xenerais pelirrojos (a secuencia de envío de mensaxeiros de A1 a A2 e viceversa de A2 a A1), na que estean garantidos para acordar un ataque á hora X. Aquí, garantías significan que ambos xenerais terán unha confirmación inequívoca de que un aliado (outro xeneral) atacará definitivamente no momento sinalado X.
Supoñamos que A1 envía un mensaxeiro a A2 coa mensaxe: "Ataquemos hoxe á media noite!" O xeneral A1 non pode atacar sen a confirmación do xeneral A2. Se chegou o mensaxeiro de A1, entón o xeneral A2 envía a confirmación coa mensaxe: "Si, imos matar aos brancos hoxe". Pero agora o xeneral A2 non sabe se o seu mensaxeiro chegou ou non, non ten garantía de se o ataque será simultáneo. Agora o Xeneral A2 volve necesitar confirmación.
Se describimos máis a súa comunicación, queda claro que non importa cantos ciclos de intercambio de mensaxes haxa, non hai forma de garantir que ambos os xenerais recibiron as súas mensaxes (asumindo que calquera mensaxeiro pode ser interceptado).
O problema dos dous xenerais é unha gran ilustración dun sistema distribuído moi sinxelo onde hai dous nodos cunha comunicación pouco fiable. Isto significa que non temos unha garantía do 100% de que estean sincronizados. Problemas semellantes só se discuten a maior escala máis adiante no artigo.
Introducimos o concepto de sistemas distribuídos
Un sistema distribuído é un grupo de ordenadores (en diante chamarémoslles nodos) que poden intercambiar mensaxes. Cada nodo individual é algún tipo de entidade autónoma. Un nodo pode procesar tarefas por si só, pero para comunicarse con outros nodos, necesita enviar e recibir mensaxes.
Como se implementan exactamente as mensaxes, que protocolos se utilizan - isto non nos interesa neste contexto. É importante que os nodos dun sistema distribuído poidan intercambiar datos entre si mediante o envío de mensaxes.
A definición en si non parece moi complicada, pero hai que ter en conta que un sistema distribuído ten unha serie de atributos que serán importantes para nós.
Atributos dos sistemas distribuídos
- Concorrencia – a posibilidade de que se produzan eventos simultáneos ou concorrentes no sistema. Ademais, consideraremos que os eventos que ocorren en dous nodos diferentes son potencialmente concorrentes sempre que non teñamos unha orde clara de ocorrencia destes eventos. Pero, por regra xeral, non o temos.
- Sen reloxo global. Non temos unha orde clara dos acontecementos debido á falta dun reloxo global. No mundo común das persoas, estamos afeitos a que temos reloxos e tempo absolutamente. Todo cambia cando se trata de sistemas distribuídos. Mesmo os reloxos atómicos ultra-precisos teñen deriva, e pode haber situacións nas que non podemos dicir cal dos dous eventos ocorreu primeiro. Polo tanto, tampouco podemos confiar no tempo.
- Fallo independente dos nodos do sistema. Hai outro problema: algo pode saír mal simplemente porque os nosos nodos non duran para sempre. O disco duro pode fallar, a máquina virtual na nube pode reiniciarse, a rede pode parpadear e perderanse as mensaxes. Ademais, pode haber situacións nas que os nodos funcionen, pero ao mesmo tempo funcionen contra o sistema. A última clase de problemas mesmo recibiu un nome separado: problema . O exemplo máis popular dun sistema distribuído con este problema é Blockchain. Pero hoxe non imos considerar esta clase especial de problemas. Interesaranos as situacións nas que simplemente un ou máis nodos poden fallar.
- Modelos de comunicación (modelos de mensaxería) entre nodos. Xa establecemos que os nodos se comunican intercambiando mensaxes. Hai dous modelos de mensaxería ben coñecidos: síncrona e asincrónica.
Modelos de comunicación entre nodos en sistemas distribuídos
Modelo sincrónico – sabemos con certeza que existe un delta de tempo finito coñecido durante o cal se garante que unha mensaxe chegue dun nodo a outro. Se este tempo pasou e a mensaxe non chegou, podemos dicir con seguridade que o nodo fallou. Neste modelo temos tempos de espera previsibles.
Modelo asíncrono – nos modelos asíncronos consideramos que o tempo de espera é finito, pero non existe tal delta de tempo despois do cal poidamos garantir que o nodo fallou. Eses. O tempo de espera dunha mensaxe dun nodo pode ser arbitrariamente longo. Esta é unha definición importante, e falaremos dela máis adiante.
O concepto de consenso en sistemas distribuídos
Antes de definir formalmente o concepto de consenso, consideremos un exemplo dunha situación na que o necesitamos, a saber: Replicación de máquinas de estado.
Temos algún rexistro distribuído. Gustaríanos que fose coherente e conteña datos idénticos en todos os nodos do sistema distribuído. Cando un dos nodos aprende un novo valor que vai escribir no rexistro, a súa tarefa pasa a ser ofrecer este valor a todos os outros nodos para que o rexistro se actualice en todos os nodos e o sistema pase a un novo estado consistente. Neste caso, é importante que os nodos estean de acordo entre si: todos os nodos coinciden en que o novo valor proposto é correcto, todos os nodos aceptan este valor e só neste caso todos poden escribir o novo valor no rexistro.
Noutras palabras: ningún dos nodos se oppuxo a que tiña información máis relevante e o valor proposto era incorrecto. O acordo entre nodos e o acordo sobre un único valor aceptado correcto é o consenso nun sistema distribuído. A continuación, falaremos de algoritmos que permiten garantir que un sistema distribuído chegue ao consenso.
Máis formalmente, podemos definir un algoritmo de consenso (ou simplemente un algoritmo de consenso) como unha determinada función que transfire un sistema distribuído do estado A ao estado B. Ademais, este estado é aceptado por todos os nodos, e todos os nodos poden confirmalo. Polo que se ve, esta tarefa non é tan trivial como parece a primeira vista.
Propiedades do algoritmo de consenso
O algoritmo de consenso debe ter tres propiedades para que o sistema continúe existindo e teña algún progreso ao pasar dun estado a outro:
- Acordo – todos os nodos que funcionan correctamente deben tomar o mesmo valor (nos artigos esta propiedade tamén se denomina propiedade de seguridade). Todos os nodos que están funcionando actualmente (non fallaron nin perderon o contacto cos outros) deben chegar a un acordo e aceptar algún valor común final.
É importante entender aquí que os nodos do sistema distribuído que estamos considerando queren estar de acordo. É dicir, agora estamos a falar de sistemas nos que algo pode simplemente fallar (por exemplo, algún nodo falla), pero neste sistema definitivamente non hai nodos que funcionen deliberadamente contra outros (a tarefa dos xenerais bizantinos). Debido a esta propiedade, o sistema segue sendo consistente.
- Integridade — se todos os nodos que funcionan correctamente ofrecen o mesmo valor v, o que significa que todos os nodos que funcionen correctamente deben aceptar este valor v.
- Terminación – todos os nodos que funcionen correctamente adquirirán un valor determinado (propiedade de vivacidade), o que permite que o algoritmo avance no sistema. Cada nodo que funcione correctamente debe aceptar tarde ou cedo o valor final e confirmalo: "Para min, este valor é certo, estou de acordo con todo o sistema".
Un exemplo de como funciona o algoritmo de consenso
Aínda que as propiedades do algoritmo poden non estar totalmente claras. Por iso, ilustraremos cun exemplo por que etapas atravesa o algoritmo de consenso máis sinxelo nun sistema cun modelo de mensaxería síncrona, no que todos os nodos funcionan como se espera, non se perden as mensaxes e non se rompe nada (realmente sucede isto?).
- Todo comeza cunha proposta de matrimonio (Propoñer). Supoñamos que un cliente conectouse a un nodo chamado "Nodo 1" e iniciou unha transacción, pasando un novo valor ao nodo - O. A partir de agora, chamaremos "Nodo 1" propoñer. Como propoñente, o "Nodo 1" agora debe notificar a todo o sistema que ten datos novos e envía mensaxes a todos os demais nodos: "Mira! O significado "O" veume e quero anotalo! Confirme que tamén gravará "O" no seu rexistro".
- A seguinte fase é a votación do valor proposto (Votación). Para que serve? Pode ocorrer que outros nodos recibiran información máis recente e teñan datos sobre a mesma transacción.
Cando o nodo "Nodo 1" envía a súa proposta, os outros nodos comproban os seus rexistros para ver os datos deste evento. Se non hai contradicións, os nodos anuncian: “Si, non teño outros datos para este evento. O valor "O" é a información máis recente que merecemos".En calquera outro caso, os nodos poden responder ao "Nodo 1": "Escoita! Teño datos máis recentes sobre esta transacción. Non "O", senón algo mellor".
Na fase de votación, os nodos toman unha decisión: ou aceptan todos o mesmo valor, ou un deles vota en contra, indicando que ten datos máis recentes.
- Se a rolda de votación foi exitosa e todos estaban a favor, entón o sistema pasa a unha nova etapa: aceptar o valor. "Nodo 1" recolle todas as respostas doutros nodos e informa: "Todos coincidiron no valor "O"! Agora declaro oficialmente que "O" é o noso novo significado, o mesmo para todos! Escríbeo no teu libriño, non o esquezas. Escríbeo no teu rexistro!"
- Os nodos restantes envían confirmación (Aceptado) de que anotaron o valor "O"; non chegou nada novo durante este tempo (unha especie de commit en dúas fases). Despois deste importante acontecemento, consideramos que a transacción distribuída finalizou.
Así, o algoritmo de consenso nun caso sinxelo consta de catro pasos: propoñer, votar (votar), aceptar (aceptar), confirmar a aceptación (aceptar).
Se nalgún paso non puidemos chegar a un acordo, entón o algoritmo comeza de novo, tendo en conta a información proporcionada polos nodos que se negaron a confirmar o valor proposto.
Algoritmo de consenso nun sistema asíncrono
Antes disto, todo era bo, porque estabamos a falar dun modelo de mensaxería sincrónica. Pero sabemos que no mundo moderno estamos afeitos a facer todo de forma asíncrona. Como funciona un algoritmo similar nun sistema cun modelo de mensaxería asíncrona, onde cremos que o tempo de espera para unha resposta dun nodo pode ser arbitrariamente longo (por certo, a falla dun nodo tamén se pode considerar como un exemplo cando un nodo pode responder durante un tempo arbitrariamente longo).
Agora que sabemos como funciona en principio o algoritmo de consenso, unha pregunta para aqueles lectores curiosos que chegaron ata aquí: cantos nodos nun sistema de N nodos cun modelo de mensaxe asíncrono poden fallar para que o sistema aínda poida chegar ao consenso?
A resposta correcta e a xustificación están detrás do spoiler.A resposta correcta é: 0. Se mesmo un nodo dun sistema asíncrono falla, o sistema non poderá chegar a un consenso. Esta afirmación está demostrada no teorema FLP, coñecido en certos círculos (1985, Fischer, Lynch, Paterson, ligazón ao orixinal ao final do artigo): “A imposibilidade de conseguir un consenso distribuído se falla polo menos un nodo. ”.
Rapaces, entón temos un problema, estamos afeitos a que todo sexa asíncrono. E aquí está. Como seguir vivindo?
Só falabamos de teoría, de matemáticas. Que significa "non se pode acadar o consenso", traducindo da linguaxe matemática á nosa -enxeñería? Isto significa que "non sempre se pode conseguir", é dicir. Hai un caso no que o consenso non é alcanzable. Que tipo de caso é este?
Esta é exactamente a violación da propiedade de vivacidade descrita anteriormente. Non temos un acordo común, e o sistema non pode ter progreso (non pode completarse nun tempo finito) no caso de que non teñamos unha resposta de todos os nodos. Porque nun sistema asíncrono non temos un tempo de resposta previsible e non podemos saber se un nodo fallou ou só tarda en responder.
Pero na práctica podemos atopar unha solución. Que o noso algoritmo poida funcionar durante moito tempo en caso de fallos (potencialmente pode funcionar indefinidamente). Pero na maioría das situacións, cando a maioría dos nodos funcionan correctamente, teremos progreso no sistema.
Na práctica, tratamos modelos de comunicación parcialmente sincrónicos. A sincronía parcial enténdese do seguinte xeito: no caso xeral, temos un modelo asíncrono, pero introdúcese formalmente un determinado concepto de "tempo de estabilización global" dun determinado momento no tempo.
Este momento pode non chegar por moito tempo, pero debe chegar algún día. Soará o espertador virtual, e a partir dese momento podemos predecir o delta horario para o que chegarán as mensaxes. A partir deste momento, o sistema pasa de asíncrono a sincrónico. Na práctica, tratamos precisamente con estes sistemas.
O algoritmo de Paxos resolve problemas de consenso
é unha familia de algoritmos que resolven o problema de consenso para sistemas parcialmente sincrónicos, suxeito á posibilidade de que algúns nodos poidan fallar. O autor de Paxos é . En 1989 propuxo unha proba formal da existencia e corrección do algoritmo.
Pero a proba resultou estar lonxe de ser trivial. A primeira publicación foi publicada só en 1998 (33 páxinas) describindo o algoritmo. Como se viu, era moi difícil de entender, e en 2001 publicouse unha explicación do artigo, que levou 14 páxinas. O volume de publicacións dáse para demostrar que, de feito, o problema do consenso non é nada sinxelo, e detrás de tales algoritmos atópase unha enorme cantidade de traballo das persoas máis intelixentes.
É interesante que o propio Leslie Lamport sinalase na súa conferencia que no segundo artigo explicativo hai unha afirmación, unha liña (non especificou cal), que se poden interpretar de diferentes xeitos. E por iso, un gran número de implementacións modernas de Paxos non funcionan completamente correctamente.
Unha análise detallada do traballo de Paxos levaría máis dun artigo, polo que tentarei transmitir moi brevemente a idea principal do algoritmo. Nas ligazóns ao final do meu artigo atoparás materiais para mergullar máis neste tema.
Papeis en Paxos
O algoritmo de Paxos ten un concepto de roles. Consideremos tres principais (hai modificacións con roles adicionais):
- Propoñentes (tamén se poden usar os termos: líderes ou coordinadores). Estes son os mozos que aprenden sobre algún novo valor do usuario e asumen o papel de líder. O seu cometido é lanzar unha rolda de propostas para un novo valor e coordinar máis accións dos nodos. Ademais, Paxos permite a presenza de varios dirixentes en determinadas situacións.
- Aceptores (Electores). Estes son nodos que votan para aceptar ou rexeitar un determinado valor. O seu papel é moi importante, porque deles depende a decisión: a que estado pasará (ou non) o sistema despois da seguinte etapa do algoritmo de consenso.
- Estudantes. Nodos que simplemente aceptan e escriben o novo valor aceptado cando o estado do sistema cambiou. Non toman decisións, só reciben os datos e poden entregalos ao usuario final.
Un nodo pode combinar varios roles en diferentes situacións.
O concepto de quórum
Supoñemos que temos un sistema de N nós E deles o máximo F os nodos poden fallar. Se os nodos F fallan, entón debemos ter polo menos 2F+1 nodos aceptadores.
Isto é necesario para que teñamos sempre a maioría, incluso na peor situación, de nodos “bos” que funcionen correctamente. É dicir F+1 "bo" nodos que acordaron, e o valor final será aceptado. En caso contrario, pode darse unha situación na que os nosos distintos grupos locais adquiran significados diferentes e non poidan poñerse de acordo entre eles. Polo tanto, necesitamos a maioría absoluta para gañar a votación.
A idea xeral de como funciona o algoritmo de consenso de Paxos
O algoritmo de Paxos implica dúas grandes fases, que á súa vez se dividen en dous pasos cada unha:
- Fase 1a: Preparación. Durante a fase de preparación, o líder (propoñente) informa a todos os nodos: “Comenzamos unha nova fase de votación. Temos unha nova rolda. O número desta rolda é n. Agora comezaremos a votar". Polo momento, simplemente informa do inicio dun novo ciclo, pero non informa dun novo valor. A tarefa desta etapa é iniciar unha nova rolda e informar a todos sobre o seu número único. O número redondo é importante, debe ser un valor maior que todos os números de votación anteriores de todos os líderes anteriores. Porque é grazas ao número redondo que outros nodos do sistema entenderán o recentes que son os datos do líder. É probable que outros nodos xa teñan resultados de votación de roldas moi posteriores e simplemente digan ao líder que está atrasado.
- Fase 1b: Promesa. Cando os nodos aceptadores recibiron o número da nova etapa de votación, son posibles dous resultados:
- O número n do novo voto é maior que o número de calquera voto anterior no que participou o aceptante. A continuación, o aceptante envía unha promesa ao líder de que non participará en máis votos cun número inferior a n. Se o aceptante xa votou por algo (é dicir, xa aceptou algún valor na segunda fase), entón atribúe á súa promesa o valor aceptado e o número do voto no que participou.
- En caso contrario, se o aceptante xa coñece o voto de maior número, pode simplemente ignorar o paso de preparación e non responder ao líder.
- Fase 2a: Aceptación. O líder debe esperar unha resposta do quórum (a maioría dos nodos do sistema) e, se se recibe o número necesario de respostas, ten dúas opcións para o desenvolvemento de eventos:
- Algúns dos aceptantes enviaron valores polos que xa votaran. Neste caso, o líder selecciona o valor do voto co número máximo. Chamemos a este valor x e envía unha mensaxe a todos os nodos como: "Aceptar (n, x)", onde o primeiro valor é o número de votación do seu propio paso Propoñer e o segundo valor é o que todos reuniron. é dicir. o valor polo que realmente votamos.
- Se ningún dos aceptantes enviou ningún valor, senón que simplemente prometeu votar nesta rolda, o líder pode invitalos a votar polo seu valor, o valor polo que se converteu en líder en primeiro lugar. Chamémoslle y. Envía unha mensaxe a todos os nodos como: "Aceptar (n, y)", semellante ao resultado anterior.
- Fase 2b: Aceptado. Ademais, os nodos aceptadores, ao recibir a mensaxe "Aceptar (...)" do líder, están de acordo con ela (enviar a confirmación a todos os nodos de que están de acordo co novo valor) só se non prometeron algún (outro) ). líder para participar na votación con número de rolda n' > n, se non, ignoran a solicitude de confirmación.
Se a maioría dos nodos responderon ao líder e todos confirmaron o novo valor, entón o novo valor considérase aceptado. Hurra! Se non se alcanza a maioría ou hai nodos que se negaron a aceptar o novo valor, entón todo comeza de novo.
Así funciona o algoritmo de Paxos. Cada unha destas etapas ten moitas sutilezas, practicamente non consideramos varios tipos de fallos, problemas de múltiples líderes e moito máis, pero o propósito deste artigo é só introducir ao lector no mundo da computación distribuída a un alto nivel.
Tamén cabe destacar que Paxos non é o único deste tipo, hai outros algoritmos, por exemplo, , pero este é un tema para outro artigo.
Ligazóns a materiais para estudos posteriores
Nivel principiante:
- , Preethi Kasireddy, artigo do blog sobre Medium
- , Adi Kancherla, artigo do blog sobre Medio
- , Ittai Abraham, blog
- , Ittai Abraham, artigo do blog
Nivel de Leslie Lampport:
- , Fischer, Lynch e Paterson, traballo de investigación, 1985
- , Leslie Lampport, traballo de investigación, 1998
- , Leslie Lampport, traballo de investigación, 2001
Fonte: www.habr.com