¿Cuáles son los papeles seminales en sistemas distribuidos? ¿Por qué? Aprendiendo y Estudiando para siempre

Nota: esto está ligeramente relacionado con los problemas de los sistemas de procesamiento en línea escalables (en su mayoría, almacenamiento de datos y mensajería) . Como tal, puedo omitir documentos relacionados con otros temas (igualmente importantes) como HPC, seguridad en sistemas distribuidos y puede omitir documentos importantes en áreas teóricas como la Tolerancia a fallos bizantinos y algoritmos distribuidos.

Tampoco soy un investigador en este tema y puedo estar representando erróneamente algunos teoremas importantes: por favor, comente o sugiera ediciones en caso de errores.

Esta no es una lista exhaustiva. La lista de Henry contiene varios documentos adicionales que deben leerse a cualquier persona interesada en construir sistemas distribuidos prácticos.

Papeles “fundacionales”

Leslie Lamport, “Tiempo, relojes y ordenación de eventos en un sistema distribuido” http://research.microsoft.com/en…

Este documento es importante ya que proporciona una manera de razonar sobre el orden en el sistema distribuido. Conceptos como la replicación de la máquina de estado, los vectores de versión también se remontan a este documento.

El concepto de tiempo lógico también proporciona un “conjunto de herramientas” que se puede utilizar para probar y refutar teoremas en sistemas distribuidos.

Consenso, multidifusión confiable / atómica.

Un gran problema en los sistemas distribuidos es el consenso. Es decir, ¿cómo hacer que todas las máquinas estén de acuerdo con un cierto valor? Un “caso privado” importante de este problema es el problema de multidifusión atómica, o el caso de acordar un registro de mensajes, por ejemplo, una WAL en un sistema de base de datos.

Jim Gray, “Notas sobre el sistema operativo de la base de datos”
http://research.microsoft.com/~G…

Este artículo introduce el compromiso de dos fases. Complementa la idea bastante elegante de la replicación de la máquina de estados al proporcionar una forma para que varios nodos en una replicación distribuida coincidan en el orden de los mensajes (y, por lo tanto, terminen en el mismo estado final)

Fisher, Lynch, Patterson, “Imposibilidad de consenso distribuido con un proceso defectuoso”
http://theory.lcs.mit.edu/tds/pa…

También conocido como “El resultado de la imposibilidad de FLP”. Antes de que nos enamoremos demasiado del consenso y la belleza de la replicación de la máquina de estados, es importante comprender sus limitaciones. Este documento en particular demuestra que es imposible lograr un consenso en una red asíncrona si alguno de los nodos tiene una posibilidad de fallo distinta de cero. Se podría argumentar que el popular teorema de la PAC es una reafirmación elegante y un corolario del resultado de la imposibilidad de FLP.

Protocolos de consenso tolerantes a fallas: 3PC, Paxos, ZAB et al.

Paxos es un protocolo de consenso tolerante a fallas: puede soportar la falla de un coordinador. Sus variantes (como Multi-Paxos y ZAB: [nota: es probable que los comensales de ZooKeeper estén leyendo esto, así que, por favor, no me maten por afirmar que Zab es una variante exacta de Paxos, es más matizado que eso ]) ampliamente utilizado en la última década: el servicio Chubby de Google, Apache ZooKeeper, BerkeleyDB HA. La aplicación más común es proporcionar una vista coherente de un grupo (p. Ej., Membresía, elección del líder).

Leslie Lamport, “Part Time Parliament” y “Paxos Made Simple”
http://research.microsoft.com/en…
http://research.microsoft.com/en…

El parlamento a tiempo parcial presenta el documento a través de la alegoría de una democracia griega. Personalmente, me gustó mucho el estilo de ese papel, pero otros lo encontraron (en un juego de palabras) bastante griego. Paxos Made Simple lo puso en términos ingleses.

Papeles industriales paxos
Paxos hecho en vivo, Paxos para constructores de sistemas, ZooKeeper Atomic Broadcast
http://labs.google.com/papers/pa…
http://www.cnds.jhu.edu/pub/pape…
http://research.yahoo.com/pub/3514

El papel original de Paxos resuelve un problema algo más difícil de lo que es práctico de implementar en la producción. Estos artículos presentan ligeras modificaciones de los algoritmos de Paxos que lo hacen más práctico de usar (garantías de vida). ZooKeeper Atomic Broadcast es específicamente interesante: define nuevas garantías de ordenación que se necesitan para manejar la replicación pasiva, donde se acuerdan las actualizaciones de estado en lugar de las operaciones.

