自作KVストアで理屈を実測する — CSの到達作品

CSの到達作品。キーと値のカード、索引付きの収納とストップウォッチ。

計算量・探索・ハッシュ表・データ構造を、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つの合わせ技です。

この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行が、呪文でなくなる
  • 道具の中身が分かると、いつ使うべきかを自分で判断できること。「とりあえず配列」で困る境目が、件数で言えるようになる

この記事でやること

  1. ~/cslab/kv/ を作り、配列に持って線形探索する「遅いKVストア」を書いて、10万件で1回引く時間を実測する
  2. 文字列を数字にするハッシュ関数(FNV-1a)を書き、それを使ったハッシュ索引を自作して、線形探索とベンチする
  3. わざと衝突させて鎖を目で見て、負荷率とリサイズを実装し、バケットを1個に潰すと O(1) が O(n) に落ちるところを測る
  4. ハッシュ索引と双方向連結リストを1つにまとめ、容量を超えたらLRUで捨てる MiniKV を作る
  5. 人気キーに偏ったアクセス列を作り、容量を変えながらヒット率を表にする
  6. 線形探索と自作KVの get 時間を1枚の表に並べ、O記法の予想と実測が一致することを確かめる
  7. 完成をチェックリストで判定し、全部消す

先に知る言葉

基本的な言葉は用語集にもまとめてあります。ここではこの記事を読むのに必要な最小限だけ書きます。どれも、このコースの過去の回で一度は出てきた言葉です。

言葉1〜2行の説明
KVストアキー(名前)を渡すと値が返る入れ物。Key-Value。Map も Redis もこれ。「一発で引けること」が命
線形探索先頭から1つずつ順番に見て、目当てを探すこと。件数が増えるほど遅くなる(平均で半分見る)
ハッシュ関数文字列などを、決まった手順で数字に変える関数。同じ入力なら必ず同じ数字。ここでは置き場所を決めるために使う
バケットハッシュ値から決まる「置き場所」の1マス。配列の1要素だと思ってよい
衝突違うキーが同じバケットに来ること。事故ではなく必ず起きる。鎖(チェイン)でつないで解く
負荷率(ロードファクタ)入っている件数 ÷ バケット数。高いほど鎖が長くなり遅くなる。0.75あたりで拡張するのが定番
リサイズバケット数を増やして、全部のキーを置き直すこと。その1回は重いが、ならすと安い(償却)
LRULeast Recently Used。最後に使われたのが一番古いものから捨てる追い出し方
ヒット率聞かれたものがキャッシュに入っていた割合。ヒット ÷ (ヒット + ミス)。キャッシュの成績表
O(1) / O(n)中身の件数を n としたとき、処理時間が件数に左右されないのが O(1)、件数に比例するのが O(n)

① 何を作るか — 2つの部品を1つに束ねる

まず作業場所を作ります。VMの中で打ちます。

bash
$ mkdir -p ~/cslab/kv
$ cd ~/cslab/kv
$ node -v

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() だと実行のたびに違う数字になり、比べられなくなるからです。

bash
$ cat > rnd.mjs <<'EOF'
  // mulberry32 — 毎回同じ列が出る乱数(測定を再現できるようにするため)
  export function makeRnd(seed) {
    return function () {
      seed |= 0; seed = (seed + 0x6D2B79F5) | 0;
      let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
      t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
      return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
    };
  }
  EOF

中身の式は理解しなくて大丈夫です。「seed を渡すと、いつでも同じ乱数列を出す関数」が返るだけです。

次に、線形探索版のKVストアです。

