🤲🏼 😻 🃏 Distribución de datos en Apache Ignite 🐷 ⏱️ 🏇🏽

¡Hola! Esta publicación es una versión ligeramente abreviada de mi conferencia homónima en la reunión de la comunidad Apache Ignite . Puede ver la versión completa del video junto con las preguntas y respuestas aquí , y descargar las diapositivas aquí . En el informe, traté de mostrar con ejemplos cómo se distribuyen los datos en Apache Ignite.

¿Por qué necesitas distribuir algo?

Un historial bastante estándar del desarrollo de cualquier sistema que requiera almacenamiento y procesamiento de datos es el logro de un cierto límite. O hay una gran cantidad de datos y no se colocan físicamente en el dispositivo de almacenamiento, o la carga está creciendo a una velocidad tal que un servidor ya no puede procesar tantas solicitudes. Hay casos frecuentes cuando ambos ocurren.

Como regla, llegan a una de dos soluciones: fragmentar el almacenamiento existente o cambiar a una base de datos distribuida. Ambas soluciones tienen una serie de características comunes, la más obvia de las cuales es el uso de más de un nodo para trabajar con datos. Además, a muchos nodos los llamaré topología.

El problema de la distribución de datos entre los nodos de topología se puede formular como un conjunto de requisitos, que nuestra distribución debe satisfacer:

Se necesita un algoritmo que permita que todos los nodos de la topología y las aplicaciones del cliente lleguen a la misma conclusión sobre en qué nodo o nodos se encuentra el determinado objeto (o clave).
Uniformidad de distribución. Cuanto más uniformemente se distribuyan los datos entre nodos, más uniformemente se distribuirá la carga en estos nodos. Aquí supongo que nuestros nodos tienen aproximadamente los mismos recursos.
. , , . , , , .

Lograr los dos primeros requisitos es bastante fácil.

Un enfoque familiar, que se usa a menudo al equilibrar la carga entre servidores funcionalmente equivalentes, dividiendo el módulo N, donde N es el número de nodos en la topología y tenemos una correspondencia uno a uno entre el número de nodo y su identificador. Entonces, todo lo que tenemos que hacer es representar la clave del objeto como un valor numérico utilizando una función hash y tomar el resto de la división entre N del valor obtenido.

imagen

El diagrama muestra la distribución de 16 claves en 3 nodos. Se puede ver que esta distribución es uniforme, y el algoritmo para obtener el nodo para el objeto es simple y garantiza que si todos los nodos de la topología usan este algoritmo, se obtendrá el mismo resultado para la misma clave y el mismo N.

Pero, ¿qué sucede si introducimos el cuarto nodo en la topología?

imagen

Nuestra función ha cambiado, ahora tomamos el resto de la división por 4, no por 3. Y si la función ha cambiado, entonces la distribución ha cambiado, y mucho.

Aquí, la ubicación anterior de los objetos para la versión anterior de la topología de tres nodos se muestra en rojo, y la posición de los objetos para la nueva versión de la topología de cuatro nodos es verde, respectivamente. Esto es muy similar a los archivos diff habituales, pero en lugar de archivos tenemos nodos.

Es fácil ver que los datos se han movido no solo al nuevo nodo, sino que también hubo un intercambio de datos entre los nodos que ya estaban en la topología. Aquellos. observamos tráfico espurio entre nodos y no se cumple el requisito de un cambio mínimo en la distribución.

Dos formas populares de resolver el problema de la distribución de datos, teniendo en cuenta los requisitos enumerados, son las siguientes:

Hash constante
El algoritmo de peso aleatorio más grande (HRW), también conocido como hash de Rendezvous.

Ambos algoritmos son muy simples. Sus descripciones en Wikipedia encajan en varias oraciones. Aunque es difícil llamarlos obvios. Para aquellos interesados, recomiendo leer los artículos originales Hashing consistente y árboles aleatorios: protocolos de almacenamiento en caché distribuidos para aliviar puntos calientes en la World Wide Web y un esquema de mapas basado en nombres para Rendezvous . Lo más comprensible, en mi opinión, la idea de un algoritmo de hash consistente se transmite en este curso de Stanford .

Veamos estos algoritmos con más detalle.

Hashing consistente

El truco que subyace al algoritmo de hash consistente es asignar ambos nodos y objetos almacenados al mismo espacio identificador. Esto hace que nuestras entidades, objetos y nodos aparentemente diferentes sean comparables.

Para obtener dicho mapeo, simplemente aplicamos la misma función hash a las teclas de los objetos y a los identificadores de los nodos. El resultado de la función hash para el nodo se llamará un token, esto nos será útil más adelante.

