Cap теорема mongodb

Everywhere I look, I see that MongoDB is CP.
But when I dig in I see it is eventually consistent.
Is it CP when you use safe=true? If so, does that mean that when I write with safe=true, all replicas will be updated before getting the result?

Community's user avatar

asked Jul 2, 2012 at 10:53

Gluz's user avatar

MongoDB is strongly consistent by default — if you do a write and then do a read, assuming the write was successful you will always be able to read the result of the write you just read. This is because MongoDB is a single-master system and all reads go to the primary by default. If you optionally enable reading from the secondaries then MongoDB becomes eventually consistent where it’s possible to read out-of-date results.

MongoDB also gets high-availability through automatic failover in replica sets:

answered Jul 2, 2012 at 16:33

stbrody's user avatar


1,6841 gold badge10 silver badges12 bronze badges


I agree with Luccas post. You can’t just say that MongoDB is CP/AP/CA, because it actually is a trade-off between C, A and P, depending on both database/driver configuration and type of disaster: here’s a visual recap, and below a more detailed explanation.

Scenario Main Focus Description
No partition CA The system is available and provides strong consistency
partition, majority connected AP Not synchronized writes from the old primary are ignored
partition, majority not connected CP only read access is provided to avoid separated and inconsistent systems


MongoDB is strongly consistent when you use a single connection or the correct Write/Read Concern Level (Which will cost you execution speed). As soon as you don’t meet those conditions (especially when you are reading from a secondary-replica) MongoDB becomes Eventually Consistent.


MongoDB gets high availability through Replica-Sets. As soon as the primary goes down or gets unavailable else, then the secondaries will determine a new primary to become available again. There is an disadvantage to this: Every write that was performed by the old primary, but not synchronized to the secondaries will be rolled back and saved to a rollback-file, as soon as it reconnects to the set(the old primary is a secondary now). So in this case some consistency is sacrificed for the sake of availability.

Partition Tolerance:

Through the use of said Replica-Sets MongoDB also achieves the partition tolerance: As long as more than half of the servers of a Replica-Set is connected to each other, a new primary can be chosen. Why? To ensure two separated networks can not both choose a new primary. When not enough secondaries are connected to each other you can still read from them (but consistency is not ensured), but not write. The set is practically unavailable for the sake of consistency.

danidemi's user avatar


4,2444 gold badges35 silver badges40 bronze badges

answered Jun 8, 2017 at 15:45

JoCa's user avatar


1,0259 silver badges14 bronze badges


As a brilliant new article showed up and also some awesome experiments by Kyle in this field, you should be careful when labeling MongoDB, and other databases, as C or A.

Of course CAP helps to track down without much words what the database prevails about it, but people often forget that C in CAP means atomic consistency (linearizability), for example. And this caused me lots of pain to understand when trying to classify. So, besides MongoDB give strong consistency, that doesn’t mean that is C. In this way, if one make this classifications, I recommend to also give more depth in how it actually works to not leave doubts.

answered May 15, 2015 at 0:19

Luccas's user avatar


4,0386 gold badges42 silver badges71 bronze badges

Yes, it is CP when using safe=true. This simply means, the data made it to the masters disk.
If you want to make sure it also arrived on some replica, look into the ‘w=N’ parameter where N is the number of replicas the data has to be saved on.

see this and this for more information.

burning_LEGION's user avatar

answered Jul 2, 2012 at 13:16

Jan Prieser's user avatar

Jan PrieserJan Prieser

1,5299 silver badges15 bronze badges

MongoDB selects Consistency over Availability whenever there is a Partition. What it means is that when there’s a partition(P) it chooses Consistency(C) over Availability(A).

To understand this, Let’s understand how MongoDB does replica set works. A Replica Set has a single Primary node. The only «safe» way to commit data is to write to that node and then wait for that data to commit to a majority of nodes in the set. (you will see that flag for w=majority when sending writes)

Partition can occur in two scenarios as follows :

  • When Primary node goes down: system becomes unavailable until a new
    primary is selected.
  • When Primary node looses connection from too many
    Secondary nodes: system becomes unavailable. Other secondaries will try to
    elect a new Primary and current primary will step down.

Basically, whenever a partition happens and MongoDB needs to decide what to do, it will choose Consistency over Availability. It will stop accepting writes to the system until it believes that it can safely complete those writes.

answered Apr 22, 2020 at 20:08

Rajneesh Prakash's user avatar


Mongodb never allows write to secondary. It allows optional reads from secondary but not writes. So if your primary goes down, you can’t write till a secondary becomes primary again. That is how, you sacrifice High Availability in CAP theorem. By keeping your reads only from primary you can have strong consistency.

answered Aug 28, 2019 at 11:07

sn.anurag's user avatar


6077 silver badges14 bronze badges

I’m not sure about P for Mongo. Imagine situation:

  • Your replica gets split into two partitions.
  • Writes continue to both sides as new masters were elected
  • Partition is resolved — all servers are now connected again
  • What happens is that new master is elected — the one that has highest oplog, but the data from the other master gets reverted to the common state before partition and it is dumped to a file for manual recovery
  • all secondaries catch up with the new master

The problem here is that the dump file size is limited and if you had a partition for a long time you can loose your data forever.

You can say that it’s unlikely to happen — yes, unless in the cloud where it is more common than one may think.

This example is why I would be very careful before assigning any letter to any database. There’s so many scenarios and implementations are not perfect.

If anyone knows if this scenario has been addressed in later releases of Mongo please comment! (I haven’t been following everything that was happening for some time..)

answered Oct 10, 2015 at 10:16

kubal5003's user avatar


7,1668 gold badges52 silver badges90 bronze badges


Mongodb gives up availability. When we talk about availability in the context of the CAP theorem, it is about avoiding single points of failure that can go down. In mongodb. there is a primary router host. and if that goes down,there is gonna be some downtime in the time that it takes for it to elect a new replacement server to take its place. In practical, that is gonna happen very qucikly. we do have a couple of hot standbys sitting there ready to go. So as soon as the system detects that primary routing host went down, it is gonna switch over to a new one pretty much right away. Technically speaking it is still single point of failure. There is still a chance of downtime when that happens.

enter image description here

There is a config server, that is the primary and we have an app server, that is primary at any given time. even though we have multiple backups, there is gonna be a brief period of downtime if any of those servers go down. the system has to first detect that there was an outage and then remaining servers need to reelect a new primary host to take its place. that might take a few seconds and this is enough to say that mongodb is trading off the availability

answered Aug 1, 2022 at 0:48

Yilmaz's user avatar


28.5k10 gold badges136 silver badges170 bronze badges

MongoDB CAP theorem

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.
MongoDB CAP theorem

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.

Person holding cap in the air

Consistency Levels and the CAP/PACLEC Theorem

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

Image title

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

Image title

Further Reading

Consistency in Databases

Cloud-Native Applications and the CAP Theorem

Opinions expressed by DZone contributors are their own.

Have you ever seen an advertisement for a landscaper, house painter, or some other tradesperson that starts with the headline, “Cheap, Fast, and Good: Pick Two”?

The CAP theorem applies a similar type of logic to distributed systems—namely, that a distributed system can deliver only two of three desired characteristics: consistency, availability, and partition tolerance (the ‘C,’ ‘A’ and ‘P’ in CAP).

A distributed system is a network that stores data on more than one node (physical or virtual machines) at the same time. Because all cloud applications are distributed systems, it’s essential to understand the CAP theorem when designing a cloud app so that you can choose a data management system that delivers the characteristics your application needs most.

The CAP theorem is also called Brewer’s Theorem, because it was first advanced by Professor Eric A. Brewer during a talk he gave on distributed computing in 2000. Two years later, MIT professors Seth Gilbert and Nancy Lynch published a proof of “Brewer’s Conjecture.”

More on the ‘CAP’ in the CAP theorem

Let’s take a detailed look at the three distributed system characteristics to which the CAP theorem refers.


Consistency means that all clients see the same data at the same time, no matter which node they connect to. For this to happen, whenever data is written to one node, it must be instantly forwarded or replicated to all the other nodes in the system before the write is deemed ‘successful.’


Availability means that any client making a request for data gets a response, even if one or more nodes are down. Another way to state this—all working nodes in the distributed system return a valid response for any request, without exception.

Partition tolerance

A partition is a communications break within a distributed system—a lost or temporarily delayed connection between two nodes. Partition tolerance means that the cluster must continue to work despite any number of communication breakdowns between nodes in the system.

CAP theorem NoSQL database types

NoSQL databases are ideal for distributed network applications. Unlike their vertically scalable SQL (relational) counterparts, NoSQL databases are horizontally scalable and distributed by design—they can rapidly scale across a growing network consisting of multiple interconnected nodes. (See «SQL vs. NoSQL Databases: What’s the Difference?» for more information.)

Today, NoSQL databases are classified based on the two CAP characteristics they support:

  • CP database: A CP database delivers consistency and partition tolerance at the expense of availability. When a partition occurs between any two nodes, the system has to shut down the non-consistent node (i.e., make it unavailable) until the partition is resolved.
  • AP database: An AP database delivers availability and partition tolerance at the expense of consistency. When a partition occurs, all nodes remain available but those at the wrong end of a partition might return an older version of data than others. (When the partition is resolved, the AP databases typically resync the nodes to repair all inconsistencies in the system.)
  • CA database: A CA database delivers consistency and availability across all nodes. It can’t do this if there is a partition between any two nodes in the system, however, and therefore can’t deliver fault tolerance.

We listed the CA database type last for a reason—in a distributed system, partitions can’t be avoided. So, while we can discuss a CA distributed database in theory, for all practical purposes a CA distributed database can’t exist. This doesn’t mean you can’t have a CA database for your distributed application if you need one. Many relational databases, such as PostgreSQL, deliver consistency and availability and can be deployed to multiple nodes using replication.

MongoDB and the CAP theorem

