データベースと分散トランザクションの振り返り
リスナーのみなさん、こんにちは。London Tech Talkへようこそ。
イギリスのロンドンからお届けしています、Ken Wagatsumaです。
本日は、London Tech TalkのBookclub、Database Internalsの振り返り収録をしていきます。
今回は、Chapter 13、Distributed Transactions、分散システムにおけるトランザクション処理、分散トランザクションについて振り返っていきます。
本書の振り返りに入る前に、13章まで一緒に読んできてくださったリスナーの方や、Bookclub参加者のみなさん、お疲れ様です。
もうすぐ、14章、最後の章を読み終わるところまで来たと思います。
8、9割くらい読んできたと思うので、本を読まずに、このエピソードの収録を聞くことでついてきているようなリスナーの方も、もう少しで読み終わるところまで来たと思います。
まずは、一旦ここでこれまでの努力を称えつつ、
残り13章、14章は分散トランザクションなり、コンセンサスアルゴリズムなり、なかなかハードで、文量も厚い章となってきますので、気を抜かず最後の2つの章を頑張っていきましょう。
読む前は、このデータベースインターナルズも、昔Bookclubで取り扱ったデータベースインターナルズとか、あとSRE界隈でいうとGoogleのSREブックであったり、システムパフォーマンスみたいな、割と分厚めの本と比べると、ページ数も少なくて、フォーカスもデータベースの実装の詳細というところにスコープが割と狭められていたので、
DDIAとかよりは割とサクッと読めるんじゃないかなという期待、緩い期待の下を選んできましたが、やっぱりちょっとなかなか内容も難しめというところで、結構頑張りながら読んできた方も多いんじゃないかなと思いますが、
あと2章となっています。今回の第13章の振り返りにいこうと思うんですが、今回の章の目玉はトランザクションですね。
具体的な旅行の予約例
トランザクション、分散環境においてトランザクションと呼ばれるのが堅苦しい定義を与えると、一連のデータベース操作をアトミック、分解不可能な、いわゆる最小限の原始的な実行単位として扱うトランザクションを分散環境でどうやって実現しますかというところが、
今回の章の目玉になってきていますね。こういったものをアトミックコミットメントというアルゴリズム名で表現するらしいんですけれども、要するにアトミックコミットメントのアルゴリズムについての理解を深めることです。
ちょっと時間が空いてしまったので、軽く前回の振り返り収録のおさらいからいきましょう。
チャプター12ではアンチエントロピーとディスエミネーションについて学びました。
大規模な分散システムにおいて、データベースのメタデータ、例えばクラスターの状態、IPアドレスとかマスターノードの状態といったメタデータを配信していくにあたって、アンチエントロピーとかゴシッププロトコルのようなアルゴリズムについて勉強しました。
具体的にはRead RepairとかDigest Read、Hinted Handoffといったアンチエントロピーアルゴリズムの仕組みを12章では見ましたね。
後半ではゴシッププロトコルについても軽く触れました。
それらを実現するためのデータ構造としては、例えばGitコマンドでも使う、裏側でも使われているようなMercuryとかについても学びました。
そしてそれらを踏まえた上で、今回はその分散システムの中で実際にデータですね、メタデータではなくてデータベースが扱うためのデータ、
例えばSNSだったらユーザーテーブルであったりとか、フィードテーブル、メッセージテーブルといったようなデータに対する複雑な操作をAtomicに実行していくというさらに挑戦的な問題に取り組んでいきます。
ここでまず分散トランザクションの難しさを身近な例で捉えてもらうために、具体的なシステムのアプリケーションの例を紹介しようかなと思います。
今回はアナロジーというよりは具体的な例となっています。
ちょうど夏休みも終わって、ちょっと秋口で忙しい頃かなと思うんですけれども、
今年の夏とか海外旅行に行った方も多いかもしれませんし、行かなかった方もいるかもしれません。
もしくは年末年始の海外旅行のプラニングをしているかもしれませんね。
ということで皆さん、海外旅行をプラニングするときに複数の都市を例えば巡るとか、
あとはその旅程の間でそれぞれの何回か飛行機に乗ったり各都市のホテルをブッキングするときに、
いろんなブッキングしなきゃいけないものがありますよね。
航空券とか電車とかホテルみたいな。
もしくは現地のレンタカーを予約する必要があるかもしれませんね。
そういったときにその予約プロセスにおける各チケットのトランザクションをちょっと考えてみましょうと。
例えばロンドンからパリ、フランスのパリを経由して、
ローマみたいなその旅程でちょっと夏休み2週間ぐらいロンドンから旅行したいなという予定を組んだとしますと。
その予定を今計画していて、それぞれの区間の航空券もしくはトレインですね。
例えばロンドンからパリはユーロスターで電車で行って、
パリからローマは飛行機で行って、
それぞれパリとローマではホテルのブッキングしなきゃいけない。
イタリアの先では現地でちょっとレンタカーを予約して移動したいので、
レンタカーを予約したいみたいなケースだったとしますと。
このときに予約するときに、
仮に全ての予約をbooking.comとかそれぞれのexpediaとかで一つ一つ予約するじゃなくて、
その予定を提案したら裏側で全て必要な、
例えばホテル付きの航空券みたいなのがありますよね。
そんな感じで、航空券とホテルとレンタカーみたいなのを合わせて予約してくれる仕組みがあるとします。
実際にそういうシステムもありますよね。
このときにこれらの予定、予約というのは、
基本的には全て成功するか全て失敗するかのall or nothingというか01のバイナリーであってほしいんですよね。
例えば予約するときにロンドンからパリのユーロスターとパリのホテルとローマのレンタカーを取れたけど、
パリからローマに行くときの飛行機券は取れませんみたいな感じになってしまうと、
ホテルは取れたけど航空券が取れなかったりすると旅行全体が台無しになってしまう可能性がありますよね。
なのでそのall or nothingのトランザクションを実現したいと。
しかし現実には色々な問題が発生します。
例えば航空会社のシステムが一時的にダウンしていて、航空券の予約確認が取れなかったりとか、
あとはホテルの予約システムがレイテンシングがすごく遅くて、いわゆるウェブサイトが重いという状態ですね。
レスポンスが返ってこなくてタイムアウトが発生してしまったりとか、
あとはイタリアの現地のレンタカー会社のシステムでは予約が成功したけれども、
非同期ジョブのメール配信システムみたいなのが壊れていて、
待てど待てど確認メールが届かないみたいなケースがあるかもしれませんね。
このような状態の中で、それぞれのトランザクションを分散環境で、
全ての予約が確実に成功したかどうかというのを確認したいんですよね。
ユーロスターのトランザクションは確認しました。
パリからローマの飛行機のトランザクションは確認できました。
レンタカーは確認できました。
全ての予約が確実に成功したかどうかというのをどうやって確認するかで、
かつもし一部が失敗していたら、全ての予約をキャンセルしてもう一回やり直したんですよね。
例えば一部のイタリアに行く便が取れなかったとして、
そこの他の前後のホテルの日程とかと合わせて、
もう一回予定をずらして取らなきゃいけないケースとか、
あとホテルの場所を変えなきゃいけないケースとか、
飛行機の時間を変えなきゃいけないケースというのがありますよね。
こういう何箇所か行く旅行って結構ピタゴラスイッチみたいになりがちで、
乗り換え、トランジットの時間とか結構シビアになってきたりすると、
トランジットがうまくいかなかったり遅延してしまったがゆえに、
旅行の予定の後半にドミノ崩し的に影響が出てしまうみたいなケースもありますよね。
なので全ての予約が成功するかどうかみたいな、
一部が失敗していたら全ての予約をキャンセルしたい、
みたいなことを実現したいんですよね。
基本的にはこの分散トランザクション、
2PCアルゴリズムの説明
今日はキーワードとしては2PC、2 Phase Commit とか3PC、3 Phase Commit みたいなのも紹介していくんですけれども、
これが分散トランザクションが解決しようとしている根本的な問題なんですね。
いくつかのチェックポイントがあって、そこでトランザクションしたいと。
でも複数の分散のトランザクションが発生していて、
それを全て成功するか、一部が失敗していたら他のすでにトランザクション仕掛けした、
チェックアウトをキャンセルしたい、みたいな、
そういった分散環境における複数のトランザクションを実現するというアルゴリズムをやっていきます。
なので、今回の章を読む目的を改めてリフレーズしてみると、
整合性を実現するためには各箇所でのロックが基本的には必要なんだけど、
整合性を下げることなくロックによるコンテンションを可能な限り最小化できる、
パフォーマンスの良いトランザクションアルゴリズムを探求するその醍醐味を感じるというところです。
先ほどの予定のシステムにおけば、
全てのシステムとやり取りするところで、
一箇所のロックを作っておけばいいかなというのが基本的にはすぐ思いつく発想なんですけど、
それだと全然パフォーマンスが出ない、その一箇所のロックによってパフォーマンスが下がってしまうので、
パフォーマンスを犠牲にせずに、でも整合性を実現しながら、
プラクティカルな現実的な範囲で動く分散トランザクションのシステムというのは、
どのようなアルゴリズムを使えばいいのかというところをやっていく話になっています。
ということで、まずは基本となる分散トランザクションといったら、
これを避けては説明できない、まず2PCからいこうと思います。
本書ももちろん2PCから説明が始まっていますし、
ネットの分散トランザクションとかデータベースの記事を読むと、2PC、3PCはよく出てくるんじゃないかなと思います。
数字の2にPCと書いて2PCです。
PCというのは、2 Phase Commit、フェイズのコミットのその頭文字を取っています。
日本語だと2層コミットとかって言ってた気がしますね。
ということで、まず2PCから見ていきましょう。
2PCは最も基本的で広く使われている分散トランザクションアルゴリズムですね。
2PCのシンプルさと確実性からMySQL、PostgreとかMongoDBなどでも
2PCとその特徴
多くの実用的なデータベースシステムで昔から実装されています。
この2PCの2はどこから来ているのかというと、
この分散トランザクションの最終的な確認までのワークフローを2つのフェーズに分けるんですね。
第1段階がプロポーズフェーズと呼ばれています。
第2段階がコミットもしくはアボートと呼ばれるフェーズです。
まず第1段階のプロポーズフェーズではコーディネーターが各個方との参加者に対して
トランザクションの準備を依頼するわけですね。
そのコミット可能かどうかの投票をプロポーズするわけです。
この結果でコミットしていいですかどうかというところを投票を求めますと。
それに対して全ての個方とがプロポーズリクエストに対してイエスかの答えています。
そのコーディネーターのもとに全ての個方との参加者からイエスが返ってきたら第2段階でコミットリクエストを受けます。
そのコミットリクエストをもらった個方とたちは実際にコミットリクエストをもらって初めてトランザクションのステートをコミットにすると。
一方一つでも第1段階のプロポーズリクエストに対してノーがあれば逆にコーディネーターはアボートリクエストですね。
キャンセルするようにリクエストをしてそれを受け取った個方とたちはやり直す。
1回キャンセルしてもやり直すという形になっています。
ブッククラブでちょっと紹介したアナロジーがあるんですけども、
2PCを意思決定における実際の現実の例促しというなら会社のチームリーダー、ちょっとこうみんなを引っ張っていくタイプのアップアウトな会社のチームリーダーみたいな存在かなと思っています。
要するにこのここでの分散トランザクションっていうのは人間の世界に置き換えると複数にいる人たちの中での意思決定なんですよね。
それぞれのみんなで意思決定をして何か最終的に結果を決めてそれに向かって突き進んでいくための意思決定をしなきゃいけないというところになって。
例えば今の例でいうと2PCというのはチームリーダーみたいな感じで参加者に一応ヒアリングをしつつその合意結果をもとに仕事を進めるんですけども、
最終的にはそのチームリーダーがみんなの意見を聞いて意思決定をすると、コミットするかアボートするかみたいな感じですね。
この途中で例えば参加者、参加者というかチームメンバーが風邪で休んでしまったりとか後はちょっと行方をくらましてしまったりしても割と置いてきぼりにしていってます。
体調を復帰してチームに戻ってきたと思えば今日までここまでキャッチアップしておくようにみたいな仕事を目の前に山積みにさせてしまっているような状況ですね。
これは2PCのノードの例でいうと途中で参加ノードがクラッシュしてリストアしたりミティゲーションしたりして戻ってきた後に溜まっているログがあるわけですね。
それを処理しなきゃいけないわけなんですよ。
2PCのポイントとしては平常時は仕事はどんどんどんどん進む一方でコーディネーターと呼ばれる会社のチームリーダー依存の構造なので逆にリーダーが仕事を休むとチームが機能不全に陥ってしまうんですね。
これは2PCはブロッキング特性があるとも呼ばれているゆえんでもあります。
このコーディネーターが機能不全に陥ると基本的に意思決定は最終合意に至りません。
3PCの改善と特性
この2PCのブロッキング特性を何とか改善しようとしたのが3PCと呼ばれる改善型のアルゴリズムです。
3PCは名前の通り3フェーズなのでフェーズを一つ増やしてますね。
2PCにあるプロポーズと最終的なコミットアボートの間にプリペアというフェーズを増やしてます。
なぜこのフェーズを増やすことによって2PCのブロッキング特性を軽減できるのかというのを説明しますが、
3PCではまずプロポーズ第一段階というのは今まで通り各参加者にプロポーズをしますと。
コミットする前にプリペアというコミットと呼ばれる追加のフェーズが設けられるんですが、
合意されたトランザクション結果が本当にそれでいいのかというのをここで改めて最終確認を取るんですね。
これまた3PCは別のアナロジーを紹介したんですけども、
アナロジーで言うなら3PCのコーディネーターは2PCにおけるアップアウトな会社のチームリーダーと比べて、
どちらかというとスイスのような完全民主主義国家の議長みたいな感じかなと僕は思いました。
これどういうことかというと、例えば2PCが何て言うんでしょうね、
イージーゴーインというか意思決定に対してコーディネーター依存であるつつも割とそのコーディネーターのスピードで進むのに対して、
3PCというのは慎重派ですと。
完全民主主義国家なので全員の合意を対質にするんですね。
民主主義者ですと。
合意された結果で行動する前に改めてプレペアトゥコミットフェーズで最終確認を取りますと。
ただ動きが遅い分ですね、一度決まった結果に対してはもうそのアライメントが取れているので、
例えば第2のプレペアトゥコミットフェーズを終わった後は、
もしそこで議長であるコーディネート役が風邪で寝込んだとしても、
参加者全員は合意結果に賛同しているためプロジェクトに進むことができますと。
2PCの場合はブロッキング特性があるといった通り、
そのコーディネーターが機能不全に落ちると意思決定ができないんですけれども、
3PCはそのコミットアボートの前に仮に機能不全に落ちたとしても、
そのアライメントが第2段階で取れているので、
参加者全員はトランザクションをそれぞれのローカルのステートで処理することができるということですね。
もちろん3PCでも完全な対象外製を兼ね備えているわけではなくて、
あくまでステップを増やしただけなので、
その第1段階、第2段階の間でネットワーク障害があったりとか、
ネットワークパーティションみたいなのが起こったりして、
メンバー間でコミュニケーションが取れなくなった場合には、
それぞれのスプリットブレインみたいな感じでグループが暴走してしまうケースは避けられないんですけれども、
あくまで2PCが持っていたブロッキング特性をフェーズを増やすことによって克服しようという話がありました。
カルビンとスパナーのアプローチ
簡単にラップアップすると、2PCはブロッキングな特性がありました。
3PCはそれにプリペアステップをフェーズを追加することによってブロッキング特性を克服しようとしたが、
逆に言うとそれによってオーバーヘッドとかスプリットブレインの可能性が出てしまったということで、
分散トランザクションアルゴリズムはまだまだ開発研究されていきます。
そこで本書で紹介されていたものが2つ3つありまして、
次に紹介されていたのが、すごいざっくり言うなら2PC、3PCでロックを必要としたアルゴリズムではなく、
スマートな頭の良いアルゴリズムを使って実行中にロックを必要とせずに成功性を保証できないのみたいなところから出発されたアルゴリズムですね。
まずはカルビン。カルビンは非常に興味深いアプローチですね。
例えばMySQLのような2フェーズコミットとか、ロックを取る必要があるアルゴリズムでは、
今まで話した通り、例えばコーディネーターノードとかが障害したときにノードが復帰するまでにロックウェイトが発生するので遅くなってしまいます。
カルビンの革新的なポイントは、トランザクションの実行順序を内部ではSequencerというコンポーネントを使って、
決定論的に事前決定するということなんですね。
これはどういうことかというと、全てのレプリカで同じ事前に決定された順番でトランザクションを実行することで決定論的になる。
つまりトランザクションの実行結果が同じ順番でされるということは、
どのレプリカでどのタイミングでトランザクションをしようが最終的に同じ結果になるはずですよね、理論上。
それを仕組みとして実現しようとしたのがカルビンになっています。
この本書を読んでいると決定論決定論とかディタミニスティックとか呼ばれていますが、
要するにトランザクションの実行順序をレプリカ間で同じにしましょうということですね。
同じ文脈で紹介されていた別のスパナーと呼ばれるものがあります。
これはコクローチDBとかイガバイトDBと呼ばれるデータベース、分散データベースでも使われている手法とのことなんですけれども、
スパナーは基本的な戦略としては2フェーズコミットが必要なスコープ、必要な流度をなるべくスマートに最小化するというところですね。
例えばロックを取るときにロックのテーブル全体をロックしなきゃいけませんとか、
あとはデータベース全体をロックしなきゃいけませんとなると基本的に遅いですよね。
例えばSQLiteなんかは今でもライトの書き込みをするときにはファイル全体のロックを取らなきゃいけないので、
基本的に同タイミングで書き込みができるプロセスは常に1個ですと。
ただこのロックできるスコープをなるべく最小化することでプラクティカルにパフォーマンスが出るというのが基本的には、
例えばMySQLとかでも行ロックとかテーブルロックみたいなロックの流度というのはコントロールできるんですけども、
Spannerの基本的な戦略としては2PCが必要な流度をスマートに最小化するというところです。
まずそのトランザクション処理をロックが必要なReadWriteとロックが不要なReadOnlyに分けますと。
データをシャードごとに分割しているわけですね。
リードオンリーはロックが不要で、リードライトはロックが必要だよというのはMVCCみたいな発想としては似ているかなと思いました。
Spannerのそもそもの前提としてデータをシャードに分けているんですね。
データベースパーティショニングというところでも紹介されているんですけども、
シャードごとに分けてシャードごとにAtomicityを担保するみたいな形になっています。
とはいえ各シャードに分割した時に複数のシャードにまたがるトランザクション処理が必要になってくる時もあるんですけども、
そういう時はコンセンサスアルゴリズムを用いて足並みを揃えると書いてありました。
Spannerバイアパキソス、これは次の章でも詳しくやっていくんですけども、
合意形成アルゴリズムを用いて足並みを揃えるが、
基本戦略としてはシャードみたいな2PCが必要な流動を最小化して、
そこでトランザクション処理を発生させるというところでした。
本章を読んでいて、結構この感想は他の参加者からももらったんですけれども、
いきなりポンとデータベースパーティショニングの説明が、
いきなりワンセクションぐらい入ってきました。
分散トランザクションの理解
これはなぜかというと、ここら辺のSpannerの分散トランザクション処理の仕組みを理解するためには、
データベースパーティショニングと呼ばれる前提知識を理解しておかなくては、
何言ってるかわかんないので、
いきなり優しい感じでデータベースパーティショニングは忘れた人もいるかもしれないけど、
こういう概念ですよ、みたいなのが入ってきました。
ここら辺DDIAとか読んだ方であれば、すでに学んでいる概念だと思います。
やっぱりこのSpannerの理解するためのいくつかのコンポーネントとしても、
この章で紹介された2PCもあれば、
他の章でも何回か語られているコンセンサスアルゴリズムであるパキソスであったりとか、
あとこれは実の前の章でも何回か出てきたトゥルータイムと呼ばれるものであったり、
あとはデータベースパーティショニングみたいな色んなキーワードとかコンセプト、テクニックが紹介されてますね。
それらを複合的に理解してようやくSpannerが何をやっているかというのを理解できるので、
ここはなかなか自分の中でも今紹介しているんですけども、難しいトピックだったんじゃないかなと思います。
本章の後半では、ビッグテーブル上のトランザクショナルAPIであるPercolatorとか、
これはちょっと僕もまだまだ全然消化しきれていないんですけど、
コーディネーションアドバイス、そもそもコーディネーションを、
ロックのために必要なノード間でのコーディネーションを不必要にするためのアルゴリズムの研究みたいなのもかなりされているので、
僕の印象としては結構まだ学術的で、
実用的な実装はどこまで存在しているのかというのをそこまではリサーチできなかったんですけども、
研究プロットタイプというのかな、そういった野心的な未来への挑戦についてのテクニックも紹介されていましたね。
第13章はですね、プルヴィスアントランザクション、難しいよというところですね。
やっぱりここら辺の分散システムにおけるトランザクションというのは、
実世界のシステムのパフォーマンスにもろに影響を与えてくるところなので、
そこのパフォーマンスを最適化するためだけでもこんなに足したようなアルゴリズムが、
昔から何十年も前から研究されているんだよみたいなその醍醐味を理解できたのは、
読んでて難しいながらも結構ワクワクしてくるポイントだったのではないかなと思います。
今回のブッククラブの簡単なテイクアウェイですけど、
今回のブッククラブもですね、いつになく非常に活発で、
実践的な議論が交わされたかなと思います。
今回はタイムゾーンとしてはAPACイミヤ会でしたので、
僕も当日の議論に参加できました。
読書ノートを読んでみると結構参加者の方がいくつかキーワードが出ていたので、
それぞれ自分の興味となっているところを深掘りしたようです。
コーディネーション・アボイダンス、僕が説明をスキップしたところについて深掘りした人もいれば、
2PCの元となった論文を読んだ方もいましたね。
あとはご自身で実装されているイベントソーシングのアプリケーションで、
2PCを実装しましたとか、そこの発展的な内容として、
その話をしてくださった方もいましたね。
参加者間の議論と振り返り
あと僕からは、例えば2PCと3PCを説明するときに、
アップアウトな会社のチームリーダーと、
スイスのような完全民主主義国家の議長みたいなアナロジーを紹介しましたけれども、
これはブッククラブでもそこそこ好評だったんじゃないかなと思います。
やっぱり少なくとも何か一つ理解するとしたら、やっぱり2PCが何か分かっておく。
できれば2PCと3PCの特性の違いまで理解しておけば、
今後のデータベース剪定とか、分散システムにおけるトランザクションの実装について、
少しは理解できるんじゃないかなと思います。
SpannerとかKalvinとかは、SREとかデータベースレジリエンシーみたいな人とか、
アーキテクトみたいな人の発展的な例なのかなと思ったりします。
ということで13章どうだったでしょうか。
あと残すところ第1章になっていますね。
ということでそのチャプター14、次のコンセンサスの簡単な頭出しだけして終わろうと思います。
チャプター14はいよいよ合意形成、コンセンサスに入っていきます。
キーワードとしては、パキソスとかラフトアルゴリズム、
あとはビザンチンフォルトレンス、ビザンチン将軍問題に、
などなどのキーワードを紹介しながら、
合意形成アルゴリズムの実装と運用について深掘りしていく章となっていきます。
このコンセンサスは分散システムの総仕上げですね。
複数のノードの間で合意を形成するというのはどういうことなの。
合意を形成するためにはどのような考え方、ワークフロー、
根本的なアルゴリズムがあるのかというのを学んでいきます。
パキソスとかラフトなんていうのは技術ブログでも時々ヒットしたりとか、
トレンドになったりするキーワードかなと思うんですけれども、
いろんなデータベースとかいろんなシステムで使われている、
分散システムの環境における基本というか、実装する側に回ったら基本の基本なので、
今まで学んできた分散環境とかデータベースの知識を総動員して、
コンセンサスアルゴリズムというのを14章、最後頑張って一緒に理解していきましょう。
なかなか興味深い章となっていると思います。
ということで、振り返りは以上にしようと思います。
今回はなかなか難しかったですね。
今回はチャプター13のディストリビューティとトランザクションについて振り返りました。
分散環境でのトランザクションストーリーは、
見てきた通りこの醍醐味と言えるほどの挑戦的な問題ですので、
今回の本を読んだだけで理解できる人は多分いないと思うので、
キーワードを入れて、キャリアの中で何年かかけてしっかり理解していく、
みたいな距離感でもいいのではないかなと思います。
2PCの基本から最新のコーディネーション、アボイダンスまで書いていました。
ということで、次はチャプター14の振り返り収録でお会いしましょう。
それでは皆さん、Have a nice day!
