Bizurのメンバーシップ管理方法

でBizurアルゴリズムの概要を説明した。

Bizurアルゴリズムは全世界のエンジニアにとって興味のあるものであったが、論文を読むのはひたすらだるく、さくっとまとまった資料があれば良いが存在しないという状態だった。だからおれはBizurを紹介した。世界各国からアクセスがあり、作った甲斐はあった。

論文には書いてないが明らかなアイデアを追記しよう。BizurがShardを導入している理由は、LeaderをBucketレベルで持つ負荷を軽減するためというのが性能的な意味合いだが、Shardが論理的に完全に独立したものと出来ることがより大きい。

これによって、Bizurのロジックは単体のShard(中にBucketがたくさん入ってる)を意識して実装出来るようになる。これは何をもたらすかというと、Shardごとにメンバーシップを決めることが出来るということだ。

メンバーシップを決める方法は色々ある。Bizurがメンバーシップ変更の参考にしているSMARTではPaxosを前提としたアルゴリズムを紹介しているがこれは実はBizurには直接は適用出来ない。なぜかというと、Bizurはlog-lessであり、メンバーシップ変更ログのインデックスをメンバーシップの認識に使うことは出来ないからだ。私はエズラに質問した。彼らは確かに別の実装をとっているが、その内容はオープンに出来ないかも知れないから言わないというのと、そもそもおれも具体的な実装が見えなかったので説明が出来ない。

メンバーシップをどうやって変更するかという方式は色々やりようがあるので各自で考えていただくとして、Shardごとにメンバーシップを決められるということは「このShardはノードAとEとJにだけ複製する」ということが出来るということだ。しかもその決定はシステムの外で行うことが出来る点も見逃せない長所だ。なぜならば、ロジックを独立してテスト出来るからである。

ただし、何を作るかによっては誰がリーダーかという情報は全員で持つ必要が出る場合もある。その複製するノードを知っていることが前提であれば別に良いが、そうでなくてどのノードからもすべてのキーがrw出来るということにするならば、複製ノード内のリーダにたどり着けなければいけなくなる。どのようにするかひ・み・つ