索引が「速い」の正体 — データベースを自作する

データベースを自作する。データのファイルと索引カード、目的の位置を示す虫眼鏡。

索引が速い理由を、言葉ではなく実測で確かめます。データベースを自作して、探し方の差を測ります。

前回: gitは差分を保存していない — コミットを自作する これは【番外編】です。 このサイトの本筋は roadmap.sh に沿った段階で、データベースの自作はそこに載っていません。 読まなくても順路は繋がります。飛ばして構いません。 それでも書いているのは、これまで何度も「索引を張ると速い」と書いてきたのに、なぜ速いのかを一度も見ていないからです。 この記事のコマンドは、すべてVMの中(Ubuntu Server)で打ちます。 新しく立てるサーバーは1つもありません。使うのは node だけです。

MySQLの回から、ずっと同じことをしてきました。

INSERT INTO tasks (title) VALUES ('買い物');

打つと Query OK, 1 row affected と返る。それだけです。 この0.01秒のあいだにディスクで何が起きたのかは、一度も説明していません。

さらに、パフォーマンスの回ではこう書きました。

索引を張ると EXPLAIN の rows が20万から1になり、クエリが速くなる。

これも「そうなる」と書いただけです。 なぜ速くなるのかは、こう説明されるのが普通です。

索引があると、全部を読まずに目的の行へ直接たどり着けるからです。

この説明を10回読んでも、何も身に付きません。 「直接たどり着ける」が何をしていることなのか、まったく像が結ばないからです。

なので、作ります。

  • まず、一番素朴なデータベースを書きます。 key,value を1行ずつファイルに足すだけ、30行です
  • 20万件入れて、読み出しが遅いことを実測します
  • メモリの上に索引を足して、同じ読み出しが桁違いに速くなるところを並べます
  • 書いた直後にプロセスを殺して、データを消します

最後まで行くと、「索引を張る」という言葉の意味が変わります。 そこが目的です。

対象レベル: 中級 / 区分: 必要に応じて読む

目次

この記事でわかること

  • データベースの一番素朴な形は「ファイルの末尾に足すだけ」だということ。それでも書き込みは十分に速いこと
  • 索引の正体は「キー → ファイルの何バイト目か」の対応表だということ。魔法ではなく、ただの Map だということ
  • その索引は、メモリに載っていなければ意味がないこと。「メモリに載る/載らない」が性能の分かれ目になること
  • ファイルに書いても、まだディスクには届いていないこと。fsync を呼ぶまで、データはOSが預かっているだけだということ
  • トランザクションログ(WAL)が、なぜ「先に」書かれるのか。追記が速いことと直結していること
  • 追記だけの設計では、削除してもファイルは小さくならないこと。墓標(tombstone)とコンパクションが要る理由
  • ハッシュの索引では範囲検索ができないこと。だから本物のデータベースは木構造を使うこと
  • 書き込み重視のLSMと、読み出し重視のB+木という分かれ道があること。MySQL(InnoDB) は B+木だということ

この記事でやること

  1. key,value を追記するだけのデータベースを30行で書く。 20万件入れて、読み出しが遅いことを測る
  2. メモリ上に「キー → ファイル内の位置」の索引を作る。 同じ読み出しを測り直して、数字を並べる
  3. 書いた直後に自分のプロセスを SIGKILL で殺し、データが消えるところと、消えないところの両方を見る
  4. fsync を呼ぶ版と呼ばない版で、書き込み速度を測って桁を比べる
  5. 削除を実装し、ファイルが大きくなることを確認して、コンパクションで縮める

先に知る言葉

この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。

言葉意味
追記(アペンド)ファイルの末尾に足すだけの書き込み。途中を書き換えないので、ディスクの針を動かす必要が無く速い
オフセットファイルの先頭から何バイト目か、という位置の数字。「3行目」ではなく「1024バイト目」で数えます
ハッシュ表キーから値へ一発で飛べる表。JavaScript の Map やオブジェクトがこれです
索引(インデックス)本の巻末にある索引と同じ。 「この言葉は何ページ」を先に持っておく表
fsync「OSが預かっている分も、いますぐ本当にディスクへ書け」とOSに命じるシステムコール。 遅い
ページキャッシュOSがメモリ上に持っている、ディスクの写し。 書いたつもりのデータは、まずここに入ります
WAL(先行書き込みログ)データ本体を書き換える前に、「これから何をするか」を追記ログに書いておくやり方。落ちても復元できます
墓標(tombstone)「このキーは消えました」という印そのもの。 追記しかできない設計では、削除も追記で表します
コンパクション古い行や墓標を捨てて、ファイルを作り直すこと。 掃除。放っておくとファイルが太り続けます
LSMツリー追記ログを土台にしたデータの持ち方。 書き込みが速い。RocksDB や Cassandra がこれ
B+木枝分かれした木でデータを並べて持つやり方。 読み出しと範囲検索が速い。MySQL(InnoDB) はこれ
書き込み増幅1回書いたつもりが、内部では何回も書かれていること。コンパクションの代金です

「データベース」という言葉が大きすぎるので、先に範囲を狭めます。 この記事で作るのは 「キーを渡すと値が返るもの」 だけです。SQLも、表も、型も作りません。 それでも、MySQL が INSERT のときにディスクへ何をしているかは、これで見えます。

