Шардирование

Шардирование (sharding) — техника горизонтального разделения данных между несколькими базами данных для масштабирования записи и хранения.

Основные концепции

Что такое шард?

interface Shard {
  id: string;
  host: string;
  port: number;
  database: string;
  // Диапазон данных, за который отвечает шард
  range?: {
    min: any;
    max: any;
  };
}

const shards: Shard[] = [
  {
    id: 'shard-1',
    host: 'db1.example.com',
    port: 5432,
    database: 'users_shard_1',
    range: { min: 0, max: 999999 }
  },
  {
    id: 'shard-2',
    host: 'db2.example.com',
    port: 5432,
    database: 'users_shard_2',
    range: { min: 1000000, max: 1999999 }
  },
  {
    id: 'shard-3',
    host: 'db3.example.com',
    port: 5432,
    database: 'users_shard_3',
    range: { min: 2000000, max: 2999999 }
  }
];

Стратегии шардирования

1. Range-based Sharding

Разделение по диапазонам значений ключа.

class RangeBasedSharding {
  constructor(private shards: Shard[]) {}
  
  getShardForUser(userId: number): Shard {
    for (const shard of this.shards) {
      if (userId >= shard.range!.min && userId <= shard.range!.max) {
        return shard;
      }
    }
    throw new Error(`No shard found for user ${userId}`);
  }
  
  async getUser(userId: number): Promise<User> {
    const shard = this.getShardForUser(userId);
    const connection = await this.connectToShard(shard);
    
    return connection.query(
      'SELECT * FROM users WHERE id = ?',
      [userId]
    );
  }
  
  async createUser(user: User): Promise<User> {
    const shard = this.getShardForUser(user.id);
    const connection = await this.connectToShard(shard);
    
    await connection.query(
      'INSERT INTO users (id, name, email) VALUES (?, ?, ?)',
      [user.id, user.name, user.email]
    );
    
    return user;
  }
  
  private async connectToShard(shard: Shard) {
    return createConnection({
      host: shard.host,
      port: shard.port,
      database: shard.database
    });
  }
}

Преимущества:

• Простая реализация
• Легко добавлять новые диапазоны
• Эффективные range queries

Недостатки:

• Неравномерное распределение данных
• Hotspots (горячие шарды)

2. Hash-based Sharding

Разделение по хэшу ключа.

class HashBasedSharding {
  constructor(private shards: Shard[]) {}
  
  private hash(key: string): number {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      const char = key.charCodeAt(i);
      hash = ((hash << 5) - hash) + char;
      hash = hash & hash; // Convert to 32-bit integer
    }
    return Math.abs(hash);
  }
  
  getShardForKey(key: string): Shard {
    const hashValue = this.hash(key);
    const shardIndex = hashValue % this.shards.length;
    return this.shards[shardIndex];
  }
  
  async getUser(userId: string): Promise<User> {
    const shard = this.getShardForKey(userId);
    const connection = await this.connectToShard(shard);
    
    return connection.query(
      'SELECT * FROM users WHERE id = ?',
      [userId]
    );
  }
  
  async getUserOrders(userId: string): Promise<Order[]> {
    // Все заказы пользователя в одном шарде
    const shard = this.getShardForKey(userId);
    const connection = await this.connectToShard(shard);
    
    return connection.query(
      'SELECT * FROM orders WHERE user_id = ?',
      [userId]
    );
  }
  
  private async connectToShard(shard: Shard) {
    return createConnection({
      host: shard.host,
      port: shard.port,
      database: shard.database
    });
  }
}

Преимущества:

• Равномерное распределение данных
• Нет hotspots

Недостатки:

• Сложно делать range queries
• Проблемы при добавлении шардов (rehashing)

3. Consistent Hashing

Решение проблемы rehashing.

class ConsistentHashing {
  private ring: Map<number, Shard> = new Map();
  private virtualNodes = 150; // Виртуальных узлов на шард
  
  constructor(private shards: Shard[]) {
    this.buildRing();
  }
  
