Consistency Models
This article explains how data propagates among offline peers, data conflicts resulting from multiple offline edits to the same data --- known as concurrency conflicts -- and how Ditto resolves them using specialized data types: REGISTER, MAP, and ATTACHMENT.
To summarize, Ditto's causal consistency feature ensures consistency across related changes by allowing concurrent messages to appear in any order while maintaining consistency.
In Ditto's decentralized architecture, data propagates asynchronously among offline peers, eliminating the need for a centralized authority like a central server to validate and merge database operations.
This decentralized model, however, presents the possibility of concurrency conflicts. A concurrency conflict happens when multiple end users make changes to the same data items at the same time. When merging these changes, any inconsistencies collide.
To resolve concurrency collisions at merge, Ditto turns to conflict-free replicated data type (CRDT) technology. CRDT is an advanced class of data type designed to manage and replicate data changes in a way that allows multiple distributed peers to make updates concurrently without needing to reach a consensus to form a single meaningful value for merge.
For an overview of the different CRDTs that Ditto offers, see REGISTER, MAP, and ATTACHMENT.
The following scenario provides a walkthrough of the mechanics of version vectors, their role in determining merging behavior, and how different peers contribute to data replication:
The HLC uses the UInt128 data type to represent the Site_ID and 64bit timestamp in Ditto; however, for simplicity, the following scenario uses basic string and number types instead.
Local Peer A document: 123abc links to a version vector that indicates:
- Its locally-stored document is currently at vector version 5.
- The most recent incoming Remote Peer B changes were incorporated and merged at version 1.
- The Remote Peer C changes were incorporated and merged at vector version 4.
Local Peer A receives document changes from remote Peer B. The incoming document's version vector indicates:
- The remote Peer B incoming version vector is value 4.
- The most recent incoming Remote Peer B changes were of version 1; a value less than the incoming document version vector value of 4.
Since 4 is greater than 1, the local Peer A determines that the changes are new and should be incorporated and merged in order to remain consistent.
Guaranteed by Ditto, causal consistency ensures that changes are causally consistent across multiple documents and different collections within the same Ditto appID.
To give an intuition about causal consistency, imagine the following scenario:
On a social network, Bob posts a message:
Then after some time, he posts:
To which Sue replies:
In contrast, an eventually consistent database shows messages in any order:
Ditto's Causal Consistency ensures that if a new message is written after seeing some prior message, then the new message is not visible unless that prior message is also visible.
To help differentiate Causal Consistency from stronger consistency models, imagine that Alice replies:
Causal Consistency allows the two concurrent messages "Great news!" from Sue and "Wonderful!" from Alice to appear in any order. Both of the following results are valid with Causal Consistency:
And: