Press "Enter" to skip to content

【数据挖掘】日志结构归并树(LSM-Tree)简介

 

 

引言: 随着数据量的与日俱增,目前mysql计算能力逐渐成为了数据页面的性能瓶颈。TIDB作为一个具有分布式特征的关系型数据库,是mysql的一个良好取代品。

 

截止到2020年11月,TIDB在国内数据库流行度排行版上稳定保持第一名:

 

 

数据来源: https://www.modb.pro/dbrank?05

 

一个优秀的产品,在进行应用之前,必不可少的是调研,本文就TIDB的底层存储结构——日志结构归并树(Log-structure Merge Tree)进行了整理分析,其中如有不恰当的理解,请指正。

 

01

 

TIDB的基本结构

 

TIDB作为一个关系型数据库,而底层却采用了一种非关系型数据库TIKV来作为存储引擎(关于TIDB如果将一个非关系型数据库进行封装转换,使其能够支持OLTP业务,并保证ACID特征)。在TIKV中,结构分为了两个部分——Raft层和RocksDB层。其中Raft层作为分布式计算层,完成寻址调度等工作,类似于Ceph中的crush算法;而RocksDB层即为真正的存储引擎。

 

 

而RocksDB,就是一款由Facebook开发的KV存储系统,基于Google的leveldb开发,是一个典型的日志结构归并树结构的存储系统。

 

02

 

日志结构归并树原因

 

所谓日志归并结构树,字面日志,存储方式为日志结构,并会进行归并操作。那幺一个存储系统为什幺需要日志结构,以及日志结构为什幺需要归并呢?

 

1. 为什幺日志结构

 

日志结构简单来说即为永远顺序写数据。 早期,机械硬盘(HDD)还作为主流存储设备时,由于机械硬盘寻址的特性,在做随机写操作过程中,需要不断地移动磁头到对应位置,再进行写磁盘过程,过多的写操作会带来巨大的寻址(移动磁头)的开销,会导致巨大的写性能损耗;

 

而现在,固态硬盘(SSD),同样也有随机写性能问题。SSD的写机制为Copy on Write机制,随机写会导致更多的块失效,需要进行更多的垃圾回收,垃圾回收机制会占据设备的大量性能损耗。

 

再以后,NVM设备也有不同的随机写问题,如intel的AEP(Apache Pass)等,总的来说,由于设备的限制,随机写操作一定会比顺序写慢,不同的设备仅仅是差距量级的区别,因此,日志结构是一个良好的解决随机写问题的方案;

 

2.为什幺需要归并

 

日志结构永远的顺序写操作,就会有一个问题——过去写的某一个数据,在将来的某一个被修改后,过去的老的无效数据(存储领域中称为脏数据)并不会被删除,这就会导致存储利用率变低,有必要在合适的时间将这些脏数据删除,这个删除的过程即为归并。

 

03

 

LSM树结构

 

同样,LSM树的结构也分为了两个部分:日志结构与合并两个部分。

 

1.日志结构

 

日志结构即追加写形式。LSM树的核心理念在于对磁盘的I/O采用批处理的方式,当数据写入到内存时,先在内存驻留,当内存中数据量达到一定阈值时,对这些数据进行排序合并后批量追加写入到磁盘尾部。

 

 

如图所示,数据在内存中进行排序组合,生成一个有序树后,当有序树的容量达到一定的阈值时,将这个有序树追加写入到磁盘的尾部。这一操作将上层应用的所有随机写的操作均转变为写内存,内存中的有序树又以追加写的形式写入磁盘,避免了对磁盘的随机写,由于磁盘的读写不对称的特性,这一操作极大程度地提高了系统的写性能。

 

2.合并

 

由于上图中的操作会导致磁盘中会出现较多的有序树,这对系统的读性能造成很大的影响,每当上层应用发起对某个数据的访问时,需要依次遍历内存中的有序树、磁盘上的所有有序树,并对每一个有序树进行相应的查找才能得到最新的目标结果,磁盘中过多的有序树数量会对这个查找过程带来极大的开销。因此,LSM树中提出了合并的概念。

 

如图所示,当磁盘中的有序树数量达到一定上限时,几个小的有序树将会合并合并生成一个大的有序树,当数据量再增大时,大的有序树也会进行相互合并,生成更大的有序树。通过如此的合并操作,系统中的有序树数量将会保持稳定较少的数量,在每次对所有的有序树进行访问时,更多时间将应用在树内部进行O(logN)效率的查找,减少了读操作的耗时。

 

 

由于不断地向下合并的原因,系统在进行读操作的过程中,需要依次去访问在磁盘中的每一棵子树,如若被访问的数据是一个冷数据,在最下层,这就可能会导致很大的读开销(好在由于28原则,热数据将会更多的被访问,冷数据被访问的次数相对较少)。因此,LSM树结构是一个典型的以牺牲部分读性能换取高速写性能的存储结构。

 

同时,伴随着数据量的增大,系统里底层磁盘中的数据层数增多,合并的次数也愈发频繁,这也会带来较大的系统开销,因此,在系统持续运行的阶段,系统性能会产生周期性的性能波动,这也是LSM树结构的存储系统的缺陷之一。

 

04

 

LSM树应用

 

如今LSM树结构已成为了KV键值存储的一个主流结构,典型的系统就有前文中提到的LevelDB和RocksDB,以及另一个响当当的名字HBase。这些存储系统都或多或少地在LSM树的基础上引入了更多地优化,针对LSM的一些缺点进行了优化,后续阶段我还会将针对RocksDB的架构进行分享。

 

除了企业界,学术界也有很多的关于LSM树的研究,一般主要的研究的点在于如何引入持久化内存来优化读写效率,降低合并操作的次数和性能开销。

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注