漫谈缓存

 

最近我在做一个网络应用程序的时候做了一个缓存。这个缓存很简单。效果也一般，不过也花了相当一部分时间来做。它的工作原理就是把所有用户访问过的数据库记录全放在内存里。当用户更新或删除它们的时候同时更新内存和数据库。这样的缓存其实是高级缓存，就是说它与应用程序密切相关。因为它是建立在程序较高级别的地方，因此它的复杂性会随用户数据的复杂性的增加而增加。可想而知，这样的缓存做起来非常费时，而且效率也不一定很高，特别是当有排序操作的时候，数据库的索引我们无法缓存，因此排序的效率一定不高。

 

对于数据库管理系统而言，它是一个通用的系统，因此它的缓存的程序复杂性与它本身要管理的数据有关，而与应用程序无关。况且许多数据库管理系统由于其专业性，缓存都经过特殊的优化，所以总体效率一定比应用程序自己的缓存高，尽管应用程序可以优化一些特殊需要以进一步提高效率。因此，如果数据库服务器与应用程序服务器是同一台电脑的话，完全没有必要使用应用程序自己的缓存。关键在于应用程序自己连接数据库需要一定时间，而减少这个时间，就能减少访问数据库的次数。因此只要让应用程序尽量一次将所有需要的数据，也可以包括一些不必要的数据，一次读入，就可以得到较高的性能。

 

操作系统的磁盘缓存与数据库的缓存有些类似。因此某些数据库管理系统基本上要求操作系统最小化磁盘缓存所占用的内存，而自行处理大多数的缓存工作，这样可以提高作为一台数据库服务器的性能。否则，将会因为双重缓存而引起内存利用率降低。

 

我以前在大二的时候设想过一种非常简单的缓存：假设我们要缓存一个磁盘上的各个扇区。我们用一个 n 个元素的数组，将所有缓存了的扇区的扇区号记在里面。另外使用一个 m 个元素的队列，m > n，记录最近访问过的扇区号。再用一个k 个元素的列表，记录队列中 k 个元素（k <= m）最近一段时间内访问的次数。由于出入队列的时间复杂度是 O(1)，因此这是非常快的。当一个扇区号进入队列时，就在那 k 个元素的列表的相应位置上加 1。当一个扇区号从队列出去时，就减 1。这样就可以实现 LRU 和频率兼顾的置换了，而不会退化成更简单的 “最近一次使用时间最远”（LRU）置换了。不过当中要解决的一个问题是，那 n 个元素的数组中存放的是不同扇区号的内容，需要一个列表对应。同样那 k 个元素的列表也有这个问题。一般可以用 B 树来处理这样的问题。不过 B 树实现起来太麻烦，AVL 树（平衡二叉排序树）实现起来也不容易，而且浪费多，并且不能按顺序访问。我自己想到的一个办法是：稀疏排序数组。比如，预先排放每 5 个元素中，有两个空位。当元素增加时，就利用空位。如果它能放进空位里（它的值正好位于空位左右元素的值之间），就放进去。否则就把左右的元素推开。如果发现推开需要的时间太长，就重新建立这个稀疏数组。反之，当删除元素时，记录数组的占空比。如果占空比太大，比如平均 5 个里面只放了 2 个元素，就重新建立。我设想的就是这样的数组。另外对于这个缓存的队列，我们可以加权，即最后一次使用的扇区号乘以一个较大的数；倒数第二次使用的扇区号乘次大的数，以此类推。结果再按扇区号加起来，看哪个最小就置换哪个。这样可以在一定程度上避免不合理的缓存（比如颠簸效应）。（不过加权以后效率会有所降低：如果对 n 个元素加权，每次替换的时候的时间复杂度就是 O(n)）

 

 

想起以前看 Linux 书的时候，里面说过为了缓存，Linux 使用了散列表。对于散列表的实现，主要有三个方面：散列函数、冲突解决方案、散列表大小策略。一般来说，整型的散列函数就是直接输出整型值。散列表的大小策略一般就是大小为一个质数（一般来说这样可以最大程序避免冲突）。而冲突解决方案主要有三种：第一种是再散列，即冲突发生时，将新加入的元素用某种方法再查找空位；第二种是链接表，即冲突发生时，将元素以链接表结点的形式记在已有元素之后；第三种是另外开一个表，专门存储冲突元素，这一般用于冲突很少的情况。

 

再散列是比较常用的做法，因为它对散列表的结构要求比较简单：只要是数组就行。.NET 类库中的散列表就采用这种做法。再散列的方法可以是依次查找再散列，即当冲突发生时，向下依次找，找到空白位置为止。可以是对称依次查找再散列。也可以是平方探测再散列。平方探测再散列有一种特殊情况：设散列表大小是 n，如果找到 n - 1 的平方还没有找到空位，那么应该采用其他方法，如依次查找，否则将会引起死循环。举个例子：当 n = 3 时，1 的平方模 3 余 1，2 的平方模 3 是 1，此时如果再找 3 的平方，是没有意义的，因为 3 的平方模 3 余 0，又回到冲突的位置上去了。如果找 4 的平方也是没有意义的，因为 4 模 3 余 1，4 的平方模 3 的结果等于 1 的平方模 3 的结果。同样，找比 4 更大的平方也没有意义。所以要改变策略。

 

散列表的好处是：当冲突较少时，查找的时间复杂度接近 O(1)。不过坏处是：当冲突较多时，查找的时间复杂度接近 O(n)。

 

比起我所设想的稀疏数组，以再散列为冲突解决办法的散列表的好处是实现简单，平均效率可能比较高。不过稀疏数组的效率比较稳定，是它的好处。

 

 

最近感觉系统上虽然装了很多内存，但是 Windows 磁盘操作的效率仍然不是很高。当然这与内存的动态调度是有关系的，某些缓存了的数据可能被抛弃。不过还有一点：写入的速度比较慢，这是因为写缓存与读缓存实现上的不同导致的。

 

写缓存，由于缓存了磁盘上数据的更改，而系统又不是百分之一百可靠的，因此要定时向磁盘上写入，以免数据因为系统故障而丢失。所以，一般在 Windows 中，如果磁盘比较空闲，那么每秒钟就会向磁盘写入部分写缓冲的数据。如果磁盘不是很空闲，也会保证写缓冲的数据在 1 分钟之内被写入。而读数据时，只要内存中有数据，就直接读，不读磁盘，无论过了多长时间。这是因为磁盘上的内容没有被期望更改。

 

因此写缓存的效率比读缓存要差一些。这是正常现象。如果你去 hack 一下 Linux，也许可以把写缓存的写回时间改得更长，这样可以达到更高的效率，不过也让数据丢失的可能性加大了。

 

 

前天晚上和昨天（2005 年 2 月 11 日）想了很长时间，发现稀疏数组的平均效率在特殊情况下（非常不均匀的情况下）可能会很低。相比散列表就低得多了！看来还是有必要用 AVL 树（平衡二叉搜索树）或 B/B+ 树来代替的。不过现在发现一个更明显的问题：虽然散列表在特殊情况下的效率可能非常低，但是一般情况下比 AVL 树和 B 树的效率都要高。而且，AVL 树和 B 树还需要程序自己开一个内存池与内存分配/释放程序以提供高速的内存分配与释放。也就是说，多数情况下，散列表更好！看来是没有必要舍弃散列表了。呵呵。

 

 

缓存替换策略是指当可能在缓存外的数据块被访问时，老的缓存块应该如何替换以适应数据块访问模式的问题。最常见的替换策略是 LRU（Least Recently Used）：最近不使用的时间最久。即当不在缓存中的数据块被访问时，找到最近一段时间里不使用的时间最久的缓存块，把它的内容替换掉成新访问的缓存块外的数据块。还有一种是基于频率的，即把频率最低的换出。还有 FIFO，是把访问过的块放在一个队列中，但一个块被第二次访问时也不将其移到队首，而是仍向队尾推进，直到被换出。FIFO 的改进版第二次机会，即当一个块在队尾时，判断它最近是不是被访问过，如果是的话就让它再移到队首，否则换出。还有 LRU 和频率策略的折衷版：老化策略。老化策略的实现可以比较偏向 LRU，也可以比较偏向频率，因此实际上的老化策略的实现可能有相当多的不同版本。

 

我前文所说的大二时的缓存设计就是一种老化策略。它比较偏向频率策略。如果把队列的权值设为 1、0.5、0.25……并把队列的长度设为 n、2n、4n……这样它就在 LRU 和频率之间取得了一种平衡了，不过 n 可以调整以设置队列变化的速度，同时也可以减少队列的个数以使其效果接近 LRU。