Zenn
🪗

etcd から始める分散合意システム入門

2023/12/18に公開
#
etcd
K8s
#
raft
#
分散合意
#
paxos
tech

この記事は Kubernetes Advent Calendar 2023 の16日目の記事です。

kubernetes のデータストア

私達が普段 manifest ファイルとして記述している Kubernetes objects [1] は kubectl など[2]を通して kube-apiserver にリクエストを送信し、そのオブジェクトは etcd に保存されます。
Kubernetesクラスターを構成するコンポーネント - kubernetes.io のドキュメントから引用

なぜ etcd なのか

etcd は一貫性と高可用性に優れた分散KVSです。
kubernetes で主に使われるデータストアは etcd ですが、 設定で変更することも可能です。

ところで、 etcd は kubernetes のために開発されたものではありません。 CoreOS チームによって 2013 年に開発が始まり[3]、その後 kubernetes のデータストアとして採用されました。[4]

etcd の initial commit

etcd の特徴

etcd は CoreOS クラスタ設定の共有とサービスディスカバリに使用する目的で開発されました。[5] CoreOS Container Linux では etcdを介して動作する Locksmith によりゼロダウンタイムでの Linux カーネルアップデートを実現しています。[6]
分散システムのためのデータストアとして作られたこともあり、etcd は強い一貫性を持っていることが特徴として挙げられます。
これは内部で採用している Raft Consensus Algorithm によるものです。
他にも、特定のキーまたはキーパスに対する変更を監視するウォッチ機能、単一のリクエストで複数リクエストをアトミックに処理できるトランザクションと linearizability などが特徴として挙げられます。[7]

etcd の 変更監視 - etcd.io のドキュメントから引用

一貫性を保つためのアプローチ

MySQL などの従来のデータストアは ACID トランザクションや source / replica[8] レプリケーション、二相コミットなどのアプローチによってデータの整合性を保っていました。
しかし、これらは単一システム内での整合性を保つために設計されたものであり、大規模クラスタでの整合性(同期遅延)や可用性[9]に問題がありました。
etcd や Apache ZooKeeper はこれらの問題に対処するため分散合意アルゴリズムを採用し、一貫性と可用性、 Self healing や Resilience を担保しました。

分散合意アルゴリズム

1つのサーバーとクライアントが存在する場合、これは問題となりませんが、複数のエージェント(ノード)間で値を共有するとき、その値について合意が必要です。
分散合意システムには可用性が求められるのはもちろんのこと、合意によってノード間のデータを同期することで一貫性を保ちます。

Raft

Raft では以下の3つの Role が存在します。

  • リーダー (Leader)
  • フォロワー (Follower)
  • 候補者 (Candidate)

システム外部からの書き込みクエリはリーダーに対して送信されます。
リーダーはこのクエリをログエントリとして処理します。
クエリを受け取ったリーダーは各フォロワーにエントリ追加を依頼し、これにフォロワーが応答することでデータがコミットされます。

なおこれはハートビートとしての役割も兼ねています。
アニメーションでの解説 → Raft

メンバの再構成と選挙

リーダーはエントリ追加依頼を含め常にハートビートを各フォロワーに送信しています。[10]
フォロワーは常にリーダーからのハートビートを期待しており、タイムアウト期間内にハートビートが送信されなかった場合、選挙が行われます。

タイムアウトが経過するとフォロワーは候補者となり、 他のフォロワーに対し投票リクエストを行います。タイムアウトはフォロワーごとに違っており、150~300ミリ秒のランダムな値がセットされるため基本的には同時に投票リクエストが行われることはありません。

候補者が過半数の票を集めると、そのノードはリーダーへと変わります。これによりリーダーがダウンした場合も速やかにフェイルオーバーが行われ、結果としてフォールトトレランスなシステムになります。

etcd で選挙が行われるケースについては etcd learner design | etcd で解説されています。

これらの Raft の仕組みを利用することで etcd では高可用性と一貫性が保たれています。

分散合意アルゴリズムと KVS

Paxos

Paxos は 1978年に Leslie によって提案されました。[11] Raft と同じく分散システムにおいてデータの一貫性と合意形成を目的としています。

合意形成の Phase

Paxos では以下の3つの Role と4つの Phase が存在します。

  • Role
    • 提案者 (Proposer)
    • 受諾者 (Acceptor)
    • 学習者 (Learner)
  • Phase
    • 提案 (Propose)
    • 約束 (Promise)
    • 受諾 (Accept)
    • 学習 (Learn)

システム外部からの書き込みクエリ発行など[12]をトリガーに Prepare Phase が開始されます。
Proposer は一意の提案番号を作成し、 Acceptor に Prepare を行います。
Acceptor はこれまで受け取った最大の提案番号[13]である提案に対し Promise を返します。
Acceptor が以前に受け入れた Prepare がある場合、その Prepare の情報を Proposer に返送します。ない場合は単に Promise のみを返します。

Proposer が Acceptor から過半数以上の Promise を得た場合に Accept Phase が開始されます。
Proposer は Acceptor に対し最終的な値の提案を行い、 Acceptor はこの値を受諾します。

Learn Phase では Acceptor が受諾した値を Learner に通知し、 Learner はこれを確認します。

これらの Phase を経て Paxos でデータのコミットが行われます。

Paxos のバリエーション

Paxos はいくつかのバリエーションが存在し、それぞれシナリオや要件によって最適化されています。

  1. Basic Paxos
    Propose, Promise, Accept, Learn 4つのフェーズを経て合意を行うもの

  2. Multi Paxos
    Basic Paxos を拡張し、合意を並列で処理できる

  3. Fast Paxos
    提案のラウンド数を減らし合意のプロセスを高速化し、パフォーマンスを重視している

  4. Cheap Paxos
    少ないノード数で利用できる Paxos

  5. Generalized Paxos
    非連続的な決定や複数の提案が同時に進行するシナリオで用いられる

これらのバリエーションによって Paxos は要件に合わせた形で実装できるとされています。

分散合意アルゴリズムの実装

Paxos と Raft の実装数を比較すると 2023年現在 Raft が多く実装されています。
Paxos は分散合意アルゴリズムの理論の基礎として高く評価されていますが、合意形成までのプロセスの複雑さ、バリエーションの多さ、抽象度の高さから理解・実装の難易度が高いと評価されているのではないかと考えます。

しかし Raft もすべてにおいて完璧だとはいえません。

Raft は書き込み・フェイルオーバーロジックを簡素にしたことにより、構造的にリーダーへの依存度が高いといえます。そのためリーダーダウンによる選挙が行われている間は一時的な書き込み制限が発生しており、これはユースケースにおいては可用性の低下を引き起こすことが考えられます。

また、書き込み処理の最適化において Raft よりMulti Paxosのようなバリエーションが高度で高速だとされることがあります。

ただ、 Paxos は複雑なアルゴリズムであるため、ユースケースによってそれらが選択されるものだと考えます。

類似のデータベース

etcd は Kubernetes objects を保存するデータストアとして採用されていますが、これ以外にも類似のデータベースは存在します。

TiKV

TiKV[14] は etcd と同じく CNCF がメンテナンスしている分散データベースです。
内部に Raft を採用し、データのレプリケーションを行っていますが etcd とは異なりトランザクション処理に特化しています。 TiDB というデータベースシステムのストレージレイヤーとして機能しており、 SQL レイヤーの TiDB と対になっています。

https://tikv.org

ZooKeeper

Apache ZooKeeper は Zab という合意アルゴリズムを採用した分散データベースです。 Zap はより一般的なユースケースを想定しています。

etcd より古く、以下のような事項で etcd の設計に影響を与えています。

  • クラスタメンバーシップの動的再構成
  • 高負荷下での安定したR/W
  • イベントのドロップが発生しない信頼性の高いキー監視

https://zookeeper.apache.org/

Redis

Redis はインメモリデータストアであり、etcd より幅広いデータ型と構造をサポートしています。また、パフォーマンスの面でも優秀です。
しかし Redis は分散アルゴリズムを採用しているわけではなく、あくまでインメモリキャッシングのためのデータストアという側面が強いです。

https://redis.io/

おわりに

この記事では、 Kubernetes のデータストアである etcd を起点に分散合意アルゴリズムについて紹介しました。
難解な点も多い分散合意アルゴリズムですが、この記事を通じて少しでも興味を持っていただければ幸いです。

脚注

  1. Objects In Kubernetes | Kubernetes ↩︎

  2. kubectl や kubeadm など The Kubernetes API | Kubernetes ↩︎

  3. What is etcd? ↩︎

  4. 現在は CNCF 傘下のプロジェクトになっています Red Hat contributes etcd, the cornerstone of Kubernetes, to the Cloud Native Computing Foundation ↩︎

  5. docs/etcd/getting-started-with-etcd.md at master · coreos/docs ↩︎

  6. CoreOS Container Linux は現在 Fedora CoreOS となっており、再起動マネージャーには Locksmith ではなく coreos/zincati が採用されています ↩︎

  7. etcd のドキュメントより ↩︎

  8. master / slave ↩︎

  9. MySQL の master 昇格作業はやりたくないですよね。人の手で行う作業には限界があると考えます。 ↩︎

  10. ハートビートにはエントリ追加依頼等の追加の情報が含まれることも、ハートビートのみを送ることもあります
    ↩︎

  11. Lamport, Leslie (July 1978). "Time, Clocks and the Ordering of Events in a Distributed System". https://doi.org/10.1145/359545.359563 ↩︎

  12. 他にはリーダー選出、システム再構成、チェックポイント作成などをトリガーに提案が行われます ↩︎

  13. 条件によっては提案者が複数存在する場合もあります ↩︎

  14. tee-kay-vee と発音するようです ↩︎

Discussion