吴峰光：应用Linux学会预读算法

Linux发展迅速，现在已经赶上了微软，怎样才能更好的应用Linux呢？本文教会你预读算法，让Linux更易用。大家好，我将在报告里面简单的回顾一下，在之前一两年里面对预读算法的改进，和I/O性能的影响。

众所周知磁盘是非常不善于寻道的，寻道的开销很大，所以要尽量减少小的IO，一般的应用程序会进行小的IO，它会进行一个小的缓冲区，然后进行度，比如说4K，4K，8K这样的读，然后内核里面会进行优化，把小的转化成大的预读。

这个预读在下面这个图里面可以看到，上面是应用程序进行的4K的读，下面是内核进行的16K大小的，或者更大的预读。这个预读的两个主要的改进性能，一个是能够改进吞吐量，通过把小的读转换成大的预读实现的。

它通过把同步的读转换成异步的预读，来实现对IO的等待。这个预读的算法呢基本的原理是对应用程序的读请求序列进行检测，如果应用程序进行顺序的读，那就可以对它进行预读。但是实际在实现中会有很多的IO的访问模式，不仅是非常简单的顺序读，还有可能有其他的变化形式，这样就会对变化形式进行检测。还有对抖动进行一些处理。

在接下来的PPT里面我主要介绍两个预读的算法。首先这些改进是对顺序读的检测开始的，最简单的顺序读就是一页一页的往前读，所以它的判断条件非常的简单。后来有人发现有些情况下某些页面会被重复读取，这种情况呢发生在读的请求跟也面的边界不是对齐的情况下，这样同一个页面会被读取多次，这种情况实际上仍然是顺序读，所以把判断条件改进一下，加一个条件该可以应付了。后面的重次读是更复杂的情况，这种情况发生在很多的网络应用程序里面，像FTP，HTTP程序的应用。还有就是内核的AIO，在这些IO里面他们会经常提交一个比较大的读请求，这个请求会只完成一部分之后就反回，在老的内核里面，是以应用程序请求的页面作为预读的判断条件，所以这个就会被搞迷糊了，在新的2.6.23里面做了改进，它以实际读取的页面，作为预读算法的输入，这样下面这个图就是一个非常好的顺序的读。

通过这个改进呢有些用户就反映一些非常好的性能提升。像这里面是一个16级内存的服务器，它用HTTP服务了1200个客户端，这个在老的内核里面和新的内核里面，CPU的IO，IO降低了17％，网络的带宽，就是实际服务量反而提高了17％，同时对于磁盘来说，磁盘的利用率降低了26％，磁盘的带宽增加的29％。

下面是另外一个HTTP的用户报告，它说IO viter从80％降低到了20％。下面一个问题是预读抖动，这会发生在当一个预读的页面，被读者实际使用到之前就被换出了缓存，避免说有三个时间，一个读者在进行一个页面一个页面的读，然后发生了预读抖动，发生预读抖动之后所有页面就完全被从缓冲里面拿出去了，老的内核里面就会进行一个页面一个页面的IO，这里面红色的就表示发生了磁盘IO，这个效率非常低，新的版本的情况就是新的窗口会被重新建立，一个IO是4K，这样依次的递增，马上效率就恢复了。这个图是发生预读抖动之后的性能比较。

我们这个电脑用了128兆的内存，在每一秒新开一个读者，这个读者读的速度是100K每秒，逐渐逐渐的到了大概二三十秒钟的时候，这个就发生了，这个时候网络的流量在老的内核是5兆每秒，新的流量是15兆每秒，提升了3倍的性能，IO的性能也提升了8倍。

这个图是另外一种不太明显的顺序读。由于Linux那些文件结构的限制，只能处理一个文件一个流，它有两个进程，分别打开两个文件描述符进行读的时候，这能够被正确的检测出来是顺利读，但是整个文件是被两个流共享的，这样就会发生相互干扰，下面这个图大家就会看到，在内核看来发生了很多的变化。这样的话预读就会被关闭，这会导致严重的性能下降。这个是内部的文件结构，每一个对应一个打开的FD。

