关于clickhouse: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 的研发团队致敬。