LSM🌲之Go与Badger

Go 与 Badger

上回我们说到LSM🌲在HDD上由于出众的写入性能和优化后可以接受的读取性能, 在B🌲混战的数据库领域获得了一席之地, 新型数据库因为LSM🌲相关的技术好学好写, 并发性好等一系列原因纷纷转头到LSM🌲相关的存储后端.

书承上回, 由于HDD是转着写的, 所以随机访问性能比顺序访问慢了100倍…

但, 有一个跨时代的发明出现了~!

他, 就是一直在涨价, 通过减低使用寿命减价的存储介质SSD!

通过上回的文章, 我们了解到LSM🌲快的原因主要有几点:

  1. 新来的先到内存去
  2. 顺序写入磁盘
  3. 定期整理磁盘

第三步决定了冷数据从磁盘读取的速度, 但代价就是必须对数据分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, and Iterate functions. On top of it, it adds CompareAndSet and CompareAndDelete atomic 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有什么更先进的地方

暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