database - lamport - ¿Qué algoritmos existen para la conmutación por error en un sistema distribuido?

algoritmo centralizado sistemas distribuidos

Question

Estoy planeando hacer un sistema de base de datos distribuida utilizando una arquitectura de nada compartido y un control de concurrencia multiversión . La redundancia se logrará a través de la replicación asíncrona (se permite perder algunos cambios recientes en caso de una falla, siempre y cuando los datos en el sistema permanezcan consistentes). Para cada entrada de la base de datos, un nodo tiene la copia maestra (solo ese nodo tiene acceso de escritura), además de que uno o más nodos tienen copias secundarias de la entrada para fines de escalabilidad y redundancia (las copias secundarias son de solo lectura) . Cuando la copia maestra de una entrada se actualiza, se marca con la marca de tiempo y se envía de forma asíncrona a los nodos con copias secundarias para que finalmente obtengan la última versión de la entrada. El nodo que tiene la copia maestra puede cambiar en cualquier momento; si otro nodo necesita escribir esa entrada, solicitará al propietario actual de la copia maestra que otorgue a ese nodo la propiedad de la copia maestra de esa entrada, y luego de recibir la propiedad de ese nodo Puede escribir la entrada (todas las transacciones y escrituras son locales).

Últimamente, he estado pensando en qué hacer cuando un nodo del clúster se desactiva, qué estrategia utilizar para la conmutación por error. Aquí hay algunas preguntas. Espero que conozcas las alternativas disponibles para al menos algunas de ellas.

• ¿Qué algoritmos existen para hacer failover en un sistema distribuido?
• ¿Qué algoritmos existen para el consenso en un sistema distribuido?
• ¿Cómo deben los nodos del clúster determinar que un nodo está inactivo?
• ¿Cómo deben determinar los nodos que las entradas de la base de datos tenían su copia maestra en el nodo fallido en el momento de la falla, para que otros nodos puedan recuperar esas entradas?
• ¿Cómo decidir qué nodo (s) tiene la última copia secundaria de alguna entrada?
• ¿Cómo decidir que la copia secundaria de qué nodo debe promoverse para que sea la nueva copia maestra?
• ¿Cómo manejarlo, si el nodo que estaba fuera de servicio, de repente regresa como si nada hubiera pasado?
• ¿Cómo evitar los escenarios de cerebro dividido, donde la red se divide temporalmente en dos, y ambos lados piensan que el otro lado ha muerto?

Answer 1

Abordar solo una pequeña parte de su pregunta: no hay forma en el escenario que describe para decidir (en el resumen) qué nodo (s) tiene la última copia secundaria. En el mejor de los casos, algunos nodos pueden sondear y determinar (después de un poco de comunicación) quiénes entre los nodos que conocen / pueden ver, y que saben / pueden ver, y que no pueden ver que el antiguo maestro tiene la más actual dupdo. Pero:

• No pueden descubrir el estado de los nodos que no pueden alcanzar
• No pueden averiguar el estado de los nodos que no pueden alcanzarlos.
• No pueden estar seguros de que lo que creen saber sobre el estado de un nodo que puede ver el maestro antiguo cuando no pueden es actual, el maestro podría haber actualizado el vecino compartido después del estado informado del vecino.

En los temas más amplios, puede querer ver cómo algo como memcached y similares manejan los problemas, y especialmente leer las listas para ver qué problemas han encontrado cuando la teoría se unió a la práctica.

Answer 2

Este problema fue resuelto por DEC para VMS con Distributed Lock Manager . Las soluciones modernas se basan en este diseño. Lea el artículo de Wikipedia para algunas soluciones actuales. Debería mirar OCFS2 , que ahora es parte del kernel de Linux.

Answer 3

No lo sé, pero cuando haya terminado quiero descargar su sistema de base de datos distribuida.

Answer 4

Un gran blog que habla mucho sobre sistemas distribuidos y algoritmos distribuidos, incluida la implementación de Paxos, es http://the-paper-trail.org/

