V13 Garbage Collection Question

[emreeren]

Hello. I'm trying to implement a function for indexed-db connector to remove gc'ed entries from database but I didn't understand how GC items gets created. I'm working on text-area sample and tried to debug it but couldn't trigger GC item creation while adding - editing text. I also enabled GC by using new {gc:true} option.

While debugging I noticed some gc stuff implemented for Type.js class. Should I delete the type to enable GC ? Other than Type.js's gcChildren() method nothing appears to call _gc() method of the Item class. I'll be glad to know if I'm missing something.

_{Huly®: YJS-107}

[cb22]

Hey @emreeren

I'm not sure if you ever figured anything further out, but after a fair amount of digging, I came to the conclusion that so far GC has only been implemented for deleting types (ie, a YArray) as opposed to entries in those types (ie, deleting array items) - @dmonad please correct me if I'm wrong.

The solution I've hacked together for my application - which seems to work with some very light testing is:

let item = y.share.myType._start
while (item !== null) {
  if (item._deleted) {
    const desiredParent = item._parent
    const desiredParentSub = item._parentSub
    const desiredOrigin = item._origin
    item._gc(socket.room.y)
    if (item._right) {
      item._right._parent = desiredParent
      item._right._origin = desiredOrigin
      item._right._parentSub = desiredParentSub
    }
  }
  item = item._right
}

This walks the linked list and GCs any unused items. The critical bits are:

1. You need to have {gc: true} enabled
2. If an item is GC'd, it sets the next item's parent to be the GC'd item's parent. Without this, when the 'client' tries to integrate the change, it will see that the parent was deleted and thus try and delete everything following the GC'd entry (ie, if you have abcd and delete b, cd will disappear too. This happens in _integrateRemoteStructHelper (it seems like this is only a concern for Y.Text)

With my application, I only really need to perform this once in a while, and it can be done on a central server when it's reasonably sure that there are no clients connected to a particular room (for compacting the state before writing it to a database).

[cb22]

Just to add to my comment above; I could never get that hack working properly or reliably in the end (for Y.Array, at least. It seemed to be fine for Y.Text).

I implemented a very clunky workaround by (after the last client has disconnected and been disconnected for more than a few minutes) creating a new Y instance and copying the actual data across into the new instance, before serializing that into the database.

When a client tries to connect to the same room, it loads the 'compacted' serialized data and all works well. This would fail pretty hard if a client was still running but merely offline for an extended period of time though!

[adabru]

Referring to emreeren's comment on using indexed-db + gc, YjsPaper.pdf section 3.5 states:

Furthermore, due to its design, the garbage collector in
YATA may break late join mechanisms. This is because
when a user is offline for a period longer than t seconds,
it will still hold references to deleted operations, while on-
line users who already performed certain removals do not.
Therefore, YATA does not support garbage collection for a
site while it is offline.

For my application not freeing memory would cause the browser client to run out of memory some time, I guess. Also initial load is affected. On my server it's no problem to keep the whole history.

@cb22 I have no better idea than your workaround and will also go for serializing and recreating the whole database from time to time. For the client it seems ok to turn from 'indexed-db' to 'memory' in my use case.

Maybe one possible yjs patch that can solve the issue would be to support specifying a 'master id' (the always-online server) that can overwrite the history from other clients in a differential way, declining potential conflicting changes from late joiners (it's their own fault to join that late anyways).

[emreeren]

@cb22 as my understanding it works fine for map of arrays without a modification. GC does not work for items deleted from the array but it works for arrays deleted from map. So to GC an array it is possible to delete the array entirely, recreate it and re-add non deleted items. This might not work fine for all cases but better than nothing.

I still couldn't figure out how to sync a GC'd array to indexed-db. Dropping indexed-db and let connector to recreate it might be a solution but I'm not sure how it should be implemented.

For my specific application a manual method to trigger GC and ignore all pending offline updates before GC will work fine but I don't know if it is something that should be implemented in YJS.

[emreeren]

For my application not freeing memory would cause the browser client to run out of memory some time,

@adabru I encountered something similar and in my case that relates with writeVarString method of Encoder.js. NodeJS appears to allocate a lot of heap when encodeURIComponent gets called and same thing appears to happen in Chrome Browser too. This is not an issue for existing clients but when a new client joins and needs to receive around 20MB's of data, heap usage increases to 200MB for a short period. It quickly releases after sync completes but Raspberry PI can't handle this and app crashes. Also my free heroku test server (500 MB memory limit) appears to reset when that happens. I could decrease memory usage by preventing writeVarString method to duplicate the data in memory but I gave up when I noticed a source code todo comment regarding full rewrite.

[dmonad]

I want to bring v13 finally to a stable release. So I decided not to implement a replacement for the GC found in v12.

But there will be garbage collection. As @cb22 noted, garbage collection only applies to deleted children. That means that any child of a deleted type will be removed from memory.

For deleted structs (that are not garbage collected), the _content will be set to null <- this is currently not implemented.

There will be a more involved GC implementation in the future. But I wonder if this is even necessary with the improved encoding introduced in v13.

@emreeren How can I reproduce this problem with encodeURIComponent? This (native) function is called to transform strings to encode strings to utf8.

If you want you can try again, I finally completed my TODO and did a full rewrite ;-)