Шардинг: обратна страна

2.1 Как да разделяте и забавяте N пъти?

Можете да шардите и забавяте точно N пъти по този начин:

• Изпращайте docs00...docs15 заявки последователно , а не паралелно.
• В прости заявки, направете избор не по ключ , WHERE something=234.

В този случай сериализираната част (serial) заема не 1% и не 5%, а около 20% в съвременните бази данни. Можете също така да получите 50% от сериализираната част, ако осъществите достъп до базата данни с помощта на изключително ефективен двоичен протокол or я свържете като динамична библиотека в скрипт на Python.

Останалото време за обработка на обикновена заявка ще бъде заето от непаралелизирани операции за анализиране на заявката, изготвяне на плана и т.н. Тоест нечетенето на записа забавя.

Ако разделим данните на 16 таблици и стартираме последователно, Howто е обичайно в езика за програмиране PHP например (той не е много добър при стартиране на асинхронни процеси), тогава ще получим 16-кратно забавяне. И може би дори повече, защото ще бъдат добавени и двупосочни пътувания в мрежата.

Изведнъж изборът на език за програмиране е важен при шардинга.

Не забравяйте за избора на език за програмиране, защото ако изпращате заявки към базата данни (or сървър за търсене) последователно, тогава откъде идва ускорението? По-скоро ще има забавяне.

2.2 Относно полуавтоматичните

На места сложността на информационните технологии вдъхва хтоничен ужас. Например, MySQL извън кутията със сигурност не е имал внедряване на шардинг към определени версии, но размерите на базите данни, използвани в битката, растат до непрorчни стойности.

Страдащото човечество в лицето на отделните DBA се измъчва от години и пише няколко лоши шардинг решения, базирани на нищо. След това се пише едно повече or по-малко прorчно решение за шардинг, наречено ProxySQL (MariaDB/Spider, PG/pg_shard/Citus, ...). Това е добре известен пример за това петно.

ProxySQL като цяло е, разбира се, пълноценно решение от корпоративен клас за отворен code, за маршрутизиране и др. Но една от задачите за решаване е шардинг за база данни, която сама по себе си не може да шардинг по човешки начин. Виждате ли, няма превключвател „shards = 16“, or трябва да пренапишете всяка заявка в приложението, а има много от тях на места, or да поставите няHowъв междинен слой между приложението и базата данни, който изглежда: „Хм ... ИЗБЕРЕТЕ * ОТ documentи? Да, трябва да се разбие на 16 малки SELECT * FROM server1.document1, SELECT * FROM server2.document2 - към този сървър с такова име / парола, към този с друго. Ако някой не отговори, тогава ..." и т.н. Точно това може да стане чрез междинни петна. Те са малко по-малко, отколкото за всички бази данни. За PostgreSQL, доколкото разбирам,

Конфигурирането на всяка конкретна корекция е отделна огромна тема, която няма да се побере в един доклад, така че ще обсъдим само основните концепции. Нека по-добре да поговорим малко за теорията на шума.

2.3 Абсолютна перфектна автоматизация?

Цялата теория за високо в случай на шардинг в тази буква F() , основният принцип винаги е приблизително един и същ: shard_id = F(object).

Шардинг – за Howво става въпрос? Имаме 2 мorарда записа (or 64). Искаме да ги разделим на няколко части. Възниква неочакван въпрос - How? По Howъв принцип трябва да разпръсна моите 2 мorарда записа (or 64) на 16 достъпни за мен сървъра?

Латентният математик в нас би трябвало да подскаже, че в крайна сметка винаги има няHowва магическа функция, която за всеки document (обект, линия и т.н.) ще определи в кое парче да бъде поставен.

Навлизайки по-дълбоко в математиката, тази функция винаги зависи не само от самия обект (самия ред), но и от външни настройки, като общия брой фрагменти. Функция, която за всеки обект трябва да каже къде да го постави, не може да върне стойност повече от сървърите в системата. И функциите са малко по-различни:

shard_func = F1(object); 
shard_id = F2(shard_func, ...); 
shard_id = F2(F1(object), current_num_shards, ...). 

Но по-нататък няма да копаем в тези дебри от отделни функции, просто ще говорим за това Howви са магическите функции F ().

2.4 Какво представляват F()?

Те могат да измислят много различни и много различни механизми за изпълнение. Примерно резюме:

• F = rand() % nums_shards
• F = somehash(object.id) % num_shards
• F = object.date % num_shards
• F = object.user_id % num_shards
• ...
• F = shard_table [ somehash() |… object.date |… ]

