About Me

• κeen
• @blackenedgold
• Github: KeenS
• GitLab: blackenedgold
• Idein Inc.のエンジニア
• Lisp, ML, Rust, Shell Scriptあたりを書きます

モチベーション

• アプリケーションでキャッシュしたいよね
  • アクセス数の80%はアクセス頻度上位20%のアイテム
  • もうちょっと極端なケースも
• 例えば crates.ioのmost downloaded
• 少量ならメモリに載るのでDBアクセスを省きたい

ハッシュマップ？

struct CachedDao { cache: HashMap<Key, Value>, dao: Dao }
impl CacheedDao {
    fn get(&mut self, key: &Key) -> Result<Option<Value>> {
        match self.cache.get(key) {
            Some(v) => Ok(Some(v)),
            None => {
                let v = dao.get(key)?;
                if let Some(v) = &v {
                    self.cache.insert(k.clone(), v.clone())
                }
                Ok(v)
            }
        }
    }
}

🙅‍

• 使ってないデータを捨てる処理がない
• 最終的に全てのデータをメモリに載せてしまう
• →メモリ使用量制限のあるハッシュマップを作ろう
  • 現実にはアイテム数制限

インメモリキャッシュ

• ほとんどハッシュマップと一緒
• 容量が足りなくなったときの挙動が違う

キャッシュポリシー

• 容量が一杯になったときにどのアイテムを削除するか？
• 色々ポリシーがある
  • ランダム
  • ハッシュが衝突したもの
  • 一番古い要素(FIFO)
  • …
• ポリシーによってパフォーマンス（ヒット率）が変わる

Least Recently Used

• 最後に参照したのが最も古いアイテムを削除
• そこそこキャッシュヒット率が良いことで知られる
• →これで実装してみよう

LRU Explained

LRU Explained

LRU Explained

LRU Explained

LRU Explained

LRU Explained

LRU Explained

LRU Explained

LRU Explained

LRU Explained

LRU Explained

LRU Explained

LRU Explained

LRU Explained

LRU Explained

LRU Explained

LRU Explained

実装

• LRU + ハッシュマップ

実装

• LRU + ハッシュマップ
• LRUは リスト（あるいはベクタ）で簡単に実装できる
  • しかし効率が悪い
  • $O(n)$ の計算量
• ハッシュマップは標準ライブラリのものを使える
  • でもちょっと無駄がある

実装(LRU)

• 少数（定数）個のバケットを保持するブロックに分ける

実装(LRU)

• LRUを効率的に実装したい
• 少数（定数）個のバケットを保持するブロックに分ける
  • 今回は16個
  • 少数ならビット演算でLRUを実装できる
• ブロックへの振り分けはハッシュ値を使う
  • 下4bitをブロック内の振り分けに
  • 5bit目以降をブロックの振り分けに
• キャッシュヒット率を捨てて速度をとった

実装(ハッシュマップ)

• ハッシュマップにはキャッシュに必要のない機能がある
  • 容量が足りなくなったら拡大など
• LRUで管理する関係上ハッシュマップ内部のインデックスを使いたい

hashbrown

• hashbrown
• 標準ライブラリのハッシュマップはcrates.ioに公開されている
• 低レベルAPIのRawTableが公開されている
• → これを使うと実装できそう

chechire

• blackenedgold/chechire
  • 発音はチェシャ猫のcheshireと同じ
• 16-way assosiativeなhashbrownベースのキャッシュ
• ほぼ標準ライブラリの HashMap と同じAPI
• 時間の都合で紹介は省略

ベンチマーク

• 以下の3つが対象
  • chechire
  • LRUを Vec で実装した簡易キャッシュ
  • LRUを VecDeque で〃
• キャッシュサイズ16348
• ベキ分布なランダムアクセス1,000,000回
• キャッシュミスすると500usのスリープ
  • DB叩くとだいたいこのくらい？

結果

===

まとめ

• 定数個のアイテムを保持できるキャッシュを作ったよ
• アイテム管理にはLRUというポリシーがあるよ
• fully associativeだと遅いから16-wayくらいにしたよ
• Rustの HashMap は改造できるよ