CRDT benchmarks

A collection of reproducible benchmarks. PRs are welcome.

# Install Node.js https://nodejs.org
npm i && npm start

You can find the benchmark results of Automerge's current performance branch here.

Benchmarks

B1: No conflicts

Simulate two clients. One client modifies a text object and sends update messages to the other client. We measure the time to perform the task (time), the amount of data exchanged (avgUpdateSize), the size of the encoded document after the task is performed (docSize), the time to parse the encoded document (parseTime), and the memory used to hold the decoded document (memUsed).

B2: Two users producing conflicts

Simulate two clients. Both start with a synced text object containing 100 characters. Both clients modify the text object in a single transaction and then send their changes to the other client. We measure the time to sync concurrent changes into a single client (time), the size of the update messages (updateSize), the size of the encoded document after the task is performed (docSize), the time to parse the encoded document (parseTime), and the memory used to hold the decoded document (memUsed).

B3: Many conflicts

Simulate √N concurrent actions. We measure the time to perform the task and sync all clients (time), the size of the update messages (updateSize), the size of the encoded document after the task is performed (docSize), the time to parse the encoded document (parseTime), and the memory used to hold the decoded document (memUsed). The logarithm of N was chosen because √N concurrent actions may result in up to √N^2 - 1 conflicts (apply action 1: 0 conlict; apply action2: 1 conflict, apply action 2: 2 conflicts, ..).

B4: Real-world editing dataset

Replay a real-world editing dataset. This dataset contains the character-by-character editing trace of a large-ish text document, the LaTeX source of this paper: https://arxiv.org/abs/1608.03960

Source: https://github.com/automerge/automerge-perf/tree/master/edit-by-index

• 182,315 single-character insertion operations
• 77,463 single-character deletion operations
• 259,778 operations totally
• 104,852 characters in the final document

We simulate one client replaying all changes and storing each update. We measure the time to replay the changes and the size of all update messages (updateSize), the size of the encoded document after the task is performed (docSize), the time to encode the document (encodeTime), the time to parse the encoded document (parseTime), and the memory used to hold the decoded document in memory (memUsed).

** For now we replay all actions in a single transaction, otherwise Automerge is running out of memory.

[B4 x 100] Real-world editing dataset 100 times

Replay the [B4] dataset one hundred times. The final document has a size of over 10 million characters. As comparison, the book "Game of Thrones: A Song of Ice and Fire" is only 1.6 million characters long (including whitespace).

• 18,231,500 single-character insertion operations
• 7,746,300 single-character deletion operations
• 25,977,800 operations totally
• 10,485,200 characters in the final document

Results

Notes

• The benchmarks were performed on a desktop computer "Intel® Core™ i5-8400 CPU @ 2.80GHz × 6" / Ubuntu 20.04 and Node 12.18.1
• There is a more exchaustive benchmark at the bottom that only runs benchmarks on Yjs.
• memUsed only approximates the amount of memory used. We run the JavaScript garbage collector and use the heap-size difference before and after the benchmark is performed. If the heap is highly fragmented, the heap size might be larger than the actual amount of data stored in the heap. In some cases this even leads to a memUsed of less than zero.
• memUsed does not measure the memory usage of the wasm runtime.
• Preliminary benchmark results for native implementation of the Ron/Chronofold CRDT (written in C++) are posted in this thread.

Older benchmark results that include automerge & delta-crdts

Development

Modify the N variable in benchmarks/utils.js to increase the difficulty.

npm run watch
node dist/benchmark.js

Now you can also open benchmark.html to run the benchmarks in the browser.

License

The MIT License © Kevin Jahns

Except for /b4-editing-trace.js © Martin Kleppmann