Интересен факт - можете естествено да разпръснете всички данни на случаен принцип - хвърляме следващия запис на произволен сървър, на произволно ядро, в произволна table. Няма да има много щастие в това, но ще работи.

Има малко по-интелигентни методи за сегментиране чрез възпроизводима or дори последователна хеш функция or фрагментиране чрез няHowъв атрибут. Нека да разгледаме всеки метод.

F = ранд()

Разпръскването наоколо не е много правилен метод. Един проблем: разпръснахме нашите 2 мorарда записа на хиляда сървъра произволно и не знаем къде е записът. Трябва да изтеглим user_1, но не знаем къде е той. Отиваме на хиляда сървъра и сортираме всичко - няHow си това е неефективно.

F = somehash()

Нека разпръснем потребителите по възрастен начин: изчислете възпроизводимата хеш функция от user_id, вземете остатъка от делението на броя на сървърите и незабавно се свържете с желания сървър.

Защо правим това? И тогава, че имаме високо натоварване и нищо друго не се побира в един сървър. Ако беше подходящо, животът щеше да е толкова прост.

Страхотно, ситуацията вече се подобри, за да вземем един запис, отиваме на един предварително известен сървър. Но ако имаме диапазон от ключове, тогава в целия този диапазон трябва да преминем през всички стойности на ключовете и в ограничението да отидем or до толкова фрагменти, колкото ключове имаме в диапазона, or дори до всеки сървър. Ситуацията се е подобрила, разбира се, но не за всички заявки. Някои заявки са засегнати.

Естествен шардинг (F = object.date % num_shards)

Понякога, тоест често, 95% от трафика и 95% от натоварването са заявки, които имат няHowъв вид естествено шардинг. Например 95% от условно социално-аналитични заявки засягат данни само за последните 1 ден, 3 дни, 7 дни, а останалите 5% се отнасят за последните няколко години. Но 95% от заявките са естествено разделени по дата, интересът на потребителите на системата е фокусиран върху последните няколко дни.

В този случай можете да разделите данните по дата, например по един ден, и да следвате отговора на заявката за отчет за някой ден or обект от този ден до този шард и да отидете.

Животът се подобрява - сега не само знаем местоположението на определен обект, но също така знаем за обхвата. Ако бъдем помолени не за диапазон от дати, а за набор от други колони, тогава, разбира се, ще трябва да преминем през всички фрагменти. Но според правилата на играта имаме само 5% от тези заявки.

Изглежда, че сме измислor идеално решение за всичко, но има два проблема:

• Това решение е пригодено за конкретен случай, когато 95% от заявките включват само последната седмица.
• Тъй като 95% от заявките засягат последната седмица, всички те ще паднат на един шард, който обслужва тази последна седмица. Този фрагмент ще се стопи, докато всички останали ще бъдат неактивни през това време. В същото време не можете да ги изхвърлите, архивните данни също трябва да се съхраняват.

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

Проблемът се решава чрез лудории, скокове и лапи, тоест увеличаване на броя на репликите за текущия ден на изгаряне, след това постепенно намаляване на броя на репликите, когато този ден стане минало и отиде в архива. Няма идеално решение, наречено „просто трябва да разпределите данните в клъстера с магическа хеш функция по грешен начин“.

2.5 Цена за плащане

Формално, сега знаем, че знаем „всичко“. Вярно е, че не познаваме едно гигантско главоболие и две по-малки главоболия.

1. Проста болка: лошо намазана

Това е пример от учебник, който почти никога не се случва в битка, а изведнъж.

• Като пример с дата, само без дата!
• Непреднамерено неравномерно (забележимо) разпределение.

Те избраха механизма за шардинг и/or данните се промениха и, разбира се, PM не предаде изискванията (нямаме грешки в codeа, PM винаги не съобщава изискванията) и разпространението стана чудовищно неequals. Тоест, изпуснали са критерия.

За да хванете, трябва да погледнете размера на парчетата. Определено ще видим проблема в момента, в който някой от шардовете ни прегрее or стане 100 пъти по-голям от останалите. Можете да го поправите просто като замените ключа or функцията за шардинг.

Това е прост проблем, честно казано, не мисля, че поне един човек от сто ще се сблъска с това в живота, но изведнъж ще помогне поне на някого.

2. "Непобедима" болка: агрегация, присъединяване

Как да направите селекции, които обединяват мorард записа от една table с един мorард записа от друга table?

