Replica Storage

Each replica has a storage backend. The interface for this backend is given in crate::taskstorage::Storage and StorageTxn.

The storage is transaction-protected, with the expectation of a serializable isolation level. The storage contains the following information:

  • tasks: a set of tasks, indexed by UUID
  • base_version: the number of the last version sync'd from the server (a single integer)
  • operations: all operations performed since base_version
  • working_set: a mapping from integer -> UUID, used to keep stable small-integer indexes into the tasks for users' convenience. This data is not synchronized with the server and does not affect any consistency guarantees.

Tasks

The tasks are stored as an un-ordered collection, keyed by task UUID. Each task in the database is represented by a key-value map. See Tasks for details on the content of that map.

Operations

Every change to the task database is captured as an operation. In other words, operations act as deltas between database states. Operations are crucial to synchronization of replicas, described in Synchronization Model.

Operations are entirely managed by the replica, and some combinations of operations are described as "invalid" here. A replica must not create invalid operations, but should be resilient to receiving invalid operations during the synchronization process.

Each operation has one of the forms

  • Create(uuid)
  • Delete(uuid, oldTask)
  • Update(uuid, property, oldValue, newValue, timestamp)
  • UndoPoint()

The Create form creates a new task. It is invalid to create a task that already exists.

Similarly, the Delete form deletes an existing task. It is invalid to delete a task that does not exist. The oldTask property contains the task data from before it was deleted.

The Update form updates the given property of the given task, where the property and values are strings. The oldValue gives the old value of the property (or None to create a new property), while newValue gives the new value (or None to delete a property). It is invalid to update a task that does not exist. The timestamp on updates serves as additional metadata and is used to resolve conflicts.

Application

Each operation can be "applied" to a task database in a natural way:

  • Applying Create creates a new, empty task in the task database.
  • Applying Delete deletes a task, including all of its properties, from the task database.
  • Applying Update modifies the properties of a task.
  • Applying UndoPoint does nothing.

Undo

Each operation also contains enough information to reverse its application:

  • Undoing Create deletes a task.
  • Undoing Delete creates a task, including all of the properties in oldTask.
  • Undoing Update modifies the properties of a task, reverting to oldValue.
  • Undoing UndoPoint does nothing.

The UndoPoint operation serves as a marker of points in the operation sequence to which the user might wish to undo. For example, creation of a new task with several properties involves several operations, but is a single step from the user's perspective. An "undo" command reverses operations, removing them from the operations sequence, until it reaches an UndoPoint operation.

Synchronizing Operations

After operations are synchronized to the server, they can no longer be undone. As such, the synchronization model uses simpler operations. Replica operations are converted to sync operations as follows:

  • Create(uuid) -> Create(uuid) (no change)
  • Delete(uuid, oldTask) -> Delete(uuid)
  • Update(uuid, property, oldValue, newValue, timestamp) -> Update(uuid, property, newValue, timestamp)
  • UndoPoint() -> Ø (dropped from operation sequence)

Storage

The storage backend stores all operations that apply to existing tasks, tracking which have and have not been synchronized. Only unsynchronized operations are used in the synchronization process. Synchronized operations are kept as a log of changes to the relevant tasks. Synchronized UndoPoint operations are not stored.