#741 ydocs with a lot of deleted map entries (tombstones) leak memory

Hi!

We have some customer docs that contain large amounts of deleted structs around the 10 million mark.

While I acknowledge that this is a lot, the docs are rather long lives and are not huge (~200mb).

When loading these docs into yjs in node / bun / deno, a lot more memory unproportional to the documents size is consumed and is not free'd upon destroying the doc + running the GC. We also observed, that even way more memory is consumed when calling encodeStateAsUpdate - which is free'd at least but does exceed reasonable amounts (75x doc size).

I prepared a repository with a simple reproduction case and some instructions here: https://github.com/Echometer-GmbH/yjs-large-file-leak

The repo also contains more detailed instructions on how to run it - should be pretty easy to do!

I tested both Bun and Deno as a runtime - behavior is similar except that Deno crashes with OOM while bun stays alive at least.

Observed Behavior for the test doc generated by the included script

Document load spikes memory usage to around 4GB (20x doc size)
Calling encodeStateAsUpdate spikes the memory usage to around 15GB (~75x doc size). However, it seems that this memory is at least free'd once it finished running.
After calling ydoc.destroy() and forcing the garbage collector to run, the memory consumption stays at ~4GB.

Environment Information

Node.js / Bun / Deno
13.6.27

Additional context The repo contains a script to generate a ydoc that reproduces the issue. The script generates a 244mb file which spikes the memory usage to at least 16gb for some time - if you do not have that much free memory available, you can reduce the ydoc size by editing the bulkUpdaterRuns variable in constants.ts to a smaller value and regenerating the file as instructed in the repo's README.md.

I'm a sponsor
[ x] This issue is a blocker for my project.