Clickhouse系列-番外-LSM算法

在本系列的第三章中介绍了clickhouse通过block和lsm来减少磁盘读取的数据量。严谨的逻辑应该时clickhouse通过lsm算法来实现数据预排序,从而减少了磁盘读取的数据量,本章番外主要为读者介绍什么是LSM算法,对LSM算法已经有了解的读者可以跳过本章。

LSM算法最早出现在1991年的ACM期刊上,之后其思想在各大大数据存储系统中被广泛使用,例如LevelDB,HBase,Cassandra……LSM算法由于适应的场景不同,存在很多的变体,clickhouse也使用lsm算来实现其预排序的功能,本文将着重介绍clickhouse中的使用,同时也会适当涉及一些其他系统的使用用以让读者体会架构设计的随心所欲。

我们都知道,用户在调用insert向clickhouse插入数据时,数据不一定是按已经按照排序键排序好的数据,大概率是乱序数据。那么这种乱序的请求如何做到写入磁盘时变得有序呢?这个就是LSM算法实现的。

LSM算法的几个核心步骤:

  • 在于数据写入存储系统前首先记录日志,防止系统崩溃
  • 记录完日志后在内存中以供使用,当内存达到极限后写入磁盘,记录合并次数Level为0(L=0)。已经写入磁盘的文件不可变。
  • 每过一段时间将磁盘上L和L+1的文件合并

我们用一个示例来展示下整个过程

T=0时刻,数据库为空。

T=1时刻,clickhouse收到一条500条insert的插入请求,这500条数据时乱序的。此时,clickhouse开始插入操作。首先将500条插入请求一次性写入日志。接着在内存中进行排序,排序完成后将有序的结果写入磁盘,此时L=0;

T=2时刻,clickhouse收到一条800条insert的插入请求,这800条数据时乱序的。此时,clickhouse开始插入操作。首先将800条插入请求一次性写入日志。接着在内存中进行排序,排序完成后将有序的结果写入磁盘,此时L=0;

T=3时刻,clickhouse开始合并,此时此刻,磁盘上存在两个L=0的文件。这两个文件每个文件内部有序,但可能存在重合。(例如第一批500条的范围是300-400,第二批800条数据的范围是350-700)。因此需要合并。clickhouse在后台完成合并后,产生了一个新的L=1的文件。将两个L=0的文件标记为删除。

T=4时刻,clickhouse开始清理,将两个被标记为删除的文件真正地物理删除。

T=5时刻,clickhouse收到一条100条insert的插入请求,这100条数据时乱序的。此时,clickhouse开始插入操作。首先将100条插入请求一次性写入日志。接着在内存中进行排序,排序完成后将有序的结果写入磁盘,此时L=0;

T=6时刻,clickhouse开始合并,此时此刻,磁盘上存在1个L=0的文件和1个L=1的文件。这两个文件每个文件内部有序,但不存在重合。(例如L0文件的范围是100-200,L1文件的范围是300-700)。因此不需要合并。clickhouse在后台将L=0的文件升级成L=1,此时数据库内存在两个L=1的互不重合的文件。

……

以上就是LSM算法在clickhouse上的应用,我们总结一下,clickhouse使用LSM算法将乱序的数据在内存中排序为有序的数据,然后写入磁盘保存,并且定期合并有重合的磁盘文件。

不难发现,上述所有的过程对于磁盘的来说都是顺序写,因此这个也是LSM算法的一个特点——可以将大量的随机写入转换为顺序写入从而减少磁盘IO时间。leveldb就借助了lsm的这个特性。当然,clickhouse并没有使用到这个特性。下面会将简单介绍下leveldb是如何使用LSM的。

clickhouse借助LSM实现了预排序的功能,提高了磁盘的利用率,但也同时带来了一些牺牲。再次强调,没有完美的架构,当架构解决一个问题的同时,一定会带来一个全新的问题。

对于clickhouse也一样,读者们已经知道了,clickhouse会在多次insert请求时创建独立的数据文件。虽然clickhouse会在合适时间进行合并,但如果查询发生在合并前,就有可能数据分布在两个数据文件内。此时clickhouse默认会返回两个列表,这两个列表内部有序,但相互之间却会有重合。这就给用户使用带来了不便,下图展示了这种情况。

可以看出,此时clickhouse未合并时查询结果分成了4个独立的结果,每个结果内部有序,但相互之间存在重合,也就说对于这种情况需要用户自行合并。我们等待其合并后再次查询,结果如下:

clickhouse合并后就能解决该问题。

LevelDB的用法

leveldb是一个允许修改的数据库,因此其对于LSM的使用和clickhouse类似,主要的不同在于写入日志后的操作不同。

clickhouse在记录日志后,会直接在内存中进行排序,从而写入磁盘。此时如果clickhouse又接到一条写入情况,会重新开启一个新的进程。

而leveldb在记录日志后,会将数据首先缓存在内存中,等待后续操作继续操作这块内存,直到这块内存被填满,才会一次性将数据写入磁盘。

这个差异主要时两个数据库面向的场景不同,clickhouse主要面向读多写少的分析场景,强调大批量一次性写入增加吞吐量。而leveldb主要面向写多读少的业务场景,强调低延时。

吞吐量和延时一向是互相对立的两个指标,不同系统都在这两个指标之间存在取舍。后续有机会我也会写一篇关于这两个指标之间的相爱相杀,以及知名开源软件在这两个指标之间的思考。

感想

扯回来,正因为面向的场景不同,clickhouse和leveldb对LSM的使用存在着不同。这也给了我们一个启发,作为架构师,我们要做到运用之妙存乎一心。要能够了解我们正在设计的业务的需求是什么,然后进行符合需求的修改。而不是无脑地认为LSM一定是用在写多读少的场景。

做到这一点会有点难,但幸好我们可以站在前人肩膀上,多体会一下前人设计的精妙绝伦的架构。有了这样的经验和思考,我们在遇到相同问题的时候就能做到更深的思考。

这也是我写这个系列的原因,clickhouse真的是工程师设计的典范之作,整个clickhouse没有发明新的科学理论,但却让我们看到了借助已有的理论也能将性能在某一方面发挥到极致,这种追求极致的工程师精神让我深深着迷,我觉得我需要将这种精妙的设计思想的传递给大家。希望有朝一日,我们中国的工程师也能将极致的产品带给世界。因为有你,因为有我,许许多多平凡而伟大的工程师的共同努力,这一天一定能够到来。向clickhouse的研发团队致敬。