Representamos nuestro espacio identificador en forma de círculo, es decir. simplemente asumimos que el valor identificador máximo sigue inmediatamente al valor identificador mínimo.

Ahora, para determinar en qué nodo vive el objeto, debe obtener el valor de la función hash de su clave, y luego simplemente moverse en el sentido de las agujas del reloj alrededor del círculo hasta que encontremos la ficha de un nodo en el camino. La dirección del movimiento no es importante, pero debe ser fija.

El movimiento imaginario en el sentido de las agujas del reloj es funcionalmente equivalente a una búsqueda binaria en una matriz ordenada de tokens de nodo.

imagen

En el diagrama, cada sector de un color particular refleja el espacio identificador del que es responsable un nodo particular.

Si agregamos un nuevo nodo, entonces ...

imagen

... dividirá uno de los sectores en dos partes y asumirá completamente las teclas correspondientes.

En este ejemplo, el nodo 3 se hizo cargo de parte de las claves del nodo 1.

Como puede ver, este enfoque proporciona una distribución bastante desigual de los objetos entre los nodos, porque depende en gran medida de los identificadores de los propios nodos. ¿Cómo se puede mejorar este enfoque?

Puede asignar más de un token a los nodos (generalmente cientos). Esto se puede lograr, por ejemplo, introduciendo muchas funciones hash para el nodo (una por token) o aplicando repetidamente la misma función hash al token obtenido en el paso anterior. Pero no debemos olvidarnos de las colisiones. No debe haber dos nodos con el mismo token.

imagen

En este ejemplo, cada nodo tiene 4 tokens.

Qué más es importante mencionar: si queremos garantizar la seguridad de los datos en el caso de que un nodo abandone la topología, entonces debemos almacenar las claves en varios nodos (las llamadas réplicas o copias de seguridad). En el caso del algoritmo hash consistente, las réplicas serán los siguientes nodos N-1 en el círculo, donde N es el factor de replicación. Por supuesto, el orden de los nodos debe estar determinado por un token específico (por ejemplo, por el primero), porque cuando se usan múltiples tokens para cada uno de ellos, la disposición de los nodos puede diferir. Preste atención al esquema: no tiene un patrón claro de repetición de nodos.

En cuanto al requisito de un cambio mínimo en la distribución al cambiar la topología, se cumple porque el orden mutuo de los nodos en el círculo no cambia. Aquellos. eliminar un nodo de la topología no cambiará la relación de orden entre los nodos restantes.

Cita hash

El algoritmo de hash de Rendezvous parece incluso más simple que el hashing consistente. El algoritmo se basa en el mismo principio de invariancia de las relaciones de orden. Pero en lugar de hacer comparables nodos y objetos, solo hacemos nodos para un objeto específico comparable. Aquellos. Determinamos la relación de orden entre los nodos para cada objeto de forma independiente.

De nuevo hashing nos ayuda con esto. Pero ahora, para determinar el peso del nodo N para un objeto O dado, mezclamos el identificador del objeto con el identificador del nodo y tomamos el hash de esta mezcla. Una vez realizada esta operación para cada nodo, obtenemos un conjunto de pesos por el cual clasificamos los nodos.

El nodo que resultó ser el primero y será responsable de almacenar el objeto.

Como todos los nodos de la topología usan los mismos datos de entrada, el resultado para ellos será idéntico. Que satisface el primer requisito.

imagen

Considera un ejemplo. Aquí tenemos una relación de orden entre tres nodos para cuatro claves diferentes. El amarillo indica el nodo con el mayor peso, es decir el nodo que finalmente será responsable de una clave particular.

Agregue otro nodo a la topología.

imagen

Lo coloqué deliberadamente en diagonal para tener en cuenta todas las opciones posibles. Aquí, el nodo 3, que se muestra en verde, ingresó a la topología. Por lo tanto, la distribución de peso de los nodos para cada una de las claves ha cambiado. El rojo indica los nodos que han cambiado su ubicación en la lista para una clave en particular, porque Los pesos de estos nodos eran menores que el peso del nodo agregado. Sin embargo, este cambio afectó solo a una de las claves, K3.

Derivemos traicioneramente un nodo de una topología.

imagen

Una vez más, los cambios afectaron solo una clave, esta vez K1. Los objetos restantes no fueron afectados. La razón, como en el caso del hashing consistente, es la invariabilidad de la relación de orden entre cualquier par de nodos. Aquellos. Se cumple el requisito de un cambio mínimo en la distribución y no hay tráfico espurio entre los nodos.

La distribución de la cita se ve bastante bien y no requiere trucos adicionales en comparación con el hashing consistente como tokens.