MongoDB is a popular NoSQL database management system that stores data as BSON (binary JSON) documents. It’s frequently used for big data and real-time applications running at multiple different locations. Relative to the CAP theorem, MongoDB is a CP data store—it resolves network partitions by maintaining consistency, while compromising on availability.

MongoDB is a single-master system—each replica set (link resides outside can have only one primary node that receives all the write operations. All other nodes in the same replica set are secondary nodes that replicate the primary node’s operation log and apply it to their own data set. By default, clients also read from the primary node, but they can also specify a read preference (link resides outside that allows them to read from secondary nodes.

When the primary node becomes unavailable, the secondary node with the most recent operation log will be elected as the new primary node. Once all the other secondary nodes catch up with the new master, the cluster becomes available again. As clients can’t make any write requests during this interval, the data remains consistent across the entire network.

Cassandra and the CAP theorem (AP)

Apache Cassandra is an open source NoSQL database maintained by the Apache Software Foundation. It’s a wide-column database that lets you store data on a distributed network. However, unlike MongoDB, Cassandra has a masterless architecture, and as a result, it has multiple points of failure, rather than a single one.

Relative to the CAP theorem, Cassandra is an AP database—it delivers availability and partition tolerance but can’t deliver consistency all the time. Because Cassandra doesn’t have a master node, all the nodes must be available continuously. However, Cassandra provides eventual consistency by allowing clients to write to any nodes at any time and reconciling inconsistencies as quickly as possible.

As data only becomes inconsistent in the case of a network partition and inconsistencies are quickly resolved, Cassandra offers “repair” functionality to help nodes catch up with their peers. However, constant availability results in a highly performant system that might be worth the trade-off in many cases.

Microservices and the CAP theorem

Microservices are loosely coupled, independently deployable application components that incorporate their own stack—including their own database and database model—and communicate with each other over a network. As you can run microservices on both cloud servers and on-premises data centers, they have become highly popular for hybrid and multicloud applications.

Understanding the CAP theorem can help you choose the best database when designing a microservices-based application running from multiple locations. For example, if the ability to quickly iterate the data model and scale horizontally is essential to your application, but you can tolerate eventual (as opposed to strict) consistency, an AP database like Cassandra or Apache CouchDB can meet your requirements and simplify your deployment. On the other hand, if your application depends heavily on data consistency—as in an eCommerce application or a payment service—you might opt for a relational database like PostgreSQL.

Related solutions

Cloud databases on IBM Cloud

Explore the range of cloud databases offered by IBM to support a variety of use cases: from mission-critical workloads, to mobile and web apps, to analytics.

IBM Cloudant

IBM Cloudant is a scalable, distributed cloud database based on Apache CouchDB and used for web, mobile, IoT and serverless applications.

DataStax Enterprise with IBM

Get this scalable, highly available, cloud-native NoSQL database built on Apache Cassandra from IBM, your single source for purchase, deployment and support.


Take the next step

IBM Cloud database solutions offer a complete portfolio of managed services for data and analytics. Using a hybrid, open source-based approach, these solutions address the data-intensive needs of application developers, data scientists and IT architects. Hybrid databases create a distributed hybrid data cloud for increased performance, reach, uptime, mobility and cost savings.

Find your IBM Cloud database solution

Before we start relating MongoDB & CAP theorem, lets refresh our knowledge about CAP theorem.

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.

  • 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.

The reality is that you can have all three providing there are no network failures.

But the CAP theorem is largely based on the assumption that network failures are inevitable and will always occur. When such partitions occur, you must choose between either consistency or availability. When you choose consistency, error messages will result if database requests fail. When you choose availability, data will still be returned but may lack accuracy due to network failures.

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.

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.

Screen Shot 2019-11-22 at 12.42.00 PM.png

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

Рекомендация: подборка платных и бесплатных курсов таргетированной рекламе —

Следующая конференция HighLoad++ пройдет 6 и 7 апреля 2020 года в Санкт-Петербурге.
Подробности и билеты по ссылке. HighLoad++ Siberia 2019. Зал «Красноярск». 25 июня, 12:00. Тезисы и презентация.

Бывает, что практические требования конфликтуют с теорией, где не учтены важные для коммерческого продукта аспекты. В этом докладе представлен процесс выбора и комбинирования различных подходов к созданию компонентов Causal consistency на основе академических исследований исходя из требований коммерческого продукта. Слушатели узнают о существующих теоретических подходах к logical clocks, dependency tracking, system security, clock synchronization, и почему MongoDB остановились на тех или иных решениях.

Михаил Тюленев (далее – МТ): – Я буду рассказывать о Causal consistency – это фича, над которой мы работали в MongoDB. Я работаю в группе распределённых систем, мы её сделали примерно два года назад.

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

Я буду рассказывать о том, как мы, являясь потребителем академического Research, готовим из него что-то такое, что мы потом можем преподнести нашим пользователям в качестве готового блюда, которым удобно, безопасно пользоваться.

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

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

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

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

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

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

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

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

Модель Strong

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

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

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


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

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


Третья модель – это 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.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *