CAP Theorem
Знаменитой CAP теореме исполнилось 25 лет, поэтому хотелось что это такое, зачем она и как появилась. Про это есть отличная статья от Eric Brewer, автора теоремы, который написал ее больше 10 лет назад, которую хотелось вспомнить, так как она хороша:) Начнем с самого утверждения теоремы (цитата из статьи выше)
The CAP theorem states that any networked shared-data system can have at most two of three desirable properties:
- consistency (C) equivalent to having a single up-to-date copy of the data;
- high availability (A) of that data (for updates); and
- tolerance to network partitions (P). Дальше надо вспомнить про ее появление
- 25 лет назад, осенью 1998 года была сформулирована CAP теорема
- в 1999 году она была опубликована в статье "Harvest, Yield, and Scalable Tolerant Systems" в ACM
- в 2000 представлена на Симпоузиуме "Symposium on Principles of Distributed Computing" (презентация здесь)
- в 2002 доказана формально (где консистентность из теоремы превратилась в линеаризуемость) Потом теорема пошла в массы и превратилась в условные "выберите 2 свойства из трех: C, A, P", что является сильным упрощением по трем причинам, что указывает Эрик в уже упоминавшейся статье:
- Из-за редкости partition нет смысла выбирать между C и A (про это подробнее в следующий раз при обсуждении PACELC Theorem)
- Решение о C или A принимается не единоразово для всех компонентов и всех данных, а на другом уровне гранулярности и может зависеть от типа операции или данных
- C, A, P - это не бинарные свойства, а скорее непрерывные - availability от 0 до 100%, уровни консистентности тоже бывают разные и даже partitions имеют нюансы:)
В итоге, Эрик говорит о том, что в отсутствии разделения системы мы можем выбирать A или C, а во время проблем у нас должен быть понятный алгоритм
- определения, что случился partition
- перехода в явный partition режим, в котором часть операций может быть лимитирована
- запуска процесса восстановления консистентности и компенсации ошибок, что возможно были в рамках partition
Потом Эрик рассказывает про связь акронимов ACID, BASE и CAP
- BASE расшифровывается как Basic Availability, Soft state и Eventually consistency. Первые два из свойств помогают достигать доступности при разделении системы на части
- ACID расшифровывается как Atomicity, Consistency, Isolation, Durability. Этот акроним знают многие, кто работал с реляционными базами данных, но как я писал выше Consistency из CAP и из ACID - это про разное и это добавляет сложности в понимании:)
Следом идет часть про latency, которая отсутствует в классической формулировке, но неявно присутствует. Ведь выполняя операцию в разделенной системе, мы в какой-то момент должны принять решение
- отменить операцию и уменьшить доступность
- продолжить операцию, но принять риск неконсистентности данных
Конечно можно попробовать повторно выполнить операцию (retries), но это просто откладывает принятие решение на некоторое время. Таким образом, с прагматической точки зрения разделение — это ограничение по времени (таймаут), который мы закладываем в свое общение. А из этого следует несколько последствий
- Не существует глобального понятия partition, поскольку некоторые узлы могут обнаружить partition, а другие — нет.
- Те узлы, что обнаружили partition входят в режим partition-mode, собственно ту часть, где нам надо выбирать между C и A В итоге, проектировщики системы выставляют time bounds так, чтобы соответствовать целевым скоростям ответа системы на запросы, а чем жестче эти time bounds, тем выше вероятность попадания в partition mode, причем даже просто при медленной сети, но без реального ее разделения.
В приведенной выше статье есть еще много интересных мыслей про scope консистентности и как это соотносится с датацентрами, как явно управлять процессами перехода в partition mode и восстанавливаться после partition. Очень рекомендую ее к прочтению.
#Software #Architecture #DistributedSystems #SystemDesign