En caso de que queramos admitir la replicación, el siguiente nodo de la lista será la primera réplica del objeto, el siguiente nodo será la segunda réplica, etc.

Cómo se usa el hash de encuentro en Apache Ignite

La llamada función de afinidad es responsable de la distribución de datos en Apache Ignite (consulte la interfaz AffinityFunction ). La implementación predeterminada es el hash de encuentro (consulte la clase RendezvousAffinityFunction ).

Lo primero a lo que debe prestar atención es que Apache Ignite no asigna objetos almacenados directamente a los nodos de topología. En cambio, se introduce un concepto adicional: partición.

Una partición es un contenedor para objetos y una unidad de replicación. Además, el número de particiones para un caché particular (este es un análogo de la tabla en las bases de datos familiares) se establece en la etapa de configuración y no cambia durante el ciclo de vida del caché.

Por lo tanto, podemos mostrar objetos en particiones usando una división de módulo efectiva, y usar hashing de encuentro para mostrar particiones en nodos.

imagen

Porque el número de particiones para la memoria caché es constante, luego podemos calcular la distribución de la partición por nodos una vez y almacenar en caché el resultado hasta que se cambie la topología.

Cada nodo calcula esta distribución de forma independiente, pero en todos los nodos con los mismos datos de entrada, esta distribución será idéntica.

La partición puede tener varias copias, las llamamos copias de seguridad. La partición primaria se llama partición primaria.

Para la mejor distribución de claves entre particiones y particiones por nodos, se debe cumplir la siguiente regla: el número de particiones debe ser significativamente mayor que el número de nodos, a su vez, el número de claves debe ser significativamente mayor que el número de particiones.

Las cachés en Ignite se particionan y replican.

En una memoria caché particionada, el número de copias de seguridad se establece en la etapa de creación de la memoria caché. Las particiones (primarias y copias de seguridad) se distribuyen uniformemente entre los nodos. Tal caché es más adecuada para trabajar con datos operativos, como proporciona el mejor rendimiento de escritura, que depende directamente de la cantidad de copias de seguridad. En general, cuantas más copias de seguridad, más nodos deben confirmar el registro clave.

imagen

En este ejemplo, el caché tiene una copia de seguridad. Aquellos. podemos perder un nodo y no perder datos, porque Las copias de seguridad de la partición nunca se almacenan en el mismo nodo que la partición primaria o su otra copia de seguridad.

En la memoria caché replicada, el número de copias de seguridad siempre es igual al número de nodos de topología menos 1. Es decir, cada nodo siempre contiene copias de todas las particiones.

imagen

Tal caché es más adecuada para trabajar con datos que rara vez cambian (por ejemplo, directorios) y proporciona la mayor disponibilidad, como podemos perder nodos N-1 (en este caso 3) sin perder datos. También en esta opción, obtendremos el máximo rendimiento de lectura si permitimos leer datos de las particiones primarias y las copias de seguridad.

Colocación de datos en Apache Ignite

Un concepto importante a tener en cuenta para obtener el mejor rendimiento es la colocación. Colocación es la colocación de cualquier objeto en el mismo lugar. En nuestro caso, los objetos son entidades almacenadas en la memoria caché, y un lugar es un nodo.

Si los objetos se distribuyen entre particiones de la misma función de afinidad, es lógico que los objetos con la misma clave de afinidad caigan en la misma partición y, por lo tanto, en el mismo nodo. En Ignite, esto se llama colocación de afinidad.

Por defecto, una clave de afinidad es la clave principal de un objeto. Pero en Ignite, puede usar cualquier otro campo de un objeto como clave de afinidad.

La colocación reduce significativamente la cantidad de datos enviados entre nodos para realizar cálculos o consultas SQL, lo que naturalmente lleva a una reducción en el tiempo dedicado a estas tareas. Considere este concepto con el ejemplo.

Deje que nuestro modelo de datos consista en dos entidades: orden (orden) y posición de orden (artículo de orden). Un pedido puede corresponder a muchos artículos. Los identificadores de pedido y línea de pedido son independientes, pero la línea de pedido tiene una clave externa que se refiere al pedido correspondiente.

Supongamos que necesitamos realizar alguna tarea, que para cada orden debe realizar cálculos para las posiciones de este orden.

Por defecto, una clave de afinidad es una clave primaria. Por lo tanto, los pedidos y las posiciones se distribuirán entre los nodos de acuerdo con sus claves principales, que, según recuerdo, son independientes.

imagen

En el diagrama, las órdenes están representadas por cuadrados y posiciones en círculos. El color indica que el artículo pertenece al pedido.