  private buildRing(): void {
    for (const shard of this.shards) {
      // Создаем виртуальные узлы для каждого шарда
      for (let i = 0; i < this.virtualNodes; i++) {
        const virtualKey = `${shard.id}:${i}`;
        const hash = this.hash(virtualKey);
        this.ring.set(hash, shard);
      }
    }
  }
  
  private hash(key: string): number {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      const char = key.charCodeAt(i);
      hash = ((hash << 5) - hash) + char;
      hash = hash & hash;
    }
    return Math.abs(hash);
  }
  
  getShardForKey(key: string): Shard {
    const keyHash = this.hash(key);
    
    // Находим ближайший узел на кольце
    const sortedHashes = Array.from(this.ring.keys()).sort((a, b) => a - b);
    
    for (const hash of sortedHashes) {
      if (hash >= keyHash) {
        return this.ring.get(hash)!;
      }
    }
    
    // Если не нашли, возвращаем первый узел (кольцо замыкается)
    return this.ring.get(sortedHashes[0])!;
  }
  
  addShard(shard: Shard): void {
    this.shards.push(shard);
    
    // Добавляем виртуальные узлы для нового шарда
    for (let i = 0; i < this.virtualNodes; i++) {
      const virtualKey = `${shard.id}:${i}`;
      const hash = this.hash(virtualKey);
      this.ring.set(hash, shard);
    }
  }
  
  removeShard(shardId: string): void {
    // Удаляем все виртуальные узлы шарда
    const toRemove: number[] = [];
    
    for (const [hash, shard] of this.ring.entries()) {
      if (shard.id === shardId) {
        toRemove.push(hash);
      }
    }
    
    toRemove.forEach(hash => this.ring.delete(hash));
    this.shards = this.shards.filter(s => s.id !== shardId);
  }
}

4. Geographic Sharding

Разделение по географическому признаку.

enum Region {
  US_EAST = 'us-east',
  US_WEST = 'us-west',
  EU = 'eu',
  ASIA = 'asia'
}

class GeographicSharding {
  private shardsByRegion = new Map<Region, Shard>();
  
  constructor(shards: Array<{ region: Region; shard: Shard }>) {
    shards.forEach(({ region, shard }) => {
      this.shardsByRegion.set(region, shard);
    });
  }
  
  getShardForUser(userRegion: Region): Shard {
    const shard = this.shardsByRegion.get(userRegion);
    if (!shard) {
      throw new Error(`No shard for region ${userRegion}`);
    }
    return shard;
  }
  
  async getUser(userId: string, region: Region): Promise<User> {
    const shard = this.getShardForUser(region);
    const connection = await this.connectToShard(shard);
    
    return connection.query(
      'SELECT * FROM users WHERE id = ?',
      [userId]
    );
  }
  
  private async connectToShard(shard: Shard) {
    return createConnection({
      host: shard.host,
      port: shard.port,
      database: shard.database
    });
  }
}

Shard Key выбор

Хороший Shard Key

// ✅ Хорошо: user_id как shard key
// - Высокая кардинальность
// - Равномерное распределение
// - Запросы обычно по одному пользователю
class UserSharding {
  getShardKey(user: User): string {
    return user.id; // UUID или auto-increment
  }
}

// ✅ Хорошо: tenant_id для multi-tenant приложений
class TenantSharding {
  getShardKey(data: any): string {
    return data.tenantId; // Все данные тенанта в одном шарде
  }
}

Плохой Shard Key

// ❌ Плохо: timestamp как shard key
// - Все новые записи идут в один шард (hotspot)
class BadTimestampSharding {
  getShardKey(data: any): number {
    return Math.floor(data.timestamp / 86400000); // День
  }
}

// ❌ Плохо: status как shard key
// - Низкая кардинальность
// - Неравномерное распределение
class BadStatusSharding {
  getShardKey(order: Order): string {
    return order.status; // 'pending', 'completed', 'cancelled'
  }
}

// ❌ Плохо: country как shard key для глобального приложения
// - Очень неравномерное распределение
class BadCountrySharding {
  getShardKey(user: User): string {
    return user.country; // US будет огромным, другие маленькими
  }
}

