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.
- 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.)
- 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.
Documentation is available on docs.rs.
See this document for a detailed explanation of the design and implementation of Eips, including benchmarks measuring its performance and memory use.
The test-cli directory contains an interactive program that demonstrates the functionality of Eips.
Eips is licensed under version 3 of the GNU Affero General Public License, or (at your option) any later version. See LICENSE.
By contributing to Eips, you agree that your contribution may be used according to the terms of Eips’s license.