Fragmentación: reverso

2.1 ¿Cómo fragmentar y ralentizar N veces?

Puede fragmentar y reducir la velocidad exactamente N veces así:

• Envía solicitudes docs00...docs15 secuencialmente , no en paralelo.
• En consultas simples, haga una selección no por clave , WHERE algo=234.

En este caso, la parte serializada (serie) no toma el 1% ni el 5%, sino alrededor del 20% en las bases de datos modernas. También puede obtener el 50 % de la parte serializada si accede a la base de datos mediante un protocolo binario extremadamente eficiente o si la vincula como una biblioteca dinámica a una secuencia de comandos de Python.

El resto del tiempo de procesamiento de una solicitud simple estará ocupado por operaciones no paralelizables de análisis de la solicitud, preparación del plan, etc. Es decir, no leer el registro se ralentiza.

Si dividimos los datos en 16 tablas y los ejecutamos secuencialmente, como es habitual en el lenguaje de programación PHP, por ejemplo (no es muy bueno para lanzar procesos asíncronos), obtendremos una ralentización de 16 veces. Y, quizás, aún más, porque también se añadirán los viajes de ida y vuelta de red.

De repente, la elección del lenguaje de programación es importante cuando se fragmenta.

Recuerde la elección del lenguaje de programación, porque si envía consultas a la base de datos (o al servidor de búsqueda) secuencialmente, ¿de dónde viene la aceleración? Más bien, habrá una desaceleración.

2.2 Sobre semiautomático

En algunos lugares, la sofisticación de la tecnología de la información inspira horror ctónico. Por ejemplo, MySQL listo para usar no tenía la implementación de fragmentación en ciertas versiones, sin embargo, los tamaños de las bases de datos utilizadas en la batalla crecen a valores indecentes.

La humanidad que sufre frente a DBA individuales ha sido atormentada durante años y escribe varias soluciones de fragmentación malas basadas en nada. Después de eso, se escribe una solución de fragmentación más o menos decente llamada ProxySQL (MariaDB/Spider, PG/pg_shard/Citus, ...). Este es un ejemplo bien conocido de esta misma mancha.

ProxySQL en su conjunto es, por supuesto, una solución completa de clase empresarial para código abierto, enrutamiento y más. Pero una de las tareas a resolver es la fragmentación de una base de datos, que por sí sola no puede fragmentarse de forma humana. Verá, no hay un interruptor "shards = 16", tiene que volver a escribir cada solicitud en la aplicación, y hay muchas en algunos lugares, o poner una capa intermedia entre la aplicación y la base de datos que se ve: "Hmm ... SELECCIONAR * DE documentos? Sí, debe dividirse en 16 pequeños SELECT * FROM server1.document1, SELECT * FROM server2.document2 - a este servidor con tal nombre de usuario/contraseña, a este con otro. Si uno no respondió, entonces...", etc. Exactamente esto se puede hacer con manchas intermedias. Son un poco menos que para todas las bases de datos. Para PostgreSQL, según tengo entendido,

La configuración de cada parche específico es un tema gigante separado que no cabe en un informe, por lo que solo discutiremos los conceptos básicos. Mejor hablemos un poco de la teoría del buzz.

2.3 ¿Automatización perfecta absoluta?

Toda la teoría de drogarse en el caso de fragmentación en esta letra F() , el principio básico es siempre el mismo aproximadamente: shard_id = F(objeto).

Fragmentación: ¿de qué se trata? Tenemos 2 mil millones de registros (o 64). Queremos partirlos en varios pedazos. Surge una pregunta inesperada: ¿cómo? ¿Según qué principio debo distribuir mis 2 mil millones de registros (o 64) en 16 servidores disponibles para mí?

El matemático latente en nosotros debería sugerir que al final siempre hay alguna función mágica que, para cada documento (objeto, línea, etc.), determinará en qué pieza colocarlo.

