Documentation
How Evolu Works

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.

ℹ️

CRDT stands for "Conflict-Free Replicated Data Type." It is a type of data structure used in distributed computing and distributed databases to enable concurrent updates to data without conflicts or the need for centralized coordination. CRDTs are designed to work in scenarios where multiple replicas of data exist in a distributed system, and these replicas can be updated independently and concurrently.

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 Mutation to send a batch to a WebWorker to not block the main thread.

export interface Mutation {
  readonly table: string;
  readonly id: Id;
  readonly values: Record.ReadonlyRecord<
    string,
    Value | Date | boolean | undefined
  >;
  readonly isInsert: boolean;
}

In the WebWorker, Evolu maps Mutation 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 Db.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