[Nota: hay una excelente publicación en el blog que cubre la importancia de estos documentos http: //betathoughts.blogspot.com…]

Ken Birman, “Explotación de la sincronía virtual en sistemas distribuidos”
http://www.cs.cornell.edu/home/r…
Un enfoque interesante para el middleware confiable orientado a problemas y mensajes (p. Ej., Pub / sub).

Aquí hay un artículo de 1993 de Cheriton y Skeen sobre las limitaciones de la mensajería causal y totalmente ordenada: http://net.pku.edu.cn/~course/cs…

Replicación de datos, nombres y enrutamiento

Paul Mockapetris, “Desarrollo del sistema de nombres de dominio”
http://cseweb.ucsd.edu/classes/w…
Un gran ejemplo de replicación optimista / consistencia eventual y una introducción a la asignación de nombres en un sistema distribuido (DNS, ¡que estamos usando para llegar a este sitio!)

Stoica et al, “Acorde: un servicio escalable de búsqueda de igual a igual para aplicaciones de Internet”
http://pdos.csail.mit.edu/papers…
Protocolo punto a punto para la búsqueda de datos

Rowston et al, “Pastelería”
http://research.microsoft.com/en…
Una vez que hayas rasgado algunos acordes, deberías tener una pasta. Otro excelente papel de nombre / enrutamiento P2P

Akamai, “Hashing consistente y árboles aleatorios”
http://www.akamai.com/dl/technic…

Para hacer una suposición alocada, casi todos los sitios web populares que ha abierto ahora en su navegador tienen algún contenido que se entrega a través de (una variante de) hashing consistente. Pueden ser imágenes enviadas desde un CDN o S3 o datos desde un almacén de datos como una implementación de Dynamo, MySQL / Postgres fragmentados personalizados o Memcache (según el cliente).

Saito et al, “Replicación optimista”
http://www.ysaito.com/survey.pdf

Como he mencionado antes, la consistencia fuerte no siempre es una opción práctica. Este documento cubre las muchas alternativas bien conocidas a la replicación “pesimista” (o basada en el consenso / transaccional). Quizás no sea tan seminal como cualquier cosa escrita por Lamport, pero se puede acceder de inmediato. Ayuda a poner lo que ya ha usado (por ejemplo, DNS, cvs / svn / git) en términos más formales.

Sistema de archivos de Google: documento bien conocido, no entraré en detalles aquí
http://labs.google.com/papers/gf…

Xerox PARC, algoritmos epidémicos para el mantenimiento de bases de datos replicadas,
http://www.bitsavers.org/pdf/xer…

Introduce los algoritmos de chismes para la eventual replicación.

Otro

Chandra y Toueg, “Detectores de falla no confiables y sistemas distribuidos confiables”,
http://www.cs.cornell.edu/home/s…
El resultado de la imposibilidad de FLP es una limitación teórica (¡así que tenga cuidado cuando un proveedor afirma que admite transacciones ACID en toda regla y anuncia una disponibilidad casi continua con baja latencia!), Pero en la práctica, los detectores de fallas imperfectas se pueden usar para solucionarlo y construir sistemas comerciales.

Leslie Lamport, el problema de los generales bizantinos
http://research.microsoft.com/en…

La mayoría de los protocolos de tolerancia a fallos y de consenso hasta ahora tratan con fallos “agradables” (las máquinas son lentas, las máquinas no funcionan, las máquinas envían datos fuera de orden o envían datos parciales). Desafortunadamente, el mundo real no es así. Hay enemigos maliciosos (máquinas comprometidas) y máquinas que actúan en un asunto completamente errático. Esto es (hasta donde entiendo) todavía un área abierta de investigación.

Eric Brewer, “Lecciones de servicios de Internet de escala gigante” http://citeseerx.ist.psu.edu/vie…

Analiza las experiencias de la construcción del motor de búsqueda Inktomi (nota al margen: ¡es fascinante contrastar lo que se consideró “Escala gigante” en 2001 vs. 2011!). Introduce los conceptos de cosecha y rendimiento.

MapReduce: http://labs.google.com/papers/ma…
No necesita presentación (es un artículo bien conocido), pero como Edward Ribeiro señaló en un comentario que realmente tomó como un concepto incluso independiente del sistema de archivos de Google y sus implementaciones. Junto con The Case for Shared Nothing de Stonebraker (mencionado en la respuesta de Henry Robinson), ha cambiado la forma en que se realiza el análisis de datos a gran escala.

Interesantes papeles industriales recientes.

PNUTs de Yahoo: http://www.brianfrankcooper.net/… Interesante en que combina la idea de bus de mensajes escalable (problema de multidifusión confiable) con un modelo de coherencia relajada que es entre la consistencia eventual y la consistencia sólida (basada en el consenso).

Dynamo de Amazon:
http: //www.allthingsdistributed….
Aunque los conceptos principales (hashing coherente, relojes vectoriales, consistencia eventual) se mencionan en otros documentos, este documento muestra cómo se pueden vincular entre sí para crear un almacén de clave / valor de baja latencia de alta disponibilidad. La elección de la disponibilidad en lugar de la coherencia también es bastante interesante (es bastante poco común en el mundo de la base de datos), al igual que las razones comerciales y las compensaciones de hacerlo.

9/13 / 11– Addendum

También hay una gran lista elaborada por Swami Sivasubramanian (que ha construido el Dynamo de Amazon y otros grandes sistemas distribuidos):

http://scalingsystems.com/2011/0…