Disruptor: una nueva estructura de datos

Algunos de ustedes tal vez conozcan el esquema productor-consumidor; es un escenario simple de concurrencia: un hilo o proceso está creando datos para procesar, los cuales tienen que ser procesados por otro hilo o proceso.

El productor puede estar generando estos datos porque está leyéndolos de un socket, o de algún sensor conectado a la computadora (temperatura, teclado, ratón, etc), o vienen de base de datos, etc. La cosa es que se dedica exclusivamente a producir estos datos, no puede procesarlos porque entonces puede perderse de algunos de los datos que vienen de la fuente, por estar procesando lo que tiene. Por eso hay un consumidor de estos datos, que debe procesarlos en un hilo aparte.

La comunicación entre productor y consumidor por lo general se resuelve utilizando una cola: una estructura de datos tipo FIFO en donde el productor va colocando los datos que produce y el consumidor va tomando datos para procesarlos.

A partir de Java 5, tenemos a nuestra disposición algunas implementaciones de este tipo de colas: una de la LinkedBlockingQueue y otra es la ArrayBlockingQueue (hay otras pero son para casos de uso más específicos; estas son las de uso más general). Esto nos evita tener que implementarlas. Alguna vez necesité una cola de este tipo en un sistema en Java 1.4 y se me hizo fácil implementar una(bueno ni tan fácil pero no había mucha opción). Funcionó bien, pero cuando llegó Java 5 e hice una comparación de performance, simplemente tuve que desechar la que yo hice y utilizar las de Java porque su velocidad era bastante mejor.

A veces se necesitan tener varios consumidores, y hay procesos que son consumidores de otros productores pero a la vez son productores para otros consumidores. Esto es debido a que se divide el procesamiento de datos en varios pasos y pues la solución más sencilla de implementar es serializar los procesos, uniéndolos con varias colas:

//En un hilo tenemos a un productor
Datos a = //obtener estos datos de una fuente externa
proceso1.encolaDatos(a, cola1);
//En otro hilo tenemos a este consumidor
Datos b = proceso2.tomaDatos(cola1);
proceso2.procesar(b);
proceso2.encolaDatos(b, cola2);
//En un tercer hilo tenemos a este otro procesador
Datos c = proceso3.tomaDatos(cola2);
proceso3.procesar(c);
proceso3.encolaDatos(c, cola3);
//La cadena puede seguir...

Esto permite que cada parte del proceso se realice de la manera más rápida posible. Sin embargo, un sistema implementado de esa forma llega rápidamente a un punto en donde la mayor parte del tiempo no está en el procesamiento de los datos, sino en la transferencia de los mismos de un proceso a otro (los datos están más tiempo en las colas que en los procesos). La razón es que las operaciones de poner datos en una cola y tomarlos de la misma son bastante caras en términos de CPU, por la sincronización que requieren, ya que estas colas están diseñadas para permitir que varios hilos puedan agregar elementos y también que varios hilos puedan tomar elementos.

El Disruptor

Recientemente, una compañía inglesa llamada LMAX liberó un software llamado Disruptor, que consiste principalmente en una nueva estructura de datos: un buffer circular, es decir, un anillo en vez de una cola. Este anillo puede ser configurado para utilizarse bajo distintos esquemas: un productor y un consumidor, o un productor y varios consumidores, varios productores y un consumidor, o varios productores y consumidores. Lo curioso es que para el escenario más común, de un productor y uno o varios consumidores, tienen una optimización muy buena, que hace al Disruptor mucho más rápido que las colas de Java, puesto que elimina la sincronización, dado que únicamente hay un hilo poniendo datos en el anillo. Y en vez de que haya otros hilos tomando datos directamente del anillo, lo que se implementa son manejadores de eventos, que son notificados cuando hay datos disponibles para procesar. De hecho el productor no se llama productor (a partir de la versión 2.0 del Disruptor); se llama publicador. De modo que tenemos el escenario más común de un proceso que publica eventos y uno o varios objetos esperando a procesar estos eventos.