bash
$ cat > 01-linear.mjs <<'EOF'
  import { makeRnd } from './rnd.mjs';
  
  // 配列に持って、キーで線形探索する版
  class LinearStore {
    constructor() { this.items = []; }
    set(k, v) {
      const it = this.items.find((x) => x.k === k);   // ここが O(n)
      if (it) { it.v = v; return; }
      this.items.push({ k, v });
    }
    get(k) {
      const it = this.items.find((x) => x.k === k);   // ここも O(n)
      return it ? it.v : undefined;
    }
  }
  
  const rnd = makeRnd(20261016);
  const M = 20_000;   // 何回引くか
  
  for (const N of [10_000, 50_000, 100_000]) {
    const store = new LinearStore();
    const keys = [];
    for (let i = 0; i < N; i++) {
      const k = 'user:' + i.toString().padStart(7, '0');
      keys.push(k);
      store.set(k, i);
    }
    // 実在するキーを M 回、ランダムに引く
    const asks = [];
    for (let i = 0; i < M; i++) asks.push(keys[Math.floor(rnd() * N)]);
  
    const t = performance.now();
    let sum = 0;
    for (let i = 0; i < M; i++) { const v = store.get(asks[i]); sum += v; }
    const ms = performance.now() - t;
    console.log(
      '件数' + String(N).padStart(7),
      '| ' + M.toLocaleString() + '回引く:', ms.toFixed(1).padStart(8) + 'ms',
      '| 1回あたり', ((ms * 1000) / M).toFixed(2).padStart(7) + 'us',
      '(check ' + sum + ')'
    );
  }
  EOF
$ node 01-linear.mjs

.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,00031.07us—
50,000150.83us約4.9倍(件数5倍)
100,000328.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 です。

bash
$ cat > hashindex.mjs <<'EOF'
  // hashindex.mjs — 自作のハッシュ索引(チェイン法 + リサイズ)
  export function fnv1a(str) {
    let h = 0x811c9dc5;                 // 決まった初期値
    for (let i = 0; i < str.length; i++) {
      h ^= str.charCodeAt(i);           // 1文字ずつ混ぜる
      h = Math.imul(h, 0x01000193);     // 素数を掛ける(32bit)
    }
    return h >>> 0;                     // 符号なし32bitに直す
  }
  
  export class HashIndex {
    constructor(cap = 8, loadLimit = 0.75) {
      this.cap = cap;                   // バケット数(2のべき乗)
      this.buckets = new Array(cap);
      this.count = 0;
      this.resizes = 0;
      this.loadLimit = loadLimit;       // この負荷率を超えたら拡張。0で拡張しない
    }
    _idx(k) { return fnv1a(k) & (this.cap - 1); }   // 余り = 下位ビット
  
    set(k, v) {
      const i = this._idx(k);
      let node = this.buckets[i];
      while (node) {                    // 同じバケットの鎖をたどる
        if (node.k === k) { node.v = v; return; }
        node = node.next;
      }
      this.buckets[i] = { k, v, next: this.buckets[i] };   // 先頭に足す
      this.count++;
      if (this.loadLimit && this.count > this.cap * this.loadLimit) this._resize();
    }
    get(k) {
      let node = this.buckets[this._idx(k)];
      while (node) {                    // 鎖をたどる(普通は1〜2歩)
        if (node.k === k) return node.v;
        node = node.next;
      }
      return undefined;
    }
    _resize() {
      const old = this.buckets;
      this.cap *= 2;
      this.buckets = new Array(this.cap);
      for (let b of old) {
        while (b) {
          const next = b.next;
          const i = this._idx(b.k);     // 新しいバケット数で置き直す
          b.next = this.buckets[i];
          this.buckets[i] = b;
          b = next;
        }
      }
      this.resizes++;
    }
    loadFactor() { return this.count / this.cap; }
    longestChain() {
      let max = 0;
      for (const b of this.buckets) {
        let n = 0, node = b;
        while (node) { n++; node = node.next; }
        if (n > max) max = n;
      }
      return max;
    }
  }
  EOF

長く見えますが、要点は3つだけです。

  • fnv1a — 文字列を1文字ずつ「掛けて混ぜる」だけ。Math.imul は32bit整数としての掛け算で、あふれを気にせず混ぜられます。同じ文字列なら、必ず同じ数字が出ます
  • _idx — ハッシュ値をバケット数で割った余りが、置き場所。バケット数を2のべき乗にしてあるので、& (cap - 1) が余りと同じになります(速い)
  • set / get — 計算した置き場所を、いきなり見る。探す作業が無い

