Search for a command to run...
La técnica que utilizan Cassandra y DynamoDB para rebalancear datos en sistemas distribuidos
👋 Hey there! I'm Juanjo, a Backend Software Engineer with a focus on API development. My colleagues know me as someone committed to quality and attention to detail, my friends know me as a funny guy who knows good places to eat food. This blog tries to blend both sides of me.
No comments yet. Be the first to comment.
¿Por qué he leído este libro? Poco antes de terminar 2025, alcancé la cifra de 14 libros leídos, de los cuales 4 eran de desarrollo de software. Casi todos se centraban en arquitectura y diseño de alto nivel, así que buscaba algo más práctico a la ho...
Repaso de las propiedades ACID en bases de datos y qué sistemas las implementan hoy en día.
Este teorema dice que un sistema distribuido solo puedes garantizar simultáneamente dos de estas tres propiedades: Consistency (consistencia) Availability (disponibilidad) Partition tolerance (tolerancia a particiones) ¿Pero qué significan estas...
Hoy vamos a hablar de algo un poco más amplio: los motores de bases de datos. A grandes rasgos, los podemos dividir en dos grandes categorías: OLTP (procesamiento de transacciones online): los que están optimizados para procesar transacciones. OLAP...
Conforme pasa el tiempo, surgen problemas que afrontar en nuestra base de datos:
La cantidad de queries por segundo aumenta, con lo que necesitas añadir más CPUs para poder aguantar la carga.
La cantidad de datos aumenta, con lo que necesitas añadir más almacenamiento en discos o RAM.
Cuando un servidor falla y es necesario que otros servidores asuman sus responsabilidades. Para ello tendremos que mover todos esos datos y peticiones de un nodo a otro nuevo.
➡️ El proceso de mover toda esta carga de un nodo a otro dentro del clúster se conoce como rebalanceo.
No importa el esquema que hayas utilizado partición de la base de datos, hay una serie de requisitos mínimos que se buscan al hacer dicho rebalanceo:
Después del rebalanceo, la carga (datos, peticiones de lectura y escritura) debe de ser distribuida de manera equitativa entre los nodos del clúster.
Mientras ocurre el rebalanceo, la base de datos debe de seguir aceptando peticiones de lectura y escritura.
No deberían de moverse más datos de los necesarios al realizar el balanceo. Así conseguiremos un rebalanceo más rápido y minimizaremos la carga por operaciones de E/S en disco y de red.
Sabiendo que estas son las cualidades que se buscan para rebalancear, vamos ahora a introducir un ejemplo.
Imaginemos que tienes un sistema montado con tu cliente, servidor y base de datos. Pero tu plataforma se ha hecho muy popular y tus servidores pueden escalar horizontalmente tranquilamente, pero tu base de datos ya no da abasto. Tienes que distribuir los datos que había en la base de datos entre diferentes nodos, vamos, lo que se conoce como sharding.
Este sistema se vería tal que así:
Lo que tenía antes en una sola instancia de mi base de datos, ahora lo tengo que repartir en 3 nodos separados. ¿Cómo lo hago? ¿Qué criterio utilizo para saber en qué base de datos tengo que guardar un dato u otro? Es decir:
El método más simple sería calcular el módulo (%) del hash de la key. Por ejemplo, si nuestra función para calcular el hash de una key devuelve un número en base 10, podríamos calcular el módulo N de ese número, siendo N el número de nodos que tenemos en total.
El algoritmo se vería tal que así:
Primero, cogemos el id de la entidad y lo pasamos por la función hash que tenemos, lo cual lo convierte a un número.
Ahora, cogemos ese número y calculamos el módulo (%) según el número de nodos que tengamos en nuestra base de datos.
El resultado nos indica donde guardar dicho dato.
Un ejemplo donde queremos calcular donde van 3 keys y tenemos 3 bases de datos sería:
ID #15→ hash(15)→ 32→ 32 % 3 = 2 → Database 2
ID #99→ hash(99)→ 27→ 27 % 3 = 1 → Database 1
ID #66→ hash(66)→ 69→ 69 % 3 = 0 → Database 0
El problema con esta manera de particionar la base de datos es que si el número de nodos cambia, es decir, si la N cambia, vamos a tener que mover la mayor parte de las keys.
Por ejemplo, digamos que hash(12345)= 6. Si tenemos 3 nodos como en nuestro ejemplo, la key se asignará a la base de datos número 0 (porque 6 mod 3 = 0). Cuando añadas una base de datos más y tengas 4, tendrás que mover dicha key al nodo 2 (6 mod 4 = 2). Pero es que cuando añadas otra instancia más y tengas 5 nodos, tendrás que moverla al nodo 1 (6 mod 5 = 1). Y no es solo esa key, tendrás que mover de un lado a otro las keys de diferentes nodos cada vez que añadas o quites una base de datos.
Esto hace que el rebalanceo sea muy costoso y hace que movamos más datos de los necesarios durante el rebalanceo.
Una solución común es crear más particiones que número de nodos, y asignar varias particiones a cada nodo. Por ejemplo, nuestro clúster de 3 nodos podríamos dividirlo en 300 particiones y así se le asignarían 100 a cada nodo. Esto va a hacer que sea mucho más fácil rebalancear los datos cuando se añadan o eliminen nodos.
Cuando añadas un nodo, dicho nodo va a simplemente robar unas cuantas particiones del cluster. Y cuando quites un nodo, pues lo mismo pero al contrario. Tienes que redistribuir las particiones entre los nodos existentes.
Solo las particiones enteras van a ser movidas entre nodos. El número de particiones no cambia, como tampoco cambia la partición que tiene asignada cada key. Mientras se hace la migración, las operaciones funcionan como en la configuración antigua hasta que se finaliza el cambio.
Aunque existe la posibilidad de dividir o combinar particiones, en la práctica muchas bases de datos eligen tener un número de particiones fijas desde que montas el sistema. Lo complicado es saber el número de particiones que vas a necesitar cuando tu sistema crezca. Pocas y largas particiones van a dificultar el balanceo, muchas particiones cortas van a generar mucho overhead. Lo ideal claro está, es encontrar un punto intermedio intentando predecir cómo va a crecer tu sistema.
Esta estrategia de balanceo es la que utilizan sistemas como Elasticsearch y Couchbase.
La última estrategia que vamos a presentar y en la que nos vamos a centrar se denomina consistent hashing. La clave principal es que vamos a distribuir nuestros datos y las bases de datos que disponemos en un anillo circular.
Vimos anteriormente que con la estrategia módulo N, al quitar o añadir nodos tendríamos que mover la mayoría de keys de sitio. Ahora que utilizamos consistent hashing, esto no va a ser así. Dado que cada servidor va a ser responsable de un arco de la circunferencia, añadir un servidor va a ser tan simple como mover ligeramente cada servidor en el anillo. De esta manera, solo un pequeño subconjunto de keys van serán reasignadas a un servidor diferente del que estaban.
Así, conseguiremos reducir el número de datos que se mueven durante el rebalanceo y, por lo tanto, disminuirán el número de cache misses durante este. Quitar un nodo del anillo será la misma operación que añadir un nodo pero a la inversa.
Esta solución ya es mucho mejor a lo que teníamos con la estrategia de modulo N. Pero hay una manera incluso mejor de repartir los nodos, una forma que al realizar el rebalanceo, consigue una redistribución más uniforme de las keys y generar un menor impacto en nuestro anillo.
Y esa manera es:
Los nodos virtuales (virtual nodes) son una extensión del consistent hashing que hace el sistema más resistente a distribuciones desequilibradas de datos en el anillo. La idea consiste en que cada base de datos va a ser representada por más de un nodo en el anillo. Esto lo podríamos conseguir con cualquiera de las siguientes 2 maneras:
Añadiendo un prefijo a la base de datos al calcular su hash. Así, sin nodos virtuales estábamos calculando hash(DB 1), pero ahora tendríamos que calcular hash(DB 1_0), hash(DB 1_1), hash(DB 1_2), etc.
Calcular la posición de los nodos de cada base de datos aplicando más de una función hash. Es decir, para saber la posición “*_0” utilizaríamos una función hash, para la posición “*_1” utilizaríamos otra función diferente y así.
En el caso de que la base de datos 4 falle:
Las keys en “BD 4_1” serán distribuidas al nodo “2_2” así que irán a la base de datos 2.
Las keys en “BD 4_3” serán distribuidas al nodo “3_2” así que irán a la base de datos 3.
Las keys en “BD 4_2” serán distribuidas al nodo “1_3” así que irán a la base de datos 1.
Las keys en “BD 4_0” serán distribuidas al nodo “1_2” así que irán a la base de datos 1.
Como vemos, esto hace que la carga de una base de datos caída se distribuya de manera más equitativa entre los diferentes nodos físicos. Cuantos más nodos virtuales uses por base de datos, más uniforme será la redistribución de la carga.
Con la llegada de los sistemas distribuidos, el consistent hashing es uno de esos algoritmos que solucionó un problema fundamental de manera elegante: cómo distribuir las carga entre bases de datos para luego minimizar la cantidad de datos que se redistribuyen al cambiar el número de servidores. Y todo esto simplemente poniendo los servidores en un anillo y siguiendo el sentido de las agujas del reloj.
Este algoritmo está integrado a día de hoy en tecnologías que utilizamos como Cassandra, DynamoDB o CDNs. Quizás no tendremos que implementarlo en los sistemas que construyamos en nuestro día a día, pero saber cómo funciona por adentro nos ayuda a tomar mejores decisiones cuando diseñemos sistemas distribuidos donde necesitemos particionar los datos.