Cap теорема mongodb

1. Overview

In this article, we will explain where MongoDB stands in terms of the CAP theorem.

The CAP theorem talks about the trade-off between consistency and availability that you have to make in your distributed system when your system ever suffers network partition or failure that interrupts communication between the systems.

CAP stands for Consistency, Availability, and Partition Tolerance.

Partition tolerance is referring to a distributed system continuing to operate even if a network partition or failure interrupts communication between some nodes. Distributed databases are CP (Consistency and Partition tolerance) or AP (Availability and Partition tolerance).

3. MongoDB CAP theorem

Scenario	CAP theorem	Description
No partition	Consistency and Availability	MongoDB system is available and provides strong consistency
Partition but a majority of nodes connected	Availability and Partition Tolerance	It ignores non-synchronized writes from the old primary thus no consistency
Partition but a majority of nodes not connected	Consistency and Partition Tolerance	Only read access to the system to avoid inconsistency but not available for the write operations.

3.1. MongoDB Availability

MongoDB gets high availability through Replica-Sets. Replica sets provide redundancy and high availability.

MongoDB automatically maintains replica sets, multiple copies of data that are distributed across servers, racks, and data centers. Replica sets help prevent database downtime using native replication and automatic failover.

A replica set comprises multiple replica set members. At any given time, one member acts as the primary member, and the other members act as secondary members. If the primary member fails for any reason (e.g., hardware failure), MongoDB automatically elects one of the secondary members as primary and that processes all reads and writes.

When the former primary becomes available again and rejoins the replica set after failover as a secondary member, a rollback operation may happen. A rollback is necessary only if the primary had accepted write operations that the secondaries had not successfully replicated before the primary stepped down. When the primary rejoins the set as a secondary, it reverts, or “rolls back,” its write operations to maintain database consistency with the other members.

When a rollback occurs, it is often the result of a network partition. Secondaries that can not keep up with the throughput of operations on the former primary, increase the size and impact of the rollback.

A rollback does not occur if the write operations replicate to another member of the replica set before the primary steps down and if that member remains available and accessible to a majority of the replica set.

3.2. Partition tolerance

As long as the majority of the servers in a Replica Set are connected to each other, a new primary can be chosen. Thus, no two separated networks can choose a new primary.

When enough secondaries are not connected to each other, you can still perform read operations, but can not write for the sake of consistency.

3.3. MongoDB Consistency

MongoDB is consistent by default: reads and writes are issued to the primary member of a replica set. Applications can optionally read from secondary replicas, in which case data is eventually consistent by default.

Reads from secondaries can be useful in scenarios where it is acceptable for data to be slightly out of date, such as in some reporting applications.

Applications can also read from the closest copy of the data (as measured by ping distance) when the latency is more important than the consistency.

4. Conclusion

To sum up, we have learned MongoDB along with its CAP theorem. To learn more about MongoDB, refer to our articles.

There is a lot of discussion in the NoSQL community about consistency levels offered by NoSQL DBs and its relation to CAP/PACELC theorem. This article seeks to address this w.r.t MongoDB in-depth, thereby providing a broad overview of approaching CAP and PACLEC theorems from a NoSQL perspective. For a quick summary of consistency levels, please refer to Consistency Matrix towards the end of the article.

You might also enjoy: 
Understanding the CAP Theorem

MongoDB Notes for the Purpose of This Article

1. MongoDB always replicates data asynchronously from primary to secondaries. This cannot be changed.

2. Even when you increase writeconcern to w:2 or w:majority and enable journaling, replication is still asynchronous.

3. Secondaries read data from the primary’s oplog and apply operations asynchronously.

4. Default writeconcern of MongoDB is w:1 (successful write to primary) and journaling is disabled j:false

5. WRITEs can be performed only on PRIMARY

6. By Default, READs are done on PRIMARY. This can be changed by sacrificing consistency.

7. Enabling READs from SECONDARIES results in stale/dirty reads and and makes MongoDB EVENTUAL CONSISTENT even without a PARTITION.

8. Availability during a partition of MongoDB cluster is always on BEST EFFORT basis. A part of the cluster is always lost in the event of a partition.

Loss of Consistency in MongoDB

1. During Partition — By default, due to asynchronous replication, when there is a partition in which primary is lost or becomes isolated on the minority side, there is a chance of losing data that is unreplicated to secondaries, hence there is loss of consistency during partitions. More on how to address this below.

2. Without Partition — If reads from secondaries are enabled, async replication forces MongoDB to be eventually consistent even when there is no partition.

Some Definitions

Tuneable Consistency (Consistency Continuum)

Consistency is not a discrete point in space, it is a continuum, ranging from Strong Consistency at one extreme to Weak Consistency on the other, with varying points of Eventual Consistency in between. Each software application, according to the use case, may choose to belong anywhere in between.

With availability during a partition being always on Best-Effort basis, Consistency Level during a PARTITION is traded off with latency during NON-PARTITION. Decisioning on write latency as per our application requirement drives us to a point in the Consistency Continuum and vice versa.

We can achieve varying levels of latency during NON-PARTITION and varying consistency guarantees during PARTITION by tuning w and j values as below:

1. Example, w:0 no guarantees — very very low latency, very very low consistency — writes can be lost without PARTITION

2. Example, w:1 and j:false guarantees writes onto primary(disk) — very low latency, very low consistency

3. Example, w:2 and j:false guarantees writes onto primary(disk) + 1 secondary (memory) — low latency, low consistency

4. Example, w:2 and j: true guarantees writes onto primary(disk) + 1 secondary (disk) — mid latency, mid consistency

5. Example, w:majority and j: false guarantees writes onto primary(disk) + majority secondary (memory) — mid latency, mid consistency

6. Example, w:majority and j: true guarantees writes onto primary(disk) + majority secondary (memory) — high latency, high consistency

7. With {w:1, j:false} — writes are faster when there is no partition as writes do not wait on replication.

