Introducción a la base de datos MyRocks de Facebook

Hola, me llamo Miguel y aquí les traigo este nuevo post.

Cómo Facebook diseñó una base de datos con un rendimiento de escritura 10X y una tasa de compresión 2X en comparación con InnoDB

Las bases de datos están en el corazón de prácticamente todas las aplicaciones de Internet. El rendimiento y las latencias de las bases de datos son normalmente el cuello de botella de muchos servicios de Internet y han atraído la atención de muchos investigadores. A medida que la cantidad de datos crece exponencialmente, es cada vez más importante almacenar los datos de manera eficiente. En este blog, presentaremos la base de datos MyRocks de Facebook y examinaremos cómo mejora el rendimiento de escritura en 10 veces y la tasa de compresión en 2 veces en comparación con InnoDB.

La arquitectura de InnoDB

InnoDB, al igual que otras bases de datos relacionales clásicas, utiliza B-Tree para organizar sus datos. Un árbol B es similar a un árbol de búsqueda binaria con algunas diferencias.

• Cada nodo tiene más de 1 valor

Como se muestra en la figura siguiente, cada nodo puede tener más de 1 valor. Por ejemplo, hay 3 valores en el nodo raíz. Todos los valores dentro del subárbol enraizado en el hijo más a la izquierda del nodo raíz son menores que 100. Todos los valores dentro del subárbol enraizado en el segundo hijo más a la izquierda de la raíz están entre 100 y 155.

• Cada nodo ocupa una cantidad constante de espacio en el disco

InnoDB asigna una cantidad constante de espacio para cada nodo del B-Tree. Suponga que la base de datos usa 28 bytes para cada nodo. El nodo raíz ha utilizado todo el espacio asignado. Suponiendo que tanto el puntero como el valor toman 4 bytes cada uno, necesitamos 28 bytes para almacenar valores y punteros en el nodo raíz. Sin embargo, para el nodo que almacena 128 y 140, se desperdician 8 bytes.

Las ventajas de InnoDB

• Leer es rápido

La operación de lectura es muy rápida con un B-Tree. Para encontrar el valor que nos interesa, podemos utilizar la búsqueda binaria. Suponga que queremos encontrar 145. En la raíz, podemos seguir el segundo puntero más a la izquierda para llegar al nodo que contiene 128 y 140. Desde ese nodo, podemos seguir el borde más a la derecha para encontrar el valor objetivo.

B-Tree en la base de datos es equilibrado, lo que significa que se necesitan O (logₓN) para encontrar los datos. x es el número de valores dentro de cada nodo y N es el número total de valores almacenados en la base de datos. En realidad, cada nodo puede tener 100 o incluso más valores. Suponga que cada entrada en la base de datos contiene 1 KB de datos del usuario. La base de datos tiene 1.000.000.000 de entradas si almacena 1 TB de datos. La altura de B-Tree es 5 si el número medio de valores dentro de cada nodo es 100. Por lo tanto, normalmente no es necesario examinar más de 5 nodos para encontrar los datos y el tiempo de ejecución de la operación de lectura puede considerarse constante.

Los problemas con InnoDB

• Almacenamiento desperdiciado

Dado que la base de datos asigna una cantidad constante de almacenamiento a cada nodo, los espacios se desperdician si el nodo no tiene suficientes valores. ¡Una de las razones por las que la base de datos utiliza memoria constante es en realidad para ahorrar almacenamiento! Con memoria constante, podemos encontrar fácilmente la ubicación del nodo con la siguiente fórmula,

location = address_of_first_node + node_number * constant_memory_size

Si mantenemos un mapa desde el número de nodo hasta su dirección física, usaremos más almacenamiento del que se desperdicia debido a la fragmentación del B-Tree.

Del experimento en [1], la fragmentación en InnoDB desperdicia entre un 25% y un 30% del espacio.

• Escribir es lento

Suponga que la base de datos asigna 32 KB para cada nodo. Si cambiamos el contenido de una entrada dentro de un nodo, tenemos que volver a escribir todo el nodo. Cambiar 1 KB de datos en realidad causaría 32 KB de escritura en el disco.

Cómo lo resolvió MyRocks DB

MyRocks DB utilizó un formato diferente para almacenar los datos, como se muestra a continuación.

Los datos se almacenan en un búfer en memoria llamado Mem-Table. (Los datos también se escriben en un registro de escritura anticipada; de lo contrario, se perderán datos si la máquina falla antes de que los datos dentro de Mem-Table se descarguen en el disco). Mem-Table podría usar un árbol de búsqueda binario equilibrado clásico para mantener sus datos.

Cuando el tamaño de Mem-Table alcanza un cierto umbral, esos datos se vacían en un archivo de datos de tabla de cadenas ordenadas (SST). Cada una de las SST almacena los datos en orden. La siguiente figura es un ejemplo de SSTable, con un entero como clave y una cadena como valor.

Las SSTables son inmutables. A medida que pasa el tiempo, tendremos múltiples SSTables, cada una con una lista ordenada de datos. Combinaremos esos archivos SSTable en un archivo SSTable más grande, que podemos nivelar el archivo SSTable 2. Cuando tengamos algunos archivos de nivel 2, los fusionaremos con el archivo de nivel 3 y así sucesivamente.

• La escritura se vuelve más rápida

Las escrituras son sustancialmente más rápidas. Cuando queremos modificar 1 KB de datos, solo necesitamos vaciar 1 KB de datos en el disco. (Bueno, esto no es exactamente cierto, hay otra copia de 1 KB en el WAL). Incluso podríamos emplear la confirmación de grupo del sistema de archivos subyacente para reducir el número de E / S.

• Se reduce el uso de espacio

Como puede verse en la figura, no hay fragmentación espacial.

• Leer se vuelve más lento

No hay almuerzo gratis. La lectura se vuelve más lenta. Dado que los datos pueden estar dentro de la SSTable en cualquier nivel. ¡Necesitamos hacer una búsqueda binaria en todos los archivos SSTable en todos los niveles! Si tenemos 4 niveles, la lectura podría ser 4 veces más lenta. Aunque podemos paralelizar las operaciones de lectura, introduciría mucho más tráfico de lectura en el disco y limitaría el rendimiento de la base de datos.

Evaluación del desempeño

Facebook lanzó MyRocks DB a su base de datos de usuarios, que contiene los datos de todos los usuarios de Facebook. El uso de espacio se redujo de 2187 GB a 824 GB. La cantidad de datos escritos se redujo de 13 MB / s a 3,4 MB / s. Los segundos de CPU indican la eficiencia del sistema y MyRocks DB también supera a InnDB.

Facebook tiene MyRocks DB de código abierto, puedes encontrarlo si estás interesado.

Referencia

[1] MyRocks: motor de almacenamiento de base de datos LSM-Tree que sirve al gráfico social de Facebook, Matsunobu y col., VLDB ’20