Работа с шардированными данными

Запросы к одному шарду

class ShardedUserService {
  constructor(private sharding: HashBasedSharding) {}
  
  // Простой запрос - один шард
  async getUser(userId: string): Promise<User> {
    const shard = this.sharding.getShardForKey(userId);
    const connection = await this.connectToShard(shard);
    
    return connection.query(
      'SELECT * FROM users WHERE id = ?',
      [userId]
    );
  }
  
  // Связанные данные - один шард (если правильно спроектировано)
  async getUserWithOrders(userId: string): Promise<UserWithOrders> {
    const shard = this.sharding.getShardForKey(userId);
    const connection = await this.connectToShard(shard);
    
    const user = await connection.query(
      'SELECT * FROM users WHERE id = ?',
      [userId]
    );
    
    const orders = await connection.query(
      'SELECT * FROM orders WHERE user_id = ?',
      [userId]
    );
    
    return { ...user, orders };
  }
  
  private async connectToShard(shard: Shard) {
    return createConnection({
      host: shard.host,
      port: shard.port,
      database: shard.database
    });
  }
}

Scatter-Gather запросы

class ScatterGatherQuery {
  constructor(private shards: Shard[]) {}
  
  // Запрос ко всем шардам
  async getAllUsers(): Promise<User[]> {
    const promises = this.shards.map(async (shard) => {
      const connection = await this.connectToShard(shard);
      return connection.query('SELECT * FROM users');
    });
    
    const results = await Promise.all(promises);
    
    // Объединяем результаты
    return results.flat();
  }
  
  // Поиск с пагинацией
  async searchUsers(
    query: string,
    limit: number,
    offset: number
  ): Promise<User[]> {
    // Запрашиваем больше данных с каждого шарда
    const perShardLimit = limit + offset;
    
    const promises = this.shards.map(async (shard) => {
      const connection = await this.connectToShard(shard);
      return connection.query(
        'SELECT * FROM users WHERE name LIKE ? LIMIT ?',
        [`%${query}%`, perShardLimit]
      );
    });
    
    const results = await Promise.all(promises);
    
    // Объединяем и сортируем
    const allUsers = results.flat();
    allUsers.sort((a, b) => a.name.localeCompare(b.name));
    
    // Применяем пагинацию
    return allUsers.slice(offset, offset + limit);
  }
  
  // Агрегация
  async getTotalUserCount(): Promise<number> {
    const promises = this.shards.map(async (shard) => {
      const connection = await this.connectToShard(shard);
      const result = await connection.query(
        'SELECT COUNT(*) as count FROM users'
      );
      return result.count;
    });
    
    const counts = await Promise.all(promises);
    return counts.reduce((sum, count) => sum + count, 0);
  }
  
  private async connectToShard(shard: Shard) {
    return createConnection({
      host: shard.host,
      port: shard.port,
      database: shard.database
    });
  }
}

Транзакции в шардированной среде

Локальные транзакции

class ShardedTransactions {
  async updateUserInShard(userId: string, updates: Partial<User>): Promise<void> {
    const shard = this.sharding.getShardForKey(userId);
    const connection = await this.connectToShard(shard);
    
    // Транзакция внутри одного шарда - работает нормально
    await connection.transaction(async (tx) => {
      await tx.query(
        'UPDATE users SET name = ? WHERE id = ?',
        [updates.name, userId]
      );
      
      await tx.query(
        'INSERT INTO user_audit_log (user_id, action) VALUES (?, ?)',
        [userId, 'name_updated']
      );
    });
  }
}

Распределенные транзакции (избегать!)

// ❌ Плохо: распределенная транзакция
class DistributedTransaction {
  async transferMoney(
    fromUserId: string,
    toUserId: string,
    amount: number
  ): Promise<void> {
    const fromShard = this.sharding.getShardForKey(fromUserId);
    const toShard = this.sharding.getShardForKey(toUserId);
    
    if (fromShard.id !== toShard.id) {
      // Требуется 2PC (Two-Phase Commit) - медленно и сложно
      throw new Error('Cross-shard transactions not supported');
    }
    
    // Если в одном шарде - обычная транзакция
    const connection = await this.connectToShard(fromShard);
    await connection.transaction(async (tx) => {
      await tx.query(
        'UPDATE accounts SET balance = balance - ? WHERE user_id = ?',
        [amount, fromUserId]
      );
      
      await tx.query(
        'UPDATE accounts SET balance = balance + ? WHERE user_id = ?',
        [amount, toUserId]
      );
    });
  }
}

Saga Pattern для распределенных операций

class TransferSaga {
  async transferMoney(
    fromUserId: string,
    toUserId: string,
    amount: number
  ): Promise<void> {
    const transferId = generateId();
    
    try {
      // Шаг 1: Резервируем деньги у отправителя
      await this.reserveMoney(fromUserId, amount, transferId);
      
      // Шаг 2: Добавляем деньги получателю
      await this.addMoney(toUserId, amount, transferId);
      
      // Шаг 3: Подтверждаем списание
      await this.confirmWithdrawal(fromUserId, transferId);
      
    } catch (error) {
      // Компенсирующие транзакции
      await this.cancelReservation(fromUserId, transferId);
      throw error;
    }
  }
  
  private async reserveMoney(
    userId: string,
    amount: number,
    transferId: string
  ): Promise<void> {
    const shard = this.sharding.getShardForKey(userId);
    const connection = await this.connectToShard(shard);
    
    await connection.query(
      'UPDATE accounts SET balance = balance - ?, reserved = reserved + ? WHERE user_id = ?',
      [amount, amount, userId]
    );
    
    await connection.query(
      'INSERT INTO pending_transfers (id, user_id, amount, status) VALUES (?, ?, ?, ?)',
      [transferId, userId, amount, 'reserved']
    );
  }
  
  private async addMoney(
    userId: string,
    amount: number,
    transferId: string
  ): Promise<void> {
    const shard = this.sharding.getShardForKey(userId);
    const connection = await this.connectToShard(shard);
    
    await connection.query(
      'UPDATE accounts SET balance = balance + ? WHERE user_id = ?',
      [amount, userId]
    );
  }
  
  private async confirmWithdrawal(
    userId: string,
    transferId: string
  ): Promise<void> {
    const shard = this.sharding.getShardForKey(userId);
    const connection = await this.connectToShard(shard);
    
    await connection.query(
      'UPDATE accounts SET reserved = reserved - (SELECT amount FROM pending_transfers WHERE id = ?) WHERE user_id = ?',
      [transferId, userId]
    );
    
    await connection.query(
      'UPDATE pending_transfers SET status = ? WHERE id = ?',
      ['completed', transferId]
    );
  }
  
  private async cancelReservation(
    userId: string,
    transferId: string
  ): Promise<void> {
    const shard = this.sharding.getShardForKey(userId);
    const connection = await this.connectToShard(shard);
    
    await connection.query(
      'UPDATE accounts SET balance = balance + (SELECT amount FROM pending_transfers WHERE id = ?), reserved = reserved - (SELECT amount FROM pending_transfers WHERE id = ?) WHERE user_id = ?',
      [transferId, transferId, userId]
    );
    
    await connection.query(
      'UPDATE pending_transfers SET status = ? WHERE id = ?',
      ['cancelled', transferId]
    );
  }
  
  private async connectToShard(shard: Shard) {
    return createConnection({
      host: shard.host,
      port: shard.port,
      database: shard.database
    });
  }
}

Решардирование

Добавление нового шарда

class ReshardingManager {
  async addShard(newShard: Shard): Promise<void> {
    // 1. Добавляем новый шард в конфигурацию
    this.shards.push(newShard);
    
    // 2. Создаем схему в новом шарде
    await this.createSchema(newShard);
    
    // 3. Мигрируем данные
    await this.migrateData(newShard);
    
    // 4. Обновляем роутинг
    this.updateRouting();
  }
  
