Шардування

1. Що таке шардування?

Якщо завзято гуглити, то з'ясується, що між так званим партиціонуванням і так званим шардингом досить розмиті межі. Кожен називає все, що хоче, чим хоче. Одні люди розрізняють горизонтальне партиціонування та шардинг. Інші кажуть, що шардинг — це певний вид горизонтального партиціонування.

Єдиного термінологічного стандарту, який був би схвалений батьками-засновниками та в ISO сертифікований, я не знайшов. Особисте внутрішнє переконання приблизно таке: Partitioning в середньому — це "ріжемо базу на шматки" довільним чином.

• Vertical partitioning — поколоночно. Наприклад, є гігантська таблиця на пару мільярдів записів із 60 колоноками. Замість того, щоб тримати одну таку гігантську таблицю, тримаємо 60 не менших гігантських таблиць по 2 млрд записів — і це не поколоночна база, а вертикальне партиціонування (як приклад термінології).
• Horizontal partitioning — ріжемо рядково, можливо, всередині сервера.

Незручний момент тут у тонкій відмінності між горизонтальним партиціонуванням і шардуванням. Мене можна на шматки різати, але я впевнено вам не скажу, у чому воно полягає. Є відчуття, що шардування та горизонтальне партиціонування — це приблизно одне й те саме.

Шардування — це загалом, коли велика таблиця в термінах баз або проколекція документів, об'єктів, якщо у вас не зовсім база даних, а document store, ріжеться саме по об'єктах. Тобто з 2 млрд об'єктів вибираються шматки неважливо якого розміру. Об'єкти самі по собі всередині кожного об'єкта не розрізаємо на шматки, окремі колонки не розкладаємо, а саме пачками розкладаємо в різні місця.

Далі вже пішли тонкі термінологічні відмінності. Наприклад, умовно кажучи, розробники на Postgres можуть сказати, що горизонтальне партиціонування — це коли всі таблиці, на які розділена основна таблиця, лежать в одній схемі, а коли на різних машинах — це вже шардування.

У загальному сенсі, не прив'язуючись до термінології конкретної бази даних та конкретної системи управління даними, є відчуття, що шардування — це просто нарізка рядково/підокументно тощо — і все.

Наголошую, типово. У тому сенсі, що ми все це робимо не просто так, щоб нарізати 2 млрд документів на 20 таблиць, кожна з яких була б більш manageable, а для того, щоб розподілити це на багато ядер, багато дисків чи багато різних фізичних чи віртуальних серверів.

2. Ділимо неподільне

Допускається, що ми це робимо для того, щоб кожен шард — кожен шматок даних — багаторазово реплікувати. Але насправді ні.

INSERT INTO docs00
SELECT * FROM documents WHERE (id%16)=0
...

INSERT INTO docs15
SELECT * FROM documents WHERE (id%16)=15

Насправді, якщо ти зробите таку нарізку даних, і з однієї гігантської SQL таблиці на MySQL на твоєму доблесному ноутбуці згенеруєте 16 маленьких табличок, не виходячи за рамки жодного ноутбука, жодної схеми, жодної бази даних тощо — все, у вас уже шардування.

Це призводить до наступного:

• Збільшується bandwidth — пропускна спроможність.
• Latency не змінюється, тобто кожен, так би мовити, worker чи consumer у цьому випадку отримує своє. Різні запити обслуговуються приблизно за один час.
• Або те й інше, і ще high availability (реплікація).

Навіщо bandwidth? У нас іноді можуть виникати такі обсяги даних, які не влазять — не зрозуміло куди, але не влазять — на 1 {ядро | диск | сервер | ...}. Просто не вистачає ресурсів, і все. Щоб з цим великим датасетом працювати, треба його нарізати.

Навіщо latency? На одному ядрі просканувати таблицю з 2 млрд рядків у 20 разів повільніше, ніж просканувати 20 таблиць на 20 ядрах, роблячи це паралельно. Дані надто повільно обробляються однією ресурсі.

Навіщо high availability? Або нарізаємо дані, для того щоб робити і одне, й інше одночасно, і заразом кілька копій кожної шарди — реплікація забезпечує високу доступність.

3. Простий приклад «як зробити руками»

Умовний шардинг можна випиляти за допомогою тестової таблиці test.documents на 32 документи, і генерацією з цієї таблиці 16 тестових таблиць приблизно по 2 документи test. docs00, 01, 02, ..., 15.

INSERT INTO docs00
SELECT * FROM documents WHERE (id%16)=0
...

INSERT INTO docs15
SELECT * FROM documents WHERE (id%16)=15

Чому приблизно? Тому що апріорі ми не знаємо, як розподілені id. Якщо від 1 до 32 включно, то буде рівно по 2 документи, інакше — ні.

Робимо ми це ось для чого. Після того, як ми зробили 16 таблиць, ми можемо «захавати» 16 того, що нам потрібно. Незалежно від того, на що ми вперлися, ми можемо на ці ресурси розпаралелітися. Наприклад, якщо не вистачає дискового простору, буде мати сенс розкласти ці таблиці за окремими дисками.

Все це, на жаль, не безкоштовно. Підозрюю, що у випадку з канонічним SQL-стандартом (давно не перечитував SQL-стандарт, можливо його давно не оновлювали), немає офіційного стандартизованого синтаксису для того, щоб будь-якому SQL-серверу сказати: «Дорогий SQL-сервер, зроби мені 32 шарди і розклади їх на 4 диски». Але в окремо взятих реалізаціях найчастіше є конкретний синтаксис для того, щоб зробити в принципі те саме. У PostgreSQL є механізми для партиціонування, у MySQL є MariaDB, Oracle напевно це все зробив вже дуже давно.