準備 — 作業用のフォルダを作る

VMの中(Ubuntu Server)で打ちます。

bash
$ node --version
v20.19.0

バージョンは違って構いません。 Node.js の回で入れたものがそのまま使えます。出てこないなら、その回に戻ってください。

bash
$ mkdir -p ~/mydb
$ cd ~/mydb

この記事で作るファイルは、すべて ~/mydb の中だけです。 npm install は一度もしません。外部ライブラリを1つも使いません。

第1段階 — 一番素朴なデータベース

いきなり本物の話をしません。 「データを保存するプログラムを、一番素朴に書いたらどうなるか」から始めます。

一番素朴な答えは、これです。

ファイルの末尾に、1行ずつ足していく。

それだけです。 書いてみます。

bash
$ nano db1.js

(VS Code の Remote SSH を使っているなら、そちらで作って構いません)

const fs = require("node:fs");

const DB_FILE = "./data.db";

// 書く: 末尾に1行足すだけ
function set(key, value) {
  fs.appendFileSync(DB_FILE, `${key},${value}\n`);
}

// 読む: 全部読んで、最後に見つかったものを返す
function get(key) {
  if (!fs.existsSync(DB_FILE)) return null;
  const text = fs.readFileSync(DB_FILE, "utf8");
  const prefix = `${key},`;
  let found = null;
  for (const line of text.split("\n")) {
    if (line.startsWith(prefix)) {
      found = line.slice(prefix.length); // 後から出てきたほうが勝つ
    }
  }
  return found;
}

module.exports = { set, get, DB_FILE };

これで全部です。 空行を除けば20行ほどしかありません。

動かします。

bash
$ node -e "const db=require('./db1.js'); db.set('user1','ワタナベ'); db.set('user2','タナカ'); console.log(db.get('user1'));"
ワタナベ

保存されています。 中身も見えます。

bash
$ cat data.db
user1,ワタナベ
user2,タナカ

これが「データベース」です。 笑うところではありません。 用途で選ぶ回で「SQLite はファイル1個」だと確かめました。あれと同じことをしています。 中の形式が違うだけで、ディスク上にあるのは1個のファイルという点は同じです。

更新も削除も「追記」でやる

この設計には、驚くところが1つあります。 上書きをしません。

bash
$ node -e "const db=require('./db1.js'); db.set('user1','ワタナベ改'); console.log(db.get('user1'));"
ワタナベ改
bash
$ cat data.db
user1,ワタナベ
user2,タナカ
user1,ワタナベ改

古い行は残ったままです。 get が「最後に見つかったもの」を返すので、結果として新しい値が返っているだけです。

これを「無駄」だと思うのが普通の感覚です。 実際、ファイルは太り続けます(後で対処します)。 それでも、この形には決定的な利点があります。 ファイルの途中を書き換えない、という一点です。 途中を書き換えるということは、「どこを書き換えるか探して、そこへ移動して、既存の内容を壊さないように差し込む」ということです。追記なら、末尾に足すだけです。

20万件入れて、実際に測る

理屈はここまでにして、数を増やします。 パフォーマンスの回と同じで、測らずに速い遅いを語らないのがこのサイトの型です。

bash
$ nano seed.js
const fs = require("node:fs");

const DB_FILE = "./data.db";
const N = 200000;

fs.rmSync(DB_FILE, { force: true });

const start = process.hrtime.bigint();

let buffer = "";
for (let i = 1; i <= N; i++) {
  buffer += `user${i},{"name":"ユーザー${i}","age":${20 + (i % 50)}}\n`;
  if (i % 10000 === 0) {
    fs.appendFileSync(DB_FILE, buffer);
    buffer = "";
  }
}
if (buffer.length > 0) fs.appendFileSync(DB_FILE, buffer);

const ms = Number(process.hrtime.bigint() - start) / 1e6;
console.log(`${N} 件を ${ms.toFixed(0)} ms で書きました`);
bash
$ node seed.js
$ ls -lh data.db
200000 件を 412 ms で書きました
-rw-rw-r-- 1 ubuntu ubuntu 9.2M Sep 14 10:02 data.db

数字は環境で違って構いません。 見てほしいのは桁です。

20万件の書き込みが1秒かかっていません。 追記しかしていないからです。 「書き込みが速い」というのは、こういうことです。

値の中にカンマが入っていることに気づいたでしょうか。 {"name":"ユーザー1","age":21} の中にカンマがあります。それでも壊れません。 get が「最初のカンマまでがキー、残り全部が値」として切っているからです。

ただし、値の中に改行を入れたら壊れます。 1行=1レコード、という前提が崩れるためです。本物のデータベースが「長さを先に書く」形式を使うのは、これを避けるためです。

読み出しを測る

bash
$ nano bench1.js
const db = require("./db1.js");

