1.介绍近一两年，每次做分布式数据库的内容分享活动，总会提到现有的两个数据库的重要存储结构，B-TREE和LSM-TREE。因为，我觉得作为数据库的存储基础，无论是选择模型还是用好数据库，了解两者的区别和各自的特点是非常重要的。但是几乎每次都只能提及哪个存储用于哪个数据库。不再稍微介绍一下LSM-TREE的写友好性。对于一些朋友来说，在面临两个项目的选择时，这些信息显然是不够的。所以他们会想知道更多关于两者之间差异的细节，以及哪一个更适合他们自己的系统。可惜我只能给出一个大概的提纲，并说明如果要说清楚，整个分享只能讲这个可能性，时间不够。不过，我还是觉得，每次都模糊的过去，有点耍流氓。我得找个机会在这里罗列一些有趣的内容。恰逢国庆宅，想来想去也该把这个坑填上了。当然，本文无意从0开始介绍LSM-TREE，那样太冗长了。本文假定读者对B-TREE和LSM-TREE有一点基础背景知识。2.后台板-分布式关系型数据库其实这两个存储引擎不用分布式数据库来写似乎更简洁。然而，这不是很实用。LSM-TREE数据库的单机版有ROCKSDB和LEVELDB，排名在100左右，它们分为KEY-VALUE类型，通常不会直接出现在我们的视野中，也很少直接在项目中使用。但是，基于LSM-TREE的分布式数据库非常普遍，比如这些：有些人甚至可能因为分布式数据库的需要而去学习和了解LSM-TREE（比如我想先用CASSANDRA）。但是在分布式的背景下，多少会让存储结构差异的比较变得不那么纯粹。因为分布式数据库总会带来一些额外的开销。例如，从数据库级别的SQL分析到分布式执行计划的生成。再比如，在分布式场景下，分布式事务，获取全局时间戳等。不过，粗略对比一下基于B树的分布式数据库的情况，还是可以解释的。但就每个数据库而言，由于每个数据库的具体实现方式不同，实际情况要看具体的数据库做了哪些额外的动作，然后添加到里面。还有一种关系类型可以算是一个重要的背景。由于一些特殊的项目场景和特殊的数据格式，使用某种数据库或存储结构速度很快，但缺乏通用性。事实上，像REDIS、CASSANDRA这样的数据库已经非常流行并被广泛使用。但是，当我们在项目中使用这些数据库时，它们仍然发挥着更多的功能作用，我们很难让它们成为系统的主数据库。尤其是那些从历史包袱中迁移过来的系统。不管怎样，关系模型基本上是我们看到的主要情况。因此，我将在分布式和关系数据库的背景下描述最常见的数据访问形式，这将具有更多的实际参考价值。我们先来展开一下数据库的主要操作都做了哪些。然后设置几个经典的案例场景进去看看。这样围绕分布式关系数据库展开这两种树的内容会更贴近大家使用这两种存储结构的实际需求，至少我是这么觉得的。在开始各种操作的眼花缭乱的描述之前，我们可以做一个草率的假设。例如，我们SQL的响应时间被认为是最关键的性能指标。例如，我们认为内存操作速度更快并且对性能的影响略小。磁盘操作比较慢，比较容易影响交易时间。再比如，异步动作基本不会影响事务性能。虽然这些假设很草率，但我认为这可以让我们对一些数据库操作的性能开销有一个更粗略和直观的认知。3.LSM-TREE的优点编写友好几乎是LSM-TREE的标志性特征，那么我们就从编写过程说起吧。让我们从经典的LSM-TREE图片开始。STEP1WAL日志写入（WriteAheadLog）磁盘操作这一步基本上每个数据库都存在，并且有各种各样的名字。比如Innodb的Redolog，Cassandra的Commitlogs。但是，功能是相同的。数据库宕机后，这个日志可以保证数据的恢复。并且这条日志是以顺序写入的方式不断追加的。所以，从某种意义上说，这部分开销应该是非常接近的。我想MYSQL的BINLOG也可以提到这里。BINLOG严格来说不属于存储引擎，属于MYSQL。与B-TREE的存储结构没有必然关系。从功能上来说，我觉得它更接近一些数据库的归档日志。明明是有开销的，但是我觉得这个账应该算在高可用的头上。STEP2树数据结构维护有观点认为B-TREE至少需要写两次，一次写WAL日志，一次写B-TREE本身，这样写B-TREE就是比LSM-TREE慢。我觉得这个说法有些模棱两可。因为LSM-TREE其实写了两次，一次写WAL，一次写tree。如果非要说，LSM-TREE是可以reduce一次的，除非是某种LSM-TREE数据库在WAL写入后被认为写入成功返回，不需要等待MemTable维护，也就是说就是存在这种数据库，可以提交无法读取数据的情况。我个人认为更准确的说法应该是LSM-TREE中MemTable的追加写入速度要比B-tree的维护快很多。首先，不管是什么树，写树本身就是内存操作，两种结构都不需要等待树结构放入数据库后才提交成功。数据库脏页通常被异步进程缓慢地清除掉。所以简单的树写动作不是重点。但是B-TREE的写树动作并不是单纯的内存操作。因为只要从根节点开始，一路到数据页。在B-TREE路径上，无论是索引页还是数据页，如果有哪一页不在缓存中，数据库就会触发磁盘IO去读取它。所以在一般的写场景下，B-tree的维护是比较慢的。这是一个先读后写的过程。我们可以比较一下。在Cassandra的写步骤中，对数据的描述只是简单的ADDTOMEMTABLE。首先，它体现了顺序添加这条数据的简单性。如果要做某事，只剩下一句话，如果ROWCACHES中存在，则丢弃已有数据。对于LSM-TREE，写入MemTable后，事务应该会返回成功。而这些都是内存操作。那我们随便看看这个阶段B-tree的维护都做了些什么：1）写Undo日志，内存操作，一般只有在Undo空间不够的时候才写入磁盘。2）从索引根节点开始，找到该记录行所在的数据页，内存加磁盘操作。如果它命中缓存，则可能会触发多个磁盘IO。3）可能是B-TREE索引分裂，一大波内存加磁盘操作。我突然觉得不对劲是吧？首先，对MemTable的额外写入显然不能通过约束检查来完成。如果你的应用要写重键回滚，那么写LSM-TREE就不能在这里停止。然后你需要，然后它需要用另一种方式实现，说：先写后读。这个时候的时间其实有点类似于UPDATE操作。这个地方显然需要两点才能看出LSM-TREE的优势。有没有不需要约束检查的超大规模写入场景？当然有，而且还有很多。比如专门写水的数据表。一张记录PV数据的表格在网上特别常见。只要有人点击某个页面，就等于一条记录。没有约束，没有交易。这样的场景，这样的系统，自然会用LSM-TREE快速起飞。但是，如果你的系统，几乎每次写都要判断是重主键还是重唯一索引。那么这种写法优势显然是有限的。STEP3Dirtydataflushing磁盘操作是异步进行的，只要机器资源没有问题，通常不会影响事务响应时间。所以，这里的性能差异不是我要说的重点。我想谈谈一些虚幻的想法。刚刚说的异步脏页放置其实是很多数据库性能优化的空间。许多数据库优化思想都是基于这一点。比如INNODB的DOUBLE-WRITE，MergeInsertBuffer等等。这些优化的核心思想围绕着如何通过异步放置磁盘来减少磁盘交互。看到这个地方的时候，不知道是不是能隐约感觉到，数据库的巨大差异中，总有一些相似之处。那么，接下来，我在讲数据库的UPDATE操作的时候，就要讲讲这个模糊的线索。4.关于存储结构的思考在其他枯燥知识点的比较和介绍之间，让我们先来一波。在学习LSM-TREE之前，B-tree是我小时候心目中唯一占主导地位的存储结构。我一直有一个潜在的概念，就是“数据库的存储结构是为数据查询服务的”。如果非要说一些不那么随意的话，至少主要是为了查询。例如最常见的索引。我们建立一个索引，以插入索引维护为代价，使用额外的磁盘空间。为什么？显然是为了加快查询速度。另一个例子是“集群”。维护数据库中某个维度数据的顺序，为什么？显然仍在进行某种查询。比如列存，为了减少解析SQL计算过程中不相关列的读取，还是为了查询。这些概念都不是针对数据写入服务的。如上所述，在接触LSM-TREE的存储结构时，我有一个特别深刻和直观的印象，这种“数据库存储结构是为数据写入服务”。它与B树有根本的不同。B树的存储结构处处消耗写性能来提高查询性能。而LSM-TREE是在提高写入性能，在某个时候可能会失去读取性能。请允许我在这里大胆地抛出一个问题和一个猜测。问题：为什么在数据库的发展历史上，先有B树，后有LSM树？只是偶然的巧合？猜测：在古代的数据库使用场景中，大部分数据的生成速度都比较慢，这些数据的变化也比较慢，但是都是反复使用和读取的。因此，数据库采用B树存储结构。后来，随着时代的变迁。一些新兴应用场景的数据生成速度大大加快，数据更新速度也加快。甚至还有超级大量的数据产生，但是这些数据产生的很快，但是重复读取和使用的次数大大减少，所以出现了LSM树。为什么要写这个猜测？因为，如果我的猜测是正确的，那么就该问了，你的数据库系统是哪个？您系统中的数据是相对稳定还是快速膨胀？您系统中的数据是否被重复读取？那么你觉得它更适合用在哪个存储引擎上呢？不要觉得豁然开朗，故事当然没有那么简单，选择当然没有那么容易。请注意，我用来描述LSM-TREE的词是“可能”在某些时候失去读取性能。这个地方至少有两个缺陷。第一，既然可以，有没有不亏的情况。然后它变成了，使用LSM-TREE，我的系统可能写得更快，但读取速度不会减慢。第二大缺陷是这个损失没有量化。不同的系统对损失的容忍度大不相同。有的项目，一个事务慢几毫秒，就会被人盯上、追杀，而有的场景，SQL语句跑个几秒、几十秒，问题不大。因此，要做出更准确的选择，我们还需要带入自身系统的实际情况，将差异量化。最好的选择当然是实测。因为它优越的地方，你的制度不一定优越，它不利的地方，你的制度不一定不利，就这么厉害。5.写入过程的推导-更新动作回到前面介绍的写入过程的主线。数据库的增、删、改、查也称为数据库的四大操作。但我认为将UPDATE视为写作过程的某种衍生是合适的。前面我们说过，B树数据的写入和维护过程，其实就是一个先读后写的过程。如果我们把INSERT一条记录看作是更新这条记录所在数据页的内容。假设有足够的空间，没有split等等，那么INSERT和UPDATE动作不就是一个过程吗？另一方面，你会发现我描述LSM-TREE写作卓越的反例实际上使用了约束检查而不是使用UPDATE操作来反例读后写。因为纯LSM-TREE的UPDATE是纯INSERT动作，没有读后写。看看2020年VLDB论文中引用的描述和图片《LSM-based Storage Techniques:A survey》。“通常，索引结构可以选择两种策略中的一种来处理更新，即就地（in-place）更新和非就地（out-of-place）更新。就地更新结构如B+树，直接覆盖旧记录来存储新的更新。例如，在图1a中，要将键k1的值从v1更新为v4，直接修改索引条目（k1，v1）以应用更新。通常读取这些结构优化是因为只存储每条记录的最新版本。但是这种设计牺牲了写入性能，因为更新会导致随机I/O。另外，索引页可以通过更新和删除进行拆分，降低空间利用率。相比之下，out-of-LSM-trees等位置更新结构总是将更新存储到新位置而不是覆盖旧条目。例如在图1b中，更新(k1,v4)存储到新位置而不是直接更新旧条目(k1,v1).这种设计提高了写入性能，因为它可以利用顺序I/O来处理写入。它还通过不覆盖旧数据过程来简化恢复。然而，这种设计的主要问题是牺牲了读取性能，因为记录可能存储在多个位置中的任何一个。此外，这些结构通常需要一个单独的数据重组过程来不断提高存储和查询效率。顺序、异地更新并不是一个新想法；从1970年代开始就成功应用于数据库系统。”可见LSM-TREE的异地（OUT-OF-PLACE）更新结构，根本不是先写后读，是一个INSERT动作，这样看是不是觉得把update动作当成了写入过程的衍生，不管是对于B-TREE还是LSM-TREE，基本没有违和感。不过，在这个一堆重复的词，你可能已经建立了牺牲LSM-TREE的读取性能的概念，你可能认为糟糕的读取性能可能是阻碍你的系统选择LSM-TREE的重要障碍。因为，即使你只是简单地看一下从前面的彩图可以看出，你的一条记录可能需要读取多个文件才能获取，从而质疑它的读取性能。如果你的内心敏感，你或许可以察觉到另一个重要的乌云我的例子。这个乌云是资源冲突。来源ofLSM-TREE的写优势是write-after-read被append-write取代。如果，你的系统有什么大的场景，避免read-after-write。那么这个优势的根基就动摇了。约束检查是最容易想到的场景之一，因为如果你不读，你无法确定你是否会写。那么，我们很容易想到另一个重要的更新场景，悲观锁和事务。为什么？B-TREE长期的经验告诉我们，要SELECTFORUPDATE，必须先SELECT再锁定FORUPDATE。否则当我异地INSERT时，去哪里查看这条记录是否被锁定？我INSERT的时候怎么保证别人不能INSERT呢？那部分内容，我们会在后面的章节中展开。让我们先阅读基本操作。六、B-TREE优点的读取再看这张图：数据读取，通常被认为是数据库最重要的能力。前面说过，有一段时间我一直觉得数据怎么写，怎么放，最终还是为了方便阅读。从画面上给人的感觉总是很直观。前面说了，很多人在LSM-TREE图片的读取动作中看到了5条读取线，就得出了LSM-TREE读取性能不好的结论（很明显，第一次看到这张图的时候，我也是这么想的）。当然，如果多次读取后性能受损，那肯定是损坏了。这是一个很大的损失吗？这很难说。来来回回看了这张图，我不再盯着那五行，而是开始仔细观察从Level1开始的SSTABLE文件，这些文件是由异步Compaction操作生成的。这个动作有很多文档将其转化为数据压缩。我觉得这很容易和数据库中DATACOMPRESS的概念混淆。我更愿意翻译成资料整理。我们来看看它做了什么，多版本数据去重，删除冗余旧数据，KEY排序数据。是的，原来是排序的。如果在SSTABLE文件的header中标出start和endKEY，是不是像一个小B-tree？还记得我之前说过的模糊线索吗？数据库总是把一些异步操作当作一些优化空间。LSM-TREE的压缩绝不是为了防止数据量持续增长而设计的清理机制。它的存在还有更重要的意义。事实上，LSM-TREE在优化写的时候并没有放弃查询。其实这跟我们之前发现的一样，数据库在异步过程中偷偷优化了数据查询的速度。前面的坑我们继续填。如果说相比于B-tree，LSM-TREE的读取总是很慢的。是不是数据比较稳定的系统就不能选择LSM-TREE？如果我们的数据在一次INSERT之后没有移动，会发生什么？让我们仔细检查一下。首先，LSM-TREE的写法优势用不上是必然的，因为你不会写？但是阅读真的很慢吗？让我们来看看。首先我们在内存中找到这条记录，缓存命中，或者MEMTABLE中有最新的数据，没有磁盘IO，速度很快。假设没有命中，那么几层的几个SSTABLE可能只出现一条INSERT记录？好像只有一个。当然这里会有一个疑惑，就是我没有读过这个SSTABLE，怎么知道里面有没有这个记录呢？在我的印象中，通常SSTABLE数据文件一般都会带一个BLOOMfilter来告诉你这个KEY能不能解决这个问题。哎，这个时候再梳理一下感觉，是不是上面记忆中的那两行写得挺快的。下面指的是盘上的三根线。好像没有三根线，只有一根。剩下的感觉有点像B-TREE。也许在这个SSTABLE中，你可以获得它也比B-TREE更快。嗯，这个例子其实有点过分了。我并不是要证明LSM-TREE的读取性能优于B-TREE。这是不可能的。我只是想提醒一下前面的一点，你的制度不一定在优越的地方就优越，你的制度不一定在不利的地方就低劣。太神奇了。例如，我经常被问到类似的问题。我的系统主要是更新。如果SSTABLE行太多，我可以不选择LSM-TREE吗？这不一定是真的。如果平时不检查，读一百行对你的系统性能有什么影响？那我的系统修改和检查了很多，不就是写的为主吗？是的，不适合，因为SSTABLE读行很多，写的优势发挥不出来。所以无论如何，还是要把自己系统的场景带进去，不要靠看图的直觉。LSM-TREE的读取性能可能确实会受到影响。但很明显，在很多情况下，这种伤害是可以通过各种手段来优化和缓解的。让这种伤害在可以接受的范围内，不然为什么LSM-TREE越来越受欢迎？正确的。至于B树的读取，我觉得这里没有太多讨论的必要，因为在前面的描述中写的时候，必须先完成读取过程，B树也相对来说请讲。熟悉的。7.资源冲突——数据锁接下来就要说说这片乌云了。资源冲突问题一直出现在数据库的重要难点附近。而且，冲突问题和分配问题有些纠缠在一起。例如，数据库单机架构向SHAREDISK架构演进过程中，曾一度成为众多数据库厂商无法攻克的难点。例如，我在集群中的某个数据库实例上锁定和修改了数据。这种锁定和修改信息需要立即在内存中，并直接与其他数据库实例通信。最后只有几个比较成熟的解决方案，比如Oracle的RAC，DB2的DATASHARING，可以解决。这个例子清楚地表明，资源冲突必须集中处理或通过可靠的相互通信来处理。这种沟通在分布式水平扩展的情况下会被放大。因此，一些SHARENOTHING数据库产品会选择专注于数据存储节点来处理数据的锁定问题。对于基于LSM-TREE的数据库产品，有的产品选择不支持锁和事务，有的选择通过其他巧妙的手段来解决。而且我们还是可以很明显的看到，在B-TREE结构中，locked或者unlocked可能只是对内存中一条记录标志的修改，locked和unlocked的性能差异看起来并不是很大。但是在LSM-TREE结构的数据库中，似乎需要格外注意加锁过程的开销。因为如果数据库一般都是先读后写，那么写的优势就没有了。如果是另一种冲突处理机制，那么这部分显然是额外的开销。为什么不支持呢？也算是一条出路。我们可以退后一步。资源冲突问题的根源是并行处理。在冲突的资源点上，我们需要切换并行和串行。其实我觉得可以分为两个问题。第一个是解决时序问题，就是我们认为后面的更新是正确的。第二个是解决时序问题。首先是解决并发过程中丢失更新和脏读的问题。对于CASSANDRA这样的数据，使用时间戳来解决时序问题，即把update改成append，在读取和合并数据时，以时间戳最新的数据为准。然后利用时间戳实现多版本读取。也算是解决了原来一半资源冲突的问题。所以对于没有第二部分问题的系统来说，这确实是一个解决方案。问题的另一半更难。比如汇款模式，有的转入，有的转出。如果钱不够，就不能转出。下面看一个我认为比较好的基于LSM-TREE存储结构的Percolator模型的实现。A有10元，B有2元，A转7元给B。首先用三个列族（COLUMNFAILY）存储三样东西，一个是数据本身，一个是锁信息，一个是书面版本。必须有时间戳和版本号才能解决时序问题，那么在PREWRITE阶段，数据库除了写入数据外，还要写入LOCK信息。最后在提交阶段，删除LOCK信息，写一个版本信息。作为read-after-write的替代方案，这种方案下的冲突解决是否可以比B-tree的维护成本更低。我们先来看看理想的LSM-TREE的UPDATE中增加了什么，只增加了一次写MEMTABLE操作。首先我们来看A记录，一共写了3次。最后的COMMIT结束后，我们需要把锁信息去掉。粗略一算，时间似乎翻了四倍。仔细一看，写数据和写版本好像应该是appendable的。但是，这个锁信息不是一个适当的先写后读吗？因为在给一条记录加锁之前，至少要检查它前面是否有锁。但是感觉这个锁的CF应该不大，基本应该是内存操作。让我们仔细看看。正常更新，把A从5版的10改成7版的3。追加写数据，追加写版本，两次内存操作。检查读锁一次，如果没有锁，写锁一次，先算作一次内存操作。如果是在B树上，随机转移的命中概率一般不高。读A后，会有一波磁盘IO，同样的内存加锁释放。感觉B树不一定快。为什么呢，因为也是read-after-write，锁CF信息的read-after-write很可能是内存没有磁盘操作。至于B-tree的read-after-write，基本上磁盘IO是跑不起来的。在这样的情况下，其实LSM基本不落下风。但是，程序不一定是这样写的。比如悲观锁。相信很多时候，你很难把上面这个场景的SQL写成UPDATETABLESETYUAN=YUAN-7WHEREKEY=A。比较常见的写法应该不是，SELECTYUANFROMTABLEWHEREKEY=AFORUPDATE。那么如果YUAN>=7YUAN_NEW=YUAN-7。然后UPDATETABLESETYUAN=YUAN_NEWWHEREKEY=A。中间发生了什么变化？响应时间比较实际上已经从单一的UPDATE比较变成了两个SQL匹配在一起的形态比较。首先，由于SELECTFORUPDATE这个动作，读盘成了逃不掉的一步。在B树上，记录会在SELECTFORUPDATE时被IO到内存中。这时候再看B-tree的UPDATE，纯粹是内存操作，应该不会比写三个CF慢。我们假设加锁和释放锁的记忆动作几乎是一样的，那么这个场景就变成了一个纯粹的读对比。而且，冲突和并发的考虑意味着这是一种数据变化频繁的情况，所以我猜测LSM-TREE读取的SSTABLE行比较多，最终会直接成为影响系统性能的重要因素。如果A和B存在于不同的节点中，我们再谈谈分布式叠加。B中的副锁要跨网络检查节点A的主锁是否已经释放。也感觉里面有一些硬件相关的开销。但应该不是重点，因为类比我们前面说的，RAC实例之间也存在基于网络的锁信息交互开销。8.HighAvailabilityAddition这个内容其实和存储引擎的联系有限，但是BINLOG在之前写的时候有提到。MYSQL的BINLOG作为主备机同步的桥梁，但是很多重要的系统必须开启。最重要的是，在RPO=0的前提下，BINLOG的远程放置是COMMIT成功的必要条件。它的开销对性能有不可避免的影响，写BINLOG几乎是写过程的一部分。不过我觉得还是可以剥离出来的，因为它本质上不是WAL日志。如果一定要benchmark，我觉得和RAFTLOG的写法差不多，都是围绕高可用和多节点数据复制展开的。写入性能开销的增加似乎是相似的。9.最后，我终于把这个坑一点点填上了。感觉自己说了很多，又觉得自己没有说很多。想必以我的认知能力，无法将所有的内容都描述完整。基本上把自己在实践中遇到和担心的一些重点整理了出来，可以给有需要的朋友提供参考。另外，我从文中也能看出来，有些内容基本靠猜测，不一定准确。也希望有大佬看到，帮我指出错漏。作者介绍宇文占全，现任金融行业核心业务系统DBA，主要参与Oracle、DB2、Cassandra、MySQL、GoldenDB、TiDB等数据库的开发。
