作者：Bowen Xiao
链接：https://www.zhihu.com/question/19887265/answer/1695928779
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
另外吐槽下题目，感觉“算法”二字把LSM渲染成为了数学一样晦涩难懂的程度。更关键它也不是传统意义上的“算法”，顶多算是方法。
和其他索引结构对比下会好理解一点。BTree是第一个比较成功的索引结构。它把数据组织成Page，非叶子节点存放类似指针的值，指向自己的子节点，叶子节点存Value。它比较成功的一点是充分利用磁盘I/O的带宽。
它最本质的问题是系统设计者被传统思路束缚住了手脚：更新数据必须要同时覆盖旧的数据，也就是同一份数据只能存一份。要更新一个值，首先必须要通过查询找到这个值的Page。这带来了无数的问题，比如更新的时候崩溃了，新值旧值参杂在一起，怎么办？（于是有了Write Ahead Log和Double Write，有一些思路也是用Copy-On-Write来解决）比如范围查询怎么做？如果要一个个随机I/O搬回内存可太慢了（于是有了B+ Tree叶子节点的sibiling指针）。又比如某些更新涉及多个Page，很可能发生分裂，如果分裂的时候崩溃了怎么办？（可能有一个孤儿Page，没有被其他任何页所指向）。又比如B Tree是按页为单位，所以即使只有几个Bytes的更改，也要忍受写整个页（4K Bytes）的开销。又比如Page里的内部碎片怎么利用？又比如B Tree的锁都得做在节点中，这让并发控制比较难实现。
相比B/B+ Tree，LSM Tree的设计理念完全不同：更新数据不需要覆盖旧的数据，有多份也不用担心，反正只取最新的值。这一看就能知道肯定写效率会提升：想象一下，你有个纷繁复杂的账本，每次update都直接写在最新的一页而不是翻回前面找到那条记录改掉，多香呀！于是乎实现上可糙多了。它不用太担心崩溃恢复的问题，因为它的新值和旧值本来就物理隔离。感觉它的实现上主要是Trade-Off，方式大家都大差不差，无非就是什么时候做Compaction，Compaction是leveled还是tiered，按行组织的数据什么时候转为列存（或者不转，一般用于AP数据库）等等。LSM最大的问题是后台Compaction线程会和写入线程共同争抢磁盘的I/O资源。
No comments:
Post a Comment