21 ms·

2Q buffer cache algorithm

53 points by wkornewald 12y ago

ihsanyounes90 12y ago
Interesting, but what about priority algoritms? I think you have the same result of 2Q buffer.
Sami_Lehtinen 12y ago
How does that compare against ARC, CAR, LIRS and CLOCK-Pro? https://bitbucket.org/SamiLehtinen/pyclockpro https://bitbucket.org/SamiLehtinen/pyclockpro
- dmit 12y ago
  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 http://www.varlena.com/GeneralBits/96.php https://github.com/postgres/postgres/commit/4e8af8d27315c4f362f110c1a67e3251dd6b1872 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 http://dbs.uni-leipzig.de/file/ARC.pdf
- jlouis 12y ago
  Hunch: It is very workload dependent.
- jandrewrogers 12y ago
  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.
gioele 12y ago
Going from LRU to 2Q looks like going from Mark and sweep garbage collection to the JVM's eden, survivor, tenured, permanent spaces.
morgo 12y ago
FWIW, MySQL's InnoDB Storage Engine switched a few years ago from an LRU to something similar to what is described as the final solution here. 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-midpoint_insertion.html http://dev.mysql.com/doc/refman/5.6/en/innodb-performance-mi...
squeed 12y ago
2Q is clever, but certainly not the only improvement over LRU for page caching. Of interest, also, is LIRS, which uses the timing between the last two accesses to decide on a caching strategy. There is a good comparison of page caching algorithms here: http://people.cs.vt.edu/~butta/docs/sigmetrics05_kernelPrefetch.pdf 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.

53 points by wkornewald 12y ago

Interesting, but what about priority algoritms? I think you have the same result of 2Q buffer.

How does that compare against ARC, CAR, LIRS and CLOCK-Pro? https://bitbucket.org/SamiLehtinen/pyclockpro https://bitbucket.org/SamiLehtinen/pyclockpro

dmit 12y ago
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 http://www.varlena.com/GeneralBits/96.php https://github.com/postgres/postgres/commit/4e8af8d27315c4f362f110c1a67e3251dd6b1872 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 http://dbs.uni-leipzig.de/file/ARC.pdf
jlouis 12y ago
Hunch: It is very workload dependent.
jandrewrogers 12y ago
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.

gioele 12y ago

Going from LRU to 2Q looks like going from Mark and sweep garbage collection to the JVM's eden, survivor, tenured, permanent spaces.

morgo 12y ago

FWIW, MySQL's InnoDB Storage Engine switched a few years ago from an LRU to something similar to what is described as the final solution here. 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-midpoint_insertion.html http://dev.mysql.com/doc/refman/5.6/en/innodb-performance-mi...

squeed 12y ago

2Q is clever, but certainly not the only improvement over LRU for page caching. Of interest, also, is LIRS, which uses the timing between the last two accesses to decide on a caching strategy. There is a good comparison of page caching algorithms here: http://people.cs.vt.edu/~butta/docs/sigmetrics05_kernelPrefetch.pdf 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.