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.76k stars 467 forks source link

Fix deduplication of changes after loading compressed document #446

Closed ept closed 2 years ago

ept commented 2 years ago

Fixes #445

Thanks @okdistribute for reporting the issue. The problem was as follows:

When applying changes we need to detect and ignore any duplicate changes that we've already applied. We do this by checking the change hash against a set of known hashes. However, we try to avoid computing the full hash graph when loading a compressed document, in which case we are not able to accurately detect duplicates, since we don't know most of the hashes.

This patch changes the logic so that when we suspect there is a duplicate change (on the basis of its sequence number), and we haven't already computed the hash graph, then we go ahead and compute the hash graph in order to know for sure whether it's a duplicate or an illegal sequence number reuse. This means we incur the hash graph computation cost only if a duplicate change is applied; if the network layer already avoids duplication, we avoid the hash graph computation.

okdistribute commented 2 years ago

Great thanks @ept, this does the trick!