磁盘的随机读写和顺序读写

xiao

众多的消息中间件比如kafka，rocketmq，以及众多的基于lsm-tree的数据库都是基于一个原理：磁盘文件的顺序写，
关于这个问题实在有很多让人困扰的地方，对于磁盘文件的顺序写高性能，除了pagecache，众多的解释都是：减少磁盘寻道时间，我举个例子：
代码：
‘’‘
file fa = open("fileA",'a');//append模式打开文件
for(int i = 0；i<10000;i++){
a.write("123");
}
’‘’
对于这种情况，有多少次寻道时间呢？假设操作系统没有内存碎片，有足够的连续盘块
相比于下面这种情况，区别在于哪里呢？
代码：
‘’‘
file fa = open("fileA",'a');//append模式打开文件
string str = "";
for(int i = 0;i<10000;i++){
str+="123";
}
fa.write(str);
’‘’

0x0001

xiao 口嗨角度来看主要是内存和硬盘读写速度的差异，直接说比较难有实感，个人比较建议写成能跑的程序实际对比下执行时间和各种操作的数量

LittleboyHarry

刚查了下资料、但很多都没讲到点子上，除了这篇“辨别顺序写和随机写区别”：

https://stackoverflow.com/questions/2100584/difference-between-sequential-write-and-random-write

Miigon

我的猜想是：

只分析例子的话，代码1中，假设有足够的盘块的话，多数磁盘文件系统会优先在原有文件所在盘块之后继续分配盘块用于写入，所以假设在每两次写入之间，操作系统没有在干其他的事情（没有其他程序尝试读取同一个磁盘），也就不会有寻道发生了。因为从 i = 1 -> 10000 的整个过程中，磁头都在同一磁道或相邻磁道上，所以写入之间不需要寻道或只需要极小的寻道。这里的寻道开销就几乎是 0，更大的开销会在频繁调用 write() 的函数 overhead 开销，以及频繁发送设备 IO 指令（IDE、SATA、NVMe）的 overhead。

另一个极端情况就是，每两次 a.write 之间，都有另一个程序在很远（磁道意义上）的地方尝试读/写一个文件，那每次写入一个"123"都需要进行一次来回寻道，这时寻道的耗时就会变得十分显著。现代硬盘寻道时间大概 9ms，10000 次每次都寻道就是大约 90s 的寻道开销。

现实情况下的数据，会介于这两个极端之间，操作系统和其他程序有可能在两次写入之间请求了其他文件的读写，也可能完全没有操作磁盘。

为了减少这种开销，文件系统可以将目标位置连续或临近的操作分组缓存到一起，再定期写到磁盘上，以减少不必要的来回寻道。

假设 A.txt 和 B.txt 所处的磁道位置很远。

A.txt -> [寻道] -> B.txt -> [寻道] -> A.txt -> [寻道] -> B.txt -> [寻道] -> A.txt

变为

[A.txt -> A.txt -> A.txt] -> [寻道] -> [B.txt -> B.txt]

我猜想的结论是：楼主提供的两个程序，即使假设系统 cache、用户态库提供的 cache、io 操作分组提交都不存在的情况下，只要操作系统和其他应用没有在进行磁盘操作，速度就不会比第二个程序显著的慢，至少不会是由于寻道而慢，而是由于频繁执行写入操作而累积的大量其他软硬件 overhead。原因是程序 1 本质上还是顺序写入。

在实际情境下（系统 cache、用户态库提供的 cache、io 操作分组提交都存在），像这样的顺序写入，并且数据量不大的情况下（例子是30KB），性能应该十分相似。

但是大型数据库/消息中间件的写入不如例子中的代码那么连续。如果写入的位置本身距离就很远，寻道依然是不可避免的。

目前手头没有合适的机械硬盘可以验证这个猜想，并且还没找到什么比较好的方法测量精确的寻道时间，各种变量（cache、group commit、操作系统自身/其他程序对磁盘的访问规律）也暂时没有很好的控制手段。后面有条件了再做一下实验测试一下具体数值。

xiao

Miigon 比较赞同这个考虑，确实是取决于多次write之间是否有其他进程使用了磁盘io，公司新人任务是写一个简单的kv数据库，采用追加写，但是我的设计每次写请求来的之后都是直接追加写落盘，后来看了leveldb的实现，也就给我带来了这样的问题，为什么会需要一个memtable的结构放在内存中，然后在之后的某个时间flush到磁盘，应该也是有考虑到这个问题，但是leveldb也有WAL（写前日志），同样采用追加写。。。，事实上写前日志也是需要相当一部分开销的吧？每次写请求都要访问WAL，就这里还是有些迷惑...

