Consistency Tradeoffs in Modern Distributed Database System Design (или whitepaper про PACELC)

Продолжая серию постов про консистентность (CAP теорема, ее доказательство), я расскажу про whitepaper 2012 года от Daniel J. Abadi с расширением CAP теоремы до PACELC (читается как [pass-elk]). Суть этой статьи звучит так

The CAP theorem’s impact on modern distributed database system design is more limited than is often perceived. Another tradeoff—between consistency and latency—has had a more direct influence on several well-known DDBSs. A proposed new formulation, PACELC, unifies this tradeoff with CAP.

Фокус CAP теоремы на поведении распределенной системы во время разделения сети. Но большую часть времени система работает в состоянии, когда с сетью все в порядке. Поэтому интересно оценить а какоой tradeoff в этом случае. И это оказывается треугольник "consistency, availability, and latency", который автор упрощает до пары consistency и latency, так как

Availability and latency are arguably the same thing: an unavailable system essentially provides extremely high latency Дальше автор выводит необходимость репликации данных из требования высокой доступности и вероятности сбоев в распределенной системе. Он делает это от противного, то есть если этого не делать, то при достаточно долгом времени работы системы один из компонентов системы выйдет из строя, его данные будут потеряны, а это эффективно приведет к их недоступности.

Дальше автор рассматривает варианты репликации данных

1. Data updates sent to all replicas at the same time
2. Data updates sent to an agreed-upon location first
3. Data updates sent to an arbitrary location first

1. Здесь отправка обновлений происходит на все ноды. Есть два варианта

• a. Pre-processing слоя нет - тут будет нарушена консистентность (линеаризуемость) из определения Gilbert and Lynch (из уже упоминавшегося доказательства CAP теоремы).
• b. Такой слой есть - время уйдет на координацию узлов, если их много, а если узел в препроцессинге один, то мы будем тратить время на пересылку запросов к нему, что в гео-распределенной системе может быть затратно.

2. Здесь мы имеем мастер-ноду (для разных элементов данных у нас могут быть разные мастера). И в эту мастер-ноду летят все запросы на обновление, которые она выполняет и эффективно определяет порядок операций, который един для всех реплик. Здесь есть 3 возможности для репликации

1. Синхронная репликация - при апдейте мы ждем пока все реплики обновятся. Это консистентно, но увеличивает latency
2. Асинхронная репликация - тут мы обычно прихраниваем update в persistent storage, но успешной репликации не ждем и подтверждаем операцию. Дальше интересно посмотреть как мы читаем данные в этом случае

• a. Если мы читаем с мастера, то мы не имеем проблем с consistency, но latency может быть большим, так как мастер далеко. Плюс при высокой нагрузке на мастер мы тоже получим проблемы с latency.
• b. Если мы читаем с реплик, то потенциально может прочитать устаревшие данные

3. Комбинация синхронное и асинхронной - по-факту, это что-то из серии tunable consistency в Cassandra, где можно указывать кворум на запись и на чтение

3. Тут похоже на второй пункт, но мы отправляем обновления не в определенный мастер для конкретного элемента, а на произвольную ноду. Проблемы с consistency и latency здесь похожи на те, что во втором пункте.

Дальше автор разбирает как эти tradeoffs работают в популярных на то время базах данных: Dynamo, Cassandra, PNUTS, Riak, ... и делается вывод, что дизайн решения в базах зачастую больше фокусируются на consistency/latency в условиях нормальной работы, а не на consistency/availability в условиях наступления partition. И дальше автор предлагает переписать CAP в PACELC с примерно такой формулировкой

If there is a partition (P), how does the system trade off availability and consistency (A and C); else (E), when the system is running normally in the absence of partitions, how does the system trade off latency (L) and consistency (C)?

#Software #Architecture #DistributedSystems #SystemDesign