MongoDB may achieve STRONGER causal consistency guarantee?

[Si_Liu]

We’ve been extensively testing MongoDB against causal consistency, following the config given at https://docs.mongodb.com/manual/core/read-isolation-consistency-recency/#std-label-sessions (e.g., majority reads + majority writes).

The causal consistency property we have been checking is actually a stronger notion (see below) of causal consistency claimed by MongoDB. So far, we found NO violation. This roused our curiosity: What exactly the causal consistency guarantee MongoDB actually implements?

*** Background on causal consistency (CC) ***
There are several notions of CC in the literature.

The weakest notion of CC, currently claimed by MongoDB, is considered as a combination of four session guarantees: “Read your writes”, “Monotonic reads”, “Monotonic writes”, and “Writes follow reads”. See the above link for details.

A stronger notion of CC, adopted by many industrial and academic cloud DBs, is called causal+, originally proposed (as far as I know) in the SOSP’11 paper “Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS”. In addition to the above four guarantees, causal+ takes into account convergent conflict handling. More specifically, I quote the definition from the POPL’17 paper “On verifying causal consistency”:

“There is a total order between non-causally dependent operations and each site can execute operations only in that order (when it sees them). Therefore, a site is not allowed to revise its ordering of non-causally dependent operations, and all sites execute in the same order the operations that are visible to them.”

Causal+ is definitely more attractive. Below is an example taken from the SOSP paper:

" … consider an example where Carol and Dan both update the starting time for an event. The time was originally set for 9pm, Carol changed it to 8pm, and Dan concurrently changed it to 10pm. Regular causal consistency would allow two different replicas to forever return different times, even after receiving both put operations. Causal+ consistency requires that replicas handle this conflict in a convergent manner. If a last-writer-wins policy is used, then either Dan’s 10pm or Carol’s 8pm would win …"
*** End ***

A quick takeaway from the SOSP paper is that “last-writer-wins” can handle convergent conflict. Coincidently, I found sth interesting here https://docs.mongodb.com/realm/sync/learn/conflict-resolution/ MongoDB claims to support “Last update wins”, though I haven’t got time to connect it to MongoDB’s causal consistency implementation.

It would be great to clarify this issue to benefit MongoDB applications! Thanks!

[A_Jesse_Jiryu_Davis]

I haven’t read the causal+ definition in detail, but I think you’re probably correct that MongoDB implements causal+, the same as most other systems that claim causal consistency.

It’s not possible in a MongoDB replica set for “two different replicas to forever return different times”. MongoDB replicas are eventually consistent. They may diverge temporarily if there are two primaries for a short period during a network partition, but eventually when the partition heals, one primary’s writes will be rolled back. A single history of writes will survive on all nodes (represented by the oplog).

In the manual page linked above, we recommend read concern “majority”. This means the client reads only majority-replicated writes, which will not be rolled back, so it will never see the results of conflicting writes. It won’t even see conflicting writes if it reads from multiple nodes and if there is a two-primary scenario.

I think that most causal systems are causal+ for the same reason as MongoDB: they all use a single totally-ordered log to represent history, and all nodes’ copies of this log are eventually consistent.

Note, Realm Sync page you linked to is about a different product from MongoDB replica sets, it’s not closely related to our causal consistency implementation. Its conflict resolution rules aren’t relevant to your question. In replica sets, all writes are ordered on the primary and we don’t need the kind of conflict resolution that Realm Sync does.

[Si_Liu]

Thanks for the clarification, Jesse! Indeed, as you described, MongoDB should be implementing causal+. It is interesting that, quite often, when people saw causal consistency claimed, they had the weaker notion in their minds, and if they did want convergence + causality, they would look for an overkill like Snapshot Isolation.