• Как да изчислим "бързо"... КЪДЕ randcol МЕЖДУ aaa И bbb?
• Как "умно" да направите... users_32shards JOIN posts_1024 shards?

Кратък отговор: няма начин, страдайте!

Ако сте разпределor мorард записа на хиляда сървъра в първата table, така че да работят по-бързо, и сте направor същото във втората table, тогава естествено хиляда до хиляда сървъра трябва да си говорят по двойки. Мorон връзки няма да работят добре. Ако направим заявки към базата данни (търсене, съхранение, съхранение на documentи or разпределена файлова система), които не се вписват добре в шардинга, тези заявки ще се забавят невероятно.

Важен момент е , че някои заявки винаги ще бъдат неуспешно размазани и ще се забавят . Важно е да се опитате да сведете до минимум техния процент. В резултат на това няма нужда да се правят гигантски присъединявания с мorард по мorард записи. Ако е възможно да копирате малка table, спрямо която се присъединявате в гигантска споделена table, към всички възли, трябва да го направите. Ако съединяванията всъщност са локални по няHowъв начин, например, възможно е да поставите потребителя и неговите публикации един до друг, да ги разделите по същия начин и да направите всички съединявания в рамките на една и съща машина - трябва да направите точно това .

Това е отделен курс от лекции за три дни, така че нека да преминем към последната адска болка и различните алгоритми за справяне с нея.

2.6. Сложна/Дълга болка: Повторно споделяне

Пригответе се: ако сте разделor данните си за първи път в живота си, средно ще ги разделите още пет пъти.

Без meaning колко клъстери конфигурирате, все пак трябва да преразпределите.

Ако сте много умен и късметлия, тогава overshard поне веднъж. Но след като сте сигурни, защото в момента, в който смятате, че 10 единици са достатъчни за потребителя, някой точно в този момент пише заявка за 30 и планира да има заявка за 100 единици неизвестни ресурси. Парчетата никога не са достатъчни. С първата схема за шардинг във всеки случай ще пропуснете - винаги ще трябва or да увеличите броя на сървърите, които да добавите, or да направите нещо друго - като цяло, по няHowъв начин да преопаковате данните.

Добре е, ако имаме хубави сor на две: имаше 16 сървърни сегмента, сега са 32. По-забавно е, ако беше 17, това е 23 - две васимално прости числа. Как го правят базите данни, може би имат няHowва магия вътре?

Верният отговор е: не, вътре няма магия, те имат ад вътре.

След това ще разгледаме Howво може да се направи „на ръка“, може би ще разберем „като автоматична машина“.

На челото №1. Преместете всичко

За всички обекти разглеждаме NewF(object), преминаване към нов шард.

Шансът за съвпадение на NewF()=OldF() е малък.

Нека покрием почти всичко.

о

Надявам се, че няма такъв ад, който да прехвърли всичките 2 мorарда записа от стари шардове в нови. Наивният подход е разбираем: имаше 17 машини, 6 машини бяха добавени към клъстера, 2 мorарда записа бяха сортирани, те бяха преместени от 17 машини на 23 машини. Веднъж на всеки 10 години вероятно дори можете да го направите. Но като цяло това е лош ход.

На челото №2. Преместете половината

Следващото наивно подобрение - нека се откажем от такава глупава схема - ще забрани 17 коли да се преразпределят в 23, а ние винаги ще преразпределяме 16 коли в 32 коли! Тогава, според теорията, ще трябва да изместим точно половината от данните, а на практика можем да направим и това.

За всички обекти разглеждаме NewF(object), преминаване към нов шард.

Беше строго 2^N, сега е строго 2^(N+1) фрагмента.

Вероятността за съвпадение на NewF()=OldF() е 0,5.

Нека прехвърлим около 50% от данните.

Оптимално, но работи само за степени на две.

По принцип всичко е наред, с изключение на обвързването на силата на две по отношение на броя на колите. Този наивен подход, колкото и да е странно, може да работи.

Моля, имайте предвид, че допълнителното разделяне на клъстера по степени на две в този случай също е оптимално. Във всеки случай, добавяйки 16 машини към клъстер от 16, ние сме длъжни да изместим половината от данните - точно половината и да изместим.

Добре, но наистина ли човечеството не е измислило нещо друго - въпросът възниква от любознателен ум.

Повече забавление #3. Последователно хеширане

Разбира се, тук е необходима снимка с кръг за последователно хеширане.

