Go の Cache package のベンチマークを測ってみた話

この投稿は、 Go4 Advent Calendar 2019の 15日目のものになります。

こんばんわ!!
だんだん寒くなってきましたね。

さて、私たちは普段GCPも多く利用しています。
しばらくすると得体の知れない使用されていないリソースが大量に出来上がっていて、コストを圧迫する問題があったりします。

コストコントロール/棚卸し作業で、「Lifecycle設定が出来ていないもの/諸事情で設定しづらいもの且つ、使用されていないdiskを探す」といったことがしたく、 aws cliにはそれを探すコマンドがありますが、goolgle-cloud-sdkのgcloudコマンドにはありません。
そこで、それを作ることにしました。
https://github.com/k-oguma/gce-available-disks

その際に option として、 誰が作成したものかわかるように Stackdriver loggingの activity log を検索するようにしました。 (保存期間は短いです)

しかし、業務で使うような大量のactivity logが発生するGCP projectでは検索が遅いです。
そもそもBigquery に投げて、AWS Athenaのようにした方が良いという話もありますが、全てのProjectでそうなっている訳でもないし、汎用的にしてOpen sourceにするには Local Cacheを使うことを選びました。

そういった訳で、Go の Cacheを使いたくなったので、いくつかのCache package の パフォーマンス測定を行ってみることにしました。
Go のCache packageは、今回初めて使ってみました。
ここでいうCacheは、Local cacheになります。

また、今回はTuningはせずにDefaultのままで検証してみます。

## 検証環境

- macOS Mojave v10.14.6
- iMac 27 inch Retina 5K 27-inch, 2017
- CPU 3.5GHz Intel Core i5
- Memory 24GB DDR4
- Fusion drive 1TB

## 試した Packages

試してみたのは、以下の3種類になります。

