ヤフー株式会社は、2023年10月1日にLINEヤフー株式会社になりました。LINEヤフー株式会社の新しいブログはこちらです。LINEヤフー Tech Blog

テクノロジー

2015.04.06

分散システムの一貫性に関する動向について

システム統括本部アーキテクト室今野です。

昨年は、Twitter,Facebookを始めとするクラウド各社で新規の分散システム開発のプロジェクトが相次いで発表された年でした。これらの新しい分散システムを開発する理由や、その背景にあるものは何なのでしょうか？

今回は、昨年末に開催された高信頼性分散システム系の国際学会であるSRDS 2014[1]の発表内容に関連する論文の話題も踏まえて、昨今のクラウド各社の分散システムの動向について整理してみます。

分散システムにおけるクラウド各社の動向

近年の分散データベースの世界では、AmazonのDynamo[2]やFacebookのCassandra[3]などを代表とする結果整合性（Eventual Consistency）ベースのものが、まだまだ隆盛かと思います。

このような結果整合性の分散データベースが隆盛な状況で、Cassandra[3]の開発元であるFacebookからはAppolo[4]、TwitterからはManhattan[5]と呼ばれるものが次期分散データベースプロジェクトとして開発が宣言されました。

結果整合性とは一時的な一貫性が保たれていない状態を許容し、時間の経過とともに最終的に一貫性が保たれている状態に移行する一貫性モデルの一つです。クラウド各社の動向を知る上で、まずは一貫性に関して整理してみます。

一貫性に関する動向

分散データベースを含む分散システムでは、さまざまな目的で同一のデータを複数のコンピューターに複製して配置する必要性があります。複製の目的としては、データ保全のためであったり、可用性（Availability）の確保や応答時間の短縮などがあり、現在の大規模なクラウドサービスでは当たり前のように多用される手法の一つです。

一貫性とは?

一貫性とは、分散システムで複製をした際に発生する問題です。一貫性が「ある」とは、複製データのある分散システムで、観察者から「一意なデータを保持している様に見える」状態を指します。以下の図は、複製されたデータに一貫性があり、観察者も一貫性のあるデータを観察できている状況を示しています。

一貫性あり

上図では分散して複製されているデータが同一であり、その結果として観察者にも一意なデータが観察されている場合を示しています。分散システム側でデータ複製の一貫性が確保されている場合を、データ中心一貫性モデル（data centric consistency model）と分類します。

一貫性が「ない」とは、複製データのある分散システムで、観察者から「単一データを保持していない様に見える」状態を指します。以下の図は、複製されたデータに一貫性がなく、観察者が要求ごとに異なるデータを観察している状況を示しています。

一貫性なし

上図では分散して複製されているデータが異なるためデータ中心一貫性モデルとしては一貫性がない状況です。説明のために、その結果がそのまま観察者により一意でないデータとして観察されている状況ですが、一貫性は観察者に一意な様に見えることが条件です。

留意点としては一貫性を確保する手法は、データ中心一貫性モデルだけではない点です。結果整合性は、後述する別の一貫性モデルであるクライアント中心一貫性モデル（client centric consistency model）に分類されるものです。

CAP定理への誤解

CAP定理[6]とは、2000年にEric Brewer氏が提唱した分散システム間のデータ複製に関する定理です。分散システムは、Consistency（一貫性）、Availability（可用性）、Tolerance to network Paritions（分断耐性）の3つの保証のうち、同時に2つの保証を満たすことはできるが、同時に全てを満たすことはできないとするものです。分散システムは、CAP定理[6]を受け、AP（可用性/分断体制重視）型、CA（一貫性/可用性重視）型などの表記により分類される場合もあります。

ただし、このようなAP型やCA型などの表記は、CAP定理[6]が単純な2択的な選択でしか印象も与えかねないものでした。本来、CAP定理は、3つの保証を完全に同時には達成できないことを示したものです。Eric氏もこの点についての懸念を「12年後のCAP定理: “法則”はどのように変わったか」として補足記事で発表しています。

この補足記事では、従来誤解の恐れがあった2択的なCAP定理の説明と合わせて、2択的な設計の限界を超えるために必要となる一貫性や可用性の段階的な選択による最適化の重要性が示されています。

クラウド環境の場合には可用性が最重要視されます。この補足記事では、可用性を重要視する場合には、因果関係の一貫性を保証することが最善の結果となる事が提案されています。

結果整合性とは?

結果整合性とはクライアント中心一貫性モデル（client centric consistency model）の代表的なもので、一時的な一貫性が保たれていない状態を許容し、時間の経過とともに最終的に一貫性が保たれている状態に移行する一貫性モデルです。

一貫性が保たれていない場合には、クライアントには一貫性があるように補正された応答が返されます。日本語では、直訳的には「イベンチュアル一貫性」または「弱い一貫性」とも表記される場合も多くあります。

結果整合性

結果整合性は、多くのNoSQLなどの分散システムの実装で採用されている一貫性モデルで、実装が容易なのが利点です。結果整合性の分散システムとしては、DNS（Domain Name System）や、分散データベースでは前述したAmazon DynamoやCassandraなどが代表的です。

因果一貫性とは?

因果一貫性モデル（causal consistency）とは、順序一貫性モデル（sequential consistency）の制限を弱めたもので、因果関係のない変数に関しては順序一貫性の制限を無視するモデルです。

