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 within 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 item size. Memory use per item is fixed, even as editing history grows; the same applies to the number of bytes needed to communicate changes to other clients.
• Resistance to malicious actors. Eips has no pathological cases that could suddenly decrease performance—time complexity is strictly logarithmic, and space complexity strictly linear—and malicious input can’t cause Eips to crash.
• Data-agnostic design: the CRDT structure doesn’t store items directly, but rather translates between local changes that use integer indices, and remote changes that use stable IDs, enabling the items themselves to be stored in any list-like structure, like a simple growable array or counted B-tree. This also speeds up local operations like searching, as tombstones don’t cause a performance penalty.
• Simple API. An edit begins by calling insert, remove, or mv, which instead of mutating the document directly, returns a remote change object describing the operation. Once the object is passed to apply_change, and sent to any network-connected peers, the edit is complete.

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.

Documentation

Documentation is available on docs.rs.

Design

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

Demo

The test-cli directory contains an interactive program that demonstrates the functionality of Eips.

License

Eips is licensed under version 3 of the GNU Affero General Public License, or (at your option) any later version. See LICENSE.

In addition, the Eips Lesser Network Exception and Eips Peer-to-Peer Exception apply to Eips. These exceptions are additional permissions under section 7 of the GNU AGPL, version 3; as such, if you modify Eips, you may choose whether to extend them to your modified version. For more information about these exceptions, see this repository.

Please note that you do not have to license your project under the AGPL if you use Eips. Your project can be licensed under any AGPLv3-compatible license, including nearly all permissive licenses such as MIT or Apache 2.0. The terms of the AGPL will apply only to the combination of your project with Eips (e.g., source code must be provided along with any compiled binaries); any portion of your project that does not depend on Eips may be used without adherence to the AGPL.

Contributing

By contributing to Eips, you agree that your contribution may be used according to the terms of Eips’s license, including the Eips Lesser Network Exception and Eips Peer-to-Peer Exception.

Footnotes

1. Pronounced /aɪps/ (rhymes with “types”). ↩