Re: 2nd Level Buffer Cache

Hi, hackers.

I am interested in this discussion!
So I surveyed current buffer algorithms around other software. I share about it.
(sorry, it is easy survey..)

CLOCK-PRO and LIRS are popular in current buffer algorithms in my easy survey.
Their algorithms are same author that is Song Jiang.
CLOCK-PRO is improved LIRS algorithm based on CLOCK algorithm.

CLOCK-PRO is used by Apache Derby and NetBSD.
And, LIRS is used by MySQL.

The following is easy explanation of LIRS.

LRU use Recency metric that is the number of other blocks accessed from last reference to the current time.

Strong points of LRU
- Low overhead and simplicity data structure
- LRU assumption is works well

Weak points of LRU
- A recently used block will not necessarily be used again or soon
- The prediction is based on a single source information

LIRS algorithm use Recency metric and Inter-Reference Recency(IRR) metric that is the number of other unique blocks accessed between two consecutive references to the block.
The priority in LIRS algorithm is the order of IRR and Recency.
IRR metric compensate for LRU weak points.

LIRS paper insists on the following.
- LIRS is same overhead as LRU.
- Results of experiments were indicated that LIRS is higher buffer hit rate than LRU and other buffer algorithms.
* Their experiment is used LIRS and other algorithms in PostgreSQL buffer system.

In CLOCK-PRO paper is indicated that CLOCK-PRO is superior than LIRS and other buffer algorithms (including Arc).

I think that PostgreSQL is very powerful and reliable database!
So I hope that PostgreSQL buffer system will be more powerful and more intelligent.

Thanks.

[Refference]
- CLOCK-PRO: http://www.ece.eng.wayne.edu/~sjiang/pubs/papers/jiang05_CLOCK-Pro.pdf
- LIRS: http://dragonstar.ict.ac.cn/course_09/XD_Zhang/%286%29-LIRS-replacement.pdf
- Apache Derbey(Google Summer Code): http://www.eecg.toronto.edu/~gokul/derby/derby-report-aug-19-2006.pdf
- NetBSD source code: http://fxr.watson.org/fxr/source/uvm/uvm_pdpolicy_clockpro.c?v=NETBSD
- MySQL source code: http://mysql.lamphost.net/sources/doxygen/mysql-5.1/structPgman_1_1Page__entry.html
- Song Jiang HP: http://www.ece.eng.wayne.edu/~sjiang/

--
Kondo Mitsumasa
NTT Corporation, NTT Open Source Software Center