LFU– tag –
-
システム設計 深掘り
キャッシュの書き込み戦略 — 更新したのに古い値が返る
在庫を 200 に直したのに、画面はいつまでも 100 のままでした。原因はキャッシュを入れたことではなく、「キャッシュをいつ書き換えるか」を決めていなかったことです。まず読み方の型を3つ(cache-aside・read-through・refresh-ahead)実装して、実装の手間・初回の遅さ・一貫性で対比します。続いて山場として、書き方の型3つ(write-through・write-behind・write-around)を実装し、書き込み時間と直後の読み込み時間を実測して表にします。さらに「消す」か「書き換える」かを比べ、2つの更新が交錯して古い値がキャッシュに残る競合を、わざと再現します。TTL を付けないと何が起きるかを maxmemory-policy を確認しながら見て、LRU・LFU・TTL の違いと、期限をばらつかせる理由まで。最後にキーの設計(何で引くか、バージョンを混ぜる、個人を混ぜ忘れて他人のデータが出る事故)と、読み多い・書き多い・失っていいかで選ぶ判断表、後片づけまでやります。 -
コンピュータ科学 深掘り
ヒープとLRUキャッシュ — 10件欲しいだけで100万件ソート
ランキングの上位10件を出すために、私は100万件を毎回まるごとソートしていました。必要なのは10件なのに、残りの999990件を丁寧に並べ替えていたわけです。この記事では VM の中に ~/cslab/heap を作り、サイズ10のヒープを手で書いて、全部ソートする版と実測で比べます。ヒープが「木なのにポインタを1つも使わず、配列1本で持てる」ことを添字の計算で確かめ、内部配列を表示してヒープがソートされていないことを見ます。後半はLRUキャッシュを素朴な O(n) 版から O(1) 版へ直し、容量を変えながらヒット率を実測します。最後に LRU・LFU・MFU・FIFO・ランダムを同じアクセス列で走らせ、LFU が「昔たくさん使われたもの」に居座られて負ける瞬間を数字で出してから、全部消します。
1