BT

InfoQ ホームページ ニュース TokutekがMongoDB用の新コンセンサスアルゴリズムを発表

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

ブックマーク

原文(投稿日: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では現在,設計と実装の両面から,フィードバックを積極的に募集中だ。

この記事に星をつける

おすすめ度
スタイル

特集コンテンツ一覧

RESTlessnessに打ち勝つ

Matt McLarty 2019年3月13日 午前7時39分

.NET CLIクイックツアー

Jeremy Miller 2019年2月18日 午前1時55分

.NET CoreとDevOps

Dave Swersky 2019年2月6日 午後11時46分

こんにちは

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

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

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

コミュニティコメント

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

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

BT

あなたのプロファイルは最新ですか?プロフィールを確認してアップデートしてください。

Eメールを変更すると確認のメールが配信されます。

会社名:
役職:
組織規模:
国:
都道府県:
新しいメールアドレスに確認用のメールを送信します。このポップアップ画面は自動的に閉じられます。