パフォーマンスに関するスライド「What Linux can learn from Solaris performance and vice-versa」を見ててARCって単語が出てきて参照カウンタ？と思ったんだけど調べてみたらAdaptive replacement cache（ARC）のことだったので調べてみた。英語版のwikipediaに解説が合ったのでそれベースで。USENIXに論文があるけどこれを今読む気力がないので今度読む。
このARCは何かというとキャッシュなんかでよく使われているLRUの発展形のようで、LRUが単純に最近使ったものだけを管理しているのと違って以下のように4つのデータを管理する
- T1:一度アクセスされたもの
- T2:T1にあるデータが2回目にアクセスされた時にこちらに移動する
- B1:T1にあったけど最近アクセスがなくてT1から追い出されたもの
- B2:T2にあったけど最近アクセスがなくてT2から追い出されたもの
B1、B2はghost listと呼ばれる。これらはデータはキャッシュしていなくてメタデータのみをキャッシュする。また、T1とB1を合わせてL1、T2とB2を合わせてL2と呼ぶ。論文ではL1は"recency"、L2は"frequency"と呼んでいる。
wikipediaにあるキャッシュの状態の図を適当に書くとこのようになっていて、
^ [a b c B1<-[d e f T1 <-!-> T2 F E D]-> B2 C B A]
ここで新しいデータgがくるとgはT1の左側に入って、B1にいたaが追い出される。
^ [b c d B1<-[e f g T1 <-!-> T2 F E D]-> B2 C B A]
つぎにeがアクセスされるとeはT1からT2に移動する。そしてDがB2に移動し、B2のなかで最近アクセスされていなかったAが追い出される。
^ [b c d B1<-[f g T1 <-!-> T2 e F E]-> B2 D C B]
今度はB1にあるbが再度アクセスされた場合はT1のサイズが増えるが、T1のサイズが増えた分T2のデータがB2に追いやられる。 説明にないけどEがB2に移動してB2が溢れるようならBも消えるんでしょう。
^ [c d B1<-[f g b T1 <-!-> T2 e F]-> B2 E D C]
この状況でCがアクセスされた場合はCがT2に復活するのとT1のサイズが縮小する
^ [c d B1<-[f g b T1 <-!-> T2 C e F]-> B2 E D]
「キャッシュミスが合った場合はサイズには影響はないけど"!"マークが^のほうに移動する」とある。
ARCはZFSで使われている。
この方式だと実際によく使われるデータはL2に置かれるようになるからキャッシュの置き換えがLRUよりも効率的になるんでしょうね。
Systems Performance: Enterprise and the Cloud
- 作者: Brendan Gregg
- 出版社/メーカー: Prentice Hall
- 発売日: 2013/10/07
- メディア: Kindle版
- この商品を含むブログを見る
