19

シェアード ナッシング アーキテクチャとマルチバージョン同時実行制御を使用して、分散データベース システムを作成する予定です。冗長性は、非同期レプリケーションによって実現されます(システム内のデータが一貫している限り、障害が発生した場合に最近の変更を失うことは許されています)。データベース エントリごとに、1 つのノードにマスター コピーがあり (そのノードだけが書き込みアクセス権を持っています)、さらに 1 つ以上のノードにスケーラビリティと冗長性のためにエントリのセカンダリ コピーがあります (セカンダリ コピーは読み取り専用です)。 . エントリのマスター コピーが更新されると、タイムスタンプが付けられ、最終的にエントリの最新バージョンを取得できるように、セカンダリ コピーを持つノードに非同期で送信されます。マスター コピーを持つノードはいつでも変更できます。別のノードがそのエントリを書き込む必要がある場合、マスター コピーの現在の所有者に、そのノードにそのエントリのマスター コピーの所有権を与えるように要求します。

最近、クラスター内のノードがダウンしたときにどうするか、フェイルオーバーにどの戦略を使用するかについて考えています。ここにいくつかの質問があります。少なくともそれらのいくつかに代わる利用可能な代替案を知っていただければ幸いです。

  • 分散システムでフェイルオーバーを行うためのアルゴリズムは何ですか?
  • 分散システムのコンセンサスにはどのようなアルゴリズムがありますか?
  • クラスター内のノードは、ノードがダウンしていることをどのように判断する必要がありますか?
  • 他のノードがそれらのエントリを回復できるように、ノードはどのデータベース エントリが障害発生時に障害ノードにマスター コピーを持っていたかをどのように判断する必要がありますか?
  • どのノードがいくつかのエントリの最新のセカンダリ コピーを持っているかを判断する方法は?
  • どのノードのセカンダリ コピーを昇格させて新しいマスター コピーにするかを決定する方法は?
  • ダウンしたはずのノードが突然何事もなかったかのように戻ってきた場合、どのように対処しますか?
  • ネットワークが一時的に 2 つに分割され、双方がもう一方の側が停止したと考えるスプリット ブレイン シナリオを回避するにはどうすればよいでしょうか?
4

5 に答える 5

31 
* What algorithms there are for doing failover in a distributed system?

おそらくアルゴリズムではなく、システムです。尋ねた質問に基づいてアーキテクチャを設計する必要があります。

* What algorithms there are for consensus in a distributed system?

おそらく Paxos を実装したいと思うでしょう。シンプルな Paxos を正しく理解するのはそれほど難しくありません。防弾にしようとしている場合は、Google の「Paxos Made Live」の論文を読んでください。高性能にしたい場合は、Multi-Paxos を検討してください。

* How should the nodes in the cluster determine that a node is down?

依存します。ハートビートは、実際にはこれを行うための非常に優れた方法です。問題は、誤検知があることですが、それは一種の避けられないことであり、管理可能な負荷を持つ同じ LAN 上のクラスターでは正確です。Paxos の良いところは、誤検知が自動的に処理されることです。ただし、他の目的で実際に障害情報が必要な場合は、ノードが障害として検出されても問題ないことを確認する必要がありますが、実際には負荷がかかっており、ハートビートに応答するのに時間がかかっています。

* How should the nodes determine that what database entries had their master copy on the failed node at the time of failure, so that other nodes may recover those entries?
* How to decide that which node(s) has the latest secondary copy of some entry?
* How to decide that which node's secondary copy should be promoted to be the new master copy?

Google FileSystem の論文を読むと本当に役立つと思います。GFS には、どのノードがどのブロックを持っているかを追跡する専用のマスター ノードがあります。このスキームはうまくいくかもしれませんが、重要なのは、このマスターへのアクセスを最小限に抑えることです。

この情報を専用ノードに保存しないと、どこにでも保存する必要があります。マスター ホルダーの ID でデータをタグ付けしてみてください。

* How to handle it, if the node which was though to be down, suddenly comes back as if nothing happened?

上記を参照してください。ただし、基本的なポイントは、マスターでなくなったノードがマスターであると考える可能性があるため、注意する必要があるということです。あなたが解決していないと思うことの1つは、更新がマスターに到達する方法、つまり、クライアントが更新を送信するノードをどのように知るかです。

* How to avoid split-brain scenarios, where the network is temporarily split into two, and both sides think that the other side has died?

Paxos は、完全な分割の場合に進行を妨げることによってここで機能します。それ以外の場合は、以前と同様に、非常に注意する必要があります。

一般に、どのノードがどのデータ項目をマスターとして取得するかを知るという問題を解決すれば、アーキテクチャの修正に向けて長い道のりを歩むことができます。更新を受信するノードだけをマスターにすることはできないことに注意してください。2 つの更新が同時に発生した場合はどうなるでしょうか。同期されたグローバル クロックにも依存しないでください。可能であれば、すべての書き込みでコンセンサスを実行することを避けたいと思われるので、代わりに、低速のマスター フェイルオーバー プロトコルと高速の書き込みパスを使用することをお勧めします。

詳細をお知りになりたい場合は、お気軽にメールでお問い合わせください。私のブログhttp://the-paper-trail.orgでは、このようなことをたくさん扱っています。

乾杯、

ヘンリー

于 2009-03-08T23:57:36.113 に答える
10

You are asking an absolutely massive question, and a lot of what you want to know is still in active research.

Some thoughts:

  • Distributed systems are difficult, because there are no foolproof systems to deal with failures; in an asynchronous system, there is no way to be sure that a node is down or whether there is network delay. This may sound trivial, but it really isn't.
  • Achieving consensus can be done by the Paxos family of algorithms, versions of which are used in Google's bigtable, and in other places.

You'll want to delve into a distributed systems textbook (or several). I like Tannenbaum's Distributed Systems: Principles and Paradigms

于 2009-03-06T23:48:57.790 に答える
3

分散システムと分散アルゴリズム (Paxos の実装を含む) について多くを語っている素晴らしいブログは、http://the-paper-trail.org/です。

于 2009-03-08T18:57:19.767 に答える
2

This problem was solved by DEC for VMS with the Distributed Lock Manager. Modern solutions are based on this design. Read the Wikipedia article for some current solutions. You should look at OCFS2, which is now part of the Linux kernel.

于 2009-03-06T23:50:23.747 に答える
0

あなたの質問のほんの一部に取り組んでください:あなたが説明するシナリオでは、どのノードが最新のセカンダリコピーを持っているかを(抽象的に)決定する方法はありません。せいぜい、一部のノードは、（少しの通信の後）ノードの中で、知っている/見ることができ、それらを知っている/見ることができ、見ることができない古いマスターが最新のものを持っているノードをポーリングして判断できます。コピー。しかし：

  • 到達できないノードのステータスを確認できない
  • 到達できないノードのステータスを確認できない
  • 彼らは、古いマスターを見ることができないときにノードのステータスについて知っていると思っていることが最新であるかどうか確信が持てません。マスターは、ネイバーがステータスを報告した後に共有ネイバーを更新した可能性があります。

より広範な問題については、memcached などが問題をどのように処理しているかを調べ、特にリストを読んで、理論と実践が一致したときにどのような問題が発生したかを確認することをお勧めします。

于 2009-03-06T23:37:31.703 に答える