for (const key of ["user1", "user100000", "user200000", "user999999"]) {
  const start = process.hrtime.bigint();
  const value = db.get(key);
  const ms = Number(process.hrtime.bigint() - start) / 1e6;
  console.log(`${key.padEnd(12)} ${ms.toFixed(1)} ms  ${value ?? "(無し)"}`);
}
bash
$ node bench1.js
user1         96.4 ms  {"name":"ユーザー1","age":21}
user100000    94.8 ms  {"name":"ユーザー100000","age":20}
user200000    95.1 ms  {"name":"ユーザー200000","age":20}
user999999    93.7 ms  (無し)

ここが第1段階の山場です。3つ読み取ってください。

見えること意味
1件読むのに約95ミリ秒20万件で0.1秒。 100万件なら0.5秒。利用者が待てる時間ではありません
1件目も20万件目も、同じ時間どこにあっても同じだけかかる=毎回、最後まで全部読んでいる証拠
存在しないキーも同じ時間「無い」と分かるためにも全部読む必要がある

これが EXPLAIN で見た type: ALL、全件走査そのものです。 パフォーマンスの回で rows に20万と出ていたあれは、いま自分が書いたこの for ループと同じことをしています。 全文検索の回で LIKE '%…%' が遅かったのも、まったく同じ構図です。

[スクリーンショット: 01_全行走査は遅い.png] node seed.js と node bench1.js を続けて実行し、どのキーでも同じくらいの時間がかかっているところが1画面に写るように撮ってください。

書き込み20万件が0.4秒なのに、読み出し1件が0.1秒。 この非対称が、この記事の出発点です。

第2段階()— メモリの上に索引を足す

遅い理由ははっきりしています。 「user100000 がファイルのどこにあるか」を毎回ゼロから探しているからです。

では、探した結果を覚えておけばいい。 それだけです。

索引とは、「キー → ファイルの何バイト目か」の対応表のことです。

「何行目か」ではありません。「何バイト目か」です。 行数で持っても、そこへ行くには結局全部読むことになります。バイト位置なら、そこへ直接飛べます。

bash
$ nano db2.js
const fs = require("node:fs");

const DB_FILE = "./data.db";

// キー -> { offset: 値が始まるバイト位置, length: 値のバイト数 }
const index = new Map();
let fileSize = 0;

function buildIndex() {
  index.clear();
  fileSize = 0;
  if (!fs.existsSync(DB_FILE)) return;

  const buf = fs.readFileSync(DB_FILE); // Buffer のまま扱う(文字数ではなくバイト数が要る)
  fileSize = buf.length;

  let lineStart = 0;
  for (let i = 0; i < buf.length; i++) {
    if (buf[i] !== 0x0a) continue; // 0x0a = 改行

    const comma = buf.indexOf(0x2c, lineStart); // 0x2c = カンマ
    if (comma !== -1 && comma < i) {
      const key = buf.toString("utf8", lineStart, comma);
      index.set(key, { offset: comma + 1, length: i - comma - 1 });
    }
    lineStart = i + 1;
  }
}

function get(key) {
  const hit = index.get(key);
  if (!hit) return null;

  const buf = Buffer.alloc(hit.length);
  const fd = fs.openSync(DB_FILE, "r");
  fs.readSync(fd, buf, 0, hit.length, hit.offset); // 必要な分だけ読む
  fs.closeSync(fd);
  return buf.toString("utf8");
}

function set(key, value) {
  const line = Buffer.from(`${key},${value}\n`);
  const keyBytes = Buffer.byteLength(`${key},`);
  fs.appendFileSync(DB_FILE, line);
  index.set(key, { offset: fileSize + keyBytes, length: line.length - keyBytes - 1 });
  fileSize += line.length;
}

module.exports = { buildIndex, get, set, index, DB_FILE };

足したものは1つだけです。 Map です。それ以外のロジックは何も賢くなっていません。

get の中身を見てください。 ファイルを読んでいません。fs.readSync で、offset から length バイトだけ取り出しています。9.2MB のファイルのうち、30バイトだけ読んでいます。

測り直す

bash
$ nano bench2.js
const db = require("./db2.js");

const t0 = process.hrtime.bigint();
db.buildIndex();
const buildMs = Number(process.hrtime.bigint() - t0) / 1e6;
console.log(`索引の構築: ${buildMs.toFixed(0)} ms / ${db.index.size} 件`);

for (const key of ["user1", "user100000", "user200000", "user999999"]) {
  const start = process.hrtime.bigint();
  const value = db.get(key);
  const ms = Number(process.hrtime.bigint() - start) / 1e6;
  console.log(`${key.padEnd(12)} ${ms.toFixed(3)} ms  ${value ?? "(無し)"}`);
}

const mb = process.memoryUsage().heapUsed / 1024 / 1024;
console.log(`索引が使っているメモリ(目安): ${mb.toFixed(1)} MB`);
bash
$ node bench2.js
索引の構築: 356 ms / 200000 件
user1         0.104 ms  {"name":"ユーザー1","age":21}
user100000    0.041 ms  {"name":"ユーザー100000","age":20}
user200000    0.038 ms  {"name":"ユーザー200000","age":20}
user999999    0.004 ms  (無し)
索引が使っているメモリ(目安): 58.3 MB

並べます。

読み出し第1段階(全行走査)第2段階(索引あり)差
user196.4 ms0.104 ms約900倍
user10000094.8 ms0.041 ms約2300倍
user20000095.1 ms0.038 ms約2500倍
存在しないキー93.7 ms0.004 ms約23000倍

