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

В процессе разговора собеседник обмолвился про CAP-теорему. Мол, есть такое правило, которое в работе с распределенными системами имеет место. Я обещал почитать подробней.

И вот с тех пор у меня в Trello на доске "Прочитать" лежала карточка с этой CAP-теоремой и кучей ссылок на толстые книги. А сегодня я посмотрел доклад Романа Гребенникова про кубернетес. А потом про распределенные системы. И там, в хабр-версии этого второго доклада я нашел очень лаконичное объяснение. Далее буду цитировать:

Начало цитаты

CAP-теорема

CAP-теорема – это краеугольный камень проектирования распределённых систем. Это теорема, которая формально не теорема, а эмпирическое правило, но все её называют теоремой.

Звучит она следующим образом. У нас есть три кита создания распределённых систем. Это целостность, доступность и устойчивость к сетевым проблемам. У нас есть три кита, мы можем выбрать любые два. Причем не совсем любые два, почти любые два. Чуть позже мы об этом поговорим.

По порядку — что такое целостность, доступность и устойчивость. Это же вроде теорема, должны быть формальные описания.

Доступность

Это доступность (availability), и она подразумевает под собой постоянную доступность. Каждый запрос к системе, любой запрос к системе к любому живому узлу должен быть успешно обработан. То есть если мы часть запросов куда-то на потом откладываем, либо мы записи в сторонку откладываем, потому что у нас что-то пошло не так — это непостоянная доступность. Если не все узлы отвечают на запросы, или не на все запросы все узлы отвечают — это тоже непостоянная доступность с точки зрения CAP-теоремы.

Если оно у вас отвечает вот так:

preview

Это тоже непостоянная доступность.

Целостность

Следующий пункт — это целостность. С точки зрения целостности вы можете сказать, что существует вот столько разных типов целостности в распределённых системах:

preview

Их порядка 50-ти. Какой их из них в CAP-теореме?

В CAP-теореме самый строгий тип. Называется линеаризуемость.

Целостность, линеаризуемость. Звучит очень просто, но под собой имеет большие последствия. Если операция B началась после операции A, то B должна увидеть систему на момент окончания A или в более новом состоянии. То есть если A завершилась, то следующая операция не может видеть то, что было до A. Вроде бы всё логично, ничего сложного нет. Если переформулировать это другими словами: «Существует непротиворечивая история последовательных операций».

Тут пропускаю много всего про линеаризуемость, см. оригинальную статью

Устойчивость

Последний пункт — это буква P. Partition tolerance, по-русски можно сказать, что это «устойчивость к сбоям в сети». Выглядит она следующим образом:

preview

Представим, что у вас есть несколько серверов, и рано утром тут проехал экскаватор и перерубил между ними провода. У вас есть два выхода, если ваш кластер развалился пополам. Первый выход: большая половинка живет, а меньшая отвалилась. Вы потеряли доступность, потому что меньшая отвалилась. Зато большая живет. Зато не потеряли целостность. Либо работают обе половинки, мы и тут и там принимаем записи, всё принимаем, всё хорошо. Только потом, когда провод спаяют, мы поймем, что у нас была одна система, а стало две, и они живут своей жизнью.

С точки зрения CAP-теоремы у нас есть три возможных подхода к проектированию системы. Это системы CP / AP / AC в зависимости от двух комбинаций из трёх.

С AC-системами есть проблема. С одной стороны, они гарантируют, что у нас есть высокая доступность и целостность. Всё классно, пока у нас не поломалась сеть. А поскольку такое часто бывает, в реальном мире AC-системы можно использовать, но только если вы понимаете те компромиссы, на которые вы идёте, когда вы используете AC-системы.

В реальном мире есть два выхода. Вы можете либо сместиться в целостности и потерять доступность, либо сместиться к доступности, но потерять целостность. Третьего не дано.

В реальной жизни есть много алгоритмов, которые реализуют различные системы CP / AP / AC. Двухфазный коммит, Paxos, кворум и прочие рафты, Gossip и прочие кучи алгоритмов.

Конец цитаты


Comments

comments powered by Disqus