And also considering to create a youtube video to explain it.
But until that (with more context):
Satellite (metadata server) and Storagenodes should agree on what pieces are stored.
There are multiple solutions for this. For example with Apache Hadoop HDFS / Ozone the Storagenods (they have different names, but I use the Storj names here) reports back to the stored pieces to the metadata server.
It has hard scalability issues, as reports can be very large. To fix this, they implemented incremental reports, which has own problems…
Storj uses the opposite direction, the Satellite sends the list of the stored pieces to Storagenodes, and all the pieces which are not in the list can be deleted.
But still the full list would be a very huge list (like Gigabytes). Instead of a huge list, Storj uses bloom filters which is a probabilistic data structure.
It can categorize each pieces:
surely can be deleted
definitely should be kept
Bloom filter is very small (like 1-2 mbytes), but in exchange, it may miss some deletes (it’s never wrong about the files which should be kept). But eventually all the files will be deleted. (0.5-1.5% overhead is possible, but seeing 7 TB used space vs 4 TB space reported by satellite is a bug.)
An issue just created to double check the current behavior / parameters of the full bloom filter.
