Conflict-free Replicated Data Types in Swift

Joseph Heck

Last update: Dec 8, 2022

Related tags

Overview

CRDT

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

Overview

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 information on CRDTs, the Wikipedia page on CRDTs is quite good. I'd also suggest the website CRDT.tech as a wonderful collection of further resources. 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), and heavily influenced/sourced from the package ReplicatingTypes, created by Drew McCormack, used under license (MIT).

What's Different about this Package

The two most notable change from Drew's code are:

consistently exposing the type used to identify the collaboration instance (be that person, process, or machine) as a generic type
adding explicit delta-state transfer mechanisms so that you didn't need to transfer the entirety of a CRDT instance to another location in order to merge the data.

Like the ReplicatingTypes package, this package is available under the MIT license for you to use as you like, asking only for recognition that it was sourced.

If your goal is creating local-first software, this implementation is start, but (in my opinion) incomplete to those needs. In particular, there are none of the serialization optimizations included that would reduce the space needed by the instances when serialized in their entirety to be stored. There are also none of the optimizations that other libraries (for example Automerge or Yjs) that improve memory overhead needed to support longer-form collaborative text interactions.

These limitations may change in the future, and contributions are welcome.

Alternative Packages and Libraries

Other Swift implementations of CRDTs:

https://github.com/appdecentral/replicatingtypes
- related article: Conflict-Free Replicated Data Types (CRDTs) in Swift
https://github.com/bluk/CRDT
https://github.com/jamztang/CRDT
https://github.com/archagon/crdt-playground
- related article: Data Laced with History: Causal Trees & Operational CRDTs
Objc.io video series: CRDTs – Introduction

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

Automerge
- (video) CRDTs: The Hard Parts by Martin Kleppmann)
Y.js (and its multi-language port Y-CRDT)
- Yrs data structure internals: https://bartoszsypytkowski.com/yrs-architecture/

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

Comments

Documentation updates

initial state:

   --- Experimental coverage output enabled. ---
                | Abstract        | Curated         | Code Listing
Types           | 80% (16/20)     | 55% (11/20)     | 0.0% (0/20)
Members         | 45% (36/80)     | 45% (36/80)     | 0.0% (0/80)
Globals         | 0.0% (0/31)     | 77% (24/31)     | 0.0% (0/31)

opened by heckj 3

Remove comparable
removes mandatory Comparable conformance for ActorID generic

stubs in some concrete CRDT implementations with pre-chosen ActorID types - UInt64 and UUID

adds a benchmark comparison script

adds (swift 5.7+ only) full swift concurrency checking for swift6 warnings and presets
opened by heckj 1
Additional checking for error states in merging related, and unrelated, CRDT instances

Thinking through #13 some more, I realized scenarios where the merge should more likely throw than directly copy without error. The DeltaCRDT protocol has been updated to now support throwing on merging deltas, specifically for the scenario where there is conflicting historical data for the existing CRDT that's merging in a delta.

opened by heckj 0
add CustomStringConvertible to types...

Debugging the internals is kind of messy and verbose when using the default string interpolation, so I think there'd be some benefit to adding CustomStringConvertible conformance to a number of the types, especially around state and delta generation for the CRDTs.
enhancement

opened by heckj 0
additional merging tests

resolves #13

The core issue was that I was attempting to merge two different sets with the same ActorID. When updated to properly reflect independent instances, it was fine.

opened by heckj 0

ORSet and GSet need more replication verification tests

While looking at sizing numbers, I ran across the following delta's and numbers (GSet and ORSet):

let orset_1 = ORSet(actorId: UInt(31), [1, 2, 3, 4])
let orset_2 = ORSet(actorId: UInt(31), [4, 5])

print("ORSet1(4 elements, UInt actorId) = \(orset_1.sizeInBytes())")
print("ORSet2(2 elements, UInt actorId) = \(orset_2.sizeInBytes())")
print("ORSet1's state size: \(orset_1.state.sizeInBytes())")
print("ORSet2's state size: \(orset_1.state.sizeInBytes())")
print("Delta size of Set1 merging into Set2: \(orset_2.delta(orset_1.state).sizeInBytes())")
print("Delta size of Set2 merging into Set1: \(orset_1.delta(orset_2.state).sizeInBytes())")

Delta Numbers for GSet:

GSet1(4 elements, UInt actorId) = 64
GSet2(2 elements, UInt actorId) = 40
GSet1's state size: 48
GSet2's state size: 48
Delta size of Set1 merging into Set2: 24
Delta size of Set2 merging into Set1: 40

Delta Numbers for ORSet:

ORSet1(4 elements, UInt actorId) = 116
ORSet2(2 elements, UInt actorId) = 66
ORSet1's state size: 16
ORSet2's state size: 16
Delta size of Set1 merging into Set2: 0
Delta size of Set2 merging into Set1: 50

The 0 in set1 merging into set2 is a notable issue - means something in the delta/state computation logic is screwed up. ORSet has fairly complicated state, delta, and diffing logic - so best to work the corners there and verify its all operating as expected.

bug

opened by heckj 0

Releases(0.5.0)

0.5.0(Sep 1, 2022)
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)

Additional checking for error states in merging related, and unrelated, CRDT instances by @heckj in https://github.com/heckj/CRDT/pull/16

String convertible by @heckj in https://github.com/heckj/CRDT/pull/17

ORmap by @heckj in https://github.com/heckj/CRDT/pull/18

Example code baseline by @heckj in https://github.com/heckj/CRDT/pull/19

additional use cases of replication tests by @heckj in https://github.com/heckj/CRDT/pull/20

Sendable by @heckj in https://github.com/heckj/CRDT/pull/21

adding stub article for details about replicating content by @heckj in https://github.com/heckj/CRDT/pull/22

