BT

TokutekがMongoDB用の新コンセンサスアルゴリズムを発表

| 作者: Benjamin Darfler フォローする 0 人のフォロワー , 翻訳者 吉田 英人 フォローする 0 人のフォロワー 投稿日 2014年9月7日. 推定読書時間: 3 分 |

原文(投稿日:2014/08/05)へのリンク

Tokutekは,MongoDBに既存のリーダ選任アルゴリズム(Leader Election Algorithm)に代わる,新たなコンセンサスアルゴリズムの開発を発表した。Arkと名付けられたそのアルゴリズムは,同社のMongoDBフォークであるTokuMXで使用するために開発されたもので,既存のMongoDBのアルゴリズムの持つさまざまな問題に対処する。

設計面ではRaftPaxosのアルゴリズムから大きな影響を受けている。目的も同じく,厳密な一貫性保証を提供することにある。Raftとの違いは,MongoDBのアーキテクチャとプログラムモデルをサポートするために,プルベースの非同期レプリケーションモデルを実装している点だ。この点について開発者は,次のように説明している

... より広範なクライアント操作をサポートすることで,安全性とレイテンシの間のトレードオフポイントを開発者が選択できるようにします。さらにArkでは,Raftの同期型プッシュモデルに比較して,チェーンレプリケーションやマルチデータレプリケーションなど,さまざまなレプリケーショントポロジを,よりフレキシブルにサポートしています。

Tokutekでは,新アルゴリズムの必要性を説明するために,現在のMongoDBが備えているリーダ選任アルゴリズムの問題点を2つ指摘している。もっとも大きな問題点は正確性だ。Arkを発表したブログ記事の中ではZardosht Kasheff氏が,マジョリティ書き込み保証(write concern)を指定して成功した更新がロールバックされる可能性を指摘する。

私たちの大きな目標は,選任プロトコルを修正して,TokuMXを本当の意味でのCPシステムとすることです。それはつまり,ネットワークパーティションに対しても,一貫性を維持するということです。そのためには,マジョリティ書き込み保証指定で成功と認識された書き込みが,ネットワークパーティションに対しても失われないことを保証する必要があります。TokuMXおよびMongoDBは,現時点ではそうではありません

Tokutexが注目する第2の問題は,可用性に関するものだ。Leif Walsh氏と共同執筆した技術レポートの中で両氏は,MongoDBのレプリカセットがフェールオーバ時に30秒以上,使用可能になる可能性について説明している。

MongoDBの選任プロトコルでは,30秒以内に複数の選挙に"yes"を投じてはならない,という要件があります。... この30秒というしきい値が,実運用上,特に選任に失敗した場合に問題となる可能性があります。少なくとも30秒間,セットが必然的に使用可能になることで,後続の選任がさらに失敗する可能性があるのです。

Arkはこれらの障害に対して,TokutekDBグローバルトランザクション識別子(Global Transaction Identifier/GTID)の構造を利用して対象する。GTIDは64bit整数(term, opid)で構成される。オペレーションがプライマリにコミットされるとopidがインクリメントされる。新たなプライマリが選出されるとtermがインクリメントされ,opidが0にリセットされる仕組みだ。GTIDにおける用語は,Raftプロトコルの用語の概念と目的を同じくしている。この類似性のためArkは,厳密な一貫性保証を提供するためにRaftが使用されているものと同じソリューションを利用することができる。

Arkは現実のデータベースで動作するコンセンサスプロトコルの実装であると同時に,Raftコンセンサスアルゴリズムの柔軟性の証明でもある。MongoDBアーキテクチャに適合するように安全な方法でRaftを調整する作業は,それほど困難なものではなかった。この柔軟性が,Raftの大きなメリットであると考えてよいだろう。

Arkには公開中の開発ブランチがある。Tokutekでは現在,設計と実装の両面から,フィードバックを積極的に募集中だ。

この記事に星をつける

おすすめ度
スタイル

こんにちは

コメントするには InfoQアカウントの登録 または が必要です。InfoQ に登録するとさまざまなことができます。

アカウント登録をしてInfoQをお楽しみください。

あなたの意見をお聞かせください。

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする
コミュニティコメント

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする

ディスカッション

特集コンテンツ一覧

ASP.NET Core - シンプルの力

Chris Klug 2018年6月4日 午前3時26分

InfoQにログインし新機能を利用する


パスワードを忘れた方はこちらへ

Follow

お気に入りのトピックや著者をフォローする

業界やサイト内で一番重要な見出しを閲覧する

Like

より多いシグナル、より少ないノイズ

お気に入りのトピックと著者を選択して自分のフィードを作る

Notifications

最新情報をすぐ手に入れるようにしよう

通知設定をして、お気に入りコンテンツを見逃さないようにしよう!

BT