#crdt #data #structure #user #concurrently #modified #different #automatically

automerge

A JSON-like data structure (a CRDT) that can be modified concurrently by different users, and merged again automatically

4 releases (breaking)

0.3.0 Jan 30, 2023
0.2.0 Nov 27, 2022
0.1.0 Aug 10, 2022
0.0.2 Dec 28, 2019

#150 in Data structures

Download history 302/week @ 2022-11-25 139/week @ 2022-12-02 554/week @ 2022-12-09 596/week @ 2022-12-16 62/week @ 2022-12-23 320/week @ 2022-12-30 710/week @ 2023-01-06 533/week @ 2023-01-13 590/week @ 2023-01-20 359/week @ 2023-01-27 798/week @ 2023-02-03 477/week @ 2023-02-10 384/week @ 2023-02-17 540/week @ 2023-02-24 597/week @ 2023-03-03 586/week @ 2023-03-10

2,138 downloads per month
Used in 7 crates

MIT license

1MB
22K SLoC

Automerge

Automerge is a library of data structures for building collaborative local-first applications. This is the Rust implementation. See automerge.org


lib.rs:

Automerge

Automerge is a library of data structures for building collaborative, local-first applications. The idea of automerge is to provide a data structure which is quite general, - consisting of nested key/value maps and/or lists - which can be modified entirely locally but which can at any time be merged with other instances of the same data structure.

In addition to the core data structure (which we generally refer to as a "document"), we also provide an implementation of a sync protocol (in [crate::sync]) which can be used over any reliable in-order transport; and an efficient binary storage format.

This crate is organised around two representations of a document - [Automerge] and [AutoCommit]. The difference between the two is that [AutoCommit] manages transactions for you. Both of these representations implement [ReadDoc] for reading values from a document and [sync::SyncDoc] for taking part in the sync protocol. [AutoCommit] directly implements [transaction::Transactable] for making changes to a document, whilst [Automerge] requires you to explicitly create a [transaction::Transaction].

NOTE: The API this library provides for modifying data is quite low level (somewhat analogous to directly creating JSON values rather than using serde derive macros or equivalent). If you're writing a Rust application which uses automerge you may want to look at autosurgeon.

Data Model

An automerge document is a map from strings to values ([Value]) where values can be either

  • A nested composite value which is either
    • A map from strings to values ([ObjType::Map])
    • A list of values ([ObjType::List])
    • A text object (a sequence of unicode characters) ([ObjType::Text])
  • A primitive value ([ScalarValue]) which is one of
    • A string
    • A 64 bit floating point number
    • A signed 64 bit integer
    • An unsigned 64 bit integer
    • A boolean
    • A counter object (a 64 bit integer which merges by addition) ([ScalarValue::Counter])
    • A timestamp (a 64 bit integer which is milliseconds since the unix epoch)

All composite values have an ID ([ObjId]) which is created when the value is inserted into the document or is the root object ID [ROOT]. Values in the document are then referred to by the pair (object ID, key). The key is represented by the [Prop] type and is either a string for a maps, or an index for sequences.

Conflicts

There are some things automerge cannot merge sensibly. For example, two actors concurrently setting the key "name" to different values. In this case automerge will pick a winning value in a random but deterministic way, but the conflicting value is still available via the [ReadDoc::get_all] method.

Change hashes and historical values

Like git, points in the history of a document are identified by hash. Unlike git there can be multiple hashes representing a particular point (because automerge supports concurrent changes). These hashes can be obtained using either [Automerge::get_heads] or [AutoCommit::get_heads] (note these methods are not part of [ReadDoc] because in the case of [AutoCommit] it requires a mutable reference to the document).

These hashes can be used to read values from the document at a particular point in history using the various *_at methods on [ReadDoc] which take a slice of [ChangeHash] as an argument.

Actor IDs

Any change to an automerge document is made by an actor, represented by an [ActorId]. An actor ID is any random sequence of bytes but each change by the same actor ID must be sequential. This often means you will want to maintain at least one actor ID per device. It is fine to generate a new actor ID for each change, but be aware that each actor ID takes up space in a document so if you expect a document to be long lived and/or to have many changes then you should try to reuse actor IDs where possible.