在这种时候呢老的算法只有一个，他们就会向两个不同的流，他们之间就没有任何相关性，顺序性就不能被检测，改进的方法是利用一个特性，就是说任何一个页面一旦被读进内存，就会被缓存一段时间，所以我们就可以去检测之前的那个页面，那个页面是不是在缓存里面，如果是的话，就是一个顺序的读。我们知道是顺序读之后就会进行预读了，然后就要解决一个进行多大预读的问题。这个预读大小就应该是安全的，预读太大了就会发生预读抖动，所以就有一些公式的推导来进行估计，这个估计是准确的，它的前提只有一个条件，就是流的数保持平稳就可以了。前面两个主要的问题解决之后，就可以得到预读的算法了。

我们看下面这个图，首先开始状况是前面一系列的等候，就表示读者已经读过了页面，这个井号表示读者正在读的页面，前面的下划线表示预读窗口，第一步我们先判断这个地方有没有页面存在，如果这个页面被缓存了，就说明这是一个顺序的流，我们就可以进行预读。为了进行预读我们就需要知道从哪里开始从哪里结束。往前收收历史的页面，确定历史页面的数目，得到一个H，这个H把它反向的影射过来，在第四步就得到了END标志，那么有了开始和结束标准，我们就可以预读了。

下面是三种预读算法的比较。在老的内核里面是只能进行一个FD，进行一个顺序读。一个文件差不多可以支持32个流，这32个流是可以改大的，但是改大了效率会比较低。根据上下文的预读是基于区域的实现，所以效率并不受流数量的影响，所以可以支持流的数目是无穷多的。这种特性非常适合对于顺序和随机读混合在一起的情况预读，这种情况下每种随机读相当于新开了一个，所以在这个图里面相当于有很多个，这种情况下是无法应付的。因为只内处理32个缺省的。那么这个上下文预读还可应用在科学计算里面。科学计算里面经常对一个大的矩阵进行裂变力。它的间隔是相等的，但是不能改进读的大小，IO的大小不能改进的话，这个性能还是受影响的，根据上小文的预读是非常多的流。这些流在进行第一次裂变力还不知道，但是是存在的，首先会进行4页面的预读，然后进行8页面的预读，这个效率就提上去了。

再下面是FNS服务器的读，这个客户端一般会进行比较大的预读，但是这个预读会被拆分成比较小的请求，这个请求到达服务器的时间可能是混乱的，这服务器可能是SMP服务器，有多个CPU，这个运行很多个FNSD，这实际接收了某一个请求的话，会使混乱加剧，这样也相当于读请求是乱序的被执行，或者是被并发的执行的。在这种情况下在6.2.23里面新的预读算法对这种混乱的读更加不敏感，有比较好的适应性，所以对NFS读性能提升是1.8倍，如果采用上下文预读的话会达到2倍，会更好一点。

接下来是稀疏读，稀疏读是当一个文件里面一部分文件，可能是1/2被应用程序读了，这样可以改变顺序性检测条件，使稀疏读得到支持。

这个是一个用户服务器，它的特点就是跳8K的读，然后再跳8K，然后再进行备份，这种就不能被老的内核检测出来，所以没有预读，在上下文预读里面性能会很好，会有40到50倍的性能提升。

最后一般认为随机读是不能常用的，但是在现实生活中会有很热门的区域，这些区域被随机读的次数非常多，也就是说它非常的密集，这样预读的命重率非常的高，这种情况下是可以进行预读的，而前面讲的基于上下文和稀疏的预读的算法，在这里面可以使用。这个另外有一个用户测试。在负载中呢，用户是随机的把一个大的文件加载到内存里面去，从这两条曲线里面可以看到，当前面部分比较稀疏读的时候，性能经常是持平的，没有太大的明显的变差，也没有明显的变好，但是当读的密度增加的时候呢，会有3倍的性能的提升。

这种密集的算法可以在其他的数据库当中应用，像播放曲目数据库等等都有不同程度的提升。希望你能学会预读算法。