8. And with {w:1, j:false} — in the event of PARTITION when primary node is lost, there is a high probability of successful writes being lost.

9. The probability of losing successful writes decreases with an increase in writeconcern and by enabling journaling.

To READ or NOT-TO-READ From Secondaries

Barring the below cases:

{w:majority, j: true } — Strong Consistency in most cases

{w:0, j:false} — Weak Consistency in any primary failure,

for all other combinations of w & j, the below is how reading/not reading from secondaries affect the consistency levels.

If reads from secondaries are enabled, stale data is read and MongoDB offers following consistency levels,

1. Successful writes when there is NO PARTITION — Eventual Consistency

2. Unsuccessful writes when there is NO PARTITION — Eventual Consistency

3. Worst Case for successful writes when there is PARTITION — Weak Consistency

4. Avg case for successful writes heavily depends on the configuration and the way cluster is partitioned leaning towards Eventual Consistency.

5. Best Case for successful writes when there is PARTITION when acting primary is not lost — Eventual Consistency

6. Worst Case for unsuccessful writes when there is PARTITION — Weak Consistency

7. Avg case for unsuccessful writes heavily depends on the configuration and the way cluster is partitioned leaning towards Weak Consistency

8. Best case for unsuccessful writes when there is PARTITION when acting primary is not lost — Eventual Consistency

If reads from secondaries are disabled, MongoDB offers the following consistency levels:

1. Successful writes(no writeTimeout) when there is NO PARTITION — Strong Consistency

2. Unsuccessful writes( errored with writeTimeout) when there is NO PARTITION — Strong Consistency

3. Worst Case for successful writes(no writeTimeout) when there is PARTITION — Weak Consistency

4. Avg case for successful writes heavily depends on the configuration and the way the cluster is partitioned leaning towards Strong Consistency.

5. Best Case for successful writes(no writeTimeout) when there is PARTITION and the acting primary is not lost — Strong Consistency

6. Worst Case for unsuccessful writes (errored writeTimeout) when there is PARTITION and the acting primary is lost — Weak Consistency

7. Avg case for unsuccessful writes(errored writeTimeout) heavily depends on the configuration and the way cluster is partitioned leaning towards Weak Consistency

8. Best case for unsuccessful writes(errored writeTimeout) when there is PARTITION and the acting primary is not lost — Strong Consistency

9.  It becomes 0 when {w:majority, j:true}

Caveats and Considerations of Varying w and j Values

1. If we want low latency during non-partition a.k.a normal times then writeconcern should be set to a lower value and journaling should be disabled.

2. However, the trade-off here is when partition occurs on such a cluster, the probability of losing successful writes is very high.

3. When there is no partition or when all nodes are up, MongoDB is consistent and achieves low latency

4. When there is a partition, MongoDB’s consistency depends on the writeconcern and journaling settings.

5. The lower the latency expectation. the lower should be the value of writeconcern(w:1) with journaling disabled (j:false).

Concluding Remarks on Tuneable Consistency — CAP/PACELC Theorem

Barring the below cases

• {w:majority, j: true } — Strong Consistency in most cases

• {w:0, j:false} — Weak Consistency in any primary failure,

For all other combinations of w & j, we cannot precisely define where a MongoDB cluster lies in the Consistency Continuum defined by CAP or PACELC theorems.

Availability [Applicable for the Entire Consistency Continuum]

1. MongoDB provides Best Effort Availability because in case of partition, we will always lose a part of the cluster — at least a minority.

2. If MAJORITY of the cluster is lost we can only READ from MongoDB. Write availability is totally impacted.

3. if MINORITY of the cluster is lost we can READ and WRITE from MongoDB. Partial Availability.

Achieving Strong Consistency

With the below settings, MongoDB offers strong consistency in most cases for practical purposes.

1. {w:majority} and {j:true}

2. WRITE on primary node(only possible setting with MongoDB)

3. READ from primary node only (for max consistency)

Consistency Levels Offered Under Various Scenarios

1. Successful writes when there is NO PARTITION — Strong Consistency

2. Unsuccessful writes when there is NO PARTITION — Strong Consistency

3. Worst Case for successful writes when there is PARTITION — Strong Consistency

4. Worst Case for successful writes Strong Consistency.

5. Best Case for successful writes when there is PARTITION and acting primary is not lost — Strong Consistency

6. Worst Case for unsuccessful writes when there is PARTITION and acting primary is lost — Weak Consistency

7. Avg case for unsuccessful writes heavily depends on the configuration and the way cluster is partitioned — Leans towards Strong Consistency

8. Best case for unsuccessful writes(errored writeTimeout) when there is PARTITION and acting primary is not lost — Strong Consistency

Caveats and Considerations of the Above Settings

1. Setting {w:majority} and {j:true} forces the client to wait till the majority of the secondaries accept and persist the write.

2. Setting {w:majority} and {j:true} introduces latency in writes.

3. Event with this setting, unsuccessful writes might be lost during partition when the primary is lost.

4. With this setting, successful writes are not lost during partition.

Concluding Remarks on Strong Consistency — CAP/PACELC Theorem

With {w:majority, j:true} and READ from primary only, MongoDB could be categorized as CP in CAP and CP/EC in PACELC theorem

Consistency Matrix

Further Reading

Consistency in Databases

Cloud-Native Applications and the CAP Theorem

Big Data, Конференции, Блог компании ua-hosting.company, IT-инфраструктура, MongoDB

---

Рекомендация: подборка платных и бесплатных курсов таргетированной рекламе — https://katalog-kursov.ru/

Причинная согласованность (Causal consistency). Определимся с понятиями

Для начала я хочу в общих чертах сказать, что же такое Causal consistency. Есть два персонажа – Леонард и Пенни (сериал «Теория большого взрыва»):

