分散システムは“故障する可能性があるもの”である　具体例から考える、データの一貫性を担保する難しさ

松田氏の自己紹介

松田丈氏：あらためまして、みなさんこんばんは。アマゾンウェブサービスジャパン ソリューションアーキテクトの松田丈です。よろしくお願いします。

私からは「分散システムの課題とリーダー選挙」というテーマでお話しします。本日4つ目の発表で、そろそろお疲れの方も多いかもしれませんが、チャットなどで盛り上げていただけるとうれしいです。ぜひリラックスして聞いてください。

はじめに自己紹介をします。2022年4月にアマゾンウェブサービスジャパンに入社して、ソリューションアーキテクトとして活動しています。好きなAWSサービスはAmazon DynamoDBです。趣味は2022年からボルダリングにはまっていて、週1回程度クライミングジムに行っています。もし見かけたら気軽にお声がけください。

あと、家ではよく『スプラトゥーン』というゲームをやっています。こちらはオンラインなので、マッチングしても恐らく気づかないと思いますが、もし気づいたらナイスを押してください。

発表の元になった2つの記事

発表に移る前に、今回の発表の元になった記事について紹介します。『The Amazon Builders' Library』の「分散システムの課題」と「分散システムのリーダー選挙」の2つの記事を元にしています。もし手元で見ながら聞きたいという方がいたら、記事のタイトルで検索するか、スライドのQRコードを読み取ってください。本発表を聞いて興味が湧いたら、ぜひ元の記事も通読してもらえるとうれしいです。

本日のアジェンダです。「分散システムとは」というところから始まり、「分散システムの課題」そして「分散システムにおけるリーダー選挙」という流れでお話しします。

そして本講演の注意点として、分散システムに関して、あまり込み入った複雑な議論は行いません。『The Amazon Builders' Library』を元に「分散システムってこういう難しさがあるんだ」とか「こういった解決策があるんだな」ということを知ってもらえるような発表を目指しています。

「オフライン分散システム」と「オンライン分散システム」

それではさっそく、分散システムとは何なのかを見ていきます。分散システムとは、多数のコンピューターがネットワークでつながり、連携して1つの作業を行うシステムを指します。

（スライドを示して）分散システムといった場合に、まず大きな分類として、オレンジの枠で囲った2種類に分けられます。左のオレンジの枠がオフライン分散システムで、これはいわゆるハイパフォーマンスコンピューティングといわれるものです。特徴としてはノード同士が物理的に近いこと、ノード間が信頼できるネットワークで接続されていることが挙げられます。

この構成を取るメリットとしては、1台のコンピューターでは不可能な大規模な計算処理をクラスタを組むことで解決することができるほか、専用の高価なコンピューターではなく、汎用の安価なコンピューターを複数用いることで、コストメリットが得られる場合もあります。

右側のオレンジの枠がオンライン分散システムです。Webやクラウドの文脈で分散システムといわれたら、多くの場合がこちらになります。

オフライン分散システムの反対で、各ノードが離れていることや、それを接続するネットワークが信頼できないという特徴があります。コンピュートノード同士を物理的に遠い距離に置くことで耐障害性を高めたり、世界中から通信を行ってくるクライアントに対してもっとも近いコンピューターでレスポンスを返すことで、レイテンシーを向上させられるというメリットがあります。

右側のオンライン分散システムの枠だけ横に長いのですが、これはオンライン分散システムがさらに2種類に分けられるためです。（この2種類は）ソフトリアルタイム分散システムとハードリアルタイム分散システムに分けられます。

ソフトリアルタイムとハードリアルタイムの差に明確な境界はありません。緩いリアルタイムと厳しいリアルタイムということで、あらかじめ決められた時間内に処理が完了しなかった場合に致命的な問題が発生するのがハードリアルタイム、そんなに致命的な問題には至らないのがソフトリアルタイムというイメージを持っていただくと良いと思います。

ソフトリアルタイムの例として、検索インデックスのような、あるタイミングで一度失敗してもやり直せばそんなに大きな影響がないようなものであったり、Amazon EC2のロールのように、あらかじめTTL（Time to Live）が決められており、その期限内に一度処理を完了できれば良い認証情報の更新などが挙げられます。

ハードリアルタイム分散システムには、フロントエンドを返すWebサーバーや分散データベースが該当します。

今回は、特にオンライン分散システムの中の、ハードリアルタイムシステムについてお話しします。3つの分類の中でもっとも難しく、かつ興味深い分野だと思います。

分散システムは壊れる

分散システムの課題に立ち入る前に、分散システムに対して悲観的な感覚を持っていただきたいと思います。

聞いている方の中にも、クラウド上のストレージサービス、データベース、ロードバランサーなどを使ったことがある方は多いと思います。しかし、自分の使っているクラウドストレージが壊れた経験を持っている方は非常に少なく、ほぼいないのではないかと思います。なので、「システムはめったなことがないと壊れない」と、直感的には思ってしまう人もいるかもしれません。

単純な計算として、MTBF（平均故障間隔）が5年のコンピューターを用いたとします。これは5年に1度故障してしまうということです。これを2,000台同時に稼働させると、5年は約1,825日なので、1日に平均1台以上壊れることがわかります。

では分散システムの参加者、ノードが壊れるとどうなるでしょうか。ごく簡単な例として、2つのノードがネットワーク経由で通信して協調する例を考えてみましょう。

ノードAはノードBに対してリクエストを送りたいので、リクエストをネットワークに送出します。ネットワークは、ノードBにリクエストをルーティングして届けます。

ノードBは、受け取ったリクエストのメッセージを検証して自身のステートを更新します。ノードBはステートの更新が終わったら、レスポンスをネットワークに送出します。ネットワークはレスポンスをノードAに届けます。そのあと、レスポンスメッセージをノードAが検証してステートを更新すれば、一連の処理が正常に終了したといえます。

ではここで、この分散システムを構成するコンポーネントが故障した場合を見ていきます。最初の例として、リクエストが到達しなかった場合、つまりネットワークが故障した場合を見ていきます。ネットワークが故障するとノードBはもちろん何のリクエストも受け取っていないので、レスポンスを送ることもありません。よって、ノードAからすると送ったリクエストに対してレスポンスが返ってこない。「返事が来ないな」という見え方になります。

次の例として、レスポンスが到達しなくなってしまったケースも見てみます。ここでは（スライドの）4番のステート更新までが正常に終了し、ノードBがレスポンスメッセージを作成したとします。しかしこのレスポンスメッセージが、ネットワークの障害により、ノードAに到着しませんでした。この場合、ノードAからするとノードBに届いたかどうかもわからず、「返事が来ない」ということしかわかりません。

最後に、ノードBがステートを更新している間に、何らかの障害を起こしてしまった例を見てみます。もう気づいている方も多いと思いますが、この場合でも同様にレスポンスメッセージが返ってこないので、ノードAにとっては「返事が来ないなぁ」ということしか見えません。

これまで見てきた3つの例の他にも、さまざまなケースでリクエストを送ったのに返事が来ないということが起こり得ます。共通していえるのは、ノードAにとってわかるのは「返事が来ない」ということだけです。

ノードBが壊れたのかもしれないし、ネットワークが壊れたのかもしれませんが、それがわかることはなく、他のノードやネットワークの状態について何も知らないまま処理を続けなければいけません。

さらにこの障害の厄介な点は、時間が経てば復旧するかもしれないということです。もっといえば障害なんて起こっておらず、レスポンスが遅れただけかもしれません。

これはネットワークの輻輳（ふくそう）やノードB、受信側のガベージコレクションなどによって起こり得ます。レスポンスをいつまで待つか。つまり、タイムアウトの時間設定もまた分散システムの課題といえるでしょう。

