Garbage collection about yorkie HOT 2 CLOSED

Other CRDT libraries garbage collection and tombstone.

Y.js:

We can't garbage collect deleted structs (tombstones) while ensuring a unique order of the structs. But we can 1. merge preceeding structs into a single struct to reduce the amount of meta information, 2. we can delete content from the struct if it is deleted, and 3. we can garbage collect tombstones if we don't care about the order of the structs anymore (e.g. if the parent was deleted).

https://github.com/yjs/yjs/blob/705dce78384bac8f25fa11d05e3b2551325a5d26/README.md#yjs-crdt-algorithm

Automerge

Yes, RGA uses tombstones. I think this is okay for now, as in most cases, the tombstones are not really the dominant cost. Also, I think it is desirable to retain history (so you can see what was changed when), and that requires remembering deleted parts of the document anyway.
automerge/automerge#221 (comment)

from yorkie.

Yorkie's GC logic looks like this:

• Agent returns MinPulledTicket to the client in the response of PushPull API
  • find min_pulled_server_seq

    document `d1` server_seq: 10
    client `c1` server_seq: 5
    client `c2` server_seq: 7
    
    min_pulled_server_seq: 5
    

  • create MinPulledTicket, time.Ticket of min_pulled_server_seq
• The client purge elements(marked with tombstone) that were removed earlier than the MinPulledTimeTicket received in response to PushPull.

from yorkie.