Conflict-free Replicated Data Types in Swift

Overview

CRDT

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

codecov

code coverage chart

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:

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

Comments
  • Documentation updates

    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
  • Additional checking for error states in merging related, and unrelated, CRDT instances

    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...

    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

    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

    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)
PassDrop is a fully-featured secure password management system, compatible with the free KeePass 1.x (Classic) and multi-platform KeePassX desktop applications.

passdrop This is a modern, updated build of Rudis Muiznieks's PassDrop application. PassDrop is a fully-featured secure password management system, co

Chad Austin 32 Feb 23, 2022
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

Cossack Labs 1.6k Sep 21, 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.

Square 3.8k Sep 20, 2022
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

Jacob Ko 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

Padloc 1.9k Sep 24, 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

Kitura 120 Sep 21, 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

Kitura 121 Jul 8, 2022
Swift-problem-solving - Swift 알고리즘 맛보기 😋

swift-problem-solving Swift 로 알고리즘 익히기 ?? Programmers 난이도 풀이 문제 바로가기 Lv.2 오픈채팅방 링크 Lv.3 다단계 칫솔 판매 링크 Lv.3 합승 택시 요금 링크 Leetcode 난이도 풀이 문제 바로가기 Medium 1

jegyun 3 Jan 6, 2022
Swift-cuckoo-collections - Cross-platform Swift dictionaries & sets that use a cuckoo hashing algorithm

CuckooCollections A Swift package for open-addressed sets and dictionaries that

Christopher Richez 0 Aug 2, 2022
Helps you define secure storages for your properties using Swift property wrappers.

?? Secure Property Storage Helps you define secure storages for your properties using Swift property wrappers. ?? Features All keys are hashed using S

Alex Rupérez 435 Aug 30, 2022
Swift cross-platform crypto library using CommonCrypto/libcrypto

BlueCryptor Swift cross-platform crypto library derived from IDZSwiftCommonCrypto. IMPORTANT NOTE: This release is NOT entirely source code compatible

Kitura 181 Aug 16, 2022
CryptoSwift is a growing collection of standard and secure cryptographic algorithms implemented in Swift

CryptoSwift Crypto related functions and helpers for Swift implemented in Swift. (#PureSwift) Note: The master branch follows the latest currently rel

Marcin Krzyzanowski 9.2k Sep 23, 2022
A wrapper for Apple's Common Crypto library written in Swift.

IDZSwiftCommonCrypto A Swift wrapper for Apple's CommonCrypto library. IDZSwiftCommonCrypto works with both CocoaPods and Cathage. For more details on

idz 469 Sep 3, 2022
A framework for the JOSE standards JWS, JWE, and JWK written in Swift.

JOSESwift is a modular and extensible framework for the JOSE standards JWS, JWE, and JWK written in Swift. ?? Please note that this implementation of

Airside Mobile, Inc. 157 Aug 8, 2022
CCCryptor (AES encryption) wrappers for iOS and Mac in Swift. -- For ObjC, see RNCryptor/RNCryptor-objc

RNCryptor Cross-language AES Encryptor/Decryptor data format. The primary targets are Swift and Objective-C, but implementations are available in C, C

null 3.3k Sep 19, 2022
Elegant Swift interface to access the CommonCrypto routines

SCrypto [Overview • Requirements • Installation • Usage • Alternatives • Licence] Overview SCrypto provides neat Swift interface to access the CommonC

Max 39 Mar 31, 2022
Simple and secure hashing in Swift with the SipHash algorithm

SipHash ⚠️ WARNING This package has been obsoleted by the Hasher type and the Hashable.hash(into:) requirement introduced in Swift 4.2. Using this pac

null 260 Jul 23, 2022
Simple Swift wrapper for Keychain that works on iOS, watchOS, tvOS and macOS.

KeychainAccess KeychainAccess is a simple Swift wrapper for Keychain that works on iOS and OS X. Makes using Keychain APIs extremely easy and much mor

Kishikawa Katsumi 7k Sep 26, 2022
A simple Swift Keychain Wrapper for iOS, watchOS, and OS X.

Latch A simple Swift 2.0 Keychain Wrapper for iOS, watchOS 2, and OS X. Usage A proper example of how to use Latch can be seen in the tests. import La

Danielle 57 Jan 29, 2022