Support time travel

[hackerwins]

Yorkie internally saves a history of all changes in documents. This enables time travel which is looking at the document state at past points in time.

The current state of the Yorkie system is as follows:

Past to Present
For now, we have not introduced inverse operations yet, we can only apply operations from the past to the present.

Changes and Snapshots

Currently, Client only has a snapshot of the current state and changes that have not been sent to Agent. Since client data is not enough, we need to use Snapshots and Changes stored on Agent for time travel.

For example, if Client A wants to go back to S7, it needs S5, C6, and C7.

Proposal

We can think of a document as a pointer to a specific location in a Change. Using this, we can create two features, fork and peek.

const doc1 = client.createDocument('docs', 'doc1');

...

// serverSeq is the position in the order of the last change stored in Agent.
const serverSeq = doc1.getCheckpoint().getServerSeqAsString(); // for example: 4

// peek returns a snapshot of the change at a specific location from Agent.
const snapshot = await client.peek(doc1, serverSeq.divide(2));

// Create a new document that forked from a specific location in doc1.
const doc2 = await client.fork('docs', 'doc2', doc1, serverSeq.divide(2)); // for example: 2
doc2.update((root) => {
  root.hello = 'world';
});

[hackerwins]

Conflict can arise when Client A is restoring the document to a point in changes while Client B makes new changes from an earlier point in time.

Google Docs exposes the following dialog with the message with a red banner.

Document cannot be saved!

An error prevented this document from being saved. Please copy your changes and paste them elsewhere. Then tap on the red banner below to remove the problematic changes and continue editing.

We also have to deal with exposing an error when there are changes created at the same time as restoring.