How Evolu Works

Evolu is simple. That's the feature, not a bug. It's based on James Long's CRDTs for Mortals (opens in a new tab) talk. I recommend you to watch it. James also made a working example (opens in a new tab), and someone very well explained it (opens in a new tab). I took that code and improved it for production.

So, how does Evolu work? Evolu creates SQLite database in the user device and stores all data locally. While we have full SQL for reads, writes must be written in a special form to sync data among devices safely and without merge conflicts. Every DB change is described as a CRDT message.

Evolu creates and stores CRDT messages locally and derives actual DB from them. The most simple CRDT mutation (and the only one implemented right now) is the last write win. A CRDT message contains a table, row, column, value, and timestamp because every CRDT message has to have a timestamp to ensure globally stable ordering via hybrid logical clocks (opens in a new tab).

How it really works?

Everything starts with a mutation, you can create or update a row.

const { create, update } = useMutation();
 
const { id } = create("todo", { title, isCompleted: false });
update("todo", { id, isCompleted: true });

Evolu uses queueMicrotask to make an array of MutateItem to send a batch to a WebWorker to not block the main thread.

export interface MutateItem {
  readonly table: string;
  readonly id: Id;
  readonly values: ReadonlyRecord.ReadonlyRecord<
    Value | Date | boolean | undefined
  >;
  readonly isInsert: boolean;
  readonly now: SqliteDate;
  readonly onCompleteId: OnCompleteId | null;
}

In the WebWorker, Evolu maps MutateItem to Message.

export interface NewMessage {
  readonly table: string;
  readonly row: Id;
  readonly column: string;
  readonly value: Value;
}
 
export interface Message extends NewMessage {
  readonly timestamp: TimestampString;
}

Every NewMessage will get a Timestamp consisting of NodeId, Millis, and Counter.

export interface Timestamp {
  readonly node: NodeId;
  readonly millis: Millis;
  readonly counter: Counter;
}

The timestamp is essential to ensure the same order of messages across all devices. Every timestamp also has to be unique. That is guaranteed via NodeId and Counter. Computer clocks are unreliable. They can accidentally go backward or be the same. If such a situation happens, the later time is chosen, and the counter is incremented. Check sendTimestamp function in Timestamp.ts. We must store the last timestamp in the database to make a new one.

Now, we have an array of messages to update the local database via the applyMessages function. The applyMessages function is also used for messages we receive from other devices. We use the same logic for all messages describing database changes to ensure messages are processed always in the same manner.

The applyMessages function in the DbWorker.ts stores messages in a separate table and updates the database if a message is new. It's the simple last-write-win approach. The applyMessages function also maintains the Merkle tree, which is used to find the last timestamp when both the local and remove Merkle trees are the same. Merkle tree is stored as a "merkleized" prefix tree (trie).

After messages are processed, a sync loop is requested, and subscribed queries are refreshed.

The sync loop compares Merkle trees until both local and remote devices are in the same state. Received messages timestamps are processed via the receiveTimestamp function.

And that's all. Take a look at the source code and check the tests. For a more detailed description, read the links above.

Videos about Evolu

• Effect | Discussing Evolu & Local-First with Daniel Steigerwald (opens in a new tab)
• PragueJS 2023 | Evolu 1.0 release - Why local-first software matters (opens in a new tab) (sadly with some recording problems)