16. 多盘散列

16.1. 背景

区块链中的账本数据通常是只增不减,而单盘存储容量有上限。目前单盘最高容量是14TB左右,需要花费4000块钱;以太坊账本数据已经超过1TB,即使是在区块大小上精打细算的比特币账本也有0.5TB左右。区块链账本数据不断增加,单盘容量上限成为区块链持续发展的天花板。 目前对leveldb的多盘扩展方案,大部分是采用了多个leveldb实例的方式,也就是每个盘一个单独的leveldb实例。这种做法的好处是简单,不需要修改leveldb底层代码,缺点是牺牲了多行原子写入的功能。在区块链的应用场景中,我们是需要这种多个写入操作原子性的。所以选择了改leveldb底层模型的技术路线。

16.2. LevelDB数据模型分析

  • Log文件:写Memtable前会先写Log文件,Log通过append的方式顺序写入。Log的存在使得机器宕机导致的内存数据丢失得以恢复;

  • Manifest文件:Manifest文件中记录SST文件在不同Level的分布,单个SST文件的最大最小key,以及其他一些LevelDB需要的元信息;

  • Current文件:LevelDB启动时的首要任务就是找到当前的Manifest,而Manifest可能有多个。Current文件简单的记录了当前Manifest的文件名;

以上3种文件可以称之为元数据文件,它们占用的存储空间通常是几十MB,最多不会超过1GB

  • SST文件:磁盘数据存储文件。分为Level 0到Level N多层,每一层包含多个SST文件;单个SST文件容量随层次增加成倍增长;文件内数据有序;其中Level0的SST文件由Immutable直接Dump产生,其他Level的SST文件由其上一层的文件和本层文件归并产生;SST文件在归并过程中顺序写生成,生成后仅可能在之后的归并中被删除,而不会有任何的修改操作。

../_images/leveldb.png

16.3. 核心改造点

Leveldb的数据主要是存储在SST(Sorted String Table)文件中,写放大的产生就是由于compact的时候需要顺序读取Level-N中的sst文件,写出到Level-N+1的sst文件中。 我们将SST文件分散在多块盘上存储,具体的方法是根据sst的编号做取模散列,取模的底数是盘的个数, 理论上数据量和IO压力会均匀分散在多块盘上。

举个例子,假设某sst文件名是12345.ldb,而节点机器有3块盘用于存储(/disk1, /disk2, /disk3),那么就将改sst文件放置在 (12345 % 3) + 1, 也就是disk1盘上

../_images/leveldb2.png

16.4. 使用方式

leveldb.OpenFile 有两个参数,一个是db文件夹路径path,一个是打开参数Options; 如果要使用多盘存储,调用者需要设置 Options.DataPaths 参数,它是一个[]string 数组,声明了各个盘的文件夹路径,可参考 配置多盘存储

16.5. 扩容问题

假设本来是N块盘,扩容后是(N+M)块盘。对于已有的sst文件,因为取模的底数变了, 可能会出现按照原有的取模散列不命中的情况。 规则是:

  • 对于读Open,先按照 (N+M) 取模去Open,如果不存在,则遍历各盘直到能Open到相应的文件,由于Open并不是频繁操作,代价可接受,且SST的编号是唯一且递增的,所以不存在读取脏数据的问题;

  • 对于写Open,就按照 (N+M) 取模,因为写Open一定是生成新的文件。

随着Compact的不断进行,整个数据文件的分布会越来越趋向于均匀分布在 (N+M) 个盘,扩容完成。

16.6. 实验

写入测试可参考代码 kv/mstorage/test/test_write.go

读取测试可参考代码 kv/mstorage/test/test_read.go