Fragmentación (Sharding)

La fragmentación es una técnica de escalado horizontal para Bases de Datos en la que el contenido se divide en varias instancias llamadas "fragmentos" (shards). Cada fragmento almacena una parte del conjunto de datos, y las solicitudes se redirigen al fragmento correspondiente según criterios predefinidos, como el valor de una clave.

---

Hashing Consistente

El hashing consistente es una técnica clave para minimizar el impacto de cambios en el número de fragmentos (por ejemplo, al añadir o eliminar nodos) sin necesidad de redistribuir la mayoría de los datos.

En un sistema estándar de hashing, los datos se asignan a fragmentos mediante:

Fragmento = h(k) mod m

donde h(k) es la función hash de la clave k y m es el número de fragmentos. Sin embargo, cambiar m provoca la redistribución de todas las claves, lo que es costoso.

En hashing consistente: 1. Las claves y nodos se colocan en un anillo virtual. 2. Cada clave k se asigna al primer nodo que aparece en el anillo en sentido horario a partir de h(k). 3. Cuando se añade o elimina un nodo, solo las claves cercanas a ese nodo son redistribuidas.

Diagrama de Anillo Virtual

graph TB

subgraph Anillo Virtual

A["Nodo 1 (Shard A)"] --> B["Nodo 2 (Shard B)"]

B --> C["Nodo 3 (Shard C)"]

C --> D["Nodo 4 (Shard D)"]

D --> A

end



Key1["Clave: h(k1)"] --> A

Key2["Clave: h(k2)"] --> C

Key3["Clave: h(k3)"] --> B

Ventaja Matemática

Si n es el número de nodos y d es el número de claves, el hashing consistente redistribuye solo una proporción d/n de las claves cuando se modifica el número de nodos, comparado con la redistribución total en el hashing tradicional.

Ley de Zipf y Distribución de Carga

El problema de hotspots ocurre cuando ciertos fragmentos reciben una cantidad desproporcionada de tráfico. Este comportamiento a menudo sigue la Ley de Zipf, que describe cómo las frecuencias de acceso a los datos decrecen exponencialmente:

P(i) ∝ 1 / i^s

donde: - P(i) es la probabilidad de acceder al i-ésimo fragmento. - s > 0 es el parámetro que controla la inclinación de la distribución (más alto significa más concentración en pocos nodos).

Solución Propuesta

Para mitigar este problema: - Hashing ponderado dinámico: Ajustar el peso de cada fragmento en el anillo virtual para distribuir mejor el tráfico. - Cachés distribuidas: Colocar datos más solicitados en múltiples nodos para balancear la carga.

Por ejemplo, si un nodo recibe un 20% más de tráfico, podemos dividir su espacio en el anillo virtual para redistribuir el exceso.

---

Consistencia Eventual

En sistemas como Cassandra, los datos entre nodos no se sincronizan inmediatamente. En su lugar, alcanzan un estado consistente con el tiempo mediante un modelo de consistencia eventual.

Modelo Matemático

La probabilidad de que todos los nodos alcancen un estado consistente después de t unidades de tiempo puede modelarse como:

P(t) = 1 - exp(-λ * t)

donde: - λ es la tasa de sincronización (cómo de rápido se propagan las actualizaciones). - t es el tiempo desde que se hizo la actualización.

Ejemplo:

Si λ = 0.5 y t = 4, la probabilidad de consistencia es:

P(4) = 1 - exp(-0.5 * 4) ≈ 0.864

Esto implica que, después de 4 unidades de tiempo, hay un 86.4% de probabilidad de que los nodos estén sincronizados.

Estas adiciones destacan cómo la fragmentación combina conceptos matemáticos y prácticos para abordar problemas fundamentales de escalabilidad, consistencia y distribución de carga.