You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
More intelligent blockstore garbage collection #3092
The current garbage collector deletes all un-pinned blocks. This makes the system more fragile, as people don't usually pin a lot of objects. And if I have configured my node to keep up to 10GB of data I would also expect it to keep close to that limit at all times.
One solution is to delete blocks at random until the disk usage falls below the threshold limit. But blocks could also be deleted based on supply and demand, or when they were last accessed.
The current garbage collector uses a mark-and-sweep algorithm, but another option would be to use reference-counting, and I think that is better.
It might also be good to have both a min and max threshold, and have a garbage collection that only removed things until the min threshold was reached. It could be automatically triggered at the max threashold, as is done now.
@jakobvarmose how would your reference counting idea work? would it count existing references to blocks? or would it simply increment some counter each time a block is referenced by another object?
I agree 100% that the current GC implementation is a bit... blunt. The issue is that the marking phase is relatively expensive, so doing smaller runs is not cheap. There has been some previous discussion towards this topic here: ipfs/notes#130
One related topic i was talking about earlier (for ipfs block rm) was keeping a bloom filter of pinned objects stored on disk to expedite pin checking. This could also help out here for a partial GC.
@jakobvarmose how would your reference counting idea work? would it count existing references to blocks? or would it simply increment some counter each time a block is referenced by another object?
I would add two new variables associated with each block:
directPin bool
refCounter uint
When an object is pinned directly just set b.directPin = true. When recursively pinning an object increment b.refCounter on that block and on each of its descendants.
To check if a block is pinned simply do b.directPin || b.refCounter > 0.
@jakobvarmose yeah, we used to do that. It was really slow, and expensive. We have thousands to millions (or more) of blocks. Blocks may also be very small, and the overhead of that reference information would be significant. Every pin operation would need to iterate over every child block and update every entry for that child block.
@whyrusleeping Oh, I didn't know. Yeah, it would use quite a bit of memory. But I can't see how it would be much slower, as the current implementation also reads each child block from disk, and this is probably the slowest part. Unpinning will of course be slower, but pinning should be about the same speed. Or what am I missing?
@jakobvarmose no, currently when you pin and unpin we only update list of root hashes, reference counting would require to iterate whole hash tree and update the reference count.
@whyrusleeping I was wondering about why we won't use reference counting for indirect pins. How is that worse than what we have to do now. How is it worse to have to iterate over every child of a single recursive pin to update it worse than having to always iterate over every child of every recursive pin just to check if a block is pinned. The checking operation would seam to me to be more frequent than the updating operation.
Have we considered storing the indirect pinned blocks individually in the datastore. That is for example for each indirectly pinned block have an entry under the name "/local/pins/indirect/". This will have disk space overhead, but since it is no longer in memory will scale well. The underlying leveldb is designed to be fast so at this point I am having a hard time understating that a mass update could be really slow.
The cost of checking pins will become more of an issue once "block rm" lands (#2962) and also in my filestore code (#2634).
A bloom filter will help in the case that a block is not pinned, but to make sure it is we will still have to iterate over every child of every single recursive pin.
@kevina we've been down this road before. The disk overhead is significant, the cost to pin large objects becomes relatively obscene. If you want to dig into it more, go check out the old code and PRs
Another related idea: To make GC faster instead of simply marking, count the number of references (you could call it count-and-sweep), and store this result to disk. Additionally store incremental updates of recursive pins. The next time the garbage collector is run it will read the results from last time, and update incrementally.
Maybe we should review proper gc algorithms and find something that matches
our perf needs (re algorithmic complexity)
On Wed, Aug 17, 2016 at 22:43 Jakob Varmose Bentzen < notifications@github.com> wrote:
Another related idea: To make GC faster instead of simply marking, count
the number of references (you could call it count-and-sweep), and store
this result to disk. Additionally store incremental updates of recursive
pins. The next time the garbage collector is run it will read the results
from last time, and update incrementally.
Activity
JesseWeinstein commentedon Aug 17, 2016
It might also be good to have both a min and max threshold, and have a garbage collection that only removed things until the min threshold was reached. It could be automatically triggered at the max threashold, as is done now.
whyrusleeping commentedon Aug 17, 2016
@jakobvarmose how would your reference counting idea work? would it count existing references to blocks? or would it simply increment some counter each time a block is referenced by another object?
I agree 100% that the current GC implementation is a bit... blunt. The issue is that the marking phase is relatively expensive, so doing smaller runs is not cheap. There has been some previous discussion towards this topic here: ipfs/notes#130
One related topic i was talking about earlier (for
ipfs block rm) was keeping a bloom filter of pinned objects stored on disk to expedite pin checking. This could also help out here for a partial GC.jakobvarmose commentedon Aug 17, 2016
I would add two new variables associated with each block:
When an object is pinned directly just set
b.directPin = true. When recursively pinning an object incrementb.refCounteron that block and on each of its descendants.To check if a block is pinned simply do
b.directPin || b.refCounter > 0.whyrusleeping commentedon Aug 17, 2016
@jakobvarmose yeah, we used to do that. It was really slow, and expensive. We have thousands to millions (or more) of blocks. Blocks may also be very small, and the overhead of that reference information would be significant. Every pin operation would need to iterate over every child block and update every entry for that child block.
jakobvarmose commentedon Aug 17, 2016
@whyrusleeping Oh, I didn't know. Yeah, it would use quite a bit of memory. But I can't see how it would be much slower, as the current implementation also reads each child block from disk, and this is probably the slowest part. Unpinning will of course be slower, but pinning should be about the same speed. Or what am I missing?
Kubuxu commentedon Aug 17, 2016
@jakobvarmose no, currently when you pin and unpin we only update list of root hashes, reference counting would require to iterate whole hash tree and update the reference count.
kevina commentedon Aug 18, 2016
@whyrusleeping I was wondering about why we won't use reference counting for indirect pins. How is that worse than what we have to do now. How is it worse to have to iterate over every child of a single recursive pin to update it worse than having to always iterate over every child of every recursive pin just to check if a block is pinned. The checking operation would seam to me to be more frequent than the updating operation.
Have we considered storing the indirect pinned blocks individually in the datastore. That is for example for each indirectly pinned block have an entry under the name "/local/pins/indirect/". This will have disk space overhead, but since it is no longer in memory will scale well. The underlying leveldb is designed to be fast so at this point I am having a hard time understating that a mass update could be really slow.
The cost of checking pins will become more of an issue once "block rm" lands (#2962) and also in my filestore code (#2634).
A bloom filter will help in the case that a block is not pinned, but to make sure it is we will still have to iterate over every child of every single recursive pin.
whyrusleeping commentedon Aug 18, 2016
@kevina we've been down this road before. The disk overhead is significant, the cost to pin large objects becomes relatively obscene. If you want to dig into it more, go check out the old code and PRs
kevina commentedon Aug 18, 2016
Some references for why we no longer store information on indirectly pinned blocks in the datastore: #1192 #1225 #1381 #1420
jakobvarmose commentedon Aug 18, 2016
@Kubuxu When unpinning you are right that the current implementation runs very quickly. But when pinning all child blocks are read from the datastore (see https://github.com/ipfs/go-ipfs/blob/master/pin/pin.go#L140-L144).
jakobvarmose commentedon Aug 18, 2016
Another related idea: To make GC faster instead of simply marking, count the number of references (you could call it count-and-sweep), and store this result to disk. Additionally store incremental updates of recursive pins. The next time the garbage collector is run it will read the results from last time, and update incrementally.
jbenet commentedon Aug 18, 2016
Maybe we should review proper gc algorithms and find something that matches
our perf needs (re algorithmic complexity)
On Wed, Aug 17, 2016 at 22:43 Jakob Varmose Bentzen <
notifications@github.com> wrote:
whyrusleeping commentedon Aug 19, 2016
reference: #2030
kevina commentedon Aug 20, 2016
A rather longest IRC discussion: https://botbot.me/freenode/ipfs/msg/71626736/ (Starting around 9 pm PDT on Aug 19). No real consensus but lots of ideas and background info.
whyrusleeping commentedon Sep 3, 2017
ref: #4149