クラウド基盤本部の新井です。
サイボウズでは、セッション情報など一時的なデータを置くために yrmcds というインメモリキーバリューストア（KVS）を開発し、クラウド基盤にホストして利用してきました。
私たちのチームでは、旧基盤にホストされてきた yrmcds を、Kubernetes をベースとした基盤である Neco に移行しようとしています。 そこで、プラットフォーム（自社基盤）コースのインターン参加者に、Kubernetes 上で KVS の冗長化を実現するアルゴリズムの設計と PoC の実装を行なっていただきました。 本記事は、その成果をメンターがまとめたものです。
同じコースのインターンに参加した柳田さんの取り組みは以下の記事にまとまっているので、ぜひ合わせてご覧ください。
旧基盤における yrmcds の冗長化
旧基盤においては、yrmcds のレプリケーションと Keepalived により冗長化を実現しています。
具体的には、yrmcds のプライマリが VIP を持ち、クライアントからのリクエストを受け付けつつ、データをレプリカに送信します。 プライマリがダウンすると、レプリカが VIP を引き継ぎ、プライマリに昇格します。 しかし、この方法によるフェイルオーバは Kubernetes と非常に相性が悪いです。
Kubernetes のネットワークとの相性
これを Kubernetes 上で動かすためには、Pod の中で Keepalived を起動して VIP を付与することになります。 しかし、Pod の IP アドレスは基本的に Kubernetes のネットワークプラグインが管理しており、Pod の中で任意に IP アドレスを付与することは推奨されていません。
さらに、Keepalived が利用する VRRP は Gratuitous ARP のような L2 ネットワークの仕組みを使って VIP の所有権を通知しますが、Kubernetes ではこのような仕組みが期待通り動作しない場合があります。
ローリングリスタートとの相性
確実に VIP が付与できる*1としても別の問題があります。
VRRP はマスタとして動作するノードがダウンした際にバックアップノードが VIP を引き継ぐ仕組みです。 そのため、KVS のローリングリスタートが実行されると、次々に VIP が移動してプライマリが入れ替わります。 その過程で KVS の状態は考慮されないので、レプリケーションが追いつかなくなって大部分のデータが消失する可能性が高いです。
旧基盤でも全ノードの再起動を行うことはありましたが、旧基盤ではオペレータが手動で再起動のタイミングを調整していたため、このような問題は起こりませんでした。 しかし、Kubernetes 上のワークロードはローリングリスタートされることが一般的であり、オペレータがそのタイミングを細かくコントロールすることは困難です。
そこで、Kubernetes 上で動作するのに適した、KVS の冗長化を実現するアルゴリズムを設計する必要があります。
インターン課題
全体のアーキテクチャは次のようにしました。
ポイントは以下です。
- インメモリ KVS を複数台（図では3台）用意し、プライマリノードからレプリカノードへレプリケーションを行います。
- プライマリノードを選出するために、コントロールプレーンと呼ばれる別のクラスタを用意します。
- コントロールプレーンの中ではただ一つのノードがリーダとなっており、リーダだけがプライマリノードを選ぶ権利を持っています。リーダ以外のノードは何もせず待機しています。
- プライマリノードとリーダノードは別物です。紛らわしいですが区別してください。
コントロールプレーンを KVS とは別に用意した理由は次の通りです。
- KVS に多くの機能を詰め込むとコードベースの把握が難しくなる
- 冗長化にはなるべく Kubernetes の機能を使いたい（全てを自作するのは避けたい）
- KVS が Kubernetes の機能に直接依存してしまうと、KVS を Kubernetes 以外で動作させられなくなる
インターンの開始前までにここまで方針が決まっていたので、インターンでは次の3つを設計してもらいました。
- プライマリとレプリカの KVS がデータを同期するためのレプリケーションプロトコル
- KVS のフェイルオーバアルゴリズム
- コントロールプレーンのリーダ選出アルゴリズム
全てを詳細に説明すると長くなるので、全体の概要について簡単に説明しつつ、工夫したところを紹介します。
レプリケーション
KVS のフェイルオーバの前後でデータを引き継ぎたいので、レプリケーションを行います。 一般的なシングルリーダレプリケーションです。
レプリカはプライマリに対して TCP で接続します。 接続が確立すると、プライマリは持っている全データをレプリカに送ります。 その後は、クライアントからデータの更新リクエストがあるたびにレプリカに更新内容を送ります。
また、レプリケーション方式としては非同期レプリケーションを採用しました。 非同期レプリケーションとは、プライマリがクライアントからの書き込みリクエストを処理したあと、レプリカへのデータ同期の完了を待たずにクライアントへ応答を返す方式です。プライマリはまず自身のストレージにデータを書き込み、クライアントに応答を返したあと、バックグラウンドでレプリカに更新内容を送信します。
非同期レプリケーションを採用した理由は次の通りです。
- プライマリへの読み書きがレプリカの遅延に巻き込まれるのを防ぎたい
- KVS は一時データの高速な読み書きのために使われている
- フェイルオーバの前後で少数のデータが消えることは許容される
- 永続化したいデータには別のストレージが使われている
KVS のフェイルオーバ
KVS のフェイルオーバとは、プライマリがダウンしたり停止したりしたときに、レプリカの中から1台選んでプライマリに昇格させることを指します。
フェイルオーバを実現するには、まずプライマリの停止を検出し、次にレプリカから新しいプライマリを選びます。そして、レプリカにレプリケーションのやり直しを指示し、最後にクライアントからの新規の接続を新しいプライマリに向ける必要があります。
これを実現するため、コントロールプレーンは現在のプライマリの情報を ConfigMap に永続化しておきます。 そして、定期的に現在のプライマリを死活監視します。 プライマリのダウンを検出すると、レプリカに対してヘルスチェックを行い、正常なレプリカをプライマリに昇格させます。 この際、コントロールプレーンは全ての KVS に新しいプライマリの情報を送ります。 新しくレプリカとなった KVS は新プライマリに接続してレプリケーションをやり直します。 そして、コントロールプレーンは旧プライマリの Pod から特定のラベルを削除し、新プライマリの Pod にそのラベルを付与します。 あらかじめそのラベルをラベルセレクタとして持っている Service リソースを適用しておくことで、クライアントにプライマリの Pod を公開できます。
工夫1：なるべく多くのデータを持ったレプリカをプライマリに昇格させたい
プライマリがダウンしたとき、全てのレプリカが同じデータを持っているとは限りません。 特に、あるレプリカが起動直後で、初期レプリケーション中にプライマリがダウンした場合、そのレプリカにはほとんどデータがない可能性が高いです。
そこで、KVS がヘルスチェックに応答する際に Operation ID を送ります。 これは、クライアントからのリクエスト回数に応じて単調増加する ID です。 これにより、コントロールプレーンは各レプリカがどれだけ多くのデータを持っているかを知ることができます。
さらに、プライマリは History ID と呼ばれる ID を、レプリケーションを通じてレプリカに伝搬させます。 フェイルオーバの際は、以前のプライマリと同じ History ID を持つレプリカの中から、最も大きな Operation ID を持つレプリカを新しいプライマリに選出します（コントロールプレーンは以前のプライマリの History ID を覚えておくため、ConfigMap に永続化します）。 万が一、全てのレプリカが異なる History ID を持っていた場合は、現在の世代のデータを持つレプリカが存在しないとみなし、ランダムなレプリカをプライマリに選出します。
Operation ID と History ID により、同じ世代のデータを持つレプリカの中から、最も多くのデータを持ったレプリカをプライマリにできます。
工夫2：プライマリが短時間で再起動したらフェイルオーバさせたい
プライマリがある時点でヘルスチェックを受けて、次のヘルスチェックまでの間に再起動してしまうケースを考えます。 KVS はインメモリでデータを保持しているので再起動するとデータは全て消えますが、コントロールプレーンから見るとプライマリは一度も死んでいないように見えてしまいます。
そこで、KVS はヘルスチェックのときに、Operation ID と History ID に加えて Instance ID を返すようにします。 Instance ID は、KVS が起動したときにランダムに採番される ID です。 コントロールプレーンは新しいプライマリを選出したときに、そのプライマリの名前と一緒に Instance ID も ConfigMap に永続化しておきます。 コントロールプレーンは定期的にプライマリをヘルスチェックするので、その際にコントロールプレーンが持っている Instance ID と KVS から返ってきた Instance ID を比較します。 両者が一致していなければプライマリが再起動したとみなし、レプリカの中から新たにプライマリを選びます。
コントロールプレーンのリーダ選出
コントロールプレーンのリーダ選出は、KVS のフェイルオーバとは全く異なります。
コントロールプレーンは必要に応じて KVS のフェイルオーバを行いますが、コントロールプレーンのノード（コントロールノードと呼びます）が1台だけだった場合、そのノードがダウンしていると一切 KVS のフェイルオーバができなくなってしまいます。 そこで、複数のコントロールノードを起動した上で、そのうちの1台だけが KVS のフェイルオーバを実行できるよう、リーダ選出を行う必要があります。
Go の client-go/tools/leaderelection パッケージを使ってリーダ選出を行います。
リーダは定期的に Lease オブジェクトを更新し、更新が途切れたらダウンしたとみなして他のコントロールノードが Lease の取得を試みます。
工夫：古いリーダによる操作を防ぎたい
client-go/tools/leaderelection は、Lease を持っているのが1台だけということは保証してくれます。
しかし、Lease を奪われた旧リーダが降格に気づかず、リーダにしか許されない操作を続けてしまう可能性があります。
これがどういうことかというと、例えば、リーダは次のようなプログラムを実行しているとします。
for { // ① 自身がリーダかどうかをチェック // リーダでなければループをやり直す if !IsLeader() { continue } // ② 自身がリーダなら、プライマリをヘルスチェック // プライマリがダウンしていればフェイルオーバ if err := healthCheck(); err != nil { newPrimary := mostSyncedReplica() updateConfigMap(nextPrimary) } }
そして、コントロールノード C1 がリーダとして、C1 が Go の GC によって①と②の間で長時間停止するケースを考えます（この状況は、GC だけでなく kube-apiserver との通信が一時的に途切れるなど、さまざまなケースで起こりえます）。 C1 が長時間停止しているので別の C2 が新しいリーダになります。C2 はプライマリのダウンを検出し、フェイルオーバを始めるかもしれません。 ここで C1 が GC から復帰すると、C1 は自分がリーダかどうかのチェックを終えているので、自分がまだリーダだと思い込んでおり、フェイルオーバを始めてしまいます。
これを防ぐために、リーダが交代したらインクリメントされる整数である LeaderTransitions を、現在のプライマリと HistoryID を永続化している ConfigMap に書き込みます。 リーダがフェイルオーバのタイミングで ConfigMap を更新するとき、まずはその ConfigMap を取得します。 ConfigMap に書かれた LeaderTransitions と、現在の LeaderTransitions を比較し、それが等しくなければ自分がもはやリーダではなくなったことを自覚し、それ以降の処理をスキップします。 等しければ、自分がまだリーダであることがわかるので、ConfigMap を更新できます。
ただし、ConfigMap の取得と更新をアトミックにはできないため、TOCTOU が起きえます。 例えば、リーダが ConfigMap を取得し、LeaderTransitions のチェックを終えたあと、更新する前に停止したとします。 ここで、他のコントロールノードがリーダになり、ConfigMap を更新します。 その後前のリーダが再開してしまうと、そのまま ConfigMap を上書きしてしまいます。
そこで、ConfigMap の resourceVersion を用いた楽観ロック を利用します。 つまり、ConfigMap を更新するときに、前に取得した ConfigMap の resourceVersion を指定します。 これにより、他のコントロールノードがリーダになって ConfigMap を更新すると resourceVersion が変わるので、前のリーダによって ConfigMap が更新されるといった不正な更新を防げます。
おわりに
プラットフォーム（自社基盤）コースのインターンでは、Kubernetes 上でインメモリ KVS をフェイルオーバさせるためのアルゴリズムを設計していただきました。 そして、インターン中にこのアルゴリズムの PoC を Go 言語で実装し、ローカル環境で動作確認するところまで進めていただきました。 これにより、プライマリの KVS がダウンしたり、プライマリの KVS が短時間で再起動したときに、コントロールプレーンがそれを正しく検出して新しいプライマリを選出することが確認できました。
今回のインターン課題は、分散システムと Kubernetes の両方の知識を必要とする非常に難易度の高い課題でした。 そのような課題に果敢に取り組み、アルゴリズムを設計した上で PoC の動作確認まで行っていただき、とても助かりました。 ありがとうございました。
現在はメンターがこの取り組みを引き継ぎ、どのような状況であっても期待通りフェイルオーバすることを TLA+ によって検証しています。 今後は、このインターンの成果を活かし、インメモリ KVS の Neco 移行を進めていく予定です。
私たちのチームでは引き続き堅牢なクラウド基盤の開発に取り組んでいきます。 興味があればぜひ以下の採用情報もご覧ください。
また、昨年のインターンの様子や取り組んだ課題については以下からご覧頂けます。ご興味あればぜひご覧ください。
nginxのproxy_cache_lockと謎の500ms - Cybozu Inside Out | サイボウズエンジニアのブログ Cloudflare の新しいロードバランサ Pingora を試してみる - Cybozu Inside Out | サイボウズエンジニアのブログ
