Binary Document Format

The chunk type is either:

The fields in a document chunk, in order, are:

A document contains a set of changes that represent the history of a collaboratively edited document. A document always contains a complete history of changes: for each change in the document, all the changes that were made to the document before that change was made are also included.

Document chunks use a columnar storage format for both changes and operations that assumes that the values of various fields are similar across adjacent changes and operations to optimize for high compression ratios and fast decoding.

Most fields are of arbitrary length, so parsing the document must proceed in order; for example it is not possible to know the length of the column fields until the column metadata has been parsed.

By implication, a document with no changes consists of 0x00 0x00 0x00 0x00, as the counts of actors, heads, change columns and operations columns are all zero. With the chunk header, this gives a file consisting of the following bytes: 0x85 0x6f 0x4a 0x83 0xb8 0x1a 0x95 0x44 0x00 0x04 0x00 0x00 0x00 0x00.

The fields in a change chunk, in order, are:

A change chunk just contains a single change, its metadata and operations. It does not include any dependent changes, so you can only apply the change to a document that already contains those dependent changes.

Change chunks use a columnar storage format that assumes that the values of various fields are similar across adjacent operations to optimize for high compression ratios and fast decoding.

The extra bytes must be retained when processing changes. If future versions of automerge add new metadata to changes, this will allow old clients to collaborate with new clients without limiting which features the new clients can use.

A compressed change chunk is a change chunk where the contents have been compressed using [DEFLATE]. The checksum of a compressed chunk is calculated as through the chunk was not compressed (with type = 1, the length of the uncompressed data, and the original uncompressed data).

For example if you have a change which has 372 bytes of data (excluding the header) which compresses to 323 bytes. If the original change chunk header consisted of the following bytes: 0x85 0x6f 0x4a 0x83 0x80 0xb7 0x5d 0x54 0x01 0xf4 0x02, the compressed change chunk header would consist of: 0x85 0x6f 0x4a 0x83 0x80 0xb7 0x5d 0x54 0x02 0xc3 0x02

To decode a compressed change chunk first decompress the chunk contents, and then construct a new chunk with the same magic bytes and checksum, but with type = 1 and the length of the decompressed data. Then parse that as a change chunk.

uLEB is an unsigned little endian base 128 value. This is a variable length encoding used throughout.

To encode a uLEB, represent the number in binary and pad it with leading zeros so that it has a length which is a multiple of 7. Take each group of 7 bytes from least-significant to most-significant and output them in bytes - the first bit of every byte is 1 except for the last byte which is 0.

To decode a uLEB, read bytes up to and including the first byte with a 0 as the first bit. Take the latter 7 bits from each byte (the last byte contains the most significant bits, so you need to concatenate them in the opposite order to which the bytes are represented on disk).

Although uLEB encoding can support numbers of arbitrary bitsize, unsigned integers in Automerge must not exceed 64 bits. Implementations should fail to parse documents with uLEBs that decode to a value too large to be represented in a 64-bit unsigned integer.

Implementations must generate the shortest possible uLEB encodings, and should reject documents with overly long encodings. For example using the decoding rules above the bytes 0b10000000 0b00000000 would be decoded as 0; but this is overly long: 0 can be represented in just one byte as 0b00000000, so should be rejected.

LEB is a signed variant little endian base 128 value

To encode a uLEB, represent the number in twos complement, and sign-extend it so that it has a length which is a multiple of seven. If the number is negative the padding will be of 1-bits and if the number is positive the padding will be 0-bits.

To decode an LEB, read bytes up to and including the first byte with a 0 as the first bit. Take the latter 7 bits from each byte (the last byte contains the most signfiicant bits, so you need to concatenate them in the opposite order to which the bytes are represented on disk). If the first bit of your number is 1 (from the second bit of the last byte in encoded form) then you have a negative number and you can take twos complement to get to its absolute value; otherwise you have a positive number (or 0).

Although LEB encoding can support numbers of arbitrary bitsize, signed integers in Automerge must not exceed 64 bits. Implementations should fail to parse documents with uLEBs that decode to a value too large to be represented in a 64-bit signed integer.

Implementations must generate the shortest possible LEB for a given integer, and should reject documents with overly long encodings. For example the decoding rules above the bytes 0b11111111 0b01111111 would be decoded as -1; but this is overly long: -1 can be represented as just one byte 0b01000000, so should be rejected.

A change hash is the 32-byte [SHA256] hash of the concatenation of the chunk type (0x01) chunk length and chunk contents fields of a change represented as a change chunk.

