【初心者歓迎】Google Cloud Spannerの超高速書き込みを支える秘密「LSM-Tree」を日本一わかりやすく解説するよ！
こんにちは！自称・Cloud Spannerのことなら何でも知っている先輩エンジニアです。
データベース（DB）の勉強をしていると、「Google Cloud Spanner（以下、Spanner）は世界中にデータを分散させているのに、なぜあんなに爆速でデータを書き込めるんだろう？」 という疑問にぶつかりませんか？
実はその裏側には、「ログ構造化マージツリー（LSM-Tree）」 という、知る人ぞ知る天才的なデータの持ち方の仕組みが隠されています。
「LSM-Tree……？ なんだか名前からして難しそう……」と身構えなくても大丈夫！
この記事を読み終わる頃には、「なんだ、日常のあの作業と同じじゃないか！」 とすっきり理解できているはずです。ここをクリアすれば、Cloud Spannerの基本はバッチリマスターできますよ。
それでは、一緒に楽しく学んでいきましょう！
—
1. なぜ普通のデータベースは書き込みが遅くなるの？
LSM-Treeの凄さを知るために、まずは「一般的なデータベースがなぜ書き込みに苦労するのか」を身近な例で考えてみましょう。
散らかった部屋の本棚（ランダムアクセス）
想像してみてください。あなたは巨大な本棚の管理人です。
本棚には、あいうえお順にびっしりと本が並んでいます。
そこへ、新しく「き」から始まる本が届きました。
あなたはどうしますか？
1. 「き」の棚を探す
2. 「き」の場所に無理やり隙間を作るために、後ろの本を全部少しずつずらす
3. 新しい本を挟み込む
これ、めちゃくちゃ大変ですよね？
1冊入れるだけで一苦労です。次に「そ」の本が来たら、また別の棚へ走っていって同じ作業を繰り返さなければなりません。
これが、従来のデータベースがディスク（SSDやハードディスク）に行っていた「ランダム書き込み（ランダムアクセス）」です。
データがあいうえお順（あらかじめ決められた場所）に並んでいるため、新しいデータが来るたびにディスクのあちこちを探しては書き換える必要があり、これが性能の限界（ボトルネック）になっていました。
—
2. LSM-Treeのアイデア：「とりあえずメモして、後でまとめる！」
「じゃあ、書き込むときにいちいち並べ替えなきゃいいんじゃない？」
そう考えた賢いエンジニアたちが生み出したのが、LSM-Tree（Log-Structured Merge-Tree） です。
LSM-Treeの発想は驚くほどシンプルです。
> 「新しく届いた本は、本棚に走って片付けに行かない！ とにかく手元のデスクのメモ帳にパパッと書き留めておこう。メモがいっぱいになったら、一括で綺麗に整理して本棚にしまえばいいよね！」
この「とりあえずメモ」と「あとで一括整理」の組み合わせこそが、Spannerをはじめとするモダンなデータベースの爆速書き込みの秘密なのです。
—
3. LSM-Treeを支える「2つの主役」
LSM-Treeの仕組みをもう少し詳しく見ていきましょう。登場人物（要素）は主に2つだけです！
[書き込みリクエスト]
│
▼
┌──────────────┐
│ MemTable │ (メモリ上のメモ帳：超高速！)
└──────┬───────┘
│ メモ帳がいっぱいになったら…
▼
┌──────────────┐
│ SSTable │ (ディスク上の整理された本棚：消えない！)
└──────────────┘
① MemTable（メモリのメモ帳）
データの書き込みリクエストが来たら、データベースはディスクではなく、超高速に動くメモリ（RAM）の上のメモ帳にデータを書き込みます。このメモ帳を MemTable（メムテーブル） と呼びます。
メモ帳（メモリ）の中では、データは自動的に綺麗にあいうえお順に並べ替えられます。メモリ上での並べ替えなら、一瞬で終わるからです。
② SSTable（ディスク上の整理ノート）
メモリのメモ帳（MemTable）がいっぱいになると、データベースはそのメモ帳の中身を丸ごとディスク（SSDなど）に保存します。このディスク上に保存されたファイルを SSTable（エスエステーブル） と呼びます。
ここで重要なポイントがあります！
SSTableをディスクに書くとき、「既存のファイルを書き換える」のではなく、「新しいファイルとして丸ごと末尾に追記するだけ」 にします。
ファイルを探して途中に挟み込む必要がないため、ディスクへの書き込み速度が極限まで速くなります。これを専門用語で 「シーケンシャル書き込み」 と呼びます。
—
4. 増えすぎたファイルを整理する「コンパクション（Compaction）」
「メモ帳をそのままファイル化して保存していくなら、古いファイルと新しいファイルがディスクの中にどんどん増えていかない？」
鋭いですね！ その通りです。
そのまま放っておくと、ファイルが何千個も増えてしまい、今度は「データを読み込む（探す）」ときに苦労してしまいます。また、更新前の古い不要なデータも残ったままになってしまいます。
そこで登場するのが、裏でひっそり働くお掃除ロボット、コンパクション（Compaction = 圧縮・統合） です。
【コンパクションのイメージ】
[古いSSTable] : A, B, C (更新前)
[新しいSSTable]: B(最新), D
│ 裏でひっそり合体＆整理！
▼
[新しい1つのSSTable]: A, B(最新), C, D （古いBは消去！）
コンパクションは、バックグラウンドで（ユーザーの邪魔をしないように）複数のSSTableを読み込み、「重複した古いデータを捨てながら、綺麗に1つの新しいSSTableに合体」 してくれます。
このおかげで、ディスクの中は常に整理整頓された状態が保たれるのです。
—
5. プログラムの動きをイメージしてみよう！
実際のSpannerの動きを理解しやすいように、LSM-Treeの書き込みフローを疑似的なコード（イメージ）で表現してみますね。
LSM-Treeへの書き込みイメージコード
class SimpleLSMTree:
def __init__(self):
self.mem_table = {} # メモリ上のメモ帳 (MemTable)
self.max_size = 3 # メモ帳の上限サイズ
self.ss_tables = [] # ディスク上のファイル一覧 (SSTables)
def write(self, key, value):
# 1. まずは高速なメモリ上のメモ帳に書く！
self.mem_table[key] = value
print(f”[MemTableに書き込み] {key}: {value}”)
# 2. メモ帳がいっぱいになったか確認
if len(self.mem_table) >= self.max_size:
self.flush_to_sstable()
def flush_to_sstable(self):
# 3. メモ帳の中身をあいうえお順（ソート済み）にしてディスクへ保存！
sorted_data = dict(sorted(self.mem_table.items()))
self.ss_tables.append(sorted_data)
print(f” └─► [SSTableとしてディスクへ保存！] {sorted_data}”)
# 4. メモ帳をクリアして次の書き込みに備える
self.mem_table.clear()
使ってみよう！
lsm = SimpleLSMTree()
どんどん書き込む
lsm.write(“User_C”, “Alice”)
lsm.write(“User_A”, “Bob”)
lsm.write(“User_B”, “Charlie”) # ここでメモ帳がいっぱいになる！
lsm.write(“User_D”, “Dave”)
【実行結果のイメージ】
[MemTableに書き込み] User_C: Alice
[MemTableに書き込み] User_A: Bob
[MemTableに書き込み] User_B: Charlie
└─► [SSTableとしてディスクへ保存！] {‘User_A’: ‘Bob’, ‘User_B’: ‘Charlie’, ‘User_C’: ‘Alice’}
[MemTableに書き込み] User_D: Dave
いかがでしょうか？
「書き込みはとにかく手元のメモ帳に書き、一杯になったら並べ替えてファイルとして落とす」という流れが直感的にイメージできたのではないでしょうか！
—
6. まとめ：SpannerとLSM-Treeの美しい関係
最後に、今回のポイントをまとめましょう！
1. 従来のDBは……
- 決められた場所に直接書き込むため、ディスク内を探し回る必要があり書き込みが遅かった（ランダムアクセス）。
2. LSM-Treeを採用したSpannerは……
- MemTable（メモリ） にとりあえず超高速で書き込む。
- メモ帳がいっぱいになったら、SSTable（ディスク） に追記する形で保存する（シーケンシャルアクセス）。
- 後から裏方である コンパクション がファイルを綺麗に合体・整理する。
Google Cloud Spannerという世界最高峰の分散データベースも、その根底にはこうした「無理をせず、効率よくデータを整理する賢いアイデア」が詰まっているんです。
LSM-Treeの概念さえ理解できれば、Spannerのアーキテクチャの半分を攻略したと言っても過言ではありません！
「なんだか自分にも理解できたぞ！」と思えたら、ぜひ自信を持って次のステップに進んでみてくださいね。
また次の記事でも、わかりやすく本質的な技術の面白さを一緒にかみ砕いていきましょう！応援しています！
コメント