Шардування

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

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

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

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

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

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

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

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

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

1.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 у даному випадку, отримує своє. Різні запити обслуговуються приблизно за один час.
• Або і те, і інше, і ще висока availability (реплікація).

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

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

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

1.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), який каже, що немає ідеальної розпаралелізації будь-якого запиту, завжди є якась послідовна частина.

1.4 Amdahl law

Завжди є серіалізована частина.

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

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

Крім того, її вплив змінюється і може відчутно підрости, наприклад, якщо ми наріжемо нашу таблицю - давайте піднімемо ставки - з 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%.