Shirakami: A Hybrid Concurrency Control Protocol for Tsurugi Relational Database System

本論文は、短期トランザクションと長期トランザクションを同時に効率的に処理するために、Tsurugi 関係データベースシステム向けにマルチバージョンビュー直列化と Silo 方式を統合したハイブリッド並行制御プロトコル「Shirakami」を提案し、PostgreSQL よりも大幅に低い遅延と高いスループットを実現したことを示しています。

要約

1. 問題：混雑するスーパーマーケットの悲劇

現代のスーパーマーケット（データベース）では、2 種類の客が同時にやってきます。

1. 短時間の客（ショート取引）
   • 「牛乳とパンだけ買いたい！」という客。
   • すぐにレジを通り、サッと帰ります。
   • 例：スマホの通話料を計算する、在庫を 1 個増やす。
2. 長時間の客（ロング取引）
   • 「全商品の原価を計算して、来月の仕入れ計画を立てる！」という客。
   • 店内をくまなく回り、棚をすべてチェックし、計算して、結果を書き換えます。
   • 例：工場の部品構成（BOM）の再計算、電話会社の請求書一括作成。

【従来のルール（既存のデータベース）
これまでのルールでは、この 2 種類の客が混ざると大混乱が起きました。

• 長時間の客が棚（データ）を調べている最中に、短時間の客が「あ、ここ空いてる！」と思って同じ棚に手を伸ばすと、「衝突（コンフリクト）が起きます。
• 従来のルールは「衝突したら、長い作業をしている客を強制的に中断（Abort）して、最初からやり直させます」という厳しいルールでした。
• 結果： 長時間の客は「また中断させられた！」と怒って、何百回もやり直しをさせられ、いつまで経っても計算が終わらない。スーパーのレジは渋滞し、店全体が止まってしまうのです。

2. 解決策：新しいルール「シラカミ」の登場

この論文の著者たちは、「シラカミ」という新しいルール（プロトコル）を考え出しました。これは、「短時間の客」と「長時間の客」が、お互いに邪魔をせずに共存できる魔法のシステムです。

シラカミは、2 つの異なるルールを上手に組み合わせた**「ハイブリッド型」**です。

① シラカミ・LTX（長時間の客専用ルール）

• 仕組み： 「書き込みの予告（Write Preservation）」という手紙を、作業を始める前に店長（システム）に提出させます。「私は今から A 棚から Z 棚まで全部チェックして書き換えますよ」と宣言します。
• 効果： 短時間の客が「A 棚を使おう」とした瞬間、店長が「あ、LTX さんが今から使う予定ですよ」と教えてくれます。短時間の客は「じゃあ、別の棚で待ちましょう」と判断し、LTX さんの作業を邪魔しないように自ら退散（または待機）します。
• メリット： 長時間の客は「中断させられる」ことがなくなり、スムーズに作業を完了できます。

② シラカミ・OCC（短時間の客専用ルール）

• 仕組み： 従来の「楽観的ロック（OCC）」という、素早く動くためのルールを少し改良しました。
• 効果： 短時間の客は、LTX さんの「書き込み予告」を常にチェックしながら動きます。もし衝突しそうなら、すぐに「ごめん、やり直します」と判断して、他の客を待たせずに素早く処理を完了します。
• メリット： 短時間の客のスピードは落ちません。

③ 「順序の転送（Order Forwarding）」という魔法

これがシラカミの最大の特徴です。

• 状況： 仮に、長時間の客（A）と短時間の客（B）が、同じ棚で衝突してしまったとします。
• 従来のルール： 「B が先に動いたから、A は中断！」となります。
• シラカミのルール： 「A は重要な作業だから優先する。でも、B も中断させたくない。だから、B の作業順序を『A の後』にずらして（転送して）、A が終わってから B が処理するようにします」
• 結果： どちらも中断されず、**「A が先に終わって、その後に B が終わる」**という順序で、どちらも無事に完了します。まるで、渋滞している道路で、大型トラック（長時間客）が先に行き、その後に小型車（短時間客）が追いかけるように、順番を柔軟に調整しているのです。

3. 実証実験：どれくらい速くなった？

著者たちは、このシラカミを実際のデータベースシステム「ツルギ（Tsurugi）」に組み込んでテストしました。

• 電話の請求計算（長時間作業）
  • 従来のデータベース（PostgreSQL）に比べて、19.7 倍も速く終わりました。
  • 従来のシステムでは、長時間の計算が終わる前に時間切れ（タイムアウト）して失敗していましたが、シラカミならサクサク終わります。
• 部品の原価計算（長時間作業）
  • 従来のシステムに比べて、5.6 倍も速く終わりました。
