swift-mrdt

An implementation of Mergeable Replicated Data Types (MRDTs) for Swift collection types, as introduced by Kaki et al. (OOPSLA 2019).

MRDTs, similar to CRDTs, are replicated data types that can be used safely in distributed settings to achieve convergence through merging concurrent changes. CRDTs typically achieve this by embedding the logic in specialized data structures that carry additional metadata (such as tombstones, vector clocks, or timestamps). MRDTs take a different approach: instead of introducing dedicated data structures, they operate on standard types and define a three-way merge function against the lowest common ancestor, much like version control systems merge branches.

This means there is no overhead of storing metadata alongside the data, and standard types can be used directly instead of specialized CRDT wrappers. When there are no concurrent changes, a newer version can simply replace the older one without requiring a merge. At the same time, MRDTs still guarantee convergence, ensuring that all replicas arrive at the same state regardless of merge order while preserving user intent. The trade-off is that the surrounding system must track version history and provide a common ancestor when performing a merge.

See also the introduction talk, which gives an overview of MRDTs and shows how to derive the merge function for a list¹ by composing the merge function of a set, an idea that served as the main inspiration for this library.

Usage

The library currently provides implementation for Set and Dictionary from the Standard Library and OrderedSet and OrderedDictionary from swift-collections.

Set

Merging two versions of a set keeps unchanged elements and applies additions and removals from both sides. No merge options are required.

let merged = Set.merge(
    base: ["a", "b"],
    left: ["a", "c"], // removed "b", added "c"
    right: ["a", "b", "d"] // added "d"
)
// => ["a", "c", "d"]

Ordered Set

Merging two versions of an ordered set works like set for members, but also preserves ordering changes (moves) from both sides.

let merged = OrderedSet.merge(
    base: ["a", "b", "c", "d"],
    left: ["b", "a", "c", "d"], // swapped "a" and "b"
    right: ["a", "b", "d", "c"], // swapped "c" and "d"
    options: .init(isOrderedBeforeWhenConflicting: <)
)
// => ["b", "a", "d", "c"]

A deterministic comparator is required to resolve ordering conflicts when the relative order of two elements cannot be determined from the merge inputs alone:

let merged = OrderedSet.merge(
    base: ["a", "b"],
    left: ["a", "b", "x"], // added "x"
    right: ["a", "b", "y"], // added "y"
    options: .init(isOrderedBeforeWhenConflicting: <)
)
// => ["a", "b", "x", "y"]

Dictionary

Merging two versions of a dictionary applies the set logic to keys and additionally merges values. Non-conflicting changes to values are applied automatically. A merge closure is required to resolve value conflicts when both sides changed the value for the same key.

let merged = Dictionary.merge(
    base: ["a": 1, "b": 2],
    left: ["a": 3, "b": 2, "c": 4], // changed "a", added "c"
    right: ["a": 5, "b": 2], // changed "a"
    options: .init(mergeValue: { left, right in max(left, right) })
)
// => ["a": 5, "b": 2, "c": 4]

For more control, separate closures can be provided for concurrent edits (where the base value is available) and concurrent insertions:

let merged = Dictionary.merge(
    base: ["a": 1],
    left: ["a": 3, "b": 10], // changed "a", added "b"
    right: ["a": 5, "b": 20], // changed "a", added "b"
    options: .init(
        mergeExistingValue: { base, left, right in
            base + (left - base) + (right - base)
        },
        mergeNewValue: { left, right in
            max(left, right)
        }
    )
)
// => ["a": 7, "b": 20]

Ordered Dictionary

Merging two versions of an ordered dictionary combines the ordered set logic for keys with the dictionary logic for values. Both a key ordering comparator and value merge closure(s) are required.

let merged = OrderedDictionary.merge(
    base: [1: "a", 2: "b", 3: "c"],
    left: [2: "b", 1: "x", 3: "c"], // moved key 2 before 1, changed value for 1
    right: [1: "y", 2: "b", 3: "c"], // changed value for 1
    options: .init(
        isKeyOrderedBeforeWhenConflicting: <,
        mergeValue: { left, right in [left, right].sorted().joined(separator: "|") }
    )
)
// => [2: "b", 1: "x|y", 3: "c"]

Installation

Add the package to your project using the Swift Package Manager, either through Xcode or a Package.swift manifest:

dependencies: [
    .package(url: "https://github.com/structuredpath/swift-mrdt", from: "1.0.0")
]

Then add the product to any target that needs it:

.target(
    name: "YourTarget",
    dependencies: [
        .product(name: "MRDT", package: "swift-mrdt")
    ]
)

License

This library is released under the MIT license. See LICENSE for details.

Footnotes

1. A list presented in the talk corresponds more closely to an OrderedSet than an Array, since elements with equal values are considered identical. ↩