日志结构化合并树(2015)
谷歌发布“大桌子”论文已经将近十年了。那张纸的许多酷的方面之一是它使用的文件组织。在这篇1996年的论文之后，这种方法通常被称为日志结构合并树(Log Structural Merge Tree)，尽管其中描述的算法与大多数现实世界的实现有很大的不同。
LSM现在作为主要的文件组织策略用于许多电子产品中。HBase、Cassandra、LevelDB、SQLite，甚至MongoDB 3.0在收购Wiring Tiger之后，都附带了一个可选的LSM引擎。
LSM树的有趣之处在于，它们与主导该领域数十年的二叉树风格和档案组织截然不同。LSM似乎几乎与直觉相反，当你第一次看到它时，只有当你仔细考虑文件在现代内存密集型系统中的工作方式时，它才有意义。
简而言之，LSM树旨在提供比传统B+树或ISAM方法更好的写入吞吐量。它们通过消除执行分散的、非就地更新操作的需要来做到这一点。
那么为什么这是个好主意呢？其核心是老问题，即磁盘对于随机操作来说速度很慢，但在顺序访问时速度很快。这两种类型的访问之间存在鸿沟，而不管盘是磁性的还是固态的，甚至是主存储器(尽管程度较小)。
这份ACM报告中的数字在这里/这里可以很好地说明这一点。它们表明，与直觉相反，顺序磁盘访问比随机访问主存更快。更相关的是，它们还显示对磁盘的顺序访问(无论是磁盘还是固态硬盘)至少比随机IO快三个数量级。这意味着要避免随机操作。顺序访问非常值得设计。
因此，考虑到这一点，让我们考虑一个小小的思维实验：如果我们对写入吞吐量感兴趣，那么使用什么是最好的方法？一个很好的起点是简单地将数据追加到文件中。此方法通常称为日志记录、日志记录或堆文件，它是完全顺序的，因此可提供相当于理论磁盘速度(通常为每个驱动器200-300MB/s)的非常快的写入性能。
得益于简单性和性能日志/日志，基于日志/日志的方法在许多大数据工具中理所当然地变得流行起来。然而，它们也有明显的缺点。在找到所需的密钥之前，从日志中读取任意数据将比向其写入要耗费更多的时间，这涉及到反向时间顺序扫描。
这意味着日志只真正适用于简单的工作负载，在这些工作负载中，数据要么像大多数数据库的预写日志那样完整访问，要么像Kafka这样的简单消息传递产品那样按已知偏移量访问。
因此，我们需要的不仅仅是一个日志来高效地执行更复杂的读取工作负载，如基于键的访问或范围搜索。广义地说，有四种有效的方法可以在这里帮助我们：二进制搜索、散列、B+或外部。
搜索排序文件：将数据保存到文件中，按关键字排序。如果数据定义了宽度，则使用二进制搜索。如果没有，请使用页面索引+扫描。
散列：使用散列函数将数据拆分成存储桶，稍后可以使用该存储桶来指导数据读取。
外部文件：将数据保留为日志/堆，并在其中创建单独的散列或树索引。
所有这些方法都显著提高了读取性能(最多为n->；O(log(N)。唉，这些结构增加了顺序，而该顺序会阻碍写入性能，因此我们的高速日志文件会在此过程中丢失。我想你不能既吃蛋糕又吃蛋糕。
一个值得做的洞察是，上述所有四个选项都对数据施加了某种形式的总体结构。
数据被刻意而明确地放置在文件系统周围，以便索引稍后可以快速找到它。正是这种结构使导航变得快速。唉，当然，在写入数据时，这种结构必须得到尊重。这就是我们开始通过添加随机磁盘访问来降低写入性能的地方。
有几个具体的问题。每次写入需要两个IO，一个用于读取页面，另一个用于将其写回。我们的日志/日志文件不是这种情况，它可以在一个文件中完成。
不过，更糟糕的是，我们现在需要更新散列或B+索引的结构。这意味着更新文件系统的特定部分。这就是所谓的就地更新，需要缓慢、随机的IO。这一点很重要：像这样的就地方法会分散文件系统执行就地更新*。这是有限的。
一种常见的解决方案是使用方法(4)将索引放入日志-但将索引保留在内存中。因此，例如，可以使用哈希表将键映射到日志文件(日志)中最新值的位置(偏移)。这种方法实际上工作得很好，因为它将随机IO划分为相对较小的东西：保存在内存中的键到偏移量的映射。这样一来，查找一个值就只有一个IO了。
另一方面，也存在可伸缩性限制，特别是当您有很多小值时。如果您的值只是简单的数字，那么索引将大于数据文件本身。尽管如此，从Riak到Oracle Coherence的许多产品中都使用了模式，这是一种明智的折衷方案。
因此，这将我们带到Log Structure Merge Trees(日志结构化合并树)。LSM对上述四个问题采取了不同的方法。它们可以完全以磁盘为中心，只需要很少的内存存储来提高效率，但也可以保持我们会与简单日志文件捆绑在一起的大部分写入性能。与B+树相比，缺点之一是读取性能略差。
本质上，他们尽其所能使磁盘访问按顺序进行。这里不能用散弹枪！
*存在许多不需要就地更新的树结构。最受欢迎的是仅附加的Btree，也称为写入时复制树。它们的工作方式是在树结构中按顺序覆盖，每次写入发生时都会在文件结束时执行。旧树结构的相关部分(包括顶级节点)被孤立。通过这种方法，由于树随着时间的推移顺序地重新定义自身，因此避免了就地更新。然而，这种方法是以代价为代价的：每次写入时重写结构都非常冗长。它还会产生大量的写入放大，这对其本身来说是一个非常不利的因素。
从概念上讲，基本LSM树相当简单。不是拥有一个大的索引结构(这将分散文件系统或显著增加写入放大)，而是将批量写入顺序保存到一组较小的索引文件中。因此，每个文件都包含一批覆盖短时间的更改。每个文件在写入之前都会进行排序，因此以后搜索会更快。文件是不变的；它们永远不会更新。新更新将放入新文件中。读取检查所有文件。定期将所有文件合并在一起，以保持较低的文件数。
让我们更详细地看一下这一点。当更新到达时，它们被添加到内存缓冲区中，该缓冲区通常以树(红-黑等)的形式保存，以保持键的排序。在大多数实现中，此“内存表”作为预写日志复制到磁盘上，仅用于恢复目的。当Memtable填满排序的数据时，会将刷新到磁盘上的新文件。随着越来越多的写入进入，此过程会重复。重要的是，系统仅执行顺序IO，因为文件未被编辑。新条目或编辑只是创建连续的文件(参见上面的图)。
因此，随着越来越多的数据进入系统，就会创建越来越多的不可更改的有序文件。每一个都代表一个小的，按时间顺序的变化子集，保持排序。
由于不更新旧文件，因此创建重复条目以取代先前记录(或删除标记)。这最初会创建一些冗余。
系统会定期执行压缩。压缩会选择多个文件并将它们合并在一起，删除任何重复的更新或删除(稍后将详细介绍此操作的工作原理)。这对于消除上述冗余很重要，但更重要的是，要保持对读取性能的控制，读取性能会随着文件数量的增加而降低。值得庆幸的是，因为文件是经过排序的，所以合并文件的过程非常高效。
当请求读取操作时，系统首先检查内存中的缓冲区(内存表)。如果找不到密钥，将按逆时间顺序逐个检查各个文件，直到找到密钥。每个文件都保持排序，以便可以导航。但是，随着文件数量的增加，读取将变得越来越慢，因为每个文件都需要检查。这是个问题。
因此，LSM树中的读取速度比它们的就地同胞慢。幸运的是，有几个技巧可以使模式具有表现力。最常见的方法是在内存中保留一个完整的页面索引。这提供了一个查找，让您“接近”您的目标键。在对数据进行排序时，您可以从那里进行扫描。LevelDB、RocksDB和Bigtable通过在每个文件的末尾保存一个块索引来做到这一点。这通常比直接的二进制搜索工作得更好，因为它允许使用可变长度的字段，并且更适合于压缩数据。
即使使用每个文件的索引，读取操作仍将随着文件数量的增加而变慢。通过定期将文件合并在一起来控制这一点。这样的压缩使文件数量和读取性能保持在可接受的范围内。
即使使用压缩，读取仍然需要访问许多文件。大多数实现都通过使用高级Bloom过滤器来使这一点无效。布隆过滤器是判断文件是否包含密钥的一种内存效率高的方法。
因此，从“写入”的角度来看，所有写入都是批处理的，并且仅按顺序区块写入。压缩轮次还会带来额外的周期性IO损失。然而，读取可能会在查找单行时触及大量文件(即读取时的散射枪)。这就是算法的工作方式。我们用写入的随机IO换取读取的随机IO。如果我们可以使用像Bloom Filter这样的软件技巧或像大型文件缓存这样的硬件技巧来优化读取性能，那么这种权衡是非常明智的。
要保持LSM读取相对较快，重要的是减少文件数量，因此让我们更深入地研究压缩。该过程有点像分代垃圾收集：
当创建了一定数量的文件时，比方说创建了5个文件，每个文件有10行，它们被合并成一个单独的文件，有50行(或者可能稍微少一点)。
此过程继续进行，创建了10个以上的行文件。每次第五个文件填满时，这些文件都会合并到50个行文件中。
最终有5个50行文件。此时，5个50行文件合并为一个250行文件。该过程将继续创建越来越大的文件。参见图。
这种通用方法的前述问题是创建了大量文件：必须单独搜索所有文件才能读取结果(至少在最坏的情况下是这样)。
较新的实现(如在LevelDB、RocksDB和Cassandra中的实现)通过实现基于级别(而不是基于大小)的压缩方法来解决此问题。这减少了在读取最坏情况时必须参考的文件数量，并降低了单个压缩的相对影响。
1.每个级别可以包含多个文件，并保证其中整体不会有重叠的键。也就是说，密钥跨可用文件进行分区。因此，要找到某一级别的密钥，只需查询一个文件。
第一级是上述属性不成立的特殊情况。密钥可以跨越多个文件。
2.文件合并到上级，一次一个文件。当一个级别填满时，会从中提取一个文件并合并到上面的级别中，从而为添加更多数据创造空间。这与基本方法略有不同，在基本方法中，将几个大小相似的文件合并为一个更大的文件。
这些变化意味着，基于水平的压缩方法可以随着时间的推移分散压实的影响，并且需要更少的总空间。它还具有更好的读取性能。但是，对于大多数工作负载，总IO会更高，这意味着一些较简单的面向写入的工作负载将看不到好处。
因此，LSM树位于日志/日志文件和传统的单一固定索引(如B+树或Hash索引)之间。它们为管理一组较小的单个索引文件提供了一种机制。
通过管理一组索引，而不是单个索引，LSM方法可以利用与B+或哈希索引中的就地更新相关的最昂贵的随机IO来实现快速的顺序IO。
正在付出的代价是，读取必须解决大量的索引文件，而不仅仅是一个。此外，压缩还需要额外的IO成本。
如果这仍然有点模糊不清，这里和这里还有其他一些很好的视频描述。
我们已经看到，LSM具有更好的写入性能，尽管这是有代价的。不过，LSM还有其他一些好处。LSM树创建的SSTables(已排序文件)是不可变的。这使得它们的锁定语义变得简单得多。通常，争用的唯一资源是Memtable。这与需要精心设计的锁定机制来管理不同级别的更改的单一树形成了鲜明对比。
因此，归根结底，问题可能是预期工作负载的写入导向程度有多高。如果您关心写入性能，LSM提供的节省很可能是件大事。大型互联网公司似乎在这个问题上相当坚定。例如，雅虎报告称，在事件日志和移动数据摄取增加的推动下，工作负载正在稳步从读繁重向读写转变，这在很大程度上是受事件日志和移动数据摄取增加的推动。不过，许多传统数据库产品似乎仍然偏爱读优化的文件结构。
与日志结构文件系统一样[参见脚注]，关键论点源于内存可用性的增加。有了更多的可用内存，通过操作系统提供的大型文件缓存，读取自然会得到优化。因此，写性能(内存不会随更多的增加而提高)成为主要的关注点。因此，换句话说，硬件进步对读取性能的影响大于对写入性能的影响。因此，选择写优化的文件结构是有意义的。
当然，像LevelDB和Cassandra这样的LSM实现通常比基于单树的方法(分别在这里和这里)提供更好的写入性能。
在LSM方法上已经有了相当多的进一步工作。雅虎开发了一个名为PNUTS的系统，它将LSM和B树结合在一起，并展示了更好的性能。“不过，我还没有看到这种算法的公开实现。IBM和谷歌最近在类似的脉络上做了更多的工作，尽管是通过不同的道路。还有一些相关的方法，它们具有类似的特性，但保留了总体结构。其中包括分形树和分层树。
当然，这只是一种选择。数据库利用了大量微妙不同的选项。越来越多的数据库为不同的工作负载提供了可插拔的数据引擎。对于HDFS，它是一种流行的替代方案，并且几乎是朝着相反的方向推进的(通过专栏格式实现聚合性能)。MySQL有一个存储抽象，可以与许多不同的引擎一起插入，比如TToku的基于分形树的索引。这也适用于MongoDB。Mongo 3.0包括Wiring Tiger引擎，该引擎既提供B+&；LSM方法，也提供传统引擎。许多关系数据库具有可配置的索引结构，这些结构使用不同的文件组织。
考虑到正在使用的硬件，这也是值得的。昂贵的固态磁盘(如FusionIO)具有更好的随机写入性能。这适合就地更新方法。更便宜的固态硬盘和机械驱动器更适合LSM。LSM可避免让固态硬盘被遗忘的小型随机访问模式**。
不过，LSM也不是没有批评者。与GC一样，它最大的问题是收集阶段及其对宝贵IO的影响。在这个黑客新闻帖子上有一个关于其中一些的有趣的讨论。
因此，如果您正在研究数据产品，无论是BDB和LevelDb，还是Cassandra和MongoDB，您可能会将它们的相对性能的一定比例与它们使用的文件结构联系在一起。测量结果似乎支持这一理念。当然，值得注意的是您使用的系统选择的性能权衡。
**在SSD中，每次写入都会导致整个512K数据块的清除重写周期。因此，较小的写入可能会在驱动器上引起不成比例的翻转。由于对数据块重写的固定限制，这可能会严重影响它们的使用寿命。
这里是原始的日志结构化合并树论文。在我看来，这确实有点难跟上。
除了名称和对写入吞吐量的关注之外，据我所知，LSM和日志结构化文件系统之间没有太多关系。
今天使用的常规文件系统倾向于“日志记录”，例如ext3、ext4、hfs等都是基于树的方法。信息节点的固定高度树表示目录结构，日志用于针对故障情况提供保护。在这些实现中，日志是逻辑的，这意味着只会记录内部元数据。这是出于性能原因。
日志结构文件系统在闪存介质上广泛使用，因为它们具有较小的写入放大。随着文件缓存开始在更一般的情况下主宰读取工作负载，并且写入性能变得更加关键，它们也受到了更多的关注。
在日志结构化文件系统中，数据只写入一次，直接写入日志，该日志被表示为按时间顺序前进的缓冲区。定期对缓冲区进行垃圾收集，以删除冗余写入。与LSM类似，日志结构文件系统的写入速度更快，但读取速度比基于树的双重写入文件系统慢。同样，如果有大量RAM可供文件缓存使用，或者介质不能很好地处理适当的更新，就像闪存的情况一样，这也是可以接受的。