• 混合状態での性能：
  • 短時間の客が大量にいる状況でも、長時間の客が680 倍もの効率で処理を進めることができました。

4. まとめ：なぜこれがすごいのか？

これまでのデータベースは、「短時間の客（普通の買い物）」と「長時間の客（大規模な計算）」を同時に処理するのが苦手でした。どちらかを犠牲にしないと、システムが止まってしまっていたのです。

シラカミ（Shirakami）は、「書き込みの予告」で衝突を避け、「順序の転送」で優先順位を柔軟に調整することで、「短時間の客も、長時間の客も、どちらも幸せに（高速に）を実現しました。

これは、スーパーマーケットの混雑を解消し、レジ待ちをなくすだけでなく、大規模な在庫整理も同時にスムーズに行えるようになる、未来のデータベースのあり方を示す素晴らしい研究です。

---

一言で言うと：
「混雑するスーパーで、大規模な在庫整理をしている人（長時間取引）と、ちょっと買い物をしに来た人（短時間取引）が、お互いに邪魔し合わずに、スムーズに済ませられるようにした**新しい『店長ルール』**です。」

技術概要

Shirakami: Tsurugi 関係データベースシステムのためのハイブリッド並行制御プロトコル

技術的サマリー（日本語）

本論文は、NAUTILUS Technologies 社と慶應義塾大学などの共同研究チームによって提案された、新しい並行制御プロトコル「Shirakami（白神）」と、それを搭載した実用レベルの関係データベースシステム「Tsurugi（つるぎ）」に関するものです。

以下に、問題定義、手法、主要な貢献、評価結果、および意義について詳細にまとめます。

---

1. 背景と問題定義

現状の課題:
現代のビジネスアプリケーション（例：BOM（部品表）管理、通信キャリアの請求処理）では、以下の 2 種類のトランザクションを同時に処理する必要があります。

1. 短時間トランザクション: 通常の OLTP 処理（YCSB や TPC-C に代表される、短い読み書き）。
2. 長時間トランザクション: 大量のデータをスキャンし、集計やコスト計算を行うバッチ処理（例：製品コストの再計算、請求明細の生成）。

既存プロトコルの限界:

• Silo, ERMIA, TicToc, Cicada などの現代的な OCC（楽観的並行制御）: 短時間トランザクションには高性能ですが、長時間トランザクションが競合すると頻繁にアボート（中止）され、スループットが極端に低下します。
• 決定論的プロトコル: 長時間トランザクションには適していますが、サブクエリを含む SQL や動的なアクセスパターンには対応できず、実用的な RDBMS には適用が困難です。
• Oze などの MVSR（マルチバージョン・ビュー・シリアライザビリティ）: 広いスケジューリング空間を持ちますが、実装例が少なく、短時間トランザクションの性能が低く、プロトコルの切り替えが必要でレイテンシが増大します。

解決すべき問い:
「本番環境のデータベースにおいて、一貫性を保ちながら、長時間のバッチトランザクションと短時間のオンライントランザクションを共存させ、効率的に処理するにはどのようなプロトコルが必要か？」

---

2. 提案手法：Shirakami プロトコル

Shirakami は、短時間トランザクションと長時間トランザクションをそれぞれ最適なプロトコルで処理し、それらをシームレスに統合するハイブリッド並行制御プロトコルです。

2.1 構成要素

1. Shirakami-OCC (S-OCC):
   • 対象: 短時間トランザクション。
   • 基盤: Silo プロトコルをベースに改良。
   • 特徴: 従来の OCC と同様に高いスループットを維持しつつ、長時間トランザクションとの共存を可能にするためのメカニズム（後述の WP や Epoch）を実装。
2. Shirakami-LTX (S-LTX):
   • 対象: 長時間の読み書きトランザクション（バッチ処理など）。
   • 基盤: 多バージョン・ビュー・シリアライザビリティ (MVSR) に基づく新しいプロトコル。
   • 特徴: 競合空間を Conflict Serializability (CSR) よりも広く取り、誤検知（False Positive）を極力減らす設計。

2.2 主要な技術的メカニズム

• Write Preservation (WP: 書き込み保持):
  • S-LTX トランザクションは開始時に、どのデータ領域を書き込む予定かを宣言（テーブルレベル）します。
  • S-OCC トランザクションは読み取り時に、この WP 情報を参照します。もし競合する書き込みが予定されている場合、S-OCC は即座にアボートするか、待機することで、長時間トランザクションが完了する前に競合で失敗するのを防ぎます。
