sparce indexing
基于chunks的去重都要求使用full index，而这RAM一般承受不起，但是纯用disk io就太慢了。所以它利用了数据局部性：
If two pieces of backup streams share any chunks, they are likely to share many chunks. 如果两个segment共享了某个chunk，那么它们很有可能共享很多chunks。
是这样的流程：
- 分段为segment；
- 计算该segment的每个chunk的fp，然后对每个chunk查询其对应的sparce indexing table: <fp, segment_id>，记录可能跟它共享很多chunk的segment的segment_id；
- 读取这些segment_id对应的segment的chunk indexing table（存储在disk中）；
- for every chunks： 重复，copy entry ；不重复，add to new container
- 最后再将该segment的信息写入磁盘，填写sparce indexing表。
而sparce indexing表最一开始，由对input segment进行chunks的随机抽样得出（或者逐渐构建起来，反正大概是这个意思）
可以看到，它将segment info保留在disk中，在RAM中只保留fp2seg_id的映射，每次只需简单从磁盘中读取几个segment info即可，利用数据局部性极大地降低了磁盘IO次数。
Odess采用的就是类似这种capping+sparce indexing的方法。
将sparce indexing从原来的<fp, seg_id>改为<fp, cid>，并且每次只取top T个包含sample chunks最多的容器，从而将对segment进行cap修改为对container进行cap。仔细想想，这样确实依然保证了原算法的核心思想，也属于是segment size = container size的特种了。
不这个<fp, cid>不就是Odess中的recipe（或者说是全局指纹表）吗？乐。Odess也确实体现了这种capping+sparce indexing结合的方法【只不过进行简化了，每个chunk固定取其第一个container】。