[スクリーンショット: 02_索引ありの比較.png] node bench1.js と node bench2.js を続けて実行し、ミリ秒の桁が変わっているところが1画面に写るように撮ってください。

アルゴリズムを賢くしていません。 Map を1つ足しただけです。

「索引を張る」というのは、これをやることです。 CREATE INDEX と打ったとき、MySQL の中で作られているのは(形は違いますが)「キー → データの位置」の対応表です。 速いのは、探さなくなったからではありません。「探した結果をあらかじめ持っている」からです。

ここで、3つの代金に気づく

いいことばかりではありません。 上の出力に、代金がそのまま出ています。

① 索引の構築に356ミリ秒かかっている。

起動のたびに、ファイルを全部読んで索引を作り直しています。 データが10GBになったら、起動に何分もかかります。本物のデータベースが「索引もディスクに保存する」のは、これを避けるためです。

② 索引が58MBのメモリを食っている。

データ本体は9.2MBです。索引のほうが大きい。 キーが文字列で、1件ごとにオブジェクトを持っているためです。

これが「メモリに載る/載らない」の話の正体です。 Redis の回や用途で選ぶ回で「メモリに載るかどうか」と何度か書きました。いま、それを自分の手で作りました。 索引がメモリに収まらなくなった瞬間、この速度は消えます。

③ 書き込みは、まだ速いまま。

set に足したのは index.set の1行だけです。追記の速さは損なわれていません。

これが「ログ構造化ストレージ」と呼ばれる考え方の入口です。 データ本体は追記ログ、位置はメモリ上の索引。 この形は実在します。Riak で使われた Bitcask がほぼこのままの設計です。 そして、これを何段にも積んで整理するようにしたものが、LSMツリー(RocksDB・LevelDB・Cassandra)です。この記事で書いた30行は、その一番下の階です。

第3段階()— 書いた直後に殺す

ここまでで「速い」は作れました。 残っているのは、壊れないかです。

トランザクションの回で、送金の途中でプロセスを殺して3000円を消しました。あれと同じことを、今度はもっと下の層でやります。

これから、わざとプロセスを強制終了させます。必ずVMの中だけでやってください。 消えて困るファイルが同じフォルダに無いことを確認してください。~/mydb の中しか触りません。

実験A — 書いたのに、消える

bash
$ nano crash1.js
const fs = require("node:fs");

const out = fs.createWriteStream("./crash1.db", { flags: "a" });

for (let i = 1; i <= 5; i++) {
  out.write(`k${i},v${i}\n`);
}

console.log("5件 書きました");
process.kill(process.pid, "SIGKILL"); // 自分を強制終了する
bash
$ rm -f crash1.db
$ node crash1.js
5件 書きました

「書きました」と出ました。 中身を見ます。

bash
$ ls -l crash1.db
$ cat crash1.db
-rw-rw-r-- 1 ubuntu ubuntu 0 Sep 14 10:20 crash1.db

0バイトです。何も入っていません。

プログラムは嘘をついていません。 out.write() は成功しています。ただ、それは「Node.js の中のバッファに積んだ」という意味でしかありませんでした。 実際にOSへ渡す前に、プロセスが殺されました。

write が返ってきた ≠ 書けた。 これが1つ目の層です。

実験B — 今度は消えない

bash
$ nano crash2.js
const fs = require("node:fs");

for (let i = 1; i <= 5; i++) {
  fs.appendFileSync("./crash2.db", `k${i},v${i}\n`); // 同期的に書く
}

console.log("5件 書きました");
process.kill(process.pid, "SIGKILL");
bash
$ rm -f crash2.db
$ node crash2.js
$ cat crash2.db
5件 書きました
k1,v1
k2,v2
k3,v3
k4,v4
k5,v5

今度は残りました。 同じ SIGKILL なのに、結果が違います。

[スクリーンショット: 03_kill直後のファイル.png] node crash1.js → cat crash1.db(空)→ node crash2.js → cat crash2.db(5行ある)を続けて実行し、同じ強制終了で結果が違うところが1画面に写るように撮ってください。

ここで、多くの説明が雑になります。 正確に書きます。

層どこにあるプロセスが死んだらOSが死んだら(電源断)
① アプリのバッファNode.js のメモリの中消える(実験A)消える
② ページキャッシュOSのメモリの中消えない(実験B)消える
③ ディスク本当の記録媒体消えない消えない

実験Bで残ったのは、②に届いていたからです。③まで届いたからではありません。 appendFileSync は「OSに渡す」までしかやっていません。OSは「後でまとめて書くから」と言って預かっただけです。 cat で読めるのは、OSが自分の預かり分を返しているからです。 ディスクを見に行っていません。

この②の状態を「まだ危ない」と考えるのが、データベースの立場です。 ②を③へ落とす命令が fsync です。

実験C — fsync の代金を測る

「じゃあ毎回 fsync すればいい」で終わりなら、話は簡単です。そうならない理由を測ります。

bash
$ nano bench_fsync.js
const fs = require("node:fs");

