原文地址: http://blog.notdot.net/2009/12/Damn-Cool-Algorithms-Log-structured-storage

通常来说, 如果你设计一个存储系统 — 例如一个文件系统或者是数据库. 你需要注意的其中一个点是将数据以何种形式存储在磁盘上. 你需要注意存储对象的空间分配和存储对应的索引数据: 你必须担心当你想要扩张一个现有对象(例如, 追加到一个文件)时会发生什么, 你还必须要注意碎片问题, 当旧对象被删除时, 新对象获得对应的位置, 就会发生碎片的问题. 所有这些都增加了很多复杂性，而且解决方案往往是错误的或低效的。

日志结构化存储是一种能够解决所有这些问题的技术。它起源于20世纪80年代的日志结构化文件系统，但最近它被越来越多地用作数据库引擎中的结构化存储方式。在其最初的文件系统应用中，它有一些缺点阻碍了它的广泛采用，但正如我们将看到的，这些对数据库引擎来说不是一个问题，而且日志结构化存储为数据库引擎带来了额外的优势，超过了更容易的存储管理。

日志结构化存储系统的基本组织形式，正如它的名字所暗示的那样，是一个日志—也就是说，一个仅有附加的数据条目序列。每当你有新的数据要写入，而不是在磁盘上为它找一个位置，你只需将它追加到日志的末尾。对数据的索引是通过以同样的方式处理元数据来完成的。元数据的更新也被追加到日志中。这看起来效率很低，但是基于磁盘的索引结构，比如B-Tree，通常是非常广泛的，所以我们每次写的时候需要更新的索引节点的数量通常是非常少的。让我们看一个简单的例子。我们将从一个只包含一个数据项的日志开始，以及一个引用它的索引节点:

到目前为止还不错。现在，假设我们想添加第二个元素。我们把新的元素附加到日志的末尾，然后我们更新索引条目，并把更新后的版本也附加到日志中。

原来的索引条目A仍然在日志文件中，但不再被使用。它已经被新的条目A'所取代，A'指向了Foo的原始、未修改的副本，以及新的条目Bar。当想要读取我们的文件系统时，它会找到索引的根节点，并像在其他使用基于磁盘索引的系统中那样使用它。

找到索引的根需要一个快速的旁证。天真的方法是简单地看一下日志中的最后一个块，因为我们写入操作的最后一件事总是索引的根。然而，这并不理想，因为有可能在你试图读取索引的时候，另一个进程已经在向日志追加内容的中途了。我们可以通过一个单一的块来避免这种情况—比如说，在日志文件的开头—它包含一个指向当前根节点的指针。每当我们更新日志的时候，我们就重写这个指针，以确保它指向新的根节点。为了简洁起见，我们没有在图中显示这一点。

接下来，让我们看看当我们更新一个元素时会发生什么。假设我们修改了Foo。

我们首先将Foo的一个全新的副本写到日志的末尾。然后，我们再次更新了索引节点（在这个例子中只有A'）并把它们也写到了日志的结尾。再一次，Foo的旧副本仍然在日志中；它只是不再被更新的索引所引用。

你可能已经意识到，这个系统并不能无限期地持续下去。在某些时候，我们会耗尽存储空间，因为所有这些旧的数据都在那里占用空间。在文件系统中，这种情况是通过将磁盘作为一个循环缓冲区来处理的，并覆盖旧的日志数据。当这种情况发生时，仍然有效的数据会被再次追加到日志中，就像它是新写的一样，这样就可以释放出旧的副本来进行覆盖。

在一个普通的文件系统中，这就是我前面提到的缺点之一，也就是它的丑陋之处。随着磁盘越来越满，文件系统需要花费越来越多的时间进行垃圾回收，并将数据写回日志的头部。当你达到80%的满度时，你的文件系统实际上就会停滞不前了。

然而，如果你在数据库引擎中使用日志结构化存储，这就不是一个问题了！我们在数据库引擎的基础上实现了这个功能。我们在普通文件系统的基础上实现这个功能，所以我们可以利用它来使我们的生活更轻松。如果我们将数据库分割成多个固定长度的块，那么当我们需要回收一些空间时，我们可以选择一个块，重写任何仍然有效的数据，然后删除这个块。在我们上面的例子中，第一段开始看起来有点稀疏，所以让我们这样做。