basic benchmarks by @heckj in https://github.com/heckj/CRDT/pull/23

Causal Tree List by @heckj in https://github.com/heckj/CRDT/pull/24

Update .spi.yml by @finestructure in https://github.com/heckj/CRDT/pull/26

New Contributors

@finestructure made their first contribution in https://github.com/heckj/CRDT/pull/26

Full Changelog: https://github.com/heckj/CRDT/compare/0.5.0-alpha1...0.5.0
Source code(tar.gz)
Source code(zip)
0.5.0-alpha1(Aug 24, 2022)
Initial alpha release.

The pre-release includes an initial implementation, API, and documentation for the raw CRDT data types:

GCounter

PNCounter

LWWRegister

GSet

ORSet

The pre-release is intended for feedback on API usage, and should not be considered stable. The delta-state merge methods are set to asynchronous, and both an ORMap and an actor-based replicator wrapper is still pending as of this release.

To use this release, add the following dependency to your Package.swift:

.package(url: "https://github.com/heckj/CRDT.git", from:"0.5.0-alpha1")
Source code(tar.gz)
Source code(zip)

Owner

Joseph Heck

GitHub https://swiftpackageindex.com/heckj/CRDT/main/documentation/crdt

PGPro can encrypt and decrypt messages as well as manage all your OpenPGP keys. It is free, simple and lightweight. Everything stays on your device. PGPro is made in Switzerland.

PGPro can encrypt and decrypt messages as well as manage all your OpenPGP keys. It is free, simple and lightweight. Everything stays on your device. P

250 Jan 4, 2023

Easy to use cryptographic framework for data protection: secure messaging with forward secrecy and secure data storage. Has unified APIs across 14 platforms.

Themis provides strong, usable cryptography for busy people General purpose cryptographic library for storage and messaging for iOS (Swift, Obj-C), An

1.6k Dec 30, 2022

Valet lets you securely store data in the iOS, tvOS, or macOS Keychain without knowing a thing about how the Keychain works.

Valet Valet lets you securely store data in the iOS, tvOS, watchOS, or macOS Keychain without knowing a thing about how the Keychain works. It’s easy.

3.8k Jan 4, 2023

To Practice UINavigationController, transition, ViewController Life Cycle, send data to different page, asset catalogs

LED Board Check Point ! StackView 여러개의 view 를 set 으로 만들어 주는 역활을 함 일정한 규칙에 따라서 stack view 안에 움직이는것임 이미지 넣기 프로젝트 내에 Assets 폴더 내에 Image Set 을 추가하여 1x, 2x

0 Dec 5, 2021

Simple, secure password and data management for individuals and teams

Padloc Simple, secure password and data management for individuals and teams (formerly known as Padlock). This repo is split into multiple packages: P

2.1k Jan 8, 2023

RSA public/private key encryption, private key signing and public key verification in Swift using the Swift Package Manager. Works on iOS, macOS, and Linux (work in progress).

BlueRSA Swift cross-platform RSA wrapper library for RSA encryption and signing. Works on supported Apple platforms (using Security framework). Linux

122 Dec 16, 2022

RSA public/private key encryption, private key signing and public key verification in Swift using the Swift Package Manager. Works on iOS, macOS, and Linux (work in progress).

BlueRSA Swift cross-platform RSA wrapper library for RSA encryption and signing. Works on supported Apple platforms (using Security framework). Linux

122 Dec 16, 2022

Conflict-free Replicated Data Types in Swift

Related tags

Overview

CRDT

Overview

What's Different about this Package

Alternative Packages and Libraries

Optimizations

Benchmarks

Comments

Documentation updates

Remove comparable

Additional checking for error states in merging related, and unrelated, CRDT instances

add CustomStringConvertible to types...

additional merging tests

ORSet and GSet need more replication verification tests

Releases(0.5.0)

0.5.0(Sep 1, 2022)

Initial API Release

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

New Contributors

0.5.0-alpha1(Aug 24, 2022)

Owner

Joseph Heck

PGPro can encrypt and decrypt messages as well as manage all your OpenPGP keys. It is free, simple and lightweight. Everything stays on your device. PGPro is made in Switzerland.

Easy to use cryptographic framework for data protection: secure messaging with forward secrecy and secure data storage. Has unified APIs across 14 platforms.

Valet lets you securely store data in the iOS, tvOS, or macOS Keychain without knowing a thing about how the Keychain works.

To Practice UINavigationController, transition, ViewController Life Cycle, send data to different page, asset catalogs

Simple, secure password and data management for individuals and teams

RSA public/private key encryption, private key signing and public key verification in Swift using the Swift Package Manager. Works on iOS, macOS, and Linux (work in progress).

RSA public/private key encryption, private key signing and public key verification in Swift using the Swift Package Manager. Works on iOS, macOS, and Linux (work in progress).

Swift-problem-solving - Swift 알고리즘 맛보기 😋

Swift-cuckoo-collections - Cross-platform Swift dictionaries & sets that use a cuckoo hashing algorithm

Helps you define secure storages for your properties using Swift property wrappers.

Swift cross-platform crypto library using CommonCrypto/libcrypto

CryptoSwift is a growing collection of standard and secure cryptographic algorithms implemented in Swift

A wrapper for Apple's Common Crypto library written in Swift.

A framework for the JOSE standards JWS, JWE, and JWK written in Swift.

CCCryptor (AES encryption) wrappers for iOS and Mac in Swift. -- For ObjC, see RNCryptor/RNCryptor-objc

Elegant Swift interface to access the CommonCrypto routines

Simple and secure hashing in Swift with the SipHash algorithm

Simple Swift wrapper for Keychain that works on iOS, watchOS, tvOS and macOS.

A simple Swift Keychain Wrapper for iOS, watchOS, and OS X.