https://github.com/MiCHiLU/go-lru-cache-stats
の備忘録です。
LRU cacheとは、”最近最も使われていないデータを最初に捨て”、ある限られた容量を維持し効率的なcacheを試みる、cacheアルゴリズムの中ではカジュアルなアルゴリズムです。
実装の仕方はいろいろな方法を取れますが、”値を配列状にして値の前後関係を示すポインタを切り貼りし、最新にアクセスした値を先頭に移動させ終端の値を削除する”方法が、ポインタ操作のみで完結するので最も高速になります。
Goの実装では、次のようなものがありました。
https://godoc.org/github.com/golang/groupcache/lru
https://godoc.org/github.com/dropbox/godropbox/container/lrucache
どちらもほとんど同じ実装でしたが、groupcacheはGoogleのプロダクションで広く使われているらしい記述があるのと、dropboxをwatchしていない、の独断と偏見でgroupcache/lruを利用しました。
groupcache/lruにはロックが含まれていないので、threadsafeに利用するにはラップする必要があります。groupcache/groupcacheにはロックの実装が含まれていたので、このgroupcache/groupcacheをベースに好みのLRUを実装することにしました。具体的には、peer関連とHTTP server機能を削除しました。groupcacheは複数で動作する場合には分散してcacheします。このときに、リモートにあるアクセス頻度が高い値を自分自身も保持するhotCacheという機能がありますが、このhotCacheも削除しました。
実装を眺めていて気になったのは、hotCacheにはmainCacheを含めた全体の容量（mainCache+hotCache）の1/8を割り当てている、点です。この割合はハードコードで埋め込まれていて、常にこの割合を維持するように実装されていました。
groupcache/groupcacheは、キャッシュヒット率など算出するための値をStats構造体に保持しています。アクセスがある度にStatsの値は更新されます。Statsの値を更新するにはロックが必要です。このロックがどれほどパフォーマンスに影響するか測定はしていませんが、要らない時は要らないので、Stats付き／Statsなしを選べるようにしました。
で、でき上がったのがこれです。
http://godoc.org/github.com/MiCHiLU/go-lru-cache-stats
先ほどでき立てのホヤホヤで、これから試用してみますので、なにか問題があるかもしれません。Google App Engineでの利用を想定しています。それ以外のネットワークサーバーの場合は、素直にgroupcacheを使うとよいと思います。