Hola a todos!
Hoy nos gustaría volver a tocar el tema de la ejecución simultánea y secuencial en varios programas, especialmente en sistemas distribuidos. En septiembre, publicamos el artículo "La
sincronicidad es un mito " sobre este tema, y ahora estamos publicando una traducción de un estudio más serio, que, esperamos, lo ayudará a navegar mejor con sistemas distribuidos.
Solo hay un problema real en informática: admitir que los errores de invalidación de caché se nombran incorrectamente. Estos son solo errores unitarios relacionados con el uso del tiempo.
- Autor desconocido
El tiempo es una cosa extraña.
Esta vez es muy extraña, porque realmente queremos creer que está completamente optimizada. Nos parece que cualquier evento a las 15.00 ocurre (como diríamos) antes de cualquier evento a las 16.00, sin excepciones, argumentos o compromisos.
Sin embargo, la informática conoce muchos ejemplos cuando es necesario abordar este requisito de manera no tan estricta. Se manifiesta a nivel de procesadores, compiladores, nodos de red. Una y otra vez en los cálculos, en diferentes niveles de la pila, nos encontramos en situaciones en las que nos enfrentamos a dos eventos, y no sabemos en qué orden ocurrieron. El tiempo obviamente no es total; Ella está fragmentada.
Por qué El hecho es que no lo sabemos, ya que el nivel de abstracción sobre el que existimos no proporciona una respuesta a esta pregunta. Ya sea accidental o no, nuestras abstracciones computacionales no dan garantías con respecto al procedimiento. La libertad de reordenar eventos a menudo le permite crear sistemas mucho más productivos y asequibles.
El procesador puede tener un
modelo de pedido de memoria ; refleja lo que garantiza que el procesador no quiere brindarle ninguna garantía en la etapa de ensamblaje, por ejemplo, qué instrucción se ejecutó antes y cuál después. El procesador decide exactamente cómo transmitir las instrucciones y las ejecuta fuera de servicio, es decir, utiliza sus chips de manera más eficiente de lo que hubiera pensado.
Un idioma puede tener un
modelo de coincidencia de memoria ("modelo de memoria" para abreviar); refleja lo que garantiza que el lenguaje no le brinda al generar un ensamblado, por ejemplo, al distribuir instrucciones en varios subprocesos. Tal reordenamiento es, por definición, inherente al modelo de hardware de la memoria y explica en gran medida por qué se proporciona un concepto de tiempo tan "débil" en los compiladores. Está dentro del marco de dicho modelo de memoria implementado en el lenguaje que usted programa cuando escribe código sin bloqueo.
Un ejemplo famoso de un modelo de memoria implementado a nivel de lenguaje es el
modelo de memoria fuerte y débil en el estándar C ++ 11. Por defecto, C ++ proporciona operaciones atómicas con sincronización, pero también puede debilitar el modelo de acceso a la memoria para mejorar el rendimiento. El comportamiento proporcionado de esta manera está destinado a servir como una abstracción sobre las arquitecturas del procesador principal utilizadas hoy (x86, POWER y ARM).
Finalmente, un sistema distribuido puede tener su propio modelo de consistencia; refleja lo que garantiza que el sistema no le dará con respecto al orden de los eventos en los clientes y las réplicas en la red informática mundial. Los pedidos que están directamente relacionados con la latencia de comunicación o la falta de sincronización explican principalmente por qué en un sistema distribuido no puede prescindir del mencionado modelo de tiempo débil. Es este modelo de consistencia lo que usted programa cuando escribe una aplicación distribuida.
En la práctica, hay un gran
zoológico de modelos de consistencia que puede usar al programar un sistema distribuido. En todas esas situaciones, estos modelos describen el comportamiento (deseado) del sistema observado desde fuera de ese sistema. Si yo, un cliente específico o una secuencia específica, escribo un valor, luego lo leo de inmediato, ¿está garantizado que definitivamente veré un registro no más antiguo que el mío? Si el tiempo no estuviera fragmentado, si siempre tuviéramos una idea clara en qué orden se desarrollan las operaciones en nuestro sistema, naturalmente, la respuesta a esta pregunta sería afirmativa. Sería extraño hacer tal pregunta en absoluto.
Pero el tiempo es fragmentario, por lo tanto, es necesario plantear esa pregunta.
Modelos de consistencia: quiero decir, modelos de memoria
Hablar de un orden tan fragmentado es a menudo difícil y siempre desagradable. Nos gustaría comenzar por el hecho de que en todos los niveles de la pila, el tiempo siempre es absolutamente absoluto, ya sea con transacciones ACID u operaciones / bloqueos atómicos. ¡Cuanto más estrictas sean las garantías, más fácil será programar con ellas!
Pero todos luchamos por la velocidad. Ya sea que se trate de sistemas distribuidos en los que se deba sacrificar la consistencia estricta en aras de la accesibilidad, o sobre la programación sin bloqueo, donde se usa un modelo de memoria débil para evitar los costos de sincronización, generalmente es recomendable que un programador que trabaje con cualquier nivel de la pila entre en estos argumentos complejos .
La consistencia de los modelos de memoria compartida y la consistencia de los modelos de memoria distribuida son ambas
abstractas . Describen el programador que trabaja con el sistema, la interfaz de este sistema. Permiten comprender qué tipos de comportamiento corresponden a un modelo de memoria débil, dado que las propiedades generales del ordenamiento de eventos en el sistema, que damos por sentado, ya no actúan en él. Puede parecer que estos dos modelos de memoria son similares, sin embargo, ambas comunidades han desarrollado sus propios discursos para la discusión. Los valores utilizados en ellos difieren, aunque se superponen.
Ya imaginamos cuán confundido puede ser esto. Que hacer
Descripción del tiempo como entidad, lo que implica entre dos y ocho tipos de orden parcial.
En
su libro de 2014, Sebastian Burkhardt busca proporcionar una descripción exhaustiva de las muchas opciones para modelos de consistencia. Con esta característica, junto con otras estructuras matemáticas, se utilizan dos variantes del ordenamiento lógico de los eventos: "visibilidad" y "arbitraje", mencionados anteriormente también en otros trabajos de Burkhardt et al, ver, por ejemplo, el
artículo sobre señalar y verificar tipos de datos replicados (2014).
La "visibilidad" es un orden parcial inherente al condicionamiento potencial. Le permite rastrear qué eventos (posiblemente en otras réplicas) son visibles para qué otros eventos. No hay requisitos de visibilidad aparte de acyclicity; los eventos en un objeto pueden ser visibles para los eventos en otro objeto, y la operación de leer o escribir un evento no afecta su visibilidad para otros eventos.
La "arbitrariedad" es un orden general que le permite rastrear cómo un sistema distribuido en el que surge una situación de elección juzgará qué evento ocurre antes y cuál después.
Dado que los modelos de consistencia distribuida son similares a los modelos de memoria, resulta que tales fenómenos de visibilidad y aleatoriedad también pueden ser útiles cuando se discuten modelos de memoria. En particular,
en el apéndice de su artículo de 2014, Burkhardt demuestra "cuán cerca" está el modelo de memoria débil de C ++ 11 a la coherencia objeto por causalidad, pero con algunas desviaciones interesantes. Esto se discutirá en el resto de la publicación.
Para empezar, desarrollemos la visibilidad y la aleatoriedad, teniendo en cuenta la "lectura" y el "orden de los cambios". Al "leer", la visibilidad entre dos objetos se tendrá en cuenta solo en situaciones en las que tanto la lectura como la escritura tocan el mismo objeto, y cuando se lee solo un registro (o más de uno) puede ser visible.
Esto corresponde a una situación en la que un procesador con memoria compartida en un momento dado puede registrar información en una sola celda de memoria para cualquier objeto en particular, incluso si diferentes subprocesos pueden acceder a ella en diferentes momentos de causa y efecto (por otro lado, en un sistema distribuido, la lógica un objeto puede grabarse inmediatamente en muchas réplicas separadas).
El “orden de modificación” corresponde a la misma etapa cuando se concreta la arbitrariedad, es objetivo y solo permite grabaciones. Nuevamente, esta especialización se basa en el hecho de que, con una especificación de memoria débil, las garantías categóricas se otorgan solo a nivel de un objeto.
A continuación, analicemos los axiomas de consistencia formulados por Burkhardt et al. Y veamos cómo se aplican a un modelo de memoria débil. Tenga en cuenta: incluso a pesar de la palabra "axiomas", estas son simplemente propiedades que pueden proporcionarse o no en varios modelos de memoria. El artículo de Burkhardt se centra en las propiedades que determinan la causalidad entre objetos.
Coherencia en última instancia
Para cualquier evento en particular, no puede haber un número indefinido de eventos que no lo vean. Es decir, cualquier evento
es en última instancia visible para el sistema.
Construir lógicamente tales condiciones en un sistema con un modelo de memoria débil debería ser algo más difícil: debe argumentarse que para cualquier
registro en particular no puede haber un número infinito de operaciones de lectura que no leerían este registro o registros anteriores (en el orden de modificación).
En la especificación C ++ 11, no se garantiza el cumplimiento de este axioma, aunque en la práctica es difícil encontrar un contraejemplo.
Consistencia Etérea
Al rastrear la "condicionalidad potencial" a nivel de flujos / operaciones del cliente y con respecto a la visibilidad / legibilidad, debe comprender que no hay tiempo de retorno. Es por eso que se requiere que los cierres al ordenar los flujos que implican lectura sean acíclicos. Como regla, no hay duda de que esta propiedad se observará en sistemas distribuidos, sin embargo, es esta propiedad la que no permite la visibilidad del usuario en algunas versiones especulativas si el sistema tiene un modelo de memoria débil.
Burkhardt et al. Señalan que este axioma "no está confirmado" en la especificación C ++ 11, y no está claro "no valida" si se pueden
observar "ciclos satisfactorios"
en la práctica .
Axiomas de condicionalidad
Para especificar con qué se relaciona exactamente el fenómeno de la condicionalidad bajo un modelo de memoria débil, debemos determinar con precisión qué eventos pueden influir en los resultados de qué otros eventos. Para comenzar, considere nuestros axiomas estándar de causa y efecto:
garantías de sesión . Estas son cuatro cualidades interrelacionadas que reflejan las propiedades de coherencia de las operaciones de lectura y escritura que ocurren en diferentes flujos, además, deben especificarse al nivel de cada objeto (ver
Burkhardt et al .
Fig. 23 ).
- RYW (Lea sus registros): la operación de lectura después de la operación de escritura se realiza en la misma celda, dentro de la misma secuencia / réplica / sesión, debe leer datos no menos relevantes que el registro. La variante de esta propiedad para sistemas distribuidos se especifica exclusivamente en términos de visibilidad, mientras que la variante para un modelo de memoria débil debe basarse tanto en el orden de lectura como en el orden de cambio.
- MR (lecturas monolíticas): las lecturas posteriores (dentro de la misma secuencia, en la misma celda) también deberían ver datos no menos relevantes en el futuro.
- WFR (primera lectura, luego escritura): si la escritura sigue a la lectura dentro de la secuencia, en la misma celda, entonces, en el orden de los cambios, debe ir más tarde que la operación de lectura.
- MW (registros monolíticos): los registros posteriores (dentro de la secuencia, en la misma celda) deben ir más tarde en el orden de modificación.
Las versiones originales de WFR y MW existen en dos versiones, para aleatoriedad y visibilidad; pero esto es importante solo cuando se trabaja con celdas de datos más complejas que con registros para enteros.
Estas propiedades reflejan las nociones de condicionalidad, consistentes con nuestro sentido común; sin embargo, extrañan lo más interesante. En particular, al analizar en un modelo de memoria débil, tales fenómenos de condicionalidad están limitados por los límites del flujo / réplica / sesión y la celda / objeto específico donde se realiza la entrada:
en un artículo de Burkhardt et al . en este caso se dice sobre "visibilidad condicional por objeto por condicional" y "arbitrariedad arbitraria por objeto por condicional", véase también la fig. 23. Estos fenómenos no limitan completamente el comportamiento del sistema cuando diferentes flujos escriben información en diferentes celdas.
Luego, los axiomas del condicionamiento de objetos cruzados describen el efecto de las relaciones causa-efecto a nivel de varios objetos / celdas de memoria.
- COCV (Visibilidad condicional de objetos cruzados): el mismo caso que RYW, pero sin la condición de que la lectura final debe realizarse en el mismo hilo / réplica / sesión. Las lecturas de un objeto que son objetivamente posteriores a los registros en este objeto deben tomar datos no menos relevantes que los ingresados durante la grabación.
La especificación C ++ 11 refleja estas propiedades. Tenga en cuenta que están definidos de tal manera que las restricciones en la visibilidad de grabación y la arbitrariedad del orden de modificación no afectan demasiado estas definiciones.
Pero esto no se aplica a la última propiedad.
- COCA (arbitrario condicional de objetos cruzados): similar a los registros monolíticos, pero se aplica a diferentes flujos, similar a COCV: es RYW para diferentes flujos. Sin embargo, dado que el orden de modificación solo afecta a los registros en un objeto, la formulación de un modelo de memoria débil permite que el sistema tenga una distribución inconsistente de los eventos de grabación en diferentes objetos, y los registros pueden no corresponder ni a las lecturas ni al orden dentro de la secuencia.
Específicamente, COCA en un modelo de memoria débil es una propiedad mucho más débil. Es por eso que con un modelo de memoria débil, el siguiente código puede devolver
{x ≡ 0, y ≡ 0} .
Thread A: y := 0; x := 1; return x
Thread B: x := 0; y := 1; return yEl orden dentro de cada flujo puede ser inconsistente con el orden objeto por orden y el orden de modificación. Tenga en cuenta: con RYW no hay
x := 0 → x := 1 en el orden de modificación y para
y es lo mismo; por lo tanto, el orden de modificación debe contener
x := 1 → x := 0 e
y := 1 → y := 0 . Por lo tanto, el orden de modificación obviamente forma un ciclo en el orden de los flujos.
Tal bucle está permitido en COCA con un modelo de memoria débil. No es que el orden de las secuencias / lecturas sea contrario al orden de modificación, sino que cada secuencia ve un historial de registros consistente. Estas historias son consistentes con las historias de otros flujos solo si limitamos objetivamente el alcance de su aplicación.
¿Qué significa todo esto?
El tiempo está fragmentado.
Aunque nos parece que el tiempo fluye de manera ordenada, estudiar sistemas distribuidos y un modelo de memoria débil muestra claramente que esto no es así. Es por eso que en ambas situaciones, nuestra sobre-aproximación estándar, según la cual el tiempo es total, limita el rendimiento, lo que no podemos permitirnos.
Luego, reconociendo que el tiempo está realmente fragmentado, encontramos muchas diferencias pequeñas pero importantes entre las variedades de tal parcialidad. Incluso los dos campos mencionados anteriormente, que parecen tan similares a primera vista, en muchos matices sutiles permiten distinguir qué tipos particulares de eventos se consideran mutuamente afectados.
Es necesario comprender con más detalle los detalles técnicos de varias propiedades ya después de que alguien pueda expresar las propiedades de un campo en el lenguaje de otro.
El tiempo está fragmentado. Quizás solo necesitemos acostumbrarnos.