Adaptive Replacement Cache (ARC) とは

read_paperalgorithm

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)...

参考

Adaptive replacement cache - Wikipedia

IBM patent sparks open source code rewrite | ZDNet