# キャッシュ戦略

## キャッシュの構造

キャッシュと言えどデータ設計を意識する必要がある.

{
  "id": 1000,
  "name": "Alice",
  "logined_at": "2018-04-01T12:00Z"
}

上記の様なデータをキャッシュする場合、大量にキャッシュした場合にサイズが膨れてしまします.

そこで以下の工夫をします.

- オブジェクト型
- キーに順序を決める
- 配列にする
- 日付文字列
- 数値に置き換える(Unixエポック)

工夫した結果、以下の構造になります.
これでキャッシュサイズは半分近くまで削減できました.

[
  1000,
  "Alice",
  1522584000
]

さらにMessage Pack等を利用すると更にコンパクトになります.

- https://msgpack.org/

## キャッシュキーの工夫

キャッシュのキーにも工夫は必要です.

例えばグループ(`group_id`)に所属するメンバー(`user_id`)のキーであれば以下の様な命名規則を作ります

- `info_v${version}_${group_id}_${user_id}`
- ex) `info_v1_1000_1001`
- `${version}` はキャッシュの内部構造のバージョン

この命名規則に以下のメリットがあります
- 特定の`user_id`のキャッシュを取得
- (事前に`group_id`が特定できるのであれば)
- 前方一致でヒットさせることができる
- キャッシュの内部構造が変わったら `info_v1_*`を全てパージする等

### Rails のキャッシュキー

`RAILS_CACHE_ID` 又は `RAILS_APP_VERSION` がキャッシュキーの一部として使われる為、Railsで自前のキャッシュキーを作る時はこの辺の環境変数を入れるといいだろう。
ActiveSupportにはこれらの環境変数を考慮したキャッシュキーをくる関数が用意されている。

> ENV["RAILS_APP_VERSION"] = "8.0.2"
> ENV["RAILS_CACHE_ID"] = "20250404200000"
> ActiveSupport::Cache.expand_cache_key([:foo, :bar], "namespace")
=> "namespace/20250404200000/foo/bar"

### 複雑な検索時のキャッシュキー
上記のキャッシュキーの様に限られた条件下であれば良いのですが、詳細検索等の機能を実現する際のキーは勝手が変わってきます。

RadisやMemcached等のKVSのキーには上限があるからです.
この上限はある程度は設定等で緩和ができますが無尽蔵ではありません.

そこで以下の手順に沿ってキャッシュキーを作成します

- 検索条件等をJSONの様なフォーマットで表現
- 正規化
- 条件に関係ないキーを削除
- オブジェクトのキーをソート
- オブジェクトがネストする構造なら再帰する
- ハッシュアルゴリズムでハッシュ値を取得
- MD5やSHA-2 を利用

この方法で作成したハッシュ値は同じ検索条件であれば同じハッシュ値になります。このハッシュ値をキャッシュのキーに含めてあげればキャッシュが引ける様になります.

## キャッシュのウォームアップ
サービス等をローンチ直後にも工夫の余地はあります.

何もしなければローンチ直後はキャッシュが存在していないので、大量にキャッシュのミスヒットが起きます.

そこで事前にキャッシュをウォームアップをする様にします.

具体的にはメンテを明ける前にキャッシュが作られる様にしておきます.

全てのキャッシュを作るのは非効率なので、ECサイトやコミュニティサイトなら直近のアクセス(３日以内とか1週間以内)を元にキャッシュに乗せるようにします.

## 更新するタイミング

### Exponential backoff
- 捨てるアルゴリズムではないが間隔調整

### 元データの削除更新時
キャッシュの元になるデータの削除若しくは更新時に対象キャッシュを操作します.

- キャッシュの削除のみ
- 元データの更新削除後にキャッシュを削除
- キャッシュの更新削除
- 元データの更新時にキャッシュを上書き
- 元データの削除時にキャッシュを削除

## 破棄するタイミング

### NFU(Not Frequently Used)
- 着ない服から捨てるような感じ

参照がある度にカウントアップして、GC等のタイミング時にカウンタが少ないものから削除する

### NRU (Not Recently Used)
- お店のクリアランスセールみたいな感じ

一定間隔毎に参照ビットを全てクリアする.
参照が無いものからキャッシュアウトしていく.

### LRU(Least Recently Used)
- ソシャゲーで仲間から追い出す基準(最終ログインが古いものとか)

NRUと似てるが履歴を持っているので、
厳密なソートができる.

### FIFO(First In First Out)
- ところてん状態
- キュー

#### FIFOの改善
- セカンドチャンス
- クロック

### cache-oblivious
- [Cache obliviousの話](https://www.slideshare.net/kumagi/cache-oblivious)

厳密にはキャッシュではなくデータへのアクセスの多層化技術

CPUの低いレイヤーの話だが、キャッシュ層を意識せずに実装する方法

エラー忘却型コンピューティング(Failure-oblivious computing)とキャッシュについて調べていたら行き着いた.

## 参照
- http://yau-3n.hateblo.jp/entry/2013/07/30/013546
- https://en.wikipedia.org/wiki/Exponential_backoff
- [ページ置換アルゴリズム - Wikipedia](https://ja.wikipedia.org/wiki/ページ置換アルゴリズム)

###### tags: `Cache`