🏗️ Розділ 17 · Питання #10

Що таке шардування sharding

Уявіть багатотомну енциклопедію:

🏗️ Мікросервіси 📄 Вихідний Markdown

🟢 Junior Level

Шардування (Sharding / Горизонтальне секціонування) — це архітектурний метод розділення однієї логічної бази даних на кілька фізично незалежних серверів (шардів), де кожен сервер зберігає лише свою унікальну частину даних.

                        [Шардована база даних]
                                     │
          ┌──────────────────────────┼──────────────────────────┐
          ▼                          ▼                          ▼
     [Шард 1]                   [Шард 2]                   [Шард 3]
Користувачі A–H            Користувачі I–P            Користувачі Q–Z
(Сервер 1: 30 млн)         (Сервер 2: 30 млн)         (Сервер 3: 30 млн)

Різниця: Реплікація vs Шардування

  • Реплікація (Read Replicas): Кожен сервер зберігає 100% повну копію всієї бази даних. Використовується для підвищення відмовостійкості та розподілу навантаження на читання (SELECT). Навантаження на запис (INSERT / UPDATE) реплікація не знижує.
  • Шардування: Сервери зберігають різні підмножини даних. Використовується, коли загальний обсяг бази даних або вхідний потік запису фізично не поміщається на один (навіть найпотужніший) сервер.

Аналогія з життя:

Уявіть багатотомну енциклопедію:

  • Якби вся енциклопедія була в одній книзі товщиною в 10 метрів, жодна людина не змогла б її підняти чи перегорнути сторінку.
  • Розділивши її на 26 окремих томів (шардів), 26 людей можуть одночасно читати і робити записи в різних томах, не створюючи черг та блокувань.

🟡 Middle Level

1. Вибір ключа шардування (Shard Key) та стратегії маршрутизації

Shard Key (Ключ шардування) — це поле сутності (наприклад, user_id або tenant_id), за значенням якого маршрутизатор визначає цільовий фізичний сервер для виконання SQL-запиту.

Стратегія Принцип роботи Плюси Мінуси / Ризики
Range-based (За діапазоном) ID 1..1M -> Shard 1, 1M..2M -> Shard 2 Швидкі Range-запити (BETWEEN date1 AND date2) 🔴 Hot Spotting: Усі нові записи йдуть строго в останній шард!
Hash-based (За хешем ключа) shard_id = hash(user_id) % N 🟢 Ідеально рівномірний розподіл навантаження Запити діапазонів вимагають опитування всіх $N$ шардів
Directory-based (Довідник) Зовнішня lookup-таблиця: tenant_123 -> Shard 4 Гнучкість: VIP-клієнтів можна ізолювати на виділені ноди Таблиця маршрутизації стає SPOF і вузьким місцем за I/O

2. Реалізація динамічної маршрутизації в Spring (AbstractRoutingDataSource)

У Java-застосунках клієнтське шардування часто налаштовується через підміну джерела даних:

public class ShardedRoutingDataSource extends AbstractRoutingDataSource {

    @Override
    protected Object determineCurrentLookupKey() {
        // Контекст поточного потоку визначає Shard Key (наприклад, TenantContext)
        Long customerId = ShardContextHolder.getCustomerId();
        if (customerId == null) {
            return "shard_default";
        }
        // Хешування: розподіл по 4 шардах
        int shardIndex = Math.abs(customerId.hashCode() % 4);
        return "shard_" + shardIndex;
    }
}

3. Фундаментальні проблеми шардування

  1. Scatter-Gather (Розсіювання-Збирання): Якщо запит не містить Shard Key (наприклад, SELECT * FROM orders WHERE status = 'SHIPPED'), координатор зобов’язаний відправити запит на всі шарди паралельно, дочекатися всіх відповідей, об’єднати та відсортувати їх у пам’яті.
  2. Втрата цілісності (No Cross-Shard Foreign Keys): База даних на Шарді 1 не може перевірити зовнішній ключ FOREIGN KEY до таблиці на Шарді 2. Контроль зв’язків переноситься повністю в код застосунку.
  3. Міжшардові транзакції: Якщо потрібно оновити дані на Шарді 1 та Шарді 2 атомарно, класичний BEGIN TRANSACTION безсилий. Потрібен протокол 2PC (XA) або патерн Saga.

