search

automerge / automerge-classic

A JSON-like data structure (a CRDT) that can be modified concurrently by different users, and merged again automatically.
http://automerge.org/
MIT License
14.75k stars 466 forks source link

Syncing with a third node when one node has a missing dependency #394

Closed ept closed 3 years ago

ept commented 3 years ago

This PR fixes a bug reported by @skokenes. He was occasionally getting the following exception:

TypeError: Cannot read property '8' of undefined
  at decodeChangeMeta (backend/columnar.js:783:13)
  at /Users/martin/dev/cl/automerge/backend/sync.js:383:62
  at Array.filter (<anonymous>)
  at Object.generateSyncMessage (backend/sync.js:383:33)
  at Object.generateSyncMessage (src/automerge.js:125:18)

I tracked it down to the following situation in the sync protocol. Say you have two nodes n1 and n2 that are syncing their changes, and due to a Bloom filter false positive n2 doesn't send some change that n1 needs, so n1 now has a missing dependency (what we sometimes call a "hole").

Now before n1 and n2 are able to fill in the missing dependency and complete their sync, n1 also performs a sync with a third node n3. n3 does not have the missing dependency either (only n2 has it), but n1 is nevertheless going to ask n3 for that missing dependency in the need part of its sync message.

The exception that @skokenes would happen when n3 received such a message with a need asking for a change that it does not have. That was easy enough to fix (n3 simply doesn't send a change in response). However, while writing a test for this situation I also found an infinite loop bug: as long as n1 had a missing dependency, generateSyncMessage on n1 would always return a message with a need field; n1 would never give up sending need messages. If n2 went offline without ever sending n1 the missing change, then n1 would never stop asking n3 for that change (even though n3 cannot do anything about it).

I therefore also changed the logic to only send a sync message if the nodes' heads differ or if there is a change to be sent; merely having a need is not sufficient condition to send a sync message if the heads are the same. I think that change is safe (the tests now pass anyway), but I could do with an extra pair of eyes to check my reasoning there.

@pvh could you take a look please?

okdistribute commented 3 years ago

Oh I ran into this today too. Thanks!

pvh commented 3 years ago

Okay, I can't think of any case where this is a problem and did give it a good think... I guess we should merge it and keep an eye out for issues.