◄ 上一步目录下一步 ►

0105: Checksum

不完全写入

往 log 里追加一条记录，我们希望要么完全写入，要么没有写入。这个可以叫做原子性（atomicity）。不完全的写入又叫做 torn write。然而文件写入在考虑断电情况下并没有原子性。不仅追加的数据本身没有原子性，甚至文件大小可能都不正确。比如追加一条1000字节的记录，可能的情况有：

文件大小增加了1000，但数据没有完全写入。
文件大小增加了1000，但数据完全没有写入，新增的部分填充了 0 或者垃圾数据。
文件大小增加了500。

但无论如何，只有最后一条记录会受影响，之前成功 fsync 过的记录不受影响。这是为什么数据库要用 log 的又一个原因。

硬盘写入的原子性

CPU 提供了一些读写内存的原子操作，可以操作像一个整数一样大小的数据。当然 CPU 的原子操作讲的是并发，而我们现在考虑的是断电情况下的持久化如何同时做到原子性。在硬件层面上，写入单个 sector 可能是有原子性的。 Sector 是硬盘读写的最小单位，一般是 512B 或 4K。

许多软件都依赖单个 sector 写入的原子性来实现更大范围的原子性。比如 log 写入，可以在 log 开头预留一个 sector，其中记录最后一条 log 的位置。在 log 记录成功 fsync 后，更新这个 sector（包括 fsync 这个 sector）。这样实现了整个 log 的原子性。

但即使没有底层硬件的原子性，上层的软件也能实现原子性，而且不需要两次 fsync。

校验码

假设 log 写入没有原子性，但如果能识别上次不完全的写入，就能直接忽略掉。因为影响到的最后一条记录必然是 fsync 成功之前。这个可以用校验码（checksum）来做到。校验码是哈希函数（hash），两份不同的数据，校验码大概率不一样。把每条记录的校验码储存进去，就能判断不完全写入的记录了。

用标准库里的 crc32.ChecksumIEEE() 计算 log 记录的校验码，然后添加到记录前面：

|  crc32  | key 大小 | val 大小 | 是否删除 | key 数据 | val 数据 |
| 4 bytes |  4 bytes |  4 bytes |  1 byte  |    ...   |    ...   |

修改以下函数：

func (ent *Entry) Encode() []byte
func (ent *Entry) Decode(r io.Reader) error

var ErrBadSum = errors.New("bad checksum")

Entry.Decode() 需要返回相应的错误码：

ErrBadSum：校验码不对（数据未完全写入）。
io.EOF：到达文件末尾（所有记录完好）。
io.ErrUnexpectedEOF：文件提前到达末尾（文件大小不对，未完全写入）。

io.ReadFull()

io.Reader 接口是允许返回的数据少于 buf 长度的。比如你要读取4个字节，返回3个字节，这不必意味着没有后续数据了（eof）。这种情况一般不会在读取硬盘文件时发生，但如果背后的实现是 TCP socket 之类，就必然会发生。所以在使用 io.Reader 时，要循环调用，直到返回的字节数满足。这个循环可以用标准库里的 io.ReadFull() 函数来取代：

func ReadFull(r Reader, buf []byte) (n int, err error)

如果 buf 只填充了部分就 eof 了，io.ReadFull() 会返回 io.ErrUnexpectedEOF。正好满足 Decode() 函数的要求。

处理不完全的 log 记录

判断 Entry.Decode() 返回的错误，忽略最后一条不完全 log 记录。也就是 eof=true。

func (log *Log) Read(ent *Entry) (eof bool, err error)

这一步的测试用例会模拟数据库从上次的不完全写入恢复的情况。

你可能会问：checksum 不通过，怎么知道是不是 log 里最后一条记录呢？其实没有办法知道，因为记录头部的 size 可能是不正确的，不能通过文件大小来判断。

校验码使用

除了不完全写入，校验码还能检测到其他原因导致的数据损坏，比如硬盘或内存硬件故障导致某些 bit 翻转了。这种情况正常的硬件也有小概率发生。然而，这并不是数据库使用校验码的目的，数据库也无法从中恢复。如果 log 中间某条记录损坏，甚至没法判断有没有后续的记录。

密码学上的哈希函数（sha256、md5 等）也能达到校验码的目的。然而并没有使用他们的理由，因为专用的校验码函数占用的空间更小，计算更快。甚至像 TCP/IP 里简单把数据按照 16-bit 整数累加的 checksum 都可以满足要求。但是要注意全部是0字节的情况，输出的校验码不能也是0，这点我们使用的 crc32 没有问题。

总结

这一步，通过 log + checksum + fsync，数据库能在断电后恢复，并且不回丢失之前成功的写入。这是数据库最重要的功能。这也是为什么移动端流行用 SQLite 数据库储存数据，而不是简单的往文件里输出一坨 JSON。不仅仅是因为数据库方便了查询，而是因为简单的文件操作并不能满足 durability 和 atomicity。

这一步仅仅是一个 log，以后如果添加了数据结构，ACID 里的 A 跟 D 就要重新考虑了。

◄ 上一步目录下一步 ►