Bloom frequency table based garbage collector

[Kubuxu]

Current garbage collector in ipfs is really simple: something either is pinned or thrown out.
It isn't really garbage collector in this state, it is just "clear cache" command.

Here is an idea for a garbage collector that would probabilistically remove unused data leaving used in ipfs repo.

freq is 1MiB byte array filled with zeros at the start. This array is stored to disk on shutdown and periodically but its loss doesn't really matter, meaning that for the most time the overhead is minimal.
After each garbage collection round (and at the begging) a nonce is chosen (32bits should be enough) which is random.

When block from disk is accessed its IPFS hash is hashed with nonce using the MurmurHash3 32bit (52 x86 instructions, 5GiB/s throughput- more info here) and truncated to 20 bits. This 20 bits number denotes index in the freq array. Byte under this index is incremented up to 255 in which case it stays that way.

When repo runs out of space or user triggers manual garbage collection the removal threshold has to be calculated. Zeros are discarded from freq array, rest is sorted, this way cumulative frequency data is obtained. This allows for calculation which value in freq array is threshold for given percentage of space freed (there might be better way of doing it). The requested percentage will be depending on user input (the user can decide how much space should be freed) or automatic calculations (settings and space quotas) if automatic garbage collection is being performed.

Then the block storage is being walked and each block is first checked against pins, then its MurMur hash is checked against freq array. If it is lower than decided threshold the block is discarded.

This garbage collection algorithm has major benefits over our current one. It will leave frequently used data in cache and remove those rarely used. This might not always be what user requests (example: some rarely used manual) but then there is always pining.

It would also make garbage collection with files API less noticeable, files inside this API will usually be used more frequently used so they won't be garbage collected.

[whyrusleeping]

I do definitely want to move towards a better GC. Using a bloom filter is likely going to be a requirement as we won't be able to store larger pinsets in memory (as ipfs scales).

The frequency table is similar to an idea I had to make an ipfs block journal, Although my idea was for an lru cache type system.

This would also help out for things like making object api calls. Creating a bunch of ephemeral objects that we still are working with and don't want to lose, but that we don't want to pin yet because they arent complete.

The advantage an lru has over a frequency table is that objects that are only used once, but used immediately before the garbage collection is run, it stands a very good chance of being removed.

[Kubuxu]

The frequency table could be modified to function like LRU with introduction of ageing. Increase the frequency by bigger value (10) per access and once a few hours hour (or less frequently) multiply all values in table by some ratio (9/10) with rounding up, going through a million ints won't take that much for modern cpu. This way newly accessed blocks should almost never be removed from the storage.

Bloom filters would be almost perfect for pinsets, but their sizes and counts will have to be chosen very carefully to minimize number of false positives. To keep from keeping some false positive blocks forever, nonced reshasing of the filters blooms would have to be performed from time to time (every few gcs).

[jbenet]

Frequency based GC is a great idea. but should be turned on with a flag or subcommand. ipfs repo gc MUST remove all unpinned things. this is a spec requirement.

Recommend taking a look at various GC papers-- there's lots of great stuff out there. :)