読者です 読者をやめる 読者になる 読者になる

CAP定理について

計算機 ノート 考察

CAP定理という分散ストレージシステムの設計において非常に重要な定理がある。まだ、以下の元の論文を読んでいないので、正確な理解かどうかは保証できないが、理解している範囲で考えることを記す。

https://www.comp.nus.edu.sg/~gilbert/pubs/BrewersConjecture-SigAct.pdf

CAP定理によると、分散システムでは以下の3つを同時に満たすことはできない:

  • Consistency 一貫性、
  • Availability 可用性、
  • Partition tolerance 分断耐性。

それぞれ、

  • all nodes see the same data at the same time,
  • every request receives a response about whether it succeeded or failed,
  • the system continues to operate despite arbitrary partitioning due to network failures

という意味である。*1

分散ストレージシステムはいろいろあるのだけれど、C・A・Pのいずれかを捨てるという選択を行っている。この選択がいわゆる設計思想というものなので、どの選択をしているかでシステムの特徴が分かる。

システムとして、Availability はほとんどの場合必須なので、

  • Consistency + Availability (CA)、 か
  • Partition tolerance + Availavility (PA)

の組み合わせが選択される。Consistency + Partition tolerance を選択している例は私は知らない。*2CA あるいは PA が選択されているシステムとしては以下が挙げられる:

列挙すると分かるが、CA は一貫性をとっているのだから当然だが、厳密でお固いものが並んでいる。一方で、PA の方は柔らかい印象だ。耐障害性・ロバスト性は PA の方が強い。柔らかいから、逆に壊れにくいという感じでしょうか。

どちらを選択するかは用途によるとしか言いようがないが、個人的には PA が好きだ。主観だが、PA の選択の方が設計思想としては新しい。一貫性を保証するというのも難しいので、初期はいかにして一貫性を担保するかを頑張ってきた。しかし、一貫性の問題が解決されたら、実は完全な一貫性はオーバスペックなのでは?――となってきた。一時的に不整合が起こるかもしれないが、それもほとんどないし、仮に不整合がおきても、時間がたてば辻褄が合うから別にいいじゃん――というある意味で割り切った態度を PA を選択したシステムはとることが多い。これを、結果整合性という。

例えば、SMB(Windowsの共有フォルダのこと)*4はネットワークに繋がっていなければ使えないし、遅い。しかし、現実同じファイルを複数人が同時に編集することはあまりしないので、常に最新である必要もない。その用途だと Windows の共有フォルダは非常に使いにくい。MS Office は整合性を保つために編集中のファイルをロックする機能があるが、あれはイライラする。競合が少ないなら、ちょっとぐらい不整合があってもいいじゃんと、Dropbox は割り切っており、この割り切りは合理的だと思う。個人用のネットワークドライブなんかは、私はセンスねえなと思う。

PA が好きなのは、どこか割り切ったところが入っている点で、言葉として変だが、何を割り切るかは割り切れないものだ。完全に Art の領域だ。どこを割り切ったらいいのか、つまり何を捨てて何を取るかということについて、まだ最もよいバランスというのは合意がとれていない。工夫の余地がまだ残っていて、興味深い。

*1:英語版 Wikipedia から引用。https://en.wikipedia.org/wiki/CAP_theorem。日本語版の記事はどうも間違っている気がする。

*2:もちろん、C・A・Pのうち一つだけしか満たしていないものもある。Consistency だけの場合が多いかな? 例えば、初期の HDFS は Consistency しか満たしていなかった。なお、C・A・P以外にもスケーラビリティという別の話があって、Consistency とスケーラビリティは相反するところがある。HDFS は Consistency を満たしつつ、スケーラビリティも持たせるために、非常に大胆な割り切りをしている。

*3:例えば日米間の光ファイバーがサメに食われても、日本のサイトは覗けるのでインターネット全体として止まるわけではないという意味です。一つのサイトと多数のクライアントという風に見れば、CA です。インターネットの強力な耐障害性は PA を選択しているといった「ゆるさ」が理由だが、このネタだけでいくらでも語れるので踏み込まない。気が向けばいつか書く。

*4:クライアントキャッシュがないことを前提としている。SMBのクライアントキャッシュの取り扱いってどうなっているのかよく知らない。