The first four bytes of the change hash are used as a checksum when a change chunk is serialized.

The actions of the reference data model are encoded in the storage format as a byte as follows:

Future versions of automerge may add new actions, and implementations must preserve operations containing actions they don’t support when processing changes for forward compatibility.

Column specifications are a 32-bit uLEB interpreted as a bitfield:

If the deflate bit is set then the column data must first be decompressed using DEFLATE before proceeding with decoding the values.

The DEFLATE bit is only permitted in document chunks, implementations must abort if they find compressed columns in change chunks.

The ID defines the purpose of the column for either Change Columns or Operation Columns, and implementations must preserve columns that they do not understand.

The column type specifies how the data in the column is encoded. The possible types are:

The actor ID array consists of a 64-bit uLEB giving the count of actor ids, followed by each actor ID as a length-prefixed byte array.

Each item in the array consists of a 64-bit uLEB giving the length in bytes, and then that number of bytes.

For example an array consisting of the single actor ID [0xab, 0xcd, 0xef] would be encoded as: 0x01 0x03 0xab 0xcd 0xef.

Implementations must store actor ids lexicographically, and should error when reading a document with actor ids in the wrong order.

The heads array consists of a 64-bit uLEB N giving the count of heads, followed by N change hashes each exactly 32-bytes long.

For example an array consisting of the heads f986a4318d1f1cc0e2e10e421e7a9a4cd0b70a89dae98bc1d76d789c2bf7904c and 4355a46b19d348dc2f57c046f8ef63d4538ebb936000f3c9ee954a27460dd865 would be represented as 0x02 0xf9 0x86 ..{28 bytes elided).. 0x90 0x4c 0x43 0x55 ..{28 bytes elided}.. 0xd8 0x65

The heads index provides a lookup table from the change hash to the change in a document. Very old automerge documents may be missing this field.

The index consists of N 64-bit uLEB's (one per head in the Heads array of the document chunk), and each uLEB gives the index of that head’s change in the columnar change storage.

In a well-formed document, the change hash of the change indicated will match the change hash in the heads array, but implementations may chose to not validate this when parsing documents to avoid having to recompute every change hash.

The column metadata consists of a 64-bit uLEB N giving the number of columns, followed by N pairs describing each columns in the chunks column data.

The column specifications must be unique and sorted. Implementations must not include both an uncompressed and a compressed column with the same ID and type, and the column order should be sorted with the deflate bit set to 0.

A column that contains only null values, or is otherwise empty, should be omitted from the chunk. In this case there will be no column specification in the column metadata and no data in the column data.

In the case that there are no changes or operations at all, then the column metadata will be encoded as 0x00 to indicate that there are no columns at all, and there will be no column data in the chunk.

The currently defined columns for changes in a document chunk are:

Each value in the dependencies index column is an index into the changes that are stored in the document’s columns. Implementations MUST abort if an index is out of bounds.

The sequence number of a change should be 1 if it is the first change by a given actor. Each subsequent change must have a sequence number exactly 1 higher than the previous change by the same actor. Implementations MUST abort if there are missing changes for a given actor ID.

The maxOp field of the change refers to the largest counter component of an operation ID in the set of operations in this change. For a given actor ID this must always increase. Implementations MUST abort if the maxOp of a change is not larger than all the maxOp of changes from that actor with smaller seq.

After decoding all the columns, and de-referencing indices into other columns, you will have an array of changes, where each change conceptually has the following fields:

The currently defined columns for operations are:

We determine the key that the operation refers to thusly:

Operations are stored with their predecessors in change chunks and with successors in document chunks. For more information see the section on implementation concerns.

After decoding all the columns, and de-referencing indices into other columns, you will have an array of operations, where each operation conceptually has the following fields:

Many columns use run length encoding to compress repeated values. Such columns are encoded as repeated pairs of the form (length, value).

A "run" in an RLE columns is encoded as pairs of the form (length,value). length is a signed LEB:

For example if you were trying to compress the array of uLEBs [0,0,0,null,null,1,2,3] you would encode it as 0x03 0x00 0x00 0x02 0x7d 0x01 0x02 0x03

Some fields in automerge have multiple values per change or operation. An example of this is the dependencies index of a change. The group column (denoted by column type 0) defines how many values should be read from each grouped column when parsing each change or operation.

Grouping affects all columns with the same ID as its column specification, so a group column will usually be followed by one or more columns with the same id but different types. It is possible to have a group column with no matching grouped columns if the grouped column is completely empty, as it will be omitted.

