Sharding – patterns and antipatterns



Костянтин Осипов (
kostja ), Олексій Рибак (
fisher
Костянтин Осипов: Доповідь народився з наступної розмови. Я, як завжди, намагався переконати Олексія більше використовувати Tarantool, а він сказав, що там досі немає шардинга і, взагалі, нецікаво. Тоді ми почали розмірковувати про те, чому немає. Я почав розповідати, що тут немає одного універсального рішення, автоматика повна за вас працює, а ви тільки кава на роботі п'єте і все…

Тому народився ця доповідь — щоб подивитися на те, який буває шардінг, які методи у яких системах використовуються, які переваги і недоліки, чому не можна однією срібною кулею» все вирішити?
Якщо говорити про шардинге, як про проблему, то, взагалі кажучи, такої проблеми немає. Є проблема розподілених систем, тобто великих баз даних, які горизонтально масштабуються, у них безліч завдань, ми їх перерахували:



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

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

Є завдання розподіленого виконання складних запитів. MapReduce або розподілений SQL. Це теж не воно.

Так, про що ми будемо говорити?

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

Олексій Рибак: Я додам. Термін вже усталений, але, все-таки, що ж таке шардінг? Раптом хтось не знає. Шардінг — це метод, як правило, горизонтального поділу даних. Найчастіше про шардінг говорять не тільки про розподілені бази даних, але і, взагалі, про розподілені сховища. Ми будемо, насамперед, фокусуватися на базах даних.



Костянтин Осипов: У нашому звіті ми взяли три речі, які складають з себе сам шардінг, це:

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

Олексій Рибак: Незважаючи на те, що ми будемо розповідати всякі історії про те, що і як було зроблено, все-таки, основа доповіді — методологічна. Щоб уявити, як завжди все робиться (а, так чи інакше, все робиться лише кількома способами), з тим, щоб вляглися терміни, і в наступний раз, якщо ми будемо заглиблюватися в якісь теми, ми говорили на одній мові.

Костянтин Осипов: Перед нами не стоїть завдання переконати вас використовувати той чи інший продукт, але за допомогою цієї доповіді, може бути, ви зможете краще розуміти, як «під капотом» працює той чи інший продукт, і які переваги і недоліки рішення, обраного розробниками цього продукту.

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

Власне, що таке шардінг на поверхні? Це вибір способу. Цей вибір я позначу ось так просто:



У нас є якийсь ключ, ми повинні визначити шард. Шард — це зазвичай або IP-адресу або DNS-адресу комп'ютера, на якому все це знаходиться.

Насправді, формула неправильна, тому що в загальному випадку тут повинна бути функція від ключа і від кількості серверів, тобто скільки у нас машин або, взагалі, від безлічі серверів. І вона повинна видавати потрібний сервер, тому що вона по-різному працює на різній кількості серверів.

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

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

Одна історія — ще з 2001 р., часів молодості SpyLOG-а — там шардінг був заснований на користувачів. Що таке SpyLOG? Зараз це Openstat. Він збирає статистику відвідувань, тобто це такий трекер, лічильник, маленька кнопочка на сторінці.

Загалом, усі сайти — як великі, так і дрібні — були на той момент розподілені по 40 машин. І, відповідно, сайти побільше жили разом з сайтами подрібніше, тобто ключем шардинга був ID сайту, наприклад, анекдот.ру, рамблер.ру, яндекс.ру…

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

Тому, коли ви вибираєте те, по чому ви шардите дані, ви повинні вибрати досить маленької об'єкт, щоб він не поклав систему.

Припустимо, у разі фейсбуку у вас є сторінка Джастіна Бібера, і ви вирішили шардить дані теж за користувачам. Природно, у Джастіна Бібера мільйон якихось фоловерів, лайкерів, на кожне повідомлення купа репостов і т. д. Тому, напевно, вибір Джастіна Бібера в якості того, кому ви будете шардить — не найкраща ідея.

Другий момент, який треба при шардинге тримати в голові, що шардінг — це не про нормалізацію, тобто якщо ви вважаєте, що є якийсь канонічний спосіб подивитися на ваші дані і визначити, як ви їх будете розподіляти за вашим машинам, то це не так. Тобто, ви повинні дивитися не на дані, а на use case-и, на ваш додаток, на ваш бізнес, і ви повинні думати, який use case у вашому бізнесі самий важливий і повинен бути самим продуктивним. Тому що в шардинге завжди є компроміси. Якісь запити працюють швидко, миттєво, якісь запити ви змушені будете виконувати на весь кластер. І вибір того, за яким ключу ви шардите, визначає це.

Олексій Рибак: Про Джастине Бибере. А я вважаю, що у більшої частини соціальних мереж, насправді, вибір користувача шардингового ключа — це хороший вибір. Але треба пам'ятати, що якщо ви при цьому всі пости, коментарі і пр. запаковуєте в один і той же шард, то будьте готові, що в якийсь момент у вас буде дуже неоднорідний розподіл даних і, можливо, вам потрібно буде використовувати у вашому проекті два типи шардинга — один ваш початковий, за юзерам, а другий — якийсь додатковий — наприклад, за комментам.

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

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

Костянтин Осипов: Ще один момент, про який хотілося б сказати. Не завжди шардінг-ключ у вас зберігається. Наприклад, зберігання сесій на мейл.ру. Припустимо, у вас є ID мейл.ру, у мене це kostea.mail.ru або щось таке. Сесія — це той об'єкт, який ідентифікує девайс, з якого я зайшов. Відповідно, у одного логіна багато сесій. Мейл.ру зберігає всі сесії одного користувача на одному шарде, т.е. ключем шардинга є логін. Але сама сесія, тобто ідентифікатор об'єкта — первинний ключ — це не ключ шардинга. Тобто, не завжди так буває, що ідентифікатор об'єкта — це ключ шардинга. І це буває зручно, оскільки все зберігається на одному шарде. Ми можемо одного юзера, наприклад, скрізь разлогинить, якщо ми підозрюємо, що його зламали пароль і т. п. Ми легко можемо цим керувати.

Ось приклад хороших і поганих шард-ключів:



Олексій Рибак: Ми до цього прикладу будемо ще неодноразово повертатися, тому продовжимо.

Якщо ви зіткнулися з шардингом, то, швидше за все, це відбулося в момент, коли ви наш доповідь ще не чули. Ви спробували щось пошукати в Інтернеті і нічого особливого не знайшли. Протягом останніх, напевно, десять років багато команди пройшли один і той же шлях винаходу велосипеда. Тому ми почнемо розгляд наших патернів або способів організації шардинга з деяких найбільш поширених і не найгірших методів.

В якості двох перших можна вибрати наступні.

Як правило, все починається з одного сервера, і є такий абсолютно простий, у тому числі системного адміністрування, метод — «йогурт системних адміністраторів». «Йогурт» — тому що він легкий і корисний.

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

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



Проблема полягає в тому, що вам потрібно весь час подвоюватися, а це буде дуже дорого. Тому треба використовувати щось інше.

Є деяка комбінація, заснована на магічних числах. Я тут написав 48, насправді це лише приклад для ідеї. Чим зручно число 48? Воно ділиться на 12, 6, 4, 3. Ви можете почати з того, що на одному сервері будете тримати 48 схем або 48 таблиць, порізаних спочатку на таке число. Після чого простими для системного адміністратора операціями, дампами ви можете переливати якусь частину даних на інші сервера. При цьому, природно, де-то у вас повинна бути логіка координації, про яку ми ще поговоримо. Ось цей метод — використання якихось спеціальних чисел, які легко діляться — дозволить вам досить легко рости, наприклад, до 48-50 серверів.

Костянтин Осипов: Взагалі, коли ви думаєте про шардинге, потрібно в першу чергу проаналізувати вашу предметну область, тобто що за дані у вас зберігаються.

Даних не може бути гигантски багато. Навіть, якщо говорити про всіх людей на нашій планеті, то це всього лише 7-8 мільярдів. Це не так багато. Припустимо, якщо ми говоримо про всіх рекламних оголошеннях на якому-небудь avito, то це теж мільйони, але це не екстраординарні значення. Тобто у вас є стеля. Будь-яка система зростає, але її зростання сповільнюється в міру того, як вона стає крупніше. Тому не завжди потрібно брати якісь найскладніші рішення, щоб все максимально масштабувати. Якщо ви знаєте, що у вас буде максимум 10 серверів, можливо, вам потрібно просте рішення.

Ще хочу зазначити, що завжди вибір шардінг-формули (на слайді ця формула — ми просто ділимо навпіл) пов'язаний з решардингом.

Олексій Рибак: Яким же чином ми розподіляємо дані між ключами? Поки ми говорили з боку перенесення якихось схем між серверами. Далі виникає питання: а як ми, взагалі, раскидываем дані? Вибрали ключ, розкидали дані по серверам. Тут є два найбільш великих способу.

Перший спосіб — щось схоже на хешування. Воно не обов'язково має бути консистентным, тобто, грубо кажучи, при додаванні нових серверів у вас безліч ключів може дуже сильно перетасоваться (це наступний момент, про який ми поговоримо). У будь-якому випадку, що ви робите? Якщо це числовий ключ, його можна поділити на число серверів, отримати залишок від ділення — і це буде номер вашого сервера. Якщо це строкової ключ, наприклад, e-mail, то від нього можна взяти числовий хеш, далі зробити те ж саме.

Є більш «гаражні» методи — типу вибрати першу літеру логіна, але оскільки ви ніяк не визначаєте розподіл логінов по буквах, ви повинні спочатку врахувати розподіл букв в мові, але це теж досить складно. Більш того, якщо ви покладете одну букву на один сервер, а потім одна буква в один сервер не влізе, то вам треба буде дуже сильно змінювати конфігурацію для того, щоб потім цю літеру розкидати. Дуже погана ідея. Я б сказав, що це антипаттерн.

Позначимо лише одну проблему, яка при хэшировании має місце бути. Це додавання нових серверів. Що у вас відбувається при решардинге з точки зору саппорта? У вас вилітає нода, вам потрібно підняти з реплік майстер-ноду для цієї частини і зробити це максимально швидко. Друге — у вас просто навантаження зросла, вам потрібно докупити нові сервера і максимально швидко ввести їх в дію. Відповідно, решардинг є ключовою проблемою.

Якщо ви просто берете залишок від ділення, то з'являється велика кількість серверів, всі хеші «переразмазываются», всі ключі, всі дані потрібно пересунути. Це дуже важка і погана операція. Вона працює, коли ви тримаєте все в пам'яті.

Наприклад, у нас є кластер memcached в Badoo. Ми розподілили всі по залишку від ділення, додали нових серверів (це відбувається не так часто), і через, може бути, 5-10 хвилин всі дані пересортировались. Все це відбувається досить швидко, без особливих проблем, тому що пересунути дані по мережі і покласти в пам'ять іншої машини — це фігня.

Якщо у вас дані юзерів лежать на диску, наприклад, листування якась тощо, то це значно більш складна річ.

Костянтин Осипов: Є шардінг «для дорослих». І це друга частина нашого доповіді.



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

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

Олексій Рибак: Тут є два принципових моменти, два методу. Ми розглянемо один з них — Table functions.



Це всього лише таблична функція.

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

За великим рахунком, це і є таблична функція і консистентное хешування.

Table functions — це коли у вас просто якийсь config. Використання підходів Table functions до шардингу дуже тісно зав'язані на такому понятті як virtual bucket.

Згадайте, у вас є функція відображення ключа на шард. Уявіть собі, що у вас посередині з'являється якесь проміжне відображення, тобто це відображення перетворюється в два. Спочатку ви отображаете ключ на деякий віртуальний bucket, потім віртуальний bucket — на відповідну координату в просторі вашого кластера.

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

Віртуальні bucket-и, як правило, вибираються в досить великій кількості. Чому вони віртуальні? Тому що насправді вони не відображають реального фізичного сервера. І використовується кілька методів для відображення безпосередньо ключа на шард.

Один метод — це коли перша частина «key to bucket» function — це просто якийсь хеш або консистентный хеш, тобто якась частина, яка визначається за формулою, а bucket безпосередньо на шард відображається через config.

Друга річ, більш складна — коли ви і те, і те отображаете через config. Більш складна, тому що вам, умовно кажучи, для кожного ключа потрібно ще пам'ятати, де він лежить. Ви маєте можливість пересунути будь ключ куди завгодно, але з іншого боку ви втрачаєте можливість легко і швидко, маючи просто маленький config в «bucket to shard», з ключа визначити bucket і потім піти досить швидко піти в потрібне місце.

Костянтин Осипов: Чому ці варіанти, взагалі, виникають? Ми зараз будемо говорити про роутинге і про решардинге. Тут все, в принципі, красиво, зручно, повністю керовано, але у вас з'являється якийсь стан. Цей стан вам потрібно десь зберігати, його потрібно змінювати. У вас збільшилася кількість серверів, вам потрібно поміняти ваші таблиці. Тут є два підходи: перший — ви забиваєте на те, що у вас є стан, намагаєтеся керувати цим станом; другий підхід — ви намагаєтесь максимально математизувати вашу формулу, і тоді у вас максимально детерміновано, без будь-якого стану можна визначити, куди йти при роутинге.

Ось один з підходів, який дозволяє як-то функціонально описати схему шардинга. Це підхід з консистентным хэшированием.



Спочатку розповім, як він влаштований. Ми уявляємо, що весь діапазон нашої хеш-функції не відображається на пряму від 0 до 232 (~ 4 млрд.), а на кільце. Тобто у нас 4 мільярди знаходиться приблизно там же, де 0, ми, як би, зав'язуємо нашу пряму.

Якщо ми просто використовуємо хеш-функцію, ми повинні при додаванні нових вузлів все це перехэшировать. Виходить так, що у нас використовується залишок від ділення на кількість вузлів.

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

Олексій Рибак: Я, коли давно це почув у перший раз, я все одно нічого не зрозумів. Якщо і вам нічого не зрозуміло, не страшно.

Ідея тут така: у консистентном хэшировании при додаванні нових нод ви перетасовываете тільки невелику частину ключів. І все.

Як це зроблено, можете подивитися за відповідними ключовими словами.

Костянтин Осипов: Ще пара слів про недоліки цієї історії з хэшированием. Мова все-таки йде про якихось випадкових величинах. Хеш-функція — це якийсь рандомизатор, він бере ваше природне значення, дає вам рандомное у відповідь на це. Все випадково випадає кудись на кільце. І це не забезпечує в простому випадку ідеального розподілу, тобто у вас може так вийти (див. на картинці), що сервер №3 знаходиться поруч з сервером №1, а між серверами №2 і №3 таке велике півкільце — практично половина даних.

Для того щоб консистентное хешування працювало правильно, ще потрібно додавати певний стан у вигляді віртуальних bucket-ів, таблиць відображення. А віртуальні bucket-и потрібно десь зберігати. Маппінг між віртуальними bucket-ами і серверами. Тобто у вас з'являється стан. Це не чиста математика.

У нас є ще один цікавий слайд з ключовим словом Watermelon/Sumbur:



Ідея Guava — у вас зникає стан, взагалі. В принципі, це функція, яка бере ключ і кількість серверів, а видає вам server_id. Коли ви на це дивитеся, ви розумієте, що насправді шардінг-функція — це саме ось така історія — відображення ключа і кількості серверів на server_id.

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

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

Друга тема, яку ми розбираємо, — це, власне, роутинг, тобто те, яким чином ми можемо шукати потрібні ключі в нашому мегакластере.

Олексій Рибак: насправді це питання про те, яким чином організована архітектура вашого додатки, які компоненти за що відповідають.

За великим рахунком, тут є три найпоширеніших методу.



Ми написали п'ять, але найпоширеніших — три:

  • це «Розумний клієнт»;
  • проксі;
  • координатор
і ще парочка «збочень».

«Розумний клієнт» — це дуже просто.



Уявіть собі, що у вас є таблична функція, яка використовує маппінг ключа на bucket. Використовується хеш, якась формула. Потім у вас є певний config, який складається з невеликої кількості даних, наприклад, 1000 маппингов, 1000 рядків, 1000 відповідностей ключ-значення. В результаті, це все десь зашито в ваш клієнт. Ваш клієнт отримав ключ, відразу визначив, на який сервер йти, та одразу пішов на цей сервер.

В принципі, хороший метод, самий простий і самий кльовий. За одним винятком — в разі, якщо у вас розростається інфраструктура, і вам в якийсь момент потрібно задевелопить купу інших якихось клієнтів, на інших мовах, для інших додатків, то вам потрібно повторити цю логіку — це по-перше. По-друге, якщо вам потрібно зробити якимось чином решардинг, і зробити це з нульовим maintenance subwindow, то це зробити досить складно, тому що вся логіка — в процесах додатків, які зараз працюють. Якимось чином вам треба сигналізувати, що то зараз буде змінюватися, така карта буде ставати іншою і т. д. Все це, загалом, досить складно.

Далі проста історія — це проксі.



Проксі — це программистская мрія.

Костянтин Осипов: В принципі, яка логіка мислення? Ви починаєте з клієнта, потім у вас щось починає виходити, і ви говорите: «Ага, проксі! Давайте цю логіку заберемо з клієнта і винесемо її на проксі».

Олексій Рибак: Є деяка кількість продуктів і підходів, в тому числі в highload-програмуванні (будемо так називати), де йдеться про те, що «Я — девелопер, я не хочу нічого вирішувати, нічого думати. От є у мене об'єкт, я хочу його зберегти. Я б хотів, щоб у мене це працювало одним простим API, і не думати, бо мені ж треба ще робити продукт, а тут якісь складнощі… Мені це не цікаво».

Є деяка кількість рішень, які експлуатують саме ось це бажання девелопера. І проксі, в деякому розумінні, відображає наступну ідею: «ОК, ти працював з однією базою, ти будеш продовжувати працювати з однією базою».

Це, в принципі, не обов'язково. Не кожен проксі повинен відповідати цим умовам.

Уявіть собі, що проксі робить наступне: він приймає запит, ніби до однієї ноде, вірніше, як ніби до одного з додатком, і клієнт просто не знає про те, що насправді за цим проксі є багато нсд.

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

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

Для великих продуктивних систем це є якимось додатковим умовою, яку треба мати на увазі — подвоєння трафіку всередині майданчика.

Костянтин Осипов: Проксі перевантажується. Ви збільшуєте їх кількість. Проксі виходять з ладу, у вас з'являється ще одна точка відмови. Рішення неідеальний, але який ще потенційний профіт у цього рішення? Ви проксі можете також займатися load balancing-му, ви можете дивитися, які ноди у вас вийшли з ладу, тобто автоматично визначати, робити failover повністю прозорим для проксі. Тобто проксі дозволяє зробити логіку програми дуже простий.

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

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



Олексій Рибак: Координатор — це річ, схожа на попередні (тобто клієнт, як і раніше, нічого не знає), але зовсім інша. Координатор — це просто такий класний хлопець, який дуже швидко відповідає на прості запитання «Куди мені йти?». Отримує маленьку порцію запитань, тобто довжина питання невелика, швидко дає відповідь, після цього клієнт сам встановлює з'єднання і йде на потрібну дата-ноду. Тут перевага полягає в тому, що у вас забирається складність проксі.

Сам по собі координатор можна зібрати «на коліні». Це може бути якийсь високопродуктивний сервер з базою даних, спеціальним чином приготований. Може бути спеціалізована база даних. Може бути якась in-memory БД.

Запрограмувати проксі — це дуже трудомістка задача, а координатор запрограмувати — це, умовно кажучи, день роботи.

Ця архітектура володіє певними проблемами. Якщо координатор раптом впаде, то все пропало. Але з іншого боку, координатор — річ вкрай проста і її дуже легко резервувати через асинхронний майстер-майстер, навіть майстер-слэйв.

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

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



Костянтин Осипов: А тут вже мегасложная історія. Припустимо, ви не хочете, щоб у вас були проксі, і хочете, щоб база даних була дуже розумна і сама все роутила. Уявіть собі торренти — це буде дуже схожа аналогія. Тобто нод дуже багато, даних дуже багато. Ви не знаєте стан всього кластера, тому що постійно змінюються ноди. Тоді ви можете використовувати роутинг всередині вашого кластера, всередині самої бази даних.

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

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

Так працює, наприклад, Redis. Вони зробили форвардінг запитів для того, щоб спростити клієнта.

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

Ми підходимо до теми решардинга.



Чому огірочки? Уявіть, що ви упакували все по банках. І тут з'ясовується, що вам потрібно все це переробляти. Ось це приблизна історія про решардинг.

Олексій Рибак: Чому решардинг важливий, ми вже сказали. Насправді ре-шардінг це завжди боляче, тому що потрібно пересувати величезну кількість даних. Можна говорити про те, що це буде аффектить клієнта, мережа. Пересування великих даних — це завжди досить велике вікно — час, на який ми повинні виключити будь-яку частину системи. При цьому клієнти не повинні цього помітити.

Костянтин Осипов: Можна придумати онлайн-решардинг. Це не так страшно, але все одно виникають проблеми з консистентностью даних. Тобто у вас дані якийсь короткий момент часу, який би він не був маленький, живуть на двох вузлах, і вам потрібно на цей маленький момент часу, що називається, не зганьбитися. Один з вузлів може вийти з ладу, а ви можете забути, де це було. Навіть якщо ви — це якийсь великий продукт, ці проблеми так само виникають, як вони вирішуються — ви цього не бачите, це знаходиться «під капотом».

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

Костянтин Осипов: і рухати просто буває неможливо. Якщо у вас одна нода, припустимо, терабайт даних, то додавання нової ноди, куди б ви її не додали, це, в першу чергу, мережа. У вас може просто лягти та стійка, в якій знаходиться ця нода. Тому не завжди решардинг, в принципі, можливий.

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



Олексій Рибак: Отже, ми говоримо про те, що пересувати дані — погано. Які патерни і і принципи можна використовувати для того, щоб дані не пересувати зовсім?

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

Один з підходів — «update is a move». Ідея следющая — завжди, коли ви міняєте будь-той ключ, ви його неявно рухаєте. Припустимо, у вас ключ шардинга — це, власне, ключ шардинга і timestamp. Коли ви міняєте дані, ви міняєте timestamp, і він у вас природним чином виявляється на іншому шарде. Ви можете в якийсь момент закрити апдейти на певний шард і рано чи пізно просто вивести його з ладу. Тобто дуже просто пересувати дані дуже просто виводити дані з ладу.

Таку ідею ми збираємося використовувати в зберіганні поштового індексу в мейл.ру, коли ми індексуємо ті слова, які використовуються в певному e-mail-е. Є юзер, є e-mail (поштову скриньку), і є список слів-ідентифікаторів. Ми з цього будуємо зворотний індекс, тобто у нас шардінг йде по юзеру і за речі, і ми додаємо до цього timestamp.

Коли певним юзерам приходить пошта, ми повинні оновити зворотний індекс, відповідно, оновити певні слова. Вони при цьому можуть переїхати на новий шард. Таким чином, це все може зростати.

Якщо ж у вас великі таблиці, великі об'єкти, звичайно ж, ви не будете рухати їх кожен раз.

Олексій Рибак: Рішення дійсно непогана, але уявити собі, що вам потрібно збирати тепер ці дані, робити пошуковий запит, а ти не можеш піти в якусь одну конкретну ноду… Потрібно робити щось складніше.

Костянтин Осипов: Другий підхід — «data expiration».

Аексей вже розповів про memcached в Badoo. У ньому просто додали кілька серверів, явно не решардили, дані природним чином заэкспайрились — вийшла нова схема шардинга.

Цей же підхід можна використовувати де завгодно, де ви можете старі дані просто видаляти. Тоді ви нові дані ллєте на нові ноди або закриваєте якісь старі ноди. Дані самі собою просто поступово переїжджають.

Олексій Рибак: Тут ключовим моментом є частині — гаряча і холодна. Автоматично з'являються на вашому кластері гаряча і холодна частини, і може виявитися, що якщо ви неправильно підібрали якісь конфігурації або ваги, то гаряча частина буде дуже маленькою, і число серверів, які вам потрібно постійно додавати для того, щоб підтримувати гарячу частину (наприклад, якщо це на twitter або вибори Обами)…

Костянтин Осипов: Була така історія, що в twitter спочатку нові твіти лилися на нові ноди. Коли у них різко зросло навантаження, тому що люди просто стали більше твітити, вони впроваджували один сервер в тиждень, потім знадобилося два сервера в тиждень… В якийсь момент у них адміни просто зашивали, тому що твітти генерувалися дуже активно, і постійно треба було додавати нові сервера — вже пачками. У підсумку вони пішли від цієї схеми і тепер старі твітти зберігають разом з новими.

Олексій Рибак: Холодна частина залишалася досить великий, в результаті дуже велика частина кластера, яка могла б бути використана, просто не використовувалася.

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

Це має сенс особливо для нашого проекту — у нас є певний час життя юзера, тобто він приходить на сайті Badoo і живе там якийсь час — хтось, хто-то півроку. Очевидно, якщо проект живе 10 років, то за цей час було кілька поставок «заліза». Що ми робимо? Ми додаємо нове «залізо», в конфігураторі говоримо, що на старі сервера тимчасово нові дані (нових користувачів) не реєструємо. Нові користувачі починають заповнювати нові машини, у результаті через якийсь час ми бачимо, що навантаження більш-менш зрівнялися. Після цього ми відкриваємо реєстрацію на старі сервера, і таким чином в ручному режимі (не щодня, може бути, раз на місяць, кілька місяців) просто розподіляємо навантаження.

Ми називаємо цей патерн «Нові дані на нові сервера». Насправді, це тимчасово нові дані на нові сервера, потім ви нові дані ллєте скрізь.

Костянтин Осипов: Тема, яку ми не будемо детально розглядати — це наявність схеми та зміни в пошарденных даних. Якісь БД зараз schema-less, але в цілому це окрема серйозна тема, про яку теж варто думати адмінам.

Олексій Рибак: Величезна кількість людей запитують про це — а як зробити так, щоб ви підтримували схему? Велика частина людей каже про те, що вони думають над складно версионированной схемою і т. д.

Тут є дуже простий підхід, який працює майже на всіх завданнях. Перше — потрібно спочатку затюнить вашу програму таким чином, щоб воно працювало і на старій і на нових схемах. Після цього ви апгрейдите базу даних, потім ще раз змінюєте додаток, позбавляючись від мотлоху, від попередньої версії у додатку в БД. Також выпиливаете все, що вам при цьому сказав моніторинг.

Ну, загалом, все.

Питання з залу: Я чув про додавання timestamp-а у зворотний індекс. Незрозуміло — навіщо? Тобто я шукаю якесь слово в своїй пошті, звідки я знаю, коли вона до мене прийшла? Як йти на ноду?

Костянтин Осипов: Timestamp використовується просто для того, щоб це автоматом переїхало. Це використовується в ключі шардинга, але не при пошуку. При пошуку інший індекс, тобто коли робиться пошуковий запит, то не використовується ця частина. Вона використовується, умовно кажучи, при апдейте.

Питання з залу: Але мені індекс потрібен для того, щоб шукати потім. Зворотний.

Олексій Рибак: З індексом все нормально. Питання: де це все лежить? Вся проблема в тому, що не відбувається координації на якусь конкретну ноду. Йде запит паралельно зі всього кластера. Насправді, це вибір між двома архітектурами великого розподіленого пошуку. Це окрема тема.

Один спосіб — це ти намагаєшся все укласти на одну ноду і дістати з неї. Він не працює на великих масштабах.

Інший спосіб — коли ти все «розмазав», з усіх зібрав, потім починаєш релевантність вираховувати, сортувати і віддаєш клієнту.

Питання з залу: Timestamp не є ключем шардинга?

Костянтин Осипов: Ні, не є.

Питання з залу: Newdata — він не сервер. А як це узгоджується з sharding function?

Олексій Рибак: Це узгоджується з sharding function наступним чином. Конкретно для випадку Badoo. Ми не використовуємо жодних формул. Як тільки ви використовуєте формулу, ви не можете пересунути окремого користувача між двома місцями. І у нас постало завдання, де потрібно конкретних користувачів рухати між дата-центрами, для того щоб користувач, який з Європи полетів в Америку, прокинувся вранці і почав користуватися сайтом Badoo швидко, але в новій темі, в новій страуе.

Ми sharding function не використовуємо, у нас все зберігається відповідно один до одного. Це означає, що ви додаєте нові сервера, а ваш код визначає, куди можна реєструвати, отримує при реєстрації ідентифікатор потрібного шарда і заносить ці дані туди.

Я вам розповів, як це зроблено в Badoo. Тепер уявімо собі, що вам потрібно все укласти в один дата-центр. Тоді ви можете використовувати функцію для мапінгу на bucket, а bucket на шард буде маппиться config-му. Ви в цей config можете внести інформацію про те, що на такі-то bucket-и реєстрація заборонена. Ви спочатку розкладаєте цей код, туди ж ви додаєте нові bucket-и, на які дозволена реєстрація, і вони маппятся на нові сервера. Через якийсь час знову розкладаєте цей код.

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

Питання з залу: Був слайд про шардінг на рівні БД, тобто коли база даних сама розуміє, де що лежить, розкладає все… Є якісь успішні кейси реально великих систем, де все це добре працює?

Костянтин Осипов: Кейси є.

По-перше, якщо у вас все-таки не дуже великі ключі і не дуже великі значення, то це може працювати успішно. Якщо у вас не дуже велике додаток, тобто вам потрібно «з коробки», але все-таки на кілька вузлів — на один вузол не уміщається, то ви можете використовувати всі автоматичні системи — і Redis, і Mongo — все, що зараз заявляють, що у них є автоматичний шардінг. Це не означає, що це не працює. Це працює. Воно є Cassandra, Hadoop, Mongo, Redis Cluster. У Tarantool-е скоро буде.

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

Але, в цілому, це тренд і, як і машини з автоматичною коробкою передач — рано чи пізно це буде скрізь.

Олексій Рибак: Це, на жаль, правда. Тому що я представляю девелоперський ком'юніті, яке все це винаходило, робило своїми руками за допомогою бруду і палиць. І ось, через деякий час з'являються якісь продукти, які щось про себе заявляють. Перший час ти думаєш: «Та що ви вмієте? Я вже це все давно минув». А вони дорослішають, після цього ти розумієш, що все це є «з коробки», і ті знання, якими ти мала — вони вже не потрібні, тому що все це вже робиться якимись продуктами.

Я думаю, що у нас є ще кілька років. Поки того, що працює ідеально, в цій сфері немає, але воно дуже скоро з'явиться.

Контакти
kostja
fisher
Блог компанії Mail.ru
Блог компанії Badoo

Ця доповідь — розшифровка одного з кращих виступів на конференції розробників високонавантажених систем HighLoad++. Зараз ми активно готуємо конференцію 2016 року — у цьому році HighLoad++ пройде в Сколково, 7 і 8 листопада.

Костянтин і Олексій — ось уже кілька років у складі Програмного комітету обирають доповіді на HighLoad++. Так що, вся програма — це їхня праця :)

Також деякі з цих матеріалів використовуються нами в навчальному онлайн-курс по розробці високонавантажених систем HighLoad.Guide — це ланцюжок спеціально підібраних листів, статей, матеріалів, відео. Вже зараз у нашому підручнику понад 30 унікальних матеріалів. Підключайтеся!
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.