Проте, якщо ми це робимо руками, без підтримки бази даних і в межах стандарту, то платимо умовною складністю доступу до даних. Там, де було простим SELECT * FROM documents WHERE id=123, тепер 16 x SELECT * FROM docsXX. І добре, якщо ми намагалися діставати запис за ключем. Значно цікавіше, якщо ми намагалися діставати ранній діапазон записів. Тепер (якщо ми, наголошую, ніби дурні, і залишаємося в межах стандарту) результати цих 16 SELECT * FROM доведеться об'єднувати у застосунку.

Якої зміни продуктивності очікувати?

• Інтуїтивно — лінійної.
• Теоретично — сублінійної, тому що Amdahl law.
• Практично — можливо, майже лінійно, можливо, ні.

Насправді правильна відповідь — невідомо. Спритним застосуванням техніки шардування можна досягти значного надлінійного погіршення роботи твоєї програми, та ще й DBA прибіжить з розпеченою кочергою.

Подивимося, як цього можна досягти. Зрозуміло, що просто поставити налаштування в PostgreSQL shards = 16, а далі воно саме злітає — це не цікаво. Давай подумаємо, як можна домогтися того, щоб від шардування в 16 разів ми загальмували б у 32 — це цікаво з того погляду, як би цього не робити.

Наші спроби прискоритися або загальмувати завжди будуть впиратися в класику — у старий-добрий закон Амдала (Amdahl law), який каже, що немає ідеальної розпаралелізації будь-якого запиту, завжди є якась послідовна частина.

4. Amdahl law

Завжди є serialized частина.

Завжди є частина виконання запиту, яка паралельна, і завжди є частина, яка не паралельна. Навіть якщо тобі здається, що ідеально паралельний запит, як мінімум збір рядка результату, яку ви збираєтеся надіслати на клієнта, з рядків, отриманих з кожного шарда, завжди є, і він завжди послідовний.

Завжди є якась послідовна частина. Вона може бути крихітною, абсолютно непомітною на загальному тлі, вона може бути гігантською і відповідно сильно впливає на паралелізацію, але вона є завжди.

До того ж, її вплив змінюється і може відчутно зрости, наприклад, якщо ми наріжемо нашу таблицю — давай піднімемо ставки — із 64 записів на 16 таблиць по 4 записи, ця частина зміниться. Звісно ж, судячи з таких гігантських обсягів даних, ми працюємо на мобільному телефоні і 86 процесорі 2 МГц, у нас і файлів бракує, які можна одночасно тримати відкритими. Мабуть, з такими вхідними даними ми по одному файлу за раз відкриваємо.

• Було Total = Serial + Parallel. Де, наприклад, parallel — це вся робота всередині DB, а serial — надсилання результату в клієнта.
• Стало Total2 = Serial + Parallel/N + Xserial. Наприклад, коли загальний ORDER BY, Xserial>0.

Цим нехитрим прикладом я намагаюся показати, що з'являється якесь Xserial. Окрім того, що завжди є серіалізована частина, і того, що ми намагаємося працювати з даними паралельно, з'являється додаткова частина для забезпечення нарізки даних. Грубо кажучи, нам може знадобитися:

• знайти у внутрішньому словнику бази даних ці 16 таблиць;
• відкрити файли;
• аллокувати пам'ять;
• розаллокувати пам'ять;
• смерджити результати;
• синхронізуватися між ядрами.

Якісь розсинхронізаційні ефекти все одно обов'язково з'являються. Вони можуть бути незначними і позичати одну мільярдну від загального часу, але завжди ненульові і завжди є. З їх допомогою ми і можемо різко втратити у продуктивності після шардування.

Це стандартна картинка про закон Амдала. Тут важливо те, що лінії, які повинні в ідеалі бути прямими і лінійно зростати, упираються в асимптоту. Але оскільки графік з інтернету нечитабельний, я виготовив, як на мене, наочніші таблиці з цифрами.

Припустимо, ми маємо певну серіалізовану частину обробки запиту, яка займає лише 5%: serial = 0.05 = 1 / 20.

Інтуїтивно здавалося б, що при серіалізованій частині, яка займає лише 1/20 від обробки запиту, якщо ми розпаралелімо обробку запиту на 20 ядер, вона стане приблизно в 20, у гіршому випадку — у 18 разів швидше.

Насправді математика — штука безсердечна:

wall = 0.05 + 0.95/num_cores, speedup = 1 / (0.05 + 0.95/num_cores)

Виявляється, що якщо акуратно порахувати, при серіалізованій частині в 5%, прискорення буде в 10 разів (10,3), а це 51% порівняно з теоретичним ідеальним.

Використовуючи 20 ядер ( 20 дисків, якщо завгодно) на те завдання, над яким раніше працювало одне, ми навіть теоретично прискорення більше ніж у 20 разів ніколи не отримаємо, а практично — набагато менше. Причому зі збільшенням числа паралелей неефективність сильно зростає.

Коли залишається лише 1% серіалізованої роботи, а 99% паралелюється, значення прискорення дещо покращуються:

Для геть термоядерного запиту, який натурально виконується годинами, і підготовча робота зі збирання результату займає дуже мало часу (serial = 0.001), ми побачимо вже хорошу ефективність:

Зверни увагу: 100% ми не побачимо ніколи. В особливо вдалих випадках можна побачити, наприклад, 99,999%, але не рівно 100%.