2Q：Postgres缓存算法

LRU是使用最广泛的缓存逐出算法之一，可将其实用程序扩展到多个数据库系统。尽管它很流行，但是它有很多限制，特别是当它用于管理磁盘支持的数据库（例如MySQL和Postgres）中的缓存时。

在本文中，我们将详细研究LRU的次优性，以及其变种之一称为2Q地址并对其进行改进。 2Q算法首次在论文中引入-2Q：Theodore Johnson和Dennis Shasha提出的一种低开销的高性能缓冲区管理替换算法。

LRU逐出算法将页面从缓冲区中逐出，而该页面尚未被最长访问。 LRU通常使用双链表和哈希表来实现。该算法的直觉是如此之强，实现也是如此简单，以至在80年代初期，LRU几乎是所有系统中的首选算法。但是如上所述，在某些情况下LRU执行次优。

如果数据库表大于LRU高速缓存，则数据库进程在扫描表时将擦除整个LRU高速缓存，并仅用一个扫描表中的页面填充它。如果没有再次引用这些页面，则将造成全部损失，并且数据库的性能将遭受重大打击。一旦将这些页面从缓存中逐出并且其他页面进行了输入，性能将会提高。

LRU算法使用单一维度-近期性-因为它会根据最近的访问从缓冲区中删除页面。由于它实际上并未考虑任何其他因素，因此它实际上可以逐出较暖的页面，并用较冷的页面代替它-该页面可以并且将仅被访问一次。

2Q通过引入并行缓冲区和支持队列解决了上述问题。 2Q在考虑确保真正热的页面在LRU缓存中占有一席之地的同时，也考虑了访问频率，而不只是考虑新近性。它只允许将热页面放入主缓冲区，并测试每个页面以供第二次参考。

2Q所依据的黄金法则是-仅一次访问页面并不意味着它会保留在缓冲区中。相反，应该确定是否再次访问它，然后仅将其保留在缓冲区中。

下面我们详细研究2Q算法的两个版本-简化和改进。

简化的2Q算法可用于两个缓冲区：主LRU缓冲区-Am和辅助FIFO缓冲区-A1。新的故障页首先进入辅助缓冲区A1，然后再次引用该页时，它将移至主要LRU缓冲区Am。这样可以确保移至主LRU缓冲区的页面很热，并且确实需要进行缓存。

如果驻留在A1中的页面不再被引用，则最终将其丢弃，这意味着该页面确实很冷并且不值得缓存。因此，此简化的2Q通过添加辅助缓冲区和测试页面以供第二参考使用，从而避免了简单LRU方案列出的两个次优问题。简化2Q算法的伪代码如下：

def（X：页面）：＃如果页面已经存在于LRU高速缓存中＃在缓冲区Am中如果X在Am中：Am.move_front（X）＃如果页面存在于辅助存储器中＃则不可以访问。 ＃由于再次访问该页面，表明您有兴趣＃和长期需要，请将其移至Am。 Elif X在A1中：A1.remove（X）Am.add_front（X）＃第一次访问X页，否则：＃如果A1已满，则释放一个插槽。如果A1.is_full（）：A1.pop（）＃将X添加到FIFO A1队列的前端A1.add_front（X）

调整简化的2Q缓冲区很困难-如果A1的最大大小太小，则热度测试变得过强；如果太大，则由于内存限制，Am将获得相对较小的内存，从而使主LRU缓存更小，最终导致性能下降数据库性能。

完整版2Q算法弥补了这一局限性，并在很大程度上避免了调整，而不会影响性能。

尽管“简化2Q”算法做得不错，但是在处理常见的数据库访问模式方面仍然有改进的余地，这表明，页面通常在短时间内收到大量引用，而在很长一段时间内没有引用。如果确实需要缓存页面，则在短时间内收到大量（而不只是一个）引用之后，它会继续定期接收引用和命中。

为了处理这种常见的数据库访问模式，2Q算法将辅助缓冲区A1分为两个缓冲区A1-In和A1-Out，其中新元素始终进入A1-In，并继续停留在A1-In中，直到获得访问权限为止，以确保最近的首次访问发生在内存中。

一旦页面变旧，它就会从内存中抛出，但是其磁盘引用存储在A1-Out缓冲区中。如果引用位于A1-Out中的页面被再次访问，则该页面将被提升为Am LRU，这意味着它确实是一个热页面，将再次被访问，因此需要进行缓存。

Am缓冲区仍然是常用的LRU，这意味着访问驻留在Am中的任何页面时，该页面都会移到头部，并且当需要丢弃某个页面时，逐出将从后端开始。

由于IBM的专利问题，Postgres使用2Q作为其缓存管理算法。 Postgres曾经将ARC作为其缓存算法，但是随着IBM获得了它的专利，Postgres转向了2Q。 Postgres还声称2Q的性能类似于ARC。