Filecoin源码研究 - SectorID 及 ProvingSet
自 go-filecoin 0.3 版本开始，正式引入时空证明（PoSt），时空证明需要矿工对所有有效的算力在一定时间内根据指定的随机参数进行证明，并向网络提交。在 submitPost 消息中需要指明所证明的sector集合。当一个矿工存储的 sector 数量较多的时候，利用什么数据结构来表示这个集合就显得非常重要，因为不同的数据结构将导致此消息参数的长度大不一样。为了高效地实现链同步和空间利用。一个适合于此应用场景的数据结构就非常重要了。本文根据官方的一些讨论和实现，做一些简单分析。
sectorID 集合的使用和特点
那么，在哪些情况下我们需要使用到sector ID的集合呢？简单地说，主要有一下几个方面：
ProvingSet：证明集合，也就是每一轮时空证明时需要全部证明的集合，这个集合要包含在submitPost消息中NextDoneSet：上一次证明过的sector相关ID的集合，这个集合表明所有在上一个周期里证明过的sector，那么至少在一个周期之内都是有效算力FaultSectorSet：因为目前 slash 代码还在实现之中，这个部分的名称还不名确，但这个集合是需要的，这是表明有错误的sector相关ID的集合，有矿工自己汇报，当矿工汇报给网络这些已知错误的sectors后，其抵押会按比例扣除，同时，在证明PoSt的时候就不用再对这些sector进行证明了。
一个矿工拥有的有效sector可能达到数十万上百万个，那就是简单地把每一个sectorID存放到一个集合里面，这样有多少个sector ID，这个集合就有多大，比如100万个，那个这个集合将大得惊人，因为每一个sector ID是一个8字节的数，一百万个就需要8M的空间来存放和传输，对于区块链来说，显然太不高效了。
这种情况下，就要考虑适合于这一应用场景的的数据结构来进行优化。那么同一矿工的sectorID集合有什么特点呢？
在go-filecoin目前的实现中，同一个矿工的 sectorID 是从0开始连续增长的，每一个sectorID会对应存储在磁盘上的一个Sealed Sector。可以想象，这些sector会存储在磁盘或其他介质上，由于磁盘容量的关系，当一个矿工seal的sector数量很大时，这些sector会分布在不同的介质上，可能是在同一台机器上，也有可能在网络中的其他机器上。
然而，磁盘或其他介质总是有寿命的，经常出现的情况是，当一个介质出问题，其上的sector有可能全部失效。这样，如果我们在同一个介质上存储的sector其ID是连续的，sectorID的集合就可能优化。
当然，sectorID是不是要连续，这个不是硬性规定的，每一个矿工可以自行决定，但是，考虑到矿工的submitPost消息也要付Gas用于验证，如果消息体过大，消耗gas就多，每一个矿工当然也希望采用最好的方式来处理。
有哪些办法来对sectorID的集合进行优化存储
最简单的办法
前面提到的简单的办法，就是简单地组成一个集合，那么假设一个矿工有 N 个sectorID 需要组成一个集合，需要的空间量为 8*N 字节，如果需要查询这个集合，最好对这个集合进行排序，排序后可以通过二叉树来进行搜索优化，这样搜索的算法复杂度是 O(logN)。
进一步，通过每一位来表示每一个ID
这种方式仅仅适用于已知sector ID在一个比较小的范围内，那么可以对这个范围内的每一个数代表一位，通过置位的方式来表示此ID是否在集合之中。比如说，我们预计没有矿工会有超过100万个sector，那么我们就可以用100万位来表示，也就是说 220位，相当于 212 （4K）字节。但搜索起来将变得十分简单，因为可以直接定位到位，搜索效率是 O(1)。
但这种方式有很大的局限性，首先是需要事先知道范围，其次是灵活性太差。
go-filecoin 在 0.3 中的实现
在0.3版本中，系统增加了一个数据类型 IntSet，顾名思义，就是整数集合。其实在系统实现中，IntSet仅仅用于 sectorID 的集合，也就是说是 u64 类型的数据集合。
IntSet目前的实现采用 SparseBitArray 的数据结构。具体参见 go-filecoin/types/intset.go 文件，其实现参见一下代码：
// IntSet is a space-efficient set of uint64
type IntSet struct {
ba bitarray.BitArray
}
// NewIntSet returns a new IntSet, optionally initialized with integers
func NewIntSet(ints ...uint64) IntSet {
// We are ignoring errors from SetBit, GetBit since SparseBitArrays never return errors for those methods
out := IntSet{ba: bitarray.NewSparseBitArray()}
for _, i := range ints {
_ = out.ba.SetBit(i)
}
return out
}
SparseBitArray 是一种专门为连续数据节省空间而设计的位阵列数据结构。在其目前的设计中，SparseBitArray采用 unitSlice 的数据结构来进行优化，其具体的做法是：
缺省采用每 64 个连续的数进行分段；对每一个数进行计算，取其除以 64 的整数值（index）和余数（remainder）如果要把一个数加入集合，其 index 插入 unitSlice 集合中，并且对其对应的 u64 的块的相应位置进行置位。删除，合并等操作同样按此处理。
在最好的情况下，连续64个整数，在 SparseBitArray数据结构中占2个u64的空间（16字节），也就是一个unitSlice值和一个全1的u64的block来表示64个连续的数。与传统的数组相比，空间需要仅仅为 1/32。大大提高了空间利用率。
但是，SparseBitArray在数据分布不连续的情况下，效率就很低了。比如对一些完全分散的数据，如果每两个数相差 64 以上，其空间利用率最差，与传统的数组相比，需要两倍的空间来存放。因此，对于Filecoin矿工而言，如果系统实现的消息中采用这种方式，则应尽量采用连续的sectorID。在0.3 版本中，这个采用SparseBitArray表示的集合直接通过 cbor 来进行序列化而后作为 PoSt 相关的消息的参数之一进行传输。
下一步的演进
目前，go-filecoin采用IntSet这样的数据结构，而不是直接采用 SparseBitArray，其实是暗藏玄机的。直接传输SparseBitArray还是非常占用空间，有没有更好的方案来进行转化呢？有的，这个方案，就是采用 RLE+ 的方式来表示 SectorID的集合。
RLE+ 是在 RLE（Run-Length Encoding，游程编码） 的协议实验室改进版。RLE对于连续的数据有很好的压缩效果，主要原理是对连续重复数据进行压缩从而实现空间节省的目的。而 RLE+ 针对 filecoin 的应用场景进行了特别的设计。其语法如下：
<encoding> ::= <header> <blocks>
<header> ::= <version> <bit>
<version> ::= "00"
<blocks> ::= <block> <blocks> | ""
<block> ::= <block_single> | <block_short> | <block_long>
<block_single> ::= "1"
<block_short> ::= "01" <bit> <bit> <bit> <bit>
<block_long> ::= "00" <unsigned_varint>
<bit> ::= "0" | "1"
这个语法定义并不复杂，但继承了协议实验室一贯的风格，那就是兼容和可扩展性。这是一个完全灵活的设计，可以表示小的或很大的范围的数据。这种表示方法，经过测试，比SparseBitArray具有更高的效率，并且可以兼容更多的情况。具体信息可以参阅RLE-Bitset-Encoding文档。这里，每一个block表示连续多少个数在这个集合中或者不在这个集合中。有意思的是，block的设计采用了变长的方式，与传统 RLE 相比，大大节省了空间。
这里需要提一句的是，unsigned_varint 数据类型，这也是 IPFS 开发过程中为 MultiFormats 设计的数据类型，用来表示可变长的无符号整数。可以利用不同的字节长度来表示不同大小的无符号整数，例如，对于0～127间的数，仅仅一个字节就够了，而对于 2^64 这个整数，则需要 9 个字节。这种设计，在与区块链的消息交互中，非常灵活也很高效。具体可以参见 unsigned_varint 文档。
据我所知，RLE+的实现已经在进行之中，不出意外，0.4版本将是基于 RLE+的ProvingSet版本用于 PoSt 相关的消息中。在当前的实现中，矿工节点内部的 ProvingSet 和 NextDoneSet 还是采用 SparseBitArray，但是在与链交互的消息中，这个集合会转换为 RLE+ 的方式来进行序列化，以进一步节省空间。
关于 RLE+ 的实现源码参见：https://github.com/filecoin-project/go-filecoin/tree/master/rleplus
有没有更好的设计呢？
如果数据的连续性非常好，最好的办法就是写出一组组的小集合的首位数值就好了。即使其中有些数据没有，还可以通过 bitfield 的方式来进行标记。这也是 BitArray 数据结果可以完全表示的，而且在数据连续性强的情况下，比SparseBitArray 效率高。为什么没有采用这种方式呢？这里可能有两个原因：1）当矿工节点经过长时间运行后，由于一些sector过期的原因，连续性并不是特别高；2）矿工可以自己分配 sectorID 以存放到不同的存储设备上，这也会导致连续性并不如想象中的高。同时，在下一个版本中，利用RLE+对 SectorID Set 进行序列化，本身就是一个非常高效的策略。