2Q buffer cache algorithm

When Postgres switched from ARC to 2Q in 8.0.2 due to patent concerns testing showed that "there is little if any performance loss from doing this."

http://www.varlena.com/GeneralBits/96.php

https://github.com/postgres/postgres/commit/4e8af8d27315c4f3...

Edit: this ARC paper has a performance comparison of various cache algorithms: http://dbs.uni-leipzig.de/file/ARC.pdf

Hunch: It is very workload dependent.

For practical purposes, the difference between various non-LRU algorithms are workload dependent. They all work better than LRU generally. It is always possible to contrive a pathological access pattern for a given algorithm. These more sophisticated cache replace algorithms attempt to minimize the cross-section of realistic workloads that break the algorithm. 2Q style cache replacement is not the most robust of these but it is simple to implement and understand.

One thing to be aware of when selecting these algorithms is that many of them were designed for the assumptions of much older computer systems. For systems with large memory and a low cache miss rate (most modern ones), the CPU cache friendliness of the cache replacement algorithm can have a significant impact on practical performance. This is, for example, one of the advantages of clock-style algorithms.

In a lot of good database engines, these basic algorithms are extended so that individual execution contexts can annotate the cache with their opinion on the disposition of the page. One thread may think a page is stone cold, another may think it is hot. All of this metadata is reduced to an adaptive determination of whether or not a page should be evicted at a particular point in time. It is robust and fast across workloads but is relatively complicated to implement and partially exposes the underlying implementation to the rest of the system.