function run(name, file, useFsync, count) {
  fs.rmSync(file, { force: true });
  const fd = fs.openSync(file, "a");
  const line = Buffer.from("key,value-0123456789\n");

  const start = process.hrtime.bigint();
  for (let i = 0; i < count; i++) {
    fs.writeSync(fd, line);
    if (useFsync) fs.fsyncSync(fd);
  }
  const ms = Number(process.hrtime.bigint() - start) / 1e6;
  fs.closeSync(fd);

  const perSec = Math.round((count / ms) * 1000);
  console.log(`${name.padEnd(16)} ${count}件 ${ms.toFixed(0)} ms  (${perSec} 件/秒)`);
}

run("fsync なし", "./bench_a.db", false, 20000);
run("毎回 fsync", "./bench_b.db", true, 20000);
bash
$ node bench_fsync.js
fsync なし         20000件 128 ms  (156250 件/秒)
毎回 fsync         20000件 9840 ms  (2033 件/秒)

約77倍の差です。

数字は環境で大きく変わります。 VMware のホスト側がディスク書き込みをキャッシュしている場合、差が10倍程度までしか開かないこともあります。 桁が変わっていれば、それで十分です。 逆に、差がまったく出ないなら、それは fsync が本当には効いていない(ホストが預かっている)ということです。仮想マシンでは、③のさらに下にもう1層あります。

ここで、ACIDの「D」が腑に落ちる

トランザクションの回で、こう書きました。

MySQL は先に「これから何をするか」をディスクのログに書いてから、実際のデータを書きます。落ちても、起動時にログを読み直して続きをやります。

あのときは「そういうものです」としか言えませんでした。いまなら、理由が全部そろっています。

疑問答え
なぜログを「先に」書くのかデータ本体はファイルのあちこちを書き換える(遅い)。ログは追記だけ(速い)。速いほうを先に確定させて、遅いほうは後回しにする
なぜ COMMIT は少し待たされるのかそこで fsync しているから。 上で測った、あの代金です
落ちたあと、なぜ復元できるのかログが③まで届いているから。 起動時にログを読み直して、やり残しをやる
COMMIT が返ったら本当に安全なのかfsync まで届いていれば安全。 設定で「1秒に1回だけ fsync」にすることもでき、その場合は最後の1秒が消えます

「速さと安全は、fsync を何回呼ぶかで買う」——これがトランザクションログの正体です。 MySQL には innodb_flush_log_at_trx_commit、PostgreSQL には synchronous_commit という設定があります。あれは、いま測った77倍を、どこで妥協するかのつまみです。

レプリケーションの回も、ここに繋がります。

あの回で複製先へ送っていたのは、データ本体ではなく「バイナリログ」でした。 なぜログを送るのか。追記ログは「起きたことが起きた順に並んでいる」ので、同じ順で再生すれば同じ状態になるからです。いま自分で作った data.db を丸ごとコピーして別のプロセスで buildIndex() すれば、それはもうレプリカです。

実験D(任意)— 本当に電源を切る

ここは飛ばして構いません。やるなら、必ずVMのスナップショットを取ってから。

②が電源断で消えることを本当に確かめたいなら、VMware側から「パワーオフ」(電源ボタンではなく、コンセントを抜く相当)を使います。

  1. VMware で スナップショットを取る
  2. VM の中で node crash2.js を実行する(fsync していない)
  3. すぐに VMware の「パワーオフ」でVMを落とす
  4. 起動し直して cat crash2.db を見る

消えているかもしれませんし、残っているかもしれません。 ホストのキャッシュ次第です。「消えることがある」を確認できれば十分で、再現しなくても失敗ではありません。

やらなくていい理由: 本番のデータベースは、この不確実さを許さないために fsync を呼びます。「たぶん残る」に賭けないのがデータベースの仕事、というのがこの節の結論です。

第4段階 — 消したデータはどこへ行くか

追記しかしないので、削除できません。 正確には、「消す」という操作を追記で表現するしかありません。

bash
$ nano db3.js
const fs = require("node:fs");

const DB_FILE = "./data.db";
const TOMBSTONE = "\u0000DELETED\u0000"; // 普通の値としては現れない印

const index = new Map();
let fileSize = 0;

function buildIndex() {
  index.clear();
  fileSize = 0;
  if (!fs.existsSync(DB_FILE)) return;

  const buf = fs.readFileSync(DB_FILE);
  fileSize = buf.length;

  let lineStart = 0;
  for (let i = 0; i < buf.length; i++) {
    if (buf[i] !== 0x0a) continue;
    const comma = buf.indexOf(0x2c, lineStart);
    if (comma !== -1 && comma < i) {
      const key = buf.toString("utf8", lineStart, comma);
      index.set(key, { offset: comma + 1, length: i - comma - 1 });
    }
    lineStart = i + 1;
  }
}

function readAt(hit) {
  const buf = Buffer.alloc(hit.length);
  const fd = fs.openSync(DB_FILE, "r");
  fs.readSync(fd, buf, 0, hit.length, hit.offset);
  fs.closeSync(fd);
  return buf.toString("utf8");
}

function set(key, value) {
  const line = Buffer.from(`${key},${value}\n`);
  const keyBytes = Buffer.byteLength(`${key},`);
  fs.appendFileSync(DB_FILE, line);
  index.set(key, { offset: fileSize + keyBytes, length: line.length - keyBytes - 1 });
  fileSize += line.length;
}

