An implementation of ∂-state based Conflict-free Replicated Data Types (CRDT) in the Swift language.
This library implements well-known state-based CRDTs as swift generics, sometimes described as convergent replicated data types (CvRDT). The implementation includes delta-state replication functions, which allows for more compact representations when syncing between collaboration endpoints. The alternative is to replicate the entire state for every sync.
The CRDT API documentation is hosted at the Swift Package Index.
- G-Counter (grow-only counter)
- PN-Counter (A positive-negative counter)
- LWW-Register (last write wins register)
- G-Set (grow-only set)
- OR-Set (observed-remove set, with LWW add bias)
- OR-Map (observed-remove map, with LWW add or update bias)
- List (causal-tree list)
For more, general, information on CRDTs, see the following sites and papers:
The implementations within this library were heavily based on algorithms described in Conflict-free Replicated Data Types by Nuno Preguiça, Carlos Baquero, and Marc Shapiro (2018)
Other Swift implementations of CRDTs:
- https://github.com/bluk/CRDT
- https://github.com/appdecentral/replicatingtypes
- https://github.com/jamztang/CRDT
- https://github.com/archagon/crdt-playground
- related article: Data Laced with History: Causal Trees & Operational CRDTs
- Obj.io's video series: https://talk.objc.io/episodes/S01E294-crdts-introduction
Two very well established CRDT libraries used for collaborative text editing:
- Automerge
- (video) CRDTs: The Hard Parts by Martin Kleppmann)
- Yjs (and its multi-language port Y-CRDT)
- Yrs data structure internals: https://bartoszsypytkowski.com/yrs-architecture/
Articles discussing tradeoffs, algorithm details, and performance, specifically for sequence based CRDTs:
- Delta-state CRDTs: indexed sequences with YATA
- 5000x faster CRDTs: An Adventure in Optimization
- CRDTs: The Hard Parts
Running the library:
swift run -c release crdt-benchmark library run Benchmarks/results.json --library Benchmarks/Library.json --cycles 5 --mode replace-all
swift run -c release crdt-benchmark library render Benchmarks/results.json --library Benchmarks/Library.json --output Benchmarks