Profundizando en las matemáticas, esta función siempre depende no solo del objeto en sí (la fila en sí), sino también de la configuración externa, como la cantidad total de fragmentos. Una función que para cada objeto debe decir dónde ponerlo, no puede devolver un valor más que servidores hay en el sistema. Y las funciones son ligeramente diferentes:

shard_func = F1(object); 
shard_id = F2(shard_func, ...); 
shard_id = F2(F1(object), current_num_shards, ...). 

Pero además, no profundizaremos en estos salvajes de funciones individuales, solo hablaremos sobre qué son las funciones mágicas F ().

2.4 ¿Qué son F()?

Pueden idear muchos y muy diferentes mecanismos de implementación. Ejemplo de resumen:

• F = rand() % nums_shards
• F = somehash(objeto.id) % num_shards
• F = objeto.fecha % num_shards
• F = objeto.id_usuario % num_shards
• ...
• F = shard_table [ somehash() |… objeto.fecha |… ]

Un hecho interesante: naturalmente, puede dispersar todos los datos al azar: lanzamos el siguiente registro en un servidor arbitrario, en un núcleo arbitrario, en una tabla arbitraria. No habrá mucha felicidad en esto, pero funcionará.

Hay métodos un poco más inteligentes para fragmentar por una función hash reproducible o incluso consistente, o fragmentar por algún atributo. Repasemos cada método.

F = al azar()

Dispersarse no es un método muy correcto. Un problema: repartimos nuestros 2 mil millones de registros en mil servidores al azar y no sabemos dónde está el registro. Necesitamos sacar user_1, pero no sabemos dónde está. Vamos a mil servidores y revisamos todo; de alguna manera, esto es ineficiente.

F = algo de hash()

Dispersemos a los usuarios de una manera adulta: calcule la función hash reproducible a partir de user_id, tome el resto de la división por la cantidad de servidores e inmediatamente comuníquese con el servidor deseado.

¿Por qué estamos haciendo esto? Y luego, que tenemos una carga alta y nada más cabe en un servidor. Si encajara, la vida sería tan simple.

Genial, la situación ya ha mejorado, para obtener un registro, vamos a un servidor conocido por adelantado. Pero si tenemos un rango de claves, entonces en todo este rango debemos pasar por todos los valores de las claves y, en el límite, ir a tantos fragmentos como claves tengamos en el rango, o incluso a cada servidor. La situación ha mejorado, por supuesto, pero no para todas las solicitudes. Algunas consultas se han visto afectadas.

Fragmentación natural (F = object.date % num_shards)

A veces, es decir, a menudo, el 95 % del tráfico y el 95 % de la carga son solicitudes que tienen algún tipo de fragmentación natural. Por ejemplo, el 95 % de las consultas analíticas sociales condicionales afectan los datos solo del último día, 3 días, 7 días, y el 5 % restante se refiere a los últimos años. Pero el 95% de las solicitudes se fragmentan naturalmente por fecha, el interés de los usuarios del sistema se centra en los últimos días.

En este caso, puede dividir los datos por fecha, por ejemplo, por un día, y seguir la respuesta a la solicitud de un informe para algún día o un objeto desde este día hasta este fragmento y listo.

La vida está mejorando: ahora no solo conocemos la ubicación de un objeto en particular, sino que también conocemos el alcance. Si no se nos pide un rango de fechas, sino un rango de otras columnas, entonces, por supuesto, tendremos que revisar todos los fragmentos. Pero según las reglas del juego, solo tenemos el 5% de este tipo de solicitudes.

Parece que hemos dado con una solución ideal para todo, pero hay dos problemas:

• Esta solución se adapta a un caso específico, cuando el 95% de las solicitudes involucran solo la última semana.
• Dado que el 95% de las solicitudes tocan la última semana, todas caerán en un fragmento que sirve esta última semana. Este fragmento se derretirá, mientras que todos los demás estarán inactivos durante este tiempo. Al mismo tiempo, no puede tirarlos, los datos de archivo también deben almacenarse.

No quiere decir que este sea un mal esquema de fragmentación: cortamos los datos calientes, sin embargo, se debe hacer algo con el fragmento más caliente.

El problema se soluciona con payasadas, saltos y cataplasmas, es decir, un aumento en el número de réplicas para el día en llamas en curso, luego una disminución gradual en el número de réplicas cuando este día se convierte en pasado y pasa al archivo. No existe una solución ideal llamada "solo necesita distribuir los datos en el clúster con una función hash mágica de manera incorrecta".

2.5 Precio a pagar

Formalmente, sabemos que ahora sabemos "todo". Es cierto que no conocemos un dolor de cabeza gigante y dos dolores de cabeza más pequeños.

1. Dolor simple: mal manchado

Este es un ejemplo de un libro de texto, que casi nunca ocurre en la batalla, sino de repente.

• Como ejemplo con fecha, ¡solo que sin fecha!
• Distribución desigual no intencional (perceptible).

Eligieron el mecanismo de fragmentación y/o los datos cambiaron y, por supuesto, el PM no transmitió los requisitos (no tenemos errores en el código, el PM siempre no informa los requisitos), y la distribución se volvió monstruosamente desigual. Es decir, no cumplieron el criterio.

Para atrapar, debes mirar el tamaño de los fragmentos. Definitivamente veremos el problema en el momento en que uno de nuestros fragmentos se sobrecaliente o se vuelva 100 veces más grande que los demás. Puede solucionarlo simplemente reemplazando la clave o la función de fragmentación.

Este es un problema simple, para ser honesto, no creo que al menos una persona de cada cien se encuentre con esto en la vida, pero de repente ayudará al menos a alguien.

2. Dolor "invencible": agregación, unión

¿Cómo hacer selecciones que unen mil millones de registros de una tabla para mil millones de registros de otra tabla?

• ¿Cómo calcular "rápidamente"... DÓNDE randcol ENTRE aaa Y bbb?
• ¿Cómo hacer "inteligentemente"... users_32shards UNIRSE a posts_1024 fragmentos?

Respuesta corta: de ninguna manera, ¡sufrir!

Si distribuyó mil millones de registros a mil servidores en la primera tabla para que trabajaran más rápido e hizo lo mismo en la segunda tabla, entonces, naturalmente, de mil a mil servidores deberían comunicarse entre sí en pares. Un millón de conexiones no funcionarán bien. Si hacemos solicitudes a la base de datos (búsqueda, almacenamiento, almacenamiento de documentos o sistema de archivos distribuidos) que no encajan bien con la fragmentación, estas solicitudes se ralentizarán enormemente.

Un punto importante es que algunas solicitudes siempre se borrarán sin éxito y se ralentizarán . Es importante tratar de minimizar su porcentaje. Como consecuencia, no hay necesidad de hacer uniones gigantescas con mil millones por mil millones de registros. Si es posible replicar una tabla pequeña, en relación con la cual se está uniendo en una tabla compartida gigante, a todos los nodos, debe hacerlo. Si las uniones son realmente locales de alguna manera, por ejemplo, es posible colocar al usuario y sus publicaciones uno al lado del otro, fragmentarlos de la misma manera y hacer todas las uniones dentro de la misma máquina; debe hacer precisamente eso. .

Este es un curso separado de conferencias durante tres días, así que pasemos al último dolor infernal y los diferentes algoritmos para lidiar con él.

2.6. Dolor complejo/largo: Resharding

Prepárese: si fragmentó sus datos por primera vez en su vida, en promedio los fragmentará cinco veces más.

No importa cuántos clústeres configure, aún necesita volver a fragmentar.

