Agile Cat — in the cloud

Database System エラー と Eventual Consistency と CAP Theorem – by Michael Stonebraker _1

Posted in NoSQL by Agile Cat on April 16, 2010

Errors in Database Systems, Eventual Consistency, and the CAP Theorem _1 
Michael Stonebraker
April 5, 2010
http://cacm.acm.org/blogs/blog-cacm/83396-errors-in-database-systems-eventual-consistency-and-the-cap-theorem/fulltext

Stonebraker_Michael_thumb[3]

Recently, there has been considerable renewed interest in the CAP theorem [1] for database management system (DBMS) applications that span multiple processing sites. In brief, this theorem states that there are three interesting properties that could be desired by DBMS applications:

最近になって、マルチ・プロセシング・サイトをまたぐ DBMS アプリケーションのための CAP theorem [1] において、かなりの量の関心事が再考されている。 手短かに説明すると、この定理(theorem)には、DBMS アプリケーションが必要とするだろう、3つの興味深い特性がある:

C: Consistency. The goal is to allow multisite transactions to have the familiar all-or-nothing semantics, commonly supported by commercial DBMSs. In addition, when replicas are supported, one would want the replicas to always have consistent states.

C: Consistency. そのゴールは、聴きなれた all-or-nothing セマンティクスを持ち、一般的に商用 DBMS にサポートされる、マルチ・サイト・トランザクションを実現することにある。それに加えて、レプリカがサポートされるときに、複数のレプリカに対して、常にコンシステントな状態が望まれる点にも留意する。

A: Availability. The goal is to support a DBMS that is always up. In other words, when a failure occurs, the system should keep going, switching over to a replica, if required. This feature was popularized by Tandem Computers more than 20 years ago.

A: Availability. 言い換えれば、失敗が生じたときに、システムは必要に応じてレプリカへの切り替えを行い、稼働し続ける必要がある。 この機能は、20年以上も昔に、Tandem Computers により普及したものである。

P: Partition-tolerance. If there is a network failure that splits the processing nodes into two groups that cannot talk to each other, then the goal would be to allow processing to continue in both subgroups.

P: Partition-tolerance. ネットワーク障害が発生した場合には、相互に交信することのない 2つのグループに、処理ノードを分割する。 したがって、このゴールは、2つのサブ・グループ内で処理を継続するものになるだろう。

The CAP theorem is a negative result that says you cannot simultaneously achieve all three goals in the presence of errors. Hence, you must pick one objective to give up.

CAP theorem とは、エラーが生じたときに、すべての 3つのゴールが同時には成立しないという、否定的な結果を伝える定理である。 それ故に、諦めるべき 1つのゴールを選択する必要がでてくる。

In the NoSQL community, this theorem has been used as the justification for giving up consistency. Since most NoSQL systems typically disallow transactions that cross a node boundary, then consistency applies only to replicas. Therefore, the CAP theorem is used to justify giving up consistent replicas, replacing this goal with “eventual consistency.” With this relaxed notion, one only guarantees that all replicas will converge to the same state eventually, i.e., when network connectivity has been re-established and enough subsequent time has elapsed for replica cleanup. The justification for giving up C is so that the A and P can be preserved.

NoSQL コミュニティにおいては、コンシステンシーを堂々と諦める理由として、この定理は利用されてきた。 大半の NoSQL システムでは、一般的にノード・バウンダリーを横断するトランザクションは認められないため、コンシステンシーはレプリカだけに適用される。 それ故に CAP theorem は、コンシステント・レプリカの断念を正当化するために用いられ、そのゴールは “eventual consistency” に置き換えられた。 このように緩やかな概念により、すべてのレプリカが、最終的には同一のステートに集約されることだけが保証される。つまり、ネットワークの接続性を何度でも確立でき、既存のレプリカを排除するための充分な時間が確保できるときに、この概念は成り立つ。 したがって、C の断念を正当化することで、A とP が成立することになる。

The purpose of this blog post is to assert that the above analysis is suspect, and that recovery from errors has more dimensions to consider. We assume a typical hardware model of a collection of local processing and storage nodes assembled into a cluster using LAN networking. The clusters, in turn, are wired together using WAN networking.