🔴 Senior Level

1. Генерація первинних ключів у шардованих БД (ID Generation)

У шардованій базі не можна використовувати AUTO_INCREMENT або SERIAL, оскільки на різних серверах неминуче виникнуть колізії (на Шарді 1 з’явиться id=42 і на Шарді 2 з’явиться id=42).

Промислові рішення:

  1. Twitter Snowflake (64-бітний ID): 
    [1 біт: знак] [41 біт: timestamp у мс] [10 біт: ID ноди/шарда] [12 біт: інкремент sequence]

    Плюси: Ідентифікатори глобально унікальні, впорядковані за часом (Time-ordered), поміщаються в 64-бітний BIGINT і відмінно індексуються в B-Tree.

  2. UUIDv7: Новий стандарт UUID, що містить 48-бітний timestamp у старших бітах. Не фрагментує індекси B-Tree на відміну від повністю випадкового UUIDv4.
  3. Centralized Sequence Allocation: Виділення блоків ID пачками (Hi/Lo алгоритм) через Redis або виділену таблицю в координаторі.

2. Consistent Hashing (Консистентне хешування) та віртуальні ноди

При наївному хешуванні hash(key) % N: При збільшенні кількості шардів з 3 до 4 стара формула перенаправить 75% усіх існуючих ключів на інші сервери. Доведеться зупинити систему й перемістити петабайти даних.

Consistent Hashing вирішує проблему:

                     Кільце хешів [0 ... 2^32 - 1]
                                 [0]
                         .----------------.
                     .'     Node A (V1)     '.
                   .'                          '.
             Node C (V2)                     Node B (V1)
                   '.                          .'
                     '.     Node A (V2)      .'
                         '----------------'
  • Простір хешів закольцований від $0$ до $2^{32}-1$.
  • При додаванні нового шарда $N+1$ переїжджає лише $\frac{1}{N+1}$ частина даних виключно від сусіднього вузла за кільцем.
  • Virtual Nodes (vnodes): Щоб уникнути нерівномірного розподілу («важких» ділянок кільця), кожен фізичний сервер представлений на кільці десятками віртуальних точок (Node_A_1, Node_A_2, Node_A_3).

3. Zero-Downtime Resharding (Міграція без простою)

Процес розділення переповненого шарда на живій продакшен-базі:

  1. Provisioning: Розгортання нового цільового шарда.
  2. Dual-Write: Застосунок налаштовується на запис змін у старий і новий шарди одночасно.
  3. Backfill: Фоновий batch-процес копіює історичні дані зі старого шарда на новий.
  4. Catch-Up & Verification: Звірка контрольних сум і застосування логів змін (CDC / Debezium).
  5. Read Switch: Перемикання запитів на читання на новий шард.
  6. Stop Dual-Write: Відключення запису в старий шард і звільнення дискового простору.

4 Tricky Questions

1. Як вирішити проблему Hotspot / Celebrity Problem, коли один користувач генерує 80% навантаження на свій шард?

Відповідь: Якщо ключ шардування — user_id, а серед користувачів є зірка з 50 мільйонами підписників, шард із цим записом зазнаватиме позамежного навантаження (CPU, IOPS, мережевий трафік), тоді як решта шардів простоюють. Рішення:

  1. Salted Shard Key: Для популярних сутностей ключ доповнюється випадковою сіллю: key = user_id + "_" + random(1..10). Дані цього користувача рівномірно розмазуються по 10 різних шардах. При читанні виконується паралельне Scatter-Gather опитування цих 10 шардів.
  2. Dedicated Shard: Виділення великих орендарів (тенантів) / знаменитостей на персональні фізичні сервери за допомогою Directory-based маршрутизації.
  3. Агресивне кешування: Винесення гарячих даних на читання в Redis/Memcached.