Предположим, что Пенни в Европе, а Леонард хочет сделать для неё какой-нибудь сюрприз, тусовку. И он ничего лучше не придумывает, чем выкинуть её из френд-листа, послать всем друзьям апдейт на feed: «Давайте порадуем Пенни!» (она в Европе, пока спит, не видит этого всего и не может увидеть, потому что она не там). В конечном моменте удаляет этот пост, стирает из «Фида» и восстанавливает access, чтобы она ничего не заметила и скандала не было.
Это всё прекрасно, но давайте предположим, что система распределённая, и события пошли не немного не так. Может, например, случится, что ограничение access Пенни произошло после того, как появился этот пост, если события не связаны между собой причинно-следственными связями. Собственно, это – пример того, когда требуется наличие Causal consistency для того, чтобы выполнить бизнес-функцию (в данном случае).

На самом деле это достаточно нетривиальные свойства базы данных – очень мало кто их поддерживает. Давайте перейдём к моделям.

Модели согласованности (Consistency Models)

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

В принципе все модели консистенции сводятся к тому, насколько распределённая система похожа на систему, которая работает, например, на одном nod’е на лэптопе. И вот насколько система, которая работает на тысячах геораспределённых «Нодов», похожа на лэптоп, в котором все эти свойства выполняются в принципе автоматически.

Поэтому модели консистенции только к распределённым системам и применяются. Все системы, которые раньше существовали и работали на одном вертикальном масштабировании, таких проблем не испытывали. Там был один Buffer Cache, и из него всё всегда вычитывалось.

Модель Strong

Собственно, самая первая модель – это Strong (или линия rise ability, как её часто называют). Это модель консистенции, которая гарантирует, что каждое изменение, как только получается подтверждение о том, что оно произошло, становится видно всем пользователям системы.

Это создаёт глобальный порядок всех событий в БД. Это очень сильное свойство консистенции, и оно вообще очень дорогое. Тем не менее оно очень хорошо поддерживается. Оно просто очень дорогое и медленное – им просто редко пользуются. Это называется rise ability.

Есть ещё одно, более сильное свойство, которое поддерживается в «Спаннере» – называется External Consistency. Мы о нём поговорим чуть позже.

Causal

Следующее – это Causal, как раз то, о чём я говорил. Между Strong и Causal существует ещё несколько подуровней, о которых я не буду говорить, но они все сводятся к Causal. Это важная модель, потому что она – самая сильная из всех моделей, самая сильная консистенция при наличии сети или partitions.

Causals – это собственно ситуация, при которой события связаны причинно-следственной связью. Очень часто их воспринимают как Read your on rights с точки зрения клиента. Если клиент наблюдал какие-то значения, он не может увидеть значения, которые были в прошлом. Он уже начинает видеть префиксные чтения. Это всё сводится к одному и тому же.
Causals как модель консистенции – частичное упорядочивание событий на сервере, при котором события со всех клиентов наблюдаются в одной и той же последовательности. В данном случае – Леонард и Пенни.

Eventual

Третья модель – это Eventual Consistency. Это то, что поддерживает абсолютно все распределённые системы, минимальная модель, которая вообще имеет смысл. Она означает следующее: когда у нас происходят некоторые изменения в данных, они в какой-то момент становятся консистентными.

В такой момент она ничего не говорит, иначе она превратилась бы в External Consistency – была бы совершенно другая история. Тем не менее это очень популярная модель, самая распространённая. По умолчанию все пользователи распределённых систем используют именно Eventual Consistency.

Я хочу привести некоторые сравнительные примеры:

Что эти стрелочки означают?

• Latency. При увеличении силы консистенции она становится больше по понятным причинам: нужно сделать больше записей, получить подтверждение от всех хостов и нодов, которые участвуют в кластере, что данные там уже есть. Соответственно в Eventual Consistency самый быстрый ответ, потому что там, как правило, можно даже в memory закоммитить и этого будет в принципе достаточно.
• Availability. Если это понимать как возможность системы ответить при наличии разрывов сети, partitions, или каких-то отказов – отказоустойчивость возрастает при уменьшении модели консистенции, поскольку нам достаточно того, чтобы один хост жил и при этом выдавал какие-то данные. Eventual Consistency вообще ничего не гарантирует по поводу данных – это может быть всё, что угодно.
• Anomalies. При этом, конечно, возрастает количество аномалий. В Strong Consistency их вообще почти что не должно быть, а Eventual Consistency они могут быть какие угодно. Возникает вопрос: почему же люди выбирают Eventual Consistency, если она содержит аномалии? Ответ в том заключается, что Eventual Consistency-модели применимы, а аномалии существуют, например, в короткий промежуток времени; существует возможность использовать мастер для чтения и более-менее читать консистентные данные; часто есть возможность использовать сильные модели консистенции. Практически это работает, и часто количество аномалий ограничено по времени.

Теорема CAP

Когда вы видите слова consistency, availability – что вам приходит на ум? Правильно – CAP theorem! Я сейчас хочу развеять миф… Это не я – есть Мартин Клеппман, который написал прекрасную статью, прекрасную книжку.

Теорема CAP – это принцип, сформулированный в 2000-х годах, о том, что Consistency, Availability, Partitions: take any two, и нельзя выбрать три. Это был некий принцип. Он был доказан как теорема несколько лет спустя, это сделали Джилберт и Линч. Затем это стало использоваться, как мантра – системы стали делиться на CA, CP, AP и так далее.

Эта теорема была доказана на самом деле вот для каких случаев… Во-первых, Availability рассматривалась не как непрерывное значение от нуля до сотни (0 – система «мёртвая», 100 – отвечает быстро; мы её так привыкли рассматривать), а как свойство алгоритма, которое гарантирует, что при всех его executions он возвращает данные.

О времени ответа там вообще нет ни слова! Есть алгоритм, который возвращает данные через 100 лет – совершенно прекрасный available-алгоритм, которые является частью теоремы CAP.
Второе: доказывалась теорема для изменений в значениях одного и того же ключа, притом что эти изменения – линия resizable. Это означает то, что на самом деле они практически не используются, потому что модели другие Eventual Consistency, Strong Consistency (может быть).