Si eres muy inteligente y afortunado, entonces salta al menos una vez. Pero una vez que esté seguro, porque en el momento en que cree que 10 unidades son suficientes para el usuario, alguien en ese momento escribe una solicitud de 30 y planea tener una solicitud de 100 unidades de recursos desconocidos. Los fragmentos nunca son suficientes. Con el primer esquema de fragmentación, en cualquier caso, se perderá; siempre tendrá que aumentar la cantidad de servidores para agregar o hacer otra cosa; en general, de alguna manera volver a empaquetar los datos.

Es bueno si tenemos buenas potencias de dos: había 16 fragmentos de servidor, ahora son 32. Es más divertido si eran 17, son 23, dos números primos mínimos. ¿Cómo lo hacen las bases de datos, tal vez tienen algún tipo de magia dentro?

La respuesta correcta es: no, no hay magia adentro, tienen un infierno adentro.

A continuación, consideraremos lo que se puede hacer "a mano", quizás entendamos "como una máquina automática".

En la frente #1. Reubicar todo

Para todos los objetos, consideramos NewF(object), cambiamos a un nuevo fragmento.

La posibilidad de que NewF()=OldF() coincida es baja.

Vamos a cubrir casi todo.

Oh.

Espero que no exista el infierno de transferir los 2 mil millones de registros de fragmentos antiguos a otros nuevos. El enfoque ingenuo es comprensible: había 17 máquinas, se agregaron 6 máquinas al clúster, se ordenaron 2 mil millones de registros, se cambiaron de 17 máquinas a 23 máquinas. Una vez cada 10 años, probablemente incluso puedas hacerlo. Pero en general es una mala jugada.

En la frente #2. Reubicar la mitad

La próxima mejora ingenua, abandonemos un esquema tan estúpido, prohibirá que 17 autos se vuelvan a dividir en 23, ¡y siempre volveremos a dividir 16 autos en 32 autos! Entonces, según la teoría, tendremos que desplazar exactamente la mitad de los datos, y en la práctica también podemos hacerlo.

Para todos los objetos, consideramos NewF(object), cambiamos a un nuevo fragmento.

Era estrictamente 2^N, ahora es estrictamente 2^(N+1) fragmentos.

La probabilidad de hacer coincidir NewF()=OldF() es 0,5.

Transfiramos alrededor del 50% de los datos.

Óptimo, pero solo funciona para potencias de dos.

En principio, todo está bien, salvo la unión a la potencia de dos en cuanto al número de coches. Este enfoque ingenuo, por extraño que parezca, puede funcionar.

Tenga en cuenta que la división adicional del clúster por potencias de dos en este caso también es óptima. En cualquier caso, al agregar 16 máquinas a un grupo de 16, estamos obligados a cambiar la mitad de los datos, exactamente la mitad y el cambio.

Está bien, pero la humanidad realmente no ha inventado nada más: la pregunta surge de una mente inquisitiva.

Más divertido #3. Hash consistente

Por supuesto, aquí se requiere una imagen con un círculo sobre hashing consistente.

Si busca en Google "hashing consistente", entonces definitivamente aparecerá un círculo, todos los resultados se completan con círculos.

Idea: dibujemos identificadores de fragmentos (hashes) en un círculo y marquemos los identificadores de servidor hash en la parte superior. Cuando necesite agregar un servidor, colocamos un nuevo punto en el círculo, y lo que resultó estar cerca de él (y solo lo que resultó estar cerca de él), lo reubicamos.

Al agregar un fragmento: no miramos todo, sino solo 2 "vecinos", cambiamos en promedio 1/n.

Al eliminar un fragmento: solo miramos el fragmento que se está eliminando, solo lo cambiamos. Tipo de óptimo.

Muy efectivo en términos de minimizar el tráfico al agregar un fragmento, y absolutamente repugnante en términos de equilibrio de datos normal. Porque cuando hacemos hash de todos estos objetos que distribuimos a una gran cantidad de máquinas, lo hacemos de manera relativamente desigual: los puntos alrededor del círculo están espaciados de manera desigual, y la carga de cada nodo en particular puede ser muy diferente del resto.

