How is y-leveldb coming along?

I’m curious how it’s progressing. I’m looking forward to being able to persist worlds in https://relm.us :slight_smile:

Persisting worlds, that just sounds awesome :slight_smile:

I’ll publish what I have on the weekend. I’ve been thinking a lot about optimizing how multiple rooms can be stored in a single file.

1 Like

Any more progress to report?

Hey @canadaduane,

Just to show you something because you have been waiting for this for quite some time. (Sorry if not everything here makes sense. It was a long day and I know I don’t always make sense when I’m tired. I still wanted to get this out for you).

I published what I have here: https://github.com/yjs/y-leveldb

What I’m currently working on: I’m working on an interface for providers that allows to exchange document updates without creating a Yjs instance. This will allow the server to process and sync large documents with constant memory consumption (just in the size of the update buffers + x bytes as working memory).

Why: Creating a Yjs instance is rather costly for a server. A large Y.Doc consumes about 40 MB of memory. With a 1GB server instance you can only handle about 20 large documents at the same time on a server because the server needs to keep the Yjs documents in memory. Hence the idea to compute document updates without actually creating a Y.Doc.

Constraints I’m looking for a generic, scalable provider approach that will work in all db environments.

Solution Currently you can transform the Yjs document to a single document update. Furthermore, you can compute a diff using state vectors (see here https://github.com/yjs/yjs#Document-Updates). In order to allow the server to sync Yjs document updates without creating Y.Docs, we need to be able to merge document updates (const singleUpdate = Y.mergeUpdates([update1, update2, ..])), and compute diffs on document updates instead of the Yjs document (const missingChanges = Y.diffUpdate(latestUpdate, stateVector)).

For this, I have completely reworked Yjs’s update encoding and I have worked on an interface to find the required document updates in leveldb without constructing the whole Y.Doc every time a client wants to sync.

The current database provider approach is to store all incremental document updates in a list. Optionally, you can merge all document updates to a single entry. This is very database friendly because you don’t have to write the whole document every time something changes (large writes are costly especially in leveldb).

In the new approach, we will still store document updates in a list in causal order. [update1, update2, update3] But we will have a separate list of state vectors that point to updates in the database.

When a client wants to sync, it will send its state-vector to the server, the server will query for the first missing document update using the state vector (e.g. update2). The server will then grab all missing document updates ([update2, update3]), merge them to a single document update updateMerged23 = Y.mergeUpdates([update2, update3]), and then perform the usual diff using the stateVector (missingUpdates = Y.encodeStateAsUpdate(updateMerged23, stateVector)).

The advantages:

  • constant memory consumption
  • cheap syncs because in most cases updates just need to be merged
  • less db load because only a subset of databases will be queried
  • Uses state vectors instead of some kind of server-clock approach. State vectors are just much easier to work with and allow for very efficient syncs.

The disadvantages

  • Need to maintain a list of state vectors + more disk space, but this can be optimized
  • Rework of the encoding/decoding protocols

It is actually quite tricky to get all of this right. First I envisioned a much easier approach, but I think this is where I want to go with this.

Nevertheless, y-leveldb can already be used as a database provider using the current y-websocket implementation. All the necessary methods (storeUpdate, getYDoc) are already available. You should be able to upgrade to the new approach when everything is ready.

I will publish a new y-leveldb release tomorrow and I will post documentation on how to set it up here.

To everyone who doesn’t know. @canadaduane is sponsoring the y-leveldb work. Thanks again for this! Who knows when I would have found the motivation to finally tackle server load.

Great work, Kevin! Thanks for the update. I’m excited for your very thorough solution.

Out of curiosity, does this open a path towards squashing history (like we talked about before, e.g. “clear out history”)?

I don’t think that this will ever be part of Yjs directly. There might be some benefit in implementing this in y-websocket / y-protocols. An event that signals the clients to migrate all data to a new instance.

For now you can use one of the discussed methods.

I reimplemented y-leveldb and also added persistence support in y-websocket

As described in the y-websocket docs, you just need to set an environment variable in order to allow persistence using y-leveldb:

YPERSISTENCE=./dbDir y-websocket-server

You can also set persistence using the setPersistence function that is exported by y-websocket/bin/utils.js:

  const LeveldbPersistence = require('y-leveldb').LeveldbPersistence
  const ldb = new LeveldbPersistence('./my-storage')
  setPersistence({
    bindState: async (docName, ydoc) => {
      const persistedYdoc = await ldb.getYDoc(docName)
      const newUpdates = Y.encodeStateAsUpdate(ydoc)
      ldb.storeUpdate(docName, newUpdates)
      Y.applyUpdate(ydoc, Y.encodeStateAsUpdate(persistedYdoc))
      ydoc.on('update', update => {
        ldb.storeUpdate(docName, update)
      })
    },
    writeState: async (docName, ydoc) => {}
  })

y-leveldb only stores incremental updates and therefore we don’t need the writeState method.

In case you want to rework the persistence approach:

writeState is called once after all clients left the room and just before the instance can be destroyed.
bindState is called once after the document is created. You can use it to start listening to document updates.

As I mentioned in the previous posts, I’m currently in the process of reworking how y-websocket uses persistence. The y-leveldb interface is pretty stable and you probably won’t have to migrate any data when the persistence layer changes. I might even keep the old interface functional.

Fantastic! I’ll give this a test drive soon. Thanks!

Since this is my first comment around here, I’d just like to start of by thanking you for your hard work on Yjs, as well as for keeping such a friendly and welcoming tone!

Now for my question — what’s the reasoning behind writing the initial update in bindState()? I’m referring to the following lines from your example above:

const newUpdates = Y.encodeStateAsUpdate(ydoc)
ldb.storeUpdate(docName, newUpdates)

Why is it not enough to write only from the update handler?

Thanks again!

Welcome @tobiasandersen!

It might be enough. I don’t make any assumptions on how y-websocket is used. If the user initialized some content (or used another database-adapter) then the initial document might not be empty (before registering the update event). In the worst case, you write a tiny / empty update to the database. One improvement might be to check beforehand if the update is empty. On the downside, this introduces a special case that requires more cognitive load without really providing any performance gain. I like to simplify things like that.

Ah, that makes a lot of sense. Thanks!