トップ > テクノロジー > クラウドネイティブデータベースを実現する技術(の一端)を理解してみた

クラウドネイティブデータベースを実現する技術(の一端)を理解してみた

テクノロジー クラウドコンピューティング アーキテクチャ アドベントカレンダー

はじめに

こちらは NTT Communions Advent Calender 2021 の 24 日目の記事です。

はじめまして、データプラットフォームサービス部の tnkgw と申します。 普段は、Smart Data Platform の契約管理機能を開発しています。

本記事では、クラウドネイティブデータベースを実現する技術の一端を理解するということでAlibaba Cloud で提供されている PolarDB のファイルシステムである PolarFS で用いられている分散合意プロトコルの ParallelRaft 1について解説します。

Raft

Raft は Ongaro らにより提唱された2理解と実装のしやすさに重きをおいて考案された分散合意アルゴリズムです。 この章では、本記事を読むにあたって前提知識となる Raft の各要素について概要を紹介します。

Raft が実現すること

Raft は、いくつかのノードで構成されたクラスタにおいて各ノードにログエントリという形でデータを複製することでクラスタとして一貫した状態をクライアントへ提供できます。 また、クラスタ内のノードが一貫した状態を持つことによりノードが故障しても残ったノードで継続して稼働し続けることによりクラスタの可用性を実現します。

各用語について

まず、Raft において扱われる各用語について説明します。

  • ノードの役割
    • Leader
      • 後述する Leader Election により選ばれるノードに割り当てられる。
      • クライアントからのクラスタへのリクエストは全て Leader に対して送信され、そのリクエスト内容は後述のログレプリケーションにより Follower ノードへ複製される。
      • Leader は、自身が故障していないことを知らせるためにハートビートメッセージをクラスタ内の各ノードへ送信する。
    • Follower
      • Leader から受け取ったログエントリを含むメッセージや後述する Candidate から受け取った投票要求メッセージに対してアクションを行うのみの役割。
    • Candidate
      • Follower から遷移して、次の Leader となる役割。
  • ログエントリ
    • クラスタが受信したデータ等を保持しておく形式で、配列で各ノードは保持する。ログエントリには、複製されるデータ本体の他にログエントリが作成されたタームの値とインデックスの値が含まれる。
  • インデックス
    • 各ノードが連続した順番で保持するログエントリに対して振られる番号。
  • ターム
    • Raft における論理時間で、単調増加する数値で表現される。Raft における合意はその区切られたタームにて行われる。また、1つのタームにおいて Leader はクラスタ内に1つのみ存在するという制約がある。

f:id:NTTCom:20211224125146p:plain

図1. Raft におけるタームのイメージ

Leader Election

Leader Election では、クラスタ内の各タームの唯一の Leader となるノードを決定するフェーズとなります。 Leader Election はクラスタが始動し始めたタイミングや予め存在していた Leader のノードが故障して Leader が不在となったタイミングで行われます。

Leader Election の流れについては以下の順番で行われます。

  1. クラスタの初期状態は、全てのノードは Follower からスタートする。各ノードは、それぞれランダムな値でタイムアウトするタイマーを持っておりメッセージを受信しない場合タイマーの値はデクリメントしていく。 タイムアウト後、Follower は Candidate へ遷移する。
  2. Candidate へ遷移したノードは、自身が保持しているタームの値を1つ増やして、投票要求のメッセージを自身以外のノードへ送信される。 投票要求メッセージには、送信時のタームの値と保持しているログエントリの最新のインデックスが含まれる。
  3. 投票要求メッセージを受信した Follower は基本的に最初に受け取ったメッセージに対して true の値を返信する。 加えて投票要求メッセージに含まれるタームの値とインデックスの値に対して以下の条件を判定要素とする。
    • 投票要求メッセージに含まれるタームの値 > 自身の最新のログエントリのタームの値
    • 投票要求メッセージに含まれるインデックスの値 > 自身のログエントリのインデックスの値（自身の最新のログエントリのタームの値と同じ場合）
  4. Candidate は過半数の Follower から true のメッセージを受信すると Leader へ遷移する。

f:id:NTTCom:20211224125152p:plain

図2. Leader Election の流れ

また、ノードの各役割の遷移は以下のようになります。

f:id:NTTCom:20211224125158p:plain

図3. Raft のノードの役割の遷移図

Log Replication

Log Replication では、Leader が保持するログエントリをクラスタ内の他のノードへ複製するフェーズです。 このフェーズによりクラスタ内のノード間の一貫性した状態がつくられて、クラスタの可用性を実現します。