另外应该就是可能就是需要考虑到pagecache了，如果整体写入的话，并且使用mmap系统调用，可以保证一个pagecache内存页全部都被更新了之后才会落盘，如此，多个连续的写入都是写同一个pagecache，绝大多数的写入都是在pagecache完成的，如果分多次，并且这多次写入之间有时间间隔的话，就会出现一种情况：一次写入，写到pagecache，然后后续的写入还没有来，pagecache已经被刷盘，并且已经被淘汰，后续的写入就又需要触发中断，再次加载pagecache。如此以来，整体写入的效率也就会高多了。

hsxfjames

取决于 open 和 write 的实现。我记得 stdio 是有缓冲区的，理论上这两种没有区别。你最好给一下 API 定义。

Miigon

xiao

WAL 作为灾难恢复手段，不断刷盘是必须的。不过 WAL 日志的写入，比起实际数据的修改而言，本身较为连续。并且数据库会确保 WAL 的写入被尽早flush（fsync或fdatasync），但不会要求对实际数据的修改立刻flush。所以连续的多个修改数据库请求，在最佳情况下，可能按照如下顺序执行：

数据库请求（均为写）：
[请求A] -> [请求B] -> [请求C]

数据库调用操作系统：
1. 写请求A的 WAL，并要求flush
2. 写请求A的实际修改
3. 写请求B的 WAL，并要求flush
4. 写请求B的实际修改
5. 写请求C的 WAL，并要求flush
6. 写请求C的实际修改

实际发生的磁盘访问：
[写请求A的WAL] -> [写请求B的WAL] -> [写请求C的WAL] -> ...(操作系统触发flush)... -> [写请求A、B、C的实际修改]

在这种情况下，请求 A、B、C 的 WAL 写入是连续的，之间的寻道时间接近 0。当然现实中的例子不可能都是这么优，两次 WAL 刷写之间依然有可能发生其他磁盘IO。

pagecache 方面，和计算机中其他所有 cache invalidation 问题是一样的。本质是 cache 粒度、cache 过期时间的选择问题。

对于数据库而言，由于有 WAL 的存在，实际数据的修改稍微延迟一些刷盘实际上问题不大。但是操作系统以及文件系统的设计的时候，可能会由于权衡安全性而过早刷盘，所以数据库有时会自己再实现一个 cache，用于将各参数精细调整到适合自身的用途的状态。甚至直接运行在 raw 格式磁盘上（无文件系统），绕过文件系统提供的机制，完全依赖自身的一致性与持久化保障机制。

TXYH

Miigon

大佬，我也对这种到处都提到的 WAL顺序写能提高性能的说法有点疑惑，顺序写本身是比随机写快，但是以上面的写入序列为例子，假设A B C三个写操作都间隔一秒，那理论上三次wal写，感觉也是三个随机写。

那么，wal本身带来的好处除了可以异步提交真正的事务内容外（避免马上flush事务操作设计的整页数据）
基本上就是需要有多个操作并发，类似mysql的组提交，才能在一定程度上起到作用？

Willendless

这学期正好上了存储系统这门课，最近期中考完，我就说一下我的理解，也不一定正确。

我觉得单纯只说寻道是不完整的，感觉你忽视了旋转延迟。磁盘数据访问包含了两部分延迟，寻道延迟和旋转延迟，这两个延迟和在一起被称为positioning time。注意这两种延迟的时间是相同数量级的。寻道延迟取决于相邻两次请求的位置（可以通过加速、匀速、减速三个阶段建模）。但是即使你的请求位于同一个track/cylinder，循转延迟也不可以忽视。最坏情况下，你连续发了两个相连的请求（我觉得这和你伪代码想表达的意思比较一致）。很不幸虽然你的两个请求是连续的，但是磁盘在解决完第一个请求、把结果传给client和开始服务下一个请求这两个动作的之间的延迟会导致你的磁头错过第二个请求的起始扇区，很不幸这时候你需要一次完整的旋转才能真正开始服务第二个请求。有个术语描述这种情况叫skew，当然针对这种情况硬件上/软件上会相应有一些优化，和你用户态程序怎么写其实关系没有那么大，换句话说你得考虑你使用的是什么文件系统以及内核block layer的实现。
至于为什么顺序写有高性能。我觉得首先需要理解什么是高性能。磁盘性能主要通过吞吐量和带宽这两方面来衡量。一般多磁盘系统（例如RAID）里面我们更关注吞吐量。至于顺序写我觉得是通过均摊（寻道+循转）延迟尽可能提高磁盘使用带宽。如果你看过FFS和LFS的相关文章就会知道LFS采用顺序写的目的就是（1）FFS的磁盘使用带宽太低，写性能太差，这个情况在随机读写的workload下尤为严重（磁盘在寻道和循转延迟是没法干有效工作的，相当于浪费了带宽）。例如创建一个文件，就需要访问directory inode，directory block，inode bitmap，inode，block bitmap，block等等。此外可以想象一下你发了n个大小为S的请求如果每个请求都有寻道+旋转的延迟和你发一个n*S大小的请求同时只具备单次寻道+循转延迟哪个有效读写时间占比大。（2）充分利用计算机系统逐渐增长的内存大小，其实只有顺序写是不够的，设想一下你的cache只有1个block，那每次写一个block就要flush到磁盘上，显然这个不可接受的。因此顺序写还需要利用足够大的写cache累积足够的写才能尽可能提供高带宽。此外注意上述讨论有一个前提，那就是你的workload主要是写操作，你的性能瓶颈是写操作，那样顺序写才有优势。具体于LFS而言，由于它保证所有写操作都是顺序写，牺牲了新写入文件block和旧文件block的相邻性，也就牺牲了一部分读性能。
你上述代码还有一个角度就是对文件的并发写。如果我没有理解错的话，对于后一段代码，append模式打开，单次write操作会去锁inode，拿到文件的末尾位置，然后原子写入。但是前一个代码就不能保证多个write操作整体的原子性了。
WAL的话，主要目的是如果你直接数据落盘，落到一半你机器断电了怎么办，显然这种情况下存储里面数据的integrity就没了。那为了解决这个问题就不能直接落盘或者说数据不能就地更新，而是额外写WAL，WAL里面主要记录当前事务执行的相关操作，只有WAL完全落盘之后才能真正开始写数据，这时候即使再次断电也可以通过WAL里的内容恢复。（当然现实里可以根据你需要保证一致性的级别和需要的性能之间的tradeoff设置不同的策略，比如我只需要保证metadata的一致，那我数据就能先落盘）。

Miigon

TXYH

那么，wal本身带来的好处除了可以异步提交真正的事务内容外（避免马上flush事务操作设计的整页数据）
基本上就是需要有多个操作并发，类似mysql的组提交，才能在一定程度上起到作用？

你说的大体上没有错，其实本质上就是，有WAL落盘提供了数据可靠性保障，实际的数据结构你可以慢点刷，（有可能并发情况下）短时间内来了多个修改，能乘机一次一起刷下去（当然WAL还是得乖乖一个一个刷）。

不过你小看了这么干对性能提升的有效性hhh。

需要意识到的，有这两个点：

刷一次 WAL 本身比刷一次实际数据页便宜得多。举个例子：一次更新可能涉及很多很多个页（比如一个大UPDATE，更新了表里一半多的记录的数据。另一个例子是 B+Tree 出现 node splitting，影响到很多个非叶子页），但是记录在WAL里可能就是一条短短的 UPDATE 语句的事情。
一旦有了WAL，你的实际数据脏页想多不频繁刷盘都可以。反正WAL已经写入磁盘中了，实际数据页你想一小时刷一次盘都可以，崩溃了从WAL恢复就行了。

实际上 MySQL InnoDB 以 Checkpoint 的形式刷盘，并使用 Adaptive Flushing 机制，来自动决定要以多快（多慢）的速度刷脏页到磁盘，防止一次把所有脏页刷盘导致剧烈而集中的磁盘访问。

所以，对于写比较频繁的场景来说，起到作用的程度那可大了。

其实本质上WAL顺序写能提高性能这句话就说得模糊且带有歧义，而你是错误理解了这句话。

并不是WAL本身刷盘的时候的顺序写能提高性能，而是「因为有了WAL，所以数据页的修改可以（安全地）不马上刷盘，因此对数据页的多次修改可合并为一次刷盘，从而提高性能」。和 WAL 顺不顺序写入没有关系。