順序一貫性モデルとは、時間軸の制限を弱めたモデルで、全ての操作が全ての観察者にある一定の順序（sequential）で確認されるのであれば良しとするものです。因果一貫性モデルは、変数に因果関係があると推測される場合のみ、順序一貫性が適用されるものです。

以下の例では、プロセス2（p2）が変数yを書き込む前に変数xを読み込んでおり、変数x→変数yの因果関係が発生しています。プロセス3（p3）ではプロセス2（p2）と同様に、変数xの読み込み結果2の後に、変数yの読み込み結果bが得られており、因果関係が保たれています。

因果一貫性

一方、プロセス4（p4）ではプロセス2（p2）とは異なり、変数xの読み込み結果2の前に、変数yの読み込み結果bが得られており、因果関係が保たれていません。

分散システムと一貫性の動向

近年のクラウド各社の分散システムの設計傾向としては、原子性や一貫性の重要性が再評価され始めている傾向が見受けられます。特に一貫性に関しては、クラウド各社は従来の結果整合性よりも、より強い一貫性を考慮する傾向があります。

従来のRDBMS（Relational Database Management System）では原子性や一貫性が担保されていましたが、結果整合性の分散システムでは開発者が原子性や一貫性をアプリケーションレベルで考慮する必要がでてきます。

結果整合性の分散システム自身は実装が容易な反面、利用する開発者にとっては考慮すべき負担が大きいものといえます。また結果整合性のシステムの中には、そもその一貫性や原子性をアプリケーションレベルで担保することが難しいものも存在します。

クラウド各社の動向

クラウド各社では、結果整合性のような弱い一貫性の分散システム上では、開発者にとって原子性や一貫性などを考慮したアプリケーション構築が難しいという認識が徐々に広まっています。

FacebookのAppolo[4]は、一貫性を重視した設計が特徴的な新しい分散データベースシステムです。Appolo[4]開発の契機について、Facebookは「CassandraのようなAP重視の分散データベースは（格好は良いが）一貫性がなくアプリケーションが組みにくい問題についても要因の一つ」だと言及しています[4]。

近年発表されたGoogleのF1[9]も、結果整合性の分散システムは開発者にとって複雑で不具合が発生しやすいとして、強い一貫性ベースの分散システムとして設計されたものです。

また、結果整合性のCassandraでも2.0で軽量トランザクション（Lightwight transaction）[10]と呼ばれる、より強い一貫性の機能が追加される動向も見受けられます。

学会での動向

SRDSは高信頼性分散システム関連の国際学会の一つであり、今年のSRDS 2014[1]にも一貫性に関する発表は数多くありました。今回は発表された論文で引用元ともなっている代表的な一貫性に関する論文をいくつか紹介してみます。

Causal+ Consistency

Causal+ Consistency[8]は、前述の「12年後のCAP定理」でも言及されているもので、より強い一貫性へのアプローチとして、クライアント側でも操作に対する因果関係および整合性を把握して、サーバー側に通知する方式を取ります。本論文では、結果整合性の分散システムであるCassandra[3]上に実装し検証されています。

CRDTs

CRDTs（Conflict-free replicated data-types）[11]は、「結果整合性の分散システムで、全ての(複製などの)処理の実行が完了した時点で、全ての分散システムが等しい状態」であるものとしてSEC （Strong Eventual Consistency）モデルを定義し、SEC定義に当てはまるモデルをCxRDTとして複数定義した束論ベースの因果一貫性モデルです。CRDTsは、Riakでの対応が表明されており[12]、現状ではPaxos[15]も用いた実装となっているようです[13]。

SDUR

SDUR（Scalable Deferred Update Replication）[14]はデータセンタ間のような大きな遅延が発生する場合の一貫性に関するものです。データセンタ間とデータセンタ内での一貫性確保を分割し、データセンタ間ではPaxos[15]のフェーズを拡張した方式を取るものです。SDURと同様のデータセンタ間の遅延を含む一貫性の確保には、GoogleのF1[9]やTwitterはManhattan[5]でも考慮されている問題です。

結果整合性ではダメなのか?

結果整合性の分散システムは、これから廃れてしまうのでしょうか？

結論としては、強い一貫性が必要か否かはアプリケーションに依存する問題です。前述したDNS（Domain Name System）やCDN（Contents Delivery Network）のシステムでは、大幅な遅延がない限りは結果整合性のシステムでも十分なアプリケーションです。

また、前述のTwitterはManhattan[5]のAP重視の分散システムとして設計されています。Twitterが対象とするアプリケーションは結果整合性は相性が良く、結果整合性こそが可用性を確保するための必須条件であることが述べられています。ただし、AP重視ではありますが、強い一貫性についても前述のSDUR[14]と同様の方式で考慮されています。

最後に

クラウドシステムでは可用性が最重要視されます。ただし、近年の傾向では、可用性一辺倒ではなく、開発や運用の利便性や効率性を考慮した、原子性や一貫性の重要性が再評価される回帰的な傾向も見受けられます。

今後は、可用性や応答性を一辺倒に求める分散システムだけではなく、開発者や運用者にとって優しく透明性のあるものが求められるのではないでしょうか。

優しく透明性のある分散システムとは何なのでしょうか？　機会があれば、次回はこの話題について別の角度から整理してみようと思います。最後まで、ご覧いただきありがとうございました。

参考資料

提供：アフロ

こちらの記事のご感想を聞かせください。

学びがある
わかりやすい
新しい視点

ご感想ありがとうございました

前の記事へ

一覧へ戻る

次の記事へ