concurrency

Concurrency

This document explains the different guarantees that Irmin's primitives, on different level, ensure in concurrent settings. See Irmin's blog post for a high-level view in the different components of Irmin.

The block store

The core storage system of Irmin is the block store: an immutable, append-only, content-addressable store, where raw values have deterministic keys which are computed by the store, for instance by taking the hash of the value.

The block store in Irmin consists in a collection plug-in backends, such as in-memory store, on-disk as a Git repository, or over HTTP using a REST API, but users of the library can also provide their own as long as they satisfy the Irmin.AO signature and that the following properties are guaranteed:

• read concurrent reads of a key should either fail if the key does not exist or always return the same value.

• add concurrent adds of the same values should always result in the same key.

Block store backends might use the fact that Sys.rename is atomic to guarantee these properties in concurrent settings.

The tag store

Every process using Irmin also have a small mutable store, where it stores the association between branch names and commit hashes. As for block stores, Irmin provides a collection of plugin backends for the tag store, and the user can provide his own as long as it satisfy the Irmin.RW signature and that the following properties are guaranteed:

• read concurrent reads of a branch name should return a consistent hash (i.e. which has been previously written).

• update concurrent updates of a branch names to a given hash should be consistent: subsequent reads of a branch name should always result in the last hash which has been written.

• compare_and_set must be atomic. This is usually not very easy to do, as the POSIX interface do not provide such an operation. Irmin_unix.Lock uses a "dotlocking" optimistic strategy (using the fact that creating a file exclusively can be done atomically on POSIX filesystems).

High-level store

The main goal of Irmin is to take a any block and tag store implementations and expose to the user a higher-level branch-consistent API, with transparent version control, fork/merge strategies, snapshot/revert, etc.

Using the properties of the underlying stores, Irmin guarantees that:

• read concurrent reads always return a consistent value (ie. which has been written before)

• update concurrent updates and merges are atomic: if two processes tries to write a different value for the same key or that branch, and they are totally ordered and (ii) the result value is the last one being written.

In case of concurrent merges, the merge commits for possible conflicts could also be recorded in the history, and be used as a base for restarting the conflicting merge. This would be useful to avoid recomputing (possibly costly) lowest common ancestors. This is not done in 0.9.4.