预读的概念

预取算法的涵义和应用非常广泛。它存在于CPU、硬盘、内核、应用程序以及网络的各个层次。预取有两种方案：启发性的(heuristic prefetching)和知情的(informed prefetching)。前者自动自发的进行预读决策，对上层应用是透明的，但是对算法的要求较高，存在命中率的问题;后者则简单的提供API接口，而由上层程序给予明确的预读指示。在磁盘这个层次，Linux为我们提供了三个API接口：posix_fadvise(2), readahead(2), madvise(2)。

不过真正使用上述预读API的应用程序并不多见：因为一般情况下，内核中的启发式算法工作的很好。预读(readahead)算法预测即将访问的页面，并提前把它们批量的读入缓存。

它的主要功能和任务可以用三个关键词来概括：

◆批量，也就是把小I/O聚集为大I/O，以改善磁盘的利用率，提升系统的吞吐量。

◆提前，也就是对应用程序隐藏磁盘的I/O延迟，以加快程序运行。

◆ 预测，这是预读算法的核心任务。前两个功能的达成都有赖于准确的预测能力。当前包括Linux、FreeBSD和Solaris等主流操作系统都遵循了一个简单有效的原则：把读模式分为随机读和顺序读两大类，并只对顺序读进行预读。这一原则相对保守，但是可以保证很高的预读命中率，同时有效率/覆盖率也很好。因为顺序读是最简单而普遍的，而随机读在内核来说也确实是难以预测的。

Linux的预读架构

Linux内核的一大特色就是支持最多的文件系统，并拥有一个虚拟文件系统(VFS)层。早在2002年，也就是2.5内核的开发过程中，Andrew Morton在VFS层引入了文件预读的基本框架，以统一支持各个文件系统。如图所示，Linux内核会将它最近访问过的文件页面缓存在内存中一段时间，这个文件缓存被称为pagecache。如图3所示。一般的read()操作发生在应用程序提供的缓冲区与pagecache之间。而预读算法则负责填充这个pagecache。应用程序的读缓存一般都比较小，比如文件拷贝命令cp的读写粒度就是4KB;内核的预读算法则会以它认为更合适的大小进行预读 I/O，比比如16-128KB。

图3以pagecache为中心的读和预读

大约一年之后，Linus Torvalds把mmap缺页I/O的预取算法单独列出，从而形成了read-around/read-ahead两个独立算法(图4)。read- around算法适用于那些以mmap方式访问的程序代码和数据，它们具有很强的局域性(locality of reference)特征。当有缺页事件发生时，它以当前页面为中心，往前往后预取共计128KB页面。而readahead算法主要针对read()系统调用，它们一般都具有很好的顺序特性。但是随机和非典型的读取模式也大量存在，因而readahead算法必须具有很好的智能和适应性。

图4 Linux中的read-around, read-ahead和direct read

又过了一年，通过Steven Pratt、Ram Pai等人的大量工作，readahead算法进一步完善。其中最重要的一点是实现了对随机读的完好支持。随机读在数据库应用中处于非常突出的地位。在此之前，预读算法以离散的读页面位置作为输入，一个多页面的随机读会触发“顺序预读”。这导致了预读I/O数的增加和命中率的下降。改进后的算法通过监控所有完整的read()调用，同时得到读请求的页面偏移量和数量，因而能够更好的区分顺序读和随机读。

预读算法概要

这一节以linux 2.6.22为例，来剖析预读算法的几个要点。

1.顺序性检测

为了保证预读命中率，Linux只对顺序读(sequential read)进行预读。内核通过验证如下两个条件来判定一个read()是否顺序读：

◆这是文件被打开后的第一次读，并且读的是文件首部;

◆当前的读请求与前一(记录的)读请求在文件内的位置是连续的。

如果不满足上述顺序性条件，就判定为随机读。任何一个随机读都将终止当前的顺序序列，从而终止预读行为(而不是缩减预读大小)。注意这里的空间顺序性说的是文件内的偏移量，而不是指物理磁盘扇区的连续性。在这里Linux作了一种简化，它行之有效的基本前提是文件在磁盘上是基本连续存储的，没有严重的碎片化。

2.流水线预读

当程序在处理一批数据时，我们希望内核能在后台把下一批数据事先准备好，以便CPU和硬盘能流水线作业。Linux用两个预读窗口来跟踪当前顺序流的预读状态：current窗口和ahead窗口。其中的ahead窗口便是为流水线准备的：当应用程序工作在current窗口时，内核可能正在 ahead窗口进行异步预读;一旦程序进入当前的ahead窗口，内核就会立即往前推进两个窗口，并在新的ahead窗口中启动预读I/O。

3.预读的大小

当确定了要进行顺序预读(sequential readahead)时，就需要决定合适的预读大小。预读粒度太小的话，达不到应有的性能提升效果;预读太多，又有可能载入太多程序不需要的页面，造成资源浪费。为此，Linux采用了一个快速的窗口扩张过程：

◆首次预读：readahead_size = read_size * 2; // or *4

预读窗口的初始值是读大小的二到四倍。这意味着在您的程序中使用较大的读粒度(比如32KB)可以稍稍提升I/O效率。

◆后续预读：readahead_size *= 2;

后续的预读窗口将逐次倍增，直到达到系统设定的最大预读大小，其缺省值是128KB。这个缺省值已经沿用至少五年了，在当前更快的硬盘和大容量内存面前，显得太过保守。比如西部数据公司近年推出的WD Raptor 猛禽 10000RPM SATA 硬盘，在进行128KB随机读的时候，只能达到16%的磁盘利用率(图5)。所以如果您运行着Linux服务器或者桌面系统，不妨试着用如下命令把最大预读值提升到1MB看看，或许会有惊喜：


共3页: 上一页123下一页

相关内容