Репликация, шардинг и CAP
Накратко: Репликацията пази копия на данните на няколко сървъра, шардингът дели данните между тях, а CAP казва какво губиш, когато мрежата се раздели.
Проблем
Един сървър за целия магазин
Магазинът расте. В петък вечер каталогът се отваря 20 000 пъти в минута, и почти всичко е четене: продукти, цени, наличност. Базата е на един сървър, а процесорът му е на 100%. В нощта срещу събота дискът му отказва, и до сутринта магазинът не работи.
Една машина е и таван на скоростта, и единствената точка, в която всичко може да спре. Трябват още машини с копия на данните.
Идеята
Лидер и последователи
Репликация значи едни и същи данни да се пазят на няколко сървъра (възли). Най-честата схема е с лидер (leader, в PostgreSQL primary): само той приема записи. Останалите възли са последователи (followers, реплики). Те получават всеки запис от лидера и го прилагат при себе си. Четенето може да отиде при всеки възел, затова три възела поемат три пъти повече четене.
Полето е симулатор на клъстер от три възела, а лидерът е A. Наличността на сиренето (продукт 7) е 18 и е на трите. Времето в симулатора стои: записът тръгва от лидера и стига до последователите на следващия tick. Всяка стойност има версия (v1, v2), за да се вижда кое копие е по-ново. Под изхода е картината: възлите, копията им и какво още пътува.
write на A връща OK веднага: лидерът е записал при себе си и не чака никого. Това е асинхронна репликация. Докато записът пътува, B още казва 18. Това закъснение е изоставането на репликата (replication lag). Обикновено е милисекунди, а при натоварване стига до секунди.
По-точно, за любопитните
Командите write, read, tick и останалите в урока са на симулатора, а не на конкретна база. tick придвижва часовника му с един такт, а в истинската база репликацията тече непрекъснато. PostgreSQL прави същото със streaming replication: лидерът праща на последователите дневника на промените си (WAL), а те го прилагат поред. MySQL праща своя binary log. И в двете репликацията по подразбиране е асинхронна, а последователите приемат само четене.
Пробвай
Смених града, а страницата показва стария
Симона (клиент 17) се мести от Русе в Пловдив. Записва новия град в профила си, а страницата, която се отваря след това, пак казва Русе:
Записът е минал, но страницата е чела от B, а B още не го е получил. Другите клиенти ще видят новия град след миг, и за тях това е без значение. На Симона ѝ изглежда, че промяната се е изгубила, и тя я пише пак. Тук трябва гаранцията четене на собствените записи (read-your-writes): който е писал, вижда своя запис. Честото решение е известно време след промяна (например минута) четенията на този клиент да отиват при лидера. Същото остаряло копие видя при кеша в урока за key-value.
Запиши новия град на Симона и го прочети веднага така, че тя да види Пловдив.
Решение
write customer:17:city = Пловдив on A
read customer:17:city from A
read customer:17:city from A: лидерът има всеки потвърден запис. tick и после четене от B също показва Пловдив, но в истинската база не знаеш колко време трябва да чакаш. Четене от B или C веднага след записа дава Русе.
Идеята
Синхронна репликация и цената ѝ
Ако лидерът падне, преди записът да стигне до последователите, записът е само при него. Затова може да го накараш да чака. При синхронна репликация лидерът казва OK чак когато последователите потвърдят, че имат записа. Тогава потвърденият запис е на всеки възел.
Цената е двойна. Всеки запис чака най-бавния последовател, а между два центъра за данни това са милисекунди при всеки запис. И един паднал последовател спира всички записи, защото лидерът няма от кого да получи потвърждение. Затова на практика се смесват: един последовател е синхронен, а другите са асинхронни. Ако синхронният падне, друг заема мястото му.
По-точно, за любопитните
В PostgreSQL синхронните последователи се задават с synchronous_standby_names. FIRST 1 (b, c) чака първия наличен от списъка, а ANY 1 (b, c) чака който и да е от двата. Ако няма кой да потвърди, транзакцията виси, докато не се появи последовател или не се смени настройката. Симулаторът не виси: отказва записа веднага и казва защо. MySQL има полусинхронна репликация: лидерът чака поне един последовател да потвърди, че е получил записа.
Виж го
Лидерът пада
Репликацията е асинхронна. Клиент купува сирене, A намалява наличността на 17 и казва OK. Миг след това A спира, преди записът да тръгне:
B и C са последователи и не приемат записи, затова магазинът стои, докато няма нов лидер. elect избира измежду възлите, които се виждат помежду си, този с най-новите данни. Трябват поне два от трите, тоест мнозинство. Всеки избор има номер (мандат, term). Новият лидер е с мандат 2, и старият, когато се върне, разбира, че вече не е лидер. Смяната на лидера се казва failover.
Но B никога не е получил 17. Потвърдената продажба изчезва: A я маха, когато се връща, защото новият лидер не я има. Това е капанът на асинхронната репликация: при failover последните потвърдени записи може да се загубят. При синхронна репликация B щеше да я има.
По-точно, за любопитните
MongoDB сменя лидера (primary) сама: ако последователите не го чуват 10 секунди (по подразбиране), гласуват, и печели възел с мнозинство от гласовете. Записите на стария primary, които не са стигнали до мнозинството, се връщат назад (rollback), когато той се присъедини. Затова важните записи се пращат с writeConcern: { w: "majority" }: потвърждават се чак когато са при мнозинството. PostgreSQL сам не сменя лидера. Това го правят външни инструменти като Patroni, а ръчно последовател става лидер с pg_promote(). В симулатора изборът също е ръчен (elect).
Идеята
Мрежата се разделя: CAP и кворуми
Паднал сървър поне се разпознава. По-коварно е, когато всички работят, но не се виждат, например прекъсната връзка между два центъра за данни. Това е разделяне на мрежата (network partition). Възелът от другата страна не знае дали другите са паднали, или само не ги чува.
Тук е полезна друга схема, без лидер. Всеки възел приема записи и ги праща на другите. Записът чака W потвърждения, а четенето пита R възела и взима най-новата версия. Ако възлите са N и W + R > N, всяко четене пита поне един възел, който има последния запис. Това е кворум. При N = 3, W = 2 и R = 2 записът и четенето винаги се срещат в поне един възел:
При W = 1 и R = 1 четенето от C пита само C, а той още няма новия запис. При W = 2 и R = 2 C пита и A и взима v3.
Сега прекъсването: C е отрязан от A и B.
A и B са мнозинство и продължават. C не стига до двама и отказва и четенето, и записа: по-добре никакъв отговор, отколкото грешен. С W = 1 и R = 1 C отговаря, но казва 18, а истината е 17.
Това е CAP, казано точно. Докато мрежата е разделена (P, partition), възелът избира. Или отказва, за да не върне стара стойност и да не приеме запис, за който другите не знаят (консистентност, C). Или отговаря с каквото има (наличност, A, availability). И двете наведнъж не може. CAP не значи „избери две от трите“: разделянето не се избира, то се случва. Без разделяне изборът е друг, и това казва PACELC: иначе (E, else) базата избира между закъснение (L, latency) и консистентност (C), защото синхронната репликация и кворумът чакат при всеки запис.
По-точно, за любопитните
Идеята за кворумите е от статията на Amazon за Dynamo (2007). Cassandra я следва: всяка заявка казва колко възела трябват (ONE, QUORUM, ALL). Версиите там са времена, и при конфликт печели по-новият запис (last write wins). Симулаторът брои версиите с брояч. DynamoDB по подразбиране чете eventually consistent, тоест може да върне стара стойност, а с ConsistentRead чете консистентно. Консистентността в CAP е друго нещо от C в ACID. В CAP значи, че всяко четене вижда последния потвърден запис, сякаш копието е едно. В ACID значи, че правилата на базата са спазени. CAP е формулирана от Eric Brewer през 2000 г. и доказана от Gilbert и Lynch през 2002 г.
Идеята
Шардинг: всеки възел със своята част
Репликацията умножава четенето, но всеки запис пак стига до всеки възел, и всеки възел пази всичко. Когато данните или записите не се побират на една машина, ги делиш: всеки възел пази своя част. Частта се казва шард (shard), а деленето шардинг. Кой ред на кой шард е, решава ключът на шардинга, обикновено колона като номера на клиента.
По диапазон: клиенти от 1 до 7 на A, от 8 до 14 на B, от 15 нагоре на C. where казва на кой възел е клиентът, а query кои шардове трябва да пита заявката:
Заявка по съседни номера пита само два шарда. Но всеки нов клиент е с по-голям номер и отива на C. Всички регистрации днес удрят един възел, а A и B почиват. Това е горещ шард (hot spot).
По хеш: от ключа се смята число, и то казва шарда. В симулатора хешът е остатъкът при деление на 3:
Новите клиенти отиват поред на A, B и C. Цената е, че заявка по диапазон вече пита всички шардове, защото съседните номера са разпръснати.
А ако ключът е градът? Заявката „клиентите от София“ ще пита един шард. Но всички от София са на едно място:
A има 9 от 20 клиента: шестимата от София, най-големия град, и още Бургас и клиентът без град. С клиентите отиват и поръчките им, и натоварването. Шардът не може и да се раздели: всички от София имат един и същ ключ. А заявка по номер вече пита всички шардове. Добрият ключ има много различни стойности и разпределя равномерно и данните, и натоварването.
И още нещо: таблица, разделена на шардове, вече не е на едно място. JOIN на клиент с поръчките му е бърз, само ако те са на един шард. Затова поръчките обикновено се шардират по номера на клиента, като самия клиент. Транзакция, която пише на два шарда, иска разпределена транзакция (two-phase commit). Тя е по-бавна, а ако координаторът ѝ падне по средата, шардовете чакат.
По-точно, за любопитните
В симулатора трите възела са или копия, или шардове. В истинската база всеки шард е отделна група от копия. В MongoDB всеки шард е replica set, а рутер (mongos) праща заявката към шарда по ключа. MongoDB шардира по диапазон или по хеш, а парче от данните с една-единствена стойност на ключа, което е твърде голямо, не може да се раздели (jumbo chunk). Cassandra хешира ключа с Murmur3 и подрежда възлите в кръг (consistent hashing): нов възел поема част от ключовете, без да размества всички. Остатъкът при деление на 3 в симулатора не е такъв: при четвърти възел почти всеки клиент сменя шарда си. „Хешът“ на града в симулатора е номерът на града в списък. За PostgreSQL шардинг дава разширението Citus, а за MySQL Vitess.
Упражнение
Авария, кворум и нови клиенти
1. Наличността на сиренето е 18 и е на трите възела. Лидерът A пада, а дискът му е за смяна.
A няма да се върне скоро. Направи така, че клъстерът пак да приема записи, и запиши новата наличност на сиренето: 17.
Решение
elect
write stock:7 = 17 on B
elect, после write stock:7 = 17 on B. B и C имат еднакви данни, а при равенство симулаторът избира първия по име. Без избор B отказва записа, защото е последовател. start A не е изход: A няма да се върне.
2. Клъстерът е без лидер, с три възела.
Избери W и R така, че четене от който и да е възел веднага след запис да вижда новата стойност и записите да минават и когато един възел е паднал.
Решение
quorum write 2 read 2
quorum write 2 read 2. 2 + 2 > 3, затова четенето винаги среща възел с последния запис. Когато един възел е паднал, остават два, и стигат и за W, и за R. При W = 3 записът спира с първия паднал възел. При W + R ≤ 3 четенето може да не намери новия запис, а при R = 3 спира четенето.
3. Магазинът пуска реклама и очаква стотици нови клиенти с номера 21, 22, 23 и нагоре.
Избери ключа на шардинга на клиентите така, че новите клиенти да се разпределят по трите възела, а не да отиват на един.
Решение
shard customers by id hash
shard customers by id hash. При диапазон всички нови номера са над 15 и отиват на C. При града новите клиенти от София пак биха отишли на един шард, а симулаторът дори не знае градовете им.
Идеята
Кога какво
- Репликация трябва почти винаги: копие на друга машина пази от авария, а последователите поемат четенето. Асинхронната е по подразбиране. Ако загубата на последните записи е недопустима (плащания), поне един последовател е синхронен.
- Четене от последовател е добро за каталога, отчетите и търсенето. Не е добро за това, което клиентът току-що е променил: тогава чете лидерът.
- Шардинг е последната стъпка, не първата. По-голяма машина, индекси, кеш като Redis и реплики за четене стигат на повечето магазини. Шардингът усложнява всяка заявка и транзакция, която минава през шардове.
- CAP се решава за всяка операция поотделно. Наличността на склада и плащането искат консистентност. Количката и „последно разгледани“ могат да са налични и малко остарели.
По-точно, за любопитните
Три възела са най-малкият клъстер, който сам сменя лидера: при два възела всеки, останал сам, не е мнозинство. Затова MongoDB препоръчва нечетен брой гласуващи в replica set. Google Spanner и CockroachDB правят транзакции между шардове с алгоритми за съгласие (Paxos в Spanner, Raft в CockroachDB). Цената е закъснение при всеки запис, и това е PACELC на практика.
Тест