Hyperledger Fabric と Indy でのコンセンサス(合意)アルゴリズムについてまとめようと思っておりましたところ、ちょっと古めですが以下のようなうまくまとまっている記事を見つけたのでご紹介いたします。
この記事では"ビザンチン問題"から始まっていますが、まずはより手前の情報をばら撒くアルゴリズムからご紹介いたします。
助走 1. 情報の伝搬・ゴシップアルゴリズム
いくつものノードが接続されたネットワークによって稼働・運用する一つのシステムにおいて、すべてのノードで一貫性のある状態が保たれている ということは基本的なことです。
接続するノードによって問い合わせの返答がバラバラではシステムになりません。まず、どこかのノードに対して行った更新などの結果をすべてのノードでちゃんと一貫性を持って共有してもらうことが前提になるわけです。
その際に、一つノードからネットワークに参加するすべてのノードにデータが到達してそれぞれのノードでコミットが終わるまで、その処理がコミットできない、というのは非常にコストの高いものとなってしまいます。
そこで一つもしくはいくつかのノードでコミットされた結果をいかに効率よくスピーディーにばら撒くかという処理が重要となってきます。
それがゴシップアルゴリズム、ゴシッププロトコルと呼ばれるものです。
Wikipedia に記事がありましたので以下にリンクを貼っておきます。
これは確立的に情報が伝搬・広がっていく方式であり、ネットワーク参加者が不安定であったり一時的に通信できない場合にもネットワーク全体の状態を"ある程度"均一にはできますが、「常に完全」ではありません。
実はクラウドの技術で最も重要なことの一つが、この一時的な"完全ではない"状態を許容するかどうか = フォルトトレランス(Fault Tolerant/Fault Tolerance) 性という点であります。
このフォルトトレランスをどのように組み込むか、どのように対応するかがクラウド技術・分散ネットワーク技術の基本的な特徴の一つとなっていきます。
今回は状態の一貫性とシステムの可用性について研究したCAP定理については触れませんがこれがクラウド技術・分散ネットワーク技術にとって非常に重要な考え方であります。
助走 2. クォーラムベース投票
ネットワーク内の各ノードにデータをばら撒くのは良いですが、データを引っ張ってくるときにノードごとにバラバラのデータを持っている状態で、どのデータが"正しい"のかを決定できる"仕組み"が必要です。
そこで、どれだけだけの散らばり具合の場合にはどのくらいのノードからデータを読み込めば、正しいデータが決定できるか、という仕組みが "Quorum" ベースの投票システム、となります。
これは単に過半数を越えればOKというものではなくて、例えばネットワークの 3/5 にデータを散りばめておけばデータを読むときは 2/3 でOK、という"確率的に正しい"データが求まりますよね、という仕組みです。
書き込みノードの割合と、読み込みノードの割合はノード数とネットワークの負荷などでバランスを取りつつ決定します。
詳しい内容は以下のWikipediaをご覧ください。
クォーラム投票を用いる分散ネットワーク技術において、従来のレガシーなシステムと決定的に違うのはこの、"正しい状態が多数決できまる"という点です。
一つのDBから読み込んだ値が完全に正しいという保証はなくて、いくつかのサーバーからデータを寄せ集めて来て、クォーラムベースの投票によって正しい値を"決定する"というのが、データの信頼性・一貫性の担保のやり方の一つになります。
助走 3. ゴシップ＆投票からコンセンサス(合意)へ
ある確率でお互いに通信しながら情報が伝搬していき投票で正しい状態を担保するのに確率に任せるのも一つの手ですが、ちゃんとネットワーク全体の状態を"コミットしていく"手順も同時に考えていかなければなりません。
そもそもの "合意" とはなんなの？という点についてはこの問題の元となるPaxon アルゴリズムについて以下のように簡潔にまとまっています。
合意とは参加者のグループにおいて単一の結果について合意を得るプロセスである。参加者や通信手法に障害が起きる可能性がある場合、この問題は困難なものとなる。
不安定なノードのネットワークに対して、どのように情報を伝搬させ、そしてどのような手段で"これがネットワークの全体で合意された結果である"とコミットしていくか、という手法・アルゴリズムがその分散システムにおいてのキモなのです。
助走 4. ビザンチン将軍問題
そしてこの不安定なネットワーク間での合意問題として有名なのが ビザンチン将軍問題 です。Wikipedia に簡潔に書いてあるのを抜き出しますと、
相互に通信しあう何らかのオブジェクト群において、通信および個々のオブジェクトが故障または故意によって偽の情報を伝達する可能性がある場合に、全体として正しい合意を形成できるかを問う問題である。
ということです。
ネットワーク上のノードが"不安定"といっても、単に接続できる・できないというレベルから、持っている情報が古い場合や書き込みに失敗する、悪意を持って改ざんされている、などの様々なパターンがあって "どのノードも完全には信用できない" 場合にどう合意形成するか、という問題になります。
そしてこれを様々な手法・アルゴリズムで解決できた・対応できたシステムは BFT(Byzantine Fault Tolerance、ビザンチン故障耐性)を備えるシステムである、ということになります。
それでは Hyperledger が採用する合意アルゴリズムをご紹介いたします。
1. Raft - Hyperledger Fabric
まずは Hyperledger Fabric におけるコンセンサスアルゴリズムについてですが以下の公式ページに解説があります。
Fabricは現在のところ、 Raft プロトコル の etcd ライブラリ をベースとしたCFTのオーダリングサービス実装を提供しています。
ということで Fabric では Raft という合意プロトコルを用いています。また上記の箇所に書いてありますが、Raft は CFT(クラッシュ故障耐性) を備えるプロトコルであってBFT(ビザンチン故障耐性)を備えるプロトコルではありません。つまり、Fabricはデフォルトでは BFT を備えるシステムでありません。ただし、Fabric は Pluggableになっておりコンセンサスのロジックを入れ替えることができるようになっております。
1-1. Raft について
Raft プロトコルについては公式の以下の紹介ページがあります。
またアルゴリズムそのものについては英語版のWikipediaがなかなか詳しくてわかりやすかったのでGoogle翻訳したのを貼り付けます。
Paxosファミリーのアルゴリズムの代替として設計されたコンセンサスアルゴリズムです。ロジックを分離することにより、Paxosよりも理解しやすくすることを目的としていましたが、正式に安全であることが証明されており、いくつかの追加機能を提供します。Raftは、コンピューティングシステムのクラスター全体にステートマシンを分散する一般的な方法を提供し、クラスター内の各ノードが同じ一連の状態遷移に同意することを保証します。
ということですが、具体的にはどのような手順なのでしょうか。実は割とシンプルで以下の2つのフェーズで Raft は動きます。
- リーダーの選出
- データの配布
"リーダの選出フェーズ"で毎度、"まともなノード"をリーダーとして選出し、そのノードからのデータを"正"として各ノードが受け取る、というシンプルな手順です。
毎度"まともなノード"を選出する というシンプルなひと手間を加えることで、ネットワーク全体のノードの安全性やデータの一貫性に対する強度を高められるわけです。
1-2. Raft の実装いろいろ
Raft には様々な言語での実装があります。上記のRaft公式サイトに載っているものでいくつか気になったものを以下に列挙いたします。
| Name | Primary Authors | Language | License | Leader Election + Log Replication? | Persistence? | Membership Changes? | Log Compaction? |
|---|---|---|---|---|---|---|---|
| etcd/raft | Blake Mizerany, Xiang Li, Yicheng Qin | Go | Apache-2.0 | Yes | Yes | Yes | Yes |
| TiKV | Jay, ngaut, siddontang, tiancaiamao | Rust | Apache-2.0 | Yes | Yes | Yes | Yes |
| hashicorp/raft | Armon Dadgar | Go | MPL-2.0 | Yes | Yes | Yes | Yes |
| Kudu | David Alves, Todd Lipcon, Mike Percy | C++ | Apache-2.0 | Yes | Yes | Yes | Yes |
| RedisRaft | Redis Labs | C | (AGPL-3.0 OR RSAL) | Yes | Yes | Yes | Yes |
| bakwc/PySyncObj | Filipp Ozinov | Python | MIT | Yes | Yes | Yes | Yes |
| canonical/raft | Free Ekanayaka | C | Apache-2.0 | Yes | Yes | Yes | Yes |
Hyperledger Fabric で採用されているのはトップに上がっている "etcd/raft" という実装です。etcd は前回までのk8sシリーズでもご紹介いたしましたが k8s のデフォルトのコントロールプレーンのストレージです。Zookeeper に続く一貫性と冗長性、高可用性のあるKVSで採用されているコアなアルゴリズムが Raft である、というのは胸アツです。
その他、TiKVやKudu、RedisRaft、hashicorp/raft、canonical/raftなどはk8s関連で紹介したプロダクトやHadoop関連、その他のOSSでも採用されています。
このように Raft アルゴリズムは間違いなく現在のクラウド・分散ネットワーク技術での中核となるプロトコル・アルゴリズムの一つである、と言えるでしょう。
2. Plenum BFT - Hyperledger Indy
Indy のコンセンサスアルゴリズムである Plenum については以下の公式ページにガッツリと解説がございます。
で、Plenum とは何なのか～？というと、RBFT(Redundant Byzantine Fault Tolerance)の実装であるという説明があります。
これはガッツリな論文でして RBFT っていうプロトコルがどんなもんか…については上記のドキュメントを読んでいただきたいと思います。すいません。。ここでは Plenum での実装がどうなっているかについて簡単に説明いたします。
2-1. Plenum BFT の流れ
Plenumでは BFT を担保するために、CFT だけの Raftに比べて少々ややこしい手順となっております。
手続き A. リーダーの選出
手続き B. 3フェーズコミット
上記の2つの手続きは順番ではなく、まったく個別のフェーズとして実施されます。ですので連続した手順ではなく別々の"手続き"としてご紹介します。
2-2-A. リーダーの選出
"リーダーの選出"は Raft の場合でも重要な手順でしたが、Plenum でも非常に重要な手順です。
Plenum では Raft の場合と違い、常に"選挙"が行われるわけではありません。
リーダーノードの"レイテンシーとスループット"というパフォーマンスが、定期的に他のすべてのノードの平均パフォーマンスと比較されて監視されています。そこでリーダーが劣化していることが判明した場合"選挙"が行われ、別のノードが新しいリーダーとして選出されます。
随時、定期的にこういうノードの負荷を計測し、ノードの負荷に応じてリーダーのポジションチェンジがコロコロと行われています。
ノードのパフォーマンスに応じてマスターを切り替えるベストエフォート方式。なかなかスゴイですね。。。
2-2-B. "3フェーズ" コミット
Plenum の中核となるロジックが3フェーズ コミットです。
正しいシークエンスは以下の公式サイトで紹介されております。
これはかなりややこしいのですが、簡素にいたしますと以下のようなフローとなります。
- リーダーから"コミットされていないデータ"、要求のダイジェスト、キー、マルチシグなどが含まれる事前準備メッセージをすべてのノードに送信します。
- 事前準備メッセージを受け取ったノードはメッセージの内容を検証し、OKであれば準備メッセージを作成して他のすべてのノードに送信します。
- 準備メッセージを送信したノードが過半数を超えた時点でコミットメッセージがすべてのノードに送信され、ネットワーク全体での合意データのコミットが行われます。
"事前準備メッセージ"を投げて、"準備メッセージ"の応答が返り、"準備メッセージ"の応答が過半数超えた時点で"合意"が取れたと判断して"コミットメッセージ"を投げる、というなかなかのロジックです。
手順はかなり複雑ですが、これでビザンチン将軍問題も解決してネットワーク全体の合意が取れている、ということらしいです。すいません、詳細には理解できてません。。。
番外編: Merkle Patricia Tree
ちなみに Indy の台帳データは Ethereum と同じ Merkle Patricia Tree 構造となっております。
これについては詳しく Ethereum の Wiki にて解説がございます。
具体的な方式は上記のページに詳しくありますので、そちらに説明をお任せするとして、ここでは "O(log(n)) という優秀な計算時間内でデータの挿入、検索、削除が可能であり、 red black tree のような複雑な比較基盤のデータ構造よりも、簡単に理解しコード化する事ができ"る、というとてもすごい構造なんだよ、というご紹介だけとさせていただきます。
まとめ
Hyperledger Fabric と Hyperledger Indy を題材として、分散ネットワークを支える様々なアルゴリズム・プロトコルをご紹介いたしました。
分散ネットワークという技術において、合意アルゴリズムは中核のアルゴリズムであり、分散ネットワーク製品やブロックチェーン製品を選定する上で CFT や BFT の耐性がどこまでサポートされているか、というのはシステムの要件上、クリティカルなファクターとなるかと思います。
当然、フォルトトレランスの程度に応じてネットワークの負荷やレスポンス性能はトレードオフの関係にあります。どのレベルまでどのくらいの性能が必要か、という検討の一助になれば幸いです。