Open3
Zig製の分散型金融取引向けデータベースTigerBeetleのメモ
coalgTigerBeetleとはどんなヤツなのか
公式サイト
TigerBeetle - Track Financial Transactions at Scale | TigerBeetle
安全性（耐障害性）・高パフォーマンス・（金融システムとしての）開発体験に重きを置いたDBであることを謳っている。
安全性
- 過酷なストレージ障害モデルでも生き残る
- 例
- 間違ったディスクセクタに書き込むファームウェア
- ディスクを誤って表示するカーネルページキャッシュ
- ログファイルの破損を検出できないファイルシステム
- 例
- Jepsen Testを公開している人がいるようだ
高パフォーマンス
- インメモリDBより高速だが、トランザクションごとにレプリケーションされた永続化を行う
- キャッシュ行アラインメントによるゼロ・デシリアライゼーション
- Direct I/Oによるゼロコピー
- io_uringsによるゼロシステムコール
- メモリ（とストレージの）静的アロケーション
開発体験
- T字勘定モデルをデフォルトで組み込んでおり、アドホックなSQLを書くことなくある口座への送金が必ず他の口座の出金になる。
- ストアドプロシージャを使うことなく、データベース内部で単一クエリを実行し処理を高速化する
- ユースケースによるだろうが、ビジネスロジック実行のためにネットワーク上でのデータの往来を削減できるため最大で1000倍程度の高速化を達成できると主張している
安全性のデモ
TigerBeetleのコンセンサスアルゴリズムが動作する様子をブラウザゲームにした動画が公開されている。
気合の入ったお遊びをしておりここで興味を持った（ただ何がすごいのかはよく理解できていない）。
17:50あたりから（埋め込みで時間指定済）
ここで出てきているのがTigerBeetle Inc.のCEOでありTigerBeetleのメイン開発者でもあるJoran Dirk Greef。そんなに喋るのが得意そうじゃない（が言いたいことは的確に伝わってくる）のが好印象を持った。
TigerBeetleのSNSでの評判を探る
Phil Eaton（EDB Postgres（エンタープライズ向けのPostgresSQL）開発者）
（2022年の情報である点に注意）
ぶら下がったツイートでTigerBeetleに関心を持つ理由を以下のとおり述べている。
- データモデリング
- 口座と送金というプリミティブなデータモデルを提供している
- 振替を挿入し、必要に応じて借方/貸方がバランスすることを問い合わせる
- 会計指向のビジネスロジック
- 口座の借方が貸方を上回るような送金を拒否するフラグを設定可能
- 送金のグループを受入/拒否することも可能
- ビルトインのコンセンサス
- VSR（Viewstamped Replicationアルゴリズム）を実装している（参考論文）
- データ破損からの回復
- TigerBeetleはプロトコル非依存リカバリー（Protocol Aware Recovery）によりとてつもないレベルのデータ破損から復旧可能（ただし詳細はPhil氏もよく分かっていないとのこと）
- ツリーでTigerBeetleのツイートを引用しており、実装の根拠論文として以下の箇所が挙げられている
- パフォーマンス
- 金融用途のワークロードに特化することで100万件/sのデータを転送しつつビジネスロジックとデータバリデーションも可能になる
- OSS
- Apache 2.0でありBSLになる心配がない
HNでの評判
-
TigerBeetle raises $6.4M to power the future of financial accounting infra | Hacker News
- 作者のJoran Greefらも現れて結構フレンドリーに話し込んでいる
- 開発者の実力
- JoranはZigの標準ライブラリにio_uringを突っ込んだエンジニアとのこと
- std: add io_uring library by jorangreef · Pull Request #6356 · ziglang/zig
-
金融エンジニアの疑問
- 2つの口座間の送金がアトミックに実行されることは基本的にあまりない。例えば口座Aから引き落とし口座Bに振替する処理を考える。アカウントAから資金をプールする中間口座に振替する前に、いくつかのビジネスチェックやデータ操作を行う。そしてプール用の中間口座から口座Bに振替する。これはビジネス上の要求によるものだがかなり時間がかかり、場合によって1日以上かかる。「積立（Reserve）」や「決済（Settle）」という口座振替のためのセマンティクスがうまく機能する理由もこれである。こうした概念の上にあらゆる高次のビジネスフローを構築できる。サブスクリプション、約定弁済などである。
- 口座振替は日次/週次/月次の取引回数や取引量など多くの速度制限により律速される。これはユーザーの本人確認レベル、反社ルール、システム内の顧客の年齢など様々な要因に左右される。口座は低い限度額から始まり、システム内で口座が年齢を重ねるにつれて限度額が徐々に引き上げられる。こうした処理をスケールさせるのは大変な苦痛を伴うことだった。
- 限度額のカウンターがボトルネックになるのだ。例えば1日に100万件のトランザクションを行う人気の商店があるとする。その口座に限度額チェックを100万回かけると、その加盟店口座がホットスポットになってしまう。こうしたことをいつかブログにまとめてダンプしたほうがいいかもしれない。
- 作者コメント「2相の積立/決済セマンティクスもプリミティブでサポートしてるよ！」
- メタデータの扱いってどうなるの？
- 作者「ここを読んでね！ TigerBeetleのメタデータフィールドは既存のDBの行にリンクすることができるよ！」とのこと
coalgTigerStyle!
TigerBeetle Inc.が運営しているSystems Distributed (Online!)というカンファレンスの動画を見ていく。JoranがTigerStyle!と銘打ってTigerBeetleでの開発体験がどのようになるのかを紹介している。
テクニカルな詳細には踏み込まず、多岐にわたる原則論を展開している。関心がある点だけまとめていく。
- TigerStyleとは
- 古の武道家のようなもので、いきなりコードを書き始めることなく、まず自制する訓練から始まる
- システムの開発はコーディングだけでなく設計段階からテスト、運用からインシデントまでの全体から成り立っており、それらの全体観を養う
- 時間 = 設計 + コーディング + テスト + 本番インシデント
- それは設計目標を達成できているか？それは価値を生むのか？ビジネスを活性化させるのか？マーケティングに影響を与えるのか？といったところまで見据える
- 「焦るな。1時間～1日かけて正しく設計することで、数週間～数ヶ月の時間を失うことを避けることができる」
- エドガー・ダイクストラの名言「シンプルでエレガントなシステムは設計を容易かつ迅速に行うことができ、かつ正しくより実行時も効率的になり、さらに十分に高い信頼性を獲得する傾向がある」
- テストはシステム開発を支配する
- 複雑なシステムは開発期間と同じくらい、場合によってはそれ以上のテスト期間がかかる
- TigerBeetleのようなDBのバグを見つける時はJepsen Testingを回すのが有効だが、バグを再現するのに実行にものすごい時間がかかることがある
- TigerBeetleには「タイムマシン」機能があり、テストフェーズをコーディングフェーズの一部に縮小することができる
- システムの4色
- ネットワーク、ディスク、メモリ、CPUの4色
- レイテンシと帯域で2つのテクスチャ
- 4x2で8次元の尺度からシステムの形が決まる
- ネーミング
- ネーミングは難しい
- 名詞と動詞を正しく決めることが問題領域のメンタルモデル形成にも役立つ
- TigerBeetleのドキュメントではネーミングの指針を公開している
- 障害モデルを定義する
- ハードウェア障害モデルを考える
- 「システムの4色」それぞれについて障害モデルを考えられる
- 例として、メモリエラーについてはECCメモリを使っていると言えば終わりだが、メモリアロケーションの失敗はプログラムで正しくハンドリングする必要がある
- 大規模なCPU障害を考慮するとECCメモリでも十分でない可能性がある
- ビザンチン障害を考えると問題はいくらでも難しくなるが、そのシステムが許容すべき障害が何であるかを確定するのが重要
- ステートレスはステートフルより良い
- 状態を持つと問題は途端に難しくなる
- ディスクに状態を読み書きしていると、ディスク書き込みが遅くなったり少し腐ったりしたときに問題の把握が難しくなる
- システムの界面領域を可能な限り小さくする
- アサーション
- ミッションクリティカルなコードでは実行時に期待されるコードをシンプルなコードで検証すべき
- 本番環境にもアサーション入れるべき。ミッションクリティカルにおいてはシャットダウンしない代償と問題を検出してその場でシャットダウンする代償を比較したら前者のほうが遥かに大きい
- アサーションは二次的な効果としてコード中の不変性を文書化することにつながる
‐ システムの制約を知る - （かなり重要なことを言っていると思うがうまく要約できる気がしない…）
-
assert(mem.eql(u8, block_cache, block_disk))- ある箇所でキャッシュがディスク上のデータと同じであることを検証するプログラム
- 特定のワークロードで失敗しデバッグに8時間を要した
- 0031: 2022, systems distributed, random ids, deleting tombstones, disorderly compaction, juggling blocks, code review woes, holiday shutdown, searching for implementors, everything is copy, sharing the page cache after fysncgate, 9/10 climbers, rise and fall of peer review, real-world concurrency
- シャーロック・ホームズの推理小説のようだが、こうしたアサーションでバグを検出しないと、本番環境で問題を引き起こす、解決に数ヶ月から数年を要する壊滅的なバグに発展していただろう
- Zigについて
- メモリ操作がしやすくアサーションが書きやすい。DB開発にとってメモリ操作がほぼ全てなので十分
- 算術演算に多数のアサーションがデフォルトで入っている
- マクロでコンパイル時にアサーションを実行できる。実行時でなくコンパイル時に検証タイミングを昇格できる
- タイムマシン
- TigerBeetleではシミュレータでプロセッサやレプリカ間のネットワーク、実行されているディスクなどをシミュレートしている
- シミュレータ上でランダムなネットワークやストレージの遅延・分断・破損の障害を注入して検証を行う
- アサーションが失敗した場合その失敗箇所を数秒で何度でもリプレイしてデバッグできる
- このデバッグは楽しくマッハ10が出ているように感じるほどだ
- シミュレータを作ってから3週間で30個もの分散処理関連のバグを潰した。毎日アドレナリンが出るのを感じ、これまでにない速度だった
coalg秒間100万件の金融トランザクション
（視聴後）このプレゼンは知りたいことに答えている。
- TigerBeetleが必要とされる背景の説明
- Adrian Hope-Bailie
- W3C Web Payments WGの元共同座長（co-chair）などを歴任してきた人物
- リップル社でInter-Ledgerプロトコル（台帳の標準化プロトコル）の策定にも参加
- Adrian Hope-Bailie
- 決済の現実
- 厳格な要件
- 金融システムではデータの逸失が許されず、データは完全にトレースできる必要がある
- 金融の分散システムは複雑で巨大で高コストになりがち
- 口座ごとに制限されるスループット
- 口座がシャーディングの単位であり口座ごとにクエリを投げるのでスケールしない
- 同じ口座に影響を与えるトランザクションを並列実行できない
- 一般的な水平スケールやシャーディングが不可能
- 口座の残高は共有状態であり、トランザクションごとにロック・アップデート・リリースを行う必要がある
- Adrianが策定に参加していたInter-Ledgerプロトコルもこの課題に直面していた
- 大量かつ少額の決済に対応する必要
- 結局口座ごとのシャードという壁にぶつかるため、トランザクションがすぐ飽和してしまう
- 現実の決済の大部分は国を跨がないし、特定のサイロ化された地域内でほとんどのお金が循環しているし、通貨ごとの制限もあるので、こうした決済トランザクションがグローバルにスケールしない問題が顕在化していない
- 暗号通貨が流行った背景にグローバルな決済ネットワークを構築した点にある
- こうしたマイクロペイメントやオープンペイメントの需要は明らかで、世界中で迅速かつ容易にできるシステム構築手法が必要とされている
- 厳格な要件
- TigerBeetleの問題解決手法の説明
- Donovan Changfoot
- TigerBeetleのエンジニア。空気圧縮式水ロケット打ち上げの高さギネス記録を持っているらしい
- Donovan Changfoot
- 決済における方程式
- 1決済につき20のデータベースクエリが発生する
- これがありがちな現在のシステム
- ネットワークホップもクエリの数に比例して増加する
- 1決済につき1のデータベースクエリが発生する
- ストアドプロシージャによりクエリを一つにまとめあげる
- ビジネスロジックを入れ込むことができない、せいぜい1ケタの改善にとどまるという制約がある
- 1決済につき1/10,000のデータベースクエリが発生する（1データベースクエリで10,000決済を行う）
- これがTigerBeetleの「すべてはバッチ処理である」という発想
- fsyncやネットワークホップの償却、同じ関数呼び出しはCPU命令にキャッシュロードする
- JavaScriptでMVPを作ってみたところ、200,000トランザクション/sの性能を発揮した
- プロトタイプがうまくいったので次は実装言語を選んで最適化を図ることに
- CやC#やRustなど色々あったがZigを選定した
- 1決済につき20のデータベースクエリが発生する
- TigerBeetleが取り組んでいる問題と背景の説明
- Joranを中心に代わる代わる話している
- 3つの柱（安全性、パフォーマンス、開発体験）
- 安全性
- ストレージ障害モデル
- ネットワーク障害モデルほどよく考察はされていない
- PostgreSQLはfsyncに誤った期待（リトライできる）をしており、それによりデータ破損するバグを抱えていた（参考）
- このバグはリトライせずpanicするように修正されたが、実はMongoDBやMySQLなど他のDBも同様のロジックをしていたので同様の修正に追われていた
-
Can Applications Recover from fsync Failures? | USENIX
- 2020年に各DBをテストしたところ、実際にはどれも修正されていなかったことが指摘された
- Postgreの場合、fsyncに失敗するとパニックするにはするが、DBが再起動して壊れたページキャッシュから読み取り書き込みを行う
-
Protocol-Aware Recovery for Consensus-Based Storage | USENIX
- 自称分散ストレージがビット破損とシステムクラッシュを区別できていないことを指摘
- 単一ストレージのデータを守れないどころかコンセンサスアルゴリズムによって破損が伝播する可能性も提示
-
ZFS: The Last Word in File Systems
- ストレージ破損、誤った書き込みや読み取りを正しく復帰する手法を示した
- デイジーチェーンやハッシュチェーンによるチェックサムにより解決
-
the major availability breakdowns and performance anomalies we see in cloud environments tend to be caused by subtle underlying faults, i.e., gray failure rather than fail-stop failure.
- Gray Failure: The Achilles’ Heel of Cloud-Scale Systems
- クラウド環境における可用性の低下問題は厳格なフェイルストップではなく微妙なパフォーマンス異常（グレー障害）が起きがちである
- ネットワーク障害モデル
- パケットは…
- 再送されうる
- 遅延しうる
- 破損しうる
- 誤ったアドレスに向けて送られうる
- 時間障害モデル
- NTPサーバがネットワーク分断された場合など
- Marzullo'sアルゴリズム
- ノイズの多い複数の時間ソースから下限と上限を確定するためのコンセンサスアルゴリズム
- TigerBeetleでは
src/vr/clock.zigに実装されている
- 人的障害モデル
- TigerBeetle自体にもバグを埋め込みうる
- 少なくとも2つの関数に2アサートを入れ込むことでバグを検出する構え
- エラーハンドリングでなくアサートを使う理由は、何か期待値と違うことが起きた場合にエラーをハンドルして処理を継続するのは無意味だからである
- ストレージ障害モデル
- パフォーマンス
- コントロールプレーンとデータプレーン
- TigerBeetle内部で明確に区別することにより設計をシンプルかつ高速性を保つ
- TigerBeetleが使うテクニック
- バッチ処理
- 上で述べた通り
- ゼロアロケーション
- TigerBeetleは事前に起動時にすべての必要なメモリを決定し、実行時にアロケーションを行わない
- 隠れたアロケーションを行わないというZigの哲学を体現したもの
- ゼロデシリアライゼーション
- ネットワーク送受信するデータは固定長バイトと決め打ちする
- 固定サイズにすることでコピーやデシリアライズのコストを払わない
- 全てのデータは最大64バイトのキャッシュラインにアラインメントされる
- ゼロコピー
- CPUのブロックを可能な限り避ける
- メモリのコピーやデータコピーを可能な限り償却し、L1-L3キャッシュヒットミスを避ける
- キャッシュヒットミスの削減はDirect IOと同等の効果をもたらす
- 7%程度の高速化
- ゼロシステムコール
- nvmeデバイスなど一部のストレージデバイスを使用したDirect IOでのスループットは非常に高速
- カーネルへの同期システムコールの実行は1ms～2msで通常のIO操作と同じオーダーになってしまう
- カーネルとユーザー間のコンテキストスイッチのコストは大きい
- カーネルスレッドプールをデータプレーンとして使う
- io_uringによりユーザスペーススレッドプールでasync I/Oをエミュレーションするためのコストを払うことなく同等のことができるようになる
- スループットが2倍に
- io_uringによりユーザスペーススレッドプールでasync I/Oをエミュレーションするためのコストを払うことなく同等のことができるようになる
- バッチ処理
- 開発体験
- 「全ては複式簿記である」という発想
-
Evolution of Financial Exchange Architectures - InfoQ
- Martin Thompsonの金融システムアーキテクチャに関する公演
- LMAXの共同創業者
- Lock-freeリングバッファで秒間100万トランザクションを実行する高性能取引プラットフォームを実装した
- 状態複製機械 = 状態（hashmapなど）を伴う機械（障害が起こりうるハードウェア）×複製（耐障害性）
- 我々が考えている文脈ではDBサーバのレプリケーションがこれにあたる
- 状態複製機械の構成要素
- ディスクへのappendコマンド（Redis AOFファイルなど）
- 他のディスクへの複製コマンド
- 状態への適用コマンド（updateのこと）
- 状態複製機械の回復
- 上記のコマンドをあらゆる複製上で同じ順序で実行する
- クラッシュが起きた場合、コマンドの実行ログをリプレイする
- 全てのマシンが同じ状態に到達できる
- 「厳格な直列性（Strict Serializability）」と呼ぶべきもので、これで最高レベルの一貫性が得られる
- TigerBeetleでもZFSでもやっていることは同じで、これらは厳格な直列性を実現する状態複製機械であると言える
- コンセンサスプロトコルで選出されたリーダー以外が障害にあった場合はこれで救える
- ではリーダーが障害された場合はどうなるか？
- Martin Thompsonの金融システムアーキテクチャに関する公演
- Viewstamped Replication
- c.f. ”Viewstamped Replication Revisited" Barbara Liskov, James Cowling (2012)
- コンセンサスプロトコルのパイオニア
- 直感的なラウンドロビン方式でリーダーを選出する
- リーダーが死んだら次の番号の人がリーダーになるだけ
- レイテンシが低いという利点がある
- 安全性