上位10件が欲しいだけで、100万件を並べ替える必要はありません。ヒープとLRUキャッシュを作って確かめます。
これは【深掘り】の記事です。本線の順路ではありません。 本線のデータ構造を自作する回で配列と連結リストまでやった人が、「では、順番を全部そろえずに『一番大きいものだけ』を速く出すには何を使うのか」を知るための記事です。飛ばしても本線は進みます。
この記事のコマンドは、VMの中(Ubuntu Server)で打ちます。 Windows の PowerShell ではありません。 VM に Node.js が入っている必要があります。 入れ方は本線のnpmの回にあります。
node -vで v20 以上が出れば大丈夫です。 作業場所は~/cslab/heap/です。 この記事のためだけに新しく作り、最後に全部消します。 既存のプロジェクトには触りません。 記事に出てくる測定値は私の環境の数字です。 皆さんの数字とは違います。見てほしいのは絶対値ではなく、条件を変えたときに何倍になるかです。
対象レベル: 中級〜上級 / 区分: 発展
「人気ランキング上位10件」で、私は100万件を並べ替えていた
自分のサイトのアクセスログから、「よく読まれた記事の上位10件」を出そうとしたときの話です。
書いたコードは、こういう形でした。
// アクセス数の配列 counts から、上位10件を取る
counts.sort((a, b) => b - a);
const top10 = counts.slice(0, 10);
2行です。動きます。 何もおかしいと思いませんでした。
おかしいと思わなかった理由は、はっきりしています。私は「上位10件を取る」という問題を、「全部を順番に並べる」という問題に、無意識で置き換えていたのです。
並べ替えてから上から10個取れば、それは確かに上位10件です。正しい。
ただ、よく考えると、私は 10件のために、残りの999,990件を丁寧に並べ替えているわけです。
11位と12位のどちらが上かは、一切知る必要がありません。 500,000位と500,001位の順序も要りません。それでも sort は全部そろえます。そういう関数だからです。
件数が1,000件のときは、これで何も困りませんでした。100万件になったときに、目に見えて待たされるようになりました。
このとき私が調べて出てきた答えが、ヒープでした。そして読んで、2つのことに驚きました。
驚いた1つ目:ヒープは「木」なのに、配列1本で持てる。 連結リストのときに出てきたポインタ(次のノードへの参照)が、1つも要りません。 親と子は添字の計算だけで分かります。
驚いた2つ目:ヒープは、ソートされていない。 「一番小さいものが先頭にある」だけです。2番目がどこにいるかは決まっていません。 それでも上位10件は正しく出ます。
そして、この記事の後半でもう1つ驚きました。同じ話が、キャッシュの「何を捨てるか」に直結していたことです。
Redis の設定に maxmemory-policy という項目があります。私はここに allkeys-lru と書いてありましたが、なぜ lru なのか、lfu を選ぶと何が変わるのかを、まったく説明できませんでした。
この記事では、LRU を自分で書いて、LFU も書いて、同じアクセス列で走らせて、負けるほうを数字で見ます。 見たあとは、設定ファイルのその1行が、ただの呪文ではなくなります。
この記事でわかること
- 「上位10件が欲しい」は、ソートの問題ではないこと。100万件の全ソートが 358ms、サイズ10のヒープなら 13.4ms(実測で 約26倍)。しかも結果は完全に一致する
- ヒープは木なのに、ポインタが1つも要らないこと。完全二分木だから、親は
(i-1)>>1、子は2i+1と2i+2という添字の計算だけで辿れる。配列1本で足りる - ヒープはソートされていないこと。条件は「親が子より小さい」だけで、左右のどちらが小さいかは決まっていない。内部配列を表示すると
1 3 2 5 9 8 7のようにきれいに並んでいない - ヒープソートは V8 の
sortより遅いこと。同じ O(n log n) でも実測で 1.2〜1.6倍遅い。O記法が同じでも速さは同じにならない - 素朴に書いた LRU キャッシュは、容量を増やすほど遅くなること。容量200で 728ms、容量1600で 8368ms(容量8倍で約11.5倍)。ハッシュマップ+双方向連結リストに直すと容量1600でも 37ms で、容量を増やしても遅くならない
- JavaScript の
Mapは挿入順を保つので、Mapだけで LRU が10行書けること。deleteしてからsetし直すだけ - LFU(使われた回数が少ない順に捨てる)は、条件によって LRU に大負けすること。流行が入れ替わると、ヒット率が LRU 44.8% に対して LFU 21.1% まで落ちる。原因は「昔たくさん使われたもの」が25件、最後まで居座り続けたこと
この記事でやること
~/cslab/heap/を作り、100万件の上位10件を「全ソート版」と「サイズ10のヒープ版」の2通りで書いて実測する- 配列1本を木として読む表を出力し、同じ木を「図」と「配列」で並べて見比べる
- 二分ヒープ(
push/pop/peek)を書き、内部配列を毎回表示して「ソートされていない」ことを目で確かめる - ヒープソートを書いて
Array.prototype.sortと競走させ、負けることを正直に測る - 優先度付きキューにして、ジョブの追い越しが起きるところを出力で見る
- LRUキャッシュを素朴な O(n) 版で書いて遅さを測り、O(1) 版に直して比べ、容量を変えながらヒット率を表にする
- LRU・LFU・MFU・FIFO・ランダムを同じアクセス列で走らせ、LFU が居座りで負ける瞬間を出してから全部消す
先に知る言葉
基本的な言葉は用語集にもまとめてあります。ここではこの記事を読むのに必要な最小限だけ書きます。
| 言葉 | 1〜2行の説明 |
|---|---|
| ヒープ | 「親が子より小さい(または大きい)」という条件だけを守った木。一番小さい(大きい)1件を速く取り出すための道具。全体はソートされていない |
| 完全二分木 | 上の段から左詰めで隙間なく埋まっている二分木。隙間が無いから、配列に順番に詰めるだけで木になる |
| 最小ヒープ / 最大ヒープ | 根(先頭)に最小が来るのが最小ヒープ、最大が来るのが最大ヒープ。条件の向きを逆にするだけで、実装はほぼ同じ |
| sift-up / sift-down | 追加した要素を親と比べながら上へ登らせるのが sift-up、根に置いた要素を子と比べながら下へ沈めるのが sift-down。日本語では「上方修正 / 下方修正」とも |
| 優先度付きキュー | 「次に処理すべきもの」を優先度で取り出す入れ物。中身はほぼ必ずヒープ。名前にキューと入っているが追い越しが起きる |
| キャッシュ | 一度計算・取得した結果を、次に同じものを聞かれたとき用に手元に置いておく仕組み。置き場所は有限なので、埋まったら何かを捨てる |
| ヒット率 | 聞かれたものがキャッシュに入っていた割合。ヒット ÷ (ヒット + ミス)。キャッシュの成績表 |
| 追い出し(eviction) | 容量が埋まったときに、どれを捨てるかを決めて捨てること。この記事の後半はここだけの話 |
| LRU | Least Recently Used。最後に使われたのが一番古いものから捨てる |
| LFU | Least Frequently Used。使われた回数が一番少ないものから捨てる |
① 上位10件のために、100万件を全部ソートしていた
まず作業場所を作ります。VMの中で打ちます。
v20 以上が出れば大丈夫です。私の環境では v22.14.0 でした。
測定を再現できるようにする
最初に、毎回同じ乱数列が出る乱数を作ります。Math.random() を使うと実行するたびに違う数字になり、比べても意味が分からなくなるからです。
中身の式は理解しなくて大丈夫です。「seed を渡すと、いつでも同じ乱数列を出してくれる関数」が返ってくるだけです。
ヒープを1つ書く
先に、この記事でずっと使う最小ヒープを作ってしまいます。中身の説明は②と③でやります。 ここでは動かすために置きます。
30行ちょっとです。 これで全部です。
2通りで上位10件を出す
私の環境での出力です。
A 全部ソート : 358.3 ms [ 999992357, 999991652, 999990398 ]
B ヒープ(size10) : 13.4 ms [ 999992357, 999991652, 999990398 ]
26倍です。そして結果は完全に一致しています。
なぜB版が速いのか
B版の中心は、この3行です。
if (h.size() < K) h.push(data[i]);
else if (data[i] > h.peek()) { h.pop(); h.push(data[i]); }
日本語にすると、こうです。
- ヒープに10件たまるまでは、とりあえず入れる
- 11件目以降は、「いま入っている10件の中で一番小さいもの」より大きいかだけを見る
- 大きければ、その一番小さいものを捨てて、新しいものを入れる
- 小さければ、何もしない
ここで 「いま入っている10件の中で一番小さいもの」を1回の操作で見られることが要点です。それが peek() です。配列の先頭を見るだけなので、比較は1回です。
これが「最小ヒープで上位10件を取る」の言い回しが最初ひっくり返って見える理由です。 上位(大きいほう)が欲しいのに、最小ヒープを使います。 ヒープに入っているのは「いまの暫定トップ10」で、そこから捨てたいのはその10件のうち一番弱いものです。だから最小を速く出せる入れ物が要る、という順序です。
O記法で言うと
計算量の書き方は本線の計算量とO記法の回でやりました。ここに当てはめると、こうなります。
| 版 | 計算量 | 100万件だと |
|---|---|---|
| A 全部ソート | O(n log n) | log₂(1,000,000) ≒ 20。100万 × 20 = 2000万 の比較オーダー |
| B サイズKのヒープ | O(n log K) | log₂(10) ≒ 3.3。100万 × 3.3 = 330万 の比較オーダー |
log の中身が n から K に変わっただけです。それだけで6倍。実測ではさらに、sort が要求する配列全体のコピーと書き戻しが無くなる分も乗って26倍になりました。
K を変えて確かめる
log K が効いているなら、K を増やすと遅くなるはずです。測ります。
K= 10 21.1ms
K= 100 22.9ms
K= 1000 24.2ms
K= 10000 48.9ms
K を1000倍にしても、2.3倍しか増えていません。 これが log K です。
この測定は、最初は失敗しました。 1つのプロセスの中で4つの K を続けて測ったら、K=1000 が一番速いという結果が出ました。詳しくは「つまずいたところ」に書きます。測定の順番で結果が変わるので、こういう比較はプロセスを分けて測る必要がありました。
📷 スクリーンショット01:
node 01-topk.mjsの出力(A版とB版のミリ秒が2行並んでいるところ)。26倍の差が1画面に収まっているのがこの記事の出発点です。
② 木なのに、配列1本で持てる
ここが、私がこの記事を書きたくなった理由です。
前の回で連結リストを書いたとき、ノードごとに「次はどこか」を持たせました。 木にするなら、当然「左の子はどこか」「右の子はどこか」を持たせるものだと思っていました。
ヒープには要りません。
理由は「隙間が無い」から
ヒープが載っている木は完全二分木です。上の段から、左詰めで、隙間なく埋まっています。
1 ← 添字 0
/ \
3 5 ← 添字 1, 2
/ \ / \
7 9 8 6 ← 添字 3, 4, 5, 6
これを上の段から左から順に、配列に詰めると、こうなります。
添字: 0 1 2 3 4 5 6
値 : 1 3 5 7 9 8 6
隙間が無いので、「どこに入るか」に迷いがありません。 だから、添字だけで親子が計算できます。
| 知りたいもの | 計算式 | JavaScript |
|---|---|---|
添字 i の親 | (i − 1) ÷ 2 の小数切り捨て | (i - 1) >> 1 |
添字 i の左の子 | 2i + 1 | 2 * i + 1 |
添字 i の右の子 | 2i + 2 | 2 * i + 2 |
| その子が存在するか | 添字が配列の長さ未満か | l < a.length |
>> 1 はビットを1つ右にずらす書き方で、2で割って小数を捨てるのと同じです。Math.floor((i - 1) / 2) と書いても同じ結果になります。
実際に確かめます。
配列: 1 3 5 7 9 8 6
添字 | 値 | 親の添字 | 親の値 | 左の子 | 右の子
0 1 - - 1(3) 2(5)
1 3 0 1 3(7) 4(9)
2 5 0 1 5(8) 6(6)
3 7 1 3 - -
4 9 1 3 - -
5 8 2 5 - -
6 6 2 5 - -
ヒープの条件を満たしているか: true
上の図と、この表を見比べてください。同じ木です。 図のほうが分かりやすいのは私も同意ですが、メモリに乗っているのは配列のほうだけです。
これが嬉しい理由は3つある
| 嬉しいこと | 中身 |
|---|---|
| メモリが小さい | ノードごとのオブジェクトも参照も要らない。値を並べるだけ |
| キャッシュに乗りやすい | 隣の添字はメモリの上でも隣。連結リストのようにあちこちに散らない |
| バグが減る | 「参照の付け替えを忘れて木が壊れる」が起きない。壊れようがない(添字は計算で出る) |
ただし、逆向きの制約もあります。 完全二分木でないものは、この持ち方ができません。 途中に隙間ができると添字の計算が合わなくなるからです。 ヒープの
pushが必ず末尾に足す、popが必ず末尾を根に持ってくるのは、隙間を作らないためです。これは効率の工夫ではなく、この持ち方を成立させるための必須条件です。
③ 二分ヒープを書く — 登って、沈む
①で置いた heap.mjs の中身を見ます。やっていることは2つだけです。
push は「末尾に置いて、上へ登る」
push(v) {
this.a.push(v); // まず末尾に置く(隙間を作らない)
let i = this.a.length - 1;
while (i > 0) { // 上へ登る(sift-up)
const p = (i - 1) >> 1; // 親の添字
if (this.a[p] <= this.a[i]) break; // 親が自分以下なら、もう条件を満たしている
[this.a[p], this.a[i]] = [this.a[i], this.a[p]]; // 親と入れ替える
i = p;
}
}
親と比べて、自分のほうが小さいなら入れ替えて上がる。 それを親が自分以下になるまで繰り返すだけです。
登る回数は木の高さを超えません。高さは要素数 n に対して log₂ n です。100万件でも20回です。
pop は「末尾を根に持ってきて、下へ沈む」
pop() {
const top = this.a[0]; // 返す値(最小)
const last = this.a.pop(); // 末尾を抜く(ここで隙間が消える)
if (this.a.length === 0) return top;
this.a[0] = last; // 末尾を根に置く(この時点で条件は壊れている)
let i = 0;
const n = this.a.length;
while (true) { // 下へ沈む(sift-down)
const l = 2 * i + 1, r = 2 * i + 2;
let m = i;
if (l < n && this.a[l] < this.a[m]) m = l;
if (r < n && this.a[r] < this.a[m]) m = r;
if (m === i) break; // 自分が2人の子より小さいなら終わり
[this.a[m], this.a[i]] = [this.a[i], this.a[m]];
i = m;
}
return top;
}
popで「小さいほうの子」と入れ替えるのが要点です。 大きいほうの子と入れ替えてしまうと、入れ替えた先で条件が壊れます(新しい親が、もう一方の子より大きくなってしまう)。私はここを一度間違えて、pop の順番がぐちゃぐちゃになりました。
沈む回数も木の高さまで。push も pop も O(log n) です。
動かして、内部配列を全部見る
ここが一番見てほしいところです。
push 5 → 内部配列: 5
push 3 → 内部配列: 3 5
push 8 → 内部配列: 3 5 8
push 1 → 内部配列: 1 3 8 5
push 9 → 内部配列: 1 3 8 5 9
push 2 → 内部配列: 1 3 2 5 9 8
push 7 → 内部配列: 1 3 2 5 9 8 7
---
peek(): 1 (最小。ここだけは必ず正しい)
内部配列はソートされているか: false
---
pop → 1 残り: 2 3 7 5 9 8
pop → 2 残り: 3 5 7 8 9
pop → 3 残り: 5 8 7 9
pop → 5 残り: 7 8 9
pop → 7 残り: 8 9
pop → 8 残り: 9
pop → 9 残り: (空)
---
取り出した順: 1 2 3 5 7 8 9
最後の内部配列を見てください。
1 3 2 5 9 8 7
ソートされていません。 3 の次に 2 が来ています。
でもヒープの条件は全部満たしています。
1
/ \
3 2
/ \ / \
5 9 8 7
- 添字0(値1)の子は 添字1(値3)と 添字2(値2)。1 < 3 かつ 1 < 2。OK
- 添字1(値3)の子は 添字3(値5)と 添字4(値9)。3 < 5 かつ 3 < 9。OK
- 添字2(値2)の子は 添字5(値8)と 添字6(値7)。2 < 8 かつ 2 < 7。OK
ヒープの条件は「親が子より小さい」だけです。 左の子と右の子のどちらが小さいかは、一切決まっていません。 ここが二分探索木との決定的な違いです。 二分探索木は「左 < 自分 < 右」なので、中順に辿ればソート済みの列が出ます。 ヒープは出ません。 逆に言うと、ヒープは守る約束が少ない。だから
pushもpopも安く済みます。
そして、pop を繰り返した「取り出した順」は 1 2 3 5 7 8 9 で、ちゃんと昇順です。
中はぐちゃぐちゃなのに、取り出す順番だけは正しい。 これがヒープです。
📷 スクリーンショット02:
node 03-run.mjsの出力全体。内部配列が1 3 2 5 9 8 7(ソートされていない)なのに、取り出した順が1 2 3 5 7 8 9になっているところが見えるように撮ります。
④ ヒープソートは、入れて出すだけ
前節の最後で、pop を繰り返すと昇順に出てきました。 ということは、これだけでソートになります。
function heapSort(src) {
const h = new MinHeap();
for (const v of src) h.push(v); // 全部入れる
const out = new Array(src.length);
for (let i = 0; i < out.length; i++) out[i] = h.pop(); // 全部出す
return out;
}
5行です。 n 回の push(各 O(log n))と n 回の pop(各 O(log n))なので、O(n log n)。sort と同じオーダーです。
しかも追加のメモリがほぼ要りません(元の配列の中でやる書き方にすれば、本当にゼロにできます)。
では、sort と同じくらい速いのでしょうか。 測ります。
N= 100000 ヒープソート 42.6ms | V8 sort 26.2ms | 比 1.62倍 | 結果一致 true
N= 200000 ヒープソート 65.7ms | V8 sort 54.8ms | 比 1.20倍 | 結果一致 true
N= 400000 ヒープソート 156.7ms | V8 sort 131.5ms | 比 1.19倍 | 結果一致 true
N= 800000 ヒープソート 342.0ms | V8 sort 254.1ms | 比 1.35倍 | 結果一致 true
負けました。 1.2〜1.6倍遅いです。
これは「O記法が同じなら速さも同じ」ではないことの、はっきりした例です。 どちらも O(n log n) です。それでも定数倍で負けます。
負ける理由は、②で「嬉しいこと」として挙げたキャッシュの効きが、ここでは逆に働くからです。
sift-downは、添字iから2i+1へ、そこから4i+3へと倍々で飛びます。n が大きいと、この飛び先はメモリの上でどんどん遠くなります- CPU はメモリからまとまった塊(キャッシュライン)で読み込むので、近くを順に読む処理は速く、遠くへ飛ぶ処理は遅い
- V8 の
sortは内部で TimSort(既にそろっている部分を見つけて活かす、隣同士をまとめる方式)を使っていて、メモリの読み方が素直です
では、ヒープソートを使う場面は無いのか。 そうでもありません。
| ヒープソートが選ばれる理由 | 中身 |
|---|---|
| 追加メモリがほぼゼロ | マージソートは作業用の配列が別に必要。組み込みなどメモリが厳しい所で効く |
| 最悪ケースでも O(n log n) | クイックソートは運が悪いと O(n²) に落ちる。ヒープソートは落ちない |
| 途中で止められる | 「上位 k 件だけ欲しい」ならk 回 pop したところで打ち切れる。①がこれ |
そして、①で26倍勝ったのは、まさに3つ目です。全部そろえないなら、ヒープのほうが強い。全部そろえるなら、sort に任せる。 この線引きが実測で出ました。
実務での結論はシンプルです。「ソートしたいだけなら
sortを使う」。 自作のヒープソートを本番に入れる理由は、ほぼありません。ヒープを自作する価値は、sortにできないこと(上位k件・優先度・追い出し)にあります。
⑤ 「優先度付きキュー」の正体
前の回で、私は「優先度付きキューはキューではない」と書きました。名前にキューと入っているのに追い越しが起きるからです。
その中身が、いまここで書いたヒープです。
数字ではなくオブジェクトを入れられるように、比較の仕方を外から渡せる形に書き直します。
投入順 : 日次バッチ(5) メール送信(3) 画像リサイズ(3) 障害アラート(1) ログ圧縮(9)
取り出し順: 障害アラート(1) メール送信(3) 画像リサイズ(3) 日次バッチ(5) ログ圧縮(9)
---
1件処理: A
緊急を投入。以降の順: 緊急 B C
最後に入れた「障害アラート」が、最初に出てきました。 キューなら最後です。
|| x.seq - y.seq を入れた理由
比較関数の2つ目の条件が、地味に大事です。
(x, y) => x.pri - y.pri || x.seq - y.seq
x.pri - y.pri が 0(優先度が同じ)のとき、|| の右側が使われて投入した順番(seq)で決着します。
これを入れないと、優先度が同じ2件の順序が「ヒープの内部の都合」で決まります。 ③で見たとおり、ヒープは左右の順序を保証しません。 だから投入順も保証されません。 出力で
メール送信(3)が画像リサイズ(3)より先に出ているのは、seqを入れたからです。入れなければ逆になることもあります。「同じ優先度なら先に来た順」を守りたいなら、自分で書く必要があります。これは安定ソートの話とまったく同じ構造です。
この形が使われている場所
| 場所 | 何を優先度にしているか |
|---|---|
| ジョブキュー | 「障害アラートは日次バッチより先」のような業務上の緊急度。待たせるAPIをキューに逃がす話は本線でも扱いました |
| ダイクストラ法 | 「いまわかっている最短距離」を優先度にして、一番近い地点から順に確定していく最短経路の求め方。カーナビや経路検索の基礎 |
| イベントスケジューラ | 発生時刻を優先度にする。ゲームやシミュレーションで「次に起きるイベント」を取り出す |
| A* 探索 | ダイクストラ法に「ゴールまでの推定距離」を足したもの。ゲームの経路探索 |
| ハフマン符号 | 出現頻度の低い2つを取り出して合体させる、を繰り返す。ZIP などの圧縮の基礎 |
5つとも「次に処理すべき1件を速く取り出したい」だけです。同じ道具です。
⑥ LRUキャッシュを書く — 容量が埋まったら何を捨てるか
ここからが山場です。
キャッシュ自体は本線のRedisの回で入れました。「一度取ったものを手元に置いておく」という話です。
そのときに私が考えていなかったのが、「置き場所が埋まったらどうするのか」です。
Redis の設定にはこう書きます。
maxmemory 100mb
maxmemory-policy allkeys-lru
この2行目が、この節と次の節の全部です。
まず素朴に書く
「一番古いものを捨てる」を、思いついたまま書きます。
容量 200 20万回: 727.7ms
容量 400 20万回: 2652.3ms
容量 800 20万回: 4348.4ms
容量 1600 20万回: 8368.3ms
容量を8倍にしたら、11.5倍遅くなりました。
これは直感に反します。「キャッシュを大きくしたら速くなる」はずですよね。 逆でした。この実装では、キャッシュを大きくするほど1回の操作が遅くなるのです。
findは先頭から順に探すので中身が多いほど遅い。「一番古いものを探す」ループも中身を全部見る。spliceは抜いたあとを全部ずらす。1回のget/setが O(n) です。
キャッシュは「速くするために入れるもの」なので、キャッシュ自体が遅いのは本末転倒です。直します。
ハッシュマップ+双方向連結リストで O(1) にする
遅い原因は、2つの「探す」です。
| 遅い操作 | いま | どうしたいか |
|---|---|---|
| キーから値を探す | 配列を先頭から find | 一発で引く |
| 一番古いものを探す | 全部の used を比べる | 探さずに、そこにある |
1つ目はハッシュマップ(JavaScript の Map)で解けます。キーから一発で引くための道具です。
2つ目は、「使った順に並んだリスト」を持っておけば、探す必要がありません。 一番古いものは必ず末尾です。
そのリストは、双方向連結リストにします。前の回で書いたあれです。
なぜ双方向(前と次の両方を持つ)なのか。 リストの真ん中にあるノードを、O(1) で抜きたいからです。 片方向リストだと「抜きたいノードの1つ前」を知るために先頭から探し直しになり、O(n) に戻ります。前へのポインタを持っているから、その場で抜けるのです。 連結リストが「配列より速いことがある」のはこういう場面で、詳しくは配列と連結リストの回でやりました。ここで効いてきます。
書きます。
head と tail の2つの番兵(sentinel)が、この実装を読みやすくしています。
番兵は「値を持たないダミーのノード」です。 これを両端に置くと、
#unlinkの中にif (n.prev === null)のような場合分けが1つも要らなくなります。 番兵が無いと、「先頭を抜くとき」「末尾を抜くとき」「1件しか無いとき」で3通りの分岐が必要になります。私は最初それを書いて、1件のときにリストが壊れました。 番兵を置いたら分岐が全部消えました。
動きを目で見て、それから測ります。
新しい→古い: C B A
get(A) = 1 → A C B
set(D) → 追い出されたのは B。中身: D A C
get(B) = undefined (もう無い)
hit=1 miss=1 evicted=1
---
容量 200 20万回: 47.3ms
容量 400 20万回: 49.7ms
容量 800 20万回: 37.1ms
容量 1600 20万回: 37.4ms
前半で、LRU の動きがそのまま見えています。
A B Cを入れた直後、新しい順はC B A。一番古いのは A- そこで
get('A')をすると、A が先頭に移る(A C B)。一番古いのは B になった set('D')で容量オーバー。捨てられたのは B。A は直前に使ったので生き残った
「最後に使われたのが一番古いもの」を捨てる。これが LRU です。
そして後半の数字。
| 容量 | 素朴な版 | O(1) 版 | 差 |
|---|---|---|---|
| 200 | 727.7ms | 47.3ms | 15倍 |
| 400 | 2652.3ms | 49.7ms | 53倍 |
| 800 | 4348.4ms | 37.1ms | 117倍 |
| 1600 | 8368.3ms | 37.4ms | 224倍 |
見てほしいのは倍率ではなく、O(1) 版の列が横一直線であることです。 容量を8倍にしても時間が増えていません。 むしろ少し減っています(容量が大きいとヒットが増えて
setの回数が減るため)。 これが O(1) の意味です。「速い」ではなく「中身の数に左右されない」。
おまけ:Map だけで LRU が10行で書ける
ここまで50行ほど書きましたが、JavaScript には抜け道があります。
JavaScript の
Mapは、キーの挿入順を保ちます。 つまりMap自体が、すでに順序付きのリストを内側に持っています。 それを使えば、連結リストを自分で書く必要がありません。
古い→新しい: A B C
get(A) 後 : B C A
set(D) 後 : C A D (Bが消えた)
---
Map版 容量 200 20万回: 80.3ms
Map版 容量 1600 20万回: 228.0ms
動きは同じです。 追い出されたのは B。
要はこの2行です。
this.m.delete(k); // いったん消す
this.m.set(k, v); // 入れ直すと、挿入順の末尾に来る
「使ったキーを最新にする」を、delete してから set で実現しています。
そして一番古いキーは this.m.keys().next().value、つまりイテレータの1個目です。
ただし、速さは自作の連結リスト版に負けます。 容量200で 80.3ms(自作は47.3ms)、容量1600で 228.0ms(自作は37.4ms)。容量を増やすと遅くなっています。
Mapのdeleteは、内部で削除済みの穴を作り、それが溜まると詰め直し(rehash)が走ります。getのたびにdelete+setをしているので、穴を作り続けているわけです。 実務ではこの差はほぼ問題になりません。 「50行の自作」より「10行のMap」のほうがバグが入らないので、私はMap版を選びます。自作版の価値は、中で何が起きているか分かることです。
ヒット率を測る — キャッシュを何%用意すればいいのか
ここまでは「速さ」の話でした。キャッシュの本当の成績は、ヒット率です。
現実のアクセスは一部のものに集中します(人気記事だけがよく読まれる)。それに近い形のアクセス列を作って、容量を変えながらヒット率を測ります。
異なるキー数: 999 / アクセス 100000
上位10キーが占める割合: 34.9%
---
容量 | 全体に対する割合 | ヒット | ミス | ヒット率 | 追い出し回数
1 0.1% 2168 97832 2.2% 97831
5 0.5% 9399 90601 9.4% 90596
10 1.0% 16568 83432 16.6% 83422
25 2.5% 30122 69878 30.1% 69853
50 5.0% 41778 58222 41.8% 58172
100 10.0% 54248 45752 54.2% 45652
200 20.0% 67180 32820 67.2% 32620
500 50.0% 85252 14748 85.3% 14248
1000 100.0% 99001 999 99.0% 0
表にすると、こうです。
| キャッシュ容量 | 全1000件に対する割合 | ヒット率 |
|---|---|---|
| 1件 | 0.1% | 2.2% |
| 10件 | 1.0% | 16.6% |
| 25件 | 2.5% | 30.1% |
| 100件 | 10.0% | 54.2% |
| 200件 | 20.0% | 67.2% |
| 500件 | 50.0% | 85.3% |
| 1000件 | 100.0% | 99.0% |
私がこの表で一番驚いたのは、10%のところです。
全体の10%しかキャッシュしていないのに、アクセスの54%がヒットしています。 1%(10件)でも16.6%。 100倍のデータのうち1%を手元に置くだけで、6回に1回は当たる。
これが「キャッシュは全部持たなくていい」の実物です。アクセスが偏っているからです。上位10キーだけで全アクセスの34.9%を占めていました。
もう1つ。容量1000(全部入る)にしても、ヒット率は 99.0% で 100% にはなりません。
ミスが 999 回残っています。これは「初めてアクセスされたとき」のミスで、どんなキャッシュでも避けられません。コールドミスと呼ばれます。1000種類のキーがあるので、ちょうど 999〜1000 回です。
キャッシュのヒット率を100%にはできません。 「初回は必ずミス」だからです。「ヒット率が上がらない」と悩む前に、上限がどこにあるかを計算するべきでした。
キャッシュを「どこに、いくつ置くか」という設計の話は、深掘りのキャッシュ層の回と更新の戦略の回でも扱っています。この節でやったのは、その1つの層の中身です。
📷 スクリーンショット03:
node 06d-hitrate.mjsの表全体。容量10%でヒット率54.2%の行が見えるように撮ります。
⑦ 追い出し方は5種類ある — LFUが居座る話
さて、⑥では「最後に使われたのが古いもの」を捨てました。それが LRU です。
捨て方は他にもあります。 全部書いて、同じアクセス列で走らせて比べます。
| 方式 | 何を捨てるか | 記録するもの |
|---|---|---|
| LRU | 最後に使われたのが一番古いもの | 最後に使った時刻 |
| LFU | 使われた回数が一番少ないもの | 使われた回数 |
| MFU | 使われた回数が一番多いもの | 使われた回数 |
| FIFO | 入れたのが一番古いもの(使ったかは見ない) | 入れた時刻 |
| ランダム | くじ引き | 何も記録しない |
MFU(多い順に捨てる)は一見あり得ませんが、「一度読んだら二度と読まない」種類のデータ(ログの流し読みなど)では理屈が立ちます。この記事では比較のための下限として置きます。
FIFO と LRU の違いは、「使ったときに順番を更新するかどうか」だけです。 FIFO は入れた順のまま。LRU は使うたびに先頭へ戻します。 ⑥の出力で
get('A')が A を先頭に移していたのが、まさにその1行の差です。
5つを同じ形で書きます。違うのは「誰を捨てるか」を返す1行だけにします。
【人気が変わらない場合】 容量 100 / アクセス 30000
LRU ヒット率 54.1%
LFU ヒット率 63.5%
MFU ヒット率 34.3%
FIFO ヒット率 48.5%
RANDOM ヒット率 47.9%
LFU-DECAY ヒット率 62.2%
【途中で流行が入れ替わる場合】 容量 30
方式 後半3万回のヒット率 / 最後まで居座った old の数
LRU 44.8% 0
LFU 21.1% 25
MFU 30.7% 0
FIFO 39.3% 0
RANDOM 39.4% 0
LFU-DECAY 52.9% 0
1つ目の結果 — 人気が変わらないなら LFU が強い
| 方式 | ヒット率 |
|---|---|
| LFU | 63.5% |
| LFU-DECAY | 62.2% |
| LRU | 54.1% |
| FIFO | 48.5% |
| ランダム | 47.9% |
| MFU | 34.3% |
LFU が LRU に約9ポイント勝ちました。
理由は素直です。人気の順位が変わらないなら、「たくさん使われた」は「これからも使われる」の良い予測になります。LRU は一度きりのアクセスが1件来ただけで、人気記事を追い出してしまうことがあります。LFU は回数で見るので動じません。
そして FIFO とランダムがほぼ同じなのも面白いところです。FIFO は「何も見ていない」のと大差ないわけです。
2つ目の結果 — 流行が入れ替わると LFU が半分に落ちる
こちらが本題です。わざと LFU が負けるアクセス列を作りました。
- 前半3万回:
old0〜old24の25件だけを、ひたすら読む(各1200回ずつ) - 後半3万回:
oldは一度も出てこない。 完全に別のnew0〜new299に移る - 容量は30件
結果です。
| 方式 | 後半のヒット率 | 最後まで居座った old の数 |
|---|---|---|
| LFU-DECAY | 52.9% | 0 |
| LRU | 44.8% | 0 |
| FIFO | 39.3% | 0 |
| ランダム | 39.4% | 0 |
| MFU | 30.7% | 0 |
| LFU | 21.1% | 25 |
LFU が最下位です。LRU の半分以下(21.1% 対 44.8%)。 右の列が原因です。
oldの25件が、最後まで1件も追い出されずに残っていました。理由は簡単です。
oldの回数は1200回ずつ。新しく入るnewは最初1回。 LFU は「回数が少ないもの」を捨てるので、捨てられるのは常に新入りです。 容量30のうち25が化石に占領され、実際に使えるのは5件だけでした。
これが LFU の弱点、「キャッシュ汚染(cache pollution)」です。
昔たくさん使われたものが、永久に居座る。 一度スターになったキーは、二度と使われなくなっても追い出せません。
対策 — 回数を減衰させる
対策は「回数を、時間が経つと減らす」です。表の一番上、LFU-DECAY がそれです。
やっていることはこの2行だけです。
if (++n % 1000 === 0) {
for (const e of m.values()) e.freq = Math.floor(e.freq / 2); // 全部半分にする
}
1000回アクセスごとに、全キーの回数を半分にする。 それだけです。
すると old の 1200 回は、1000アクセスごとに 600 → 300 → 150 → … と減っていき、やがて新入りの回数に追い抜かれて追い出されます。 右の列が 0 になっているのがその結果です。
そしてヒット率は 52.9% で、LRU の 44.8% より上になりました。「回数で見る」の強さを残したまま、居座りだけを消せたわけです。
Redis の設定は、まさにこの選択だった
ここまで書いたものが、そのまま Redis の設定項目です。
maxmemory 100mb
maxmemory-policy allkeys-lru
maxmemory-policy に指定できるものを、この記事で書いたものと並べます。
| Redis の値 | この記事で書いたもの |
|---|---|
noeviction | 捨てない。 容量を超えたら書き込みをエラーにする(読みは通る) |
allkeys-lru | ⑥で書いた LRU。全キーが対象 |
allkeys-lfu | ⑦の LFU。しかも減衰付き(lfu-decay-time) |
allkeys-random | ⑦のランダム |
volatile-lru / volatile-lfu / volatile-random | 同じだが、有効期限(TTL)が付いているキーだけを対象にする |
volatile-ttl | 残り時間が一番短いものから捨てる |
私の設定にあった allkeys-lru は、⑥で自分で書いたあれでした。
そして公式ドキュメントを読み直すと、2つ、自分の実装と違うことが書いてありました。
1つ目:Redis の LRU は、正確な LRU ではありません。 ⑥では全キーを順序リストで正確に並べていました。Redis はやりません。キーを数件ランダムに抜き出し(既定5件)、その中で一番古いものを捨てるという近似です。 理由はメモリです。全キーを双方向連結リストで並べると、キー1つあたりのポインタ2本が丸ごと無駄になります。抜き出す件数は
maxmemory-samplesで増やせて、10 にするとほぼ正確な LRU に近づくとドキュメントに書かれています。2つ目:Redis の LFU も近似で、しかも減衰が最初から入っています。 回数を正確に数えるのではなく、数バイトの確率的なカウンタで数え、
lfu-decay-time(既定1分)ごとに減らします。⑦で私が2行足した減衰が、最初から仕様として入っているわけです。理由も同じで、「過去に人気だったものを、いつまでも人気扱いしないため」とはっきり書いてあります。
設定ファイルの1行の裏に、この記事で書いたものが全部入っていました。
判断表 — どれを選ぶか
| 状況 | 選ぶもの | 理由 |
|---|---|---|
| 迷ったら | LRU(allkeys-lru) | ほとんどの現実のアクセスは偏っていて、しかも流行が変わる。 LRU は流行の変化に自動で付いていく。公式も「他を選ぶ理由が無ければこれ」と書いている |
| 人気の順位がほぼ固定(マスタデータ、設定値) | LFU(allkeys-lfu) | 回数のほうが良い予測になる。Redis の LFU は減衰付きなので、居座りも対策済み |
| 全キーが同じくらいの頻度で、順に一巡する | ランダム(allkeys-random) | 順序を記録するコストが丸ごと無駄。LRU は一巡アクセスで最悪になる(毎回、次に必要なものを捨てる) |
| TTL を丁寧に付けている | volatile-ttl | どれが要らないかをアプリ側が知っているなら、それに従うのが一番賢い |
| キャッシュではなくデータストアとして使っている | noeviction | 勝手に消えたら困るデータを、キャッシュ設定で消してはいけない。 エラーで気づくほうが良い |
| 自分でコードに書くとき | Map 10行の LRU | 自作の連結リスト版は速いが、バグが入る。 差が問題になるまで Map で足りる |
そして、どの方式を選んでも「測る」以外に答えはありません。 この記事の2つの実験で、同じ LFU が 63.5% と 21.1% になりました。 アクセス列が変わっただけです。 Redis の
INFO statsはkeyspace_hitsとkeyspace_missesを返します。hits ÷ (hits + misses)が、⑥で自分で計算したヒット率と同じものです。設定を変えたら、これを見る。 推測で選んで終わりにしない、というのは本線のパフォーマンス改善の回と同じ話です。
つまずいたところ
1. 「最小ヒープで最大10件を取る」が、頭で3回ひっくり返った
上位(大きいほう)が欲しいのに、最小ヒープを使う。 ここで完全に混乱して、最大ヒープで書き始めて動かなくなりました。
整理できたのは、ヒープに入っているものに名前を付けてからです。
- ヒープの中身は「最終結果」ではなく、「いまのところの暫定トップ10」
- 新しい候補が来たとき捨てたいのは、その10件の中で一番弱いもの
- だから最小を速く出す入れ物が要る
「何を速く取り出したいか」で向きが決まる。 最大ヒープで書くと、暫定トップ10の中の最大が先頭に来てしまい、捨てるべき最弱を探すのに10件全部見ることになります。
2. 2 * i + 1 を 2 * i と書いて、無限ループになった
添字を1から始める書き方(2i / 2i+1、親は i/2)を先にどこかで見ていて、0から始める配列に混ぜてしまいました。
i = 0 のとき 2 * 0 = 0 で、自分が自分の子になります。 while が終わりません。
添字が0から始まるなら
2i+1と2i+2、1から始めて添字0を空けるなら2iと2i+1。 どちらでもいいが、混ぜると壊れます。 私は0から始める形(2i+1)に統一しました。
3. pop で「大きいほうの子」と入れ替えて、順番が壊れた
sift-down で、比較を1つしか書いていませんでした。
// 間違い:左の子とだけ比べていた
if (l < n && this.a[l] < this.a[i]) { 入れ替え; i = l; }
これだと、左が自分より大きく、右が自分より小さいときに何も起きずに終わります。
正しくは「自分・左・右の3つの中で一番小さいもの」を選んで入れ替えます。heap.mjs の let m = i; から始まる3行がそれです。候補を変数 m に持ってから1回だけ入れ替える書き方にすると、間違えにくくなりました。
4. K を変えた測定で、K=1000 が一番速いという結果が出た
①の最後の測定です。最初は1つのプロセスの中で4つの K を順に測りました。 結果がこれです。
K= 10 15.5ms
K= 100 25.3ms
K= 1000 6.9ms
K= 10000 22.3ms
K=1000 が K=10 の半分以下。 理屈に合いません。
原因はJITコンパイラとGCです。
- Node.js(V8)は、同じコードが何度も呼ばれると、途中で機械語にコンパイルし直します。 3回目・4回目の測定は「温まった」状態で走ります
- GC(メモリの掃除)は、いつ走るか分かりません。 1回目の測定中に走れば1回目だけ遅くなります
プロセスを分けたら、素直な結果になりました。
「1回のプロセスの中で、A→B の順に測る」は、それだけで結果を歪めます。 後から測ったほうが速く出やすい。 ①のA/B比較(354ms と 13.4ms)は差が26倍なので順番の影響では説明できませんが、1.2倍のような差を測るときは、プロセスを分ける必要がありました。④のヒープソート対決も、比が 1.62 → 1.20 → 1.19 → 1.35 と揺れています。「1.2倍から1.6倍のあいだで負ける」までしか言えません。
5. 番兵を置かずに双方向連結リストを書いて、1件のときに壊れた
⑥の #unlink を、番兵なしで書いたときのコードです。
// 番兵が無いと、こうなる
if (n.prev) n.prev.next = n.next; else this.head = n.next;
if (n.next) n.next.prev = n.prev; else this.tail = n.prev;
分岐が2つ。 そして1件しか無いとき(prev も next も無い)に head と tail の両方を更新する必要があり、そこを書き忘れて、消したはずのノードが残りました。
番兵(値を持たないダミーノード)を両端に置くと、prev と next が絶対に null にならないので、分岐が全部消えます。
#unlink(n) { n.prev.next = n.next; n.next.prev = n.prev; }
1行になりました。 番兵は「メモリを2ノード余分に使って、バグを何個も消す」取引です。
6. Map 版 LRU で delete を忘れて、順番が更新されなかった
Map 版の get で、最初こう書きました。
// 間違い:delete していない
get(k) {
if (!this.m.has(k)) return undefined;
const v = this.m.get(k);
this.m.set(k, v); // これだけでは順番が変わらない
return v;
}
動きます。値も正しく返ります。 ただ LRU として機能していません。
Mapのsetは、すでに存在するキーに対しては「値を上書きするだけ」で、挿入順を変えません。 順番を最後に持っていくには、いったんdeleteして、新しいキーとしてsetする必要があります。
これに気づいたのは、⑥のヒット率が LRU として不自然に低かったからです。keysNewToOld() のような中身を表示する関数を先に用意しておいたから気づけました。キャッシュは「動いているけど賢くない」状態になりやすく、エラーが出ません。
7. LFU が負ける例を作るのに、3回失敗した
⑦の2つ目の実験です。「LFU が居座りで負ける」を見せたいのに、最初の3回は LFU が勝ってしまいました。
| 試した条件 | 結果 | なぜ失敗したか |
|---|---|---|
old 10件 / new 50件を順に一巡 / 容量60 | 全方式 99.9% | 容量が足りていた。 10 + 50 = 60 で追い出しが起きない |
old 10件 / new 50件を順に一巡 / 容量30 | LRU が 0% | 一巡アクセスは LRU の最悪ケースで、LFU 以前に LRU が壊れる |
old 10件 / new 300件に偏り / 容量30 | LFU が 47.0% で勝ち | 居座りは10件だけ。 残り20件で偏りを吸収できてしまった |
old 25件 / new 300件に偏り / 容量30 | LFU 21.1% で最下位 | 容量30のうち25が占領され、使えるのが5件だけになった |
「弱点がある」と読んで納得するのと、「弱点が出る条件」を作れるのは別のことでした。 3回目までは、弱点はあるのに数字に出ていなかっただけです。
oldが何件残っているかを表示する列を足したら、1回目から居座りは起きていたことが分かりました。症状が出ていないだけで、原因はあったわけです。そして2回目の失敗も、それ自体が学びでした。一巡アクセス(1,2,3,…,50,1,2,3,…)では、容量が1件足りないだけで LRU のヒット率が 0% になります。 次に必要になるものを、毎回ちょうど捨てるからです。Redis の公式が「一巡するアクセスなら
allkeys-random」と書いている理由がこれでした。
8. performance.now() を Date.now() で書いて、0ms が並んだ
短い測定を Date.now() でやると、0 や 1 ばかり出ました。
Date.now() はミリ秒単位の整数しか返しません。13.4ms のようなものは測れず、13 か 14 になります。 数ミリ秒の測定だとほぼ意味のない数字になります。
performance.now() は小数点以下も返す高精度タイマーで、Node.js では追加の import なしで使えます(グローバルに performance があります)。
const t = performance.now();
// 測りたい処理
console.log((performance.now() - t).toFixed(1), 'ms');
後片づけ
作ったものは ~/cslab/heap/ の中だけです。丸ごと消します。
まず、消す前に何があるかを見ます。
01-topk.mjs 01b-varyk.mjs 02-index.mjs 03-run.mjs 04-heapsort.mjs
05-pq.mjs 06-lru-naive.mjs 06b-lru-o1.mjs 06c-lru-map.mjs
06d-hitrate.mjs 07-policies.mjs heap.mjs lru.mjs rnd.mjs
14ファイル、全部この記事で作ったものです。 node_modules はありません(外部パッケージを1つも使っていないので npm install をしていません)。
消します。
~/cslab が空になったなら、それも消します。
rm -rfは確認を出さずに消します。 打つ前にパスを目で読んでください。~/cslab/heapです。先頭の~/を打ち忘れて相対パスになっていないか、pwdで今どこにいるかを確かめてからにします。
残るものは何もありません。 システムの設定も、パッケージも、サービスも触っていません。
まとめ — 理解できたこと
- 「上位10件が欲しい」は、ソートの問題ではなかった。 100万件の全ソートが 358ms、サイズ10のヒープが 13.4ms で、結果は完全に一致した。 私は10件のために999,990件を並べ替えていた
sortを呼ぶ前に「本当に全部そろえる必要があるか」を聞く。 全部そろえるならsortが最速。一部だけならヒープが勝つ。この線引きが実測で出た- ヒープは木なのに、ポインタが1つも要らない。 完全二分木で隙間が無いから、親は
(i-1)>>1、子は2i+1と2i+2という添字の計算だけで辿れる。配列1本で足りる pushが必ず末尾に足し、popが必ず末尾を根に持ってくるのは、効率の工夫ではない。 隙間を作らないための必須条件で、隙間ができたら添字の計算が成立しなくなる- ヒープはソートされていない。 条件は「親が子より小さい」だけで、左右の順序は決まっていない。内部配列は
1 3 2 5 9 8 7のように並んでいないのに、popを繰り返すと1 2 3 5 7 8 9と昇順に出る。守る約束が少ないから安い - だから優先度付きキューは、同じ優先度の順序を保証しない。 投入順を守りたいなら、比較関数に連番を自分で足す(
x.pri - y.pri || x.seq - y.seq) - O記法が同じでも速さは同じにならない。 ヒープソートと V8 の
sortはどちらも O(n log n) だが、実測で 1.2〜1.6倍負けた。sift-downが添字を倍々で飛ぶので、メモリの読み方が不利 - 素朴に書いた LRU は、容量を増やすほど遅くなった。 容量200で 728ms、容量1600で 8368ms。キャッシュを大きくすると遅くなるキャッシュを私は書いていた
- ハッシュマップ+双方向連結リストにすると、容量1600でも 37ms で横一直線になった。 O(1) の意味は「速い」ではなく「中身の数に左右されない」
- 双方向にする理由は「真ん中のノードを O(1) で抜くため」。 片方向だと1つ前を探し直しで O(n) に戻る。番兵を両端に置くと
#unlinkが1行になり、場合分けが全部消える - JavaScript の
Mapは挿入順を保つので、Mapだけで LRU が10行書ける。deleteしてからsetし直すだけ。自作版より遅いが、実務ではこれを選ぶ(バグが入らない) - 全体の10%しかキャッシュしていないのに、ヒット率は54.2%になった。 1%でも16.6%。キャッシュは全部持たなくていい。アクセスが偏っているから
- ヒット率は100%にはならない。 全部入る容量でも 99.0% で止まり、残りは初回アクセスのミス(コールドミス)。上限を先に計算する
- 同じ LFU が、条件によって 63.5% と 21.1% になった。 人気が固定なら LRU に9ポイント勝ち、流行が入れ替わると LRU の半分以下に落ちる。方式の優劣はアクセス列が決める
- LFU が負けた原因は「昔たくさん使われた25件が、最後まで1件も追い出されなかった」こと。 容量30のうち25が化石に占領され、使えるのは5件だけだった(キャッシュ汚染)
- 対策は「回数を定期的に半分にする」の2行。 それで居座りが消え、ヒット率が 52.9% になって LRU を超えた。Redis の
allkeys-lfuには、この減衰が最初から入っている(lfu-decay-time) - Redis の LRU は正確な LRU ではなく、数件を抜き出して比べる近似だった。 全キーをリストで並べるとポインタの分だけメモリを食うから。
maxmemory-samplesで精度を上げられる - 迷ったら LRU。 現実のアクセスは偏っていて、しかも流行が変わる。LRU は変化に自動で付いていく。公式も「他を選ぶ理由が無ければこれ」と書いている
- ただし、キャッシュではなくデータストアとして使っているなら
noeviction。 消えたら困るデータを、キャッシュの設定で消してはいけない - 測定は、順番だけで結果が歪む。 1プロセスで4つ続けて測ったら K=1000 が最速という嘘が出た。JIT と GC のせい。プロセスを分けて測り直す
- 短い時間は
Date.now()では測れない。 ミリ秒の整数しか返らないので、13.4ms が 13 になる。performance.now()を使う
参考リンク
- roadmap.sh — Computer Science — この記事が扱っている範囲の地図
- Redis 公式 — Key eviction —
maxmemory-policyの全選択肢、近似LRUの仕組み、maxmemory-samples、lfu-log-factorとlfu-decay-time。⑦の元ネタはここ - Redis 公式 — INFO —
keyspace_hits/keyspace_misses/evicted_keysの場所。ヒット率を実測するときに見る - Redis 公式 — CONFIG SET — 再起動せずに
maxmemoryやmaxmemory-policyを変える - MDN — Map — 「Map オブジェクトはキーの挿入順を保持する」の一文。⑥の
Map版 LRU の根拠 - MDN — Array.prototype.sort — 安定ソートであること、比較関数を渡さないと文字列として比べられること
- Node.js 公式 — Performance measurement APIs —
performance.now()の仕様。高精度タイマー - Wikipedia — Approximate counting algorithm — Redis の LFU が使っている Morris カウンタ。数バイトで回数を近似する方法
次に読む
この記事は 【深掘り】コンピュータ科学 の 10 / 25 本目です。
| 記事 | |
|---|---|
| ← 前の記事 | バランス木とB木 — 100万件が3段で届く |
| → 次の記事 | ソートアルゴリズム6種 — 並べ替えたら10が2の前に来た |
上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
- ヒープは配列で持てる
- LRU を O(1) にする
この記事は、上の項目を実際に手を動かして確かめる回です。

コメント