Go 与 Badger
上回我们说到LSM🌲在HDD上由于出众的写入性能和优化后可以接受的读取性能, 在B🌲混战的数据库领域获得了一席之地, 新型数据库因为LSM🌲相关的技术好学好写, 并发性好等一系列原因纷纷转头到LSM🌲相关的存储后端.
书承上回, 由于HDD是转着写的, 所以随机访问性能比顺序访问慢了100倍…
但, 有一个跨时代的发明出现了~!
他, 就是一直在涨价, 通过减低使用寿命减价的存储介质SSD!
通过上回的文章, 我们了解到LSM🌲快的原因主要有几点:
- 新来的先到内存去
- 顺序写入磁盘
- 定期整理磁盘
第三步决定了冷数据从磁盘读取的速度, 但代价就是必须对数据分level, 比如10M是一个level, 100M是另一个level, 从小的level在不断的整理的时候level变大的过程叫compaction, 升级的公式大部分LSM都是以下公式:
sizeof( L+1 ) = 10 * sizeof( L )
当一个Level撑不下这个Level装的信息的时候需要整理到更大的Level和别人合并的时候这个叫做写放大 (毕竟多写了N遍)
同理,当我在找一个key的时候, 这个key存储在不同的level上的时候我会找很多次, 这个就叫做读放大(毕竟多读了N遍)
所以…优化的空间就是使用SSD比HDD高效的随机读取性能去优化LSM🌲从而降低读放大和写放大.
但是写放大这个步骤会大幅度缩短SSD的寿命, 所以我们要利用高效的随机读取能力的时候减少写放大.
Badger横空出世
创始人: 老子是Go用户, 老子要写DB, 一看RocksDB, 可以是可以, 但是我咋得开CGo, 一开CGo Goroutine就被pthread拖慢成了💩, 诶, 咋还有内存泄漏?! 垃圾C艹(本人也赞同), 老子拿Go重写(本人也赞同, 毕竟RocksDB的开发者连怎么写CMake都不知道)
大概Badger只提供了如下功能
Get,Set,Delete, andIteratefunctions. On top of it, it addsCompareAndSetandCompareAndDeleteatomic operations
相较于RocksDB, Badger从一开始就对事物做出了一定的考量, 使得写数据库更简单.
Badger和HDD上的LSM🌲的区别
把 KV pair分开存储, Key存在一个LSM🌲上, 而Value存在WAL上(原文 value log), 这样LSM🌲的大小就变成了RocksDB的一半, 从而降低了写放大的性能损耗, 第二点就是通过使用SSD的随机读取功能直接从WAL里取出来值.
实现细节
KV 分别存储
由于原教旨LSM🌲的主要的成本就是compaction, 在这期间要进行离线排序, 所以产生了迭代, 但是往往是对Key排序, Value在这个过程中不会更改, 所以Badger分配了Key和Value的存储, 这样降低了一大半无用的Value被排序浪费的内存.
第二, Badger把Value的位置用delta encoding AKA 指针 的方式存储在了Key的右边, 这样就可以告诉SSD这个key对应了什么位置的Value, 同时通过限制单个文件的大小提升了缓存的性能, 假设一个key 16 byte 一个指针16byte就可以在一个64M的文件中存储超过200万行的KV.
写放大缩小
因为降低了Value部分存储在LSM🌲的大小, 所以Value这部分就不会产生写放大, 也不会随着Key到处乱窜,
如果我们假设Value大小1kb, 16byte还是key的大小, 那么写放大仅仅有
(10*16 + 1024)/(16 + 1024) ~= 1.14
也就是仅仅放大了一点点🤏
这体现在性能上就是写入速度是RocksDB的N倍, N取决于Value产生的写放大落入磁盘的时间.
读放大缩小
还是因为Value没在LSM, 所以LSM的大小大幅度缩小, 这还意味着产生的层级变少了, 进而在内存中存储的部分就变多了, 通过bench发现RocksDB在值固定在1kb, 有两千两百万行数据的时候RocksDB用了72gb的数据集存在了LSM树上, 而Badger这边只存Key和偏移,所以仅仅存了1.7G, 全部在内存里…
所以读取速度吊打了RocksDB 3.5倍….
迭代速度… 那就是3.5*N
具体bench mark大概是这样吊打的
由于篇幅有限
下期预告…可能采访一下老迟看看俺们Agate有什么更先进的地方