К чему это всё? К тому, что теорема CAP именно в той форме, в которой она доказана, практически не применима, редко используется. В теоретической форме она каким-то образом всё ограничивает. Получается некий принцип, который интуитивно верен, но никак, в общем-то, не доказан.

Causal consistency – самая сильная модель

То, что сейчас происходит – можно получить все три вещи: Consistency, Availability получить с помощью Partitions. В частности Causal consistency – самая сильная модель консистенции, которая при наличии Partitions (разрывов в сети) всё равно работает. Поэтому она и представляет такой большой интерес, поэтому мы ею и занялись.

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

Внутренняя кухня MongoDB

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

MongoDB (далее – «МонгоБД») – это распределённая система, которая поддерживает горизонтальное масштабирование, то есть шардинг; и внутри каждого шарда она также поддерживает избыточность данных, то есть репликацию.

Шардинг в «МонгоБД» (не реляционная БД) выполняет автоматическую балансировку, то есть каждая коллекция документов (или «таблица» в терминах реляционных данных) на кусочки, и уже сервер автоматически двигает их между шардами.

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

Ещё один важный момент: MongoDB – это single master. Есть один Primary – он может брать записи, поддерживающие те ключи, которые он в себе содержит. Нельзя сделать Multi-master write.

Мы сделали релиз 4.2 – там появились новые интересные вещи. В частности, вставили Lucene –поиск – именно executable java прямо в «Монго», и там стало возможным выполнять поиск через Lucene, такой же, как в «Эластике».

И сделали новый продукт – Charts, он тоже доступен на «Атласе» (собственный Cloud «Монго»). У них есть Free Tier – можно поиграться с этим. Charts мне очень понравился – визуализация данных, очень интуитивная.

Ингредиенты Causal consistency

Я насчитал порядка 230 статей, которые были опубликованы на эту тему – от Лесли Ламперта. Сейчас из памяти своей я вам их донесу какие-то части этих материалов.

Всё началось со статьи Лесли Ламперта, которая была написана в 1970-х годах. Как видите, до сих пор продолжаются какие-то исследования в этой теме. Сейчас Causal consistency переживает интерес в связи с развитием именно распределённых систем.

Ограничения

Какие ограничения есть? Это на самом деле один из главных моментов, потому ограничения, которые накладывает продакшн системы, сильно отличаются от ограничений, которые существуют в академических статьях. Часто они достаточно искусственны.

• Во-первых, «МонгоДБ» – это single master, как я уже говорил (это сильно упрощает).
• Мы считаем, что порядка 10 тысяч шардов система должна поддерживать. Мы не можем принимать какие-то архитектурные решения, которые будут явно ограничивать это значение.
• Есть у нас облако, но мы предполагаем, что у человека должна оставаться возможность, когда он скачивает binary, запускает у себя на лэптопе, и всё прекрасно работает.
• Мы предполагаем то, что в Research редко используется: внешние клиенты могут делать что угодно. «МонгоДБ» – это опенсорс. Соответственно, клиенты могут быть такие умные, злые – могут хотеть всё сломать. Мы предполагаем, что византийские Фейлоры могут происходить.
• Для внешних клиентов, которые за пределами периметра – важное ограничение: если эта фича выключена, то никаких performance degradation не должно наблюдаться.
• Ещё один момент – вообще антиакадемический: совместимость предыдущих версий и будущих. Старые драйверы должны поддерживать новые апдейты, и БД должна поддерживать старые драйверы.

В общем, всё это накладывает ограничения.

Компоненты Causal consistency

Я сейчас расскажу о некоторых компонентах. Если рассматривать вообще Causal consistency, можно выделить блоки. Мы выбирали из работ, которые относятся к какому-то блоку: Dependency Tracking, выбор часов, как эти часы можно между собой синхронизировать, и как мы обеспечиваем безопасность – это примерный план того, о чём я буду говорить:

Полное отслеживание зависимостей (Full Dependency Tracking)

Зачем оно нужно? Для того чтобы, когда данные реплицируются – каждая запись, каждое изменение данных содержало в себе информацию о том, от каких изменений оно зависит. Самое первое и наивное изменение – это когда каждое сообщение, которое содержит в себе запись, содержит информацию о предыдущих сообщениях:

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

Почему мы решили не пользоваться таким подходом (полный трекинг)? Очевидно, потому что этот подход непрактичен: любое изменение в социальной сети зависит от всех предыдущих изменений в этой соцсети, передавая, скажем, «Фейсбук» или «Вконтакте» в каждом обновлении. Тем не менее есть много исследований именно Full Dependency Tracking – это пресоциальные сети, для каких-то ситуаций это действительно работает.

Явное отслеживание зависимостей (Explicit Dependency Tracking)

Следующий – более ограниченный. Здесь тоже рассматривается передача информации, но только той, которая явно зависит. Что от чего зависит, как правило, определяет уже Application. Когда данные реплицируются, при запросе выдаются только ответы, когда предыдущие зависимости были удовлетворены, то есть показаны. В этом и суть того, как Causal consistency работает.

Она видит, что запись 5 зависит от записей 1, 2, 3, 4 – соответственно, она ждёт, прежде чем клиент получает доступ к изменениям, внесённым постановлением access’а Пенни, когда все предыдущие изменения уже прошли в базе данных.

Это тоже нас не устраивает, потому что всё равно информации слишком много, и это будет замедлять. Есть другой подход…

Часы Лэмпорта (Lamport Clock)

Они очень старые. Lamport Clock подразумевает то, что эти dependency сворачиваются в скалярную функцию, которая и называется Lamport Clock.

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

Я разбил тот большой шард надвое, чтобы было понятно: Friends могут жить в одном ноде, который содержит кусок коллекции, а Feed – вообще в другом ноде, в котором содержится кусок этой коллекции. Понятно, как они могут попасть не в очередь? Сначала Feed скажет: «Реплицировался», а потом – Friends. Если система не обеспечивает каких-то гарантий, что Feed не будет показан, пока зависимости Friends в коллекции Friends тоже не будут доставлены, то у нас как раз возникнет ситуация, о которой я упомянул.