2. У чому небезпека глибокої пагінації (ORDER BY created_at LIMIT 10 OFFSET 100000) у шардованій СУБД?

Відповідь: При запиті без Shard Key координатор повинен опитати всі шарди. Щоб повернути сторінку зі зміщенням 100 000, координатор зобов’язаний запросити з кожного з $N$ шардів по $100\,010$ записів! При 10 шардах координатор вивантажить мережею понад 1 000 000 рядків, відсортує їх усі у своїй оперативній пам’яті, відкине перші 100 000 і віддасть клієнту 10 штук. Це гарантовано викличе OutOfMemoryError або гігантський latency spike. Рішення: Використання Keyset Pagination (Seek Method) замість OFFSET: WHERE created_at < :last_seen_timestamp AND id < :last_seen_id ORDER BY created_at DESC LIMIT 10.

3. Чому в шардованих базах даних вкрай складно реалізувати глобальні унікальні обмеження (UNIQUE constraint) не за Shard Key?

Відповідь: Реляційна СУБД перевіряє UNIQUE через локальний B-Tree індекс на конкретному сервері. Якщо таблиця шардована за user_id, а унікальним має бути поле email:

  • Щоб перевірити, чи вільний email = "test@domain.com" при реєстрації, СУБД на Шарді 1 не знає, чи є такий рядок на Шарді 2.
  • Довелося б робити розподілене блокування всіх шардів перед кожною вставкою. Рішення: Створення окремого сервісу/таблиці зіставлення (Lookup Index): email -> user_id, шардованого за hash(email).

4. У чому різниця між шардуванням на рівні застосунку (Client-Side) та на рівні СУБД (Distributed SQL / NewSQL)?

Відповідь:

  • Шардування на рівні застосунку (ShardingSphere, Hibernate, Custom Router): Застосунок сам знає про шарди і керує пулами з’єднань. СУБД — звичайні незалежні інстанси PostgreSQL/MySQL. Плюси: повний контроль, дешевше. Мінуси: складний код застосунку, відсутність підтримки крос-шардових транзакцій та перебалансування з коробки.
  • Шардування на рівні СУБД (CockroachDB, YugabyteDB, Vitess, Citus): Для застосунку база виглядає як єдиний монолітний сервер. СУБД сама розподіляє шарди (Ranges/Tablets) по нодах за допомогою розподіленого консенсусу (Raft/Paxos), автоматично робить ребалансування і розподілені транзакції. Мінуси: вищі вимоги до ресурсів та мережевого latency між нодами.

🎯 Шпаргалка для інтерв’ю

Головне:

  • Шардування — горизонтальний поділ даних за рядками на незалежні сервери для масштабування запису та обсягу даних.
  • Shard Key — поле, що визначає адресу сервера (вимагається висока кардинальність і рівномірний розподіл).
  • Стратегії: Hash-based (найпопулярніша і найрівномірніша), Range-based (ризик Hot Spots), Directory-based (максимальна гнучкість).
  • Consistent Hashing захищає від необхідності переносити всю базу при додаванні нових серверів.
  • ID у шардованих системах: Twitter Snowflake або UUIDv7 (автоінкремент бази непридатний через колізії).
  • Головні проблеми: Scatter-Gather запити, втрата зовнішніх ключів (FK), складність міжшардових транзакцій і пагінації.

Червоні прапорці (Чого говорити НЕ МОЖНА):

  • ❌ «Шардування потрібно підключати в проєкт із першого дня» (Шардування впроваджують лише при вичерпанні лімітів вертикального масштабування, від 1–2 ТБ або сотень тисяч TPS).
  • ❌ «Для шардованої бази ми використовуємо автоінкрементні ID у таблицях» (Це призведе до дублікатів ID на різних шардах).
  • ❌ «Міжшардові JOIN працюють так само, як звичайні» (Вони вимагають викачування даних мережею на координатор і призводять до деградації продуктивності).

Пов’язані теми: