PACELC定理

データベース理論において、PACELC 定理はCAP 定理の拡張です。分散コンピュータシステムでネットワーク分割 (P) が発生した場合、可用性 (A) と一貫性 (C) のどちらかを選択する必要がある (CAP 定理による) が、それ以外の場合 (E) は、分割が存在せずシステムが正常に動作している場合でも、レイテンシ (L) と一貫性の損失 (C) のどちらかを選択する必要があることを述べています。

概要

CAP定理は「PAC」とも呼ばれ、分散データストアはパーティションを含む実行において一貫性と可用性の両方を持つことはできないという不可能性定理です。これはレイテンシを調べることで証明できます。システムが一貫性を保証する場合、操作のレイテンシはメッセージの遅延とともに増大し、したがってネットワークがパーティション化されている場合、操作は最終的に終了できず、つまりシステムは可用性を保証できません。^[1]

パーティションがない場合、一貫性と可用性の両方を満たすことができます。^[2]そのため、PACELC はさらに進んで、システムがどのようにデータを複製するかを調べます。具体的には、パーティションがない場合、レイテンシと一貫性の間に追加のトレードオフ(ELC) が存在します。^[3]ストアがアトミックに一貫性がある場合、読み取りと書き込みの遅延の合計は、少なくともメッセージ遅延になります。実際には、ほとんどのシステムは、配信を保証するために時間指定の遅延ではなく明示的な確認に依存しており、一貫性を保証するために完全なネットワークラウンドトリップと、読み取りと書き込みの両方でのメッセージ遅延が必要です。^[1]対照的に、低レイテンシシステムでは、レイテンシを短縮するために一貫性が緩和されます。^[2]

PACELC スペースには 4 つの構成またはトレードオフがあります。

PA/EL - 一貫性よりも可用性とレイテンシを優先する
PA/EC - パーティションがある場合は可用性を選択し、それ以外の場合は一貫性を選択します
PC/EL - パーティションがある場合は一貫性を選択し、それ以外の場合はレイテンシを選択します
PC/EC - 常に一貫性を選択する

PC/EC と PA/EL は、アプリケーション開発者に自然な認知モデルを提供します。PC/EC システムは、ACID のようにアトミックな一貫性をしっかりと保証しますが、PA/EL はより複雑な一貫性モデルで高可用性と低レイテンシを提供します。対照的に、PA/EC と PC/EL システムは、一貫性の条件付き保証のみを行います。開発者は、保証が守られないケースを処理するためにコードを記述する必要があります。PA/EC システムは、システムが地理的地域にローカライズされ、レイテンシと一貫性のトレードオフが重要ではないインメモリデータグリッド業界以外ではまれです。^[4] PC/EL はさらに理解しにくいです。PC は、システムが完全に一貫していることを示すのではなく、ネットワークパーティションが発生したときにシステムがベースライン一貫性レベルを超えて一貫性を低下させないことを示します。代わりに、可用性が低下します。^[3]

マーク・ブルッカーのような専門家は、CAP定理はモノのインターネット（IoT）やモバイルアプリケーションに関連するものなど、断続的に接続された環境で特に重要であると主張しています。これらのコンテキストでは、停電やエレベーターなどの限られたスペースに入るときなど、困難な物理的条件によりデバイスが分割される可能性があります。クラウドアプリケーションなどの分散システムでは、より包括的で、ネットワーク分割がない場合でもレイテンシや一貫性などのトレードオフを考慮したPACELC定理を使用する方が適切です。 ^[5]

歴史

PACELC定理は、イェール大学のダニエル・アバディが2010年にブログ投稿で初めて説明し、^[2]彼は後に2012年に論文でそれを明らかにしました。^[3] PACELCの目的は、「複製システムの一貫性/遅延のトレードオフを無視することは、[CAPにおける]大きな見落としである。なぜなら、それはシステム動作中は常に存在するのに対し、CAPはネットワーク分割というおそらくまれな場合にのみ関連するからである」という彼の論文に対処することです。PACELC定理は、2018年にSIGACTニュース記事で正式に証明されました。^[1]

データベース PACELC 評価

^[3]オリジナルデータベースPACELCの評価は、以下のものです。^[6]その後の更新は、Wikipediaコミュニティによって行われました。

