存储(六)—— LSM Tree

上文(存储(五)—— B+树)中提到,B+树是一种原地更新的策略,由于机械磁盘需要转动磁头寻找数据写入的地方,因此在大量随机写的场景下,B+树的效率并不是很高。这里先不提SSD(最后一篇中会讲到硬件的革命对软件技术的影响),考虑到成本问题,当前大规模数据存储的主要介质还是机械磁盘。
这是一个数据爆炸的时代,随着通信技术的进一步发展(5G),物联网大规模应用后,可以预见数据规模将随着数以亿计的传感器的加入更进一步增长。大量数据的随机写入会变成家常便饭,所以:

怎样解决机械磁盘随机写的问题?

现在回忆一下第三篇存储(三)—— 缓存和一致性原理中提到的:为了解决磁盘随机读取效率慢的问题,磁盘会利用局部性原理在每次读取数据时,进行预读,把临近的数据也读到内存中,如果预读的数据在下一次被使用了,那么就相当于只转动了一次磁盘,却读取了“两份”数据。
所以写入能不能也如此呢? 只转动一次磁盘,却写入(新增、更新或者删除)两份或者更多份数据?如果可以的话,那么磁盘的随机写问题就可以解决了。你看,看似伟大的技术背后都是简单而朴素的思想
理论有了,具体怎么做呢?新增数据是一种情况,更新或删除数据是另一种情况。我们分开来看:

新数据的写入

来举个例子,比如磁盘上已经存在一串数据“1,3,5”。这个时候,依次有三个数字6,2,4到来。按照之前的做法,我们为了保证写入后数据是有序的(有序这一点必须保证,这是数据查找的要求,没有商量的余地),当6到来时,我们插到5后面:

1,3,5    6 <--      1,3,5,6
1,3,5,6    2<--     1,2,3,5,6
1,2,3,5,6    4<--	1,2,3,4,5,6   

每插入一次数据,都需要转动磁盘,找到插入的位置。
而最高效的写入办法是什么呢?不用找位置,每次有数据来时,直接往上次写入的位置后面追加就行了。
于是乎,整个过程就变成这样了:

1,3,5	6<--		1,3,5,6
1,3,5,6		2<--		1,3,5,6,2
1,3,5,6,2		4<--		1,3,5,6,2,4

最终的数据并不是有序的,这显然不是我们想要的结果。
那有没有什么办法使得能一致追加的同时还能保证数据是有序的呢?
有,排完序再追加就好了,排序可以在内存中完成,于是乎,整个过程就变成下面这个样子了:

1,3,5    6<---     	磁盘:1,3,5         内存:6   
1,3,5     2<---		磁盘:1,3,5	   内存:2,6  
1,3,5     4<--		磁盘:1,3,5	   内存:2,4,6
1,3,5	2,4,6<---		1,3,5,2,4,6

嗯。。 看起来至少是局部有序了,局部有序肯定是不行的,还得再处理一下:
最后一步,拆成两步,先单独写到一个地方,此时我们就得到了两个有序的数据块,最后把这两个有序的数据块合并就行了,于是乎,最终的数据写入过程就变成这个样子了。

1,3,5    6<--    	磁盘:1,3,5         内存:6   
1,3,5     2<--		磁盘:1,3,5	   内存:2,6  
1,3,5     4<--		磁盘:1,3,5	   内存:2,4,6
1,3,5    2,4,6<--	磁盘:1,3,5     磁盘:2,4,6
合并 ---> 磁盘:1,2,3,4,5,6

是不是看起来也挺简单的,其实这几乎就是LSM的思想的核心了,从名字上也可以看出一二,LSM Tree的全称是:Log Structured Merge Tree。

数据的更新和删除

当我们要更新或者删除一条数据时,最直接的想法就是找到这条数据,然后更新或者删除之。这也正是B+树的做法。
LSM树在数据更新时,仍然沿用顺序写入的思想,对于删除和更新的数据,加上时间戳之类的标记后写入磁盘,后台线程定期进行数据版本的合并。
举个例子,磁盘上现有数据1,2,3 此时新增4,删除2,更新3,那么流程示意图如下所示(括号里的数字表示数据的时间戳):

1(1),2(1),3(1)     add 4          磁盘块A:1(1),2(2),3(1)      内存:4(2)
1(1),2(1),3(1)     delete 2      	磁盘块A:1(1),2(1),3(1)	  内存:4(2),2(2d)
1(1),2(1),3(1)     update 3      	磁盘块A:1(1),2(1),3(1)	  内存:4(2),2(2d),3(2)
内存顺序写入磁盘   ----> 	   磁盘块A:1(1),2(1),3(1)	    磁盘快B:4(2),2(2d),3(2)
合并  ---->  磁盘1(1)3(2)4(2)

LSM Tree 核心思想

我理解LSM的思想主要有两点:

1. 随机写变顺序写。

写入数据时,通过在内存中维护一颗排序树,将数据排序,当数据达到一定大小时,将数据顺序写入磁盘。

2. 数据定期合并。

定期合并,主要做两件事:1,将更新和删除的数据版本进行合并,合并后会腾出来旧版本数据占用的空间。2, 将有序的小文件合并为有序的大文件,提高查询的效率。
image.png

LSM的代价

在硬件和自然定律不变的情况下,软件中的设计都是根据应用场景进行取舍,没有最好,只有最适合,LSM通过将随机写转换成顺序写的方式,很大的提高数据写入效率,但同时,也在其他方面做出了一定的牺牲。

写放大

从示意图中可以看出,LSM必须定时合并小文件到大文件中,这个合并的动作,几乎全是磁盘I/O操作,在合并的过程中,有可能会和正常数据的写入抢夺I/O资源。
而在合并之前,磁盘上的数据可能存在好几个版本,旧版本的数据白白占用了存储空间。
这种额外的数据文件合并操作就称之为写放大,也就是说,LSM把写入速度提高了,但是却把工作量放大了。
定期合并示意图:
image.png

读放大

现在来想想,数据读取的流程。
不像B+树种那样,我们可以顺着索引找到数据的位置。
在LSM Tree中,我们并不知道我们想要的数据到底在哪里,在内存中?在level1?在level2?
没办法,我们只有按照从新到旧的顺序来读取数据:

  1. 从内存中查找,如果没有,那么:
  2. 按照从新到旧的顺序遍历level中的文件,如果还是没找到,那么:
  3. 按照同样的方式遍历下一层level中的文件进行查找。
    为了查找数据而进行这些额外的操作就叫做读放大。
    当然,大多数LSM的实现中会对数据读取进行优化,比如利用布隆过滤器飞快的判断数据是否存在于某个数据文件中。

LSM Tree的应用

基于LSM Tree实现的数据存储软件有很多,比较著名的有:

  1. Google的BigTable
  2. Apache的HBase
  3. LinkedIn的Kafka
  4. Google的Level DB
  5. Facebook的RocksDB

从LSM的特点可以看出,这类数据库适合存储数据频繁大量写入,读取相对不是很高的场景,
比如:

  1. 地图坐标、行驶轨迹等。
  2. 基于时间序列的存储,比如监控、传感器采集,天气、温度等数据。
  3. 日志数据。
  4. 交易流水,交易记录等数据。
  5. 消息数据。

从单机到分布式

目前为止,本系列所述几乎没有涉及到分布式相关的内容,在了解了存储的基本原理后,下一步我们将把视野扩展到分布式的领域,欲知后事如何,且看
《存储——(七)Replication》


我有一壶酒,
足以慰风尘。
尽倾江海里,
赠饮天下人。