Running into "Internal error: unexpected root node key" issues

[Gozala]

Hi Team,

I have being trying to get okra to persist in IDB in browser and sync with remote replica using sync protocol, but seem to run into a problem after bunch of fast writes coming from here

okra-js/packages/okra/src/NodeStore.ts

Lines 106 to 112 in eeaceb6

	public getRoot(): Node {
	const upperBound = { key: KeyValueNodeStore.metadataKey, inclusive: false }
	for (const entry of this.entries(null, upperBound, { reverse: true })) {
	const node = this.parseEntry(entry)
	assert(node.key === null, "Internal error: unexpected root node key", node)
	return node
	}

Initially I attempted to use okra-idb package from npm but I was running into lot of problems with IDB transactions completing mid writes. As @joeltg have pointed out here #3 that is because IDB completes transaction as soon as you yield to event loop & async generators do exactly that.

To overcome this problem I have effectively rewrote IDB backend and most of the core okra constructs to use generator based task scheduling library which I have being using already to abstract over sync / async interfaces. General idea is that you can author potentially async logic as follows

Task.spawn(function* () {
   const awaited = yield* Task.wait(maybePromise)
   ....
})

In case of IDB I also have wrote task poll that just like Task.wait will suspend execution and resume once passed IDBRequest succeeds or fails. This way I could represent entries / nodes using custom Sequence type which utilized tasks.

Above switch addressed premature IDB transaction completion issues, as task scheduler ensures that continuations take places on IDBRequest events without yielding to event-loop.

---

Unfortunately I am running into the mentioned invariant mentioned at the beginning of the issue. It appears that after some bunch of writes store ends up in a state where iteration over nodes does return an entry where first key isn't a single byte.

Perhaps more surprising is the fact that DB does actually contain record where with 0xFF key which makes me wonder if iteration order assumed is invalid

I realize that at this point, I'm basically working off a fork but any help would be highly appreciated. I also would be very delighted if any of the ideas could be uplifted to this library.

[Gozala]

Perhaps more surprising is the fact that DB does actually contain record where with 0xFF key which makes me wonder if iteration order assumed is invalid

I realize this fact was irrelevant given that range read was exclusive. However after closer inspection I do see that first entry returned by a cursor has key like [1, 2, 0, ...] and db store does have record with a key [1]

So I'm starting to suspect that there is something with an iteration order here

[Gozala]

I did some more investigation and it appears to me that idb behaves as expected, and indeed there is a root node missing.

As I understand there should be a node with key [2] to denote the new root which does not seem to exist and which is also why getRoot seems to raise an error.

[Gozala]

Doing more debugging I see that new root write is logged

However it does not seem to appear in the IDB store, which seems to be a cause of the problem here.

[joeltg]

The entry at 0xFF is the metadata record containing the database version number and parameters.

We also had difficulty working with indexeddb, partly due to issues around consistency and durability, and also a more severe problem: it isn't possible to hold a read-only snapshot transaction open without locking the entire database, so syncing with browsers (either browser->browser or server->browser) wasn't practical.

As a result, we switched to using in-memory okra-memory in the browser, which uses this lock-free r/b-tree for multi-reader concurrency. I just marked okra-idb as deprecated on npm to clarify that we're only maintaining @canvas-js/okra-memory and @canvas-js/okra-lmdb (and the base package @canvas-js/okra) from now on.

[joeltg]

I'm not sure why you're seeing inconsistency with your fork; nothing stood out to me from a cursory reading here. Sorry :/

[Gozala]

I think I'm getting close to the root of the problem, I do have a following code path in the downstream use of the okra for convenience here is the simplified version

xport const transact = ({ store }, changes) =>
  store.write(function* (writer) {
    const root = yield* writer.getRoot()
    const hash = root.hash

    performWrites(store, changes)

    return {
      before: new Revision(root),
      after: new Revision(yield* writer.getRoot()), // ⚠️
      cause: commit,
    }
  })

I think what happens here is that bunch of writes are made in the IDB transaction and then towards the end on line with ⚠️ I do attempt to .getRoot in the same transaction, but since those writes did not got flushed yet read can not find new root.

I don't know if IDB lets you read written data from transaction that has not being committed yet, but if there is no guarantee that written data can be read that would explain the problem.

What I still can't seem to understand yet, is why does behavior appears random. This error does not occur at consistent times, sometimes I reach level 3 root sometimes I do encounter at level 2.

---

I could change my that code to read root in a separate read transaction, but I wonder if fact that written data can be read in the same transaction would violate invariants that Okra assumes.

[Gozala]

We also had difficulty working with indexeddb, partly due to issues around consistency and durability, and also a more severe problem: it isn't possible to hold a read-only snapshot transaction open without locking the entire database, so syncing with browsers (either browser->browser or server->browser) wasn't practical.

That is good to know. I have being thinking of using in memory db for writes while sync takes process and the flushing data from it back to IDB.

Relatedly we're thinking of developing alternative implementation which does not do in place mutations of the tree to avoid concurrency constraints of okra. Something more similar to git. That way sync can happen from the root tree had at initiation, yet delta could be applied to the latest tree.

I was pondering if mapping onto key value store could still be accomplished, but I have not came up with a way. As I understand current approach would break down if old nodes are left behind since they would come up when iterating nodes.

If you had any thoughts in this direction, please consider sharing them as I'm sure they would be invaluable.

As a result, we switched to using in-memory okra-memory in the browser, which uses this lock-free r/b-tree for multi-reader concurrency. I just marked okra-idb as deprecated on npm to clarify that we're only maintaining @canvas-js/okra-memory and @canvas-js/okra-lmdb (and the base package @canvas-js/okra) from now on.

okra-memory and okra-lmdb had worked really well for us. However amount of data that fits in memory which is not the invariant we want to have. Also getting whole db over the wire after reload does not seem ideal. Which is why I've being trying to resurrect IDB

[Gozala]

It appears that my task scheduling library has some bug related to recursive tasks. Rewriting some of the Writer methods to be iterative instead seems to fix the problem.