Linux内核设计与实现之页高速缓存和页回写

pulbieup

  s# b( s" E+ {+ C5 F1 F/ _  P主要内容：
6 L& p" E* A+ p9 ^- C) x

• 缓存简介
• 页高速缓存
• 页回写
  

+ T& l, l# F/ w6 w2 u& Y# a! W7 T# Y1. 缓存简介
" @0 U' P$ h3 r9 p/ A5 W0 e/ t( J在编程中，缓存是很常见也很有效的一种提高程序性能的机制。

linux内核也不例外，为了提高I/O性能，也引入了缓存机制，即将一部分磁盘上的数据缓存到内存中。
# Q/ t+ l& u" \; b* i( f9 {
) M' T* z% E: I  S0 w

$ Q0 J1 H% W. H# t* S! E- @1 s1 A1.1 原理

之所以通过缓存能提高I/O性能是基于以下2个重要的原理：

$ j$ o  k% _4 m

• CPU访问内存的速度远远大于访问磁盘的速度（访问速度差距不是一般的大，差好几个数量级）
• 数据一旦被访问，就有可能在短期内再次被访问（临时局部原理）
  

) E2 v! X4 l9 M) Z1.2 策略
0 e; {& P5 v: r: _
缓存的创建和读取没什么好说的，无非就是检查缓存是否存在要创建或者要读取的内容。

1 L' n( w# n( C但是写缓存和缓存回收就需要好好考虑了，这里面涉及到「缓存内容」和「磁盘内容」同步的问题。

1.2.1 「写缓存」常见的有3种策略

• 不缓存(nowrite) :: 也就是不缓存写操作，当对缓存中的数据进行写操作时，直接写入磁盘，同时使此数据的缓存失效
• 写透缓存(write-through) :: 写数据时同时更新磁盘和缓存
• 回写(copy-write or write-behind) :: 写数据时直接写到缓存，由另外的进程(回写进程)在合适的时候将数据同步到磁盘
  

/ N8 G) d% h) ^9 a  N, p
: A( Y: Y$ G0 r3种策略的优缺点如下：
$ [# K) G7 j) C

策略	复杂度	性能
不缓存	简单	缓存只用于读，对于写操作较多的I/O，性能反而会下降
写透缓存	简单	提升了读性能，写性能反而有些下降(除了写磁盘，还要写缓存)
回写	复杂	读写的性能都有提高(目前内核中采用的方法)

- _1 }. t# d1 M- `# u# v, A

7 Y, n+ n9 x$ R: n6 W- m. Y1.2.2 「缓存回收」的策略

• 最近最少使用(LRU) :: 每个缓存数据都有个时间戳，保存最近被访问的时间。回收缓存时首先回收时间戳较旧的数据。
• 双链策略(LRU/2) :: 基于LRU的改善策略。具体参见下面的补充说明
    T/ ?. s% A. W. ~# U1 s4 A1 J/ Z

! B0 `7 I$ _* |# {1 V# S
9 j/ m/ e1 d9 y% y补充说明(双链策略):
: j3 Q# }  ?* M0 h+ X1 C7 E
$ Q! V  L# I' ~. G! M7 k5 H0 Z) Y! [双链策略其实就是 LRU(Least Recently Used) 算法的改进版。

它通过2个链表(活跃链表和非活跃链表)来模拟LRU的过程，目的是为了提高页面回收的性能。
/ q  D% T% [. l  q
页面回收动作发生时，从非活跃链表的尾部开始回收页面。
( }  S6 U$ U+ d1 G  j
2 P0 j9 @) w5 w. C

; F0 y9 K5 d/ l& V双链策略的关键就是页面如何在2个链表之间移动的。
6 O) f1 S6 r2 D6 x6 ?' |) r
双链策略中，每个页面都有2个标志位，分别为
0 G( p- H' G3 g) N0 c) {
PG_active - 标志页面是否活跃，也就是表示此页面是否要移动到活跃链表
  a% Y4 z9 m& N! w7 V
0 F4 _# G& H+ y$ W' TPG_referenced - 表示页面是否被进程访问到
9 [& P6 L) u, B  k  V- |# R# P# Q
/ c& J, G4 a- Y9 W
/ c" T1 |7 F. x) [' T
7 R3 L0 A6 j$ M$ F5 v页面移动的流程如下：

• 当页面第一次被被访问时，PG_active 置为1，加入到活动链表
• 当页面再次被访问时，PG_referenced 置为1，此时如果页面在非活动链表，则将其移动到活动链表，并将PG_active置为1，PG_referenced 置为0
• 系统中 daemon 会定时扫描活动链表，定时将页面的 PG_referenced 位置为0
• 系统中 daemon 定时检查页面的 PG_referenced，如果 PG_referenced=0，那么将此页面的 PG_active 置为0，同时将页面移动到非活动链表
  ( H; g9 I5 i; m6 x% O" y

+ u3 [- z2 l  z: n) o
0 B+ n- e2 u$ w$ o' p! \" ^  _8 b
2. 页高速缓存
0 ~* e. `: u! |; ?
故名思义，页高速缓存中缓存的最小单元就是内存页。

! P% m/ a* }* f9 W7 k但是此内存页对应的数据不仅仅是文件系统的数据，可以是任何基于页的对象，包括各种类型的文件和内存映射。
: W( G' W$ @; f* q9 u


2.1 简介
  E) C3 J3 D+ C7 h! y