このブログ・ポストの目的は、上記の分析が疑わしく、また、エラーからのリカバリは検討すべき数多くの次元を持つと、断言することにある。 ここで私たちが想定するものは、ローカル処理のコレクションにおける一般的なハードウェア・モデルと、LAN ネットワーキングを用いてクラスタ内にアセンブルされるストレージ・ノードである。なお、これらのクラスタは、WAN ネットワーキングを用いて、順番に接続されていく。

Let’s start with a discussion of what causes errors in databases. The following is at least a partial list:

さあ、データベースのエラーをもたらすものについて、一緒に論考していこう。 以下のリストは、少なくとも部分的な要因を示している:

1) Application errors. The application performed one or more incorrect updates. Generally, this is not discovered for minutes to hours thereafter. The database must be backed up to a point before the offending transaction(s), and subsequent activity redone.

1) Application errors. アプリケーションにおいて、1つあるいは複数の、不適切なアップデートが実行されれた。 一般的に、その後の数分~数時間の間、この問題は発見されない。この不適切なトランザクションの後に、データベースのバックアップ・ポイントが生成され、それに続くアクティビティが再実行される。

2) Repeatable DBMS errors. The DBMS crashed at a processing node. Executing the same transaction on a processing node with a replica will cause the backup to crash. These errors have been termed Bohr bugs. [2]

2) Repeatable DBMS errors. DBMS が、は処理ノードにおいてクラッシュした。 レプリカを用いた処理ノード上での、同じトランザクションの実行は、バックアップをクラッシュさせるだろう。 こうしたエラーは、Bohr バグと呼ばれる。 [2]

3) Unrepeatable DBMS errors. The database crashed, but a replica is likely to be ok. These are often caused by weird corner cases dealing with asynchronous operations, and have been termed Heisenbugs [2]

3) Unrepeatable DBMS errors. データベースがクラッシュしたが、レプリカには問題が生じない可能性は高い。 大半の場合、こうした状況は非同時性オペレーションを取り扱う weird corner cases により引き起こされ、Heisen バグと呼ばれる。 [2]

4) Operating system errors. The OS crashed at a node, generating the “blue screen of death.”

4) Operating system errors. ノードで OS がクラッシュし、“blue screen of death” をもたらす。

5) A hardware failure in a local cluster. These include memory failures, disk failures, etc. Generally, these cause a “panic stop” by the OS or the DBMS. However, sometimes these failures appear as Heisenbugs.

5) A hardware failure in a local cluster. メモリやディスクにおける障害などが含まれる。 一般的に、OS あるいは DBMS による、 “panic stop”  が引き起こされる。 しかし、これらの障害は、Heisen バグとして現われる場合もある。

6) A network partition in a local cluster. The LAN failed and the nodes can no longer all communicate with each other.

6) A network partition in a local cluster. LAN における障害に続いて、ノード間でのすべての相互通信が停止する。

7) A disaster. The local cluster is wiped out by a flood, earthquake, etc. The cluster no longer exists.

7) A disaster. ローカル・クラスタが、洪水や地震などによるって全壊する。 もはや、クラスタは存在しない。

8) A network failure in the WAN connecting clusters together. The WAN failed and clusters can no longer all communicate with each other.

8) A network failure in the WAN connecting clusters together. WAN における障害に続いて、ノード間でのすべての相互通信が停止する。

References

[1] Eric Brewer, “Towards Robust Distributed Systems,” http://www.cs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf

[2] Jim Gray, “Why Do Computers Stop and What Can be Done About It,” Tandem Computers Technical Report 85.7, Cupertino, Ca., 1985. http://www.hpl.hp.com/techreports/tandem/TR-85.7.pdf

<続く>

ーーーーー

間違い勘違いなど見つかりましたら、お知らせください。 ーーー A.C.

ーーーーー

<関連>
Database System エラー と Eventual Consistency と CAP Theorem _2
Stonebraker と CAP Theorem と Databases – by James Hamilton
イベンチュアル・コンシステンシーはお好き?
かなり気になる、NoSQL 関連のポスト : Cassandra や CAP Theorem など
Google 的 クラウド連携の ABC ?

Database System エラー と Eventual Consistency と CAP Theorem – by Michael Stonebraker _2

