Bupstash垃圾收集器

我的备份工具bupstash将备份作为一组不断增长的加密数据树存储在存储库中，这些数据树使用内容寻址和结构共享来消除重复数据。为了删除未使用的备份，我们需要执行与多种编程语言非常相似的操作，以释放未引用的内存-垃圾回收。出于好奇，本文将解释bupstash中垃圾收集器的演变和实现。

bupstash垃圾收集器的最初版本是一个幼稚的世界垃圾收集器。它遍历所有备份数据树，以创建一组可访问的数据块（按地址），然后删除不可达的数据。

在all_backups（）中用于data_tree的lock_repository（）reachable_addresses = empty_set（）：work_list = new_work_list_from_backup（data_tree.root_address）直到work_list.is_empty（）：node_height，node_address = work_list.pop（）reachable_addresses.add（nodeeightaddress！） ：存储库中的块地址的add_child_nodes_to_worklist（work_list，node_address）：如果没有可达地址.has（chunk_address）：delete_chunk（chunk_address）unlock_repository（）

该算法简短有效，但是如果存储库很大，则可能很长一段时间我们的存储库都不可用。下一版本大大缩短了存储库的停机时间。

由于许多备份彼此共享数据，因此我们可以记住步行阶段以跳过工作。

因为在存储库未锁定时备份是不可变的，所以我们可以在不停步的情况下完成大部分备份。

这次，我们在没有锁定存储库的情况下遍历存储库，然后将其锁定并使用我们的备忘录再次遍历存储库以快速完成作业。如果在我们的第一个步骤中出现了任何新的备份，则保证已保存存储库锁定，因此我们将对其进行标记。在不锁定存储库的情况下执行大部分慢标记阶段将大大提高存储库可用于其他操作的可用性。

walked_trees = empty_set（）reachable_addresses = empty_set（）func walk_repository（）：用于all_backups（）中的data_tree：如果walked_trees.has（data_tree）：继续walked_trees.add（data_tree）work_list = new_work_list_from_backup（data_tree.is ）：node_height，node_address = work_list.pop（）has_walked = reachable_addresses.has（node_address）reachable_addresses.add（node_address）如果node_height！= 0且尚未被walked：add_child_nodes_to_worklist（work_list，node_address）walk_repository（）lock_repository（）存储库中的chunk_address：如果不可达，则为has（chunk_address）：delete_chunk（chunk_address）unlock_repository（）

在bupstash中，每个数据块地址为32个字节，这意味着我们必须在存储库中每个块至少有32个字节的RAM才能成功执行垃圾回收。对于包含1亿块或更多块的存储库，这很容易耗尽繁忙或小型系统上的内存。

如果我们愿意接受保留一些额外数据的可能性非常低，则可以将其减少到每块几位，从而将内存使用量减少64倍或更多，为此，我们使用一种称为Bloom Bloom的概率数据结构来跟踪可访问数据地址。

他们可能有误报。对我们来说，这意味着我们可能会意外释放实际上可以释放的数据块。

由于每个地址的内存使用量非常低，因此即使对于大型存储库，我们也可以慷慨地设置Bloom过滤器的大小，从而将误报率降低到小于百分之一。

我们可以很容易地检测出Bloom过滤器何时变得过满并产生许多误报，从而为将来的垃圾收集调整其大小。

另外，bloom过滤器的bupstash实现实际上比哈希表更简单，实现的权重约为30行代码以及测试和帮助程序。

walked_trees = empty_set（）walked_addresses = empty_cache（）reachable_addresses = empty_bloom_filter（repository_bloom_size（））func walk_repository（）：用于all_backups（）中的data_tree：如果walked_trees.has（data_tree）：继续walked_trees.back（list_upload_list_ups） .root_address）直到work_list.is_empty（）：node_height，node_address = work_list.pop（）has_walked = walked_addresses.has（node_address）reachable_addresses.add（node_address）walked_addresses.add（node_address）如果node_height！= 0而不是not_walked：add_child_node_to work_list，node_address）walk_repository（）lock_repository（）walk_repository（）如果​​bloom_filter_overutilized（reachable_addresses）：则增加bloom_filter_size_for_next_gc（）否则如果bloom_filter_underutilized（reachable_addresses），则减少_bloom_filter_size_for_next_g unlock_repository（）

关于此实现的注意事项是，由于Bloom筛选器具有误报，因此我们不能使用它来跳过处理地址，相反，我们必须为此目的引入一个新的缓存。高速缓存还使我们可以为大型存储库设置固定的内存使用上限。

总体而言，对于大型存储库，添加Bloom Bloom过滤器可将内存需求从千兆字节的范围降低到数十兆字节，同时将存储库的大小仅增加百分之一。

bupstash垃圾收集器尽力使存储库尽可能长时间可用，同时还以较小的内存配置文件提供出色的性能。如果您正在实施内容寻址的存储系统，则希望该博文为您提供一些新的想法。

将来，bupstash可能会遵循与编程语言垃圾收集器相同的路径，以寻求更多改进：