WAL 的写入之间（没有group commit的前提下）也确实是认为总是随机的，但是一次随机 WAL 刷盘就是一次寻道+一次旋转延迟而已，相比我可能因此节省的几十上百个数据页的刷盘的耗时来说，简直就是弟弟（更别说大多数数据页的写入本身也是随机写入）。

题外话：这里插一句： WAL 的 group commit 不是免费的，在得到性能的同时，交换的要么是任务延迟，要么是可靠性。

那“顺序”两字到底从哪里来呢？

实际上如果单论 MySQL + InnoDB 的话，因为是 B+Tree，确实没什么好“顺序”的，先写WAL节省的其实是「某些页在短时间内重复的刷盘」造成的浪费。B+树本身就决定了读写多个节点之间不可能能有多顺序。

但是一些其他数据库设计，只要能够延迟刷盘，确实可以把原本相对随机的写入变成顺序的写入，最出名的例子就是 LSM Tree 数据库。

LSM Tree 数据库的设计是将数据分为多个 level，从 c0 到 ck 依次由热数据到冷数据分级，一般 c0 存在内存中，从 c1 开始落盘。

数据插入的时候，先把数据插入到 c0 的页中（LSM Tree 中的页称为 SSTable，页内数据有序），由于 c0 是在内存中的，随机修改 c0 的性能特别的高（c0 的 SSTable 页一般用红黑树实现）。

然后，当 c0 中的页大/多到一定程度的时候，会发生 Compaction，即多个 c0 中的页可以合并成为一个更大的 c1 中的页，并刷到磁盘中，这个就是数据落盘的时间点。由于任何页内的数据都是有序的，多个 c0 中的页合并成一个 c1 中的页的过程，只需要一次简单的顺序归并即可，显然这个过程是顺序写盘的：

# pageA 和 pageB 在 c0
while pageA.hasLeft() and pageB.hasLeft():
    if pageA.peek() < pageA.peek():
        c1_newpage.append(pageA.next());
    else:
        c1_newpage.append(pageB.next());

c1_newpage.append(pageA.everythingLeft());
c1_newpage.append(pageB.everythingLeft());

题外话：这个归并过程可以一层一层类推直到 c2、c3、c4......原理相同，每一层页数量越来越少但是单个页大小越来越大。分多层的原因是为了适应不同的存储介质，比如可以 c0=内存 c1=本地固态硬盘 c2=本地机械硬盘 c3=远程冷数据 等等。

即：因为处于内存中所以随机写性能优良的 c0，扛下了相对随机的写请求，并通过 Compaction 落盘的方式，将 c0 中的数据顺序地写入 c1（处于硬盘上，随机写性能较差）。这里就是 LSM-Tree “利用不同存储介质的不同特性”的体现。

但是，c0 是存在内存中的，如果只有 Compaction 的时候才落盘，如何保证数据持久呢？当然还是依靠 WAL。数据写入 c0 之前，会先打 WAL。如果出现崩溃，则重启时需要从 WAL 恢复整个 c0。

当然我们前面已经提到了，写一次 WAL 的开销相比 c0 能避免的潜在随机写/写放大而言，几乎微不足道。并且只要没有 Compaction 导致磁头移走，磁盘平时也就只是需要写WAL，多次 WAL 写之间大概率不用寻道（可以理解为大多数时候 WAL 的写入也是顺序的，虽然并不是时间上严格连续）。这也是为什么说 LSM Tree “只做顺序写入”。

而假设不设置 c0，直接把数据写到磁盘 c1 上，因为每次写位置都比较随机，肯定是寻道寻到吐。所以额外写一个 WAL 来设置一层 c0 是远远值得的。

这里就是我猜为啥会说出WAL顺序写能提高性能这句话了：因为假设没有 WAL 的话，就不能把 c0 放到内存了（因为不安全，可能丢数据），那这个用内存挡下随机写的设计就不能成功。WAL是必要条件之一，但不是充分条件，更不是这个设计的核心要义。所以这句话虽然理论上没有说错但是关注的重心不对，有很强的误导性。

WAL 不是这类数据库能实现顺序写盘的根本原因，LSM Tree 才是。

LSM Tree 简介：

LSM Tree 与 B+Tree 对比（读写放大与空间放大）：

https://tikv.org/deep-dive/key-value-engine/b-tree-vs-lsm/