Вы видите, как увеличивается логически время counter на Feed’е:

Таким образом, основное свойство этого Lamport Clock и Causal consistency (объяснённого через Lamport Clock) заключается в следующем: если у нас есть события A и B, и событие B зависит от события A *, то из этого следует, что LogicalTime от Event A меньше, чем LogicalTime от Event B.

* Иногда ещё говорят, что A happened before B, то есть A случилось раньше B – это некое отношение, которое частично упорядочивает всё множество событий, которые вообще произошли.

В обратную сторону неверно. Это на самом деле один из основных минусов Lamport Clock – частичный порядок. Там есть понятие об одновременных событиях, то есть событий, в которых ни (A happened before B), ни (A happened before B). Примером может служить параллельное добавление Леонардом в друзья кого-нибудь ещё (даже не Леонардом, а Шелдоном, например).
Это и есть свойство, которым часто пользуются при работе Lamport-часами: смотрят именно на функцию и из этого делают вывод – может быть, эти события зависимы. Потому что в одну сторону это верно: если LogicalTime A меньше LogicalTime B, то B не может happened before A; а если больше, то может быть.

Векторные часы (Vector Clock)

Логическое развитие часов Лэмпорта – это Векторные часы. Они отличаются тем, что каждый нод, который здесь есть, содержит в себе свои, отдельные часы, и они передаются как вектор.
В данном случае вы видите, что нулевой индекс вектора отвечает за Feed, а первый индекс вектора – за Friends (каждый из этих нодов). И вот они сейчас будут увеличиваться: нулевой индекс «Фида» увеличивается при записи – 1, 2, 3:

Чем Векторные часы лучше? Тем, что позволяют разобраться, какие события одновременны и когда они происходят на различных нодах. Это очень важно для системы шардирования, как «МонгоБД». Однако мы это не выбрали, хотя это и прекрасная штука, и замечательно работает, и нам подошла бы, наверное…

Если у нас 10 тысяч шардов, мы не можем передавать 10 тысяч компонентов, даже если сжимаем, ещё что-то придумываем – всё равно полезная нагрузка будет в разы меньше, чем объём всего этого вектора. Поэтому, скрипя сердцем и зубами, мы отказались от этого подхода и перешли к другому.

Spanner TrueTime. Атомные часы

Я говорил, что будет рассказ о «Спаннере». Это крутая штука, прям XXI век: атомные часы, GPS-синхронизация.

Идея какая? «Спаннер» – это гугловская система, которая недавно даже стала доступна для людей (они приделали к ней SQL). Каждая транзакция там имеет некоторый time stamp. Поскольку время синхронизировано*, каждому событию можно назначить определённый times – у атомных часов есть время ожидания, после которого гарантированно «происходит» уже другое время.

Таким образом, просто записывая в БД и ожидая какой-то период времени, автоматически гарантируется Serializability события. У них самая сильная Consistency-модель, которую в принципе можно представить – она External Consistency.

* Это основная проблема часов Лэмпарта – они никогда не синхронны на распределённых системах. Они могут расходиться, даже при наличии NTP всё равно работают не очень хорошо. «Спаннер» имеет атомные часы и синхронизацию, кажется, то микросекунд.

Почему мы не выбрали? Мы не предполагаем, что у наших пользователей в наличии есть встроенные атомные часы. Когда они появятся, будучи встроенными в каждый лэптоп, будет какая-то суперкрутая GPS-синхронизация – тогда да… А пока что лучшее, что возможно – это «Амазон», Base Stations – для фанатиков… Поэтому мы использовали другие часы.

Гибридные часы (Hybrid Clock)

Это фактически то, что тикает в «МонгоБД» при обеспечении Causal consistency. Гибридные они в чём? Гибрид – это скалярное значение, но оно состоит из двух компонентов:

• Первое – это unix’вая эпоха (сколько секунд прошло с «начала компьютерного мира»).
• Второе – некоторый инкремент, тоже 32-битный unsigned int.

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

Почему это важно для «МонгоБД»? Потому что позволяет делать какие-то бэкап-ресторы на определённый момент времени, то есть событие индексируется временем. Это важно, когда нужны некоторые события; для БД события – это изменения в БД, которые произошли в определённые промежутки момент времени.

Самую главную причину я скажу только вам (пожалуйста, только никому не говорите)! Мы так сделали потому, что так выглядят упорядоченные, индексированные данные в MongoDB OpLog. OpLog – это структура данных, которая содержит в себе абсолютно все изменения в базе: они сначала попадают в OpLog, а потом уже применяются уже собственно к Storage в том случае, когда это реплицированная дата или шард.

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

Синхронизация часов

Существует несколько способов синхронизации, описанных в научной литературе. Я говорю о синхронизации, когда у нас есть два различных шарда. Если одна реплика-сет – там никакой синхронизации не нужно: это «сингл-мастер»; у нас есть OpLog, в который все изменения попадают – в этом случае всё уже sequentially ordered в самом «Оплоге». Но если у нас есть два разных шарда, здесь синхронизация времени важна. Вот тут векторные часы больше помогли! Но у нас их нет.

Второй подходит – это «Хартбиты» (Heartbeats). Можно обмениваться некоторыми сигналами, которые происходит каждую единицу времени. Но «Хартбиты» – слишком медленные, мы не можем latency обеспечить нашему клиенту.

True time – конечно, прекрасная штука. Но, опять же, это, наверное, будущее… Хотя в «Атласе» уже можно сделать, уже есть быстрые «амазоновские» синхронизаторы времени. Но это не будет доступно для всех.

Gossiping – это когда все сообщения включают в себя время. Это примерно то, что мы и используем. Каждое сообщение между нодами, драйвер, роутер дата-ноды, абсолютно всё для «МонгоДБ» – это какие-то элементы, компоненты базы данных, которые содержат в себе часы, которые текут. У них везде есть значение гибридного времени, оно передаётся. 64 бита? Это позволяет, это можно.

Как всё это работает вместе?

Здесь я рассматриваю один реплика-сет, чтобы было чуть-чуть проще. Есть Primary и Secondary. Secondary делает репликацию и не всегда полностью синхронизирован с Primary.

Происходит вставка (insert) в «Праймери» с некоторым значением времени. Этот insert увеличивает внутренний каунтер на 11, если это максимально. Или он будет проверять значения часов и синхронизируется по часам, если значения часов больше. Это позволяет упорядочить по времени.

После того как он делает запись, происходит важный момент. Часы в «МонгоДБ» и инкрементируются только в случае записи в «Оплог». Это и является событием, которое меняет состояние системы. Абсолютно во всех классических статьях событием считается попадание сообщения в нод: сообщение пришло – значит, система изменила своё состояние.

Это связано с тем, что при исследовании не совсем можно понять, как это сообщение будет интерпретировано. Мы точно знаем, что если оно не отражено в «Оплоге», то оно никак не будет интерпретировано, и изменением состояния системы является только запись в «Оплог». Это нам всё упрощает: и модель упрощает, и позволяет вести упорядочивание в рамках одного реплика-сета, и много чего другого полезного.

Возвращается значение, которое уже записано в «Оплог» – мы знаем, что в «Оплоге» уже лежит это значение, и его время – 12. Теперь, скажем, начинается чтение с другого нода (Secondary), и он передаёт уже afterClusterTime в самом сообщении. Он говорит: «Мне нужно всё, что произошло как минимум после 12 или во время двенадцати» (см. рис. выше).

Это то, что называется Causal a consistent (CAT). Есть такое понятие в теории, что это некоторые срез времени, которое консистентно само по себе. В данном случае можно сказать, что это состояние системы, которое наблюдалось в момент времени 12.

Сейчас здесь пока ничего нет, потому что это как бы имитирует ситуацию, когда нужно, чтобы Secondary реплицировал данные с Primary. Он ждёт… И вот данные пришли – возвращает назад эти значения.

Вот так примерно всё и работает. Почти что.

Что значит «почти что»? Давайте предположим, что есть некоторый человек, который прочитал и понял, как это всё работает. Понял, что каждый раз происходит ClusterTime, он обновляет внутренние логические часы, и потом следующая запись увеличивает на единицу. Эта функция занимает 20 строк. Допустим, этот человек передаёт максимально большое 64-битное число, минус единица.

Почему «минус единица»? Потому что внутренние часы подставятся в это значение (очевидно, это самое большое возможное и больше текущего времени), потом произойдёт запись в «Оплог», и часы инкрементируются ещё на единицу – и уже будет вообще максимальное значение (там просто все единицы, дальше некуда, unsaint int’ы).

Понятно, что после этого система становится абсолютно недоступна ни для чего. Её можно только выгрузить, почистить – много ручной работы. Полный availability:

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

Наш путь – подписывать clusterTime

Так оно передаётся в сообщении (до синего текста). Но мы стали ещё и генерировать подпись (синий текст):

Подпись генерируется ключом, который хранится внутри базы данных, внутри защищённого периметра; сам генерируется, обновляется (пользователи этого ничего не видят). Генерируется hash, и каждое сообщение при создании подписывается, а при получении – валидируется.
Наверное, возникает вопрос у людей: «Насколько это всё замедляет?» Я же говорил, что должно быстро работать, особенно при отсутствии этой фичи.

Что значит пользоваться Causal consistency в данном случае? Это показывать afterClusterTime-параметр. А без этого он просто будет передавать значения в любом случае. Gossiping, начиная с версии 3.6, работает всегда.

Если мы оставим постоянное генерирование подписей, то это будет замедлять систему даже при отсутствии фичи, что не соответствует нашим подходам и требованиям. И что мы сделали?

Делай это быстро!

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

Получая такую подпись, мы ускоряем систему (условно) в 65 тысяч раз. Оно прекрасно работает: когда поставили эксперименты – там реально в 10 тысяч раз сократилось время, когда у нас последовательный апдейт. Понятно, что когда они в разнобой, этого не получается. Но в большинстве практических случаев это работает. Комбинация подписи Range вместе с подписью позволила решить проблему безопасности.

Чему мы научились?

Уроки, которые мы из этого извлекли:

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

  Вообще, наблюдается определённая разница в мышлении, когда имеет место академическая конференция («Сигмон», например) – там все фокусируются на новых идеях. В чём новизна нашего алгоритма? Здесь новизны особой нет. Новизна скорее заключается в том, как мы смешали вместе существующие подходы. Поэтому первое – нужно читать классиков, начиная с Лэмпарта.

• В продакшне совершенно другие требования. Я уверен, что многие из вас сталкиваются не со «сферическими» базами данных в абстрактном вакууме, а с нормальными, реальными вещами, у которых существуют проблемы по availability, latency и отказоустойчивости.
• Последнее – это то, что нам пришлось рассмотреть разные идеи и скомбинировать несколько вообще разных статей в один подход, вместе. Идея про подписывание, например, вообще пришла из статьи, которая рассматривала Paxos-протокол, которые для невизантийских Фейлоров внутри авторизационного протокола, для византийских – за пределами авторизационного протокола… В общем, это ровно то, что мы в итоге и сделали.

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

На этом закончу. Спасибо!

Вопросы

Вопрос из зала (далее – В): – Спасибо, Михаил за доклад! Тема про время интересная. Вы используете Gossiping. Сказали, что у всех есть своё время, все знают своё локальное время. Я так понял, что у нас есть драйвер – клиентов с драйверами может быть много, query-planner’ов тоже, шардов тоже много… А к чему скатывается система, если у нас вдруг возникнет расхождение: кто-то решит, что он на минуту впереди, кто-то — на минуту позади? Где мы окажемся?

