CAP-теорема простым русским языком

Вольный перевод поста Kaushik Sathupadi: A plain english introduction to CAP Theorem.

Часто можно услышать, что существует теоретический предел, который невозможно преодолеть при построении распределенных систем: CAP-теорема, которая утверждает, что система не может одновременно достичь согласованности данных (консистентности, Consistency), доступности (Availability) и устойчивости к разделению (Partition tolerance). Попробуем проиллюстрировать это примером из нашей обычной жизни.

Глава 1. Ваш новый бизнес ООО "Запоминайка"

Вчера, когда Ваша жена была искренне рада тому, что вы не забыли о ее дне рождения и сделали ей чудесный подарок, Вам в голову внезапно пришла интересная идея: люди так плохо умеют запоминать различные вещи, а у Вас-то это так легеко получается. Почему бы не организовать компанию, в которой Вы бы могли полностью раскрыть свой талант? Чем больше вы думаете о новом предприятии, тем больше оно Вам нравится. В конце концов вы даете объявление в местную газету:

ООО "Запоминайка"! Никогда ни о чем не забывайте, даже ничего не запоминая!

Было ли вам неудобно от того, что Вы что-то забыли? Позвоните нам и мы поможем!

Когда вам надо что-то запомнить, просто позвоните нам по бесплатному номеру 8-(800)-200-10-20 и скажите, что необходимо запомнить. Например, позвоните нам и продиктуйте телефонный номер вашего начальника. Теперь Вам нет необходимости запоминать его самостоятельно, просто когда он Вам понадобится снова, позвоните нам по номеру 8-(800)-200-10-20 и мы вам подскажем телефонный номер вашего начальника. Стоимость: 3 рубля за запрос.

Ваш диалог с клиентом звучал бы примерно следующим образом:

  • Клиент: Добрый день, вы можете запомнить день рождения моего соседа?
  • Вы: Конечно, когда у него день рождения?
  • Клиент: Второго января.
  • Вы (записывая дату на страничке этого клиента в Вашей записной книжке): Записано. Теперь Вы можете позвонить нам в любой момент и мы напомним Вам, когда день рождения у Вашего соседа.
  • Клиент: Спасибо!
  • Вы: Пожалуйста, мы списали с Вашей карточки 3 рубля за услугу.

Глава 2. Бизнес растет

Ваша компания получила инвестиции от Мильнера. Это будет отличный бизнес - вам всего-то и нужны записная книжка и телефон, а от клиентов нет отбоя: вы отвечаете на сотни звонок каждый день.

И тут появляется первая проблема: все больше и больше клиентов висит на линии в ожидании разговора, они плюют и вешают трубку, так и не дождавшись ответа. Кроме того на той неделе Вы заболели и не могли отвечать на звонки целый день - страшно даже подумать о чувствах тех клиентов, которые не могли получить доступ к своей информации в течение всего этого дня.

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

Сам собой вырисовывается простой план:

  1. У Вас с женой будут отдельные телефоны.
  2. Клиенты будут так же как и раньше звонить по телефону 8-(800)-200-10-20, им надо запомнить всего один номер.
  3. Офисная АТС будет направлять звонки по очереди на Ваш телефон и телефон Вашей жены с учетом занятости линии.

Глава 3. Первый сбой

Через два дня после того как заработала ваша новая система с двумя телефонами, Вам звонит Ваш постоянный клиент Петр. Вот какой диалог происходит между вами:

  • Петр: Доброе утро!
  • Вы: Спасибо за звонок в ООО "Запоминайка". Чем могу помочь?
  • Петр: Скажите пожалуйста, во сколько у меня рейс в Одессу?
  • Вы: Одну минуту. (Вы ищете в блокноте... Странно, но на странице Петра нет информации о времени вылета)
  • Вы: Думаю, произошла ошибка. Но вы не просили запомнить время вылета в Одессу.
  • Петр: Как? Я ведь звонил вам вчера! (Бросает трубку)

Как такое могло случиться? Разве Петр может обманывать? Вы задумываетесь над этим и тут же понимаете, как такое могло произойти. Может быть, на вчерашиний звонок Петра ответила Ваша жена? Вы идете к столу Вашей жены и проглядываете ее записную книжку. Конечно, так и есть, в нем есть запись о времени вылета. Вы рассказываете это жене и она тоже осознает проблему.

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

Глава 4. Решение проблемы несогласованности

