# New IPFS GC rev2

## Problem with Current Garbage Collector
The current garbage collector implementation causes significant delays during a GC cycle, as it locks the entire blockstore during the GC cycle preventing other activity. The lock is held for a potentially long time while GC filters out blocks that are pinned or within the MFS tree, and deletes the remaining blocks. For large pin sets, this is expensive in both memory and time.

## Solution Overview

### Blocks are Reference-Counted
IPFS will maintain reference counts for blocks. When a block is part of content that is pinned or added to MFS, the block's reference count is increased. Reference counts are decreased when content is unpinned or removed from MFS. Reference counts are only stored for counts > 0.

Garbage collection performance issues arise because the previous GC attempts to remove blocks by loading a set of all pinned CIDs into memory and searching for each block’s CID in this set. In this new design, GC will instead examine a block's reference count to determine if a block can be deleted. This removes the need to load all pinned CIDs into memory.

:::warning
TODO: Are reference counts changed by anything other than pinning or MFS?
:::

### Bulk GC
A GC cycle that removes all unreferenced blocks will only have to look at a block's reference count before deciding whether or not to remove the block. This is faster than searching the entire set of pinned blocks. This also saves time and memory since the a set of pinned CIDs does not need to be constructed in memory.

Bulk GC is performed the same way as the previous GC implementation.

### Targeted GC
Targeted GC means that the IPLD DAG starting at a specific CID is walked down to the leaves, and all associated blocks that have a 0 reference count (not pinned or part of MFS), and are not part of any other DAG, are removed. This operation would typically be performed after removing pins or after removing items from MFS, to delete that old content.

This is faster than bulk GC since only a specific set of blocks needs to be needs to be examined collected, whereas with bulk GC all blocks need to be checked to see if they are collectible. For pinning services, this may be the only form of GC necessary since blocks become unreferenced only when content is unpinned.

Targeted GC is performed by passing a CID when invoking garbage collection. As a convenience, it can also be performed as part of removing pins or items from MFS.

### Incremental/Concurrent GC
:::info
Incremental and concurrent GC are not required for the initial implementation.
:::

GC can run relatively concurrently with other portions of IPFS that access the block store. Each GC cycle can some set of candidate blocks to remove without exclusively locking the blockstore. At the end of the cycle, GC will check that the candidate blocks exist, are not references or in an exclusion set, and then delete the blocks. The set of blocks is kept small to minimize the lock time for the check and delete. By removing small groups of unreferenced blocks at a time, GC can run without disrupting other operations, incrementally removing unreferenced blocks

Logically deleting blocks may allow GC to quickly mark blocks as deleted, and make those blocks unavailable to the rest of the system. The a background GC process could cleanup to actual storage. Note: The added complexity of logical deletion needs to be evaluates against any blocking time saved.

Note, It may be useful to better choose which blocks are better candidates by looking at:
- Blocks in same DAG
- Last use time
- Fequency of use
- Size

### Excluding New Content from GC
Newly arrived blocks need to be protected from concurrent GC. When new blocks are being fetched, the session responsible for fetching a DAG will keep a set of CIDs fetched. GC will exclude any blocks from collection that exist in an active fetch set. Maintaining a GC exclusion set can be done when pinning, adding files, etc. by starting a new session.

Note: From the perspective of every session/transaction, GC will always have happend either before the transaction started, or after it ended, because everything the transaction touches will be excluded from GC.

:::warning
Is this really necessary?

- warpfork suspects: yes. Think I've heard anecdatal reports from partners that attempt to run IPFS-a-a-S that they effectively don't run GC in prod because of the lack of safety for concurrent puts.
:::

### Metrics
When GC runs it will keep metrics for each run:
- Total blocks searched
- Blocks with 0 external reference count
- Blocks with 0 reference, but in exclusion set
- Blocks with 0 reference, but with >1 parent
- Blocks collected (marked for removal)
- Blocks removed from blockstore
- Total time to complete GC cycle

The metrics track GC progress over time and can be used to tune GC settings, such as frequency of execution and maximum storage settings.

### Diagnostics
The metrics can be checked against the blocks in the block store for accuracy. If there are no changes to the local IPFS content, then the blocks in the block store should be consistent with the last GC metrics.

Functionality to verify all block references counts should also exist. If a block has a nonzero reference count, then there must be pinned or part of content in MFS. The value of the nonzero reference count should be verified by determining that it matches the number of pins and number items of MFS content that refer to the block.

## Implementation

