計算量・探索・ハッシュ表・データ構造を、1つの動くキーバリューストアに束ねる演習です。索引を付けた効果を自分で測ります。
これは【深掘り】コンピュータ科学コースの「到達作品」の回です。本線の順路ではありません。 この回では新しい知識を1つも足しません。 これまで別々に書いてきた——計算量とO記法・線形探索・ハッシュ表・配列と連結リスト・ヒープとキャッシュ——を、1つの動くツールに束ねて、実際に作って、計測して締めます。 飛ばしても本線は進みます。
この記事のコマンドは、VMの中(Ubuntu Server)で打ちます。Node.js が要ります。 Windows の PowerShell ではありません。入れ方は本線のnpmの回にあります。
node -vで v20 以上が出れば大丈夫です。私の環境ではv22.14.0でした。 作業場所は~/cslab/kv/です。 この記事のためだけに新しく作り、最後に全部消します。 既存のプロジェクトには触りません。 記事に出てくる測定値は私のVMの数字です。 皆さんの数字とは違います。見てほしいのは絶対値ではなく、件数を変えたときに何倍になるかです。
対象レベル: 中級〜上級 / 区分: 発展
めがける作品
このコースで学んだことは、正直に言うと、バラバラでした。
「計算量は測ると本当に100倍になる」「ハッシュは一発で引ける」「連結リストは真ん中を速く抜ける」「LRUは古いものを捨てる」——どれも1本ずつは分かったのに、それらが1つの道具の中でどう協力しているのかは、見ていませんでした。
だからこの回で、それを1つに束ねた小さな道具を、自分の手で作ります。
自分で小さなKVストアを作る。ハッシュで一発で引き、容量を超えたらLRUで古いものを捨てる。線形探索の版と比べて、計算量の理屈が実測で確かめられる。
KVストアとは「キー(名前)を渡すと、値が返ってくる入れ物」です。Map も、Redis も、データベースの索引も、いちばん底ではこれをやっています。中身を自分で書くと、「なぜ速いのか」が魔法でなくなります。
作るものは、部品で言うと2つの合わせ技です。
- 一発で引く部分=ハッシュ表の回で書いたハッシュ索引
- 容量を超えたら捨てる部分=ヒープとキャッシュの回で書いたLRU
この2つを1つのクラスにまとめると、get も set も、追い出しも、全部が「中身の件数に左右されない(O(1))」入れ物になります。 それを、遅い線形探索の版と並べて測って、「O記法の予想」と「実測の数字」が一致することを目で見る——これがこのコースの到達点です。
この記事でわかること
- 「一発で引ける」の正体は、探していないからだということ。線形探索は10万件で1回引くのに 328.90マイクロ秒、自作KVは0.715マイクロ秒(実測で約460倍)。しかも件数が増えるほど差が開く
- O記法の予想は、実測の数字とちゃんと一致すること。線形探索は件数を10倍にすると時間もほぼ10倍(O(n))、自作KVは件数を10倍にしても時間がほぼ変わらない(O(1))。これがこのコースの到達点
- ハッシュ索引は、放っておくと壊れること。バケットを1個に固定すると、自作KVは線形探索と同じ 312.7ミリ秒に落ちる。O(1)は「衝突が散っていること」に賭けた上での性質
- キャッシュは大きくするほど得だが、得の伸びは鈍ること。キー1万件に対し容量を1%にするとヒット率30.9%、10%で67.2%、50%で88.5%。全部を持たなくても、人気キーだけで大半が当たる
- RedisやMapの中で起きているのは、いま自分で書いたものと同じだということ。
maxmemory-policy allkeys-lruの1行が、呪文でなくなる - 道具の中身が分かると、いつ使うべきかを自分で判断できること。「とりあえず配列」で困る境目が、件数で言えるようになる
この記事でやること
~/cslab/kv/を作り、配列に持って線形探索する「遅いKVストア」を書いて、10万件で1回引く時間を実測する- 文字列を数字にするハッシュ関数(FNV-1a)を書き、それを使ったハッシュ索引を自作して、線形探索とベンチする
- わざと衝突させて鎖を目で見て、負荷率とリサイズを実装し、バケットを1個に潰すと O(1) が O(n) に落ちるところを測る
- ハッシュ索引と双方向連結リストを1つにまとめ、容量を超えたらLRUで捨てる
MiniKVを作る - 人気キーに偏ったアクセス列を作り、容量を変えながらヒット率を表にする
- 線形探索と自作KVの get 時間を1枚の表に並べ、O記法の予想と実測が一致することを確かめる
- 完成をチェックリストで判定し、全部消す
先に知る言葉
基本的な言葉は用語集にもまとめてあります。ここではこの記事を読むのに必要な最小限だけ書きます。どれも、このコースの過去の回で一度は出てきた言葉です。
| 言葉 | 1〜2行の説明 |
|---|---|
| KVストア | キー(名前)を渡すと値が返る入れ物。Key-Value。Map も Redis もこれ。「一発で引けること」が命 |
| 線形探索 | 先頭から1つずつ順番に見て、目当てを探すこと。件数が増えるほど遅くなる(平均で半分見る) |
| ハッシュ関数 | 文字列などを、決まった手順で数字に変える関数。同じ入力なら必ず同じ数字。ここでは置き場所を決めるために使う |
| バケット | ハッシュ値から決まる「置き場所」の1マス。配列の1要素だと思ってよい |
| 衝突 | 違うキーが同じバケットに来ること。事故ではなく必ず起きる。鎖(チェイン)でつないで解く |
| 負荷率(ロードファクタ) | 入っている件数 ÷ バケット数。高いほど鎖が長くなり遅くなる。0.75あたりで拡張するのが定番 |
| リサイズ | バケット数を増やして、全部のキーを置き直すこと。その1回は重いが、ならすと安い(償却) |
| LRU | Least Recently Used。最後に使われたのが一番古いものから捨てる追い出し方 |
| ヒット率 | 聞かれたものがキャッシュに入っていた割合。ヒット ÷ (ヒット + ミス)。キャッシュの成績表 |
| O(1) / O(n) | 中身の件数を n としたとき、処理時間が件数に左右されないのが O(1)、件数に比例するのが O(n) |
① 何を作るか — 2つの部品を1つに束ねる
まず作業場所を作ります。VMの中で打ちます。
v20 以上が出れば大丈夫です。
この回で作るものを、先に1枚の絵にします。新しい部品は1つもありません。 過去2回で書いたものを、横に並べるだけです。
get("user:42")
│
▼
┌──────────────────┐ ← ③④で作る:ハッシュ索引
│ fnv1a("user:42") │ キーを数字にして、余りでバケットを決める
│ → バケット17 │ → 一発で「そのノードはどこか」が分かる
└──────────────────┘
│ 見つけたノードを…
▼
┌──────────────────┐ ← ⑤で作る:双方向連結リスト(LRUの順番)
│ 新しい ⇄ … ⇄ 古い │ 使ったノードを「新しい側」の先頭へ移す
│ head tail │ 容量オーバーなら tail(最古)を捨てる
└──────────────────┘
上の箱(ハッシュ索引)が「速く引く」を担当し、下の箱(連結リスト)が「何を捨てるか」を担当します。 1つのノードが、両方に同時に所属しているのがミソです。ハッシュからは「どこにあるか」で辿れて、リストからは「新しい順」で辿れる。同じノードを2通りの見方でつないでおく——これが合わせ技の中身です。
この作品には、このコースで書いてきた回が、そのまま部品として入っています。 どの回が、どこに効くのかを1枚にします。
| このコースの回 | この作品での役割 |
|---|---|
| 計算量とO記法 | 「O(n)」「O(1)」という予想の物差し。⑥で実測と突き合わせる |
| 探索の回 | ②の線形探索。まず遅い版を作る根拠 |
| ハッシュ表 | ③④のハッシュ索引。一発で引く/衝突/リサイズ |
| 配列と連結リスト | ⑤の双方向連結リスト。真ん中を O(1) で抜く |
| ヒープとキャッシュ | ⑤のLRU。容量を超えたら捨てる/ヒット率 |
別々に読むと「へえ」で終わっていた5本が、1つの道具の中で役割を持ちます。 それを組み立てて、動かして、測る。これが到達作品です。
なぜわざわざ2つ持つのか。 「速く引く」だけならハッシュ索引1つで足ります。でも、容量が有限だと『どれを捨てるか』を決めないといけません。 ハッシュ索引は「順番」を持っていないので、そのままでは「一番古いもの」が分かりません。だから順番を持つリストを横に足すのです。Redisの回で
maxmemory-policyを設定したときの、あの「捨て方」の中身がこれです。
では、なぜ最初からその合わせ技を作らないのか。 遠回りに見えても、「まず遅い版を作って、遅さを自分の手で測る」ところから始めます。 速い版だけ見せられても、「何がどう速いのか」は身に付かないからです。
② まず遅い版 — 配列に持って、線形探索する
一番素朴なKVストアを書きます。配列に { キー, 値 } を並べて、キーで探すだけです。
まず、測定を再現できるように、毎回同じ乱数列が出る乱数を用意します。Math.random() だと実行のたびに違う数字になり、比べられなくなるからです。
中身の式は理解しなくて大丈夫です。「seed を渡すと、いつでも同じ乱数列を出す関数」が返るだけです。
次に、線形探索版のKVストアです。
.find() は、配列を先頭から1つずつ見て、条件に合う最初の要素を返す関数です(MDN の Array.find)。つまり get のたびに、平均で件数の半分を見ています。
測り方に、2つ工夫を入れています。あとの節でも全部これに揃えるので、先に断っておきます。
asks(何を引くか)を、計測ループの外で先に作っておく。 ループの中で乱数を回すと、乱数の生成時間まで一緒に測ってしまうからです。純粋に「引く時間」だけを測りたい- 件数
Nと、引く回数M(2万回)を別にする。Nはストアの中身の量、Mは測定の精度です。1回だけ測ると誤差が大きいので、同じ条件で2万回引いて、その合計を回数で割ります
performance.now() は、ミリ秒を小数まで返す高精度な時計です(MDN・Node.js ではperf_hooks)。Date.now() より細かく測れます。
私の環境での出力です。
件数 10000 | 20,000回引く: 621.5ms | 1回あたり 31.07us (check 100304590)
件数 50000 | 20,000回引く: 3016.6ms | 1回あたり 150.83us (check 501668188)
件数 100000 | 20,000回引く: 6578.0ms | 1回あたり 328.90us (check 1008647330)
注目は「1回あたり」の列です。
| 件数 | 1回引く時間 | 前の行から |
|---|---|---|
| 10,000 | 31.07us | — |
| 50,000 | 150.83us | 約4.9倍(件数5倍) |
| 100,000 | 328.90us | 約10.6倍(件数10倍) |
件数を10倍にしたら、1回引く時間もほぼ10倍になりました。 これが O(n) です。計算量の回で「データが10倍で100倍」と書いたのは、中で線形探索を2重に回したときの話でした。今回は1重なので、素直に10倍です。 これが「なぜハッシュが要るか」の答えの半分です。 件数が増えるだけで、何もしていないのに引く時間が伸びていく。これを止めたい。
[スクリーンショット: 01_linear.png] node 01-linear.mjs の出力を撮ってください。「1回あたり」の列が 31 → 150 → 328 マイクロ秒と、件数に比例して伸びているのが、この記事の出発点です。
check の列は、引いた値の合計です。あとで速い版と数字が一致することの確認に使います。 「速いけど答えが違う」では意味がないからです。
③ ハッシュ索引を自作 — 探さずに、場所を計算する
線形探索が遅いのは、「どこにあるか分からないから、探している」からです。
ハッシュ表の考え方はこうでした(ハッシュ表の回)。
キーを数字に変えて、その数字からバケット(置き場所)を計算する。すると、探さずに置き場所が分かる。
まず「文字列を数字にする」関数を書きます。定番の FNV-1a です。
長く見えますが、要点は3つだけです。
fnv1a— 文字列を1文字ずつ「掛けて混ぜる」だけ。Math.imulは32bit整数としての掛け算で、あふれを気にせず混ぜられます。同じ文字列なら、必ず同じ数字が出ます_idx— ハッシュ値をバケット数で割った余りが、置き場所。バケット数を2のべき乗にしてあるので、& (cap - 1)が余りと同じになります(速い)set/get— 計算した置き場所を、いきなり見る。探す作業が無い
同じ条件で、線形探索と同じベンチを回します。
件数 10000 | 20,000回引く: 3.3ms | 1回あたり 0.167us | バケット 16384 | 最長鎖 4
件数 50000 | 20,000回引く: 4.3ms | 1回あたり 0.213us | バケット 131072 | 最長鎖 5
件数 100000 | 20,000回引く: 3.9ms | 1回あたり 0.197us | バケット 262144 | 最長鎖 5
線形探索の328.90us(10万件)が、0.197us になりました。 桁で言うと3桁違います。
そして、もっと大事なのは「1回あたり」が横一直線なことです。件数を10倍にしても、0.167 → 0.197 とほとんど変わっていません。線形探索は10倍になったのに、こちらは変わらない。 これが O(1) です。 「最長鎖」の列も見てください。10万件入れても、一番混んでいるバケットでも5歩しか鎖がありません。だから件数に関係なく速いのです。
「速いけど答えは合っているのか」は、check で確かめられます。線形探索の check と、ここで sum を出せば一致します(次の⑥でまとめて突き合わせます)。
④ 衝突を扱う — 違うキーが同じバケットに来る
_idx は「ハッシュ値をバケット数で割った余り」でした。違うキーでも、余りが同じになれば、同じバケットに来ます。 これが衝突です。事故ではなく、必ず起きます。
目で見ます。
語 | fnv1a(32bit) | &7(バケット8個での置き場所)
apple | 280767167 | 7
banana | 3649609552 | 0
cherry | 1232791672 | 0
grape | 2893541840 | 0
lemon | 3368108496 | 0
melon | 1927437660 | 4
peach | 2698319462 | 6
plum | 3064836203 | 3
---
バケット0: lemon -> grape -> cherry -> banana
バケット3: plum
バケット4: melon
バケット6: peach
バケット7: apple
最長の鎖: 4 歩
バケットが8個だと、banana cherry grape lemon の4つが、全部0番に来ました。 これを解くのがチェイン法——同じバケットに来たものを、鎖(連結リスト)でつなぐやり方です。set の this.buckets[i] = { k, v, next: this.buckets[i] } が、新しいノードを鎖の先頭につないでいる行です。
衝突そのものは、バグでも失敗でもありません。 バケットが有限である以上、キーが増えれば必ず起きます。問題になるのは「鎖が長くなりすぎたとき」だけです。だから対策は「衝突をゼロにする」ではなく、「鎖が短いうちに、バケットを増やす」——次に見るリサイズです。バケットが8個しかないから4つも重なったのであって、②③のように十分な数のバケットがあれば、鎖はほとんど1〜2歩に収まります。
[スクリーンショット: 02_collision.png] node 03-collision.mjs の出力を撮ってください。&7 の列で複数の語が同じ 0 に来ていて、下の「バケット0」に4つが鎖でつながっているのが見えるようにしてください。
鎖が長くなると、O(1) は O(n) に落ちる
衝突が増えて鎖が長くなると、get は「鎖をたどる」歩数が増えます。 極端に、バケットを1個に潰すと、全部が1本の鎖になり、ただの線形探索に戻ります。それを測ります。ついでに、10万件を普通に入れたときリサイズが何回起きたかも見ます。
10万件を入れた結果:
最終バケット数: 262144
拡張(リサイズ)の回数: 15 回
最終の負荷率: 0.381
一番長い鎖: 5 歩
---
バケット 1 | 最長鎖 20000 | 5,000回引く 312.7ms (check 50250105)
バケット 16384 | 最長鎖 7 | 5,000回引く 0.8ms (check 50250105)
2つ、はっきり見えます。
- リサイズは15回起きて、最終的にバケットは262144個になりました。負荷率は0.381に保たれ、最長鎖は5歩。「負荷率が0.75を超えたら2倍にする」を繰り返した結果です
- バケットを1個に潰すと、最長鎖が20000歩、引く時間は312.7ms。 これは②の線形探索とほぼ同じ遅さです。バケット16384なら0.8ms
「O(1)だから速い」は、無条件ではありません。 バケットが足りず衝突だらけになると、鎖が伸びて O(n) に戻ります。
checkが両方 50250105 で一致しているとおり、答えは同じで、速さだけが3桁違う——これが「同じ問題でも、持ち方で速さが変わる」の実物です。 だからsetの中にリサイズがあります。件数が増えたら、バケットも増やす。「たまに重いリサイズ」を払ってでも、普段のgetを速く保つ——ハッシュ表の回で「償却でならすと O(1)」と書いた、あれの中身です。
なぜ拡張の合図を「負荷率0.75」にしたのかも、天秤の話です。しきい値を高くする(例:2.0まで我慢する)と、バケットは少なくて済むがメモリは節約できる代わりに、鎖が長くなって get が遅くなります。 低くする(例:0.25で拡張)と、鎖は短く速くなるが、バケットの配列がスカスカでメモリを食い、リサイズも頻発します。 0.75前後は、多くのハッシュ表が採用している「速さとメモリのちょうどいい妥協点」です。私の測定でも、10万件で負荷率0.381・最長鎖5歩という、十分に散った状態に収まりました。
⑤ LRUで、容量を超えたら捨てる
ここまでの HashIndex は、入れたものを永久に持ち続けます。 現実のキャッシュはそうはいきません。メモリは有限なので、容量を決めて、あふれたら何かを捨てる必要があります。
捨て方はヒープとキャッシュの回でやった LRU——「最後に使われたのが一番古いもの」から捨てる——を使います。
問題は「一番古いものを、どうやって速く見つけるか」でした。全部を見て回ると O(n) です。答えは、
「使った順」に並んだ双方向連結リストを持っておく。一番古いものは、必ず末尾にいる。探さない。
でした。なぜ双方向(前と次の両方を持つ)か——リストの真ん中にあるノードを O(1) で抜きたいからです(配列と連結リストの回)。前へのポインタがあるから、その場で抜けます。
この「ハッシュ索引」と「双方向連結リスト」を、1つのクラスに合体させます。 これが到達作品の本体です。
1つのノードが、hnext(ハッシュの鎖)と prev/next(LRUのリスト)の両方を持っているのが要点です。
get—_findでハッシュから一発で引き(③の速さ)、見つけたら_toFrontでリストの先頭へ移す(「最近使った」印)setの追い出し —this.tail.prev(末尾=最古)を、リストからもハッシュからも抜く。探していません
head と tail の2つの番兵(値を持たないダミー)を置くと、「先頭を抜くとき」「末尾を抜くとき」「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
LRUの動きが、そのまま見えています。
A B Cを入れた直後、新しい順はC B A。一番古いのは A- そこで
get('A')すると、Aが先頭へ移る(A C B)。一番古いのは B になった set('D')で容量オーバー。捨てられたのは B。Aは直前に使ったので生き残った
「最後に使われたのが一番古いもの」を捨てる。これが LRU です。
ヒット率を測る — 容量を何%用意すればいいか
ここまでは「動くか」でした。キャッシュの本当の成績は、ヒット率です。現実のアクセスは一部のキーに集中します(人気記事だけがよく読まれる)。それに近い、偏ったアクセス列を作って、容量を変えながらヒット率を測ります。
キー総数 10000 / アクセス 200,000 回(人気キーに集中)
容量 | 全体比 | ヒット率 | 追い出し回数
50 | 1% | 30.9% | 138,235
100 | 1% | 38.9% | 122,044
200 | 2% | 47.2% | 105,498
500 | 5% | 58.4% | 82,781
1000 | 10% | 67.2% | 64,571
2000 | 20% | 76.4% | 45,207
5000 | 50% | 88.5% | 17,955
表を、縦に読んでください。
- 容量が全体の1%(50件)でも、ヒット率は30.9%。1万件のうち50件しか持っていないのに、3回に1回は当たっています。アクセスが人気キーに偏っているからです
- 容量を10%(1000件)にすると67.2%、50%(5000件)で88.5%
- ただし、伸びは鈍っていきます。 1%→10%で+36ポイント、10%→50%(5倍)でも+21ポイントしか増えません
これが「キャッシュを何%用意するか」の判断材料です。 「全部持てば100%当たる」のは当たり前ですが、全部持てないからキャッシュなのです。 この表があると、「メモリを5倍にしても、ヒット率は21ポイントしか上がらない。なら容量10%で十分」という判断が、勘ではなく数字でできます。 追い出し回数の列も見てください。容量が小さいほど、しょっちゅう捨てて入れ直しています(138,235回)。この「捨てて入れ直す」1回1回が、④で作ったハッシュの抜き差しです。 それでも全体が速いのは、抜き差しが O(1) だからです。
実は Map なら10行で書ける — でも自作した理由
ここまで、ハッシュ索引と双方向連結リストを合わせて50行ほど書きました。正直に打ち明けます。JavaScript には抜け道があります。
JavaScript の
Mapは、キーの挿入順を保ちます。 つまりMap自体が、すでに『順序付きのリスト』を内側に持っています。 それを使えば、連結リストを自分で書く必要がありません。
Map のこの性質は仕様で決まっています(MDN の Map)。それを使うと、LRUはこれだけになります。
古い→新しい: A B C
get(A) 後 : B C A
set(D) 後 : C A D (Bが消えた)
---
容量 200 | 自作MiniKV 47.2% | Map版 47.2% | 一致 true
容量 1000 | 自作MiniKV 67.2% | Map版 67.2% | 一致 true
要は、この2行です。
this.m.delete(k); // いったん消す
this.m.set(k, v); // 入れ直すと、挿入順の末尾に来る
「使ったキーを最新にする」を、delete してから set で実現しています。そして一番古いキーは this.m.keys().next().value、つまりイテレータの1個目です。下の表を見てください。 自作した MiniKV と、この10行の MapKV は、同じアクセス列でヒット率が完全に一致しました(47.2%、67.2%)。⑤の表の数字と同じです。
では、なぜ50行の自作版を書いたのか。 実務なら、私は迷わず
Map版を選びます。10行のほうがバグが入りません。 でも、Map版を先に見せられていたら、私は何も分からなかったはずです。 「Mapの挿入順を使えばLRUになる」と言われて、なぜ挿入順が保たれているのか、なぜdelete+setで最新になるのかを、説明できません。 自作版の価値は、速さでも短さでもなく、『Mapの中で何が起きているか』が分かることです。Mapは、まさに私が④⑤で書いた「ハッシュ索引+順序付きリスト」を、内部で持っています。一度自分で書いたから、Mapが信用できる。 これが、深掘りで手を動かす意味です。
この作品は、Redisのどこまで本物か
Redisの回で設定した、あの1行を思い出してください。
maxmemory 100mb
maxmemory-policy allkeys-lru
この2行目が、いま作った MiniKV の capacity と追い出しそのものです。 maxmemory が「容量」、allkeys-lru が「あふれたらLRUで捨てる」。呪文ではなくなりました。
ただし、正直に線引きします。本物のRedisは、いくつかの点で私の MiniKV より賢いです。
| 項目 | 私の MiniKV | 本物のRedis |
|---|---|---|
| 追い出し方 | LRU 固定 | LRU / LFU / random / TTL付き など、設定で選べる |
| LRUの正確さ | 完全なLRU(毎回リストを更新) | 近似LRU。全部を毎回並べ替えるのは重いので、標本を見て「だいたい古いもの」を捨てる |
| 容量の測り方 | 件数 | バイト数(値の大きさもみる) |
| 持続 | メモリだけ。プロセスが死ぬと消える | ディスクに保存でき、再起動で戻せる |
「近似LRU」に注目してください。 Redisは、完全なLRUは重すぎるので、あえて手を抜いています。 私の
MiniKVは毎回リストを付け替えて厳密にLRUを守りますが、件数が莫大になるとその付け替え自体が積もります。 だからRedisは「標本を数件見て、その中で一番古いものを捨てる」で妥協しています。厳密さより、全体の速さを取ったわけです。 これは、④のリサイズと同じ発想です。 「完璧」より「ならして速い」。中身を自分で書いたから、この妥協の意味が分かる——それが、この作品でRedisに近づけた距離です。
⑥ 計測でまとめる — 予想と実測が一致する
このコースの到達点は、ここです。 「O記法で予想したこと」と「実測の数字」を、1枚の表で突き合わせます。
②の線形探索と、④⑤の自作KVを、同じキー・同じ引き方で並べます。線形探索の遅さは②で、自作KVの速さは③で測りました。両方を「1回あたり(マイクロ秒)」で並べると、こうなります(自作KVの get は、容量を全件ぶんにして追い出しが起きない状態で測っています)。
| 件数 | 線形探索 get | 自作KV get | 速さの差 | O記法の予想 |
|---|---|---|---|---|
| 10,000 | 31.07us | 0.149us | 約208倍 | 線形=O(n) / KV=O(1) |
| 50,000 | 150.83us | 0.673us | 約224倍 | 同上 |
| 100,000 | 328.90us | 0.715us | 約460倍 | 同上 |
縦に読むと、予想がそのまま出ています。
- 線形探索の列:31 → 150 → 328。件数10倍で、時間もほぼ10倍。O(n) の予想どおり
- 自作KVの列:0.149 → 0.673 → 0.715。件数を10倍にしても、時間はほとんど変わらない。O(1) の予想どおり
- だから「速さの差」は、件数が増えるほど開きます(208倍 → 460倍)。これは「KVが速くなった」のではなく、線形探索だけが件数ぶん遅くなっているからです
自作KVの数字は、次のスクリプトで測れます(線形と同居させるとメモリを取り合って数字が揺れるので、KV単独で回数を増やして測ります)。
件数 10000 | 1回あたり 0.149us (200,000回で 29.9ms)
件数 50000 | 1回あたり 0.673us (200,000回で 134.6ms)
件数 100000 | 1回あたり 0.715us (200,000回で 143.0ms)
正直に、1つ補足します。自作KVの get は、③の「ハッシュ索引だけ」の版(0.197us)より、少し遅くなっています(10万件で0.715us)。理由ははっきりしていて、get のたびに「使った印」としてノードをリストの先頭へ付け替えているからです。LRUを守る以上、この付け替えは避けられません。それでも、件数を10倍にしても一定という性質(O(1))は保たれています。 「LRUの管理ぶん、定数倍だけ重い」——これも、測ったから言えることです。
これが、このコースでやりたかったことの全部です。 「計算量は理屈だけの話」ではありません。紙の上で O(n) と O(1) と予想したものが、VMの中で走らせると、本当にその通りの数字になる。 線形探索は件数ぶん遅くなり、ハッシュ索引は件数に関係なく一定。理屈と実測が一致する——これを自分の手で確かめられたら、このコースは終わりです。
[スクリーンショット: 03_measure.png] node 07-kvget.mjs の出力を撮ってください。「1回あたり」が 0.149 → 0.673 → 0.715 と、件数10倍でもほとんど動かないところが、O(1) の実物です。
速いだけでは意味がない — 答えが一致することを確かめる
「速いけど答えが違う」では、この作品は失敗です。 最後に、線形探索と自作KVが同じ答えを返すことを、機械で突き合わせます。
50,000回 + 存在しない3件を突き合わせ
答えが食い違った回数: 0
線形探索と自作KVは同じ答えを返すか: true
速さの実験でいちばん危ないのは、「速いけど間違っている実装」に気づかないことです。 自作KVは、線形探索より3桁速い。でも、その速さは「答えが同じ」でなければ、ただのバグです。 存在しないキーで両方
undefinedを返すことまで含めて、5万回すべて一致しました。これで初めて、⑥の速さの表を信用できます。「速い」の前に「正しい」を確かめる——順番はいつもこれです。
⑦ 完成の判定
この回の到達を、チェックリストで確かめます。全部にチェックが付けば、コンピュータ科学深掘りコースの到達作品は完成です。
- [ ] 線形探索の版を書き、10万件で1回引くのに何マイクロ秒かかるかを実測できた(そして件数10倍で時間もほぼ10倍=O(n) を目で見た)
- [ ] ハッシュ索引を自作し、線形探索より桁違いに速く、しかも件数を増やしても一定(O(1))であることを測れた
- [ ] 衝突を鎖(チェイン法)で扱え、負荷率とリサイズを実装できた
- [ ] バケットを1個に潰すと O(1) が O(n) に落ちることを、
checkの一致つきで確かめられた - [ ] ハッシュ索引と双方向連結リストを1つにまとめ、容量を超えたらLRUで捨てる
MiniKVを作れた - [ ] 偏ったアクセス列で、容量を変えながらヒット率を表にできた
- [ ] 「O記法の予想」と「実測の数字」が一致することを、1枚の表で確認できた
全部を、ライブラリなしで、自分の手で書きました。 Map も Redis も使っていません(⑤の近道で Map 版も比べましたが、本体の MiniKV は素の配列と参照だけです)。使ったのは配列と、ノードをつなぐ参照だけです。
~/cslab/kv/ に、こういうファイルが並んでいるはずです。この一式が「作品」です。
01-linear.mjs 03-collision.mjs 05-lru-demo.mjs 07-kvget.mjs hashindex.mjs rnd.mjs
02-hash.mjs 04-resize.mjs 06-hitrate.mjs 08-map-lru.mjs 09-verify.mjs minikv.mjs
| ファイル | 役割 |
|---|---|
rnd.mjs | 毎回同じ乱数列を出す(測定を再現する) |
hashindex.mjs | ハッシュ関数と、ハッシュ索引(③④) |
minikv.mjs | 本体。 ハッシュ索引+LRUの合わせ技(⑤) |
01〜09 | 各節の実験と計測 |
番号付きの実験ファイルは、消しても構いません。 残す価値があるのは
hashindex.mjsとminikv.mjsの2つです。「一発で引けて、容量を守るKVストア」が、この2ファイル・約100行に収まっている——これが、コンピュータ科学を深掘りした手ごたえです。
つまずいたところ
そのまま書きます。
| 症状 | 原因 |
|---|---|
| 速い版が「速いのに答えが違う」 | 最初、get が見つからないと 0 を返す実装にしていて、sum が線形版とずれました。undefined を返すよう直し、check が両方一致するまで信用しないことにしました |
| 10万件のベンチが、線形版と同居させると遅くなったり速くなったりした | 2つのストアを同じプロセスに置くと、メモリを取り合って数字が揺れました。⑥で自作KVを単独プロセスで測り直したら安定しました。測定はプロセスを分ける |
バケットを1個にした版が、get で無限に近く遅い | これは想定どおりでした。1本の鎖に2万件つながる=ただの線形探索です。「O(1) は無条件ではない」を示すために、わざと残しました |
リサイズを入れたら、たまに set が急に重くなった | リサイズはその1回だけ全件を置き直すので重い。普段の set を速く保つための代償です。1件あたりでならすと安い(償却) |
| LRUで、容量1件のとき番兵まわりが壊れた | 最初、番兵を置かず「先頭・末尾・1件」で場合分けしていて、1件のときにリストが輪になりました。head/tail の番兵を置いたら分岐が全部消えました |
追い出したはずのキーが、get でまだ返ってきた | LRUのリストからは抜いたのに、ハッシュの鎖から抜き忘れていました。 MiniKV が2つの構造を持つ以上、捨てるときは両方から抜く。_hashRemove を足して直りました |
fnv1a の結果がマイナスになった | JavaScript のビット演算は符号あり32bitなので、最上位ビットが立つと負になります。>>> 0 で符号なしに直すのを忘れていました |
| ヒット率がやけに高く出た | 最初、アクセス列を一様乱数で作っていて「偏り」が無く、逆に容量が小さいとヒット率が異常に低く出ました。現実に近い偏り(Zipfっぽい列)にしたら、表が素直な形になりました |
今回いちばん助けられたのは
check(合計値の突き合わせ)でした。 速さの実験は、速いけど間違っている実装に気づけないと意味がありません。「答えが一致していること」を毎回機械で確かめる——速さの実験ほど、この確認が要ります。
後片づけ
この記事のために作ったものを、全部消します。
確認します。
消えました
~/cslab/ごと消したい場合はrm -rf ~/cslabです。ただし、このコースの他の回(~/cslab/hashなど)も一緒に消えます。 残したい回があるなら、~/cslab/kvだけを消してください。rm -rfは戻せないので、打つ前にパスをもう一度見る習慣を。
まとめ — 理解できたこと
- KVストアの命は「一発で引けること」。
Mapも Redis も、いちばん底ではこれをやっている。中身を自分で書くと、速さが魔法でなくなる - 線形探索は O(n)。 配列に持って
findで探すと、件数10倍で引く時間もほぼ10倍(31 → 150 → 328us)。何もしていないのに、件数が増えるだけで遅くなる - ハッシュ索引は「探さずに、置き場所を計算する」。 キーを数字(FNV-1a)にして、バケット数で割った余りが置き場所。だから件数に関係なく一定(O(1))
- 衝突は事故ではなく、必ず起きる。 違うキーの余りが同じになれば同じバケットに来る。チェイン法(鎖でつなぐ)で解く
- O(1) は無条件ではない。 バケットが足りず鎖が伸びると O(n) に戻る。バケット1個の版は、線形探索と同じ312.7msに落ちた
- リサイズは「たまの重さ」で「普段の速さ」を買う取引。 10万件で15回起き、負荷率を0.381に保った。1件あたりでならすと安い(償却)
- 容量が有限だと「何を捨てるか」を決めないといけない。 それがLRU。最後に使われたのが一番古いものから捨てる
- 一番古いものを速く見つけるには、「使った順」の双方向連結リストを持つ。 末尾が最古。探さない。真ん中を O(1) で抜くために双方向にする
- 到達作品は「ハッシュ索引+双方向連結リスト」の合わせ技。 1つのノードが両方に所属し、ハッシュからは「どこか」、リストからは「新しい順」で辿れる
- キャッシュは大きいほど得だが、伸びは鈍る。 キー1万件に対し、容量1%で30.9%、10%で67.2%、50%で88.5%。全部持たなくても、人気キーだけで大半が当たる
- 「捨てるときは、持っている全部の構造から抜く」。 LRUのリストとハッシュの鎖、両方から抜かないと、消したはずのキーが返ってくる
- O記法の予想は、実測の数字と一致する。 線形はO(n)どおり件数ぶん遅くなり、KVはO(1)どおり一定。理屈と実測が合うのを自分の手で確かめた——これがこのコースの到達点
- RedisやMapの中で起きているのは、いま自分で書いたものと同じ。
maxmemory-policy allkeys-lruの1行が、呪文でなくなった - 道具の中身が分かると、いつ使うべきか判断できる。 「とりあえず配列」で困る境目が、件数で言えるようになる。これが、深掘りコースを1本ずつ書いてきた理由
バラバラだった知識が、1つの動く道具の中で協力する形を、自分の手で見られました。 計算量も、ハッシュも、連結リストも、LRUも、別々の話ではなかった——それを確かめるのが、この到達作品でした。
ここから先、Map や Redis を使うとき、あなたはもう中身を知っています。 速い理由も、壊れる条件も、いつ使うべきかも。道具を「信じて使う」から「分かって選ぶ」へ——コンピュータ科学を深掘りした意味は、そこにあります。
参考リンク
- roadmap.sh — Computer Science
- MDN — Map
- MDN — Math.imul()
- MDN — ビット論理積 (&)
- MDN — Array.prototype.find()
- MDN — Performance.now()
- Node.js — Performance measurement APIs (perf_hooks)
この段階の確認
【深掘り】コンピュータ科学 は、ここで終わりです。 次に進む前に、答えを見ずに試してください。
読み終えた直後は、たいてい「分かった気」になっています。 手が動くかどうかは別です。
説明できますか
- データが10倍で100倍遅くなるのはなぜか。O記法で言えますか
0.1 + 0.2が0.3にならないのはなぜか- 配列の先頭への追加が数百倍遅いのはなぜか
手が動きますか
- 同じ処理を2通りで書き、実際に時間を測って比べる
includesで止まるコードを、ハッシュテーブルで書き直す- 再帰にメモ化を1行足し、一瞬で終わることを確かめる
1つでも詰まったら、飛ばした回があります。 そこへ戻ってください。戻るのは後退ではありません。 戻り先の目安: 計算量とO記法の回 / 配列と連結リストの回 / ハッシュテーブルの回 / 再帰とメモ化の回
全部答えられたなら、次の段階へ進んでください。
次に読む
この記事は 【深掘り】コンピュータ科学 の 25 / 25 本目です。
| 記事 | |
|---|---|
| ← 前の記事 | スケールとアムダールの法則 — 状態を持つと台を増やせない |
ここが現時点の最後です。 続きは書き次第、はじめに のカリキュラムに並びます。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
【深掘り】コンピュータ科学の到達作品です。 ハッシュ索引と LRU を持つ KV ストアを自作し、線形探索との差を実測で確かめます。

コメント