The group column is a run length encoded list of 64-bit uLEBs that specifies how many items should be read from the subsequent grouped columns per change or operation. Implementations MUST abort if they cannot read the correct number of values from each of the grouped columns.

For example if you had five changes in a document with [0,1,2,2,2] dependencies each, the group column would be encoded as 0x7e 0x00 0x01 0x03 0x02, and the dependencies index column would contain seven values.

Note that it is not possible for two columns in a group to have the same type as it would not be possible to have a deterministic ordering for the column specifications. Implementations MUST abort if they encounter two column specifications with the same type and column ID.

Implementations MUST abort if they encounter multiple group column specifications with the same ID.

An actor column (denoted by column type 1) uses run length encoding to compress a list of uLEBs that represent an index into an array of actor ids.

In a document chunk the index is the position of the actor id in the array of actor IDs.

In a change chunk index 0 represents the actor id of the change, and index 1+ are given to the other actor ids in the order they appear.

A uLEB column (denoted by column type 2) uses run length encoding to compress a list of 64-bit uLEBs.

It is used (instead of a delta column) when there is no expectation that delta compression would help reduce the storage requirement, or if the column may contain null values.

A delta column (denoted by column type 3) uses run length encoding to compress a list of 64-bit uLEBs.

The sequence is assumed to start from zero, so if you wanted to encode the list [3,4,5,6,9,7,8] you would first calculate the list of deltas [+3,+1,+1,+1,+3,-2,+1], and then run length encode the resulting signed LEBs to get the bytes 0x7f 0x03 0x03 0x01 0x7d 0x03 0x7e 0x01.

A boolean column (denoted by column type 4) encodes a list of booleans. The column contains sequences of 64-bit uLEB integers which represent the lengths of alternating sequences of false/true. The initial value of the column is always false

For example if you wanted to encode the list [true, true, false, false, false], you would end up with a list of lengths of [0,2,3], which would be encoded as 0x00 0x02 0x03.

A string column (denoted by column type 5) uses run length encoding to compress a list of length-prefixed UTF-8 strings. Each string is encoded as a 64-bit uLEB followed by that many literal bytes.

For example, if you wanted to encode the list ["a", "", null, "boo", "boo"] you would end up with 0x7e 0x01 0x65 0x00 0x00 0x01 0x02 0x03 0x66 0x6f 0x6f.

The value metadata column (denoted by column type 6) is always paired with a value column with the same ID. The metadata column is a run length encoded list of 64-bit LEBs that defines the type and length of each value in the value column.

These integers are laid out like so:

The type code may be

If the type tag is none of these values it may be a value produced by a future version of Automerge. In this case implementations MUST read and store the type code and length bytes when reading and write them back in same position when writing.

If the bytes in a UTF8 string value (type 6) are not valid utf-8, then implementations should replace them by the unicode replacement character (U+FFFD).

The value column (denoted by column type 7) contains raw values. The type and length of each value in the column is determined by the value metadata column with the same column ID.

Note that raw value columns which do not contain values may be omitted. If implementations encounter a lone value metadata column they must assume that it is accompanied by an empty raw value column.

Implementations must abort if they encounter a raw value column not preceeded by a metadata column with the same id. Implementations must also abort if they encounter more than one metadata column with the same column id, or more than one raw value column with the same id.

When reading the column metadata applications may encounter column specifications which they are not expecting. These column specifications may be produced by future versions of the application. If an implementation encounters an unknown column whilst reading data it MUST retain this data when writing that data back to storage.

This is possible because every column type has some concept of a null value. When inserting new rows into a collection of rows stored in the columnar storage format application MUST write a null value into columns which they do not recognise for the new rows they are inserting.

Operations are grouped by the object that they manipulate. Objects are then sorted by their IDs. Thus operations are ordered using the following procedure:

The document storage format does not encode a predecessors field. Instead this information is encoded in the successors field. This can be used to reconstruct the predecessors field from the reference data model.

Delete operations do not carry any information other than the object ID and key they are deleting. As such they are encoded in the document by appending the operation ID of the delete operation to the successors of the operation creating the data to be deleted.

Implementations MUST abort if they encounter explicitly encoded delete operations in a document chunk.

Operations in the document format are not stored in the order they were generated, as they are in the change data model. Furthermore, operations in the document format have a successor rather than predecessor field. The following procedure specifies how to map from document operations to the change operations.

First expand operations:

Second, match up changes:

For each document operation

Implementations MUST abort if no matching change is found

For each change sort the operations within the change by lamport timestamp of the operation ID.