This crate provides a Rust implementation of DSON, a space-efficient, delta-state Conflict-Free Replicated Datatype (CRDT) for JSON-like data structures. It is based on the research paper "DSON: JSON CRDT Using Delta-Mutations For Document Stores" and started as a port of the original author's JavaScript implementation.
The primary goal of this library is to enable robust, and efficient multi-writer collaboration in extremely constrained environments (high latency and low bandwidth; opportunistic networking).
See also Helsing's announcement blog post.
DSON provides three fundamental, composable CRDTs:
OrMap: An Observed-Remove Map, mapping string keys to other CRDT values.OrArray: An Observed-Remove Array, providing a list-like structure.MvReg: A Multi-Value Register, for storing primitive values. When concurrent writes occur, the register holds all conflicting values.
These primitives can be nested to create arbitrarily complex data structures. All modifications produce a delta, which is a small set of changes that can be transmitted to other replicas.
DSON uses Observed-Remove (OR) semantics. This means an element can only be removed if its addition has been observed. If an element is updated concurrently with its removal, the update "wins" and the element is preserved.
DSON is a causal CRDT, using causal history to resolve conflicts. A key advantage of this model is the elimination of tombstones, which prevents unbounded metadata growth in long-lived documents.
This crate provides the core data structures and algorithms for DSON. It is a low-level library, and you will likely want to build a typed abstraction layer on top of it.
It does not include any networking protocols. You are responsible for implementing the transport layer to broadcast deltas to other replicas.
The initial version of this crate was based on the JavaScript implementation by the DSON paper authors.
The following people have contributed to this implementation:
This project is licensed under either of
- Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
- Talk on DSON and CRDTs - A presentation covering CRDTs in general and DSON in particular.
This repository provides a Nix development shell. If you have Nix installed, you can enter the shell by running:
nix developThis will provide you with a consistent development environment, including the correct Rust toolchain and other helpful dependencies.
In general, dson has very little dependencies, so you should expect to run cargo build/cargo test
just fine.
For a complete guide, including detailed explanations of the core concepts, advanced topics, and API usage, please refer to the generated docs.