Particionamiento de Base de Datos (Sharding)

¿Qué Es el Sharding de Base de Datos?

El sharding de base de datos (también llamado particionamiento horizontal) es la práctica de dividir una base de datos grande en piezas más pequeñas y manejables llamadas shards. Cada shard es una base de datos independiente que contiene un subconjunto de los datos totales. Juntos, los shards componen el conjunto de datos completo.

El sharding es típicamente el último recurso para escalar bases de datos — primero debes optimizar consultas, agregar caché, escalar verticalmente y agregar réplicas de lectura. Pero cuando tus datos crecen más allá de lo que una sola máquina puede manejar, o tu rendimiento de escritura excede lo que un solo primario puede soportar, el sharding se vuelve necesario.

Estrategias de Sharding

1. Sharding Basado en Hash

Aplica una función hash a la clave de partición (ej. ID de usuario) y usa el resultado para determinar qué shard almacena los datos. El enfoque más común es número_de_shard = hash(clave_de_partición) % número_de_shards.

// Hash-based sharding
function getShardIndex(userId: string, totalShards: number): number {
  // Simple hash function
  let hash = 0;
  for (let i = 0; i < userId.length; i++) {
    const char = userId.charCodeAt(i);
    hash = ((hash << 5) - hash) + char;
    hash = hash & hash; // Convert to 32-bit integer
  }
  return Math.abs(hash) % totalShards;
}

// Usage
const shardIndex = getShardIndex('user_12345', 4);
// Routes to shard 0, 1, 2, or 3 based on the hash

class ShardedDatabase {
  private shards: DatabaseConnection[];

  constructor(shardConnections: DatabaseConnection[]) {
    this.shards = shardConnections;
  }

  async getUser(userId: string): Promise<User> {
    const shardIndex = getShardIndex(userId, this.shards.length);
    const shard = this.shards[shardIndex];
    return shard.query('SELECT * FROM users WHERE id = $1', [userId]);
  }

  async createUser(user: User): Promise<void> {
    const shardIndex = getShardIndex(user.id, this.shards.length);
    const shard = this.shards[shardIndex];
    await shard.query('INSERT INTO users (id, name, email) VALUES ($1, $2, $3)',
      [user.id, user.name, user.email]);
  }
}

• Ventajas: Distribución uniforme de datos (si la función hash es buena), simple de implementar, no necesita tabla de búsqueda.
• Desventajas: Agregar o eliminar shards requiere re-hashear todos los datos (a menos que uses hashing consistente). Las consultas entre shards son difíciles. Las consultas por rango en la clave de partición no son posibles.

2. Sharding Basado en Rango

Particiona datos basándose en rangos de la clave de partición. Por ejemplo, usuarios con IDs 1-1,000,000 van al shard 1, IDs 1,000,001-2,000,000 van al shard 2, y así sucesivamente. Otro enfoque común es particionar por rango de fechas — cada mes o año obtiene su propio shard.

// Range-based sharding
interface ShardRange {
  min: number;
  max: number;
  connection: DatabaseConnection;
}

class RangeShardedDatabase {
  private ranges: ShardRange[];

  constructor(ranges: ShardRange[]) {
    // Ranges must be sorted and non-overlapping
    this.ranges = ranges.sort((a, b) => a.min - b.min);
  }

  getShardForKey(key: number): DatabaseConnection {
    for (const range of this.ranges) {
      if (key >= range.min && key <= range.max) {
        return range.connection;
      }
    }
    throw new Error(`No shard found for key: ${key}`);
  }

  // Range queries are efficient because they often hit a single shard
  async getUsersInRange(startId: number, endId: number): Promise<User[]> {
    const relevantShards = this.ranges.filter(
      range => range.max >= startId && range.min <= endId
    );

    const results = await Promise.all(
      relevantShards.map(shard =>
        shard.connection.query(
          'SELECT * FROM users WHERE id BETWEEN $1 AND $2',
          [Math.max(startId, shard.min), Math.min(endId, shard.max)]
        )
      )
    );

    return results.flat();
  }
}

• Ventajas: Las consultas por rango son eficientes (los datos en un rango probablemente están en el mismo shard), fácil de entender, se pueden agregar nuevos shards para nuevos rangos sin re-particionar datos existentes.
• Desventajas: Propenso a hotspots (ej. el shard con los datos más nuevos recibe todas las escrituras), distribución desigual si los datos no están uniformemente distribuidos en el rango.

