Linux内核中的预取算法

论文摘要

计算机系统中最严重的不平衡来自CPU与I/O之间持续扩大的性能差距。磁盘传输带宽的改善速度跟不上CPU计算能力的增长,数据访问延迟的改善更是严重地滞后。预取作为提升磁盘I/O性能的一种重要技术,可以有效地将来自应用程序的同步的小I/O转化为异步的大I/O,从而减少访问延迟,并促成I/O的并行化。对顺序文件访问的预读是现代操作系统的一项必备功能。Linux内核在虚拟文件系统层实现了一个通用的文件预读算法。随着Linux的广泛应用和在越来越多样化的负载环境中运行,它的预取算法遇到了很多微妙问题的挑战。例如:当内存压力较大的时候,预读页面会被过早地回收,出现预读抖动;对已经缓存在内存中的页面进行预读操作是毫无意义的;被中断的读请求及其重试读可能使顺序性检测算法陷于混乱。本文设计了一个模块化的按需预读框架。通过引入一对预取触发条件,使一些原本复杂的问题以统一和自然的方式得到了处理。在此基础上,对访问模式的检测和预读逻辑被简化,并可以独立地进行扩展。随着多核、多线程处理器成为新的硬件设计方向,软件的并行化也随之成为新的潮流,并带来更多的并发I/O。如何在交织的并发I/O中有效地识别和处理顺序流,已经成为预取算法所面临的一个现实挑战。我们在按需预读框架的基础上,设计并实现了被动和主动两种顺序流的检测和预读算法,引入页面状态作为对不可靠的预读状态变量的必要补充,采用更宽松的顺序性判决条件。它们可以有效地支持:淹没在随机读中的顺序访问;对单个文件实例的并发访问产生的交织访问模式;稀疏的顺序读;局部重排序的NFS顺序读;高密度的随机读区域;对大矩阵的列扫描,等等。被动算法在单线程的情况下不会造成额外的开销,而在多线程情况下的时空复杂度与并发度的大小无关。主动算法通过高效的检测逻辑,确保发现顺序流和随机访问的热点区域,自适应的预读大小可以避免预读抖动,因而往往可以获得更好的性能。实验表明本文算法相对传统预读有突出的优势:在发生预读抖动的情况下,网络输出流量可达到传统算法的3～4倍;在随机干扰之下的顺序读性能可提高29%;交织读的性能是传统算法的4～27倍,同时应用程序可见延迟改善了35倍;在NFS文件服务中,性能提高了1.8倍:在lighttpd文件服务中,磁盘占用率降低了26%,网络输出提高了17%;在随机文件加载实验中,主动检测算法可以获得3倍于传统预读的性能。本文所述的预读算法具有重大的应用价值,其中的按需预读基本框架和顺序流的被动预读算法已先后被Linux 2.6.23和2.6.24内核采用。

论文目录

• 摘要
• Abstract
• 插图
• 表格
• 第一章 绪论
• 1.1 选题的背景与意义
• 1.1.1 磁盘的演进趋势与挑战
• 1.1.2 存储设备的I/O特性
• 1.1.3 I/O性能优化方法
• 1.1.4 预取及其作用
• 1.2 相关工作
• 1.3 问题与挑战
• 1.4 研究内容
• 1.5 论文结构
• 第二章 Linux的缓存和预读机制
• 2.1 内存分区（memory zones）
• 2.2 页面分配（allocating pages）
• 2.3 页面回收（reclaiming pages）
• 2.4 同步页面老化（balanced page aging）
• 2.5 页面缓存（page cache）
• 2.6 页面缓存的预读
• 2.7 read-ahead与read-around
• 2.8 预读API
• 第三章 按需预取算法框架
• 3.1 Linux预读算法的历史
• 3.2 系统分析
• 3.3 数据结构
• 3.4 预读窗口和流水线预读
• 3.5 算法框架
• 3.6 预取触发条件
• 3.7 自适应预取大小和提前量
• 3.8 预读缓存命中
• 3.9 非对齐读和重试读
• 3.10 预读抖动
• 3.11 平凡负载中的开销
• 第四章 顺序流的预取算法
• 4.1 传统检测算法
• 4.2 被动检测算法
• 4.2.1 空间连续访问
• 4.2.2 并发流的识别
• 4.2.3 预读状态的恢复
• 4.3 主动检测算法
• 4.3.1 交织流的识别
• 4.3.2 自适应预读大小
• 4.3.3 基于页面缓存上下文的预读算法
• 4.4 交织的顺序流
• 4.5 矩阵的列向扫描
• 4.6 随机+顺序并发访问
• 4.7 稀疏的顺序读
• 4.8 局部随机的顺序读
• 4.9 高密度的随机读
• 4.10 实验与评价
• 4.10.1 实验环境
• 4.10.2 随机干扰
• 4.10.3 并发流
• 4.10.4 运行时开销
• 第五章 结束语
• 参考文献
• 致谢
• 在读期间的主要工作