我们在这里所做的就是把’Bar’的现有副本写到日志的末尾，然后是更新的索引节点，如上所述。现在我们已经完成了，已经没有引用指向第一个日志段，可以被删除。

这种方法比文件系统的方法有几个优点。首先，我们并不局限于先删除最古老的段：如果一个中间段几乎是空的，我们可以选择垃圾收集，而不是。这对于数据库来说特别有用，因为数据库中有一些数据会停留很长时间，还有一些数据会反复被覆盖。我们不希望浪费太多时间来重写同样的未修改的数据。对于何时进行垃圾收集，我们也有了更多的灵活性：我们通常可以等到一个段大部分都过时了才进行垃圾收集，从而进一步减少了我们必须做的额外工作。

不过，这种方法对数据库的优势并没有结束。为了保持交易的一致性，数据库通常使用 “超前写入日志”，或称WAL。当一个数据库想把一个事务保存到磁盘上时，它首先把所有的变化写到WAL上，把这些变化冲到磁盘上，然后再更新实际的数据库文件。这使得它可以通过 “重放WAL中记录的变化 “从崩溃中恢复。然而，如果我们使用日志结构化存储，提前写入日志就是数据库文件，所以我们只需要写入一次数据。在恢复的情况下，我们只需打开数据库，从最后记录的索引头开始，线性地向前搜索，边搜索边从数据中重构任何缺失的索引更新。

利用我们上面的恢复方案，我们也可以进一步优化我们的写操作。我们可以在内存中缓存更新的索引节点，并定期将其写入磁盘，而不是在每次写入时写入更新的索引节点。我们的恢复机制将负责在崩溃时重建事物，只要我们为它提供一些方法来区分已完成的事务和未完成的事务。

使用这种方法，备份也会更容易。我们可以连续地、增量地备份我们的数据库，方法是在每个新的日志段完成后将其复制到备份介质上。要恢复，我们只需再次运行恢复过程。

这个系统的最后一个主要优势与数据库中的并发性和事务性语义有关。为了提供事务性的一致性，大多数数据库使用复杂的锁系统来控制哪些进程可以在什么时间更新数据。根据所需的一致性水平，这可能涉及到读者拿出锁来确保数据在他们阅读时不被修改，以及写者锁定数据进行写入，如果有足够多的并发读取发生，即使是相对较低的写入率也会导致显著的性能下降。

我们可以用多版本并发控制（Multiversion Concurrency Control）或MVCC来解决这个问题。每当一个节点想要从数据库中读取数据时，它就会查找当前的根索引节点，并在其交易的剩余时间内使用该节点。因为在基于日志的存储系统中，现有的数据永远不会被修改，进程现在有一个它抓取句柄时的数据库的快照。并发事务所做的任何事情都不会影响它对数据库的看法。就这样，我们有了无锁的读取!

当涉及到写回数据时，我们可以利用优化的并发性。在一个典型的读-改-写循环中，我们首先执行我们的读操作，如上所述。然后，为了写下我们的修改，我们为数据库取下写锁，并验证我们在第一阶段读到的数据没有被修改。我们可以通过查看索引，并检查我们关心的数据的地址是否与我们上次查看时相同，来快速完成这一工作。如果是一样的，就说明没有发生过写操作，我们可以自己继续修改它。如果不一样，就说明发生了一个冲突的事务，我们只需回滚并从读阶段重新开始。

我如此大声地赞美它，你可能想知道哪些系统已经使用了这种算法。据我所知，使用这种算法的系统出乎意料的少，但这里有几个值得注意的系统。

• 尽管最初的Berkeley DB使用了一个相当标准的架构，但Java移植的BDB-JE使用了我们刚才描述的所有组件。
• CouchDB使用了刚才描述的系统，只不过它不是把日志分成几段并进行垃圾收集，而是在积累了足够多的陈旧数据时重写整个数据库。
• PostgreSQL使用MVCC，其写头日志的结构允许我们描述的增量备份方法。
• App Engine的数据存储是基于Bigtable的，它对磁盘存储采取了不同的方法，但交易层使用乐观的并发性。