En los sistemas distribuidos, hay una serie de problemas fundamentales: transacciones distribuidas eficientes, procesamiento de datos exactamente una vez, sincronización precisa de relojes físicos. Para resolver este último problema , se inventaron diferentes tipos de relojes lógicos .
Sin embargo, los relojes vectoriales tienen propiedades desagradables: introducen una dependencia condicional entre eventos donde no existe y la pierden donde realmente está.
Sin embargo, puede encontrar algo más confiable: Kronos. En el artículo, veremos el algoritmo de contabilidad de la relación causa-efecto y su aplicación para construir el repositorio Key-Value con transacciones distribuidas.
Los problemas
Como ya se mencionó, hay una serie de problemas con el reloj lógico:
Las dependencias inexistentes surgen porque un reloj lógico introduce un orden completo en los eventos, es decir, se puede decir que cualquiera de los dos eventos es condicional antes y que condicionalmente más tarde. El contrato es condicional, ya que es imposible determinar con precisión la relación entre eventos en el tiempo, incluso debido a la Teoría Especial de la Relatividad.
Por otro lado, un reloj lógico solo considera la interconexión a través de mensajes dentro del sistema. Si se conectan algunos dos eventos, pero fuera del sistema, por ejemplo, a través del usuario (agregando productos a la cesta en una parte del sistema -> pago del pedido), entonces el reloj lógico puede perder esa relación.
No se puede acceder a los relojes lógicos desde el exterior, y también es difícil interconectar varios componentes independientes (sistema de archivos distribuido, servicios de procesamiento de solicitudes, análisis).
Solución
Un artículo de 2014 de Kronos: The Design and Implementation of Event Eventing Service propone una solución: un servicio independiente que tendrá en cuenta las relaciones de causa y efecto en los eventos.
La abstracción principal dentro de Kronos es un evento en el que se introduce el ordenamiento parcial. La relación de causalidad es transitiva, es decir, si, por ejemplo, sabemos que la creación de un archivo precede a su cambio, y el cambio precede a la eliminación, podemos llegar a una conclusión lógica de que la creación se produjo antes de la eliminación.
La API mínima se puede definir mediante el siguiente conjunto de métodos:
| Método | Resultado | Comentario |
|---|
create_event() | e | Crea un nuevo evento en Kronos |
query_order([(e_1, e_2), ...]) | [<-, concurrent, ->, ...] | Para cada par de la solicitud, devuelve la dirección de la relación de causa y efecto, o la simultaneidad de los eventos. |
assign_order([(e_1, e_2, must), (e_3, e_4, prefer), ...]) | OK/FAIL | Para cada par de la solicitud, establece la dirección de causalidad |
acquire_ref(e) | OK | Aumenta el contador de referencia para este evento. |
release_ref(e) | OK | Disminuye el recuento de referencias para este evento. |
Implementación
Es lógico que el sistema se base en un gráfico de eventos orientado, con una búsqueda efectiva de amplitud para verificar la relación de eventos, un mecanismo de estabilidad en caso de falla y recolección de basura.
Como se puede ver en la API, la solicitud assign_order acepta un tipo de relación causal: must or prefer . must corresponde a invariantes estrictos; por ejemplo, _->_ , prefer no se puede aplicar si entra en conflicto con las relaciones must . Un ejemplo de uso de prefer es que las solicitudes que vinieron antes están mejor envueltas antes, pero esto no afecta la corrección.
BFS efectivo
En nuestro caso, el gráfico puede ser grande, pero los eventos para los que se ejecutarán las solicitudes de verificación generalmente estarán cerca. Por lo tanto, debe ejecutar BFS más rápido para tales casos.
En la implementación estándar, el lugar más largo es la inicialización de la matriz de vértices visitados, que siempre lleva un tiempo igual al número de vértices en el gráfico. En cambio, puedes usar una tabla hash o aplicar otros trucos.
Recolección de basura
Como puede ver en la tabla, hay dos métodos más: acquire_ref y release_ref .
Dentro de Kronos, se almacena un contador de referencia para cada evento. Si bien algunos servicios procesan el evento o se reservan la posibilidad de agregar nuevos eventos que suceden después del actual, almacena el enlace. Cuando esta necesidad desaparece, el servicio llama a release_ref .
Kronos eliminará el evento cuando se cumplan todas las condiciones:
- El número de enlaces llegó a cero
- Todos los eventos que preceden a esto ya se eliminan del gráfico.
Este enfoque no limita las posibles consultas, pero ahorra memoria dentro de Kronos.
Aplicaciones
Considere el uso del sistema usando el ejemplo de almacenamiento de valor clave con transacciones distribuidas.
Supongamos que hay varios servidores, cada servidor es responsable de un rango de claves.
Cada transacción corresponde a un evento en Kronos. Para cada clave, el servidor debe almacenar el número de la última transacción en la que participó esta clave. El cliente crea un evento y envía su número a todos los servidores cuyas claves se ven afectadas por esta transacción. El servidor está intentando crear una dependencia en Kronos entre el número de transacción actual y el evento anterior que se guardó para esta clave. Si no puede crear la dependencia, la transacción se reconoce como no exitosa (tenga en cuenta que hasta ahora todavía no hay interacción con los datos).
Si toda la operación de agregar dependencia se completó con éxito, esto significa que la transacción se llevará a cabo y se puede realizar. Los servidores se enteran de esto por el cliente y comienzan a ejecutar partes de la transacción.
Tenga en cuenta que dichas transacciones serán ACID :
- Atomicidad : la transacción no se programará en Kronos o se ejecutará en todos los nodos.
- Consistencia : automáticamente en repositorios KV.
- Aislamiento : si dos transacciones se cruzan de acuerdo con los datos, entonces estarán conectadas por una relación causal en Kronos, lo que significa que una se ejecutará antes que la otra.
- Durabilidad : dado que Kronos es resistente a caídas y supone que todas las réplicas de la bóveda también son estables, lo único que debe probar es la persistencia de los datos de las transacciones pendientes. De hecho, si el cliente marca la transacción como exitosa, pero el registro aún no se ha completado en el servidor, entonces este hecho es fácil de establecer, ya que el servidor también realiza un seguimiento de las partes completadas de las transacciones.
Rendimiento
Implementar tal almacenamiento de KV puede ser realmente efectivo. El artículo original cita datos de que la implementación descrita del almacenamiento KV es 4 veces más rápida que la transacción basada en bloqueos.
Además, en comparación con MongoDB, el sistema en la parte superior de Kronos tiene solo un 6% de retraso, a pesar de que MongoDB no utiliza transacciones distribuidas.
Análisis
Sin embargo, la operación de Kronos tiene varias desventajas.
- Primero, existe la sobrecarga de acceder a Kronos: cada solicitud requerirá al menos una llamada.
- Kronos también será un punto único de falla: los autores del artículo no ofrecen formas de particionar el gráfico de eventos.
- Sería bueno agregar una serie de métodos al sistema. Por ejemplo, en el ejemplo con KV-storage sería bueno tener una devolución de llamada que informaría al servidor sobre el estado de la transacción, se agregó con éxito al gráfico con todas las dependencias necesarias, o, por el contrario, la transacción no se pudo completar.
Sin embargo, el sistema descrito permite un control flexible de una relación causal entre eventos, asegurando el cumplimiento predecible de los invariantes necesarios.
Conclusión
Sobre esto, nosotros en GoTo School enseñamos a estudiantes y escolares en la dirección de Sistemas Distribuidos.
Y hay algoritmos y aplicaciones , programación aplicada, bioinformática y análisis de datos
Ven a nuestra escuela de otoño del 27 de octubre al 4 de noviembre o a la escuela de invierno a principios de enero.
Y si ya no eres un estudiante o un colegial, ven a enseñar .