function get(key) {
  const hit = index.get(key);
  if (!hit) return null;
  const value = readAt(hit);
  return value === TOMBSTONE ? null : value; // 墓標なら「無い」と答える
}

function del(key) {
  set(key, TOMBSTONE); // 削除も「書き込み」
}

module.exports = { buildIndex, get, set, del, index, DB_FILE, TOMBSTONE };

del の中身が set なのがすべてです。 削除しても、ファイルは大きくなります。

bash
$ nano bench_del.js
const fs = require("node:fs");
const db = require("./db3.js");

db.buildIndex();
console.log(`削除前: ${(fs.statSync(db.DB_FILE).size / 1024 / 1024).toFixed(2)} MB / ${db.index.size} 件`);

for (let i = 1; i <= 150000; i++) db.del(`user${i}`);

console.log(`削除後: ${(fs.statSync(db.DB_FILE).size / 1024 / 1024).toFixed(2)} MB / ${db.index.size} 件`);
console.log(`user1 を読む: ${db.get("user1")}`);
bash
$ node bench_del.js
削除前: 9.24 MB / 200000 件
削除後: 12.90 MB / 200000 件
user1 を読む: null

15万件を消したのに、ファイルが3.7MB増えました。 そして索引の件数も減っていません。「消えました」という印を20万件分のうち15万件に足しただけだからです。

これが墓標(tombstone)です。 消したのに増える、というのは直感に反します。しかし追記しかしない設計では、これしかありません。 レプリケーションの回を思い出してください。削除を「印」として書いておかないと、複製先に「消えたこと」を伝えられません。 何も書かなかったら、複製先は消したことを知りようがない。墓標は、複製のためにも要ります。

コンパクション — 掃除をする

放っておけば、ファイルは無限に太ります。 掃除が要ります。

やることは単純です。 「いま生きている値だけを、新しいファイルに書き直す」。

bash
$ nano compact.js
const fs = require("node:fs");
const db = require("./db3.js");

db.buildIndex();
const before = fs.statSync(db.DB_FILE).size;

const TMP = db.DB_FILE + ".compacting";
fs.rmSync(TMP, { force: true });

let alive = 0;
let buried = 0;
let buffer = "";

for (const key of db.index.keys()) {
  const value = db.get(key); // 墓標なら null が返る
  if (value === null) {
    buried++;
    continue; // 墓標そのものも捨てる
  }
  alive++;
  buffer += `${key},${value}\n`;
  if (buffer.length > 1024 * 1024) {
    fs.appendFileSync(TMP, buffer);
    buffer = "";
  }
}
if (buffer.length > 0) fs.appendFileSync(TMP, buffer);
if (!fs.existsSync(TMP)) fs.writeFileSync(TMP, "");

fs.renameSync(TMP, db.DB_FILE); // 差し替えは一瞬で終わる操作にする
db.buildIndex();                // 位置が全部変わったので、索引を作り直す

const after = fs.statSync(db.DB_FILE).size;
console.log(`生き残り ${alive} 件 / 捨てた ${buried} 件`);
console.log(`${(before / 1024 / 1024).toFixed(2)} MB → ${(after / 1024 / 1024).toFixed(2)} MB`);
bash
$ node compact.js
$ ls -lh data.db
生き残り 50000 件 / 捨てた 150000 件
12.90 MB → 2.36 MB

[スクリーンショット: 04_コンパクション前後.png] node bench_del.js(12.90MB に増える)→ node compact.js(2.36MB に縮む)を続けて実行し、増えてから減るところが1画面に写るように撮ってください。

この掃除には、3つの厄介さがあります。

厄介さ中身
索引が全部無効になる位置が変わるので、作り直し(buildIndex())。上で測った356ミリ秒を、また払う
掃除中も書き込みが来る本物は新しい書き込みは別ファイルへ流しておき、掃除が終わってから合流させます
一時的にディスクが2倍要る新旧2つのファイルが同時に存在します。空きが無いと掃除に失敗する

これが「書き込み増幅」の正体です。 1件書いたつもりが、コンパクションで何度も書き直されている。 LSM系のデータベースが「書き込みは速いがディスクI/Oは意外と多い」と言われるのは、これが理由です。 renameSync を使っているのにも意味があります。ファイルの差し替えを、途中で落ちても壊れない1回の操作にするためです。コピーで上書きすると、途中で落ちたときに「半分だけ新しいファイル」が残ります。

B+木との違い — なぜMySQLは追記ログではないのか

ここまでで作ったものは、追記ログ+ハッシュ索引です。 MySQL は違う作りをしています。なぜか。

この記事のもの(LSM系の入口)B+木(MySQL の InnoDB)
書き込み末尾に足すだけ。速い木の中の該当する場所を書き換える。遅い
読み出し索引が当たれば速い。当たらないと複数の場所を探す木を根から数回たどるだけ。安定して速い
範囲検索ハッシュ索引では不可能(後述)得意。並んでいるので順に辿るだけ
ファイルの太り方太る。コンパクションで掃除する太りにくい。同じ場所を書き換えるため
代表例RocksDB / LevelDB / Cassandra / HBaseMySQL(InnoDB) / SQLite(PostgreSQL も索引は B木だが、表の本体は更新・削除で古い行を残して VACUUM で回収する方式なので、上の「太りにくい」には当てはまらない)

