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 a synchronization operation.

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)

Once a sequence of operations has been synchronized, there is no need to store those operations on the replica. The current implementation deletes operations at that time. An alternative approach is to keep operations for existing tasks, and provide access to those operations as a "history" of modifications to the task.