CRDT

0.5.0

Conflict-free Replicated Data Types in Swift
heckj/CRDT

What's New

Initial API release

2022-09-01T15:46:54Z

Initial API Release

  • Multiple well-known CRDT types included:
    • GCounter, PNCounter, GSet, ORSet, ORMap, and List
  • Documentation hosted at Swift Package Index
  • All included CRDT implementations support whole-instance merging and delta-state replication and merging.
  • APIs for merging include merged(:_) which implicitly makes a copy, and merging(:_) which modifies an in-place struct.
  • Corrupted history is identifier and thrown as an error, relevant for ORSet, ORMap, and List types.
  • Project includes basic benchmarks, with results available through the GitHub repo.
  • extended conformances for CRDT types, when underlying (and ActorID) types support it: Codable, Hashable, Equatable, and Sendable

What's Changed since the pre-release (0.5.0-alpha1)

New Contributors

Full Changelog: 0.5.0-alpha1...0.5.0

CRDT

An implementation of ∂-state based Conflict-free Replicated Data Types (CRDT) in the Swift language.

codecov

code coverage chart

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)

Alternatives

Other Swift implementations of CRDTs:

Two very well established CRDT libraries used for collaborative text editing:

Optimizations

Articles discussing tradeoffs, algorithm details, and performance, specifically for sequence based CRDTs:

Benchmarks

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

Current Benchmarks

Description

  • Swift Tools 5.6.0
View More Packages from this Author

Dependencies

Last updated: Tue Dec 10 2024 11:10:08 GMT-1000 (Hawaii-Aleutian Standard Time)