どちらが優れている、という話ではありません。

書き込みが多いなら追記が有利。読み出しと範囲検索が多いなら木が有利。 用途で選ぶ回で「何を速くしたいか」を軸の1つに置きました。その軸は、この層で決まっています。

そして、面白いのはここです。

MySQL は、両方持っています。

  • データ本体は B+木(ibd ファイル。同じ場所を書き換える)
  • redoログは追記だけ(この記事で書いたものと同じ形)

書き込みが来たら、まず追記ログへ書いて fsync し、「確定した」と返す。 B+木のほうは、あとから落ち着いて書く。追記の速さと、木の読みやすさを、両取りしているわけです。

COMMIT が返ってきた時点で、データ本体はまだ書かれていないことがあります。 それでも安全なのは、追記ログが③まで届いているからです。 この一文が意味不明でなくなったなら、この記事の目的は達成です。

限界 — 範囲検索ができない

作ったものには、致命的な穴があります。

bash
$ node -e "const db=require('./db3.js'); db.buildIndex(); console.log(db.get('user160000'), db.get('user160001'));"

1件ずつなら引けます。 では、これはどうでしょう。

「user160000 から user160010 までを、まとめて出してほしい」

Map にはできません。

理由は単純です。ハッシュ表には順番が無いからです。 Map は「このキーの値はどこ」しか答えられません。「このキーの次のキーは何か」を知りません。

// できない。全キーを取り出して並べ直すしかない
const keys = [...db.index.keys()].filter((k) => k >= "user160000" && k <= "user160010");

これは全キー走査です。 20万件のうち10件が欲しいだけなのに、20万件を見ています。第1段階に逆戻りしました。

SQLに直せば、これができないということです。

SELECT * FROM users WHERE id BETWEEN 160000 AND 160010;
SELECT * FROM tasks ORDER BY created_at DESC LIMIT 20;

下の ORDER BY ... LIMIT 20 は、どんなアプリにもあります。 「新着20件」です。ハッシュ索引だけでは、これが全件走査になります。

だから木構造が要ります。 木は、キーを並べて持っています。 だから「ここから、ここまで」を、端から順に辿るだけで取り出せます。 LSM系も、この問題を知っています。 だから追記ログをそのまま置かず、キーで並べ替えたファイル(SSTable=Sorted String Table)に書き直します。コンパクションのついでに並べ替えているわけです。

そして、これは全文検索の回の答え合わせでもあります。

LIKE 'ubuntu%'(前方一致)は索引が効くのに、LIKE '%ubuntu%'(部分一致)は効かない。 理由は、並んでいるものは「前から一致するもの」しかまとめて取れないからです。真ん中に来るものは、並び順の役に立ちません。

やらないこと

ここまでを「データベースを作った」と呼ぶのは言い過ぎです。 何を作っていないか、正直に数えます。

作っていないもの本物では
SQL文字列を解析して、実行計画を立てて、EXPLAIN で見せる。それだけで数万行
表・型・スキーマINT と VARCHAR の区別すらありません。全部ただの文字列です
同時実行制御2つのプロセスから同時に書いたら壊れます。 ロックもトランザクションもありません
ネットワークlocalhost:3306 で待ち受けていません。同じプロセスから関数を呼ぶだけ
クラッシュ後の検証途中で落ちて行が半分だけ書かれたら、その行はゴミです。本物は1件ごとにチェックサムを持ちます
索引の永続化起動のたびに全件読み直しています。10GBあったら起動できません
複数キーの索引・外部キー・結合テーブル設計の回でやったことは、1つも実装していません

同時実行制御が無い、が一番重いです。トランザクションの回で在庫1個を2人に売った事故は、このデータベースでは100%再現します。 直す手段もありません。 「じゃあ本物を使え」——それがこの記事の実用的な結論です。作るのは、中で何が起きているかを知るためです。

なお、上の表で挙げた「半分だけ書かれた行」について。buildIndex() は改行を見つけたときだけ索引に入れているので、末尾の書きかけの行は自然に無視されます。 ただしこれは偶然そうなっているだけで、行の途中のバイトが化けた場合は検出できません。 本物がチェックサムを持つのは、そのためです。

つまずいたところ

症状原因
Cannot find module './db1.js'~/mydb の外で node を打っている。 cd ~/mydb してから実行する
node bench2.js が全部 (無し) を返すbuildIndex() を呼び忘れている。 索引は起動のたびに作り直しが要ります
索引ありでも、なぜか値が途中で切れるバイト数と文字数を混同している。 日本語は1文字3バイト。length ではなく Buffer.byteLength を使う
crash2.js で消えると思ったのに残った正しい動きです。 OSのページキャッシュに届いているので、プロセスが死んでも消えません(本文の②)
fsync あり/なしで差が出ないVMware のホスト側がキャッシュしている可能性。仮想マシンではディスクの下にもう1層あります
bench_del.js を2回流すとファイルが増え続ける仕様どおりです。 追記しかしないため。node compact.js で掃除する
compact.js のあと get が変な値を返すbuildIndex() を呼び直していない。 位置が全部ずれています
seed.js が ENOSPC で失敗するVMのディスクが足りない。 df -h で確認。N の値を減らす
メモリ使用量が思ったより大きい索引はデータ本体より大きくなり得ます。 これは異常ではなく、本文③の話そのものです