页高速缓存缓存的是具体的物理页面，与前面章节中提到的虚拟内存空间(vm_area_struct)不同，假设有进程创建了多个 vm_area_struct 都指向同一个文件，

/ c$ d  ~; f$ B3 C# Z% [% K: F9 s. X" u那么这个 vm_area_struct 对应的 页高速缓存只有一份。

也就是磁盘上的文件缓存到内存后，它的虚拟内存地址可以有多个，但是物理内存地址却只能有一个。
" }0 o5 w- L& u# M
" p( F. g& l, `. ?! S

为了有效提高I/O性能，页高速缓存要需要满足以下条件：

" Q/ O2 ^- v  ]! ]/ }: n, o* ?5 E

• 能够快速检索需要的内存页是否存在
• 能够快速定位 脏页面(也就是被写过，但还没有同步到磁盘上的数据)
• 页高速缓存被并发访问时，尽量减少并发锁带来的性能损失
  ( U( k4 l; [0 T2 d

0 c+ w* |, V! P
) O  n* `. r8 l+ g# R1 t" H  {下面通过分析内核中的相应的结构体，来了解内核是如何提高 I/O性能的。



6 C  P# S( }- Q+ i2.2 实现
+ }3 f- Z2 d; \
实现页高速缓存的最重要的结构体要算是 address_space ，在 <linux/fs.h> 中

2 M& L2 W" ]& y* b. O

• struct address_space {
•     struct inode        *host;        /* 拥有此 address_space 的inode对象 */
•     struct radix_tree_root    page_tree;    /* 包含全部页面的 radix 树 */
•     spinlock_t        tree_lock;    /* 保护 radix 树的自旋锁 */
•     unsigned int        i_mmap_writable;/* VM_SHARED 计数 */
•     struct prio_tree_root    i_mmap;        /* 私有映射链表的树 */
•     struct list_head    i_mmap_nonlinear;/* VM_NONLINEAR 链表 */
•     spinlock_t        i_mmap_lock;    /* 保护 i_map 的自旋锁 */
•     unsigned int        truncate_count;    /* 截断计数 */
•     unsigned long        nrpages;    /* 总页数 */
•     pgoff_t            writeback_index;/* 回写的起始偏移 */
•     const struct address_space_operations *a_ops;    /* address_space 的操作表 */
•     unsigned long        flags;        /* gfp_mask 掩码与错误标识 */
•     struct backing_dev_info *backing_dev_info; /* 预读信息 */
•     spinlock_t        private_lock;    /* 私有 address_space 自旋锁 */
•     struct list_head    private_list;    /* 私有 address_space 链表 */
•     struct address_space    *assoc_mapping;    /* 缓冲 */
•     struct mutex        unmap_mutex;    /* 保护未映射页的 mutux 锁 */
• } __attribute__((aligned(sizeof(long))));
  

# j. X2 Z, \% K# a* y; h" c
& X- w, G. D7 a* M5 [+ [4 }补充说明：

9 V( B- W  J8 _) e

• inode - 如果 address_space 是由不带inode的文件系统中的文件映射的话，此字段为 null
• page_tree - 这个树结构很重要，它保证了页高速缓存中数据能被快速检索到，脏页面能够快速定位。
• i_mmap - 根据 vm_area_struct，能够快速的找到关联的缓存文件(即 address_space)，前面提到过， address_space 和 vm_area_struct 是 一对多的关系。
• 其他字段主要是提供各种锁和辅助功能
  & K1 ]* @/ }0 o3 t( I- O( V' p

此外，对于这里出现的一种新的数据结构 radix 树，进行简要的说明。
- v( `4 K: X' E3 F
radix树通过long型的位操作来查询各个节点， 存储效率高，并且可以快速查询。

linux中 radix树相关的内容参见： include/linux/radix-tree.h 和 lib/radix-tree.c
0 v. Y# l/ I( _. N! p' E% B
, O, o: ]7 H9 D& ~8 b下面根据我自己的理解，简单的说明一下radix树结构及原理。



2.2.1 首先是 radix树节点的定义

6 h2 U! p- u% U% S8 i

• /* 源码参照 lib/radix-tree.c */
• struct radix_tree_node {
•     unsigned int    height;        /* radix树的高度 */
•     unsigned int    count;      /* 当前节点的子节点数目 */
•     struct rcu_head    rcu_head;   /* RCU 回调函数链表 */
•     void        *slots[RADIX_TREE_MAP_SIZE]; /* 节点中的slot数组 */
•     unsigned long    tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS]; /* slot标签 */
• };
  9 D' i& P/ L. B, G4 ]( f: a