• Order Forwarding (順序転送):
  • 優先度の低い S-LTX トランザクションが、優先度の高いトランザクションによって書き込まれたデータを読み取った場合、直ちにアボートするのではなく、シリアライズ順序を動的に変更します。
  • 具体的には、低優先度のトランザクションの順序を、高優先度のトランザクションと同じ Epoch に「転送（Forwarding）」させ、順序を逆転させることでコミットを成功させます。これにより、MVSR の広いスケジューリング空間を活用し、アボートを大幅に削減します。
• Epoch ベースの同期と優先度管理:
  • 全トランザクションは「Epoch（時間区切り）」に割り当てられます。
  • 優先度: S-LTX > S-OCC。S-LTX は常に S-OCC より優先され、S-OCC が S-LTX の進行を妨げることはありません。
  • S-LTX は次の Epoch の開始時に実行され、S-OCC が完了したスナップショットを基準に読み取りを行います。
• ファントム読み取りの回避:
  • S-LTX の Order Forwarding により生じる可能性のあるファントム読み取り（Predicated Read）に対して、S-OCC のコミット時に predicated read の検証を行うことで一貫性を保証します。

---

3. システム実装：Tsurugi

Shirakami は、NAUTILUS Technologies 社が開発した実用レベルのメモリ内 RDBMS「Tsurugi」のトランザクション処理モジュールとして実装されています。

• アーキテクチャ: モノリシックではなくコンポーネントベース。
  • SQL エンジン (Jogasaki): DAG 形式のデータフローで並列実行。
  • インデックス (Yakushima): Masstree をベースにした並列木構造。
  • ログ/ストレージ (Limestone): 非同期永続化とスナップショット管理。
• 特徴: 多数のコアと大規模メモリを前提とした設計。サブクエリを含む SQL をネイティブにサポート。

---

4. 評価結果

実験環境は、Intel Xeon Platinum 8580 (120 コア/240 スレッド) を搭載したサーバーです。

4.1 実世界ベンチマーク結果

1. 通信キャリア請求処理ベンチマーク:
   • 大量の通話履歴と顧客契約情報を照合するバッチ処理と、リアルタイム更新を同時に行うシナリオ。
   • 結果: 並列度が高い状況（16 スレッド）において、Tsurugi は PostgreSQL よりも19.7 倍低いレイテンシ（高速）を達成。
   • PostgreSQL は 64 スレッドでベンチマーク時間内に完了しませんでした。
2. BOM（部品表）ベンチマーク:
   • 食品製造業における製品コスト計算（木構造データの走査と集計）。
   • 結果: Tsurugi は PostgreSQL より5.6 倍高速でした。
   • PostgreSQL を READ COMMITTED に設定すると Tsurugi より速くなりましたが、データ不整合（アノマリー）が発生し、実用不可でした。

4.2 Shirakami プロトコル単体の評価 (YCSB ベース)

• シナリオ: 短時間トランザクションと長時間トランザクションを混在させた負荷。
• 結果:
  • 長時間トランザクションの長さが 1000 操作以上の場合、S-LTX は S-OCC よりも680 倍高いスループットを達成しました。
  • S-OCC のみでは、長時間トランザクションが競合により頻繁にアボートし、スループットがゼロに近づくのに対し、S-LTX は安定してコミットを完了しました。
  • 短時間トランザクションのみの負荷では、S-OCC と同等の性能を維持しました。

---

5. 主要な貢献と意義

1. ハイブリッド・アーキテクチャの確立:
   • 短時間トランザクション用（S-OCC）と長時間トランザクション用（S-LTX）の 2 つのプロトコルを、動的な切り替えなしに統合し、それぞれが互いの性能を阻害しないように設計しました。
2. 実用レベルでの MVSR 実装:
   • 理論的には MVSR の有効性は知られていましたが、サブクエリ対応や実用的な RDBMS として実装されたのは本稿が初めてです。Order Forwarding による「誤検知の排除」が鍵となっています。
3. 生産環境での実証:
   • 単なる研究プロトタイプではなく、Tsurugi として実用システムに組み込まれ、通信や製造業などの具体的なユースケースで PostgreSQL を凌駕する性能を示しました。
4. HTAP（ハイブリッド・トランザクショナル・アナリティカル・プロセッシング）への貢献:
   • 従来の RDBMS が抱えていた「OLTP（オンライン処理）」と「OLAP（分析処理/バッチ）」の分離（夜間バッチ実行など）を解消し、リアルタイムで両者を統合処理する基盤を提供しました。

結論

Shirakami は、現代の複雑なビジネスワークロード（短時間トランザクションと長時間バッチの混在）に対して、既存の単一プロトコルでは達成できない高効率と一貫性を両立させる画期的なソリューションです。特に、長時間トランザクションの成功率とスループットを劇的に向上させつつ、短時間トランザクションの性能を維持する点において、次世代データベースの重要な指針となる研究です。