メインコンテンツまでスキップ
 
新しい会話を開始

未解決

JPCommunityMgr

Community Manager

 • 

3.1K メッセージ

1385

2022年12月8日 23:00

【Coffee Break】分散システムにおける原理原則「CAP定理」を知る

 

coffeebreak.png

 

 

この投稿は「ちょっとしたストレージ関連技術のTIPSを思いついたら書いてみる」というコンセプトで、デル・テクノロジーズ社内のTeamsグループ/チームでゆる～く運営されている「Coffee Break」からの情報抜粋です。今回はDBスペシャリスト（とそれ以外にも複数の顔を持つ社内有名人）からの投稿を抜粋しました。

 

 

 

さて、今日は法則というか、分散システムに関する定理 「CAP定理（きゃっぷていり）」というのを紹介したいと思います。
クラウドを使う以上、基本的に分散システムが前提になるわけですが、そのアーキテクチャを考える上で基本になる考え方だと思いますので、お客様とのその手の会話でも役に立つかもしれません。
データベースの話をしていても、この辺に突き当たることはよくあります。CAP定理で言っているようなことは、たとえそれを知らなくても、実際には当たり前すぎて皆さん無意識のうちにこれに基づいた会話をしているように思いますが、基本を知っておくことは重要かなと。

 
今回はCAP定理をメインとして、以下の流れで書いていきたいと思います。
  • トランザクション（おさらい）
  • ACID（これもおさらい）
  • CAP定理
  • BASE
まずは基礎を振り返るところから行ってみたいと思います。トランザクションとかACIDなんて知ってるよ、という方は読み飛ばしてください。


■トランザクション

トランザクション (transaction) とは、分けることのできない一連の情報処理の単位である。 トランザクション内では、ユーザインタフェース、アプリケーションプログラム、永続性記憶資源、各種I/Oが実行される。
　　　　　　＜＜中略＞＞
トランザクションが満たすべき技術的要件にACID特性がある。ACID＝「あしっど」と読む

以上、 Wikipediaから抜粋。
 
必ず出てくる銀行口座の例で説明したいと思います。
 
例）銀行口座Aから、口座Bに１０万円振り込む
  1. 口座Aの残高を確認
  2. 口座Aから１０万円減らす
  3. 口座Bに　１０万円増やす
  4. 処理を確定する
JPCommunityMgr_0-1670570292624.jpeg

 

 
ここで、仮に２と３の間の微妙なタイミングでシステム障害が起こったらどうなるでしょうか？
口座Aから１０万円減らされるが、口座Bは１０万円増えていない状態が発生する？その１０万円はどこに行ってしまうのでしょうか？
これが典型的な「分けることのできない一連の処理」です。通常の振込処理は、正常に完了するか、すべて無かったことになるかのどちらかしか許されず、中途半端な状態は許されません。

 

■ACID

信頼性のあるトランザクションシステムの持つべき性質として1970年代後半にジム・グレイが定義した概念。一般的なRDBMSはこれを満たす。
 
  • Atomicity: 原子性（あるいは不可分性）
    • すべてのトランザクションは不可分(Atomic)である。All or Nothing
    • 例：銀行取引は完了するか、なかったことになるか、どちらかしかない
  • Consistency:一貫性
    • トランザクションの開始と終了時に一貫性を保証する。整合性と言うことも
    • 例：口座データはマイナスにならない　などのデータの一貫性を保証する
  • Isolation: 独立性
    • トランザクションはお互い独立。実行過程は隠蔽され他のトランザクションから参照できない
    • 例：銀行取引の途中の状態は、他の処理からは観測されない
  • Durability: 永続性
    • コミット（確定）したトランザクションは消えて無くならない
    • 例：処理を確定したら、その後システムに障害があっても銀行取引の結果は消えない
    • （RDBMSだけではどうにもならないこともありますが、できる範囲で実装するという感じでしょうか）
ちょっと話はそれるかもしれませんが、こういった特性がアプリケーションにどう役に立つのか、という部分に触れておきたいと思います。
お客様のいわゆるエンタープライズシステムを見ると、RDBMSがいたるところで使われています。私は以前そういったシステムを作る側にいました。C言語とかJavaとかでアプリケーションを手作りしていました。その時の経験では、データを扱う際に自分でいろいろ作り込まなくてもRDBMSがやってくれる、というのは非常に楽だと感じました。例えば以下のような感じです。。。
 
  • トランザクション処理が楽
    • 処理中に何らかのエラーになっても、やりかけの処理をなかったことにしてくれる
    • 何も考えずにデータを参照しても、Isolationが保たれている
  • データの整合性を確保するのが楽
    • ユニークIDが簡単に扱える（例：「社員番号」は必ずユニーク。重複するレコードを挿入しようとするとエラーになる）→プライマリキー制約
    • データとデータの間の整合性を保ってくれる（例：存在しない部署番号をもった社員情報を挿入しようとするとエラーになる）→参照整合性制約
  • 複数ユーザの同時処理でも、必要な排他制御はDBがやってくれる
    • 複数のユーザ、プロセスが同じレコード、同じカラムを書き換えようとしても、よしなに処理してくれる（難しいこともあるけど）
  • データの物理的な場所を気にしなくていい
    • どのサーバの、どのディレクトリの、どのファイルの、どの場所にデータが有る、といったことはDBがやってくれる
  • 一度処理を確定したら、データが消えない
    • バグや障害でプロセスがダウンしても、確定したところまではRDBMSがデータを保証してくれる
