Yjs state diverging, trying to figure out why

1

Hey @dmonad (or anybody else who might have thoughts) –

As mentioned previously, I’m working on some Yjs bindings for a collaborative editing aspect of a web app. In the course of that work, I’ve put together a test harness that models concurrent edits between two different editors – applying different sets of changes to both editors, capturing the resulting Yjs state updates, cross-propagating the updates between the editors, then verifying that the resulting editor states match (both at the application level and the Yjs level). This has proven to be terribly useful, and with it I’ve managed to find/fix a number of bugs in our bindings.

But now I’ve run into a bug that feels different than those I’ve encountered previously. While I do see divergence at the application level, I also see it at the Yjs level – the values returned by Y.encodeStateVector() match between the two editors, but the values returned by Y.encodeStateAsUpdate() do not. At this point, I’ve only seen this happen for a one set of changes applied to the two editors – those comparisons pass for ~1000 other test cases.

If it helps provide context, the test case in question involves deleting seven characters from a short line of text in one editor and marking two of those characters as bold (implemented at the Yjs level using formatting attributes) in the other editor.

While I certainly can’t rule out that this is due to a bug in our bindings, I haven’t been able to chase that down yet, and the fact that the full Yjs state diverges in the same test case where I see the application-level divergence seems like it might not be a coincidence.

Any ideas about what might be happening here? (If it would be helpful, it may be possible for me to capture the binary states + updates and build a small standalone test jig that can reproduce the Yjs-level divergence.)

Thanks as always – Yjs is cool stuff!

2

re: a small standalone test jig – indeed, I believe I have such in hand. 55 lines, Yjs only, reconstituting the states + updates from dumps of their byte-level contents, cross-propagating the updates, then demonstrating that the state vectors for the two documents match, but the full states do not. Let me know what the best way to share this is.

Thanks!

3

Hi @kjohnson,

It is not guaranteed that the encoded state is the same for all instances. Although, if you are using a current Yjs version, I see no reason that it shouldn’t work. So you might have encountered a bug.

Just because the encoded states don’t match doesn’t mean that the states diverge. One of the instances might have applied an optimization that the other doesn’t. The clients could still end up with the same decoded state.

I currently only test that the internal state representation matches (yjs/tests/testHelper.js at main · yjs/yjs · GitHub). Then I check that the end-result (the shared type) matches with the decoded content from all the other shared types (yjs/tests/testHelper.js at main · yjs/yjs · GitHub).

Could you please make the diverging states somehow available? Maybe as a base64 encoded string here on the forum.

re: a small standalone test jig – indeed, I believe I have such in hand. 55 lines, Yjs only, reconstituting the states + updates from dumps of their byte-level contents, cross-propagating the updates, then demonstrating that the state vectors for the two documents match, but the full states do not. Let me know what the best way to share this is.

That would be great! https://stackblitz.com/ and gitpod.io would work great for me. If the code has only few dependencies, you could also share it as a codeblock.

4

Hello @dmonad –

Thanks for the quick reply. Here’s the standalone test:

const Y = require('yjs');

stateOfFirstDoc = Uint8Array.from(
  [1, 12, 179, 149, 176, 177, 9, 0, 39, 1, 7, 99, 111, 110, 116, 101, 110, 116, 
   8, 100, 111, 99, 117, 109, 101, 110, 116, 0, 7, 0, 179, 149, 176, 177, 9, 0, 
   1, 39, 0, 179, 149, 176, 177, 9, 1, 8, 99, 104, 105, 108, 100, 114, 101, 110,
   0, 7, 0, 179, 149, 176, 177, 9, 2, 1, 39, 0, 179, 149, 176, 177, 9, 3, 4, 
   116, 101, 120, 116, 2, 4, 0, 179, 149, 176, 177, 9, 4, 1, 103, 129, 179, 149,
   176, 177, 9, 5, 7, 132, 179, 149, 176, 177, 9, 12, 2, 101, 108, 40, 0, 179, 
   149, 176, 177, 9, 3, 6, 111, 98, 106, 101, 99, 116, 1, 119, 4, 116, 101, 120,
   116, 40, 0, 179, 149, 176, 177, 9, 1, 6, 111, 98, 106, 101, 99, 116, 1, 119,
   5, 98, 108, 111, 99, 107, 40, 0, 179, 149, 176, 177, 9, 1, 4, 116, 121, 112,
   101, 1, 119, 4, 108, 105, 110, 101, 40, 0, 179, 149, 176, 177, 9, 1, 4, 100,
   97, 116, 97, 1, 118, 0, 1, 179, 149, 176, 177, 9, 1, 6, 7]);

updateForFirstDoc = Uint8Array.from(
  [1, 2, 234, 166, 220, 135, 7, 0, 198, 179, 149, 176, 177, 9, 8, 179, 149, 176,
   177, 9, 9, 6, 115, 116, 114, 111, 110, 103, 6, 34, 116, 114, 117, 101, 34, 
   198, 179, 149, 176, 177, 9, 10, 179, 149, 176, 177, 9, 11, 6, 115, 116, 114, 
   111, 110, 103, 4, 110, 117, 108, 108, 0]);