Amazon の初期 (内部) Dynamo、 Cassandra、Riak、およびCosmos DBのデフォルトバージョンはPA/EL システムです。パーティションが発生した場合、可用性のために一貫性を放棄し、通常の操作では、レイテンシを短縮するために一貫性を放棄します。
VoltDB /H-Store、Megastore、MySQL Cluster 、 PostgreSQLなどの完全な ACID システムはPC/EC です。つまり、一貫性を放棄せず、一貫性を実現するために可用性とレイテンシのコストを支払います。BigtableやHBaseなどの関連システムも PC/EC です。
Amazon DynamoDB (2012 年 1 月にリリース) は、PACELC 論文で検討された初期の (Amazon 内部の) Dynamo とはまったく異なります。^[6] DynamoDB は強力なリーダーモデルに従っており、すべての書き込みが厳密にシリアル化され (条件付き書き込みにはペナルティはありません)、書き込み後の読み取りの一貫性をサポートします。この保証は、リージョン間の「グローバルテーブル^[7]」には適用されません。DynamoDB SDK は、デフォルトで結果的に一貫性のある読み取りを使用します (可用性とスループットが向上します)。ただし、一貫性のある読み取りが要求されると、サービスはアイテムの現在のビューまたはエラーを返します。
Couchbase は、分割中に一貫性と可用性のさまざまなオプションを提供し、同様に分割がない場合のレイテンシと一貫性のさまざまなオプションも提供します。他のほとんどのデータベースとは異なり、Couchbase には単一の API セットはなく、すべてのデータサービスを均一に拡張/複製することもありません。書き込みの場合、Couchbase は可用性よりも一貫性を優先するため、正式には CP になりますが、読み取りの場合は、インデックスレプリケーション、必要な一貫性レベル、アクセスの種類 (単一ドキュメント検索、範囲スキャン、全文検索など) に応じて、ユーザーが制御できる変動性が大きくなります。それに加えて、複数の CP クラスターを取得して非同期レプリケーションで接続するデータセンター間レプリケーション (XDCR) と、組み込みデータベースで完全なマルチマスター (リビジョン追跡付き) 分散トポロジを作成する Couchbase Lite に応じて、さらに変動性があります。
Cosmos DB は、 P 中の C/A と E 中の L/C のトレードオフを可能にする 5 つの調整可能な一貫性レベルをサポートしています。Cosmos DB は指定された一貫性レベルに違反することはないため、正式には CP です。
MongoDB はPA/EC システムとして分類できます。ベースラインケースでは、システムは読み取りと書き込みの一貫性を保証します。
PNUTS は PC/EL システムです。
Hazelcast IMDGやほとんどのインメモリデータグリッドはPA/ECシステムの実装です。HazelcastはECではなくELとして構成できます。^[8]並行性プリミティブ（Lock、AtomicReference、CountDownLatchなど）はPC/ECまたはPA/ECのいずれかになります。^[9]
^{FaunaDBは、PACELC定理の著者[3]}であるDaniel Abadi博士によって作成されたトランザクションプロトコルであるCalvinを実装し、LCトレードオフの調整可能な制御をユーザーに提供します。これは、厳密にシリアル化可能なトランザクションの場合はPC/EC、シリアル化可能な読み取りの場合はELです。

参照

注記

^ abcd Dynamo、Cassandra、Riakには、LCトレードオフを制御するためのユーザーが調整可能な設定があります。^[6]
^ Cosmos DBには、LCトレードオフを制御するために選択可能な5つの一貫性レベルがあります。^[11]

参考文献