いちいち自分でファイルを作ってそこに書き込んで処理をして、、、という世界からRDBMSの世界に来ると、「データを扱う部分を自分で作らなくて良い」というのは最高でした。工数は減らせるしバグも減るし。
というわけで、データを持つシステムには何らかのRDBMSがあり、それに依存したアプリケーションが必ずある、と考えて間違いないと思います。
 

■CAP定理

DBというよりは、分散処理に関する定理と考えてください。2000年にEric Brewer が提唱して、2002年には定理として証明されました。
 
定理の趣旨としては、同じデータを持つ複数のノードから成る分散システムにおいて、以下の3つの特性のうち同時に成立するのは2つだけ　ということです：
  1. Consistency　（一貫性）
    • 全てのノードにおいて、同時に同じデータが見える
  2. Availability　（可用性）
    • SPOF（単一障害点）が無い。ノード障害が発生しても生存しているノードが機能する
  3. Partition-tolerance (（ネットワークの）分断耐性）
    • 任意の通信障害などによるメッセージ損失に対し、継続して動作が可能
JPCommunityMgr_1-1670570292626.jpeg

 

 
この絵で考えてみたいと思います。Node 1 と Node 2 は、同じデータを持ちネットワークで繋がった分散システムとお考えください。
その状況で、ネットワークが分断してしまったとき・・・
 
  • Node 1 だけ更新できるようにすると、Node間に一貫性(C)がなくなる
  • 一貫性を維持するためには、Node 1 を更新できなくする。すなわち可用性(A)がなくなる
  • 一貫性(C)と可用性(A)を維持するためには、ノード間の通信ができることが必須。すなわち分断耐性(P)が失われる
一般的に広域分散システムでネットワーク障害が起こらないという前提は置けないので、分断耐性は必須条件となります。ゆえに、システムとしては可用性と一貫性の間で選択を迫られることになります。
（後に Brewer は、これらは0か1かの話ではなく程度の問題、と述懐しています）
 
CAPのうち2つを満たした例：
  • CA型：一貫性＋可用性を重視（分断耐性を犠牲）
    • NFSとか、2相コミットするような厳しいRDBMSとか
    • ネットワークが分断したら、片方を切り捨てたりする
  • AP型：可用性＋分断耐性を重視（一貫性を犠牲に）
    • DNSとか Apache Cassandra とか
      • DNSはある時点でサーバ間で必ずしもデータは一致しないかもしれないが、時間がたてば一致するようになる。ACIDのCのように強い整合性はないが、ある意味「弱い」整合性がある。これに関しては後述のBASEの解説で補足します
    • SRDFとかのストレージレプリケーションはこのタイプ？　後から一貫性を回復する、という感じでしょうか
  • CP型：一貫性＋分断耐性を重視（可用性を犠牲に）
    • Apache Hbase とか
    • ネットワークが切れたら整合性がとれないので全体を止める＝可用性が犠牲になる

■BASE

前段で、DBのACIDの話をしましたが、BASEは分散システム向けのもっとゆるい一貫性モデルを含んだ考え方です
 
  • BAsically Available　（基本的に利用可能）
    • （データの一貫性などは保証しないが）基本的にいつでも読み書き可能
  • Soft-state　（「ソフトな」状態））
    • スイッチのオンオフ(hard-state)のように状態がきっちり確定していない
  • Eventually Consistent　（結果整合性）
    • 最終的に一貫性がある（ある程度の時間が経てば収束する）
※この辺の訳は諸説ありますので、興味のある方はいろいろ調べてみてください
余談ですが、化学の世界では ACIDは酸、BASEは塩基です。わざとこういう略語にしたんだろうな、と推測しています。
 
分散システムを考えた場合、ネットワーク分断を避けては通れないので、CAPのPを避けることはできません。すなわちPありきで、CかAを選ぶということになります。ここでACIDのようにきっちりした一貫性を保とうとすると、CP型を選択せざるを得ず可用性が犠牲になってしまいます。
分散システムで高い可用性を実現しつつ、でも、データの整合性もほしい、という時に用いられる整合性モデルが BASEのE: Eventually Consistency です。
インターネットのDNSやNTPなどがこの例になります。ある時点ではノード間でデータがずれているかもしれないが、時間が経てば収束して最終的には一貫性を持つ、という考え方です。
いわゆるNoSQLの製品などでもこういった考え方が取り入れられたものもありますし、ストレージレプリケーションなんかも、基本的にはこの考え方になるかと思います。



■蛇足：最近のトレンド NewSQL

最近、ACID特性を満たせると謳う分散RDBMS製品が登場してきています。いわゆる NewSQLと呼ばれるカテゴリーです。ちょっと思いつくだけでも、Google Spanner、Yugabyte DB（ゆがばいとでぃーびー）、TiDB（たいでぃーびー） などがあります。
本当にそうならCAP定理を覆したのか？と思ったりします（証明済みの定理なので覆せないはずですが）。
TiDBを開発している PingCAP社の社名の由来は、CAP定理のC,A,P全てにつながりたい(Pingしたい）という思いから名付けたそうで、その辺をかなり意識しているのは間違いありません。

 
最近は、お客様からもこれらの製品の名前を聞くようになってきました。クラウドの複数リージョンにデータを分散させて一つのSQL文で処理できる、となれば非常に魅力的ではあります。実際のところはどうなんでしょう？　おそらくは、ACIDとBASEの間で折り合いを付けつつ、シャーディングなどを使ってデータを分散配置しながらうまく扱うような仕組みを実現しているのだろうと推測します。
この辺、機会があれば調べてみたいと思っています。
 
 
レスポンスがありません。

Was this post helpful?

すべて表示

イベントは見つかりませんでした！

Top