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


--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Reply via email to