2Q buffer cache algorithm(tedunangst.com) |
2Q buffer cache algorithm(tedunangst.com) |
The LRU is split to a hot (5/8ths) and cold (3/8ths) chain. Scans can only evict contents of the cold chain, and optionally you can specify a minimum amount of time (5.6 default: 1000ms) before a page can be promoted to the hot chain.
More details: http://dev.mysql.com/doc/refman/5.6/en/innodb-performance-mi...
There is a good comparison of page caching algorithms here: http://people.cs.vt.edu/~butta/docs/sigmetrics05_kernelPrefe... . However, the conclusion seems to be that for non-synthetic loads, the difference is fairly minimal.
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
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.