我也聊聊数据与磁盘 IO

作者「陈龙」| 基础研发平台 - IoT中心

小编「西顿」| 人力资源中心

Figure  1

说到磁盘，我们大多数人脑海里都能想到磁盘的物理模型（Figure 1）——“一个旋转轴上插着一个或多个磁性圆盘，盘每面上可能都有一个能来回移动的读写头“，还有相关CHS、LBA、DMA……一大堆词；结合物理模型和教科书上的金科玉律——“磁盘随机操作慢，顺序操作快“，但是在OS、VM、各种库的层层包装下，在应用级别的API里我们如何利用这条定律，即”何为随机何为顺序？”

从 Page Cache 说起

说到磁盘IO就不得不提到page cache，很多人隐约知道OS会“缓存”我们的磁盘IO操作，但这种”缓存“是如何发生的？它有什么特性？会对我们的系统/产品有什么影响？如何利用它的特性做设计？

Read时发生了什么

传统的UNIX思想信奉“一切皆文件”，其后继者Plan 9更是将其发挥到了极致，在这种思想下，read/write就成了最重要的syscall，所有通过User/Kernel Mode流通的磁盘、套接字、设备、管道、IPC……数据都需要通过read/write syscall，可见其为UNIX系统乃至今Linux User Mode的核心API。

当应用调用read时除了switch到kernel mode，kernel需要“帮”我们取好数据并放到我们传入的buf地址处。该过程大致如下：

Table 1

从上面的伪代码可以看出，当我们读取的数据在page cache中不存在的时候将会挂起操作进程，等待硬件部件读取完成，而这种硬件操作基本都是百毫秒级别。

Write时发生了什么

Table 2

如上面的伪代码，让人没想到的是一次write竟然会可能产生一次read！

有了以上2个操作的大致过程，有人自然能想到，关于read能不能让OS帮我们“预读取”到page cache？write能不能不走page cache直接写入磁盘？我们能想到的自然已经有前辈们实现出来了，他们就是readahead(2)和open(2)的O_DIRECT参数。

page cache会不会占太多内存？会！当我们用free命令时，Buffer/Cache部分就是page cache和其他各种内核缓存的东西了，随着应用使用的内存越来越多，OS会逐步释放page cache所占用的内存，即OS通过page cache利用空闲内存，为文件IO操作加速，操作同一个文件块的所有进程都能受益！并且是OS全局的不随任何进程的生命周期结束而消亡！这些点非常重要，我们列出来：

• 自动利用空闲内存

• 自动管理淘汰机制

• 自动加速所有文件操作

• 所有进程受益

• OS级别全局缓存（即使应用进程崩溃退出）

• 无GC，几乎不影响应用进程

• ……

看到这里大家一定会觉得page cache真是好东西啊，敬CS领域的前辈们！

何为顺序，何为随机

有了以上read/write的简要过程，可能对该问题还是不甚清晰，我们来看两个例子吧。

1GB RAM的机器冷启动后，1个10GB的磁盘文件，page cache块大小为4KB，当我们每次读取1Byte从文件头 顺序 读到尾的时候，实际只会发生10*1024*1024/4=2621440次磁盘读取操作！而假如我们分别 随机 读4000，5000，1048567……位置的数据然后再读取3200位置的数据时第1个包含0~4096数据的page cache块可能已经清里掉了，将会再次从磁盘中读取，导致读放大。

1GB RAM的机器冷启动后，每次写1Byte， 顺序 写10GB的数据到磁盘文件，page cache块大小4KB，同样也只会发生10*1024*1024/4=2621440次磁盘写入操作，如果不是顺序的写入，当再次写之前写过的块时可能会需要再次从磁盘中读取到page cache。

看完以上的例子，可能我们并没有完全弄清楚问题，到底OS内部怎么个顺序/随机？我们似乎完全看不到。

磁盘IO调度与电梯算法

磁盘的物理特性决定，“顺序”意味着磁道的邻近，即磁头移动尽可能少的距离，比如同磁道的“同心圆”，相邻磁道的“同心环”；参考我们平时乘坐的电梯，为保证最大吞吐和每层用户的平均等待时间电梯都是始终朝一个方向运行到底，然后再向接到请求的相反方向运行；相比之下在我们磁盘IO调度的场景里是磁头从磁盘圆心到边缘，再从边缘到圆心，也就是说OS会对请求访问的磁盘块排序，然后使用磁头最小化移动磁头的电梯算法调度磁盘IO请求，如（Figure 2）所示：

Figure  2

我们一个猛子扎入OS的深水中，以尽可能简短的文字描述相关的read/write、page cache、磁盘IO调度，终于理清楚了“顺序”与“随机”，到这里可能很多人发现磁盘和我们过去Walkman听歌的卡带多么相似啊，需要倒带/前进到前后n首歌曲，如果随机的一会听第2，再听5，再听1，那我们就“人肉卡带播放调度”吧 :blush:

“内存是新的硬盘，硬盘是新的磁带” ——图灵奖得主Jim Gray

查询（读）效率   VS   写吞吐量

只要是现实世界就有太多跷跷板的两端让人权（jiu）衡（jie）的东西，计算机领域的Latency/Throughput、CAP、一致性/读写效率……我们这里磁盘IO相关的简单来讲就是要 “查的快还是要写的快？能不能两者都快？我全都要！”可以，但一定会存在缺陷，总之无法完美 ☹

来回顾下平时我们使用的查询和写入数据的场景：

以上的场景很容易发现，当查询的时候我们需要按“规律”查询，按某字段相等、大于、小于……，而我们写入的（新）数据其源头来自于真实世界，数据是不可能按照我们的“意愿”的，也就是说写入本质上是随机的！ 但前一节讲过， 对磁盘来说随机就意味着慢！效率低！ 这在CS领域是不可接受的。这里出现的矛盾也就是，将随机的数据顺序写入磁盘很快，但查询（读）怎么办？把数据按查询的“规律”排好序查询很快，但写入前要排序，写又慢了；这似乎是两个不可调和的矛盾，需要我们的权（zhong）衡（yong）之道，好在CS领域汇聚了无数的聪明人，在短短几十年内发明了各种算法、数据结构（包括上面讲的page cache、disk scheduling），让数据、磁盘之花越开越艳。

花儿为什么这样红 之 RDBMS索引

想到过去经常在面试中提到一个开放性问题“为什么Oracle/DB2/MySQL…这些niubility的大厂的世界级RDBMS产品的主要索引结构都不约而同的使用B+ Tree为基础，它有什么NB之处让如此爱重复造轮子的CS领域拿得起放不下？能不能用更平常的RBTree/AVLTree代替？”，其实并不是故意为难，而是对一个数据系统来说这一系列的为什么涉及到磁盘IO的方方面面，也即是开头所说的如何利用磁盘的特性做设计的问题。

B+ Tree：

Figure  3

如（Figure 3）所示，B+Tree为有序树，说到有序树自然就能想到RBTree、AVLTree这些二叉平衡树，都是有序，为什么MySQL不用后者，Java TreeMap为什么不用B+Tree？

上图中树高为3，如果用RBTree树高为，比B+Tree高1层，RBTree是二叉树，每个节点只有1个数据，如果数据量大，树高将会差距很大，定位一个数据时从根到数据节点，每经过的一个节点有可能就是一次磁盘IO（page cache中没有所需的数据块），而且这里每次的磁盘IO还是随机的，带来大量的随机磁盘IO！而B+Tree每个节点（块/页）内为多个有序的数据，大小一般和page cache一致（比如x86的4KB）方便装入page cache，降低了树的高度，也就减少了可能的随机磁盘IO操作，而每个块内部的有序数据也利于顺序读取查找；按块划分使部分块有空余空间，方便做insert，不需要向RBTree那样频繁的做rebalance，要知道rebalance在磁盘IO上也是效率杀手。

正是在这种软硬件结合的设计思想造就的B+ Tree，天然适合磁盘这种 亲顺序存储的设备 ；而反观TreeMap，内存自然没有磁盘的这些限制，随机和顺序操作几乎一样速度，所以更省空间，定位效率更高的RBTree被用于这些内存数据结构、容器。

随着大数据的到来，数据越来越多，《HBase权威指南》一书里开头部分介绍的大数据来临时RDBMS纵向扩展、横向扩展、分库分表、反模式……简直一部血泪史了，其根本原因是随着数据增多B+Tree的树高不断增加，虽然B+Tree的O(log)复杂度理论上来说和常数级别差别不大，但每次增高都会因磁盘寻道时间带来的近乎上百毫秒的一次延迟，最终达到不可接受的地步，可见理论和现实实践是有差距的，由此也发展出了新的技术，即后面讲的LevelDB/HBase等。

花儿为什么这样红 之 “企业级“SSD

前段时间看到一篇对比入门企业级SSD和旗舰消费级SSD的文章，说到“企业级”，似乎和互联网人的颠覆与打破传统格格不入，因为有次看到公司从IDC拉回来的旧服务器里的SAMSUN 830……更觉着应该将这篇文章里的精华带给大家。

WAL、Undo、Redo

这几个词本质上来说都是Log！是的，Log在CS工程领域是如此的重要，HBase的WAL，数据库的Undo/Redo Log，分布式事务/协调器的Undo/Redo Log……这些Log和我们平常程序打印输出的Log是不同的，这类Log是不允许丢失的，当我们write后，相应的数据就 必须立刻马上 的出现在磁盘的某个扇区上！而不能向之前所讲的停留在page cache里然后待内核的flush线程异步写到磁盘上，也就是说必须保证“ 落盘 “，因为这类日志本来就是用来故障恢复的，已经是“ 最后一道防线 ”了，必须保证立刻的持久化。

不经过page cache保证“落盘”的方法一个是前面讲过的 open(2)的O_DIRECT参数，一个就是fsync(2)。后者在程序中使用更多；这些都是高开销操作，家用PC上主要是读多写少，而对服务器来说有可能是读写都多，这里的“企业级”SSD就是说保障读的同时也得保障写的fsync效率；就好比消费级旗舰SSD是个“偏科生”，而企业级SSD才是“真学霸”，当然谁都喜欢“真学霸”，但“真学霸”价钱却不低，所以才有了用“偏科生”冒充“企业级”的，只写SSD字眼，大家要擦亮眼睛，搞清楚自己的业务到底是哪种类型。

由此，我们了解了两者的优缺点，也就对我们的设计/选型更又了把握；当大多数只是读取的时候用消费级SSD没问题，比如下载站、web静态文件……（似乎CDN更好:blush:）;而涉及到大量事务/故障恢复的DB、分布式一致性算法、需大量保证落盘的写操作……这类就得要仔细的选择到底是哪种SSD了。

花儿为什么这样红 之 Kafka

还记得当第一次看到kafka官方文档Design部分时拍手叫好的激动，所以只要有机会我就要为之宣传：

Don't fear the filesystem!

这是该文档中第一句标题，通常我们认为文件系统/磁盘一定是慢的，宁愿用网络IO，而kafka的成功告诉我们 “一个设计得当的基于磁盘的系统可以和网络一样快！“ 。我们先把kafka的磁盘网络IO相关的设计精要列出来吧。

• 把文件当队列，利用append文件的高效顺序磁盘IO。

• 利用 Zero-Copy 技术减少User/Kernel Mode的切换次数和数据复制。

• 利用批量写，提高压缩率，提高网络利用率，减少write syscall。

关于第一点，我们整篇文章都是讲利用磁盘顺序操作的高效率，第二点先看一下当我们通过网络发送一个文件的过程：

Figure 4

Steps：

1. DMA data from disk to kernel buffer #1

2. copy data from kernel buffer #1 to user buffer

3. copy data from user buffer to kernel buffer #2

4. DMA buffer from kernel buffer #2 to network

注：kern buf1为page cache，kern buf2为内核socket buf。

发送文件这样简单的操作，数据在内存里要复制3次，总线上要跑6次，如此低效，但实际这可能是我们时时刻刻都在用的机制。所以有了zero-copy，比如linux的sendfile，windows的TransmitFile，其不是标准POSIX API，故会影响使用这些API的应用的移植性，好在Java为我们提供了统一的API java.nio.channels.FileChannel#transferTo，这些zero-copy api将如上彩色步骤部分的2-3步合并为一步，直接将page cache的内容复制到socket buf，减少到User Mode的复制，过程如下：

Figure 5

看到这里很多人要问这不是真正的“ 零 “拷贝啊，为什么不直接将page cache的内容发送到网卡？当底层硬件网卡支持gather operations时，该操作是可以进一步优化为：

Figure 6

最终实现了我们理想中的真正的“零拷贝“。Zero-Copy这么美好，没有缺陷么？有，凡事都有两面性，Zero-Copy数据不经过User Mode，所以使用场景只能是 将磁盘文件数据不做任何改动的发送到网络 ，这样的场景很多，比如web的静态资源、下载站、CDN……这个限制直接对kafka的设计造成一定影响：

• 只支持End-to-End的压缩

• 因上一条，所有Consumer必须支持Producer采用的压缩格式

• broker和Consumer间不能对数据做任何转码/过滤/压缩/解压的操作

kafka可谓利用硬件和现代OS特性而设计的典范，基于这些设计特点，针对kafka集群的机器需要有如下特点：

• 高转速磁盘，无需RAID，支持快速顺序append操作。

• “企业量级”的fsync速度和保障。

• 网卡以及驱动要支持gather operations。

• 内存大小要支持绝大多数消费者offset到生产者写入这段数据的page cache支持。

花儿为什么这样红 之 LevelDB、HBase

将LevelDB与HBase放在一起，是因为这2个东西底层存储查询机制几乎一模一样，HBase几乎就是LevelDB的分布式翻版产品。

我们一直在讲“顺序快，随机慢“，但我们的目标是读写都要顺序都要快！前面我们知道B+Tree在数据量过大的情况下已经跪了，现在讲的这2个东西就是为了解决这种大数据量的场景；可能已经有人想到B+Tree在大数据量时跪了是因为树高太高了，如果拆分成多个树不就解决了么？对，LevelDB/HBase本质上来说就是这种思想，只不过把树的拆分/合并全部自动化了，并且起了个新名字叫LSM Tree：

Figure  7

图Figure 7主要分为2部分，In Memory和On Disk，不管是在内存还是磁盘中的数据结构都是有序的，新增改的数据在内存中采用RBTree/SkipList等构建有序数据结构，在磁盘上保存有序的静态文件，通过一次次的合并（compact）将小的有序数据文件合并为大的有序数据文件，正如我们一直反复说的，一切都是为了磁盘操作的有序。合并的过程其实就是merge sort外排序的过程：

Figure 8

In Memory数据的有序性在需要写到磁盘上时利于批量写的同时可直接按顺序写出，顺序的数据又利于查询（读），简直是两全其美啊，然而任何设计都有其两面性，很难做到“我全都要”

• 曾经有人问我HBase能不能不compact？答案显然是不行的，并且compact越来越成为HBase等大数据产品的痛点，因为compact是高IO操作，如果业务有峰谷还好，可以控制在低谷时段人工触发compact，反之将会对TPS/QPS产生影响。

• 关于HBase还有个常见问题，读取老的冷数据为什么会引起TPS/QPS的剧烈抖动？真正的答案并不是线程、CPU资源抢占，而是我们一开头讲的page cache，HBase读写的应该都是尾部的热数据，如果大量读取冷数据，冷数据加载到page cache后必然将热数据挤出去，而热数据又是主要业务操作的数据，必然造成抖动。

细想一下LSM Tree的设计也是一种空间换时间的策略，利用内存中方便排序的特点保存一批有序的数据，然后有序顺序的写入磁盘文件，然后再通过外排序算法——merge sort，将多个小的有序文件合并为大的有序文件……似乎每句话都离不开“ 序 ”这个字，是的，当我们做应用时用qsort、std::sort、Collections.sort()、order by……很少有去在意具体的某个排序算法，但当我们探入底层结构时才发现排序算法几乎是这些数据产品得以实现的基石。

“ 勿在浮沙筑高台 ”

—— 《深入浅出MFC》侯捷著

共勉。

陈龙自我简介：

“多年的C/C++、Java、游戏、大数据等架构与开发经验，让我更习惯刨去一个产品的层层表面去看待并分析它最核心的设计亮点，并乐在其中；我追求技术，崇尚Hacker精神，向往自由软件世界。对一切计算机编程技术兴趣浓厚，喜爱研究学习一切基础底层技术。”

怎么样

是不是感觉

小哥自带酷酷的调调

来看看“酷龙”小哥的帅照

对一切底层基础技术感性去的同学

欢迎随时找“酷龙”小哥座谈一下

带上一瓶名扬海内外的“夺命大乌苏”

和这个新疆汉子边品边聊吧