% g( D" J5 V# @) n) K
弄清楚 radix_tree_node 中各个字段的含义，也就差不多知道 radix树是怎么一回事了。

" P  i1 X% i7 K8 D

• height   表示的整个 radix树的高度（即叶子节点到树根的高度）， 不是当前节点到树根的高度
• count    这个比较好理解，表示当前节点的子节点个数，叶子节点的 count=0
• rcu_head RCU发生时触发的回调函数链表
• slots    每个slot对应一个子节点（叶子节点）
• tags     标记子节点是否 dirty 或者 wirteback
    W5 m4 D% J5 O% b8 o3 S4 _% ?' d5 ~( x

" {. b" f0 U: _: B; E4 T$ n. e) G
2.2.2 每个叶子节点指向文件内相应偏移所对应的缓存页

比如下图表示 0x000000 至 0x11111111 的偏移范围，树的高度为4 （图是网上找的，不是自己画的）





% G) Z) p1 K# z2.2.3 radix tree 的叶子节点都对应一个二进制的整数，不是字符串，所以进行比较的时候非常快

0 n7 f. w9 }+ R, j3 u( P其实叶子节点的值就是地址空间的值(一般是long型)


; u, _0 c9 P4 R& ^, B, K: o
3. 页回写
6 l) z  J5 {& P+ g' y
由于目前linux内核中对于「写缓存」采用的是第3种策略，所以回写的时机就显得非常重要，回写太频繁影响性能，回写太少容易造成数据丢失。
/ U% C+ G1 c( C6 B6 d" C# Q. F8 r
6 H% \/ B# B1 N2 ~1 w

3.1 简介
; A- ~9 y9 k( s( R$ T5 C2 n" q, P
* b+ [/ E6 P/ N& X( mlinux 页高速缓存中的回写是由内核中的一个线程(flusher 线程)来完成的，flusher 线程在以下3种情况发生时，触发回写操作。
# R8 N3 T) X. K& M
1. 当空闲内存低于一个阀值时
) B9 S5 g& `3 d
    空闲内存不足时，需要释放一部分缓存，由于只有不脏的页面才能被释放，所以要把脏页面都回写到磁盘，使其变成干净的页面。

) q- k9 U6 F  h5 D5 c' \- Y2. 当脏页在内存中驻留时间超过一个阀值时

   确保脏页面不会无限期的驻留在内存中，从而减少了数据丢失的风险。
( i3 r' }; j' t- x
0 q2 h2 f" p9 s" x+ M; S6 S( ]3. 当用户进程调用 sync() 和 fsync() 系统调用时

   给用户提供一种强制回写的方法，应对回写要求严格的场景。

& g6 G4 B8 j8 o4 L0 t; J! f

页回写中涉及的一些阀值可以在 /proc/sys/vm 中找到

, a' C: O5 P! ], P) ^下表中列出的是与 pdflush(flusher 线程的一种实现) 相关的一些阀值
  B, w- P# j, c6 s2 Y" [

阀值	描述
dirty_background_ratio	占全部内存的百分比，当内存中的空闲页达到这个比例时，pdflush线程开始回写脏页
dirty_expire_interval	该数值以百分之一秒为单位，它描述超时多久的数据将被周期性执行的pdflush线程写出
dirty_ratio	占全部内存的百分比，当一个进程产生的脏页达到这个比例时，就开始被写出
dirty_writeback_interval	该数值以百分之一秒未单位，它描述pdflush线程的运行频率
laptop_mode	一个布尔值，用于控制膝上型计算机模式

  `$ v4 e$ A5 t) y8 l; u
" y6 ]( n! j- f+ B5 m0 @/ e0 \' K
3.2 实现

flusher线程的实现方法随着内核的发展也在不断的变化着。下面介绍几种在内核发展中出现的比较典型的实现方法。

1. 膝上型计算机模式

这种模式的意图是将硬盘转动的机械行为最小化，允许硬盘尽可能长时间的停滞，以此延长电池供电时间。
2 T! Q$ d; ]1 M! \( ?6 A
. e- `& a6 `) c7 F" x1 a5 A- K该模式通过 /proc/sys/vm/laptop_mode 文件来设置。(0 - 关闭该模式  1 - 开启该模式)


( O" Y- x0 y- c. Y6 Y5 F9 I7 ~; V8 ]
2. bdflush 和 kupdated (2.6版本前 flusher 线程的实现方法)
' }  r8 s( k! |" D; j# @' \4 v
: i" Q" j( D8 H0 C* Cbdflush 内核线程在后台运行，系统中只有一个 bdflush 线程，当内存消耗到特定阀值以下时，bdflush 线程被唤醒
: j# w& E0 h: L# S% o/ [6 M
kupdated 周期性的运行，写回脏页。

7 E% b7 R3 \' x% x( V1 s

bdflush 存在的问题：

; ~/ I: H+ e1 P. f' u8 S整个系统仅仅只有一个 bdflush 线程，当系统回写任务较重时，bdflush 线程可能会阻塞在某个磁盘的I/O上，
, r, Q  @# A- h! S" f
8 p# F3 h" U& _$ x9 j导致其他磁盘的I/O回写操作不能及时执行。
2 b) s" _7 J/ c% g
4 K- i8 \% M9 X8 @: ]  b  m2 L+ X

, q" N/ |' q4 i) i3. pdflush (2.6版本引入)

, |9 D, G5 p7 p8 o9 p7 bpdflush 线程数目是动态的，取决于系统的I/O负载。它是面向系统中所有磁盘的全局任务的。
: y2 e& s7 q& u8 f) z: B
" r/ o( z6 V# K9 O
! u! D6 F, \) X
pdflush 存在的问题：

. F  G+ P. {9 W1 J# Y& g/ Gpdflush的数目是动态的，一定程度上缓解了 bdflush 的问题。但是由于 pdflush 是面向所有磁盘的，

所以有可能出现多个 pdflush 线程全部阻塞在某个拥塞的磁盘上，同样导致其他磁盘的I/O回写不能及时执行。

% `1 p, n; g4 {
* x+ W1 m3 p4 b( v$ |! a  g
4. flusher线程 (2.6.32版本后引入)

$ g8 G* `! A* _9 v8 x8 d: O( k7 Nflusher线程改善了上面出现的问题：
2 ^7 H6 |8 h4 {! B- Q
( v7 e% U5 c, H首先，flusher 线程的数目不是唯一的，这就避免了 bdflush 线程的问题
3 W6 H# [6 Z( G; q
其次，flusher 线程不是面向所有磁盘的，而是每个 flusher 线程对应一个磁盘，这就避免了 pdflush 线程的问题
% q6 Z3 J4 }' @# j

youOK

Linux内核设计与实现之页高速缓存和页回写