Disk-native Yjs

Ysr (read: wiser) is yet another implementation of Yjs/Yrs Conflict-free Replicated Data Type libraries, used for building collaborative applications. The twist here is that this time we're moved from in-memory database into one that lies natively on disk. This way we hope to target a long living challenges of building yjs apps.

Motivation

Yjs has become one of the most popular collaborative/local-first libraries out there. However it's not headache-free: people often run themselves into corners, usually by abusing its features or not understanding how do they map onto underlying data structure.

Even when they do understand the characteristics, sometimes its possible to reach the limits of what's possible with up-front design, which leads to building architecture with growing complexity made up to amortise the limitations.

A few pain points that we can try to address, are:

• Persisting and loading large documents: most users eventually want to store their documents in some file or database and most likely will use existing providers for this. However loading/storing document representation between memory and disk can come with significant cost, especially when it needs to be done often and the document size is huge.
• Memory consumption: sometimes we run into situations when the document is simply too big to be reasonably kept in memory (especially if it needs to happen on the broker server that may contain multiple such documents). This is especially prevalent for data that is edited frequently with a history change track kept around (document GC turned off).
• Subdocuments: yjs subdocuments feature were originally created to address some of the issues above. It's essentially a way to split document data into parts that can be loaded independently. However, subdocuments are independent entities and that makes them hard to use when they keep intertwined data.
• Stage changes or simply, apply-but-don't commit, which so far required us to rebuild the entire document from the previous snapshot when you decided to rollback the changes.

With ysr we want to move out of the in-memory limitations and build something that simply scales better.

Why LMDB?

Since our internal document structure is very access heavy and using high-level database (eg. SQLite) would not reach the performance goals, we decided to use a persistent key-value store, and our initial pick landed on LMDB.

Why LMDB and not other key-value stores? RocksDB being one of the most popular ones and is quite often a preference for some people. And while it's possible that we're going to try a RocksDB implementation in the future for comparison (the db access layer of ysr is fairly abstracted), here's why we think, that LMDB is a good choice:

• It's simple: less foot guns, code that fits into cache of machine and human brain.
• It's fairly scalable for multiple documents: in our design we want to have a single LMDB file to support potentially 10,000+ ysr documents, each represented by it's own LMDB database object. And while LMDB overhead (3+ pages, or 12KiB) may sound heavy for lot of small documents, the RocksDB column families are no better.
• Mmap reads: there's a lot of discussion about this in database community, but we're not building a standalone database running on a dedicated VM. Since most likely you have many other processes running in the same machine (which itself may belong to another person), OS has arguably better understanding of how to manage resources for your buffer/cache than your app alone.
• It actually allows zero-copy abstractions: loading pages from disk to memory operates through mmap, but once its done there's no more data copying in the user space. RocksDB (at least used through Rust crates) is not so gentle, and we move between KV-store and library data structures a lot.
• It's good for read-heavy operations and has very predictable speed in that regard. I never managed to create a benchmark when RocksDB would actually win here for any realistic scenario.
• Cheap open/close semantics: some of our scenarios include frequent opening the document, making few operations and then closing it. In LMDB once the fsync is done, you're done - there's no compaction or WAL application. When opening the LMDB again, the recovery process is essentially O(1) operation.
• Some people have problem with LMDB not performing file compaction/defragmentation, but mdb_env_copy2 with MDB_CP_COMPACT is your friend (btw. SQLite vacuum works exactly the same way). Beside that, if you want to keep track of your documents history (which very often you do), your document will not shrink anyway.

An interesting idea worth pursuing would be to actually implement our own persistent key-value store, optimised for the scenarios that we discussed. With that we could potentially move ysr to the browser (via OPFS persistence) or replace LMDB with in-memory KV store: which would allow us to make cheap tests, but also potentially more constrained and allocation aware data access than yrs/yjs can currently offer.

Challenges

When porting the logic from yjs/yrs into new medium, there's a plenty of challenges to be addressed. In order to understand what we're going to talk about, you should be already aware about how these libraries work internally. If you don't, you can read about yrs architecture here.

The center piece of the entire yjs design is so called block: it's a structure that holds metadata of sequential inserts made by the same client (without changing a cursor position).

First of all, yjs algorithm is both update- and read-heavy. Every block update comes with corresponding updates in its neighbours (as we keep the references to left/right neighbour blocks), but also potentially the parent node. If you apply an update consisting of multiple blocks, sometimes the same blocks can be written over many times. Fortunately, LMDB allows us to replace-in-place any dirty entry via MDB_CURRENT flag... as long as both old and new value have the same size. We'll come to that later.

Blocks are also frequent targets of split/merge mechanics. Depending on the user data size, it may mean moving a large amount of data around.

Architecture overview

The overall ysr overview starts at MultiDoc. We don't create documents directly, instead operate on them via transaction proxy (similar to how yrs already works). If you want to create a new document, simply create a read-write transaction and it will initialise the doc on demand.

These structures are mapped directly onto LMDB primitives:

• MultiDoc→ LMDB Env object. This way single LMDB file can hold many documents inside.
• Document → LMDB database.
• Transaction → LMDB transaction + db handle. For read-write transactions it also carries ysr specific state used to generate incremental updates, block merges etc.

Internally each document is split into multiple key-spaces called stores. All entries within the same store keep the same schema of their entries.

This part of architecture is still subject to change, as we're evaluating other possible stores eg.:

• Document delete set, which is currently a computed property of BlockStore. It may be useful, since generating updates for other clients sometimes involves calculating delete set for the entire document, which implies iterating over ALL blocks in the document.
• Skip list index used to speedup large text/array navigation (conceptually similar to yjs search markers).
• Attributions (one of the new features of yjs v14).

Block store

Probably most important piece is the BlockStore which is responsible for holding the block metadata. Each entry is a pair of (ID, BlockHeader) describing current block's metadata. Unlike Yjs, garbage collected objects are not represented in this space at all.

BlockHeader is unique in this sense, that they have always fixed size. The reason for that is because of MDB_CURRENT flag update-in-place requirements. Blocks are updated often even within the same transaction scope and we want to reduce full page reallocations when that happens. This way, we can always swap the blocks in place.

In order to make BlockHeader fixed size, we had to remove all variable size elements, such as entry keys (used by Maps) or content, which have been moved into their own space.

Block content management was probably the biggest rework in this space. Since jumping for content data would now require a separate random disk access, we don't want to do it too often. For this reason each BlockHeader contains a special inlined content space: it's a fixed-size array inlined directly into block header itself. For small values, like short strings, small objects or YType array navigation pointers, we store them all directly onto block headers. 

Content store

Once the values stored by blocks grow beyond the bounds of inline-able content data, we move them into another key-space known as content store. Effectively this only happens for 2 types of data:

• JSON-like values.
• Bigger string chunks.

The content store is fairly simple in its structure. One thing that deserves recognition however is how it reacts in case of block split/merge.

Reminder: whenever you insert something in between chunks represented as a single block, you perform block split. Inversely, whenever two blocks were inserted sequentially, they can potentially be merged together into one. This greatly reduces the metadata overhead, especially when typing text.

Now the content store doesn't necessarily have to map its entries to block store entries in 1-1 fashion. Since merging is mostly advantageous because it allows us to reduce block metadata (present in block store) not the user data (present in content store), we don't need to shuffle user bytes around every time we're about to merge/split blocks. This is especially true for the JSON objects stored by collaborative arrays.

Map Entry store

The next store is responsible for maintaining key-block entries of Y.Map types (a.k.a. attrs of YType (v14)). Since in yjs/yrs/ysr user data always is wrapped in block metadata, what we store here is actually an index of (YMap.id, key_hash, key) → block_id. 

Look at key_hash here. It's necessary since our blocks are fixed size. That means we cannot keep keys directly inside of the block itself. However for some operations we still need to be able to access map entry given its key from the block level alone. In the future we hope to get rid of that part.

Nodes

Another note that we didn't discuss before is representation of Nodes a.k.a. AbstractStruct/ YType (yjs v14). It's an object that represents individual collaborative collection, and as such it used to contain multiple properties, often of variable size:

• Head block pointer of the Y.Array/Y.Text etc. We now keep them inlined within the BlockHeader data itself.
• Entries of Y.Map, which now have their dedicated store.
• Name of root type which also lives in dedicated store used for string interning.

For this reason we managed to basically conflate the definition of the block and node data together. Now each node - including roots which originally didn't live inside of blocks - can be described by its block header. Root block can be recognised by ClientID::ROOT - for this reason we also don't allow users to use that ClientID. For roots specifically the clock is also replaced by hash of the root type name - name itself resides in intern strings store.

What about performance?

It's hard to create a benchmark that will accurately create a meaningful comparison. First of all, we're kinda comparing apples to oranges. Usually you don't compare inserting elements to a list in your favourite programming languages with inserting them as SQLite table rows. So these kind of experiments are doomed to be inadequate.

But let's at least try to make some sort of comparison. Let's try to apply the same input (~9000 ops) into a non-empty document and commit it on each op. We compare ysr against yrs with a LMDB persistence backend. We turn off fsync through NOSYNC flag - otherwise the cost of fsync would dwarf any other measurements.

So far, we landed in area around 7-8x slower than pure in-memory representation: mostly since we cannot use pointers and memory addressing in order to navigate between blocks. Honestly, not that bad for a MVP (first implementation of yrs made 5 years ago was about 10x slower than the current one).

What's next?

We still have a bunch of ideas how to optimise the whole process, eg. by reducing number of block allocs and merges (which happen during transaction commit) in favour of modifying the block directly when the update is being made.

We don't plan to cover all of the features of yrs - i.e. reactivity through observer callbacks was done to fit yrs in JavaScript ecosystem, but maintaining this type of reactivity in Rust has been a constant headache since then. However we plan to provide enough features to give an equivalent capabilities to the users.