stateOfSecondDoc = Uint8Array.from(
  [2, 12, 179, 149, 176, 177, 9, 0, 39, 1, 7, 99, 111, 110, 116, 101, 110, 116, 
   8, 100, 111, 99, 117, 109, 101, 110, 116, 0, 7, 0, 179, 149, 176, 177, 9, 0, 
   1, 39, 0, 179, 149, 176, 177, 9, 1, 8, 99, 104, 105, 108, 100, 114, 101, 110,
   0, 7, 0, 179, 149, 176, 177, 9, 2, 1, 39, 0, 179, 149, 176, 177, 9, 3, 4, 
   116, 101, 120, 116, 2, 4, 0, 179, 149, 176, 177, 9, 4, 4, 103, 111, 108, 102,
   132, 179, 149, 176, 177, 9, 8, 2, 32, 104, 132, 179, 149, 176, 177, 9, 10, 4,
   111, 116, 101, 108, 40, 0, 179, 149, 176, 177, 9, 3, 6, 111, 98, 106, 101, 
   99, 116, 1, 119, 4, 116, 101, 120, 116, 40, 0, 179, 149, 176, 177, 9, 1, 6, 
   111, 98, 106, 101, 99, 116, 1, 119, 5, 98, 108, 111, 99, 107, 40, 0, 179, 
   149, 176, 177, 9, 1, 4, 116, 121, 112, 101, 1, 119, 4, 108, 105, 110, 101, 
   40, 0, 179, 149, 176, 177, 9, 1, 4, 100, 97, 116, 97, 1, 118, 0, 2, 234, 166,
   220, 135, 7, 0, 198, 179, 149, 176, 177, 9, 8, 179, 149, 176, 177, 9, 9, 6, 
   115, 116, 114, 111, 110, 103, 6, 34, 116, 114, 117, 101, 34, 198, 179, 149, 
   176, 177, 9, 10, 179, 149, 176, 177, 9, 11, 6, 115, 116, 114, 111, 110, 103, 
   4, 110, 117, 108, 108, 0]);

updateForSecondDoc = Uint8Array.from(
  [0, 1, 179, 149, 176, 177, 9, 1, 6, 7]);

describe('standalone', () => {
  it('test', () => {
    const yi = new Y.Doc();
    Y.applyUpdate(yi, stateOfFirstDoc);
    Y.applyUpdate(yi, updateForFirstDoc);

    const yj = new Y.Doc();
    Y.applyUpdate(yj, stateOfSecondDoc);
    Y.applyUpdate(yj, updateForSecondDoc);

    expect(Y.encodeStateVector(yi)).toEqual(Y.encodeStateVector(yj));
    expect(Y.encodeStateAsUpdate(yi)).toEqual(Y.encodeStateAsUpdate(yj));
  })
})

Per node_modules/yjs/package.json, I’m currently running against Yjs 13.4.9.

Thanks!

5

Thanks @kjohnson,
that helped me to figure out the issue.

First note that ydoc.getMap('content').toJSON() is the same for all clients.

I noticed that yi has two deleted formatting attributes while yj does not. This is why the updates don’t have the same length. Here is some background about formatting:

Internally, Yjs manages formatting as markers in the text: {bold:true}some text{ bold: null }. Assume User1 deletes "some" and User2 deletes "text" (resulting in two different document updates). When we apply both document updates at User3, User3 creates a third document update that deletes the formatting attributes (because the inner content is now deleted). This document update must also be applied at other clients.

I modified your test and listened to these events:


/**
 * There is some custom encoding/decoding happening in PermanentUserData.
 * This is why it landed here.
 *
 * @param {t.TestCase} tc
 */