ファイルの中身を直接見たいときは、テキスト処理の回の道具がそのまま使えます。

bash
$ head -c 200 data.db
$ grep -c "" data.db

head -c は「先頭から200バイト」です。 行ではなくバイトで見ると、オフセットの話が具体的になります。

後片づけ

常駐しているものは1つもありません。 フォルダごと消すだけです。

bash
$ cd ~
$ rm -rf ~/mydb
bash
$ df -h /

ディスクの空きが戻っていることを確認してください。 実験用のファイルは合わせて30MB程度です。

このあとの回で使うものは、何も壊していません。 apt で入れたものもありません。

これで何が変わるか

この記事の価値は、動くソフトを1つ増やしたことではありません。 使う言葉の中身が変わったことです。

前はこれからは
「索引を張ると速い」「キー → 位置の対応表を、メモリに先に作ってある」
「メモリが足りない」「索引がメモリに載らなくなった。載っていたときの速度はもう出ない」
「COMMIT は確定」「fsync がどこまで届いたか、の設定次第。確定の意味は選べる」
「削除した」「墓標を1件追記した。ファイルは増えた。掃除は別の仕事」
「レプリケーションで同期する」「追記ログを、起きた順に再生している」
「NoSQLは速い」「書き込みに寄せた設計を選んだ。範囲検索は別途どうにかする必要がある」

そして、用途で選ぶ回の結論が、もう一段はっきりします。

製品の違いは、たいてい「この2つの代金を、どこで払うと決めたか」の違いです。 ① 追記で速く書くか、木で速く読むか。② fsync をどれだけ呼ぶか。

「個人のサービスなら1つでいい」は変わりません。 ただ、なぜ MySQL がその1つでいいのかは、もう他人の言葉ではなくなったはずです。

まとめ

  • 一番素朴なデータベースは「ファイルの末尾に key,value を足すだけ」。 20行で書ける
  • 追記しかしないので、更新も削除も「足す」。 古い行は残り、最後に書かれたものが勝つ
  • 20万件で、読み出しは1件あたり約95ミリ秒。 どのキーでも同じ時間=毎回、最後まで全部読んでいる
  • EXPLAIN の全件走査は、この for ループそのもの。 LIKE '%…%' が遅かったのも同じ構図
  • 索引の正体は「キー → ファイルの何バイト目か」の Map。 アルゴリズムは何も賢くなっていない
  • 同じ読み出しが 0.04 ミリ秒になった(約2000倍)。 速いのは、探した結果をあらかじめ持っているから
  • 代金は3つ。 起動時に索引を作り直す時間、索引が食うメモリ(データ本体より大きかった)、そして索引の永続化という宿題
  • データ本体は追記ログ、位置はメモリ上の索引。 これがログ構造化ストレージ(LSM系)の一番下の階
  • 書き込みは3層ある。 ①アプリのバッファ ②OSのページキャッシュ ③ディスク
  • プロセスを殺すと①は消えるが、②は消えない。 ②が消えるのはOSごと落ちたとき
  • ②を③へ落とす命令が fsync。 実測で約77倍遅くなった。安全は時間で買う
  • だから WAL は「先に」書かれる。 データ本体の書き換えは遅く、追記は速いから、速いほうで確定させる
  • COMMIT が返ってもデータ本体は未書き込みでよい。 追記ログが③まで届いていれば復元できる
  • 削除は墓標の追記。 15万件消したらファイルは 9.24MB → 12.90MB に増えた
  • コンパクションで 2.36MB に縮む。 代金は索引の作り直し・掃除中の書き込み・一時的に2倍のディスク(=書き込み増幅)
  • B+木は書き込みが遅く、読み出しと範囲検索が速い。 MySQL(InnoDB) は B+木。用途で選ぶのは、この層の話
  • MySQL は両方持っている。 データ本体は B+木、redoログは追記だけ
  • ハッシュ索引では範囲検索ができない。 BETWEEN も ORDER BY ... LIMIT も全件走査になる
  • だから木が要る。 LSM系も、コンパクションのついでにキーで並べ替えて(SSTable)この穴を埋めている
  • 作っていないもの: SQL・型・同時実行制御・ネットワーク・チェックサム・索引の永続化。 本物を使う理由はここにある

参考リンク


次に読む

この記事は 【番外編】roadmap.sh の外 の 22 / 35 本目です。

記事
← 前の記事GPOが適用されない原因|リンク先・OU・適用順の仕組みとgpresultでの確認
→ 次の記事sysprepで一般化する手順|クローンのSID重複を防ぎunattend.xmlで無人化

ここは番外編です。 本筋から外れているので、飛ばして構いません。

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

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

【番外編】既にあるものを自作して仕組みを知る回。roadmap.sh の範囲外。

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

コメント

コメントする

目次