编写数据库:第2部分-预写日志

与往常一样,请访问https://github.com/danchia/ddb上的代码

所以,您的数据不是很耐用…

第1部分中,我使用gRPC和Go编写了一个非常简单的服务器,该服务器用于服务GetPut请求内存中的映射。如果服务器退出,它将丢失所有数据,对于数据库,我必须承认这是非常糟糕的。
我实现了预写日志记录,允许在服务器重新启动时恢复内存中状态。尽管这个想法真的很简单,但实现起来却是很困难的!最后,我看了 LevelDB , Cassandra 和 etcd 如何解决此问题。

预写日志

预写日志(WAL)是数据库系统中一种常用的技术,用于保证写操作的原子性持久性。WAL背后的关键思想是,在我们对数据库状态进行任何实际修改之前,我们必须首先记录我们希望是原子性的和持久存储(例如磁盘)的完整操作集。

通过在将更改应用于例如内存中表示之前,先将预期的改变写入WAL来提供持久性。通过首先写入WAL,如果数据库之后崩溃,我们将能够恢复改变并在必要时重新应用。

原子性更加微妙。假设一个改变需要改变ABC发生,但是我们的应用没有办法一下应用所有的改变。我们可以先记日志

intending to apply A
intending to apply B
intending to apply C

然后才开始制作实际的应用程序。如果服务器中途崩溃,我们可以查看日志并查看可能需要重做的操作。

在DDB中,WAL是记录 append-only 的文件:

record:
  length: uint32      // length of data section
  checksum: uint32    // CRC32 checksum of data
  data: byte[length]  // serialized ddb.internal.LogRecord proto 

由于序列化原型不是自我描述的,因此我们需要一个 length 字段来知道data有效载荷的大小。此外,为了防止各种形式的损坏(和错误!),我们提供了数据的 CRC32 校验和。

性能至关重要,但是磁盘速度很慢

通常,WAL结束了所有变更操作的关键路径,因为我们必须在进行变更之前执行预写日志的记录。

您可能会认为我们会在File.Write调用返回后继续前进,但是由于操作系统缓存,通常情况并非如此。

我将在这里以Linux为例。 __buffer cache. 这些缓存有助于提高性能,因为应用程序经常读取它们最近写的内容,而且应用程序并不总是按顺序读取或写入。

Linux通常以写回模式(write-back)运行,在该模式下,缓冲区缓存仅定期(约30秒)刷新到磁盘。 File.Write``fsync()

写了一个快速的基准来判断我的WAL的性能。该测试重复记录100字节或1KB的记录,每n次调用一次fsync()。这些测试在装有本地SSD的Windows 10计算机上运行。

基准测试

DDB WAL Benchmarks
BenchmarkAppend100NoSync             529 ns/op         200.23 MB/s
BenchmarkAppend100NoBatch         879939 ns/op           0.12 MB/s
BenchmarkAppend100Batch10          88587 ns/op           1.20 MB/s
BenchmarkAppend100Batch100          9727 ns/op          10.90 MB/s
BenchmarkAppend1000NoSync           2213 ns/op         455.45 MB/s
BenchmarkAppend1000NoBatch        906057 ns/op           1.11 MB/s
BenchmarkAppend1000Batch10         94318 ns/op          10.69 MB/s
BenchmarkAppend1000Batch100        14384 ns/op          70.08 MB/s

毫不奇怪,fsync()它很慢!100字节的日志条目没有同步需要529ns,同步需要880us。880us会将我们限制在〜1.1k QPS。对于普通的HDD,可能会更糟,因为磁盘寻道可能要花费我们10毫秒左右的时间。对于HDD来说,仅将专用驱动器用于WAL以减少寻道时间并不少见。

为了理智地检查我的结果,我运行了etcd的WAL基准测试。

etcd WAL Benchmarks
BenchmarkWrite100EntryWithoutBatch    868817 ns/op           0.12 MB/s 
BenchmarkWrite100EntryBatch10         79937 ns/op           1.35 MB/s
BenchmarkWrite100EntryBatch100        9512 ns/op          11.35 MB/s
BenchmarkWrite1000EntryWithoutBatch   875304 ns/op           1.15 MB/s 
BenchmarkWrite1000EntryBatch10        84618 ns/op          11.92 MB/s
BenchmarkWrite1000EntryBatch100       12380 ns/op          81.50 MB/sk

etcd的单个100字节写操作为869ns,所以我非常接近!他们的大批产品的性能要好一些,但这并不奇怪,因为他们的实现得到了更优化。我怀疑如果我要测量等待时间直方图,它们的性能可能会缩短尾部等待时间。

同步还是不同步?

鉴于同步是如此昂贵,其他数据库又是怎么做的呢?

  • LevelDB 实际上默认为不同步。他们声称非同步写入通常可以安全地使用,并且用户应该在希望进行同步时进行选择。
  • Cassandra 默认为每10秒进行一次定期同步。写入将被放置到OS文件缓冲区中后被确认。
  • etcd 对于是否同步有一些逻辑,但最好的办法是告诉用户写操作最终会导致同步。

我现在决定改正正确性并始终保持同步。我要寻找的一种潜在优化是尝试批量更新WAL,从而分摊同步成本。

其他的问题/我没有做的事情

大多数WAL实现将其日志记录在段中。段达到一定大小后,WAL将开始一个新段。一旦不再需要日志的较早部分,这将很容易截断它们。
处理多个文件,或者实际上是一般的文件系统,可能会很棘手。特别是,就像使用编译器和内存一样,操作系统通常可以自由地将操作重新排序到磁盘,并且许多文件操作不是原子的。诸如写入临时文件然后将其重命名为最终位置以进行原子文件写入之类的技术很常见。对此,你可以检查出GitHub上另一个项目 issue 来了解 ACID 文件系统写入的难度。

下一次:共识

我希望接下来通过共识算法(例如Raft)进行复制。

如果您喜欢阅读本文,请重新分享并通过任何推文(@DanielChiaJH)发给我!

译自:https://medium.com/@daniel.chia/writing-a-database-part-2-write-ahead-log-2463f5cec67a

本文由博客一文多发平台 OpenWrite 发布!

https://juejin.im/post/5e33ee125188252c30002fe1

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论