#8 GETするだけなのに書き込みが走る？memcachedのLRUとCPUの話

キャッシュサーバmemcachedをGoで再実装したcatatsuy。

「マップに入れて返すだけでしょ」と思いきや、メモリを使い切る前にデータを捨てるeviction、最近使われていないデータを管理するLRU、そして素直なLRU実装では「GETがhitしてもリスト更新が走る」という落とし穴がありました。

read-heavyなキャッシュなのに、GETが書き込みに近い処理になる。この自作版ではLRUがボトルネックになり、コード上は1コアしか使わない実装になっていました。自作してみると、mapで返すだけでは終わらない、LRUとロックの難しさが見えてきます。

本家memcachedはHOT / WARM / COLD / TEMPのような世代分けを持ち、GETのたびに毎回LRU順位を真面目に更新するのではなく、active bit、async bump、LRU maintainerなどでリスト更新を分散・近似しています。LRUを真面目にやりすぎるとロックが増えるから、あえて真面目にやらない。その工夫があるからこそ、本家memcachedは複数CPUのある環境でもスケールしやすい。

hentekoと一緒に、プロトコルの単純さと内部実装の難しさのギャップを覗いていきます。

- utsuro: https://github.com/catatsuy/utsuro

- memcached: https://github.com/memcached/memcached

- memcached - a distributed memory object caching system https://memcached.org/blog/modern-lru/

- Redis: https://redis.io/

- OpenAI Codex: https://github.com/openai/codex

- Go: https://go.dev/

─────────────

YouTube: https://youtu.be/KzZSzbZF5ik

Web: https://yaoyorozu-oss.henteko07.com/

X: https://x.com/yaoyorozu_oss