Может быть, Ваши конкуренты могут смириться со сбоями в работе, но Вы-то не такой. Всю ночь, пока Ваша жена спит, Вы думаете над решением проблемы, и к утру Вам в голову приходит отличная идея. Вы будите жену и говорите ей: "Дорогая, с сегодняшнего дня мы будем действовать следующим образом":

  • Когда нам звонит клиент с новой информацией (он хочет, чтобы мы что-то запомнили), до того как мы вешаем трубку, мы сообщаем новую информацию друг другу.
  • Таком образом, каждый из нас записывает всю поступающую информацию.
  • Когда же нам звонят за информацией (просят что-то напомнить), на нет необходимости уточнять что-либо друг у друга: так как у нас обоих записана вся информация и все изменения, нам достаточно заглянуть в свою записную книжку.

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

- Классно, - говорит Ваша жена, - но есть одна ситуация, о которой ты не подумал: что если кто-то из нас не сможет выйти на работу? В такой день мы не сможем принять ни одного звонка от клиентов, которые хотят что-то запомнить, так как мы не сможем передать новую информацию другому. И у нас будет проблема доступности: если мне позвонит клиент, который попросит что-то запомнить, я не смогу завершить звонок, потому что даже после того, как я запишу все в своей записной книжке, я не могу передать эту информацию тебе. Таким образом, я не смогу обслужить этот звонок.

Глава 5. Вам в голову приходит самое классное решение

Только сейчас Вы начинаете понимать, что создать распределенную систему не так просто, как кажется вначале. Так ли сложно придумать решение, которое будет одновременно согласованным по данным и доступным? Может, для кого-то это сложно, но не для Вас! На следующее утро у Вас есть такое решение, о котором Ваши конкуренты и не мечтают! Вы снова будите жену и начинаете ей взахлеб рассказывать свою идею:

- Слушай, - говорите Вы, - вот что нам надо сделать, чтобы быть одновременно согласованными и доступными. Это очень похоже на то, что я рассказывал тебе вчера:

  • Когда нам звонит клиент с новой информацией (он хочет, чтобы мы что-то запомнили), если мы оба на работе, мы тут же сообщаем новую информацию друг другу.
  • Если кто-то из нас сегодня не работает, мы отправляем другу письмо по электронной почте с обновленной информацией.
  • Когда кто-то из нас выходит на работу после отгула, он первым делом просматривает почту, вносит все изменения в свою записную книжку. Все этого надо сделать до того, как поступит первый звонок от клиента.

- Ты гений! - отвечает Вам жена. - Я не вижу к чему можно было бы придраться в такой схеме. ООО "Запоминайка" теперь одновременно согласованная по данным и доступная!

Глава 6. Ваша жена обижается

Все было хорошо до поры до времени. Ваша система согласована по данным. Ваша система доступна даже тогда, когда кто-то из вас не вышел на работу. Но что если вы одновременно не придете на работу? А если кто-то из вас не передаст обновленную информацию другому? Сколько раз Вы будили рано утром свою жену, чтобы рассказать ей свою новую дурацкую идею? Что если Ваша жена примет звонок, но из-за того, что злится на Вас, решит не передавать Вам новую информацию целый день? Вся ваша система развалится! Ваша система хороша с точки зрения согласованности и доступности, но не проходит проверку на устойчивость к разделению!

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

Глава 7. Заключение

Давайте теперь рассмотрим CAP-теорему: она утверждает, вы при создании распределенной системы Вы не можете достичь одновременно согласованности по данным, доступности и устойчивости к разделению:

  • Согласованность по данным (Consistency): Клиент уверен, что если он сделал звонок и попросил запомнить информацию, при следующем звонке он получит актуальный ответ независимо от того, когда он позвонит, сразу же или через некоторое время.
  • Доступность (Availability): ООО "Запоминайка" сможет отвечать на звонки, если хотя бы один из вас пришел на работу.
  • Устойчивость к разделению (Partition tolerance): ООО "Запоминайка" будет корректно работать даже если вы перестали общаться со своей женой!

Дополнение: согласованность в конечном счете с помощью секретаря "на побегушках"

Вот над чем еще можно подумать: вы можете нанять секретаря "на побегушках", который будет обновлять ваши записные книжки, как только в одной из них появляются изменения. Самое большое преимущество данного подхода заключается в том, что он может работать не отвлекая вас с женой от приема звонков, а для успешного завершения звонка с изменением информации достаточно записать ее в свою записную книжку. Так работают многие NoSQL системы, в которых узел запоминает изменения локально и потом с помощью фонового процесса синхронизирует их с другими узлами. Единственной проблемой является то, что время от времени согласованность будет пропадать. Например, если звонок клиента будет перенаправлен Вашей жене раньше, чем секретарь сможет перенести изменения из Вашей записной книжки в ее книжку, клиент получит несогласованный ответ. Хотя может это и не так плохо, если такие случаи редки. Может быть, можно предположить, что клиент не забывает все так быстро и не перезванивает раньше, чем через 5 минут.

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

Комментарии

Comments powered by Disqus
Contents © 2015 Andrey - Powered by Nikola