Ако търсите в Google „последователно хеширане“, определено ще излезе кръг, всички резултати са попълнени с кръгове.

Идея: нека начертаем идентификатори на шард (хешове) върху кръг и да маркираме хешираните сървърни идентификатори отгоре. Когато трябва да добавите сървър, поставяме нова точка върху кръга и това, което се оказа близо до него (и само това, което се оказа близо до него), преместваме.

Когато добавяме шард: преглеждаме не всичко, а само 2 "съседи", изместваме средно 1/n.

При изтриване на шард: гледаме само изтривания шард, изместваме само него. НяHow оптимално.

Много ефективен по отношение на минимизиране на трафика при добавяне на шард и абсолютно отвратителен по отношение на нормалното балансиране на данни. Защото, когато хешираме всички тези обекти, които разпределяме на голям брой машини, ние го правим сравнително неравномерно: точките около кръга са неравномерно разположени и натоварването на всеки отделен възел може да бъде много различно от останалите.

Този проблем се решава от последния ред на виртуалния възел. Всеки възел, всеки сървър в кръга е обозначен с повече от една точка. Добавяйки сървър, шард и т.н., добавяме няколко точки. Всеки път, когато премахваме нещо, ние съответно премахваме няколко точки и изместваме малка част от данните.

Говоря за това пространство с кръгове, защото например такава схема е вътре в Касандра. Тоест, когато тя започне да преследва записи между възлите, знайте, че кръгът ви гледа и вероятно не одобрява.

Въпреки това, в сравнение с първите методи, животът се подобри - когато добавяме / премахваме фрагмент, вече преглеждаме не всички записи, а само част и преместваме само част.

Внимание, въпросът е: може ли да се подобри допълнително? И също така да се подобри равномерността на зареждането на фрагменти? Казват, че е възможно!

Повече забавление #4. Рандеву/HRW

Следващата проста идея (материалът е образователен, така че нищо сложно): shard_id = arg max hash(object_id, shard_id).

Защо се нарича Хеширане на Rendezvous, не знам, но знам защо се нарича Най-голямо произволно тегло. Много е лесно да си го представите така:

Имаме например 16 шарда. За всеки обект (низ), който трябва да бъде поставен някъде, изчисляваме 16 хеша в зависимост от обекта от номера на шарда. Който има най-висока хеш стойност, печели.

Това е така нареченото хеширане на HRW, известно още като хеширане на Rendezvous. Тъпа като пръчка, схемата за изчисляване на броя на парчетата, първо, е по-лесна за окото от кръговете и дава равномерно натоварване, от друга страна.

Единственият минус е, че добавянето на нов шард се влоши за нас. Има риск при добавяне на нов шард все още да имаме някои хешове, които ще се променят и може да се наложи да прегледаме всичко. Технологията за премахване на фрагменти не се е променила много.

Друг проблем е, че е изчислително тежък с голям брой фрагменти.

По-забавно #5. Още техники

Интересното е, че изследванията не стоят неподвижни и всяка година Google публикува някои нови космически технологии:

• Jump Hash – Google '2014.
• Multi Probe—Google '2015.
• Maglev-Google '2016.

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

заключения

Има важна основна техника, наречена шардинг, кръстена на Галий Юлий Цезар: „Разделяй и владей, владей и разделяй!“. Ако данните не се побират в един сървър, е необходимо да ги разделите на 20 сървъра.

След като научи всичко това, човек трябва да остане с впечатлението, че би било по-добре да не се шарди. Ако решите, че е по-добре да не шардите, това е правилното усещане. Ако можете да добавите памет към сървъра за $100 и да не разбивате нищо, тогава трябва да го направите. При шардинг ще се появи сложна разпределена система с прехвърляне на данни напред и назад, натрупване на данни в никой не знае къде. Ако може да се избегне, трябва да се избегне.

По-добре е да не го правите на ръка, по-добре е „базата“ (търсене, DFS, ...) да може сама да се раздели. Във всеки случай рано or късно ще дойде високо натоварване и по няHowъв начин данните ще трябва да бъдат разделени. Не е факт, че дори ако базата може да се справи сама, няма да срещнете ниHowви проблеми. Не забравяйте за алгоритмичния фундаментализъм - трябва да разберете How работи всичко вътре.

Когато настройвате шардинг за първи път, изберете внимателно F(), помислете за заявки, мрежа и т.н. Но се пригответе, вероятно ще трябва да избирате 2 пъти и поне веднъж ще трябва да повторите всичко.