Este problema se resuelve con la última línea del nodo virtual. Cada nodo, cada servidor en el círculo se indica con más de un punto. Al agregar un servidor, un fragmento, etc., estamos agregando algunos puntos. Cada vez que eliminamos algo, eliminamos algunos puntos y cambiamos una pequeña parte de los datos.

Estoy hablando de este espacio con círculos porque, por ejemplo, ese esquema está dentro de Cassandra. Es decir, cuando ella comenzó a perseguir registros entre nodos, sepa que el círculo lo está mirando y probablemente no lo apruebe.

Sin embargo, en comparación con los primeros métodos, la vida ha mejorado: al agregar / eliminar un fragmento, ya no revisamos todos los registros, sino solo una parte, y cambiamos solo una parte.

Atención, la pregunta es: ¿se puede mejorar más? ¿Y también mejorar la uniformidad de la carga de fragmentos? ¡Dicen que es posible!

Más divertido #4. Cita/HRW

La siguiente idea simple (el material es educativo, así que nada complicado): shard_id = arg max hash(object_id, shard_id).

No sé por qué se llama hash de Rendezvous, pero sí sé por qué se llama Peso aleatorio más alto. Es muy fácil visualizarlo así:

Tenemos, por ejemplo, 16 fragmentos. Para cada objeto (cadena) que debe colocarse en algún lugar, calculamos 16 hashes según el objeto del número de fragmento. Gana quien tenga el valor hash más alto.

Este es el llamado HRW-hashing, también conocido como Rendezvous hashing. Tonto como un palo, el esquema para calcular el número de un fragmento, en primer lugar, es más fácil para la vista que los círculos y proporciona una carga uniforme, por otro lado.

Lo único negativo es que añadir un nuevo fragmento nos ha empeorado. Existe el riesgo de que al agregar un nuevo shard todavía tengamos algunos hashes que cambiarán y puede ser necesario revisar todo. La tecnología de eliminación de fragmentos no ha cambiado mucho.

Otro problema es que es computacionalmente pesado con una gran cantidad de fragmentos.

Más divertido #5. Más técnicas

Curiosamente, la investigación no se detiene y Google publica cada año alguna nueva tecnología espacial:

• Saltar hash - Google '2014.
• Sonda múltiple: Google '2015.
• Maglev-Google '2016.

Si está interesado en el tema, puede leer muchas disertaciones. Presento estos datos para dejar claro que el problema no está resuelto, no existe una súper solución que se pueda implementar en todas las bases de datos. Hasta ahora, la gente defiende tesis.

conclusiones

Hay una técnica básica importante llamada fragmentación que lleva el nombre de Gallius Julius Caesar: “¡Divide y vencerás, gobernarás y dividirás!”. Si los datos no caben en un servidor, es necesario dividirlos en 20 servidores.

Habiendo aprendido todo esto, uno debería tener la impresión de que sería mejor no fragmentar. Si decide que sería mejor no fragmentar, este es el sentimiento correcto. Si puede agregar memoria al servidor por $ 100 y no fragmentar nada, entonces debería hacerlo. Al fragmentar, aparecerá un sistema distribuido complejo con la transferencia de datos de un lado a otro, apilando datos en nadie sabe dónde. Si se puede evitar, se debe evitar.

Es mejor no hacerlo a mano, es mejor que la "base" (búsqueda, DFS, ...) pueda fragmentarse. En cualquier caso, tarde o temprano, llegará una gran carga y, de alguna manera, habrá que dividir los datos. No es un hecho que incluso si la base puede hacerlo por sí misma, no tendrá ningún problema. Recuerde sobre el fundamentalismo algorítmico: debe comprender cómo funciona todo por dentro.

Cuando configure la fragmentación por primera vez, elija F() con cuidado, piense en las solicitudes, la red, etc. Pero prepárate, probablemente tendrás que elegir 2 veces y al menos una vez tendrás que rehacer todo.