introducción
"Tienes que correr lo más rápido que puedas para mantenerte en el lugar,
¡Y para llegar a algún lugar, tienes que correr al menos el doble de rápido!
(c) Alicia en el país de las maravillas
Hace algún tiempo me pidieron que diera una conferencia. analistas nuestra empresa en el tema del diseño de modelos de datos, porque sentados en proyectos durante mucho tiempo (a veces durante varios años) perdemos de vista lo que sucede a nuestro alrededor en el mundo de las tecnologías de la información. En nuestra empresa (da la casualidad de que) muchos proyectos no utilizan bases de datos NoSQL (al menos por ahora), por lo que en mi conferencia les presté atención por separado usando el ejemplo de HBase y traté de orientar la presentación del material hacia esos Quienes nunca los han usado han funcionado. En particular, ilustré algunas de las características del diseño de modelos de datos usando un ejemplo que leí hace varios años. . Al analizar ejemplos, comparé varias opciones para resolver el mismo problema para transmitir mejor las ideas principales a la audiencia.
Recientemente, "sin nada que hacer", me hice la pregunta (el largo fin de semana de mayo en cuarentena es especialmente propicio para esto): ¿en qué medida los cálculos teóricos corresponderán a la práctica? De hecho, así nació la idea de este artículo. Es posible que un desarrollador que haya estado trabajando con NoSQL durante varios días no aprenda nada nuevo (y, por lo tanto, se salte inmediatamente la mitad del artículo). Pero para analistasPara aquellos que aún no han trabajado estrechamente con NoSQL, creo que será útil para obtener una comprensión básica de las características del diseño de modelos de datos para HBase.
Análisis de ejemplo
En mi opinión, antes de empezar a utilizar bases de datos NoSQL, es necesario pensar detenidamente y sopesar los pros y los contras. A menudo, lo más probable es que el problema pueda resolverse utilizando DBMS relacionales tradicionales. Por lo tanto, es mejor no utilizar NoSQL sin motivos importantes. Sin embargo, si decide utilizar una base de datos NoSQL, debe tener en cuenta que los enfoques de diseño aquí son algo diferentes. Especialmente algunos de ellos pueden resultar inusuales para aquellos que anteriormente sólo se han ocupado de DBMS relacionales (según mis observaciones). Entonces, en el mundo “relacional”, generalmente comenzamos modelando el dominio del problema y solo entonces, si es necesario, desnormalizamos el modelo. En NoSQL nosotros debe tener en cuenta inmediatamente los escenarios esperados para trabajar con datos e inicialmente desnormalizar los datos. Además, existen otras diferencias, que se analizarán a continuación.
Consideremos el siguiente problema "sintético", con el que seguiremos trabajando:
Es necesario diseñar una estructura de almacenamiento para la lista de amigos de los usuarios de alguna red social abstracta. Para simplificar, asumiremos que todas nuestras conexiones son dirigidas (como en Instagram, no en Linkedin). La estructura debería permitirle efectivamente:
- Responda la pregunta de si el usuario A lee al usuario B (patrón de lectura)
- Permitir agregar/eliminar conexiones en caso de suscripción/cancelación de suscripción del usuario A del usuario B (plantilla de cambio de datos)
Por supuesto, existen muchas opciones para solucionar el problema. En una base de datos relacional normal, lo más probable es que simplemente hagamos una tabla de relaciones (posiblemente tipificada si, por ejemplo, necesitamos almacenar un grupo de usuarios: familia, trabajo, etc., que incluya a este "amigo"), y optimizar la velocidad de acceso agregaría índices/particiones. Lo más probable es que la mesa final se vea así:
user_id
amigo_id
vasya
Petia
vasya
Оля
En adelante, para mayor claridad y mejor comprensión, indicaré nombres en lugar de DNI.
En el caso de HBase, sabemos que:
- Es posible una búsqueda eficiente que no resulte en un escaneo completo de la tabla. exclusivamente por clave
- de hecho, es por eso que escribir consultas SQL familiares para muchos en este tipo de bases de datos es una mala idea; Técnicamente, por supuesto, puedes enviar una consulta SQL con Joins y otra lógica a HBase desde el mismo Impala, pero ¿qué tan efectivo será?
Por lo tanto, nos vemos obligados a utilizar el ID de usuario como clave. Y mi primer pensamiento sobre el tema "¿dónde y cómo almacenar las identificaciones de amigos?" tal vez sea una idea almacenarlos en columnas. Esta opción más obvia e "ingenua" se verá así (llamémosla Opción 1 (predeterminada)para mayor referencia):
FilaClave
altavoces
vasya
1: Petia
2: Olia
3: Dasha
Petia
1: Masha
2: Vasya
Aquí, cada línea corresponde a un usuario de la red. Las columnas tienen nombres: 1, 2, ... - según la cantidad de amigos, y los ID de los amigos se almacenan en las columnas. Es importante tener en cuenta que cada fila tendrá un número diferente de columnas. En el ejemplo de la figura anterior, una fila tiene tres columnas (1, 2 y 3), y la segunda tiene solo dos (1 y 2); aquí nosotros mismos usamos dos propiedades de HBase que las bases de datos relacionales no tienen:
- la capacidad de cambiar dinámicamente la composición de las columnas (agregar un amigo -> agregar una columna, eliminar un amigo -> eliminar una columna)
- diferentes filas pueden tener diferentes composiciones de columnas
Comprobemos que nuestra estructura cumple con los requisitos de la tarea:
- Lectura de datos: para saber si Vasya está suscrita a Olya, necesitaremos restar toda la linea por la clave RowKey = "Vasya" y ordenar los valores de las columnas hasta que "nos encontremos" con Olya en ellos. O repita los valores de todas las columnas, "no cumpla" con Olya y devuelva la respuesta Falso;
- Editar datos: agregar un amigo: para una tarea similar también necesitamos restar toda la linea usando la clave RowKey = “Vasya” para calcular el número total de sus amigos. Necesitamos este número total de amigos para determinar el número de la columna en la que debemos escribir el ID del nuevo amigo.
- Cambiar datos: eliminar un amigo:
- necesidad de restar toda la linea por la clave RowKey = “Vasya” y ordenar las columnas para encontrar aquella en la que está registrado el amigo que se va a eliminar;
- Luego, después de eliminar a un amigo, debemos "desplazar" todos los datos a una columna para no tener "espacios en blanco" en su numeración.
Evaluemos ahora qué tan productivos serán estos algoritmos, que necesitaremos implementar en el lado de la "aplicación condicional", utilizando . Denotemos el tamaño de nuestra red social hipotética como n. Entonces, la cantidad máxima de amigos que puede tener un usuario es (n-1). Podemos ignorar aún más este (-1) para nuestros propósitos, ya que dentro del marco del uso de símbolos O no tiene importancia.
- Lectura de datos: es necesario restar la línea completa e iterar por todas sus columnas en el límite. Esto significa que la estimación superior de costos será aproximadamente O(n)
- Editar datos: agregar un amigo: para determinar la cantidad de amigos, debe recorrer todas las columnas de la fila y luego insertar una nueva columna => O(n)
- Cambiar datos: eliminar un amigo:
- Similar a agregar: debe revisar todas las columnas en el límite => O(n)
- Después de eliminar las columnas, debemos "moverlas". Si implementa esto "de frente", entonces, en el límite, necesitará hasta (n-1) operaciones. Pero aquí y más adelante en la parte práctica usaremos un enfoque diferente, que implementará un "pseudo-desplazamiento" para un número fijo de operaciones, es decir, se dedicará un tiempo constante, independientemente de n. Este tiempo constante (O(2) para ser exactos) puede despreciarse en comparación con O(n). El enfoque se ilustra en la siguiente figura: simplemente copiamos los datos de la “última” columna a aquella de la que queremos eliminar datos y luego eliminamos la última columna:
En total, en todos los escenarios recibimos una complejidad computacional asintótica de O (n).
Probablemente ya hayas notado que casi siempre tenemos que leer toda la fila de la base de datos y, en dos de cada tres casos, simplemente revisar todas las columnas y calcular el número total de amigos. Por lo tanto, como intento de optimización, puede agregar una columna de “recuento”, que almacena el número total de amigos de cada usuario de la red. En este caso, no podemos leer toda la fila para calcular el número total de amigos, sino leer solo una columna de "recuento". Lo principal es no olvidarse de actualizar el "recuento" al manipular datos. Eso. nos mejoramos Opción 2 (recuento):
FilaClave
altavoces
vasya
1: Petia
2: Olia
3: Dasha
cuenta: 3
Petia
1: Masha
2: Vasya
cuenta: 2
Comparado con la primera opción:
- Lectura de datos: para obtener una respuesta a la pregunta "¿Vasya lee a Olya?" nada ha cambiado => O(n)
- Editar datos: agregar un amigo: Hemos simplificado la inserción de un nuevo amigo, ya que ahora no necesitamos leer la fila completa e iterar sobre sus columnas, sino que solo podemos obtener el valor de la columna "count", etc. determine inmediatamente el número de columna para insertar un nuevo amigo. Esto conduce a una reducción de la complejidad computacional a O(1)
- Cambiar datos: eliminar un amigo: Al eliminar a un amigo, también podemos usar esta columna para reducir el número de operaciones de E/S al “desplazar” los datos una celda hacia la izquierda. Pero aún persiste la necesidad de recorrer las columnas para encontrar la que debe eliminarse, por lo que => O(n)
- Por otro lado, ahora, al actualizar los datos, necesitamos actualizar la columna "recuento" cada vez, pero esto requiere un tiempo constante, que puede despreciarse en el marco de los símbolos O.
En general, la opción 2 parece un poco más óptima, pero se parece más a “evolución en lugar de revolución”. Para hacer una “revolución” necesitaremos Opción 3 (col).
Pongamos todo “patas arriba”: asignaremos nombre de columna ID de usuario! Lo que se escribirá en la columna en sí ya no es importante para nosotros, que sea el número 1 (en general, allí se pueden guardar cosas útiles, por ejemplo, el grupo “familia/amigos/etc.”). Este enfoque puede sorprender al "profano" no preparado que no tiene experiencia previa trabajando con bases de datos NoSQL, pero es precisamente este enfoque el que le permite utilizar el potencial de HBase en esta tarea de manera mucho más efectiva:
FilaClave
altavoces
vasya
Petia: 1
Olia: 1
Dasha: 1
Petia
masha: 1
Vasya: 1
Aquí obtenemos varias ventajas a la vez. Para entenderlos, analicemos la nueva estructura y estimemos la complejidad computacional:
- Lectura de datos: para responder a la pregunta de si Vasya está suscrito a Olya, basta con leer una columna “Olya”: si está ahí, entonces la respuesta es Verdadero, si no – Falso => O(1)
- Editar datos: agregar un amigo: Agregar un amigo: simplemente agregue una nueva columna "ID de amigo" => O(1)
- Cambiar datos: eliminar un amigo: simplemente elimine la columna ID de amigo => O(1)
Como puedes ver, una ventaja importante de este modelo de almacenamiento es que en todos los escenarios que necesitamos operamos con una sola columna, evitando leer toda la fila de la base de datos y, además, enumerar todas las columnas de esa fila. Podríamos detenernos ahí, pero...
Puede quedar desconcertado y avanzar un poco más en el camino de optimizar el rendimiento y reducir las operaciones de E/S al acceder a la base de datos. ¿Qué pasaría si almacenáramos la información completa de la relación directamente en la clave de fila? Es decir, ¿componer la clave como userID.friendID? En este caso, ni siquiera tenemos que leer las columnas de la línea (Opción 4 (fila)):
FilaClave
altavoces
Vasya.Petya
Petia: 1
Vasya.Olya
Olia: 1
Vasya.Dasha
Dasha: 1
petya.masha
masha: 1
Petya.Vasya
Vasya: 1
Obviamente, la evaluación de todos los escenarios de manipulación de datos en dicha estructura, como en la versión anterior, será O(1). La diferencia con la opción 3 estará únicamente en la eficiencia de las operaciones de E/S en la base de datos.
Bueno, la última "reverencia". Es fácil ver que en la opción 4, la clave de fila tendrá una longitud variable, lo que posiblemente pueda afectar el rendimiento (aquí recordamos que HBase almacena datos como un conjunto de bytes y las filas de las tablas están ordenadas por clave). Además, tenemos un separador que puede ser necesario manejar en algunos escenarios. Para eliminar esta influencia, puedes usar hashes de ID de usuario y ID de amigo, y dado que ambos hashes tendrán una longitud constante, puedes simplemente concatenarlos, sin un separador. Entonces los datos de la tabla se verán así (Opción 5(hash)):
FilaClave
altavoces
dc084ef00e94aef49be885f9b01f51c01918fa783851db0dc1f72f83d33a5994
Petia: 1
dc084ef00e94aef49be885f9b01f51c0f06b7714b5ba522c3cf51328b66fe28a
Olia: 1
dc084ef00e94aef49be885f9b01f51c00d2c2e5d69df6b238754f650d56c896a
Dasha: 1
1918fa783851db0dc1f72f83d33a59949ee3309645bd2c0775899fca14f311e1
masha: 1
1918fa783851db0dc1f72f83d33a5994dc084ef00e94aef49be885f9b01f51c0
Vasya: 1
Obviamente, la complejidad algorítmica de trabajar con dicha estructura en los escenarios que estamos considerando será la misma que la de la opción 4, es decir, O(1).
En total, resumamos todas nuestras estimaciones de complejidad computacional en una tabla:
Agregar un amigo
Revisando a un amigo
Eliminar a un amigo
Opción 1 (predeterminada)
O (n)
O (n)
O (n)
Opción 2 (recuento)
O (1)
O (n)
O (n)
Opción 3 (columna)
O (1)
O (1)
O (1)
Opción 4 (fila)
O (1)
O (1)
O (1)
Opción 5 (hash)
O (1)
O (1)
O (1)
Como puede ver, las opciones 3 a 5 parecen ser las más preferibles y, en teoría, garantizan la ejecución de todos los escenarios de manipulación de datos necesarios en un tiempo constante. En las condiciones de nuestra tarea, no existe un requisito explícito para obtener una lista de todos los amigos del usuario, pero en las actividades reales del proyecto, sería bueno para nosotros, como buenos analistas, "anticipar" que tal tarea podría surgir y "Extiende una pajita". Por tanto, mis simpatías están del lado de la opción 3. Pero es muy probable que en un proyecto real esta petición ya se hubiera podido solucionar por otros medios, por lo que, sin una visión general de todo el problema, es mejor no hacer conclusiones finales.
Preparación del experimento.
Me gustaría poner a prueba los argumentos teóricos anteriores en la práctica; este era el objetivo de la idea que surgió durante el fin de semana largo. Para ello, es necesario evaluar la velocidad de funcionamiento de nuestra “aplicación condicional” en todos los escenarios descritos de uso de la base de datos, así como el aumento de este tiempo al aumentar el tamaño de la red social (n). El parámetro objetivo que nos interesa y que mediremos durante el experimento es el tiempo que dedica la "aplicación condicional" a realizar una "operación comercial". Por “transacción comercial” nos referimos a una de las siguientes:
- Agregar un nuevo amigo
- Comprobar si el usuario A es amigo del usuario B
- Eliminando a un amigo
Así, teniendo en cuenta los requisitos planteados en el enunciado inicial, el escenario de verificación surge de la siguiente manera:
- Grabación de datos. Genere aleatoriamente una red inicial de tamaño n. Para acercarnos al “mundo real”, la cantidad de amigos que tiene cada usuario también es una variable aleatoria. Mida el tiempo durante el cual nuestra "aplicación condicional" escribe todos los datos generados en HBase. Luego divida el tiempo resultante por el número total de amigos agregados; así es como obtenemos el tiempo promedio para una "operación comercial"
- Lectura de datos. Para cada usuario, cree una lista de "personalidades" para las cuales necesita obtener una respuesta, ya sea que el usuario esté suscrito a ellas o no. La longitud de la lista = aproximadamente el número de amigos del usuario, y para la mitad de los amigos marcados la respuesta debe ser "Sí", y para la otra mitad - "No". La verificación se realiza en tal orden que las respuestas “Sí” y “No” se alternan (es decir, en cada segundo caso tendremos que recorrer todas las columnas de la línea para las opciones 1 y 2). Luego, el tiempo total de evaluación se divide por el número de amigos evaluados para obtener el tiempo promedio de evaluación por sujeto.
- Eliminación de datos. Eliminar todos los amigos del usuario. Además, el orden de eliminación es aleatorio (es decir, "mezclamos" la lista original utilizada para registrar los datos). Luego, el tiempo total de verificación se divide por la cantidad de amigos eliminados para obtener el tiempo promedio por verificación.
Los escenarios deben ejecutarse para cada una de las 5 opciones del modelo de datos y para diferentes tamaños de la red social para ver cómo cambia el tiempo a medida que crece. Dentro de n, las conexiones en la red y la lista de usuarios a verificar deben, por supuesto, ser las mismas para las 5 opciones.
Para una mejor comprensión, a continuación se muestra un ejemplo de datos generados para n= 5. El “generador” escrito produce tres diccionarios de identificación como salida:
- el primero es para insertar
- el segundo es para comprobar
- tercero – para su eliminación
{0: [1], 1: [4, 5, 3, 2, 1], 2: [1, 2], 3: [2, 4, 1, 5, 3], 4: [2, 1]} # всего 15 друзей
{0: [1, 10800], 1: [5, 10800, 2, 10801, 4, 10802], 2: [1, 10800], 3: [3, 10800, 1, 10801, 5, 10802], 4: [2, 10800]} # всего 18 проверяемых субъектов
{0: [1], 1: [1, 3, 2, 5, 4], 2: [1, 2], 3: [4, 1, 2, 3, 5], 4: [1, 2]} # всего 15 друзей
Como puede ver, todos los ID superiores a 10 en el diccionario para verificar son precisamente aquellos que seguramente darán la respuesta Falso. La inserción, verificación y eliminación de "amigos" se realizan exactamente en la secuencia especificada en el diccionario.
El experimento se llevó a cabo en una computadora portátil con Windows 10, donde HBase se ejecutaba en un contenedor Docker y Python con Jupyter Notebook se ejecutaba en el otro. A Docker se le asignaron 2 núcleos de CPU y 2 GB de RAM. Toda la lógica, como la emulación de la "aplicación condicional" y la "tubería" para generar datos de prueba y medir el tiempo, se escribió en Python. La biblioteca se utilizó para trabajar con HBase. , para calcular hashes (MD5) para la opción 5 - hashlib
Teniendo en cuenta la potencia de cálculo de una computadora portátil en particular, se seleccionó experimentalmente un lanzamiento para n = 10, 30,…. 170 – cuando el tiempo total de funcionamiento del ciclo de prueba completo (todos los escenarios para todas las opciones para todos n) fue incluso más o menos razonable y adecuado durante una fiesta de té (en promedio 15 minutos).
Aquí es necesario señalar que en este experimento no evaluamos principalmente cifras de rendimiento absolutas. Incluso una comparación relativa de dos opciones diferentes puede no ser del todo correcta. Ahora nos interesa la naturaleza del cambio en el tiempo dependiendo de n, ya que teniendo en cuenta la configuración anterior del "banco de pruebas", es muy difícil obtener estimaciones de tiempo "limpias" de la influencia de factores aleatorios y de otro tipo ( y tal tarea no fue establecida).
resultado del experimento
La primera prueba es cómo cambia el tiempo dedicado a completar la lista de amigos. El resultado está en el gráfico siguiente.
Las opciones 3 a 5, como se esperaba, muestran un tiempo de "transacción comercial" casi constante, que no depende del crecimiento del tamaño de la red y una diferencia indistinguible en el rendimiento.
La opción 2 también muestra un rendimiento constante, pero ligeramente peor, casi exactamente el doble que las opciones 2-3. Y esto no puede dejar de alegrarnos, ya que se correlaciona con la teoría: en esta versión el número de operaciones de E/S hacia/desde HBase es exactamente 5 veces mayor. Esto puede servir como prueba indirecta de que nuestro banco de pruebas, en principio, proporciona una buena precisión.
La opción 1 también, como se esperaba, resulta ser la más lenta y demuestra un aumento lineal en el tiempo dedicado a agregar unos a otros al tamaño de la red.
Veamos ahora los resultados de la segunda prueba.
Las opciones 3 a 5 nuevamente se comportan como se esperaba: tiempo constante, independientemente del tamaño de la red. Las opciones 1 y 2 demuestran un aumento lineal en el tiempo a medida que aumenta el tamaño de la red y un rendimiento similar. Además, la opción 2 resulta un poco más lenta, aparentemente debido a la necesidad de revisar y procesar la columna adicional de "recuento", que se vuelve más notoria a medida que n crece. Pero aún así me abstendré de sacar conclusiones, ya que la precisión de esta comparación es relativamente baja. Además, estas proporciones (qué opción, 1 o 2, es más rápida) cambiaron de una carrera a otra (manteniendo la naturaleza de la dependencia y "yendo codo con codo").
Bueno, el último gráfico es el resultado de las pruebas de eliminación.
Una vez más, no hay sorpresas aquí. Las opciones 3 a 5 realizan la eliminación en tiempo constante.
Además, curiosamente, las opciones 4 y 5, a diferencia de los escenarios anteriores, muestran un rendimiento ligeramente peor que la opción 3. Aparentemente, la operación de eliminación de filas es más costosa que la operación de eliminación de columnas, lo cual en general es lógico.
Las opciones 1 y 2, como se esperaba, demuestran un aumento lineal en el tiempo. Al mismo tiempo, la opción 2 es consistentemente más lenta que la opción 1, debido a la operación de E/S adicional para "mantener" la columna de recuento.
Conclusiones generales del experimento:
- Las opciones 3 a 5 demuestran una mayor eficiencia ya que aprovechan HBase; Además, su rendimiento difiere entre sí de forma constante y no depende del tamaño de la red.
- No se registró la diferencia entre las opciones 4 y 5. Pero esto no significa que no deba utilizarse la opción 5. Es probable que el escenario experimental utilizado, teniendo en cuenta las características de rendimiento del banco de pruebas, no permitiera detectarlo.
- La naturaleza del aumento en el tiempo necesario para realizar “operaciones comerciales” con datos confirmó en general los cálculos teóricos obtenidos previamente para todas las opciones.
El acto final
Los duros experimentos llevados a cabo no deben tomarse como una verdad absoluta. Hay muchos factores que no se tuvieron en cuenta y distorsionaron los resultados (estas fluctuaciones son especialmente visibles en los gráficos con un tamaño de red pequeño). Por ejemplo, la velocidad de ahorro que utiliza happybase, el volumen y el método de implementación de la lógica que escribí en Python (no puedo afirmar que el código se haya escrito de manera óptima y haya utilizado de manera efectiva las capacidades de todos los componentes), tal vez las características del almacenamiento en caché de HBase, la actividad en segundo plano de Windows 10 en mi computadora portátil, etc. En general, podemos suponer que todos los cálculos teóricos han demostrado experimentalmente su validez. Bueno, o al menos no fue posible refutarlos con semejante “ataque frontal”.
En conclusión, recomendaciones para todos los que recién comienzan a diseñar modelos de datos en HBase: abstraerse de la experiencia previa trabajando con bases de datos relacionales y recordar los "mandamientos":
- Al diseñar, partimos de la tarea y los patrones de manipulación de datos, y no del modelo de dominio.
- Acceso eficiente (sin escaneo completo de la tabla): solo mediante clave
- Desnormalización
- Diferentes filas pueden contener diferentes columnas
- Composición dinámica de los ponentes.
Fuente: habr.com