МТ: – Отличный вопрос на самом деле! Я как раз про шарды хотел сказать. Если я правильно понимаю вопрос, у нас такая ситуация: есть шард 1 и шард 2, чтение происходит с этих двух шардов – у них расхождение, они между собой не взаимодействуют, потому что время, которое они знают – разное, особенно время, которое у них существует в оплогах.
Допустим, шард 1 сделал миллион записей, шард 2 – вообще ничего, а запрос пришёл на два шарда. И у первого есть afterClusterTime более миллиона. В такой ситуации, как я объяснил, шард 2 вообще никогда не ответит.

В: – Я хотел узнать, как они синхронизируются и выберут одно логическое время?

МТ: – Очень просто синхронизируются. Шард, когда к нему приходит afterClusterTime, и он не находит времени в «Оплоге» – инициирует no approved. То есть он руками поднимает своё время до этого значения. Это означает, что у него нет событий, отвечающих этому запросу. Он создаёт это событие искусственно и становится таким образом Causal Consistent.

В: – А если к нему после этого ещё приедут какие-нибудь события, которые в сети где-то затерялись?

МТ: – Шард так устроен, что они уже не приедут, поскольку это single master. Если он уже записал, то они уже не приедут, а будут после. Не может так получиться, что где-то что-то застряло, потом он сделает no write, а потом эти события приехали – и нарушилась Causal consistency. Когда он делает no write, они все должны приехать дальше (он их подождёт).

В: – У меня есть несколько вопросов относительно очередей. Causal consistency предполагает, что есть определённая очередь действий, которые нужно выполнить. Что произойдёт, если у нас один пакет пропадает? Вот пошёл 10-й, 11… 12-й пропал, а все остальные ждут, когда он исполнится. И у нас вдруг машина умерла, мы ничего не можем сделать. Есть ли максимальная длина очереди, которая копится, прежде чем выполняется? Какой fatal failure происходит при потере какого-либо одного состояния? Тем более, если мы записываем, что есть какое-то состояние предыдущее, то от него же мы должны как-то отталкиваться? А от него не оттолкнулись!

МТ: – Тоже прекрасный вопрос! Что мы делаем? В MongoDB есть понятие кворумных записей, кворумного чтения. В каких случаях сообщение может пропасть? Когда запись некворумная или когда чтение не кворумное (тоже может пристать какой-то garbage).
Относительно Causal consistency выполнили большую экспериментальную проверку, результатом которой стало то, что в случае, когда записи и чтение – некворумные, возникают нарушения Causal consistency. Ровно то, что вы говорите!

Наш совет: использовать хотя бы кворумное чтение при использовании Causal consistency. В этом случае пропадать ничего не будет, даже если кворумная запись пропадёт… Это ортогональная ситуация: если пользователь не хочет чтобы пропали данные, нужно использовать кворумную запись. Causal consistency не даёт гарантии durability. Гарантию durability даёт replication и machinery, связанная с replication.

В: – Когда мы создаём instance, который у нас шардинг выполняет (не master, а slave соответственно), он опирается на unix-время собственной машины или на время «мастера»; синхронизируется в первый раз или периодически?

МТ: – Сейчас проясню. Шард (т. е. горизонтальная партиция) – там всегда есть Primary. А в шарде может быть «мастер» и могут быть реплики. Но шард всегда поддерживает запись, потому что он должен поддерживать некоторый домен (в шарде стоит Primary).

В: – То есть всё зависит сугубо от «мастера»? Всегда используется «мастер»-время?

МТ: – Да. Можно образно сказать: часы тикают, когда происходит запись в «мастер», в «Оплог».

В: – У нас есть клиент, который коннектится, и ему не нужно знать про время ничего?

МТ: – Вообще ничего не нужно знать! Если говорить о том, как это работает на клиенте: у клиента, когда он хочет пользоваться Causal consistency, ему нужно открыть сессию. Сейчас там всё: и транзакции в сессии, и retrieve a rights… Сессия – это упорядочение логических событий, происходящих с клиентом.

Если он открывает эту сессию и там говорит, что хочет Causal consistency (если по умолчанию сессия поддерживает Causal consistency), всё автоматически работает. Драйвер запоминает это время и увеличивает его, когда получает новое сообщение. Он запоминает, какой ответ вернуло предыдущее с сервера, который вернул данные. Следующий запрос будет содержать afterCluster («time больше этого»).

Клиенту не нужно знать ровным счётом ничего! Это абсолютно для него непрозрачно. Если люди используют эти фичи, что позволяет сделать? Во-первых, можно безопасно читать secondaries: можно писать на Primary, а читать с географически реплицированных secondaries и быть уверенным, что это работает. При этом сессии, которые записал на Primary, можно передать даже на Secondary, т. е. можно использовать не одну сессию, а несколько.

В: – С темой Eventual consistency сильно связан новый пласт Compute science –типы данных CRDT (Conflict-free Replicated Data Types). Рассматривали ли вы интеграцию этих типов данных в базу и что можете сказать об этом?

МТ: – Хороший вопрос! CRDT имеет смысл для конфликтов при записи: в MongoDB – single master.

В: – У меня вопрос от девопсов. В настоящем мире встречаются такие иезуитские ситуации, когда византийский Failure происходит, и злые люди внутри защищённого периметра начинают втыкаться в протокол, специальным образом крафтовые пакеты присылать?

МТ: – Злые люди внутри периметра – всё равно что троянский конь! Злые люди внутри периметра могут сделать много плохих вещей.

В: – Понятное дело, что оставлять в сервере, грубо говоря, дырочку, через которую можно зоопарк слонов просунуть и обвалить весь кластер навсегда… Потребуется время для ручного восстановления… Это, мягко говоря, неправильно. С другой стороны, любопытно вот что: в реальной жизни, в практике встречаются такие ситуации, когда натурально подобные внутренние атаки происходят?