Los manejadores de eventos incluso pueden configurarse de distintas maneras; cuando no importa el orden del procesamiento se pueden poner en paralelo, y cuando ya importa el orden, se ponen de manera encadenada. Incluso puede haber un manejador que solamente se invoque después de que un dato ha sido procesado por N cantidad de manejadores previos. Un ejemplo puede ser que haya un logger de los datos que van llegando; no importa si el log se hace antes o después de que se validen los datos, por lo que se puede configurar en paralelo al manejador que valida los datos. Pero el manejador que procesa únicamente datos válidos debe ser llamado después de que los datos hayan sido validados y registrados.

Además de todo esto, el esquema de un solo consumidor tiene algunas optimizaciones adicionales, relacionadas directamente con el manejo de memoria en arquitecturas multi-core, las cuales se detallan mejor en este blog.

Hace tiempo ya había leído de este proyecto y decidí hacer una prueba para comparar las colas de Java con el disruptor, pero tenía varios problemas y además era para la versión 1.0. Pero ahora ya corregí estos problemas que tenía mi prueba, además de que la actualicé para usar el Disruptor 2.0, y la verdad es que es notablemente más rápido su desempeño, y no sólo eso: es más constante (seguramente debido a esas optimizaciones en el uso de los caches de CPU).

La prueba

La prueba es muy simple, consiste simplemente en que un objeto inserte elementos en una cola (o en el Disruptor) y que otro objeto tome dichos objetos. Cada elemento tiene un número distinto (una secuencia que va incrementándose) y el productor va sumando los números de los elementos que lee. Hay un elemento especial que indica el fin de la prueba.

Este proceso se hace con varios miles de elementos, y se realiza varias veces con cada implementación, para sacar un promedio de tiempos. En mi computadora, los resultados del disruptor siempre quedan alrededor 10 a 13 milisegundos, mientras que las colas tardan de 20 a 300 milisegundos, lo cual me parece una variación gigantesca. Esto significa que la velocidad del Disruptor no sólo es mucho mayor que la de las colas de Java, sino que es mucho más estable, lo cual puede resultar en desempeño más predecible.

El código de la prueba que hice lo pueden ver en GitHub.

Me parece una opción bastante interesante para ciertos tipos de aplicaciones, ciertos tipos de servicios, despacho asíncrono de peticiones, etc. Todavía tengo que comprender mejor su funcionamiento para poder realmente aprovecharlo bien, pero definitivamente es algo a considerar para futuros desarrollos, sobre todo si consideramos que ya hoy en día se utiliza en sistemas que procesan hasta 6 millones de peticiones por segundo (cosa que se logra en parte por el disruptor y en parte por una arquitectura bastante peculiar, pero eso es otra historia).

Comentarios

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.
Imagen de CesarAlducin

Que tal @ezamudio Bastante

Que tal @ezamudio

Bastante interesante este articulo, yo solo conocía el clásico ejemplo del productor-consumidor y hasta ahí nadamas.

ahora nos damos cuenta como este tipo de proyectos nos pueden ayudar a mejorar procesos en nuestras aplicaciones.

Que bueno que te tomes el tiempo en evaluar estos proyectos y nos comentes tus conclusiones, créeme que los que nos tomamos el tiempo
en leer tus publicaciones lo valoramos y aprendemos mucho.

Saludos.

Imagen de Algus Dark

Sigo diciendolo, desde que

Sigo diciendolo, desde que entré a JavaMéxico he aprendido mucho. Los artículos de Ezamudio son entretenidos por que ése nivel no lo encuentro en mi ciudad, aquí reina la apatía.

@Ezamudio, tengo una duda. ¿Cuanto tiempo tienes estudiando programación?

Saludos!!!

Imagen de ezamudio

estudiando...

Pues si consideramos que nunca realmente he dejado de estudiar programación, porque siempre hay que aprender nuevos lenguajes, nuevas plataformas, paradigmas, herramientas, frameworks, bibliotecas, patrones de diseño, prácticas, estilos, etc etc... 20 años de manera profesional, pero empecé por gusto 9 años antes, así que ya voy para 30 años programando.

Imagen de Algus Dark

Uno nunca deja de estudiar,

Uno nunca deja de estudiar, siempre hay cosas nuevas que debemos entender, nuevos retos y , cómo no, nuevas quebraduras de cabeza.
Es bueno encontrar gente que le gusta seguir aprendiendo por diversión. Yo llevo 1 año programando profesionalmente y 7 años programando por diversión. Pero siento que fue en hace unos 5 (4 sin contar éste año profesional) años que me sumergí en serio a la programación.