^ abc Golab, Wojciech (2018). 「PACELC の証明」ACM SIGACT ニュース49 ( 1): 73–81. doi :10.1145/3197406.3197420. S2CID 3989621.
^ abc Abadi, Daniel J. (2010-04-23). 「DBMS Musings: CAP の問題と、Yahoo のあまり知られていない NoSQL システム」。2016年 9 月 11 日閲覧。
^ abcde Abadi, Daniel J. 「現代の分散データベースシステム設計における一貫性のトレードオフ」(PDF)。イェール大学。
^ Abadi, Daniel (2019 年 7 月 15 日)。「条件付き一貫性保証の危険性」。DBMS Musings。2024年8 月 29 日閲覧。
^ データ集約型アプリケーションの設計: 信頼性、拡張性、保守性に優れたシステムを支える重要なアイデア。O'Reilly Media。ISBN 978-1449373320。
^ abc Abadi, Daniel J.; Murdopo, Arinto (2012-04-17). 「現代の分散データベースシステム設計における一貫性のトレードオフ」。 2022年7月18日閲覧。
^ 「グローバルテーブル - DynamoDB のマルチリージョンレプリケーション」。AWSドキュメント。2023 年1 月 4 日閲覧。
^ ab Abadi, Daniel (2017-10-08). 「DBMS Musings: Hazelcast と神話的な PA/EC システム」。DBMS Musings 。2017-10-20に閲覧。
^ ab 「Hazelcast IMDGリファレンスマニュアル」。docs.hazelcast.org 。 2020年9月17日閲覧。
^ ポーター、ケビン（2023年3月29日）。「PACELCでエアロスパイクはどこに位置しますか？」エアロスパイクコミュニティフォーラム。 2023年3月30日閲覧。
^ 「Azure Cosmos DB の一貫性レベル」。2021 年 6 月 21 日に取得。
^ Abadi, Daniel (2018-09-21). 「DBMS Musings: NewSQL データベースシステムは一貫性を保証できず、Spanner のせいだ」。DBMS Musings 。2019 年 2 月 23 日閲覧。
^ Zelinskie, Jimmy (2024-04-23). 「SpiceDB の概念: 一貫性」。SpiceDBドキュメント。2024-05-02に取得。

外部リンク

「現代の分散データベースシステム設計における一貫性のトレードオフ」、ダニエル・J・アバディ、イェール大学 PACELC を形式化したオリジナル論文
「CAP の問題と、Yahoo のあまり知られていない NoSQL システム」、ダニエル J. アバディ、イェール大学。PACELC について最初に説明した元のブログ投稿
「PACELC の証明」、ウォイチェフ・ゴラブ、ウォータールー大学 PACELC 定理の正式な証明

[lctradeoff-11] Dynamo、Cassandra、Riakには、LCトレードオフを制御するためのユーザーが調整可能な設定があります。^[6]

[csmsclvl-13] Cosmos DBには、LCトレードオフを制御するために選択可能な5つの一貫性レベルがあります。^[11]

[Golab-1] Golab, Wojciech (2018). 「PACELC の証明」ACM SIGACT ニュース49 ( 1): 73–81. doi :10.1145/3197406.3197420. S2CID 3989621.

[Musings2020-2] Abadi, Daniel J. (2010-04-23). 「DBMS Musings: CAP の問題と、Yahoo のあまり知られていない NoSQL システム」。2016年 9 月 11 日閲覧。

[Abadi-3] Abadi, Daniel J. 「現代の分散データベースシステム設計における一貫性のトレードオフ」(PDF)。イェール大学。

[4] Abadi, Daniel (2019 年 7 月 15 日)。「条件付き一貫性保証の危険性」。DBMS Musings。2024年8 月 29 日閲覧。

[5] データ集約型アプリケーションの設計: 信頼性、拡張性、保守性に優れたシステムを支える重要なアイデア。O'Reilly Media。ISBN 978-1449373320。

[ctmddsd-6] Abadi, Daniel J.; Murdopo, Arinto (2012-04-17). 「現代の分散データベースシステム設計における一貫性のトレードオフ」。 2022年7月18日閲覧。

[7] 「グローバルテーブル - DynamoDB のマルチリージョンレプリケーション」。AWSドキュメント。2023 年1 月 4 日閲覧。

[dbmsmusings201710-8] Abadi, Daniel (2017-10-08). 「DBMS Musings: Hazelcast と神話的な PA/EC システム」。DBMS Musings 。2017-10-20に閲覧。

[:0-9] 「Hazelcast IMDGリファレンスマニュアル」。docs.hazelcast.org 。 2020年9月17日閲覧。

[10] ポーター、ケビン（2023年3月29日）。「PACELCでエアロスパイクはどこに位置しますか？」エアロスパイクコミュニティフォーラム。 2023年3月30日閲覧。

[12] 「Azure Cosmos DB の一貫性レベル」。2021 年 6 月 21 日に取得。

[14] Abadi, Daniel (2018-09-21). 「DBMS Musings: NewSQL データベースシステムは一貫性を保証できず、Spanner のせいだ」。DBMS Musings 。2019 年 2 月 23 日閲覧。

[15] Zelinskie, Jimmy (2024-04-23). 「SpiceDB の概念: 一貫性」。SpiceDBドキュメント。2024-05-02に取得。