同じ条件で、線形探索と同じベンチを回します。

bash
$ cat > 02-hash.mjs <<'EOF'
  import { makeRnd } from './rnd.mjs';
  import { HashIndex } from './hashindex.mjs';
  
  const rnd = makeRnd(20261016);
  const M = 20_000;
  
  for (const N of [10_000, 50_000, 100_000]) {
    const store = new HashIndex();
    const keys = [];
    for (let i = 0; i < N; i++) {
      const k = 'user:' + i.toString().padStart(7, '0');
      keys.push(k);
      store.set(k, i);
    }
    const asks = [];
    for (let i = 0; i < M; i++) asks.push(keys[Math.floor(rnd() * N)]);
  
    const t = performance.now();
    let sum = 0;
    for (let i = 0; i < M; i++) { const v = store.get(asks[i]); sum += v; }
    const ms = performance.now() - t;
    console.log(
      '件数' + String(N).padStart(7),
      '| ' + M.toLocaleString() + '回引く:', ms.toFixed(1).padStart(6) + 'ms',
      '| 1回あたり', ((ms * 1000) / M).toFixed(3).padStart(6) + 'us',
      '| バケット', String(store.cap).padStart(7),
      '| 最長鎖', store.longestChain()
    );
  }
  EOF
$ node 02-hash.mjs
件数  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 は「ハッシュ値をバケット数で割った余り」でした。違うキーでも、余りが同じになれば、同じバケットに来ます。 これが衝突です。事故ではなく、必ず起きます。

目で見ます。

bash
$ cat > 03-collision.mjs <<'EOF'
  import { fnv1a, HashIndex } from './hashindex.mjs';
  
  const words = ['apple', 'banana', 'cherry', 'grape', 'lemon', 'melon', 'peach', 'plum'];
  console.log('語     | fnv1a(32bit)  | &7(バケット8個での置き場所)');
  for (const w of words) {
    const h = fnv1a(w);
    console.log(w.padEnd(6), '|', String(h).padStart(12), '|', h & 7);
  }
  
  // バケット8個・拡張しない設定で、鎖を目で見る
  console.log('---');
  const h = new HashIndex(8, 0);          // loadLimit=0 → 拡張しない
  for (const w of words) h.set(w, w.length);
  h.buckets.forEach((b, i) => {
    const chain = [];
    for (let n = b; n; n = n.next) chain.push(n.k);
    console.log('バケット' + i + ':', chain.length ? chain.join(' -> ') : '(空)');
  });
  console.log('最長の鎖:', h.longestChain(), '歩');
  EOF
$ node 03-collision.mjs
語     | 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万件を普通に入れたときリサイズが何回起きたかも見ます。

bash
$ cat > 04-resize.mjs <<'EOF'
  import { makeRnd } from './rnd.mjs';
  import { HashIndex } from './hashindex.mjs';
  
  // (1) 10万件入れる間に、拡張が何回起きたか
  const store = new HashIndex(8);
  const N = 100_000;
  for (let i = 0; i < N; i++) store.set('user:' + i.toString().padStart(7, '0'), i);
  console.log('10万件を入れた結果:');
  console.log('  最終バケット数:', store.cap);
  console.log('  拡張(リサイズ)の回数:', store.resizes, '回');
  console.log('  最終の負荷率:', store.loadFactor().toFixed(3));
  console.log('  一番長い鎖:', store.longestChain(), '歩');
  
  // (2) わざとバケットを増やさないと、O(1) は O(n) に落ちる
  console.log('---');
  const rnd = makeRnd(42);
  const M = 5_000;
  for (const cap of [1, 16384]) {
    const s = new HashIndex(cap, 0);      // 拡張しない
    const keys = [];
    for (let i = 0; i < 20_000; i++) {
      const k = 'user:' + i.toString().padStart(7, '0');
      keys.push(k); s.set(k, i);
    }
    const asks = [];
    for (let i = 0; i < M; i++) asks.push(keys[Math.floor(rnd() * keys.length)]);
    const t = performance.now();
    let sum = 0;
    for (let i = 0; i < M; i++) sum += s.get(asks[i]);
    const ms = performance.now() - t;
    console.log(
      'バケット' + String(cap).padStart(6),
      '| 最長鎖', String(s.longestChain()).padStart(6),
      '|', M.toLocaleString() + '回引く', ms.toFixed(1).padStart(8) + 'ms',
      '(check ' + sum + ')'
    );
  }
  EOF
$ node 04-resize.mjs
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つのクラスに合体させます。 これが到達作品の本体です。

bash
$ cat > minikv.mjs <<'EOF'
  // minikv.mjs — 自作KVストア。ハッシュ索引(一発で引く) + 双方向連結リスト(LRUで捨てる)
  import { fnv1a } from './hashindex.mjs';
  
  export class MiniKV {
    constructor(capacity, buckets = 1024) {
      this.capacity = capacity;         // 何件まで持つか(超えたらLRUで捨てる)
      this.cap = buckets;               // ハッシュのバケット数(2のべき乗)
      this.buckets = new Array(this.cap);
      this.size = 0;
      // LRU用の双方向リスト。head側が新しく、tail側が古い。両端は番兵
      this.head = { k: null };
      this.tail = { k: null };
      this.head.next = this.tail;
      this.tail.prev = this.head;
      this.hit = 0; this.miss = 0; this.evicted = 0;
    }
    _idx(k) { return fnv1a(k) & (this.cap - 1); }
    _find(k) {                          // バケットの鎖から探す
      let n = this.buckets[this._idx(k)];
      while (n) { if (n.k === k) return n; n = n.hnext; }
      return null;
    }
    _hashRemove(node) {                 // ハッシュの鎖から1つ抜く
      const i = this._idx(node.k);
      let n = this.buckets[i], prev = null;
      while (n) {
        if (n === node) {
          if (prev) prev.hnext = n.hnext; else this.buckets[i] = n.hnext;
          return;
        }
        prev = n; n = n.hnext;
      }
    }
    _unlink(n) { n.prev.next = n.next; n.next.prev = n.prev; }   // リストから抜く
    _toFront(n) {                       // リストの先頭(新しい側)へ
      n.next = this.head.next; n.prev = this.head;
      this.head.next.prev = n; this.head.next = n;
    }
  
    get(k) {
      const n = this._find(k);
      if (!n) { this.miss++; return undefined; }
      this.hit++;
      this._unlink(n); this._toFront(n);        // 使ったので先頭へ
      return n.v;
    }
    set(k, v) {
      let n = this._find(k);
      if (n) { n.v = v; this._unlink(n); this._toFront(n); return; }
      if (this.size >= this.capacity) {          // 容量オーバー → 一番古いのを捨てる
        const old = this.tail.prev;              // 末尾=最古。探さない
        this._unlink(old);
        this._hashRemove(old);
        this.size--;
        this.evicted++;
      }
      n = { k, v };
      const i = this._idx(k);
      n.hnext = this.buckets[i];                 // ハッシュに登録
      this.buckets[i] = n;
      this._toFront(n);                          // リストの先頭に登録
      this.size++;
    }
    keysNewToOld() {
      const out = [];
      for (let n = this.head.next; n !== this.tail; n = n.next) out.push(n.k);
      return out;
    }
    hitRate() {
      const t = this.hit + this.miss;
      return t === 0 ? 0 : this.hit / t;
    }
  }
  EOF

1つのノードが、hnext(ハッシュの鎖)と prev/next(LRUのリスト)の両方を持っているのが要点です。

  • get — _find でハッシュから一発で引き(③の速さ)、見つけたら _toFront でリストの先頭へ移す(「最近使った」印)
  • set の追い出し — this.tail.prev(末尾=最古)を、リストからもハッシュからも抜く。探していません

head と tail の2つの番兵(値を持たないダミー)を置くと、「先頭を抜くとき」「末尾を抜くとき」「1件のとき」の場合分けが全部消えます。まず動きを目で見ます。

bash
$ cat > 05-lru-demo.mjs <<'EOF'
  import { MiniKV } from './minikv.mjs';
  
  const kv = new MiniKV(3);               // 3件しか持てないKVストア
  kv.set('A', 1); kv.set('B', 2); kv.set('C', 3);
  console.log('新しい→古い:', kv.keysNewToOld().join(' '));
  console.log('get(A) =', kv.get('A'), '→', kv.keysNewToOld().join(' '));
  kv.set('D', 4);
  console.log('set(D)(容量オーバー)→ 捨てたのは B。中身:', kv.keysNewToOld().join(' '));
  console.log('get(B) =', kv.get('B'), '(もう無い)');
  console.log('hit=' + kv.hit, 'miss=' + kv.miss, 'evicted=' + kv.evicted);
  EOF
$ node 05-lru-demo.mjs
新しい→古い: 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 です。

ヒット率を測る — 容量を何%用意すればいいか

ここまでは「動くか」でした。キャッシュの本当の成績は、ヒット率です。現実のアクセスは一部のキーに集中します(人気記事だけがよく読まれる)。それに近い、偏ったアクセス列を作って、容量を変えながらヒット率を測ります。

bash
$ cat > 06-hitrate.mjs <<'EOF'
  import { makeRnd } from './rnd.mjs';
  import { MiniKV } from './minikv.mjs';
  
  // 現実のアクセスは偏る(人気キーに集中)。Zipfっぽいアクセス列を作る
  const rnd = makeRnd(20261016);
  const UNIVERSE = 10_000;   // キーの総数
  const OPS = 200_000;       // アクセス回数
  
  // ランクrのキーが選ばれる確率 ∝ 1/r。累積表からサンプリング
  const weights = [];
  let total = 0;
  for (let r = 1; r <= UNIVERSE; r++) { total += 1 / r; weights.push(total); }
  function pick() {
    const x = rnd() * total;
    let lo = 0, hi = UNIVERSE - 1;
    while (lo < hi) { const mid = (lo + hi) >> 1; if (weights[mid] < x) lo = mid + 1; else hi = mid; }
    return 'key:' + lo;
  }
  const stream = [];
  for (let i = 0; i < OPS; i++) stream.push(pick());
  
  console.log('キー総数 ' + UNIVERSE + ' / アクセス ' + OPS.toLocaleString() + ' 回(人気キーに集中)');
  console.log('容量 | 全体比 | ヒット率 | 追い出し回数');
  for (const cap of [50, 100, 200, 500, 1000, 2000, 5000]) {
    const kv = new MiniKV(cap, 16384);
    for (let i = 0; i < OPS; i++) {
      const k = stream[i];
      if (kv.get(k) === undefined) kv.set(k, i);   // 無ければ取ってきて入れる想定
    }
    console.log(
      String(cap).padStart(4),
      '|', (cap * 100 / UNIVERSE).toFixed(0).padStart(4) + '%',
      '|', (kv.hitRate() * 100).toFixed(1).padStart(6) + '%',
      '|', kv.evicted.toLocaleString().padStart(9)
    );
  }
  EOF
$ node 06-hitrate.mjs
キー総数 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はこれだけになります。