Answer 5

Usted está haciendo una pregunta absolutamente masiva, y mucho de lo que quiere saber todavía está en investigación activa.

Algunos pensamientos:

• Los sistemas distribuidos son difíciles, porque no hay sistemas infalibles para hacer frente a las fallas; en un sistema asíncrono, no hay forma de estar seguro de que un nodo esté inactivo o de que haya demora en la red. Esto puede sonar trivial, pero en realidad no lo es.
• La familia de algoritmos Paxos puede lograr un consenso, cuyas versiones se utilizan en la mesa grande de Google y en otros lugares.

Usted querrá ahondar en un libro de texto de sistemas distribuidos (o varios). Me gustan los sistemas distribuidos de Tannenbaum: Principios y paradigmas

Answer 6

* What algorithms there are for doing failover in a distributed system?

Posiblemente no algoritmos, tanto como sistemas. Necesita diseñar su arquitectura alrededor de las preguntas que ha hecho.

* What algorithms there are for consensus in a distributed system?

Probablemente quieras implementar Paxos. El simple Paxos no es demasiado difícil de entender. Si está intentando hacerlo a prueba de balas, lea el documento "Paxos Made Live" de Google. Si desea lograr un alto rendimiento, consulte Multi-Paxos.

* How should the nodes in the cluster determine that a node is down?

Depende. Los latidos del corazón son en realidad una muy buena manera de hacer esto. El problema es que tiene falsos positivos, pero eso es algo inevitable, y en un clúster en la misma LAN con una carga manejable son precisos. Lo bueno de Paxos es que los falsos positivos se tratan automáticamente. Sin embargo, si realmente necesita información de fallas para algún otro propósito, debe asegurarse de que está bien que detecte un nodo como fallido, pero en realidad solo está bajo carga y le lleva tiempo responder a un latido cardíaco.

* How should the nodes determine that what database entries had their master copy on the failed node at the time of failure, so that other nodes may recover those entries?
* How to decide that which node(s) has the latest secondary copy of some entry?
* How to decide that which node''s secondary copy should be promoted to be the new master copy?

Creo que realmente podría beneficiarse de leer el documento de Google FileSystem. En GFS hay un nodo maestro dedicado que realiza un seguimiento de qué nodos tienen qué bloques. Este esquema podría funcionar para usted, pero la clave es mantener los accesos a este maestro mínimo.

Si no almacena esta información en un nodo dedicado, tendrá que almacenarla en todas partes. Intente etiquetar los datos con la identificación del titular principal.

* How to handle it, if the node which was though to be down, suddenly comes back as if nothing happened?

Vea más arriba, pero el punto básico es que debe tener cuidado porque un nodo que ya no es el maestro podría pensar que lo es. Una cosa que no creo que hayas resuelto: ¿cómo llega una actualización al maestro? Es decir, ¿cómo sabe un cliente a qué nodo enviar la actualización?

* How to avoid split-brain scenarios, where the network is temporarily split into two, and both sides think that the other side has died?

Paxos trabaja aquí impidiendo el progreso en el caso de una división perfecta. De lo contrario, como antes, hay que tener mucho cuidado.

En general, resuelva la pregunta de saber qué nodo obtiene qué elemento de datos como maestro, y estará muy lejos de arreglar su arquitectura. Tenga en cuenta que no es posible que el nodo que recibe la actualización sea el maestro. ¿Qué sucede si se producen dos actualizaciones a la vez? Tampoco confíe en un reloj global sincronizado, de esa forma la locura. Probablemente desee evitar la ejecución de un consenso en cada escritura si puede evitarlo, por lo que quizás tenga un protocolo lento de conmutación por error maestro y una ruta de escritura rápida.

Siéntete libre de mandarme un correo fuera de línea si quieres saber más detalles. Mi blog http://the-paper-trail.org/ trata con muchas de estas cosas.

aclamaciones,

Enrique