この問題にはtail latencyという特性が大きくかかわります。発表時間が限られているので割愛しますが、興味を持った方はtail latencyについて調べてみてください。

障害が起きてもそれを各ノードが知るすべはない

参加ノードの障害についてまとめます。リクエストまたはレスポンスのメッセージが失われた場合、ネットワークの障害の可能性も対向ノードの障害の可能性もありますが、それを各ノードが知るすべはありません。この場合、送信ノード側ではタイムアウトとして処理の終了ハンドリングを行う必要がある上、どれだけ待ったらタイムアウトと見なすのか、その設定も難しいということを見てきました。

また、受信ノード側の処理は冪等性を担保する必要があります。つまり、処理が2回以上行われても問題ないような処理の仕方にしておく必要があるということです。これは、ノードAからするとノードBにリクエストが届いたかどうかもわからず、リクエストは多くの場合リトライされるためです。

非同期レプリケーションで問題が発生する例

次に、こういった過酷な分散システムの中で、データの一貫性を担保するためにはどういった工夫が必要かを見ていきます。

初めに、分散システムにおけるレプリケーションについて見ていきます。この例では単純な非同期レプリケーションを用いるので、問題が発生するものとして見てください。

（スライドを示して）これは飛行機の予約（システム）において、ある特定の席を予約する例です。まず初めにユーザーは、ノードBに対して17Aという席を予約したいとリクエストしたとします。

ノードBは17Aが空席というデータを持っていたので、ユーザーに予約完了というレスポンスを返すのと同時に、他のノードに17Aの席が埋まったという情報をレプリケーションします。ここは非同期レプリケーションであることに注意します。

ユーザーBに予約完了のメッセージを送るのとほぼ同時に、ノードAとノードCに17Aが予約されたというデータを送り、ノードAとノードCからの返事を待つ前に、ユーザーBにレスポンスを返しています。

オレンジの点線で示した、ノードBからノードAへの通信が失敗または遅延して、その間に他のユーザーがノードAに対して17Aの席を予約したいというリクエストをした場合に、何が起こるでしょう。

先ほどノードBで見た時と同じように、ノードAはユーザーAにOK、予約完了というメッセージを返します。まだ17Aが埋まったという情報はノードBから届いておらず、ノードAの持っているデータでは空席状態なためです。

通信が復旧するとノード間でデータの同期が行われますが、ノードAとノードBの両方が17Aを埋めてしまい、データのコンフリクトが生じます。

このコンフリクトを自動で解決するのは非常に困難です。もしコンフリクトを解消できたとしても、まだ問題があります。

ユーザーAとユーザーBから見ると予約完了のメールは受け付けているので、ダブルブッキングが解消されません。このままでは、同じ時間に同じ空港の同じ席にユーザーAとユーザーBが来てしまうことでしょう。

同期レプリケーションは耐障害性が下がる

分散システムにおけるレプリケーションについてまとめます。分散システムでは通信が遅延したり届かない場合があるのは先ほど見たとおりです。この場合、単純なレプリケーションでは、データの一貫性を保つことが難しいということがわかりました。

ここで非同期レプリケーションではなく同期レプリケーションを行うとどうかと考えた方もいるかもしれませんので、補足しておきます。

（スライドを示して）下の図を見てください。同期レプリケーションを行うと、他のノードからの応答をすべて待つ必要があり、逆に耐障害性が下がってしまう問題があります。

ユーザーBが17Aを予約したいといった時に、先ほどのようにノードBからノードAへのレプリケーションメッセージが届かなかった場合、もしくはノードAからのレスポンスメッセージが届かなかった場合、ユーザーBに対して予約完了のメッセージをいつまでも返すことができません。分散システムにおいてすべてのノードが動作していればいけないという状態は、逆に耐障害性が下がっているといえます。

（次回に続く）