Log Replication の流れについては以下の順番で行われます。

  1. クラスタへリクエストがあった場合は、Leader がそのリクエストを受け取る。Leader は、現在のタームの値を含めたログエントリを作成して、リストへ追加する。
  2. Leader は作成したログエントリをログエントリ複製メッセージに含めて Follower ノードへ送信する。また、メッセージには、送信するログエントリの1つ前のログエントリのタームの値とインデックスの値を含める。
  3. Follower は、受け取ったメッセージについて自身が保持しているログエントリとの関係を判定する。判定には、受け取ったログエントリの1つ前のタームとインデックスの値を用いる。 Follower は、このタームとインデックスの値が保持する先頭のログエントリのものと一致するか判定する。一致した場合、受信したログエントリを自身のリストへ追加して、Leader に true の値を返信する。 また、異なった場合は false の値を返信する。
  4. Leader は、過半数の Follower から true の値を受信すると追加したログエントリをコミットする。その後、Leader はコミットしたログエントリのインデックスを含めたメッセージを送信する。
  5. Follower は、Leader から受信したコミットされたインデックスの値を確認してそのインデックスまでの自身のログエントリをコミットする。

f:id:NTTCom:20211224125205p:plain

図4. P1 を Leader とした Log Replication の例

ParallelRaft

ParallelRaft は、PolarFS における ストレージサーバ間の一貫性と可用性を実現するために Raft をカスタマイズして考案された分散合意プロトコルです。 既存の Raft と大きく異なるポイントとしては、Raft の根本的なコンセプトである厳密な順序でログエントリを複製するという制約をなくしていることです。 そのような制約をなくしたうえで ParallelRaft がどのようにノード間の一貫性を実現しているか各要素について紹介していきます。

Raft の課題

まず、PolarFS の開発チームが Raft を改善するに至った背景について紹介します。

Raft を高スループットな分散化されたストレージサーバの可用性を実現するために用いた場合以下のような理由でパフォーマンスに課題があります。（原論文）

  • Raft の作成されたログエントリを順繰りに複製・コミットするという特性上、クラスタに対して書き込み要求が多数実行された場合も順繰りに適用されるため待ち時間が発生してスループットが低下する。
  • 複数のコネクションを張ったノード間では、ネットワーク遅延等で必ずしも順繰りにログが届かずに行き違いが発生してしまう可能性がある。
    • 行き違いが発生した場合、そのログエントリは Leader が再送しなければならず場合によっては Leader のコミットが遅れる。
    • しかし、通信網の可用性と高度な同時処理環境を実現するためには複数のコネクションが必要となる。

f:id:NTTCom:20211224125211p:plain

図5. ログエントリがインデックスの順番通りに届かず、コミットが遅れる例

Out-of-Order Log Replication

Out-of-Order Log Replication は、上記の Raft の課題を解決するために ParallelRaft において提案されている Log Replication の手法です。 Out-of-Order Log Replication では、Out-of-Order Acknowledge と Out-of-Order Commit の2つのステップによりノード間の一貫性が実現されます。

  • Out-of-Order Acknowledge
    • Follower が Leader から受信したログエントリは自身が保持するログエントリとの関係性を確認せず即時に追加する。
      • 変更の背景として、順繰りにログエントリを受け取る過程で発生する余分な待ち時間による書き込みのレイテンシを短縮するため。
  • Out-of-Order Commit
    • Leader は、過半数の Follower に対して複製できたと確認できた時点で先行するログエントリがコミットされていなくてもコミットする。
      • このようなコミットセマンティクスについては、強力な一貫性を保証しないストレージシステムにとっては許容できるものとなっている。（原論文）

f:id:NTTCom:20211224125218p:plain

図6. ログリストが欠落している例

以上のように順不同でログエントリを追加、コミットした場合、Raft のように厳密な順序を保証されたうえでの複製ではないため前後のログエントリが欠落して書き込まれる可能性があります。 そこでログエントリをストレージに書き込む際、書き込まれる LBA が重複しないように Look Behind Buffer というデータ構造をログエントリに追加します。 Look Behind Buffer には、直前の N 個のログが変更した LBA の情報が含まれています。 Follower は、このデータ構造を参照することで欠落したログを補完することが可能となります。

ParallelRaft における Leader Election

次に ParallelRaft における Leader Election について紹介します。

