はじめに

RistrettoはグラフデータベースのDgraph内のキャッシュが遅いという問題から生まれたキャッシュライブラリです。
GolangWeekly(@golangweekly)で紹介されていたのを見つけて気になったので、動きを追ってみました。

Ristrettoは、以下の特徴を持っています。

EventualConsistency(更新が遅延する)
LFU(TinyLFU)を使用
リングバッファ・ブルームフィルタによるmutexの削減

今回の記事では、Ristrettoの動きを通して、これらの特徴を解説します。

なお、この記事で使用したコミットは1982be43114b186bccc231adc44a72c474369470です。
また、DgraphでRistrettoを使用するプルリクエストはありますが、まだDgraphには入っていないようです。(#4025: Use ristretto in getNew)

参考資料:

GitHubはこちら
Dgraphによる解説記事はこちら

全体像

Ristrettoを使って、Set→Getした場合の動きは下図のようになります

f:id:mrasu:20190930014715p:plain

非同期

RistrettoはSetしてもすぐに参照できるわけではありません。なぜなら、

goroutineを使うので、追加が非同期
追加するキーを評価しているので、追加に値しないと判断された場合は追加されない

からです。

Ristrettoは最初にインスタンスを作るときに、Cache#processItems()という関数をgoroutineで動かします。このprocessItemsがchannelを使ってキャッシュの更新をしています。そのため、Setは非同期になります。
また、キャッシュが満杯になっている場合には「重要なキーをキャッシュする」という信念のもと、既存のキーと新規に追加するキーの重要度を比較するので、新規のキーの重要度が低いと判断された場合にはキーは追加されません。(現在は、ランダムに選ばれた５個の既存のキーと重要度とを比較しています)

ちなみに、現時点では更新や削除の時にも同じchannelを使っているので非同期に更新されます。
そのため、下のように動きます。

cache.Set("key", "value", 1)  

time.Sleep(time.Second / 100)  
value, found := cache.Get("key")  
// value は "value"  
cache.Set("key", "value2", 1)  
cache.Del("key")  

value, found := cache.Get("key")  
// まだ、value は "value"  

time.Sleep(time.Second / 100)  
value, found = cache.Get("key")  
// value はnil (foundはfalse)

LFU(TinyLFU)を使用

RistrettoはLFUの改変版であるTinyLFUを採用しています。
まだこの論文を読んでいないのでどこまでがTinyLFUで、どこからがRistrettoの工夫なのかわからないのですが、実装では

参照時には、キーをリングバッファに追加するだけで、TinyLFU用の参照情報は非同期に更新する
リングバッファが貯まると、貯めていたキーをchannelへ追加
channelを通して、参照情報を更新する(ただし、ブルームフィルタを使用することで、対象のキーが初めて参照されたかを確認する。初めての場合には参照情報には追加せずブルームフィルタにのみ追加される)