分散システム

CAP定理

分断下の不可能性。

条文

もし

ネットワーク化されたデータストアは、一貫性 (C)・可用性 (A)・分断耐性 (P) を同時には保証できない。現実世界でネットワーク分断は不可避なので、実際に選べるのは分断が起きたその瞬間の「一貫性か可用性か」である。

ならば

「障害が起きる前に、各操作が一貫性と可用性のどちらを優先するか決めておけ。分断は必ず起きる。問われるのは「起きた時にシステムが何をするか」だけだ。」

ただし

PACELC / 調整可能な一貫性

この三角形はよく「3つから2つを選ぶ」と描かれるが、それは誤解を招く。分断を断る権利はこちらにはなく、ネットワークが勝手に断ってくる。P は選択ではなく世界の事実である。実際に選べるのは底辺の上の一点だけで、しかもそれを選ぶのは分断の最中ではなく、その前だ。

出典

Eric Brewer, Towards Robust Distributed Systems (PODC 基調講演, 2000); Seth Gilbert & Nancy Lynch が証明 (SIGACT News, 2002)。