¿Cómo funciona el patrón disruptor de LMAX?
Estoy tratando de entender el patrón disruptor . Vi el video de InfoQ e intenté leer su artículo. Entiendo que hay un búfer en anillo involucrado, que se inicializa como una matriz extremadamente grande para aprovechar la localidad del caché y eliminar la asignación de nueva memoria.
Parece que hay uno o más números enteros atómicos que realizan un seguimiento de las posiciones. Cada 'evento' parece tener una identificación única y su posición en el anillo se encuentra encontrando su módulo con respecto al tamaño del anillo, etc., etc.
Desafortunadamente, no tengo una idea intuitiva de cómo funciona. He realizado muchas aplicaciones comerciales y estudié el modelo de actor , miré SEDA, etc.
En su presentación mencionaron que este patrón es básicamente como funcionan los routers; sin embargo, tampoco he encontrado buenas descripciones de cómo funcionan los enrutadores.
¿Hay algunos buenos consejos para una mejor explicación?
El proyecto Google Code hace referencia a un documento técnico sobre la implementación del búfer circular, sin embargo, es un poco aburrido, académico y difícil para alguien que quiera aprender cómo funciona. Sin embargo, hay algunas publicaciones de blog que han comenzado a explicar los aspectos internos de una manera más legible. Hay una explicación del búfer circular que es el núcleo del patrón disruptor, una descripción de las barreras del consumidor (la parte relacionada con la lectura del disruptor) y cierta información sobre el manejo de múltiples productores disponibles.
La descripción más simple del Disruptor es: Es una forma de enviar mensajes entre hilos de la manera más eficiente posible. Puede usarse como alternativa a una cola, pero también comparte una serie de características con SEDA y Actors.
Comparado con colas:
El Disruptor brinda la capacidad de pasar un mensaje a otros subprocesos y activarlo si es necesario (similar a BlockingQueue). Sin embargo, existen 3 diferencias distintas.
- El usuario del Disruptor define cómo se almacenan los mensajes extendiendo la clase Entry y proporcionando una fábrica para realizar la preasignación. Esto permite la reutilización de la memoria (copia) o la Entrada podría contener una referencia a otro objeto.
- Colocar mensajes en el Disruptor es un proceso de 2 fases: primero se reclama una ranura en el búfer de anillo, que proporciona al usuario la entrada que se puede completar con los datos apropiados. Luego se debe confirmar la entrada; este enfoque de dos fases es necesario para permitir el uso flexible de la memoria mencionado anteriormente. Es la confirmación la que hace que el mensaje sea visible para los hilos de los consumidores.
- Es responsabilidad del consumidor realizar un seguimiento de los mensajes que se han consumido desde el búfer circular. Alejar esta responsabilidad del búfer circular ayudó a reducir la cantidad de contención de escritura, ya que cada subproceso mantiene su propio contador.
Comparado con los actores
El modelo Actor está más cerca del Disruptor que la mayoría de los otros modelos de programación, especialmente si usa las clases BatchConsumer/BatchHandler que se proporcionan. Estas clases ocultan todas las complejidades de mantener los números de secuencia consumidos y proporcionan un conjunto de devoluciones de llamadas simples cuando ocurren eventos importantes. Sin embargo, hay un par de diferencias sutiles.
- El Disruptor usa un modelo de 1 subproceso - 1 consumidor, donde los Actores usan un modelo N:M, es decir, puede tener tantos actores como desee y se distribuirán en un número fijo de subprocesos (generalmente 1 por núcleo).
- La interfaz BatchHandler proporciona una devolución de llamada adicional (y muy importante)
onEndOfBatch(). Esto permite que los consumidores lentos, por ejemplo aquellos que realizan E/S, agrupen eventos para mejorar el rendimiento. Es posible realizar procesamiento por lotes en otros marcos de Actor; sin embargo, como casi todos los demás marcos no proporcionan una devolución de llamada al final del lote, es necesario utilizar un tiempo de espera para determinar el final del lote, lo que genera una latencia deficiente.
Comparado con SEDA
LMAX creó el patrón Disruptor para reemplazar un enfoque basado en SEDA.
- La principal mejora que proporcionó con respecto a SEDA fue la capacidad de trabajar en paralelo. Para hacer esto, Disruptor admite la transmisión múltiple de los mismos mensajes (en el mismo orden) a múltiples consumidores. Esto evita la necesidad de bifurcar etapas en la tubería.
- También permitimos que los consumidores esperen los resultados de otros consumidores sin tener que interponer otra etapa de cola entre ellos. Un consumidor puede simplemente observar el número de secuencia de un consumidor del que depende. Esto evita la necesidad de unir etapas en el proceso.
Comparado con las barreras de la memoria
Otra forma de verlo es como una barrera de memoria estructurada y ordenada. Donde la barrera del productor forma la barrera de escritura y la barrera del consumidor es la barrera de lectura.
Primero nos gustaría entender el modelo de programación que ofrece.
Hay uno o más escritores. Hay uno o más lectores. Hay una línea de entradas, totalmente ordenadas de antigua a nueva (en la foto de izquierda a derecha). Los escritores pueden agregar nuevas entradas en el extremo derecho. Cada lector lee las entradas secuencialmente de izquierda a derecha. Obviamente, los lectores no pueden leer a escritores anteriores.
No existe el concepto de eliminación de entradas. Utilizo "lector" en lugar de "consumidor" para evitar que se consuma la imagen de las entradas. Sin embargo entendemos que las entradas a la izquierda del último lector se vuelven inútiles.
Generalmente los lectores pueden leer de forma simultánea e independiente. Sin embargo, podemos declarar dependencias entre lectores. Las dependencias del lector pueden ser un gráfico acíclico arbitrario. Si el lector B depende del lector A, el lector B no puede leer más allá del lector A.
La dependencia del lector surge porque el lector A puede anotar una entrada y el lector B depende de esa anotación. Por ejemplo, A hace algunos cálculos en una entrada y almacena el resultado en el campo ade la entrada. Luego A continúa y ahora B puede leer la entrada y aalmacenar el valor de A. Si el lector C no depende de A, C no debería intentar leer a.
De hecho, este es un modelo de programación interesante. Independientemente del rendimiento, el modelo por sí solo puede beneficiar a muchas aplicaciones.
Por supuesto, el principal objetivo de LMAX es el rendimiento. Utiliza un anillo de entradas preasignado. El anillo es lo suficientemente grande, pero está delimitado para que el sistema no se cargue más allá de la capacidad de diseño. Si el anillo está lleno, los escritores esperarán hasta que los lectores más lentos avancen y hagan espacio.
Los objetos de entrada están preasignados y viven para siempre, para reducir el costo de recolección de basura. No insertamos nuevos objetos de entrada ni eliminamos objetos de entrada antiguos; en cambio, un escritor solicita una entrada preexistente, completa sus campos y notifica a los lectores. Esta aparente acción de 2 fases es en realidad simplemente una acción atómica.
setNewEntry(EntryPopulator);
interface EntryPopulator{ void populate(Entry existingEntry); }
La preasignación de entradas también significa que las entradas adyacentes (muy probablemente) se ubican en celdas de memoria adyacentes y, debido a que los lectores leen las entradas secuencialmente, esto es importante para utilizar los cachés de la CPU.
Y muchos esfuerzos para evitar bloqueos, CAS e incluso barreras de memoria (por ejemplo, use una variable de secuencia no volátil si solo hay un escritor)
Para desarrolladores de lectores: diferentes lectores anotadores deben escribir en diferentes campos para evitar conflictos de escritura. (En realidad, deberían escribir en diferentes líneas de caché). Un lector anotador no debe tocar nada que otros lectores no dependientes puedan leer. Por eso digo que estos lectores anotan entradas, en lugar de modificarlas .
Martin Fowler ha escrito un artículo sobre LMAX y el patrón disruptor, The LMAX Architecture , que puede aclararlo aún más.
De hecho, me tomé el tiempo de estudiar la fuente real, por pura curiosidad, y la idea detrás de esto es bastante simple. La versión más reciente al momento de escribir esta publicación es 3.2.1.
Hay un búfer que almacena eventos preasignados que contendrán los datos para que los consumidores los lean.
El búfer está respaldado por una matriz de indicadores (matriz de números enteros) de su longitud que describe la disponibilidad de las ranuras del búfer (consulte más detalles). Se accede a la matriz como java#AtomicIntegerArray, por lo que, a los efectos de esta explicación, también puede suponer que es uno.
Puede haber cualquier número de productores. Cuando el productor quiere escribir en el búfer, se genera un número largo (como al llamar a AtomicLong#getAndIncrement, el Disruptor en realidad usa su propia implementación, pero funciona de la misma manera). Llamemos a esto generado durante mucho tiempo productorCallId. De manera similar, se genera un consumerCallId cuando un consumidor TERMINA leyendo una ranura de un búfer. Se accede al consumerCallId más reciente.
(Si hay muchos consumidores, se elige la llamada con la identificación más baja).
Luego se comparan estos identificadores y, si la diferencia entre los dos es menor que en el lado del búfer, el productor puede escribir.
(Si el productorCallId es mayor que el reciente consumerCallId + bufferSize, significa que el búfer está lleno y el productor se ve obligado a esperar en el autobús hasta que haya un lugar disponible).
Luego, al productor se le asigna la ranura en el búfer según su callId (que es prducerCallId módulo bufferSize, pero dado que bufferSize es siempre una potencia de 2 (límite aplicado en la creación del búfer), la operación real utilizada es productorCallId & (bufferSize - 1 )). Entonces es libre de modificar el evento en ese espacio.
(El algoritmo real es un poco más complicado e implica almacenar en caché el ID de consumidor reciente en una referencia atómica separada, con fines de optimización).
Cuando se modificó el evento, el cambio se "publica". Al publicar, el espacio respectivo en la matriz de banderas se llena con la bandera actualizada. El valor del indicador es el número del bucle (producerCallId dividido por bufferSize (nuevamente, dado que bufferSize es una potencia de 2, la operación real es un desplazamiento a la derecha).
De manera similar, puede haber cualquier número de consumidores. Cada vez que un consumidor quiere acceder al búfer, se genera un consumerCallId (dependiendo de cómo se agregaron los consumidores al disruptor, el átomo utilizado en la generación de identificación puede compartirse o separarse para cada uno de ellos). Luego, este consumerCallId se compara con el productortCallId más reciente y, si es menor de los dos, se permite al lector continuar.
(De manera similar, si el productorCallId es par al consumidorCallId, significa que el búfer está vacío y el consumidor se ve obligado a esperar. La forma de esperar está definida por WaitStrategy durante la creación del disruptor).
Para los consumidores individuales (los que tienen su propio generador de identificación), lo siguiente que se verifica es la capacidad de consumir por lotes. Las ranuras en el búfer se examinan en orden desde la correspondiente al consumerCallId (el índice se determina de la misma manera que para los productores) hasta la correspondiente al productorCallId reciente.
Se examinan en un bucle comparando el valor del indicador escrito en la matriz de indicadores con un valor del indicador generado para consumerCallId. Si las banderas coinciden, significa que los productores que ocupan los espacios han confirmado sus cambios. De lo contrario, el bucle se rompe y se devuelve el ID de cambio confirmado más alto. Las ranuras de ConsumerCallId que se reciben en changeId se pueden consumir en lotes.
Si un grupo de consumidores lee juntos (los que tienen un generador de identificación compartido), cada uno solo toma un único callId, y solo se verifica y devuelve la ranura para ese único callId.
