コンテンツにスキップ

コンセンサス・アルゴリズムのメモ

Raft

Elasticsearch

安全モジュールと呼ばれる独自のアルゴリズム

アルゴリズムの中核となる安全モジュールはシンプルかつ簡潔であり、Elasticsearchリポジトリの公式モデルとプロダクションコードの間は1対1で直接対応しています。 Paxos、Raft、Zab、Viewstamped Replication（VR）などの分散合意アルゴリズムのファミリーに精通していれば、中核となる安全モジュールについてもよく分かります。これは単一の書き換え可能なレジスタをモデル化し、Paxosの投票、Raftのターム、VRのビューに類似したマスター用語の概念を使用します。また、中核となる安全モジュールとその公式モデルは、クラスターブートストラップ、ノードの再起動における永続性、動的な再構成にも対応します。これらすべての機能は、システムがどのような状況でも適切に動作するために重要です。

Raftではない理由についても言及されている．

https://www.elastic.co/jp/blog/a-new-era-for-cluster-coordination-in-elasticsearch

Hadoop

Zookeeperを使うらしい．

Hadoopにおいて用いられる分散ファイルシステムのHDFSにおいては，ファイルのメタデータを管理するNameNodeの可用性向上のために，NameNodeを複数台構成にし，それらへの更新をStrong ConsistentにするためにZookeeperを用います

http://gihyo.jp/admin/serial/01/how_hadoop_works/0012

MySQL

PostgreSQL

Oracle DB

コンセンサス・アルゴリズムのリスト

  • Paxos
  • Raft
  • Zab
  • Viewstamped Replication
  • 2相コミット(Two-Phase Commit)
  • Chandra–Toueg consensus algorithm
  • Chubby
  • PBFT