export const testForumIssue = async tc => {
  const stateOfFirstDoc = Uint8Array.from(
    [1, 12, 179, 149, 176, 177, 9, 0, 39, 1, 7, 99, 111, 110, 116, 101, 110, 116,
      8, 100, 111, 99, 117, 109, 101, 110, 116, 0, 7, 0, 179, 149, 176, 177, 9, 0,
      1, 39, 0, 179, 149, 176, 177, 9, 1, 8, 99, 104, 105, 108, 100, 114, 101, 110,
      0, 7, 0, 179, 149, 176, 177, 9, 2, 1, 39, 0, 179, 149, 176, 177, 9, 3, 4,
      116, 101, 120, 116, 2, 4, 0, 179, 149, 176, 177, 9, 4, 1, 103, 129, 179, 149,
      176, 177, 9, 5, 7, 132, 179, 149, 176, 177, 9, 12, 2, 101, 108, 40, 0, 179,
      149, 176, 177, 9, 3, 6, 111, 98, 106, 101, 99, 116, 1, 119, 4, 116, 101, 120,
      116, 40, 0, 179, 149, 176, 177, 9, 1, 6, 111, 98, 106, 101, 99, 116, 1, 119,
      5, 98, 108, 111, 99, 107, 40, 0, 179, 149, 176, 177, 9, 1, 4, 116, 121, 112,
      101, 1, 119, 4, 108, 105, 110, 101, 40, 0, 179, 149, 176, 177, 9, 1, 4, 100,
      97, 116, 97, 1, 118, 0, 1, 179, 149, 176, 177, 9, 1, 6, 7])

  const updateForFirstDoc = Uint8Array.from(
    [1, 2, 234, 166, 220, 135, 7, 0, 198, 179, 149, 176, 177, 9, 8, 179, 149, 176,
      177, 9, 9, 6, 115, 116, 114, 111, 110, 103, 6, 34, 116, 114, 117, 101, 34,
      198, 179, 149, 176, 177, 9, 10, 179, 149, 176, 177, 9, 11, 6, 115, 116, 114,
      111, 110, 103, 4, 110, 117, 108, 108, 0])

  const stateOfSecondDoc = Uint8Array.from(
    [2, 12, 179, 149, 176, 177, 9, 0, 39, 1, 7, 99, 111, 110, 116, 101, 110, 116,
      8, 100, 111, 99, 117, 109, 101, 110, 116, 0, 7, 0, 179, 149, 176, 177, 9, 0,
      1, 39, 0, 179, 149, 176, 177, 9, 1, 8, 99, 104, 105, 108, 100, 114, 101, 110,
      0, 7, 0, 179, 149, 176, 177, 9, 2, 1, 39, 0, 179, 149, 176, 177, 9, 3, 4,
      116, 101, 120, 116, 2, 4, 0, 179, 149, 176, 177, 9, 4, 4, 103, 111, 108, 102,
      132, 179, 149, 176, 177, 9, 8, 2, 32, 104, 132, 179, 149, 176, 177, 9, 10, 4,
      111, 116, 101, 108, 40, 0, 179, 149, 176, 177, 9, 3, 6, 111, 98, 106, 101,
      99, 116, 1, 119, 4, 116, 101, 120, 116, 40, 0, 179, 149, 176, 177, 9, 1, 6,
      111, 98, 106, 101, 99, 116, 1, 119, 5, 98, 108, 111, 99, 107, 40, 0, 179,
      149, 176, 177, 9, 1, 4, 116, 121, 112, 101, 1, 119, 4, 108, 105, 110, 101,
      40, 0, 179, 149, 176, 177, 9, 1, 4, 100, 97, 116, 97, 1, 118, 0, 2, 234, 166,
      220, 135, 7, 0, 198, 179, 149, 176, 177, 9, 8, 179, 149, 176, 177, 9, 9, 6,
      115, 116, 114, 111, 110, 103, 6, 34, 116, 114, 117, 101, 34, 198, 179, 149,
      176, 177, 9, 10, 179, 149, 176, 177, 9, 11, 6, 115, 116, 114, 111, 110, 103,
      4, 110, 117, 108, 108, 0])

  const updateForSecondDoc = Uint8Array.from(
    [0, 1, 179, 149, 176, 177, 9, 1, 6, 7])

  const yi = new Y.Doc()
  const yj = new Y.Doc()

  yi.on('update', (update, origin) => {
    console.log('yi updated')
    if (origin !== 'test') {
      console.log('yi created an extra update that must be sent to other clients')
      Y.applyUpdate(yj, update, 'test')
    }
  })

  yj.on('update', (update, origin) => {
    console.log('yj updated')
    if (origin !== 'test') {
      console.log('yj created an extra update that must be sent to other clients')
      Y.applyUpdate(yi, update, 'test')
    }
  })

  Y.applyUpdate(yi, stateOfFirstDoc, 'test')
  Y.applyUpdate(yi, updateForFirstDoc, 'test')

  Y.applyUpdate(yj, stateOfSecondDoc, 'test')
  Y.applyUpdate(yj, updateForSecondDoc, 'test')

  t.compare(yj.getMap('content').toJSON(), yi.getMap('content').toJSON())

  t.compare(Y.encodeStateVector(yi), (Y.encodeStateVector(yj)))
  t.compare(Y.encodeStateAsUpdate(yi), Y.encodeStateAsUpdate(yj))
}

The above test case doesn’t fail. You can add it to yjs/tests/y-text.tests.js and run npm run debug, or convert it back to mocha.

The output of this test is:

yi updated
tests.js:15418 yi updated
tests.js:15418 yi updated
tests.js:15420 yi created an extra update that must be sent to other clients
tests.js:15426 yj updated
tests.js:15426 yj updated

It shows that there is an update that you don’t send. Once you apply the “extra update”, your test case will work as well :wink:

6

Aha, that makes sense. When I update my test framework to allow for the possibility of “cascading updates”, my issues are resolved.

Thanks for the help!