  private async migrateData(targetShard: Shard): Promise<void> {
    // Определяем, какие данные нужно мигрировать
    const dataToMigrate = await this.identifyDataToMigrate(targetShard);
    
    for (const { sourceShard, keys } of dataToMigrate) {
      const sourceConn = await this.connectToShard(sourceShard);
      const targetConn = await this.connectToShard(targetShard);
      
      // Мигрируем батчами
      for (let i = 0; i < keys.length; i += 1000) {
        const batch = keys.slice(i, i + 1000);
        
        // Читаем из источника
        const data = await sourceConn.query(
          `SELECT * FROM users WHERE id IN (${batch.map(() => '?').join(',')})`,
          batch
        );
        
        // Пишем в целевой шард
        await targetConn.query(
          `INSERT INTO users (id, name, email) VALUES ${data.map(() => '(?, ?, ?)').join(',')}`,
          data.flatMap(u => [u.id, u.name, u.email])
        );
        
        // Удаляем из источника (опционально, после проверки)
        // await sourceConn.query(
        //   `DELETE FROM users WHERE id IN (${batch.map(() => '?').join(',')})`,
        //   batch
        // );
      }
    }
  }
  
  private async identifyDataToMigrate(
    targetShard: Shard
  ): Promise<Array<{ sourceShard: Shard; keys: string[] }>> {
    // Логика определения данных для миграции
    // зависит от стратегии шардирования
    return [];
  }
  
  private async connectToShard(shard: Shard) {
    return createConnection({
      host: shard.host,
      port: shard.port,
      database: shard.database
    });
  }
  
  private updateRouting(): void {
    // Обновляем маршрутизацию запросов
  }
  
  private async createSchema(shard: Shard): Promise<void> {
    const connection = await this.connectToShard(shard);
    await connection.query(`
      CREATE TABLE IF NOT EXISTS users (
        id VARCHAR(36) PRIMARY KEY,
        name VARCHAR(255),
        email VARCHAR(255),
        created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
      )
    `);
  }
}

Best Practices

1. Проектирование схемы

// ✅ Хорошо: денормализация для избежания cross-shard запросов
interface UserShard {
  id: string;
  name: string;
  email: string;
  // Денормализованные данные
  totalOrders: number;
  lastOrderDate: Date;
}

interface OrderShard {
  id: string;
  userId: string; // Shard key
  // Денормализованные данные пользователя
  userName: string;
  userEmail: string;
  items: OrderItem[];
  total: number;
}

2. Мониторинг

class ShardMonitor {
  async getShardMetrics(): Promise<ShardMetrics[]> {
    const metrics = await Promise.all(
      this.shards.map(async (shard) => {
        const connection = await this.connectToShard(shard);
        
        const [size, count, load] = await Promise.all([
          connection.query('SELECT pg_database_size(current_database())'),
          connection.query('SELECT COUNT(*) FROM users'),
          connection.query('SELECT * FROM pg_stat_activity')
        ]);
        
        return {
          shardId: shard.id,
          size: size.pg_database_size,
          recordCount: count.count,
          activeConnections: load.length,
          timestamp: new Date()
        };
      })
    );
    
    return metrics;
  }
  
  detectHotspots(metrics: ShardMetrics[]): string[] {
    const avgLoad = metrics.reduce((sum, m) => sum + m.activeConnections, 0) / metrics.length;
    
    return metrics
      .filter(m => m.activeConnections > avgLoad * 1.5)
      .map(m => m.shardId);
  }
  
  private async connectToShard(shard: Shard) {
    return createConnection({
      host: shard.host,
      port: shard.port,
      database: shard.database
    });
  }
}

interface ShardMetrics {
  shardId: string;
  size: number;
  recordCount: number;
  activeConnections: number;
  timestamp: Date;
}

Заключение

Шардирование — мощная техника масштабирования, но с компромиссами:

Преимущества:

• Практически неограниченное масштабирование
• Распределение нагрузки
• Изоляция отказов

Недостатки:

• Сложность реализации
• Проблемы с cross-shard запросами
• Сложность транзакций
• Необходимость решардирования

Когда использовать:

• Данные не помещаются на один сервер
• Нагрузка на запись превышает возможности одного сервера
• Есть естественный shard key (user_id, tenant_id)