bash
$ cat > 08-map-lru.mjs <<'EOF'
  import { makeRnd } from './rnd.mjs';
  import { MiniKV } from './minikv.mjs';
  
  // Map は挿入順を保つ。それだけで LRU になる(連結リストを自分で書かなくていい)
  class MapKV {
    constructor(cap) { this.cap = cap; this.m = new Map(); this.hit = 0; this.miss = 0; }
    get(k) {
      if (!this.m.has(k)) { this.miss++; return undefined; }
      this.hit++;
      const v = this.m.get(k);
      this.m.delete(k);        // いったん消して
      this.m.set(k, v);        // 入れ直す → 挿入順の末尾(=最新)になる
      return v;
    }
    set(k, v) {
      if (this.m.has(k)) this.m.delete(k);
      else if (this.m.size >= this.cap) this.m.delete(this.m.keys().next().value); // 先頭=最古
      this.m.set(k, v);
    }
  }
  
  // (1) 動きが MiniKV と同じか、目で見る
  const c = new MapKV(3);
  c.set('A', 1); c.set('B', 2); c.set('C', 3);
  console.log('古い→新しい:', [...c.m.keys()].join(' '));
  c.get('A');
  console.log('get(A) 後   :', [...c.m.keys()].join(' '));
  c.set('D', 4);
  console.log('set(D) 後   :', [...c.m.keys()].join(' '), '(Bが消えた)');
  
  // (2) 偏ったアクセスで、ヒット率が MiniKV と一致するか
  console.log('---');
  const rnd = makeRnd(20261016);
  const UNIVERSE = 10_000, OPS = 200_000;
  const weights = []; let total = 0;
  for (let r = 1; r <= UNIVERSE; r++) { total += 1 / r; weights.push(total); }
  function pick() {
    const x = rnd() * total; let lo = 0, hi = UNIVERSE - 1;
    while (lo < hi) { const mid = (lo + hi) >> 1; if (weights[mid] < x) lo = mid + 1; else hi = mid; }
    return 'key:' + lo;
  }
  const stream = []; for (let i = 0; i < OPS; i++) stream.push(pick());
  
  for (const cap of [200, 1000]) {
    const a = new MiniKV(cap, 16384), b = new MapKV(cap);
    for (let i = 0; i < OPS; i++) { if (a.get(stream[i]) === undefined) a.set(stream[i], i); }
    for (let i = 0; i < OPS; i++) { if (b.get(stream[i]) === undefined) b.set(stream[i], i); }
    const ra = (a.hit / (a.hit + a.miss) * 100).toFixed(1);
    const rb = (b.hit / (b.hit + b.miss) * 100).toFixed(1);
    console.log('容量' + String(cap).padStart(5), '| 自作MiniKV', ra + '%', '| Map版', rb + '%', '| 一致', ra === rb);
  }
  EOF
$ node 08-map-lru.mjs
古い→新しい: 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,00031.07us0.149us約208倍線形=O(n) / KV=O(1)
50,000150.83us0.673us約224倍同上
100,000328.90us0.715us約460倍同上

縦に読むと、予想がそのまま出ています。

  • 線形探索の列:31 → 150 → 328。件数10倍で、時間もほぼ10倍。O(n) の予想どおり
  • 自作KVの列:0.149 → 0.673 → 0.715。件数を10倍にしても、時間はほとんど変わらない。O(1) の予想どおり
  • だから「速さの差」は、件数が増えるほど開きます(208倍 → 460倍)。これは「KVが速くなった」のではなく、線形探索だけが件数ぶん遅くなっているからです

自作KVの数字は、次のスクリプトで測れます(線形と同居させるとメモリを取り合って数字が揺れるので、KV単独で回数を増やして測ります)。

bash
$ cat > 07-kvget.mjs <<'EOF'
  import { makeRnd } from './rnd.mjs';
  import { MiniKV } from './minikv.mjs';
  const rnd = makeRnd(20261016);
  const M = 200_000;   // 引く回数を増やして安定させる
  for (const N of [10_000, 50_000, 100_000]) {
    const kv = new MiniKV(N + 1, 16384);
    const keys = [];
    for (let i = 0; i < N; i++) { const k = 'user:' + i.toString().padStart(7, '0'); keys.push(k); kv.set(k, i); }
    const asks = [];
    for (let i = 0; i < M; i++) asks.push(keys[Math.floor(rnd() * N)]);
    let s = 0; const t = performance.now();
    for (let i = 0; i < M; i++) s += kv.get(asks[i]);
    const ms = performance.now() - t;
    console.log('件数' + String(N).padStart(7), '| 1回あたり', ((ms * 1000) / M).toFixed(3).padStart(6) + 'us', '(' + M.toLocaleString() + '回で ' + ms.toFixed(1) + 'ms)');
  }
  EOF
