Kubernetes ControllerをScale-Outする方法

この記事は [Kubernetes Advent Calendar 2022](https://qiita.com/advent-calendar/2022/kubernetes) の9日目の記事です。

この記事では、Kubernetes ControllerをScale-Outするアーキテクチャについて考察します。(注: ここで議論されているアーキテクチャは、プロダクションに適用されているものもありますが、まだ検証段階の域を超えていないものもあります。ご注意ください。)

2022/12/22に開催される[Kubernetes Meetup Tokyo #55](https://k8sjp.connpass.com/event/267620/
)にて本記事の内容について、もう少し詳しく実装にも踏み込んで発表([スライド](https://www.slideshare.net/pfi/kubernetes-controllerscaleout-kubernetes-meetup-tokyo-55))しますので、そちらも是非ご参加ください👋 

## (おさらい) 典型的なKubernetes Controllerのアーキテクチャ

まずは典型的なKubernetes Controllerの作りをおさらいしてみます。

### Pod内部のアーキテクチャ

下図は[controller-runtime](https://github.com/kubernetes-sigs/controller-runtime)をつかったControllerのソフトウェアアーキテクチャの概要です。

<iframe src="//www.slideshare.net/slideshow/embed_code/key/fjCXnz3zNzgRzP?startSlide=7" height="300" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe> <div style="margin-bottom:5px"> 

ものすごく大まかに説明すると、Controllerは下記のような動作をします。

- Kubernetes APIをつかってリソースの変更イベントをWatchし内部のeventqueueに貯めて
- eventqueueからeventがフェッチされInfomerに渡されます
- Informerはそのeventを使ってincrementalにin-memory Cacheを更新しつつ
- Controllerが事前に`Watch()`等で登録したEvent Handlerにeventを渡します
- Event Handlerはeventをreconcile要求に変換しreconcile queueに詰めます
- Controllerはreconcile queueからreconcile要求をと知りだし、Reconcilerに渡します。
  - Reconcilerは並列に実行できます
- Reconcilerは実際にreconcile要求を処理します
  - _通常Read系のAPIはin-memory Cacheを通して行います_

### Pod間のアーキテクチャ

通常Kubernetes Controllerは下図のように、Deployment等をつかって複数レプリカをデプロイします。

<iframe src="//www.slideshare.net/slideshow/embed_code/key/fjCXnz3zNzgRzP?startSlide=8" height="300" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe> 

- 複数レプリカはActive/Warm Standbyな感じでデプロイされる
- レプリカPod間でLeader Electionを行い
  - __LeaderのみがReconcile__ を行い、
    - こうする（Single Writerにする)ことで、__リソースの並行更新による衝突が起きないことを保証できるためです__
  - FollowerはStandby(自分がLeaderになったらすぐ動き出せるように)
　
### 典型的なKubernetes ControllerのアーキテクチャはScale-Upしかできない

<iframe src="//www.slideshare.net/slideshow/embed_code/key/fjCXnz3zNzgRzP?startSlide=9" height="300" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe> 
つまり、このアーキテクチャだと、Scale-Upはできるけれども、Scale-Outは出来ないアーキテクチャであると言えます。

### Scale-Upの限界が来るとReconcileが詰まり始める

<iframe src="//www.slideshare.net/slideshow/embed_code/key/fjCXnz3zNzgRzP?startSlide=10" height="300" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe> 

- Pod内部は処理の並行度を上げられますが限界があります[^1]
- 限界が来ると
  - Reconcilerの処理スループットよりもReconcile要求が多くなり、
  - Controller内部のqueueが詰まりはじめ、
  - Reconcile間隔が長くなってReconcileされていないように見えたり、
  - in-memory Cacheの内容もStaleし始めるためReconcile結果もStaleしてしましいます。
- 特に、下記のようなControllerの場合は並行度が上げられても、Reconcile自体の処理時間が長くなりがちで、すぐに詰まってしまうことがあります
　　- Reconcile対象のResourceのManifestサイズが大きくて、Resource数も大量にある
　　- Reconcilerが外部のAPI、Database、大規模なI/O等Latencyの高い処理に依存している

[^1]: 最近は非常に多くのコアを搭載した高性能サーバもあったりするので実際問題あまり問題にならないかもしれませんが。

## ControllerをScale-Outする方法

そこで、やっぱりControllerをScale-Outさせたくなるわけです。

<iframe src="//www.slideshare.net/slideshow/embed_code/key/fjCXnz3zNzgRzP?startSlide=14" height="300" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe> 

もともとLeaderしかReconcileしないのがやりすぎなわけですから、Controller Podを全部活用することを考えます。ただ、同じリソースを複数PodからReconcileしてしまうと、並行更新によるConflictが起きてしまうので、重複の内容になんとかしてReconcile対象のオブジェクトをController Podに割り振ってやると良さそうです。

いわゆる、シャーディングですね。

### Namespace単位でControllerをDeployする

まず最初に思いつく方法が、同じ構成をNamespace単位でDeployする方法です。これなら難しい割り振り方法を考えなくても、自然に重複なく割り振ることができそうです。実際、[Argo Workflow](https://argoproj.github.io/argo-workflows/)のcontrollerはnamespaceに閉じたdeployを[サポートしています](https://argoproj.github.io/argo-workflows/scaling/#one-install-per-namespace)。

<iframe src="//www.slideshare.net/slideshow/embed_code/key/fjCXnz3zNzgRzP?startSlide=16" height="300" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe> 

この方法の良い点としては
- 実装が簡単
- Manifestもほぼそのまま使えそう
- ControllerのServiceAccountの権限がNamespaceに閉じる[^2]

が考えられる一方で、

- Controller Podが大量に必要[^3]
- Namespaceの増減に対応しづらい
- Namespace間の負荷の偏りは防げない
- Cross-NamespaceなReconcileはNG
- Cluster ScopeのResourceもNG

という欠点もあります。
[^2]: Namespace間のIsolationが大切な時は良さそう
[^3]: Kubernetes的にはPodもリソースでnode単位にdeployできるPod数の上限があります

ということで、やはり、汎用性を考えてもリソース単位でシャーディングしたいと思いますよね。

### Resource単位でシャーディングする

既に試みていらっしゃる方がいましたので、ここではそれを紹介します。[@stackitcloud](https://github.com/stackitcloud)のエンジニアで、[gardener/gardener](https://github.com/gardener/gardener)のメンテナでもある、Tim Ebert [@timebertt](https://github.com/timebertt)さんです。彼の今年の修士論文である["Towards Horizontally Scalable Kubernetes Controllers"](https://github.com/timebertt/thesis-controller-sharding/releases/tag/v1.0)です(できたてほやほや！！)。彼の成果は主に下記の3つのGithub Repoに分かれています。
- [timebertt/thesis-controller-sharding](https://github.com/timebertt/thesis-controller-sharding): 修士論文本体
- [timebertt/kubernetes-controller-sharding](https://github.com/timebertt/kubernetes-controller-sharding): Shardingに対応したサンプルController実装
- [timebertt/controller-runtime@v0.12.3-sharding-1](https://github.com/timebertt/controller-runtime@v0.12.3-sharding-1): Sharding対応のcontroller-runtime

#### アーキテクチャ概要
下記の図は `kind: Foo` 向けのControllerをシャーディングするアーキテクチャの概要図です。
[![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/8678/e04805c4-d9f6-67d4-e50c-4cfef93b4803.png)](https://github.com/timebertt/thesis-controller-sharding/blob/master/assets/design-overview.pdf)

- __ShardはLeaseで定義__
  - Shard名 = Lease名 = Controller Pod名 [^5]
- __Sharder (Singleton)__
  - Shard群をwatchして、Resource群をshardに割り振り、Reconcile対象リソース(図中だとFooに `shard:<shard名>` を付与(by [Consistent Hashing](https://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%B3%E3%82%B7%E3%82%B9%E3%83%86%E3%83%B3%E3%83%88%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E6%B3%95))
- __Controller (≒Shard)__
  - `shard:<shard名>` ラベルが付いているリソースのみをReconcile
  - 自身のShardのstatusをLeaseで管理（_実質1podなのでheartbeatによる死活監視_)

[^5]: StatefulSetだとShard名を安定させられますね

思ったより複雑だという感じがするかもしれません。ただオブジェクトをContistent Hashするだけなら、Controller Podを各PodからListできるのだから、そこでやればいいのではないか？と思う方も居ると思います。

実際に[kube-state-metrics](https://github.com/kubernetes/kube-state-metrics)では古くから、Controller Pod内で独立してConsistent Hashingすることで負荷を分散する手法が取られています[^4]。ただ、各Controller Podで独立してConsistent Hashingを計算すると、Controller Podの再起動やScale-Out/Inの際に各Podで計算される割当が一致しなくなり、結果としてリソースが複数のController Podに割当たる可能性が排除できません。kube-state-metricsはwatchしているmetricsをexportするだけですのでこれでもあまり問題にならないのですが、実際のControllerでは不都合があると考えられます。

[^4]: 詳しくは[TechFeed Experts Night (25) / Kubernetesオブジェクトのメトリクスを提供する「kube-state-metrics」で使われているシャーディング手法](https://techfeed.io/entries/637af22d161c11678aedba06)で詳しく解説されているので参照してください。

そこで、このちょっと複雑に見えるアーキテクチャがなぜそうなっているのか？を次の設計ポイントに分けて解説していきます。

- Shardメンバーシップと耐障害性
- オブジェクトの振り分け
- オブジェクトの割当
- 並行Reconcileの防止

#### 設計ポイント1: Shardメンバーシップと耐障害性

<iframe src="//www.slideshare.net/slideshow/embed_code/key/fjCXnz3zNzgRzP?startSlide=21" height="300" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe> 

ここでは、２つの設計判断についてその背景を説明します。

- SharderがSingletonになっている
  - 上で説明したようにConsitent Hashingによるオブジェクトの振り分けはReconcileの並行更新を防ぐためにController Pod群で判断のずれがあっては困ります。そこで、SharderというプロセスをController Pod群でSingletonで保持し、そこでオブジェクトの振り分けを行うこで、認識ズレが発生しないようにしています。Consistent Hashingを行うために必要なのは、resourceのUIDのみですので、オブジェクト数が多くなってもあまり問題にならないと考えられます。
- ShardがLeaseである(Podじゃない)
  - 実質Controller PodがShardなんだから、わざわざLeaseを挟んでいる理由が気になるかもしれません。これは一時故障時のConstent Hashingの安定性が理由です。Shard=Podだと、Rolling UpdateやPodの障害時にShardが増減してしまい、リソース→Shardの割当に移動が生じてしまうのです。Leaseにすることで、短時間のPodの不在にたいしてRobustなリソース割当が実現できるようになっています。

#### 設計ポイント2: オブジェクトの振り分け

これはここではあまり詳しくは説明しません。リソース➔Shardの割当に関して、Shardの増減に対して、割当の変更量を少なくするためにConsistent Hashingを使っています。

#### 設計ポイント3: オブジェクトの割当

<iframe src="//www.slideshare.net/slideshow/embed_code/key/fjCXnz3zNzgRzP?startSlide=24" height="300" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe> 

リソース➔Shardへの振り分けはSharderによってConsistent Hashingで決定されますが、それを各Shardを担当するController Podにどのように知らせるか？です。

ここでは　__リソースに`shard: <shard_id>`というラベルを付与する__ ことで実際の割当を行っています。__ラベルをつかうことで、リソースを担当するshardが高々1つ__という条件を保証でき、重複割当を防ぎ並行更新を防ぐことが出来ます。

__ただし、まだこれだけでは並行Reconcileは完全には防ぎきれないので注意が必要です__。あくまでラベルはSharderによるリソース割当の判断を記録したに過ぎません。実際のReconcile処理は各Controller Podがリソースをpull(watch)してReconcile処理を実行しているので、割当判断をラベルに記録したからと言ってそれがController Podに伝わっているわけではないからです。

具体的には、Shardの増減に伴って、あるリソースが`shard-a`から`shard-b`に移動した場合を考えましょう。この時、リソースの`shard`ラベルの値は`shard-a`から`shard-b`に変更されますが、`shard-a` Podがこの変更を受け取っておらずReconcileを継続していたらどうでしょうか？ さらに、`shard-b`Podが割当を検知してReconcileを始めてしまったらどうなるでしょうか？

つまり、ラベルを使うことでリソース➔Shardの割当は高々1にできるけれど、shard移動時にはより細かなケアが必要であることがわかります。

#### 設計ポイント4: 並行Reconcileの防止

Shardの増減が起きる典型例はController PodのScale-Out/In時です。この時にどのような処理が必要になるかを説明します。


<iframe src="//www.slideshare.net/slideshow/embed_code/key/fjCXnz3zNzgRzP?startSlide=26" height="300" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe> 

- Scale-Out時
  1. `shard-b` が出現し、Sharderは`shard-a`➔`shard-b`に再割当てを行う場合
  1. いきなりラベル値を変更するのではなく、`drain: "true"`ラベルをリソースに付与します
  1. `shard-a`　Podは`drain`ラベルによってSharderが再割り当てをしようとしていることを検知し、
  1. その応答として、`shard`ラベル、`drain`ラベルを削除します(当然この段階で当該ResourceのReconcileを放棄します)
  1. Sharderが、すべてのラベルが消えたことを確認後`shard: shard-b`への割当を行います
- Scale-In時
  1. `shard-a`が居なくなる(つまりLeaseがexpireした場合)、
  1. (この時 `shard-a` も自身がLeaseにheartbeatを送れずexpireしたことを検知しているはずなのでReconcile処理は止まっています)
  1. ので、Sharderは安全にラベル値を付け替えるだけで良いので単純に`shard: shard-b`に書き換えます


## 注意: Kubernetes自体にはScale制限がある

こうして、Controller自体は水平スケールできることがわかったわけですが、Kubernetesの状態はすべてKubernetes APIを経由して行われるのでKubenetes自体のスケーラビリティも考慮しなくてはなりません。

ただ、残念ながら、Kubernetesは無限にスケールするようには出来ていません。Kubernetes公式ドキュメントの[Considerations for large clusters](https://kubernetes.io/docs/setup/best-practices/cluster-large/) には、上限値の明記があります。
- No more than 110 pods per node
- No more than 5000 nodes
- No more than 150000 total pods
- No more than 300000 total containers

また、Kubernetesのストレージである[etcd](https://etcd.io/)自体、すべての書き込みを直列処理するため、更新はScale-Outしないストレージとなっています[^7]。

[^7]: `--etcd-servers-overrides`でgroup/resource単位でetcd更新負荷をOffload/分離可

となると、せっかくController Scale-Outしても意味ないのでは!?😇と思う方もいるかも知れません。

## ControllerをShardingして嬉しい時

Kubernetesクラスタ、特にetcdはScale-Out出来ないわけですが、etcdのScale-Up限界の範囲内で、それ以外のところにボトルネックがある時はShardingが有効な場合があります。[上でも書いたとおり](https://qiita.com/everpeace/private/2214383e7e27a068eccb#scale-up%E3%81%AE%E9%99%90%E7%95%8C%E3%81%8C%E6%9D%A5%E3%82%8B%E3%81%A8reconcile%E3%81%8C%E8%A9%B0%E3%81%BE%E3%82%8A%E5%A7%8B%E3%82%81%E3%82%8B)、

- 外部のAPI, Database, I/O等に依存していて1回のReconcileに時間がかかる場合
  - リソースが多い場合すぐにScale-UpしてもControllerだけが詰まる傾向にあります
  - (1回のReconcileが長い場合には並行数を増やしてもまたすぐ詰まってしまう場合が多いと考えられます)
- Reconcile対象リソースのサイズも量も多い場合
  - リソースサイズが大きいとReconcile時間が伸びる傾向(Ser/DeSer処理が重い)があり、加えてリソース数も多いとControllerだけが詰まる傾向にあります

## まとめ

- Kubernetes Controllerの基本的なアーキテクチャはScale-Upしかできない
- ControllerにShardingを適用したScale-Outなアーキテクチャが提案&検証がされている
  - まだForkedな[timebertt/controller-runtime@v0.12.3-sharding-1](https://github.com/timebertt/controller-runtime@v0.12.3-sharding-1)でのみのサポートなので検証段階ですが今後とても楽しみ
- ただしKubernetes自体のScale Limitには注意が必要
- Reconcile自体に時間がかかるようなControllerの場合は効果ありそう