引き続き分散システムのデザインパターンの話をしていく。例によって適切な名前を見つけられなかった場合にはその場で適当に名づけているので、ここに書いてある名称が技術レベルでの正式名称だとは思わず、正式名称を見つけたらそっとコメント欄で教えてください。
Application Level Ack
リクエストを受け取った際にAcknowledgment(Ack) を返却するのは重要であるというのは異論の余地はない。だが、どのレベルで返却すべきかというのはデザインスペースの一部である。
ご存知の通り、TCPはそもそもSYN → SYN-ACK →ACKの3方向ハンドシェイクを行い、それぞれの通信ペイロードにシーケンス番号を付けて送達を確認している。SO_LINGERを使えばclose時に未送信パケットが残っていればそれを送り終わるまでclose()をブロッキングする事もできる。TCPのトランスポート層で送達確認をしてくれるので、write(2)が正常に戻り値を返せば送信が完了したと思ってしまいがちだ。しかし、分散システムの世界はもう少し複雑である。
この思い込みを崩す反例は例えばこのようなパターンがある。
- クライアントはconnectionの為にSYNパケットを投げつける。
- さらにSYN-ACKが帰ってくると楽観的に仮定し高速化のためTCPペイロードを含んだパケットまで投げつける。
- サーバは別の理由でそもそも高負荷が掛かっているが、最終的にはOSのレベルでSYN-ACKとペイロードに対してACKを返す(この時点でサーバプロセスに一切通知はない)。
- クライアントは全ての送信データにACKが返ってきたので円満にコネクションを切断するためFINパケットを投げつける
- サーバのOSはサーバのプロセスがaccept()するのを待っているが、異常に時間がかかってacceptに辿り着く前にOSが諦めてバッファを捨て、FINパケットを投げてきたコネクションに向かってRSTを投げる（無意味）
- 最終的に、クライアント側は「正常にデータを送信しACKを得た」と確信し、サーバ側はOSレベルでは通信を検知したがサーバプロセスには通信を試みられた痕跡すら残らない。
という最悪の状態が起こりうる。出典は以下のサイト。
TCP is UNreliable | Cliff Click's Blog
OSが勝手にacceptを諦めてタイムアウトするのは一見無責任に見えるが、おそらくDDoS対策であろうとされている。このサイトやここからのリンクにも対策方法はまとめられており「SO_LINGERでは解決しない」「SIOCOUTQというLinux特有の機能で対症療法的に解決可能だが移植性は低い」「カーネルの設定を弄る事で調整可能だがいつもカーネルレベルでチューニングができるとは限らない」「ユーザレベルでAckをしろ」という結論になっている。TCPが保証するのはOSのレイヤーまでの送達であり、プロセスのレイヤーまでパケットが届けられた確信を常に持ちたいのであればユーザレベルでAckするのが一番である。
実地で使われている例で言うと、MQTTプロトコルはTCPを使ってその上に組まれたプロトコルであるが、MQTTはAckを返す。これはTCPのレイヤーで送達したことではなく、MQTTのレイヤーまで届いた事を明示的に保証するための設計である。MQTTはIBM発のプロトコルであり、おそらく分散システムの専門家が設計したのだと思う。同様にHTTPのAPIを設計する際も、通信できている限りは必ず何らかの値を返す事が慣例である。これはユーザレベルAckが充分浸透している事の証左だが、オレオレプロトコルを設計する際にはこの基本を忘れてしまう事もある。
他に実地で使われている例でいうと、分散機械学習フレームワークであるH2Oなんかは良い例だ。
これは上のTCPの議論のURLで対象とされていたシステムである。面白いことに「リクエスト等の小さなパケットはUDP+ユーザレベルの送達確認」「大容量データのバルク転送にはTCP」という面白い使い分けをしている。前者はどの道TCPを使っても送達確認を実施するし、分散システムは通信内容や通信相手が消失しても適切に再送する必要があるのでTCPでも同様のユーザレベルスタックを構築する事になるし、それならUDPの方が遅延やFast Start的な特性にて優れているから。後者は大規模データをUDPで送るとラック内の通信帯域をむやみに消費してしまう事からTCPのSlow Startな特性を活かすためと説明していた。
User Level Keepalive
通信セッションを確立した後に、定期的に死活確認の通信を行う事は大事である。頻度の低いTCP通信ではセッションの途中経路が物理的に切断されても通信をしない限りそれに気づくことはできない。TCPは両端が生きていれば放置した程度で明示的に通信が切断されることはないが、途中経路で例えばNATを通っている場合にはNATテーブルから消えた段階でNATの外側からの通信が通らなくなったりする。RPC等のプロトコルを設計する際は（特に内部でソケットをプーリングする際には）、コネクション確立後定期的にTCP通信を行う事で経路の死活を管理することが求められる。これはアプリケーションのレイヤー(=RPCクライアントのユーザ)まで突き抜ける必要はなく、RPCより下のレイヤで吸収してもよい。RPCプロトコルの仕様書を読んだ時にこれに相当する機能を持っているかどうかを確認することでどの程度作りこまれているかを見分ける指標の一つに使える。自分で設計する際も忘れずにおきたい。
実地の例では、Twitterのtweetデータがストリームで得られるAPIではJSONが改行区切りで次々と送られてくるのだが、時々明白に空行を送り付けてくる事が仕様に明記されている。通信頻度が低い状況が想定される場合には大事である。よく設計されている。
Streaming message types | Twitter Developers
On slow streams, some messages may be blank lines which serve as “keep-alive” signals to prevent clients and other network infrastructure from assuming the stream has stalled and closing the connection.
やってはいけないのは「壊れました」と壊れた奴自身に報告させることである。ZooKeeperの死活監視も、ZooKeeperクライアントがKeep Aliveパケットを送り続けることで成立している。
Round通信モデル
困難は分割せよというのがコンピュータの基本である。メモリやCPUの管理を行うOS、通信の信頼性やプロセス間の通信に責任を持つTCP/IP、様々はコンポーネントは我々の前に共通して存在しがちな問題の一部を分割して幾らかのオーバーヘッドを伴って解決してくれている*1。分散システムの世界におけるRoud通信モデルという抽象化はある意味でこのような困難の分割である。
まず通信を行うグループに参加するマシン群を整理しお互いに認識させる。その通信グループの間では常に一つのRoundという状態について足並みを揃える。Roundは循環した数字であり、例えば1→2→3→4→1→2→3というように遷移する。各プロセスは自分が置かれているRoundを把握し、Roundに沿った通信を行う。また、Roundに沿ったリクエストを受信することを期待する。期待に沿わないRoundの通信が届いた場合には通信モデルレイヤに立ち返ってやり直させる。なお各ラウンドは定数時間で終わることを仮定して構わない、もし期待した定数時間内で終わらなければRoundのレイヤーで問題を解決（あまりに通信が遅延したマシンをグループから除外するなど）してから、Roundの状態をリセットして再開する。TCPがパケットのリオーダを暗黙のうちに行うからパケットの順序変動を無視して良いのに似ている。
このようなグループ内通信での手順の決まり事を作った一例がRound通信モデルである。これにより非同期通信の状況で発生しうる状態の多くをこのレイヤーで吸収し、ユーザに簡単な通信モデル(同期的・届くメッセージは期待の範囲のみ)を提供することができる。例えばビザンチン障害等の非常に複雑な論理的な問題に対処する際などに使う事もある*2。 Roundを回さないと状況が進展しなくてオーバーヘッドもそれなりにあるため、常に使うべきとまでは言えない。だが非常に複雑な通信手順を設計しなくてはならなくなった時、このように困難を分割することで難度を下げる事ができる事は頭の片隅に置いておいても良いと思う。
適当なビザンチン障害耐性を備えたプロトコルの論文を読んでみれば、時間軸を垂直に分割するRoundの線が描かれていることが多い。シーケンス図の形でも人に説明しやすい。
それと、論文に書かれている分散クラスタ内の通信定義は前提条件としてRoundモデルを仮定している場合もあり、その場合は愚直にTCP/IP上にRound通信モデルのないRPCをそのまま実装してもまともに動かないので注意が必要である。
State Machine Replication
状態を持ったプロセスが障害に耐えるためには複製されなくてはならない。だが、ありとあらゆる状態(e.g. CPUのプログラムカウント)まで複製していては大抵の速度要件に合うはずもない。そこで、サービスのレイヤーのプロセスを「命令を渡される事で状態が更新され」「同じ命令群が同じ順序で渡されたら全く同じ状態になる」という状態機械として抽象化してそれを複製する。全てのプロセスに全く同じ順序で命令列を渡す方法についてクラスタ内で合意が取れれば、全てのプロセスは全く同じ状態になるはずである。この問題の解決手法の事をState Machine Replicationと呼ぶ。1984年にLamportによって提案されたので、この記事を書いている僕より年上である。ユーザは命令を受けとって状態を変更する状態機械のみを定義すれば良いので例えばオブジェクト指向のメッセージパッシングモデルと相性が良く、理解しやすい。State Machine Replicationのレイヤーで複製間の一貫性と耐障害性を解決してくれるので、ユーザからは仮想的に「落ちないプロセス」と見做すことができる。上の方法と同様に、ある種の問題を分割したアプローチとも言える。
上の図は Raft Refloated: Do We Have Consensus? から。State Machineの部分はユーザが任意の物を記述することでフレームワーク側がログの一貫性を保証してくれるので結果としてステートマシンが複製される。
実地ではPaxos Made Liveの論文によるとGoogle社内の分散クラスタの心臓部とされるChubbyはPaxosを内部で使っているようだ。Paxos自体は単一の値に対して合意するためのものだが「n番目に状態機械に実行してもらいたい命令」という単一の値に対して合意するという操作を連続して行っていく事で、状態機械に同一の命令列を与える事ができるようになる。この方法を愚直に行うと性能が出ないので、前回の合意時のリーダーがしばらく連続すると仮定してリーダー選出を重畳して高速化するMultiPaxosなど、様々な改善が行われている。
Paxosの方法では辛すぎるので、Replicated State Machineを実現するためのアルゴリズムとしてRaft等のアルゴリズムが提案されている。これはCrash-Recover故障モデルにも耐える堅牢なアルゴリズムであり、実装もいっぱいある(RaftのURLのページの下の方)。アルゴリズムに関しても様々なところで解説が行われており、以下のサイトが中でも絵的に良く説明されていて気に入っている。
分散システムの専門家を名乗るなら一度ぐらいは実装しておきたいアルゴリズムである。
RaftアルゴリズムがCrash-Recover故障モデルに耐えるのはTLA+というツールによって確認されている。これは分散システム界の神の1人であるLamport氏が作っているツールで、最近ではAWSの内部の複雑なバグを発見するのに使われているという。
Why Amazon Chose TLA + - Springer
TLA+についてもう少し脱線すると、Amazonではこのような手法で設計レベルで仕組み上のバグを見つける事に大きな価値を見出しており、各エンジニアリングチームに1人はTLA+が使えるよう教育していく方針であると書かれている。*3利用は無料なので興味のある方は是非試して欲しい。こちらも分散システムの専門家としてやっていくなら使い方を学んでおきたいツールである。（なお僕は中途半端で手が止まっている）
Raft自体はどんなふうに使うかというと、CoreOSのetcdとかhashicorpのconsulなんかはRaftをコアとしている。ClouderaがC++でデータ分析とデータ追加速度を両立した分散ストレージエンジンKuduとか、GoogleのSpannerを下敷きにGoで分散対障害SQLエンジンを実装したCockroachDBも使っている。どちらもSQLで用いるテーブルを複数行ごとに１つの単位として一つのRaftグループへパーティションするという用法である。GoogleのSpanner実装者も「Spannerで使ってるPaxosはどちらかというとRaftに似ている」との事を言っていた。*4
他にもステートマシンを複製できる機能を活かしてSQLiteをRaftで多重化するなんてのもある。落ちないSQLiteがあれば片付く用件は意外と世の中にいっぱいありそうで上手い目の付け所だなと感心している。このようにいろんなところでベースとして使われ初めている。
複製といえば複製についてもっと書きたい事があるけど今日はこのへんで。
