カラムストアの遅延更新：delta-mainとマージ

なぜ列ストアは「直接更新」できないのか

列指向ストレージ は同一カラムの値を連続配置し、辞書符号化や RLE で強く圧縮することで、集計スキャンを桁で速くします。ところがこの構造は更新と相性が最悪です。理由は二つあります。

第一に、1行を挿入・更新するだけで全カラムの圧縮ブロックに触れる必要があります。値はカラム別に連続して詰められているため、論理的な「1行」は物理的にバラバラの位置に散っているからです。第二に、辞書符号化では各値が辞書 ID（整数）に置き換えられ、ID はソートされた辞書上の位置に対応します。新しい値を1つ足すだけで辞書のソート順がずれ、既存の全 ID を振り直す羽目になることもあります。圧縮済みのカラムを途中で書き換えるのは、ZIP ファイルの中身を1バイトだけ差し替えるのに似て、ほぼ全体の再構成を招きます。

そこで列ストアは、更新を圧縮済みの本体へ直接当てるのを諦め、書き込み最適化の小さな層にいったん吸わせ、後でまとめて畳むという遅延更新（lazy update）を採ります。これが delta-main アーキテクチャです。

delta と main の役割分担

要点は、main を不変（immutable）に保つことです。書き込みはすべて delta が受け、main は周期マージのときだけ作り替えられます。これにより main の圧縮効率とスキャン局所性が壊れません。delta は小さく未圧縮なので点更新を低コストで追記でき、読み取り時には main と delta を重ね合わせて一貫した像を見せます。

トゥームストーンによる削除と更新

main が不変なら、削除と更新をどう表すのかが問題になります。答えは main の値を物理的に消さず、論理的に無効化することです。各行版に有効/無効を示すビットを持たせ、削除はそのビットを倒す（あるいは delete bitmap の該当ビットを立てる）ことで表します。この無効化マーカーが**トゥームストーン（tombstone、墓石）**です。

更新は「削除＋挿入」に分解されます。旧版をトゥームストーンで無効化し、新版を delta へ追記する、という追記専用（append-only）モデルです。

DELETE row r:
  main 上の r の validity ビットを 0 にする（物理削除しない）

UPDATE row r → r':
  main 上の r を validity=0 でトゥームストーン化
  r' を delta に追記（valid な新版）

scan:
  for v in (main ∪ delta):
    if v.validity == 1 and visible_at(snapshot_ts):
      yield v   # トゥームストーンと不可視版を弾く

main ∪ delta のスキャンで、トゥームストーンが立った旧版と、スナップショット時刻に不可視な版を弾くのがポイントです。可視性の判定は MVCC のスナップショットに従い、各行版のコミット時刻とクエリのスナップショット時刻を比べます。これにより、マージや GC が走っても実行中のクエリは一貫した像を見続けられます。

周期マージ：delta を main へ畳む

delta は放置すれば肥大化し、(1) 読み取りの重ね合わせコスト増、(2) 未圧縮 delta のスキャンが列スキャンより非効率、(3) トゥームストーンの蓄積、を同時に悪化させます。そこで背景プロセスが周期的に delta を main へマージし、delta を空に戻します。これは LSM-Tree のコンパクションと同根の発想で、ランダムな点更新をシーケンシャルなまとめ書きに均す操作です。

ただし列ストアのマージには、LSM にはない固有の重さがあります。辞書の再構築と再符号化です。

merge(main, delta) → main':
  1. main の有効行（validity=1）と delta の有効行を集める
  2. 統合した値集合から新しいソート済み辞書を作る
  3. 全行を新辞書の ID で再符号化し、列ごとに再圧縮する
  4. main' を別領域に構築し、アトミックに切り替える
  5. 旧 main を参照するスナップショットが消えたら GC で回収

main と delta では辞書が別物なので、単純に連結はできません。両者の値域を合わせた新しい辞書を作り直し、全行を新 ID で符号化し直します。同時にトゥームストーン化された無効行はここで落とされ、main が物理的に詰め直されます。マージは重い一括処理ですが、書き込みパスから切り離された背景処理なので、OLTP のレイテンシには直接乗りません。

マージ中も読み書きは止まりません。新しい main を別領域に構築してからアトミックに切り替えるコピーオンライト方式が定石で、切り替え前の古い main は参照中のスナップショットに見せ続けます。どのスナップショットからも参照されなくなった旧 main は MVCC のガベージコレクションと同じ理屈で回収されます。

マージ契機の調律がすべてを決める

delta-main の性能は、究極的には delta をどれだけ小さく保てるかに集約されます。書き込みレートに対してマージのスループットが上回っていれば delta は小さく保たれ、読み取りは main 主体で高速に走ります。逆にマージが追いつかなければ delta が膨れ、未圧縮 delta のスキャンと重ね合わせが分析を遅くします。

かといってマージを攻めすぎると、辞書再構築と再符号化の CPU・I/O コストが書き込みと競合します。SAP HANA の二段構成（L1 → L2 → main）は、まさにこの調律を段階化したもので、軽い L1→L2 マージを頻繁に、重い L2→main マージを稀に走らせることで、書き込み即応性とマージ負荷のバランスを取っています。契機・粒度・段数の設計が、書き込みと読み取りのどちらにどれだけ余力を回すかを決めるわけです。

まとめ