Adaptive Replacement Cache (ARC) は4つのLRU Cacheを用いることでチューニングを自動で行いヒット率を向上させたメモリのページ置換のアルゴリズム。 PostgreSQLでバッファ管理のため一時期用いられていたが、IBMの特許を回避するため今は使われていない。
ARC: A SELF-TUNING, LOW OVERHEAD REPLACEMENT CACHE, Nimrod Megiddo and Dharmendra S. Modha
それぞれ次のデータを保持する。
- T1: 最近アクセスしたもの
- T2: 2回以上参照したもの
- B1: T1から追い出されたもののキー
- B2: T2から追い出されたもののキー
次の図では中央が各LRU Cacheの先頭で、!がT1の先頭、^がT1のサイズを表す。
新規データは!の左に格納され、既にT1またはB1に存在するデータは!の右に格納される。
...(B1)...[...(T1)...!...^...(T2)...]...(B2)...
ghost listと呼ばれるB1とB2によってrecencyとfrequencyに応じたリソースの調整が自動で行われる。
B1でヒットした場合^を右に動かしてT1のサイズを増やし、T2の末尾のデータはB2に追い出される。
B2でヒットした場合^を左に動かしてT2のサイズを増やし、T1の末尾のデータはB1に追い出される。
いずれもヒットしなかった場合は!を^に近づける。
...(B1)...[...(T1)..!...→^.(T2)...]...(B2)...
...(B1)...[...(T1)..!..^←..(T2)...]...(B2)...
...(B1)...[...(T1)..→!..^..(T2)...]...(B2)...