МТ: – Поскольку я нечасто сталкиваюсь с security breach’ами в реальной жизни, не могу сказать – может, они и происходят. Но если говорить о девелоперской философии, то мы считаем так: у нас есть периметр, который обеспечивает ребят, которые делают security – это замок, стена; а внутри периметра можно делать всё, что угодно. Понятно, что есть пользователи с возможностью только посмотреть, а есть пользователи с возможностью стереть каталог.

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

В: – В защищённом периметре кто-то полез формировать неожиданные протоколы для сервера, чтобы раком поставить сервер, а если повезёт, то и весь кластер… Бывает ли настолько «хорошо»?

МТ: – Ни разу не слышал о таких вещах. То, что таким образом можно завалить сервер – это не секрет. Завалить внутри, находясь с протокола, будучи авторизованным пользователем, который может записать в сообщение что-то такое… На самом деле нельзя, потому что всё равно он будет верифицироваться. Есть возможность отключить эту аутентификацию для пользователей, которые не хотят – это тогда их проблемы; они, грубо говоря, сами разрушили стены и можно запихнуть туда слона, который растопчет… А вообще, можно одеться ремонтником, прийти и вытащить!

В: – Спасибо за доклад. Сергей («Яндекс»). В «Монге» есть константа, которая лимитирует количество голосующих членов в Replica Set’е, и эта константа равна 7 (семи). Почему это константа? Почему это не параметр какой-то?

МТ: – Replica Set у нас бывает и по 40 нодов. Там всегда majority. Я не знаю какая версия…

В: – В Replica Set’е можно не голосующих членов запускать, но голосующих – максимум 7. Как в этом случае переживать выключение, если у нас Replica Set стянут на 3 дата-центра? Один дата-центр может запросто выключиться, и ещё одна машинка выпасть.

МТ: – Это уже немного за пределами доклада. Это общий вопрос. Может, потом его могу рассказать.

Немного рекламы 🙂

Спасибо, что остаётесь с нами. Вам нравятся наши статьи? Хотите видеть больше интересных материалов? Поддержите нас, оформив заказ или порекомендовав знакомым, облачные VPS для разработчиков от $4.99, уникальный аналог entry-level серверов, который был придуман нами для Вас: Вся правда о VPS (KVM) E5-2697 v3 (6 Cores) 10GB DDR4 480GB SSD 1Gbps от $19 или как правильно делить сервер? (доступны варианты с RAID1 и RAID10, до 24 ядер и до 40GB DDR4).

Dell R730xd в 2 раза дешевле в дата-центре Equinix Tier IV в Амстердаме? Только у нас 2 х Intel TetraDeca-Core Xeon 2x E5-2697v3 2.6GHz 14C 64GB DDR4 4x960GB SSD 1Gbps 100 ТВ от $199 в Нидерландах! Dell R420 — 2x E5-2430 2.2Ghz 6C 128GB DDR3 2x960GB SSD 1Gbps 100TB — от $99! Читайте о том Как построить инфраструктуру корп. класса c применением серверов Dell R730xd Е5-2650 v4 стоимостью 9000 евро за копейки?

The CAP Theorem and MongoDB

29 April 2012

/ Technology

This week I learned some things about MongoDB. One of them was about how it fits in with the CAP theorem.

They say a picture is worth a thousand words, and I think this diagram from my excellent new colleague Mat Wall while he was explaining it to me says everything:

Over and out.

OK, perhaps I can offer a tiny bit of exposition.

The CAP Theorem is: where C is consistency, A is availability, and P is partition tolerance, you can’t have a system that has all three. (It gets to be called a theorem because it has been formally proved.)

Roughly speaking:

• Consistency means that when two users access the system at the same time they should see the same data.
• Availability means up 24/7 and responds in a reasonable time.
• Partition Tolerance means if part of the system fails, it is possible for the system as a whole to continue functioning.

If you have a web app backed by a SQL database, most likely, it is CA.

It is C because it’s transaction-based. So when you update the database, everything stops until you’ve finished. So anything reading from the database will get the same data.

It can be A, but it won’t be P because SQL databases tend to run on single nodes.

If you want your application to be P, according to the CAP theorem, you have to sacrifice either A or C.

With MongoDB, in order to gain P, you sacrifice C. There are various ways to set it up, but in our application we have one master database, that all writes go to, and several secondaries (as can be seen from the diagram: M is the Master, the Rs are the secondaries – also called replicas, or slaves). Reads may come from the secondaries. So it is possibly that one or more of the secondary nodes could be disconnected from the application by some kind of network failure, but the application will not fall over because the read requests will just go to another node. Hence P.

The reason this sacrifices C is because the writes go to the master, and then take some time to filter out to all the secondaries. So C is not completely sacrificed – there is just a possibility that there may be some delay. We are not allowing a situation where the secondaries are permanently out of synch with the master – there is «eventual consistency».

So you might use this in applications where, for example, you are offering the latest news story. If User A gets the latest news 10 seconds earlier than User B, this doesn’t really matter. Of course, if it was a day later, then that would be a problem. The failure case of C is just around the time of the write and you want to keep that window of consistency small.

There is also a concept of durability, which you can also be flexible with.

Take the following two lines of pseudocode:

1. insert into table UNIVERSAL_TRUTHS (name, characteristic) values (‘Anna’, ‘is awesome’)
2. select characteristic from UNIVERSAL_TRUTHS where name = ‘Anna’

What we’re saying when we sacrifice consistency is, if I run these two lines on the same node then when I run line 2, I can be sure it will return ‘is awesome’. However, if I run line 2 on a different node, I can’t be sure it’s in already. It will still be «eventually consistent» so if I run it later (and it hasn’t been changed again in the interim) it will at some point return the correct data.

However, you can also configure MongoDB to be flexible about durability. This is where, if you run the two lines of code on the same node, it might be the case that line 2 hasn’t run, and possibly even never will. You might do this, for example if you were storing analytics. If you are looking for general trends, it might not matter so much if 1% of the transactions fail, so you might configure it to be flexible on durability. Of course you wouldn’t do that for something as crucial as characteristics about Anna.