从 Web 页缓存谈起
在单位工作比较忙。没有很多时间来写正式的网页。不过在这里可以和大家随便谈谈。最近我在做一个网络应用程序的时候做了一个缓存。这个缓存很简单。效果也一般，不过也花了相当一部分时间来做。它的工作原理就是把所有用户访问过的数据库记录全放在内存里。当用户更新或删除它们的时候同时更新内存和数据库。这样的缓存其实是高级缓存，就是说它与应用程序密切相关。因为它是建立在程序较高级别的地方，因此它的复杂性会随用户数据的复杂性的增加而增加。可想而知，这样的缓存做起来非常费时，而且效率也不一定很高，特别是当有排序操作的时候，数据库的索引我们无法缓存，因此排序的效率一定不高。
对于数据库管理系统而言，它是一个通用的系统，因此它的缓存的程序复杂性与它本身要管理的数据有关，而与应用程序无关。况且许多数据库管理系统由于其专业性，缓存都经过特殊的优化，所以总体效率一定比应用程序自己的缓存高，尽管应用程序可以优化一些特殊需要以进一步提高效率。因此，如果数据库服务器与应用程序服务器是同一台电脑的话，完全没有必要使用应用程序自己的缓存。关键在于应用程序自己连接数据库需要一定时间，而减少这个时间，就能减少访问数据库的次数。因此只要让应用程序尽量一次将所有需要的数据，也可以包括一些不必要的数据，一次读入，就可以得到较高的性能。
操作的磁盘缓存与数据库的缓存有些类似。因此某些数据库管理系统基本上要求操作系统最小化磁盘缓存所占用的内存，而自行处理大多数的缓存工作，这样可以提高作为一台数据库服务器的性能。否则，将会因为双重缓存而引起内存利用率降低。
我以前在大二的时候设想过一种非常简单的缓存：假设我们要缓存一个磁盘上的各个扇区。我们用一个 n 个元素的数组，将所有缓存了的扇区的扇区号记在里面。另外使用一个 m 个元素的队列，m > n，记录最近访问过的扇区号。再用一个 k 个元素的列表，记录队列中 k 个元素（k <= m）最近一段时间内访问的次数。由于出入队列的时间复杂度是 O(1)，因此这是非常快的。当一个扇区号进入队列时，就在那 k 个元素的列表的相应位置上加 1。当一个扇区号从队列出去时，就减 1。这样就可以实现 LRU（最近最少使用）置换了，而不会退化成更简单的“最近一次使用时间最远”置换了。不过当中要解决的一个问题是，那 n 个元素的数组中存放的是不同扇区号的内容，需要一个列表对应。同样那 k 个元素的列表也有这个问题。一般可以用 B 树来处理这样的问题。不过 B 树实现起来太麻烦，AVL 树（平衡二叉排序树）实现起来也不容易，而且浪费多，并且不能按顺序访问。我自己想到的一个办法是：稀疏排序数组。比如，预先排放每 5 个元素中，有两个空位。当元素增加时，就利用空位。如果它能放进空位里（它的值正好位于空位左右元素的值之间），就放进去。否则就把左右的元素推开。如果发现推开需要的时间太长，就重新建立这个稀疏数组。反之，当删除元素时，记录数组的占空比。如果占空比太大，比如平均 5 个里面只放了 2 个元素，就重新建立。我设想的就是这样的数组。另外对于这个缓存的队列，我们可以加权，即最后一次使用的扇区号乘以一个较大的数；倒数第二次使用的扇区号乘次大的数，以此类推。结果再按扇区号加起来，看哪个最小就置换哪个。这样可以在一定程度上避免不合理的缓存（比如颠簸效应）。