Con esta distribución de datos, nuestra tarea hipotética se enviará al nodo donde se encuentra el orden deseado, y luego tendrá que leer las posiciones de todos los demás nodos, o enviar una subtarea a estos nodos y obtener el resultado del cálculo. Esta es una interacción de red innecesaria que puede y debe evitarse.

¿Qué sucede si le decimos a Ignite que los artículos de pedido deben colocarse en los mismos nodos que los mismos pedidos, es decir? ¿recolectar datos?

Como clave de afinidad para la posición, tomamos la clave externa OrderId y este campo se utilizará al calcular la partición a la que pertenece el registro. Además, dentro de la partición, siempre podemos encontrar nuestro objeto por la clave primaria.

imagen

Ahora, si ambas memorias caché (Order y OrderItem) usan la misma función de afinidad con los mismos parámetros, nuestros datos estarán cerca y no necesitaremos recorrer la red para buscar artículos.

Configuración de afinidad en Apache Ignite

En la implementación actual, un objeto de función de afinidad es un parámetro de configuración de caché.

La función de afinidad en sí toma los siguientes argumentos al crear:

Número de particiones;
El número de copias de seguridad (de hecho, este también es el parámetro de configuración de la memoria caché);
Filtro de respaldo;
La bandera excluye a los vecinos.

Estas configuraciones no se pueden cambiar.

Con la cantidad de particiones y copias de seguridad, todo parece estar claro. Hablaré sobre el filtro de respaldo y la bandera excludeNeighbours un poco más tarde.

En tiempo de ejecución, la función de afinidad de entrada recibe la topología de clúster actual, esencialmente una lista de nodos de clúster, y calcula la distribución de particiones por nodos de acuerdo con los ejemplos que mostré cuando hablé sobre el algoritmo de hash de encuentro.

En cuanto al filtro de respaldo, este es un predicado que le permite prohibir que las funciones de afinidad asignen particiones de respaldo a un nodo para el cual el predicado devolvió falso.

Como ejemplo, supongamos que nuestros nodos físicos (servidores) están ubicados en el centro de datos en diferentes bastidores. Por lo general, cada bastidor tiene su propio poder independiente ...

imagen

... y si perdemos el rack, perdemos los datos.

imagen

En este ejemplo, perdimos la mitad de las particiones.

Pero si configuramos el filtro de copia de seguridad correcto, la distribución cambiará de tal manera ...

imagen

... que si se pierde el bastidor, no habrá pérdida de datos y aún estarán disponibles.

imagen

El indicador excludeNeighbours realiza una función similar y, de hecho, es una abreviatura para un caso específico.

A menudo, varios nodos Ignite se ejecutan en el mismo host físico. Este caso es muy similar al ejemplo con bastidores en el centro de datos, solo que ahora estamos luchando contra la pérdida de datos con la pérdida del host, no los bastidores.

imagen

El resto es igual. Puede implementar este comportamiento utilizando un filtro de respaldo. Esta bandera es un legado histórico y puede eliminarse en la próxima versión principal de Ignite.

Parece que hablé sobre la función de afinidad y la distribución de datos, todo lo que un desarrollador que usa Apache Ignite necesita saber.

En conclusión, veamos un ejemplo de la distribución de 16 particiones de acuerdo con la topología de 3 nodos. Por simplicidad y claridad, creemos que las particiones no tienen copias de seguridad.

Acabo de tomar y escribí una pequeña prueba que me trajo la distribución real:

imagen

Como puede ver, la uniformidad de la distribución no es ideal. Pero el error será notablemente menor con un aumento en el número de nodos y particiones. La regla principal que debe observarse es que el número de particiones es significativamente mayor que el número de nodos. Ahora, en Ignite, el número predeterminado de particiones para un caché particionado es 1024.

Ahora agregue un nuevo nodo a la topología.

imagen

Parte de las partes se mudaron a él. Al mismo tiempo, se observó el requisito de un cambio mínimo en la distribución: el nuevo nodo recibió parte de las particiones, mientras que los otros nodos no intercambiaron particiones.

Eliminamos de la topología el nodo que estaba presente en él en la etapa inicial:

imagen

ahora todas las particiones que estaban asociadas con el nodo cero se redistribuyeron a otros nodos de la topología, sin violar nuestros requisitos de distribución.

Como puede ver, la solución a problemas complejos a menudo se basa en ideas bastante triviales, aunque no del todo obvias. Las soluciones descritas se utilizan en la mayoría de las bases de datos distribuidas y hacen un buen trabajo. Pero estas decisiones son aleatorias y, por lo tanto, la uniformidad de distribución dista mucho de ser ideal. ¿Se puede mejorar la uniformidad sin sacrificar el rendimiento y otros requisitos de distribución? La pregunta permanece abierta.