3. Sharding Basado en Directorio

Mantiene una tabla de búsqueda (directorio) que mapea cada clave de partición a su shard. Este es el enfoque más flexible porque puedes mover datos entre shards simplemente actualizando el directorio, pero el directorio en sí se convierte en un componente crítico y un posible cuello de botella.

// Directory-based sharding
class DirectoryShardedDatabase {
  private directory: Redis; // Fast lookup store
  private shards: Map<string, DatabaseConnection>;

  async getShardForUser(userId: string): Promise<DatabaseConnection> {
    // Look up which shard this user belongs to
    const shardId = await this.directory.get(`user-shard:${userId}`);

    if (!shardId) {
      // New user - assign to the least loaded shard
      const targetShard = await this.getLeastLoadedShard();
      await this.directory.set(`user-shard:${userId}`, targetShard);
      return this.shards.get(targetShard)!;
    }

    return this.shards.get(shardId)!;
  }

  // Moving a user to a different shard is easy
  async migrateUser(userId: string, targetShardId: string): Promise<void> {
    const currentShardId = await this.directory.get(`user-shard:${userId}`);
    const currentShard = this.shards.get(currentShardId!)!;
    const targetShard = this.shards.get(targetShardId)!;

    // Copy data to new shard
    const userData = await currentShard.query('SELECT * FROM users WHERE id = $1', [userId]);
    await targetShard.query('INSERT INTO users VALUES ($1, $2, $3)', [
      userData.id, userData.name, userData.email
    ]);

    // Update directory
    await this.directory.set(`user-shard:${userId}`, targetShardId);

    // Delete from old shard
    await currentShard.query('DELETE FROM users WHERE id = $1', [userId]);
  }
}

Hashing Consistente para Sharding

El problema con el sharding basado en hash básico (hash(key) % N) es que cuando agregas o eliminas un shard, el módulo cambia y casi todas las claves necesitan ser remapeadas. El hashing consistente resuelve esto asegurando que solo K/N claves necesiten ser remapeadas cuando se agrega o elimina un shard (donde K es el número total de claves y N es el número de shards).

Con hashing consistente, tanto servidores como claves se colocan en un anillo de hash. Cada clave se asigna al servidor más cercano en sentido horario en el anillo. Cuando se agrega o elimina un servidor, solo las claves entre él y el servidor anterior en el anillo se ven afectadas.

Consultas Entre Shards

Uno de los mayores desafíos con el sharding es manejar consultas que abarcan múltiples shards. Si una consulta necesita datos de múltiples shards, debes consultar cada shard individualmente, combinar los resultados y ordenarlos/filtrarlos en la capa de aplicación. Esto se conoce como un patrón scatter-gather.

Ejemplos de Sharding del Mundo Real

Estrategia de Sharding de Instagram

Instagram particiona su base de datos PostgreSQL por ID de usuario. Cada shard lógico se mapea a un esquema PostgreSQL dentro de una base de datos más grande, y múltiples esquemas viven en cada servidor físico. Su clave de partición está incrustada en sus IDs de foto globalmente únicos usando un esquema personalizado de generación de IDs:

• 41 bits para timestamp (milisegundos desde época personalizada)
• 13 bits para ID de shard lógico
• 10 bits para secuencia auto-incremental

Esto les permite determinar el shard para cualquier foto solo mirando su ID, sin una tabla de búsqueda. Usan miles de shards lógicos distribuidos en un número menor de servidores físicos, facilitando el rebalanceo al mover shards lógicos entre máquinas físicas.

Almacenamiento de Mensajes de Discord

Discord particiona mensajes por ID de canal. Todos los mensajes en un canal viven en el mismo shard, lo que mantiene las consultas a nivel de canal rápidas. Comenzaron con MongoDB pero migraron a Cassandra al escalar. Su clave de partición es (channel_id, message_id), que asegura que los mensajes dentro de un canal se almacenen juntos en disco para una recuperación eficiente.

Sin embargo, eventualmente se movieron de Cassandra a ScyllaDB (una reescritura en C++ de Cassandra) porque las pausas de recolección de basura de Cassandra causaban picos de latencia. Esto resalta una lección importante: la estrategia de sharding y la elección de tecnología de base de datos son decisiones interconectadas.