Posted in NoSQL by Agile Cat on April 16, 2010

Errors in Database Systems, Eventual Consistency, and the CAP Theorem _2 
Michael Stonebraker
April 5, 2010
http://cacm.acm.org/blogs/blog-cacm/83396-errors-in-database-systems-eventual-consistency-and-the-cap-theorem/fulltext

Stonebraker_Michael

First, note that errors 1 and 2 will cause problems with any high availability scheme. In these two scenarios, there is no way to keep going; i.e., availability is impossible to achieve. Also, replica consistency is meaningless; the current DBMS state is simply wrong. Error 7 will only be recoverable if a local transaction is only committed after the assurance that the transaction has been received by another WAN-connected cluster. Few application builders are willing to accept this kind of latency. Hence, eventual consistency cannot be guaranteed, because a transaction may be completely lost if a disaster occurs at a local cluster before the transaction has been successfully forwarded elsewhere. Put differently, the application designer chooses to suffer data loss when a rare event (such as a disaster) occurs, because the performance penalty for avoiding it is too high.

最初に指摘しておきたいのは、error 1 と 2 が、あらゆる高可用性スキームであっても、問題を引き起こす点だ。 この 2つのシナリオにおいては、運用を継続する方法が無く、可用性を達成することが不可能になる。それと同様に、レプリカ・コンシステンシーは無意味になり、最新の DBMS ステートは、単に不正確なものとなる。 Error 7 の回復は可能だが、対象となるトランザクションが、WAN で接続された他のクラスタに受け入れられたという保証の後に、ローカル・トランザクションがコミットされていることが条件となる。この種のレイテンシーを受け入れようとするアプリケーション・ビルダーは、ほとんど居ない。 それ故に、イベンチュアル・コンシステンシーは保証されない。 その理由は、トランザクションの他所への転送が成功する前に、ローカル・クラスタに大災害が起こる場合に、トランザクションが完全に失われる可能性があるからだ。 言い換えると、パフォーマンスのペナルティーがあまりにも高いため、アプリケーション・デザイナーは、(大惨事のような)稀な出来事が起こる際に、データの喪失を受け入れるという選択とる。

As such, errors 1, 2, and 7 are examples of cases for which the CAP theorem simply does not apply. Any real system must be prepared to deal with recovery in these cases. The CAP theorem cannot be appealed to for guidance.

このように、CAP theorem が単純に適用されないケースの例として、error 1、2、7がある。 しかし、現実のシステムでは、このような場合にリカバリを取り扱うための、用意を整えているに違いない。 そして、CAP theorem にガイダンスを求めることはできない。

Let us now turn to cases where the CAP theorem might apply. Consider error 6 where a LAN partitions. In my experience, this is exceedingly rare, especially if one replicates the LAN (as Tandem did). Considering local failures (3, 4, 5, and 6), the overwhelming majority cause a single node to fail, which is a degenerate case of a network partition that is easily survived by lots of algorithms. Hence, in my opinion, one is much better off giving up P rather than sacrificing C. (In a LAN environment, I think one should choose CA rather than AP). Newer SQL OLTP systems (e.g., VoltDB and NimbusDB) appear to do exactly this.

ここで、CAP theorem の適用が可能なケースに、話題を切り替えよう。LAN パーティションにおける、error 6 について考えてほしい。 私の経験において、とりわけ Tandem がそうしたように、LAN がリプリケートされている場合には、このような状況に陥るのはきわめて稀である。 ローカルな失敗(3、4、5、6)を考慮に入れると、シングル・ノードを失敗させる要因は、きわめて多数になる。 それらは、ネットワーク・パーティションが劣化したケースであり、各種のアルゴリズムにより容易に生き残らせることが可能である。 それ故に、私の意見としては、C を犠牲にするよりも、P を断念する方が適切な選択となる(LAN 環境では、AP よりも CA を選択すべきと考える)。 最近の SQL OLTP システム(たとえば  VoltDB やNimbusDB)では、こうした処理が正確に行われると思われる。

Next, consider error 8, a partition in a WAN network. There is enough redundancy engineered into today’s WANs that a partition is quite rare. My experience is that local failures and application errors are way more likely. Moreover, the most likely WAN failure is to separate a small portion of the network from the majority. In this case, the majority can continue with straightforward algorithms, and only the small portion must block. Hence, it seems unwise to give up consistency all the time in exchange for availability of a small subset of the nodes in a fairly rare scenario.

次に、WAN パーティションにおける error 8 を考えてみよう。 今日の WAN には、充分な冗長性があるので、その障害はきわめて稀なものとなる。 私の経験においては、ローカルでの障害と、アプリケーション・エラーの確率の方がずっと高い。 さらに言えば、最も確率の高い WAN 障害は、ネットワークの小さなかたまりを、その他の大部分から分離してしまうことである。 この場合、大部分の方は簡単なアルゴリズムを用いて継続され、小さい部分だけがブロックされるはずだ。 それ故に、ノード上の小さなサブ・セットの可用性と引き換えに、常にコンシステンシーを断念することは、かなり稀なシナリオであり、賢明ではないと思われる。

Lastly, consider a slowdown either in the OS, the DBMS, or the network manager. This may be caused by skew in load, buffer pool issues, or innumerable other reasons. The only decision one can make in these scenarios is to “fail” the offending component; i.e., turn the slow response time into a failure of one of the cases mentioned earlier. In my opinion, this is almost always a bad thing to do. One simply pushes the problem somewhere else and adds a noticeable processing load to deal with the subsequent recovery. Also, such problems invariably occur under a heavy load–dealing with this by subtracting hardware is going in the wrong direction.

最後に、 OS/DBMS/ネットワーク・マネージャのスローダウンについても考えてみよう。 それらは、負荷による歪みや、バッファプールの問題、そして数え切れない程の理由により引き起こされるだろう。 これらのシナリオにおいて可能な唯一の判断は、不適切なコンポーネントを "fail" にすることだ。 つまり、反応が遅いという状況を、以前に言及した失敗のケースに置き換えることである。私の意見として、それを行うことは、大半のケースに置いて、良くないことになる。 つまり、問題を他所に押し出すことになり、また、継続してリカバリを行う際に注意すべき、処理の負荷を増大することにつながる。さらに、この種の問題は、重い負荷のもとで一様に引き起こされる。 つまり、ハードウェアを間引いて処理することは、間違った方向の選択となる。

Obviously, one should write software that can deal with load spikes without failing; for example, by shedding load or operating in a degraded mode. Also, good monitoring software will help identify such problems early, since the real solution is to add more capacity. Lastly, self-reconfiguring software that can absorb additional resources quickly is obviously a good idea.

明らかなことは、ピークを持つ負荷を、失敗せずに取り扱うソフトウエアを記述すべきである。 たとえば、負荷を発散させるか、ディグレート・モードでの稼働により対処する。 また、現実のソリューションでは、さらに多くのキャパシティが加えられるはずなので、適切なモニタリング・ソフトウェアの利用が、こうした問題の早期の識別に役立つだろう。 最後になるが、追加のリソースを迅速に吸収できる、何度でもセルフ・コンフィグレーションが可能なソフトウェアは、明らかに良いアイデアである。

In summary, one should not throw out the C so quickly, since there are real error scenarios where CAP does not apply and it seems like a bad tradeoff in many of the other situations.

簡単にまとめると、CAP が適用されない場所に本質的なエラー・シナリをがあるため、早急に C を諦めるべきではない。 そして、それは、大半の状況において、不適切なトレードオフになると思われる。

References

[1] Eric Brewer, “Towards Robust Distributed Systems,” http://www.cs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf

[2] Jim Gray, “Why Do Computers Stop and What Can be Done About It,” Tandem Computers Technical Report 85.7, Cupertino, Ca., 1985. http://www.hpl.hp.com/techreports/tandem/TR-85.7.pdf

Disclosure: In addition to being an adjunct professor at the Massachusetts Institute of Technology, Michael Stonebraker is associated with four startups that are either producers or consumers of database technology.

ーーーーー

<関連>
Database System エラーと Eventual Consistency と CAP Theorem_1
Stonebraker と CAP Theorem と Databases – by James Hamilton
イベンチュアル・コンシステンシーはお好き?
かなり気になる、NoSQL 関連のポスト : Cassandra や CAP Theorem など
Google 的 クラウド連携の ABC ?

%d bloggers like this: