Crate eips

Eips is the efficient intention-preserving sequence: a sequence CRDT with worst-case non-amortized logarithmic-time operations, minimal memory usage, and no issues with interleaving concurrent insertions or duplicating moved elements as seen in some other CRDTs.

Features

• No interleaving of characters when multiple users insert text at the same position, even when text is typed in reverse (by typing a letter, moving the cursor back one, typing the next letter, etc.)
• Support for move operations. Items can be moved to another position in the sequence and will not be duplicated if multiple users try to move the same item concurrently.
• Insertions, deletions, moves, and accesses are worst-case non-amortized O(log h), where h is the total number of items ever inserted in the document.
• Constant memory use per item. Even as the editing history grows, and even with huge numbers of clients and concurrent edits, changes always use the same amount of memory. This applies to the number of bytes it takes to communicate changes to other clients, too.
• The CRDT structure doesn’t store items directly, but rather translates between local changes (which use simple integer indices) and remote changes (which use IDs and are suitable for sending over a network). This means the items themselves may be stored in any plain list-like type, such as a simple growable array (Vec) or an unsorted counted B-tree like btree-vec. The time complexity of local operations on the sequence then depends only on the number of visible items—tombstones don’t cause a performance penalty.
• Simple API. Three functions provide the ability to insert, delete, and move elements, and one function applies changes from remote clients. A basic use case won’t need much else. (Also, the function that applies changes is the only one that can mutate the CRDT structure, making it easy to reason about the state of the document.)

Requirements

• As with many sequence CRDTs, Eips assumes changes are delivered in causal order.
• Clients must be capable of generating unique IDs. If each client already has a unique client ID, a common approach is to use (client-id, counter) pairs, where counter is a simple per-client increasing integer. UUIDs may be used in cases where this isn’t possible.

Design

See this document for a detailed explanation of the design and implementation of Eips, including benchmarks measuring its performance and memory use.

Crate features

When the crate feature serde is enabled, RemoteChange (and types it contains) will implement Serde’s Serialize and Deserialize traits.

This crate can be used in no_std contexts by disabling the std feature with default-features = false. In this case, at least one of allocator-fallback or allocator_api (unstable) must be enabled.

Re-exports

pub use change::LocalChange;

pub use change::RemoteChange;

pub use options::EipsOptions;

pub use options::Options;

Modules

change

Types representing remote and local changes.

error

Error types.

iter

Iterators.

options

Options for Eips.

Structs

Eips

An intention-preserving sequence CRDT.

Traits

Id

The trait that ID types must implement.