This demo imports the complete history of the Loro repo into the latest version of Loro. The document opened here stores the full editing history of this file, allowing for smooth transitions between file histories. With sufficiently fast backtracking and version switching, we can reimagine interaction modes for Timeline, Undo/Redo, and version management
This demo imports the complete history of the Loro repo into the latest version of Loro. The document opened here stores the full editing history of this file, allowing for smooth transitions between file histories. With sufficiently fast backtracking and version switching, we can reimagine interaction modes for Timeline, Undo/Redo, and version management
Loro 1.0 Change Summary
- Data format has now stabilized. There will be no breaking changes to the data format in version 1.x, ensuring forward and backward compatibility within the 1.x format
- Capable of lazy loading history and state, providing 10x to 100x loading speed with lower memory usage
- Shallow snapshot. Like Git, Loro stores the complete directed acyclic graph edit history, but sometimes this history takes up too much space, or in some scenarios we don't want to expose this history, so we can provide shallow clone like Git. It contains the latest state of the document and a small portion of history. This can significantly reduce the overhead of CRDTs with long histories.
- Better version control primitives. Now in Loro, you can switch versions and start editing directly on the target version (thus forming a new branch at the target location). In our demo, we used this primitive to import an entire Git Repo into a Version Control System organized based on Loro.
- Other details
Here's a speed comparison of Snapshot import and export between versions 1.0 and 0.16.12. The benchmark uses real-world document editing history, with data kindly provided by latch.bio. You can find the benchmark code at https://github.com/loro-dev/latch-bench. The documents contain 1,659,541 operations.
In Loro, a snapshot stores both the document history and its current state. The shallow snapshot format, similar to Git's shallow clone, allows for the removal of historical data. In this benchmark, the shallow snapshot has a depth of 1 (keeping only the most recent operation history, with older operations removed).
name |
task |
avg. time |
0 Old Snapshot Format on 0.16.12 |
Import |
15.688953ms +- 10.263µs |
|
Import+GetAllValues |
15.781199ms +- 12.296µs |
|
Import+GetAllValues+Edit |
15.916294ms +- 113.443µs |
|
Import+GetAllValues+Edit+Expo |
30.2621ms +- 32.936µs |
2 New Snapshot Format on 1.0.0-beta.1 |
Import |
906.097µs +- 23.672µs |
|
Import+GetAllValues |
880.976µs +- 25.544µs |
|
Import+GetAllValues+Edit |
773.657µs +- 23.585µs |
|
Import+GetAllValues+Edit+Export |
4.102005ms +- 92.102µs |
3 Shallow Snapshot Format on 1.0.0-beta.1 |
Import |
255.449µs +- 9.661µs |
|
Import+GetAllValues |
185.39µs +- 10.48µs |
|
Import+GetAllValues+Edit |
225.466µs +- 10.787µs |
|
Import+GetAllValues+Edit+Export |
581.245µs +- 17.223µs |
For more detailed interface change information, check Loro v0.16 到 v1.0.0-beta 变动
Introduction to Eg-walker
Loro's algorithm architecture has been greatly inspired by the Eg-walker algorithm, so it is very similar to Eg-walker in terms of algorithm properties.
The Eg-walker paper was published in September 2024. It combines the advantages of both CRDT and OT algorithms, while achieving the following points:
- It conforms to the definition of CRDT, so it has the strong eventual consistency property of CRDT, making it usable in distributed environments
- Fast local operation: It processes operations much faster than previous CRDTs because it doesn't need to generate corresponding operations through CRDTs data structures
- Fast merging of remote operations: OT's complexity for merging remote operations is O(n^2), while Eg-walker, like mainstream CRDTs, is O(nlogn), only reaching O(n^2) complexity in extremely rare worst-case scenarios. And it's faster than other CRDTs in most real-world scenario benchmarks.
- Lower memory usage: Because it doesn't need to persistently store the complete CRDTs structure in memory, its memory usage is lower than general CRDTs
- Faster import speed: CRDTs import is often time-consuming because it needs to parse corresponding CRDTs structures or Operations to build out the CRDTs data structure, without which it cannot continue subsequent editing, leading to long import times. Eg-walker, like OT algorithms, only needs the current state of the document and doesn't need to build these additional structures to allow users to start editing the document directly, thus achieving multi-order of magnitude improvements in document import speed.
<aside>
💡
Differences between Loro and Eg-walker
In terms of performance, Loro and Eg-walker have similar local editing and remote operation merging performance. Eg-walker has an advantage in import performance because Loro's encoding format carries additional ID information and integrity checks, resulting in larger volume and slower import.
- Loro supports multiple data types beyond text, such as Map, List, Movable List, Tree, Counter, etc. Some types are not easily combined with Eg-walker directly and require additional adaptation and adjustment.
- Loro's Document State has some additional metadata, including the ID of each character. This metadata is used to support features like cursor synchronization. IDs on text can provide a stable position information expression, used for functions like commenting.
- Loro lacks certain features of Eg-walker. For example, Eg-walker can directly import a plain text document and then start writing from this document. Eg-walker's Snapshots can start writing directly from the current plain text document (without any CRDT information). Loro can't do this; it needs at least a Shallow Snapshot. This Shallow Snapshot is similar to Git's shallow snapshot, which will know the latest few operations.
- Our text supports not only plain text but also rich text. This results in our text data format being different from plain text and cannot be described directly using plain text description methods.
- Loro's design supports not only real-time collaboration but also version management. So we have extra data structures to ensure the speed of switching between different version.
</aside>