κeenです。先日発表したRustで作るインメモリキャッシュが全然話し足りなかったので色々補足します。 実は今回の話題はソフトウェアというよりはハードウェアの仕組みに由来するものなのですが、ソフトウェアにも応用できるだろうということで試してみた結果です。 ハードウェアでもソフトウェアでもアクセスするデータは時間局所性、つまり短期間にアクセスするデータには偏りがあるというのが仮定としてあります。 よくある例が冪乗則、あるいは80:20の法則とよばれるもので、アクセス数上位20%のものが全体の80%のアクセスを占めたりします。 データ全部はメモリに乗らないけど20%くらいだったら載るようなケースではその20%を上手く選んでメモリに載せられる仕組みがあればパフォーマンスがあがるはずです。 ということでそのような仕組み、キャッシュがほしいよねというのがモチベーションです。 キャッシュの話 まずはキ