### Reference Count Storage
Reference counts will be stored as key-value pairs using the `Datastore` interface from `go-datastore`. The key will be a multibase-base64 encoded CID, and the value will be an int32.

The datasore used will be the same used to store pins. Reference counts will be stored in a `/refcounts/` namespace.

An extra datastore action per ref-count change should not be too expensive. The datastore should keep the changes in memory and will only write these when flushed, which will happen at the end of pinning or adding content to MFS is complete. Even if this does incur some expense, it is only incurred at these specific times, when the DAG is already being traversed.

#### External vs Internal References
These reference counts are "external" reference counts and are changed by pinning and MFS. These are different from "internal" reference counts which are references from other blocks in the blockstore. Internal reference counts are kept by the blockstore itself.

Currently, internal reference counts are not available. This GC implementation does not strictly depend on having internal reference counts. If the blockstore implementation does not make internal reference counts available then these are not part of the decision about whether to delete a block. If a unreferenced block is part of multiple DAGs, and the block gets deleted when one of the dags is deleted, this is OK. If/when the remaining DAG is traversed, the missing block will be re-retched. Remember, the deleted block was unreferenced, so it is not like it was pinned or in MFS.

### Pinner Changes

#### Recursive Pins
When adding a recursive pin, the pinner walks the IPFS DAG starting with the CID being pinned. This is done by calling `merkledag.FetchGraph` which fetches all the content and stores it on the local node. A new version of FetchGraph should either:
1. Increment block reference counts for all blocks referenced by the DAG. Or...
2. Return a list of block CIDs so that the reference counts for those blocks can be incremented.

This could be implemented without any changes to `go-merkeldag` but would require a separate walk of the DAG. Since the pinner already walks the DAG to fetch all nodes when adding a pin, it would be most efficient to be able to increment reference counts during this walk, or return a set of all blocks referenced by the walked DAG

When removing a recursive pin, the DAG referenced by the CID being unpinned will need to be walked to leaves, and all blocks referenced will have their reference decremented.

:::warning
It may be safer to update block reference counts in a single transaction to prevent having invalid reference counts in the case of an error during the pinning or reference update. Invalid high counts would result in unremovable blocks without some other recovery mechanism. Invalid low counts would cause GC to remove content that is pinned or in MFS.
:::

#### Direct Pins
If a block is identified by a CID being directly pinned, then that block's reference count is incremented. When removing a direct pin, the block identified by the CID has it reference count decremented. Both adding and removing a direct pin will require loading the IPLD node for the CID.

### DAG Service Changes
The DAG service needs to provide functionality for walking a DAG and returning a set of all blocks associated with the DAG. This will be used to increment or decrement reverence counts for the blocks.

### MFS Changes
When adding files to MFS, all blocks referenced by the DAG rooted at the CID being copied into MFS, get their reference count incremented.

Modifying a file in MFS decrements ref counts for blocks associated with files old DAG and increments ref counts for blocks associated with file's new DAG.

Changing CID: same as modifying file

#### Directories

When new directorys are created and files copied into those directories, the reference counts of blocks associated with files are not incremented as a result of putting those files in one or more directories. The reference counts are only chnaged when content is added to or removed from MFS.

### Block command changes

The `ipfs block rm` command will need to change to remove the reference count for a block that is removed.

The `ipfs block stat` command should probably show reference count.

### GC command changes

The `ipfs repo gc` command will all have a new `--cid` option:

ipfs repo gc --cid=<cid>

A `-verify` flag will run a check to verify that all referenced blocks have the correct reference count, and that all unreferenced blocks are excluded from deletion or are elligible for deletion.

ipfs repo gc -verify

## Related
- [New GC Proposal Pitch](https://github.com/protocol/web3-dev-team/pull/8)
- [Previous GC design, obsoleted by this one](https://docs.google.com/document/d/1wWbGFZhv4MDLAcasoBFi8VmyEcpUFoWip6na5YmjQDc/edit#heading=h.kyt8xl5gwuc2)
- [GC Design Notes](https://hackmd.io/0T8z0ex8RWmI8BmFNPSafQ?view) from @warpfork

## Proposed Optimizations

**Index blocks with reference count > 1**
Faster to determine which blocks in a set can be deleted.

**Store reference counts for blocks with reference count > 1**
:::info
Storing only reference counts > 1 may offer a significant savings in storage, but means that GC could only be done if given a specific CID to target. Also, when reference counts are incremented, determining if a block gets a reference count > 1 requires checking against all pinned and MFS blocks. Having to create that set in memory is something the new GC is trying to avoid.
:::