Text Encoding

Both [Automerge] and [AutoCommit] provide a with_encoding method which allows you to specify the [crate::TextEncoding] which is used for interpreting the indexes passed to methods like [ReadDoc::list_range] or [transaction::Transactable::splice]. The default encoding is UTF-8, but you can switch to UTF-16.

Sync Protocol

See the [sync] module.

Serde serialization

Sometimes you just want to get the JSON value of an automerge document. For this you can use [AutoSerde], which implements serde::Serialize for an automerge document.

Example

Let's create a document representing an address book.

use automerge::{ObjType, AutoCommit, transaction::Transactable, ReadDoc};

# fn main() -> Result<(), Box<dyn std::error::Error>> {
let mut doc = AutoCommit::new();

// `put_object` creates a nested object in the root key/value map and
// returns the ID of the new object, in this case a list.
let contacts = doc.put_object(automerge::ROOT, "contacts", ObjType::List)?;

// Now we can insert objects into the list
let alice = doc.insert_object(&contacts, 0, ObjType::Map)?;

// Finally we can set keys in the "alice" map
doc.put(&alice, "name", "Alice")?;
doc.put(&alice, "email", "alice@example.com")?;

// Create another contact
let bob = doc.insert_object(&contacts, 1, ObjType::Map)?;
doc.put(&bob, "name", "Bob")?;
doc.put(&bob, "email", "bob@example.com")?;

// Now we save the address book, we can put this in a file
let data: Vec<u8> = doc.save();
# Ok(())
# }

Now modify this document on two separate devices and merge the modifications.

use std::borrow::Cow;
use automerge::{ObjType, AutoCommit, transaction::Transactable, ReadDoc};

# fn main() -> Result<(), Box<dyn std::error::Error>> {
# let mut doc = AutoCommit::new();
# let contacts = doc.put_object(automerge::ROOT, "contacts", ObjType::List)?;
# let alice = doc.insert_object(&contacts, 0, ObjType::Map)?;
# doc.put(&alice, "name", "Alice")?;
# doc.put(&alice, "email", "alice@example.com")?;
# let bob = doc.insert_object(&contacts, 1, ObjType::Map)?;
# doc.put(&bob, "name", "Bob")?;
# doc.put(&bob, "email", "bob@example.com")?;
# let saved: Vec<u8> = doc.save();

// Load the document on the first device and change alices email
let mut doc1 = AutoCommit::load(&saved)?;
let contacts = match doc1.get(automerge::ROOT, "contacts")? {
    Some((automerge::Value::Object(ObjType::List), contacts)) => contacts,
    _ => panic!("contacts should be a list"),
};
let alice = match doc1.get(&contacts, 0)? {
   Some((automerge::Value::Object(ObjType::Map), alice)) => alice,
   _ => panic!("alice should be a map"),
};
doc1.put(&alice, "email", "alicesnewemail@example.com")?;


// Load the document on the second device and change bobs name
let mut doc2 = AutoCommit::load(&saved)?;
let contacts = match doc2.get(automerge::ROOT, "contacts")? {
   Some((automerge::Value::Object(ObjType::List), contacts)) => contacts,
   _ => panic!("contacts should be a list"),
};
let bob = match doc2.get(&contacts, 1)? {
  Some((automerge::Value::Object(ObjType::Map), bob)) => bob,
  _ => panic!("bob should be a map"),
};
doc2.put(&bob, "name", "Robert")?;

// Finally, we can merge the changes from the two devices
doc1.merge(&mut doc2)?;
let bobsname: Option<automerge::Value> = doc1.get(&bob, "name")?.map(|(v, _)| v);
assert_eq!(bobsname, Some(automerge::Value::Scalar(Cow::Owned("Robert".into()))));

let alices_email: Option<automerge::Value> = doc1.get(&alice, "email")?.map(|(v, _)| v);
assert_eq!(alices_email, Some(automerge::Value::Scalar(Cow::Owned("alicesnewemail@example.com".into()))));
# Ok(())
# }

Dependencies

~2.5–5.5MB
~111K SLoC