$ node 07-kvget.mjs
件数  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が同じ答えを返すことを、機械で突き合わせます。

bash
$ cat > 09-verify.mjs <<'EOF'
  import { makeRnd } from './rnd.mjs';
  import { MiniKV } from './minikv.mjs';
  
  class LinearStore {
    constructor() { this.items = []; }
    set(k, v) { const it = this.items.find((x) => x.k === k); if (it) { it.v = v; return; } this.items.push({ k, v }); }
    get(k) { const it = this.items.find((x) => x.k === k); return it ? it.v : undefined; }
  }
  
  const rnd = makeRnd(999);
  const N = 30_000, M = 50_000;
  const lin = new LinearStore();
  const kv = new MiniKV(N + 1, 16384);
  const keys = [];
  for (let i = 0; i < N; i++) { const k = 'id:' + i; keys.push(k); lin.set(k, i * 7); kv.set(k, i * 7); }
  
  let mismatch = 0;
  for (let i = 0; i < M; i++) {
    const k = keys[Math.floor(rnd() * N)];
    if (lin.get(k) !== kv.get(k)) mismatch++;
  }
  // 存在しないキーも同じく undefined を返すか
  const missKeys = ['id:-1', 'nope', 'id:999999'];
  for (const k of missKeys) if (lin.get(k) !== kv.get(k)) mismatch++;
  
  console.log(M.toLocaleString() + '回 + 存在しない3件を突き合わせ');
  console.log('答えが食い違った回数:', mismatch);
  console.log('線形探索と自作KVは同じ答えを返すか:', mismatch === 0);
  EOF
$ node 09-verify.mjs
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/ に、こういうファイルが並んでいるはずです。この一式が「作品」です。

bash
$ ls ~/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(合計値の突き合わせ)でした。 速さの実験は、速いけど間違っている実装に気づけないと意味がありません。「答えが一致していること」を毎回機械で確かめる——速さの実験ほど、この確認が要ります。

後片づけ

この記事のために作ったものを、全部消します。

bash
$ cd ~
$ rm -rf ~/cslab/kv

確認します。

bash
$ ls ~/cslab/kv 2>/dev/null || echo "消えました"
消えました

~/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 を使うとき、あなたはもう中身を知っています。 速い理由も、壊れる条件も、いつ使うべきかも。道具を「信じて使う」から「分かって選ぶ」へ——コンピュータ科学を深掘りした意味は、そこにあります。

参考リンク


この段階の確認

【深掘り】コンピュータ科学 は、ここで終わりです。 次に進む前に、答えを見ずに試してください。

読み終えた直後は、たいてい「分かった気」になっています。 手が動くかどうかは別です。

説明できますか

  1. データが10倍で100倍遅くなるのはなぜか。O記法で言えますか
  2. 0.1 + 0.2 が 0.3 にならないのはなぜか
  3. 配列の先頭への追加が数百倍遅いのはなぜか

手が動きますか

  • 同じ処理を2通りで書き、実際に時間を測って比べる
  • includes で止まるコードを、ハッシュテーブルで書き直す
  • 再帰にメモ化を1行足し、一瞬で終わることを確かめる

1つでも詰まったら、飛ばした回があります。 そこへ戻ってください。戻るのは後退ではありません。 戻り先の目安: 計算量とO記法の回 / 配列と連結リストの回 / ハッシュテーブルの回 / 再帰とメモ化の回

全部答えられたなら、次の段階へ進んでください。


次に読む

この記事は 【深掘り】コンピュータ科学 の 25 / 25 本目です。

記事
← 前の記事スケールとアムダールの法則 — 状態を持つと台を増やせない

ここが現時点の最後です。 続きは書き次第、はじめに のカリキュラムに並びます。

全体の順路は はじめに にあります。

roadmap.sh のどこをやっているか

【深掘り】コンピュータ科学の到達作品です。 ハッシュ索引と LRU を持つ KV ストアを自作し、線形探索との差を実測で確かめます。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次