ParallelRaft における Leader Election でも複製された最新のログレプリケーションを保持する Candidate が Leader に選ばれることは同じです。 ただし、前述したとおり ParallelRaft では Follower がログリストを欠落した状態で保持している可能性があり、投票において Candidate へ遷移したノードもこれに当てはまります。 それでは、そのような状況下で全てのログエントリを保持する Leader を選出するにはどうすれば良いでしょうか？

そこでParallelRaft の Leader Election では、Candidate から Leader へ遷移する前にノード同士でログをマージするフェーズが追加されます。 そのフェーズでは、Candidate が Leader Candidate、Follower が Follower Candidate というテンポラリな役割に遷移します。 また、ログエントリをマージする際には以下の制約が設けられます。（原論文）

  1. Leader Candidate においてコミットされているが、保持されていないログエントリについては1つ以上の Follower Candidate が保持している。
  2. いずれの Leader Candidate、Follower Candidate にコミットされず保存もされていないログエントリについては、Raft と同様にそのログエントリを無視してもよい。
  3. コミットされていないログエントリを保存している Follower Candidate が存在した場合、Leader Candidate は最も最新のタームの値を持つログエントリを有効なものとして認識する。

マージステージを含んだ Leader Election の流れについては、以下の順序で実行されます。

  1. Follower から Candidate へ遷移して、他の Candidate へ投票するまでの課程は Raft と同じ
  2. Follower Candidate が Leader Candidate に自身のログエントリを送信する
  3. Leader Candidate は、受け取ったこれらのログエントリと自身のログエントリをマージする
  4. Leader Candidate は、マージして補完されたログエントリを Follower Candidate へ送信して状態を同期する
  5. Leader Candidate は、マージされたログエントリを全てコミットしてそれを他の Follower Candidate へ通知する
  6. Leader Candidate と Follower Candidate はそれぞれ Leader と Follower へ遷移する

f:id:NTTCom:20211224125224p:plain

図7. P1 = Leader Candidate、P2, P3 = Follower Candidate としたときのマージステージの例

以上のステップによって、新しい Leader が全てのコミットされたログエントリを保持する状態が作られます。

Correctness of ParallelRaft

ParallelRaft の整合性について紹介するためにまず Raft における整合性を担保するための制約を紹介します。 Raft では、以下が保証されています。（原論文）

  • Election Safety
    • 1つのタームにおいて、Leader は1つしか存在しない
  • Leader Append-Only
    • Leader は自身のログリストに対して追加のみ行う
  • Log Matching
    • 2つのログリストを比較した際、あるログエントリが同じインデックスで同じタームの値をもつ場合にそれまでのログエントリは同一である
  • Leader Completeness
    • Leader はそれまでにコミットされたログエントリを全て保持する
  • State Machine Safety
    • 全ノードはステートマシンに対して同じ順序で同じログエントリを適用する

これらの制約に対して、ParallelRaft では Election Safety、Leader Append-Only、Log Machine については変更されていないためこれら3つの制約は保証されます。 Leader Completeness と State Machine Safety については ParallelRaft による変更に対して以下の理由で制約が保証されます。

  • Leader Completeness
    • ParallelRaft の Leader Election において、ログエントリのマージステップがあるため保証される
  • State Machine Safety
    • Look Behind Buffer によって、競合せずにログエントリはログリストへ適用されるため

さいごに

今回は、クラウドネイティブデータベースを実現する技術の一端を理解するということで ParallelRaft について解説してみました。 ParallelRaft は、あくまでストレージサーバ間の一貫性を実現するプロトコルでありクラウドネイティブサーバを実現する技術は多岐に渡りますのでこれをきっかけに他の技術要素についても知見を深めたいと思いました。 また、Raft については近年の分散システムにおいて広く利用されており今後も独自にカスタマイズされたプロトコルが提案されていくと思いますので、それらについても関心を持って調査していきたいです。

この記事を読まれることによって、分散システムを支えるプロトコルやクラウドネイティブデータベースを支える技術に少しでも関心を持っていただけると幸いです。

明日は、ついに NTT Communions Advent Calender 2021 の最終日です。明日の記事もお楽しみに！

参考文献

  1. Wei Cao, Zhenjun Liu, Peng Wang, et al. PolarFS: An Ultra-low Latency and Failure Resilient Distributed File System for Shared Storage Cloud Database↩

  2. D. Ongaro and J. K. Ousterhout. In Search an Understandable Consensus Algorithm (Extended Version)↩

© NTT Communications Corporation 2014