- [akyoto/cache](https://github.com/akyoto/cache)
- [patrickmn/go-cache](https://github.com/patrickmn/go-cache)
- [eko/gocache](https://github.com/eko/gocache)

この中で、eko/gocache は特殊で、GoのCache library で様々なCache機構と連携できるようにするのがコンセプトのようです。
(go build の env GOCACHEと関係ありません)

### eko/gocache の補足説明

上記3つのうち、eko/gocache は既存のものを取り入れていくスタイルで開発されています。

- Built-in stores
    - Memory (bigcache) (allegro/bigcache)
    - Memory (ristretto) (dgraph-io/ristretto)
    - Memcache (bradfitz/memcache)
    - Redis (go-redis/redis)
    - More to come soon

https://github.com/eko/gocache#built-in-stores

この中で、Local cache して検証を bigcache および ristretto で行いたいと思います。

### gocacheの注意点

この中で一番クセがあります。

- import する際は、pathに注意してください
    - `github.com/eko/gocache` ではなく、 `github.com/eko/gocache/cache` などになります。
- waitを入れないと実行で出来ません
    - `time.Sleep(10 * time.Millisecond)`

### Bigcache について

Bigcacheは、gigabyte の大きさに高速対応したcacheです。 
パフォーマンスを出すために、並行処理で例えばsync.RWMutexでは書き込みがブロックされるためにそういったものを利用するのは避け、シャードを用いて適切に分散させてゴルーチンのブロックを避けられる工夫をしているそうです。
シャードの数が比較的多く、ハッシュ関数が一意のキーに対して適切に分散された数を返す場合、ロックの競合はほぼゼロに最小化できるとのことでシャードを使用することにした理由だそうです。
また古くなったキャッシュのパージはFIFOでタイムスタンプを比較して簡単に行うようにして、キャッシュエントリに対してgcを行わないようにしlatency を減らしたようです。
https://awesomeopensource.com/project/allegro/bigcache
https://allegro.tech/2016/03/writing-fast-cache-service-in-go.html
https://github.com/allegro/bigcache

意訳
>開発を開始したとき、Go 1.6はRCにありました。要求の処理時間を短縮するための最初の取り組みは、最新のRCバージョンに更新することでした。私たちの場合、パフォーマンスはほぼ同じでした。より効率的なものを探し始め、fasthttpを見つけ ました。これは、ゼロalloc HTTPサーバーを提供するライブラリです。文書によると、合成テストでは標準のHTTPハンドラーの10倍の速度になる傾向があります。私たちのテストでは、1.5倍しか高速ではないことがわかりましたが、それでもなお優れています！

ここに書かれている fasthttp についてですが、会社でも検証されていて memory allocate をかなり減らして高速化されているようで、検証結果も良いパフォーマンスが出ました。


### Ristretto について

対して[Ristretto](https://github.com/dgraph-io/ristretto) は、次のような特徴を持っているようです。

パフォーマンスと正確性に重点を置いていて、
[Dgraph](https://github.com/dgraph-io/dgraph) (水平スケールが可能なオープンソースのグラフデータベース。GraphQLライクなQueryを持ち、Protocol Buffers over GRPC and HTTPに対応とのこと)で競合のないキャッシュが必要で開発された。
https://github.com/dgraph-io/benchmarks/tree/master/cachebench/ristretto
https://blog.dgraph.io/post/introducing-ristretto-high-perf-go-cache/

高いヒット率のようです。
ここに載っているベンチマーク結果を見ると、とてもヒット率が高く、スループットも良いようです。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4326/72285ee3-b849-b7ae-9c11-53d8c8b88213.png)
https://github.com/dgraph-io/ristretto#search


では実際どうでしょうか。
これらを試してみることにします。

## 測定用のrepository を作りました。

https://github.com/k-oguma/go-cache-benchmarks
のようなものを作りました。

測定ルールとフローとしては次のようになります。

1. 最初にメモリをflushする
    - 共有メモリではないので、最初の一回でok
2. 以下のそれぞれのpackageのDefault設定で同じ内容のベンチマーク測定を行う
    - [akyoto/cache](https://github.com/akyoto/cache)
    - [patrickmn/go-cache](https://github.com/patrickmn/go-cache)
    - [eko/gocache](https://github.com/eko/gocache) の中の以下２つ
        - Bigcache
        - Ristretto
3. key: "a", value: "b" という一文字のCache SetとGet、およびDeleteの測定を行う
4. 長文valueのCache Set とGet、およびDeleteの測定を行う

以上のような測定内容となっています。
それでは実際に計測をしてみます。

これらは全てSet & Getが出来ることを確認しています。
gocacheは少々特殊なので、コメントアウトしているものを参考にしてください。
 
### Usage

#### help

```bash
make help
```

#### Run benchmark test

```bash
make test
```

### Result

```bash
% make test
Benchmark target:  /Users/katsuyuki/go/src/github.com/k-oguma/go-cache-benchmarks/cache
goos: darwin
goarch: amd64
pkg: github.com/k-oguma/go-cache-benchmarks/cache
BenchmarkAppend_CacheEveryTime-4                          560948              1919 ns/op             744 B/op         15 allocs/op
BenchmarkAppend_CacheForLargeStringsEveryTime-4           634150              2236 ns/op             744 B/op         15 allocs/op
PASS
ok      github.com/k-oguma/go-cache-benchmarks/cache    2.546s
----------------------
Benchmark target:  /Users/katsuyuki/go/src/github.com/k-oguma/go-cache-benchmarks/go-cache
goos: darwin
goarch: amd64
pkg: github.com/k-oguma/go-cache-benchmarks/go-cache
BenchmarkAppend_CacheEveryTime-4                          379837              3836 ns/op             909 B/op         11 allocs/op
BenchmarkAppend_CacheForLargeStringsEveryTime-4           222919              4854 ns/op             913 B/op         11 allocs/op
PASS
ok      github.com/k-oguma/go-cache-benchmarks/go-cache 2.717s
----------------------
Benchmark target:  /Users/katsuyuki/go/src/github.com/k-oguma/go-cache-benchmarks/gocache
goos: darwin
goarch: amd64
pkg: github.com/k-oguma/go-cache-benchmarks/gocache
BenchmarkAppend_CacheEveryTimeForBigcache-4                           62          39577989 ns/op        337197180 B/op     11301 allocs/op
BenchmarkAppend_CacheForLargeStringsEveryTimeForBigcache-4            36          37570676 ns/op        337200235 B/op     11302 allocs/op
BenchmarkAppend_CacheEveryTimeForRistretto-4                          74          15981556 ns/op        50624497 B/op        548 allocs/op
BenchmarkAppend_CacheForLargeStringsEveryTimeForRistretto-4           76          15482215 ns/op        50625023 B/op        548 allocs/op
PASS
ok      github.com/k-oguma/go-cache-benchmarks/gocache  6.365s
----------------------
```
グラフにしてみます。
以下は実行できた回数。多い方が良いです。
<img width="593" alt="スクリーンショット 2019-12-16 0.27.01.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4326/ad6922e5-c435-4a44-9af2-69984a6859ba.png">
<img width="594" alt="スクリーンショット 2019-12-16 0.27.10.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4326/599d05b3-80ed-aaa4-a587-1046e0622388.png">

以下は、
ns/op = 処理一回あたりにかかったnsec
B/op = 一回あたりの割り当てたメモリ量(Byte)
allocs/op = 一回あたりのメモリ割り当て回数
となっていて、少ない方が良いです。
<img width="616" alt="スクリーンショット 2019-12-16 0.36.00.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4326/de99822f-897d-2720-df89-804fd60fdfc1.png">
<img width="629" alt="スクリーンショット 2019-12-16 0.37.24.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4326/1a279cc5-0c1e-ba25-7ce1-1c4d994bdd33.png">


予想外の結果になりました。
今回はDefault設定で行い、全くチューニングしていませんので、それらでも変わるかも知れません。
また、gocacheの場合は少々クセがありますが、様々なcache package をbuilt-inしているのでchain cacheみたいなCacheの連結も出来たりしていますので、高機能な方向へ向かうようです。

https://github.com/k-oguma/gce-available-disks では、go-cacheを利用させていただくことにしました。

他にもこんなGoのCache実装があるよとかオススメのGo Cache packageがありましたら、教えていただけると幸いです。

また、そのうち調べてみたり自分でも作ってみたいと思います。

明日は [mergit](https://qiita.com/mergit) さんの記事になります！