k8sを運用するなら絶対抑えておきたい、可用性とScalabilityを担保するための大事な観点
概要
先日、Kubernetes Novice Tokyoというイベントで「k8sのAvailabilityとScalabilityを担保するための大事な観点」というタイトルで登壇させていただきました。 運用する上で気にするべき、可用性とスケーラビリティに関する基本的な内容を、 今後のプロジェクトで振り返って参照できるよう体系的にまとめて資料にしています。
内容
スライドはこちら。
まとめ
今後もk8sを本番で運用する上で得られた知見を積極的に発信していく予定です。
Kubernetesの負荷試験で絶対に担保したい13のチェックリスト
概要
ここ最近、Kubernetesクラスタを本番運用するにあたって負荷試験を行ってきました。
Kubernetesクラスタに乗せるアプリケーションの負荷試験は、通常の負荷試験でよく用いられる観点に加えて、クラスタ特有の観点も確認していく必要があります。
適切にクラスタやPodが設定されていない場合、意図しないダウンタイムが発生したり、想定する性能を出すことができません。
そこで私が設計した観点を、汎用的に様々なPJでも応用できるよう整理しました。 一定の負荷、スパイク的な負荷をかけつつ、主に下記の観点を重点的に記載します。
- Podの性能
- Podのスケーラビリティ
- クラスタのスケーラビリティ
- システムとしての可用性
本記事ではこれらの観点のチェックリスト的に使えるものとしてまとめてみます。
確認観点
攻撃ツール
- 1: ボトルネックになりえないこと
Podレベル
- 2: 想定レイテンシでレスポンスを返せること
- 3: 想定スループットを満たせること
- 4: 突然のスパイクに対応できること
- 5: ノードレベルの障害、ダウンを想定した設定になっていること
- 6: 配置が想定どおりに行われていること
- 7: 新バージョンリリースがダウンタイム無しで可能なこと
- 8: 長時間運転で問題が起こり得ないこと
クラスタレベル
- 9: Podの集約度が適切であること
- 10: 配置するPodの特性に合わせたノードになっていること
- 11: 突然のスパイクに対応できること
- 12: クラスタの自動アップグレードの設定が適切であること
- 13: Preemptibleノードの運用が可能であるか
攻撃ツールの観点
1: 攻撃ツールがボトルネックになりえないこと
攻撃ツール(locust, JMeter, Gatlingなど)を使って、担保したいRPSの負荷を攻撃対象に対してかけることができるか
解説
意外と失念しがちですが、攻撃ツール自体が想定する負荷をかけられるとは限りません。
たとえば一つのマシンで大きな負荷をかけようとすればファイルディスクリプタやポート、CPUのコアなどが容易に枯渇します。
大きなRPSを扱う場合は、JMeterやlocustなど柔軟にスケールして、分散して負荷をかけることのできる環境を用意しましょう。
検証方法
私のPJではlocustのk8sクラスタを立て、同じクラスタ内にNginxのPodを立て、静的ページに対してリクエストさせてどのくらいのスループットが出るかを検証しました。
要件的には6000RPSほど担保すれば良いシステムだったので、workerの数やユーザの数を調整して余裕をもって8000RPSくらいまでは出せることを確認しました。
Podの観点
2: 想定レイテンシでレスポンスを返せること
Pod単体で想定するレイテンシでレスポンスを返すことができるか
解説
HPAを無効にしてPod単体の性能が要件を満たすかをまず確認します。
想定レイテンシを超過してしまう場合、Podのresource requestとlimitを積んでいきましょう。
また、もしアプリケーションに問題があってレイテンシが超過する場合はアプリケーションのチューニングが必要です。
3: 想定スループットを満たせること
Podレベルで見たときに想定するスループットを出すことができるか
解説
HPAを無効にしてPodを手動でスケールアウトしていき、どこまでスループットを伸ばせるかを確認します。
スケールアウトしてもスループットが伸びない場合、どこかにボトルネックが出ている可能性が高いです。
その場合まず私は下記を確認します。
各PodのCPU使用率
- 特定のPodだけCPU使用率が偏ってる場合はルーティングポリシーの再確認
各Podのレイテンシ
- 一つ前の「想定レイテンシでレスポンスを返せること」に戻って確認
攻撃側のCPU使用率
- 攻撃ツールのスケールアップ、スケールアウト
4: 突然のスパイクに対応できること
突然急激に負荷が高まったときに対応することができるか
解説
HPAを設定しておけばオートスケーリングしてくれますが、ポリシーを適切に設定する必要があります。
HPAは一定期間でPodの数をアルゴリズムに応じて算出し、定期的に調整することで実現されています。
よって、スケールする条件がギリギリに設定されていたりすると突然負荷が高まっても急にスケールできずに最悪ダウンタイムを挟んでしまったりします。
また、k8sの1.18からはスパイクで急激にPodが増えたり減ったりしすぎないように、behaviorという設定項目も追加されています。
私の場合はlocustで急激な負荷を再現し、下記の観点をチェックしました。
- 監視するメトリクスは適切か？
- 監視するメトリクスのしきい値は適切か？
- Podの増減制御が必要そうか？
5: ノードレベルの障害、ダウンを想定した設定になっていること
ノードが柔軟にダウンしてもServiceに紐づくPodレベルで正常にレスポンスを返し続けることができるか
解説
k8sは、クラスタのオートアップグレードなどでノードが柔軟にダウンしたり、 クラスタのオートスケールでノードがスケールインするので、かなりの頻度でPodが削除されて再作成されることを考慮する必要があります。
そこで注意することとして２つの観点があります。
１つ目はPodのライフサイクルです。
Podが削除されるとき、まずServiceからルーティングされないようにすることと、コンテナへのSIGTERMが同時に発生するため、ルーティングが止まる前にコンテナが終了しないようにする必要があります。
具体的にはlifecycle hookを使い、preStopでsleepしてルーティングが止まるまで待ちましょう。 Kubernetes: 詳解 Pods の終了
lifecycle:
preStop:
exec:
command: ["/bin/sh", "-c", "sleep 30"]
また、NEGなどを活用してContainer Nativeなロードバランシングを行っている場合、下記のような配慮も必要です。
【Kubernetes】GKEのContainer Native LoadbalancingのPodのTerminationの注意点
2つ目はPod Distruption Budgetです。
これを適切に設定しておくことで、ノードのアップデートなどでPodが排出される際に一気に排出されないよう制御することができます。 後述のノードのSurge Updateと合わせて確認するといいでしょう。
apiVersion: policy/v1beta1
kind: PodDisruptionBudget
metadata:
name: sample-service
spec:
maxUnavailable: "25%"
selector:
matchLabels:
app: sample-service
namespace: default
project: default
6: Podの配置が想定どおりに行われていること
Podが想定するノードに配置されているか、想定どおりに分散されているか
解説
Podの配置は何も考えないと空いているリソースからkube-schedulerが任意に選択してしまうため、下記のような観点の考慮が不可欠です。
特定のゾーン、ノードに集中して置かれてしまっている場合、いくらPodを冗長化したとしても、ノードのダウンや、ゾーン障害で一斉にサービスが止まる
Preemptibleノードなどを使っている場合は一斉に複数ノードが落ちることがある
- (通常ノードとPreemptibleノードは併用するのが定石になっています)
Container Native Loadbalancingを使用する場合、LBはPodに平等にルーティングするわけではなく、NEGに対して均等にルーティングしようとするため、NEG(つまりはゾーン)でPod数の偏りがあると安定性やスケーラビリティ、スループットに悪影響を与える
ディスクIO処理が多いPodなどはディスクタイプがssdのノードの配置するなど、Podの特性に応じたノード選択が必要かどうか
Podは、下記を活用することで配置制御を行うことができるので、これらを駆使して配置制御を行いましょう。
- TaintとToleration
- Pod Affinity
- Node Selector
- Node Affinity
- Topology Spread Constraints
7: 新バージョンリリースがダウンタイム無しで可能なこと
PodのDeploy戦略が正しく機能しているか
解説
これはチームのデプロイ運用方針でも変わりますが、一定の負荷をかけつつ、ダウンタイム無しでPodのバージョンを切り替えられるか検証しておくと良いと思います。
8: 長時間運転で問題が起こり得ないこと
長時間運用することによって顕在化する問題を含んでいないか
解説
アプリケーションの実装がイケてない場合、メモリリークや、ファイルディスクリプタの枯渇などがよく発生します。
1日以上負荷をかけ続けたときに消費が増加し続けるようなリソースがないか、ノードのスケールイン、スケールアウト、GKEならメンテナンスウィンドウの時間でも問題なく稼働し続けられているかは検証しておくと良いでしょう。
クラスタ観点
9: Podの集約度が適切であること
Podが効率的かつ安全にノードのリソースを活用できているか
解説
Podは、PodのRequestされたリソースと、ノード内の割当可能なリソースを加味してスケジューリングされます。
つまりRequestが適切に設定されていないとリソースが全然余っているのにどんどんノードが増えてしまったり、逆にスケールしてほしいのに全然スケールしてくれない、といったことが起こりえます。
GCPなどのダッシュボードや、kubectl topコマンドを用いてノードのリソースを有効に活用できているかをチェックしておきましょう。
10: 配置するPodの特性に合わせたノードになっていること
IOアクセスが頻繁なPodなど、特性に応じたノードが選択されているか
解説
特定のPodはSSDを搭載したNodeに配置されてほしいなど、Podに応じた要件がある場合、 Node Selector、Node Affinityを利用して適切に配置されているかを確認しましょう。
11: クラスタの自動アップグレードの設定が適切であること
クラスタの自動アップグレード設定が意図した通りになっていること
解説
例えばGKEを利用している場合、メンテナンスウィンドウとしてメンテナンス可能な時間を設定してあげることで、アクセスが少ない時間にアップグレードを行うなどの制御が可能です。 また、一気にノードが再起動しないようサージアップグレードを積極的に活用していきましょう。
12: 突然のスパイクに対応できること
クラスタがPodのスケールに追従し、スパイクに対応することができるか
解説
これは前述の集約度の話と共通していますが、PodのRequestによってどのようにしてノードがスケールするか、という点が決まります。
基本的に、GKEではスケジュールするためのノードが足りなくなって初めてスケールアウトします。 つまり、突然スパイクしてPodがスケールアウトしようとしたものの、配置できるノードが足りないため、まずノードがスケールアウトしてからPodのスケジューリングがされるケースが発生します。 このような場合にも突然のスパイクに耐えうるか、というのは検証しておく必要があります。
運用したいシステムの要件次第ですが、柔軟にスケールしたい場合はPodのHPAの設定をゆるくしたりなど工夫が必要になります。
13: Preemptibleノードの運用が適切であるか
Preemptibleノードへの過度なPodの集中など、意図しないリソースの使われ方をしていないか
解説
基本的に本番クラスタでPreemptibleノードOnlyで運用するのは危険です。 Preemptibleノードを運用する場合は、通常のノードと一緒に運用し、 かつTaintとTolerationを適切に設定して、Preemptibleノードによりすぎないようにしましょう。
まとめ
今回は私が負荷試験によって担保した、
- スケーラビリティ
- 可用性、安定性
- レイテンシとスループット
- リソース利用効率
の観点を整理しました。 もしご意見、感想あればぜひコメントなどいただけると嬉しいです！
【Kubernetes】GKEのContainer Native LoadbalancingのPodのTerminationの注意点
概要
最近のGKEはContainer Nativeなロードバランシングを推奨しています。 これは、Alias IP, NEGという仕組みを使って、GCPのロードバランサーがPodのIPに直接ルーティングすることができます。 しかし、適切にPodを設定していない場合、クラスタのメンテナンスなどでノードからPodがevictされたときにダウンタイムが発生してしまいます。 この記事ではContainer Native LoadBalancerの仕組みと、Podの適切な設定について説明していきます。
Container Nativeなロードバランシングの仕組み
Container Native LoadBalancingに記載してある通り、
引用: Container Native LoadBalancing
GKEのMasterノードにNEG ControllerというCustom Controllerがいて、特定のAnnotationがついたServiceが登録されたときに、GCPにNEGリソースを作成し、Serviceに紐づくPodをNEGにAttachするという仕組みのようです。 また、zonal network endpoint groupという名前の通り、各ゾーンごとにNEGはつくられ、Podは自分が存在するゾーンのNEGに所属する形になります。
Podの退避時に纏る注意点
GKEではクラスタを自動アップグレードしてくれるので、ノードがローリングアップデートされます。するとそのタイミングでスケジュールされていたPodは一旦吐き出されて別のノードに再作成されるため、ライフサイクルに注意しないとダウンタイムが発生してしまいます。
Podが退避されるときのライフサイクル
Podが退避され、一旦NEGから外れてルーティングされなくなる時、下記のようなフローになります。
- PodがTerminating状態へ
- 下記が同時に走る
- ServiceのEndpointから退避されたPodが外れる
- PodのpreStop + SIGTERM処理が走る
- ServiceからPodが外れたことを検知してNEG ControllerがNEGからPodを外す
- GCLBが、退避されたPodにルーティングしなくなる
つまり、ここで意識しないといけないポイントは2点です。
- NEGから外れる前にPodが停止しないようにする
- NEGから外れても処理中のリクエストだけは処理完了させる
具体的な対応
1に関しては、PodにpreStopを適切に実装しましょう。 基本的なServiceによるルーティングのときと一緒ですね。
lifecycle:
preStop:
exec:
command: ["/bin/sh", "-c", "sleep 20"]
2に関しては、GCLBのBackendの設定にコネクションドレインを設定しておきましょう。
Ingressを使用している場合は、CRDで設定することもできます。 BackendConfig パラメータによる Ingress 機能の構成
そして1のsleepの時間はコネクションドレインの時間より長く設定しておく必要があります。
確認方法
locustやApache Benchなどを使って一定負荷をかけつつ、drainコマンドを使ってノードからPodを退避させてもダウンタイム無しで安全に移動ができてることがわかるかと思います。
サンプル
kubectl drain gke-service-1-service-1-nodes-320d8165-7p7p --ignore-daemonsets --delete-local-data
まとめ
Container Load Balancingはとても強力な仕組みですが、 基本的なServiceのルーティング、LBの設定の考え方を踏襲し、忠実に設定してあげる必要があります。
【Kubernetes】マルチクラスタの最適なヘルスチェックとFailOverについての考察
概要
ここ最近関わっているプロジェクトで、 クラスタを安全にBlue/Greenで更新するためにマルチクラスタ構成にして冗長化する案件を推進していました。 クラスタの安全な更新とクラスタのHealth Check、Fail Overは切っても切れない関係にあります。 そこで得られた、どのような目的で、どのような構成でヘルスチェックするべきか、という1意見を記述してみます。
想定の構成
Istioが入っており、LBはまずIstio Ingress Gatewayにルーティングし、Ingress Gatewayでクラスタ内の各サービスにルーティング
- (これによってGCLBからのトラフィックに対してもIstioのproxyルールを適用させる)
なぜクラスタを冗長化するのか？
クラスタのアップデート、Istioのバージョンアップデート時にダウンタイム無しで安全に更新するために冗長化しています。 InPlaceでUpdateするのではなく、 一度レプリカクラスタをLBから切り離して更新し、もう一度LBに紐づけ、 しばらく様子を見て問題なさそうならメインのクラスタも更新する、という方針をとっています。 またシステムのユーザへの影響を最小にするためにも、クラスタに問題があったときにまだ更新していないクラスタにちゃんとFail Overさせたいので、 ヘルスチェックの定義がとても重要になってきます。
ヘルスチェックを定義する上での課題
本来クラスタ自体の更新といえども、どのサービスにどんな影響を与えるかは各サービス依存です。 例えば、クラスタの中にはバージョン依存のリソースを使っているサービスもあり、アップデートすると一部壊れてしまうかもしれません。
よって、
といったような方針で安全を担保することが考えられます。
しかし1は現状構成が複雑になりがちであり、 2に関していえば特定のサービスだけの障害がクラスタ全体に波及してしまうため論外です。
(たとえばあるサービスに障害が出たときに、クラスタ全体でFail Overされてしまい、仮にFail Over先もヘルスチェックに通っていなかったときにLBからみてルーティング先がなくなる)
とはいえ、クラスタ更新起因でサービスに障害が発生したときに検知してFail Overする必要あります...
ではどうすればいいでしょうか？
採用した方針
ニーズに応じてヘルスチェックの内容を変えることにしました。
本来サービスの可用性は、CanaryやBlue/Greeなどを駆使してサービスのレイヤーで担保するべきであり、サービスすべての状態を検知する必要があるのはクラスタの更新中の間だけです。
よって、
ヘルスチェック用のサービスを実装
- 全サービスのヘルスチェックを行い、すべて健康ならOK、そうじゃないならNGを返すエンドポイントを提供 ※1
- 何もせず200を返すエンドポイントを提供
クラスタ更新中はGCLBのヘルスチェックは、Istio IngressGatewayを通して1のエンドポイントを見に行く
- 更新が落ち着いたらFeature Toggleなどで、GCLBが見るヘルスチェックエンドポイントを2に切り替える ※2
という方針を採用しました。
これにより、クラスタ更新中はかなりシビアに全サービスをチェックし、 それ以外のときは、Istioの疎通だけ死んでいないことだけ担保して、サービスの可用性担保はサービスのレイヤに任せる、 といった方針を実現しています。
補足
- ※1 実施自体は裏で非同期で行い、エンドポイントに問い合わせが来たら最新のスナップショットから結果を返す
- ※2 Istio IngressGatewayを通すことでクラスタ全体でIstio起因で疎通が死んでいないことを担保する
まとめ
今回、普段はクラスタはIstioの疎通まで担保できてたら健康とし、サービスごとの可用性はサービスに任せるという思想で、 見るべきヘルスチェックエンドポイントを切り替えるという方針を取りました。 アーキテクチャの良し悪しは運用してはじめて明らかになるので、しばらく運用して所感を別の機会に振り返りたいと思います。
Istioはいかにしてサービス間通信のセキュリティを担保しているのか？
この記事について
この記事では、Istioがどのような考え方でサービス間通信のセキュリティを担保し、 どのように担保しているかを概観レベルで整理する。
サービス間通信で担保したいものと従来のセキュリティモデル
サービス間通信として担保したいものとして、 通信するアクセス元を制御し、盗聴やなりすまし、改ざんといった攻撃から守ることが挙げられる。 つまり、
- man in the middle攻撃への防御
- アクセス制御
がセキュリティ要件として挙げられる。 従来のセキュリティモデルとしては、 プライベートネットワークを構築し、IPベースでアクセス元を制限することでこれらを担保してきた。 (AWSのPrivate VPCとSGがわかりやすい)
Istioではどういうアプローチをとったのか？
昨今のコンテナベースで構築されるシステムでは、IPアドレスは高頻度で動的に変更されるためこのアプローチだと破綻する。 そこでIsitoは各ワークロードに対してIDを定義し、IDベースでアクセス制御を行うことととした。 具体的にはどういうアプローチなのか？
コアコンセプト
ワークロードに割り振られたIDをベースとしてTLS通信することで認証と暗号化通信をし、 認証されたIDに対する認可制御を行うことでアクセス制御を実現している。 そのために下記の仕組みを実装している。
- ワークロードに一意のIDを割り振る
- IDを認証するための証明書の発行、配布、ローテーション
これらは、SPIFFE(Secure Production Identity Framework For Everyone)と呼ばれる標準仕様で定義されており、IstioはCitadelコンポーネントがこれを踏襲した実装にあたる。 具体的なSPIFEEの仕様、フローはSPIFFEとその実装であるSPIREについてでわかりやすく言及されている。
ポイント
つまり、ワークロードのためのID、証明書を発行し、登録しておくための認証局としての役割を担ったisdiod(Citadel)が存在し、各ノードに存在するistio-agentが、このCitadelとistio proxyの間のやり取りを仲介し、証明書配布などを行っている。 (istio proxyのSDSはこのagentが担当している) これによって、Podが大量に存在するような大規模クラスタでも、Pod自体はistio agentによって分割統治されているので、istiodに対しての負荷をかなり抑えることができる。
また、通常想定されるTLSと違い、この証明書の期限は非常に短く設定されていて、頻繁にローテーションされている。 これによって攻撃者は攻撃を継続していくためにはこの証明書をローテーションされるたびに逐一盗み出さなくてはならず、攻撃の難易度を上げている。
まとめ
このようにIstioはワークロードレベルで認証し、それぞれにアクセス制御を設けている。 これによって動いているプラットフォームに左右されず、どのような環境においても安全な通信を実現することができる。
【ArgoCD】最小ではじめるプロジェクトごとのユーザ権限管理
本記事の概要
ArgoCDをクラスタにインストールするとまずadminユーザが作られます。 しかし、adminクラスタは権限が強く(いわゆるsuperuser)、自由にアプリケーションを更新したり削除したりできてしまいます。
マイクロサービスなどによってサービスごとに分割されたチームでは、チームごとに異なる権限を与えることが多いはずで(他チームのリソースへの権限をつけないなど)、adminユーザを共有するわけにはいきません。
とはいえ、個別にユーザを発行して権限を管理していくのも運用負荷がそれなりにかかります。 そこで本記事ではsmall teamのための最小ではじめるユーザの権限を管理を提案してみます。
ArgoCDのユーザと権限管理
ArgoCDでは、バージョン1.5以降からユーザのRBAC機能が実装されています。 これによって、ユーザに対して細かいリソースアクセスの権限設定ができます。
ドキュメントに記載している通り、ArgoCDでは直接ユーザを定義していく方法とSSOにより、GoogleやGitHubのアカウント認証を通してユーザを定義していく2通りの方法を提供しています。 SSOを使えばユーザのグルーピングなど、複雑な機能を扱えたりするのですが、小規模な運用チームでは少々過剰なので、直接ユーザを定義していくLocal usersを作成していく方針でいくことにします。
想定する環境
今回は、クラスタ内にいろんなチームのサービスが混在する環境ということで、
マルチテナントなクラスタを想定します。
当然TeamAの人々はTeamBのサービス群に対して権限を持ちたくないハズです。
提案する構成
ArgoCDのProjectリソースを論理的なサービスの区分けごとに定義し、
このProjectに対してのみ権限を持つユーザを定義します。
Project & Role定義
apiVersion: argoproj.io/v1alpha1
kind: AppProject
metadata:
name: projectA
namespace: argocd
spec:
description: projectA project
sourceRepos:
- '*'
destinations:
- namespace: '*'
server: '*'
clusterResourceWhitelist:
- group: '*'
kind: '*'
roles:
- name: viewer
description: Read-only privileges to projectA
policies:
- p, proj:projectA:viewer, applications, get, projectA/*, allow
- name: editor
description: Edit privileges to projectA applications
policies:
- p, proj:projectA:editor, applications, create, projectA/*, allow
- p, proj:projectA:editor, applications, update, projectA/*, allow
- p, proj:projectA:editor, applications, delete, projectA/*, allow
- p, proj:projectA:editor, applications, sync, projectA/*, allow
- g, proj:projectA:editor, proj:projectA:viewer
- ここでは参照用ロールと編集用ロールを定義しています。
- pがpolicy、gがおそらくgrantです。pでどのロール、ユーザに対して、どのような操作を拒否/許可するかというルールを定義し、gで実際にロール、ユーザに対してロールをアサインできます。(ロールに対してロールをアサインできるので、上記ではeditorにviewerのポリシーも付与しています)
Account
apiVersion: v1 kind: ConfigMap metadata: name: argocd-cm data: accounts.projectA-viewer: login,apiKey accounts.projectA-editor: login
Roleのアサイン
apiVersion: v1
kind: ConfigMap
metadata:
name: argocd-rbac-cm
data:
policy.csv: |-
g, projectA-viewer, proj:projectA:viewer
g, projectA-editor, proj:projectA:editor
実際にロールをアサインするにはargocd-rbac-cmに記載します。 projectファイルに記載しても動作しますが、こちらに集約したほうが一見してユーザと権限の割当がわかるのでおすすめです。
ユーザのパスワード更新
仕上げに作成したユーザがログインできるようにパスワードを更新しておきます。
argocd account update-password \ --account <name> \ --current-password <current-admin> \ --new-password <new-user-password>
また、匿名ユーザや、デフォルトのロールアサインを無効にしておくとより安全だと思います。
結果
- 管理画面にログインしてみると、read権限がないほかのプロジェクトのサービスは見えないようになっています
- また、viewerでsyncしようとした結果
分散システムにおけるScalableな名前付けアルゴリズム「Chord Protocol」を実装してみた
概要
分散システムを学術的に学びたくて、 Chord Protocolというアルゴリズムが面白かったので実際に論文を読んで実装してみました。 この記事では、分散システムにおける名前付けの概念と、Chord Protocolの紹介、簡単な検証について言及していこうと思います。
 |
|---|
| 実際に作ったサーバ |
分散システムにおける名前付けとは？
分散システムの分野には「名前」、「名前付け」、「アドレス」と呼ばれる概念があります。 それぞれどのような意味を持っているのでしょうか？
名前付けと名前
分散システムはネットワークを通じてそれぞれのサーバ、プロセスが協調して動作しています。 この中で、各サーバ、プロセスはやり取りをする相手の「名前」を知らなければやり取りを行うことができません。 この名前の解決を行うことを「名前付け」と呼んでいます。 そして、あるリソース（特定のプロセス、サーバなど）を一意に特定するための文字列を「名前」呼んでいます。
アドレス
名前が分かっていても実際にはそれだけではやり取りできず、実際には「アドレス」と呼ばれるリソースの住所に対してアクセスすることでやり取りが成立します。 つまり、リソースに対する実質的なアクセスポイントをアドレスと呼んでいます。 名前との違いは、名前は永続的にリソースを一意に特定するもの、 アドレスはアクセスするために必要な実際のリソースの住所、つまり位置情報を持っているということです。 名前は永続的に同じリソースを指し続けるのに対し、アドレスはそのときリソースが存在する位置によって変化します。
具体例
ドメイン名(example.com)が「名前」、example.comに紐づくAレコードのIPが「アドレス」に当たります。 ドメイン名はずっと変わりませんが、IPアドレスはサーバを移管したりすることで変化することがありえます。 永久に同じリソースへのポインタになるのでドメインは「名前」として成立するわけです。
Naming Serverとは？
名前からアドレスを解決したり、特定のリソースに名前をつけてくれるサービスのことをNaming Serviceと呼びます。 一番わかり易い例としては、DNSが挙げられます。 DNSは、ドメインという名前からIPというアドレスを解決し、またIPに対してドメイン名をつける名前付けを行うことで成立しています。
代表的なアルゴリズム ~Consistent Hash~
名前付け、名前解決のためのアルゴリズムとしてメジャーなものにConsistent Hashがあります。 Consistent Hashは、 サーバの集合(以降各要素をノードと呼ぶ)に対してハッシュ関数で一意のID(たいていはホスト名などのハッシュ)を振り、 各ノードをID順に円状に並べ、 あるIDがどのノードに配置されるべきかを決定するアルゴリズムです。 与えられたID以上であり、値が一番近いノードに解決され、 円状になっているので、 仮にそのノードがいなくなったとしても次のノードに回されるといったように、ノード障害に強いアルゴリズムになっています。
詳しくは、こちらがわかりやすいです。 コンシステントハッシュ法
ハッシュによって名前付けを行い、 ハッシュによるIDから対応するサーバを解決して名前解決を行います。
(引用: https://vitalflux.com/wtf-consistent-hashing-databases/)
Consistent Hashの拡張、Chord Protocol
前述のConsistent Hashは完璧ではなく、欠点があります。 それは、ノードの離脱、ノードの参画がいつ起こったとしても、 ただしい結果を返し続けるためには一つのノードは、参加している他のすべてのノードの状態を把握している必要があることです。 (そうでないとノードが増えたり減ったりした時点で正しく結果を返すことができなくなる) これは大規模な分散システムになればなるほど、大きな課題になりえます。 大規模なノードの集合では各ノードは他のノードの情報を保持するために大規模なリソースを要求し、また、ノードの参加、離脱時の情報更新などの計算コストも高くつくことになります。 これを解決するべく生まれたのがChord Protocolになります。
基本的なアルゴリズムは下記の資料がとてもわかり易くまとめられています。
Chord Protocolは何が優れているのか？
基本的なことは上の資料がとてもわかり易いので、ここではかいつまんで何が優れているポイントなのかを説明しておきます。 乱暴にいってしまえば、
- 経路表による高速な検索
- ノード参画、離脱時に各ノードが独立して経路表を更新する仕組み
- 経路表が最新化されていない場合のためのFallback手段としてのSuccessorList
が主なポイントになります。 これらのポイントにより、耐障害性を担保しつつスケーラビリティを向上させることに成功しています。 順に追っていきましょう。
経路表による高速な検索
各ノードは、全てのノードの状態を維持する代わりに、一定サイズの経路表をメンテナンスします。 例えば、32ビット長のハッシュをIDとする場合、32個の行数を持つ経路表を持ち、 この表を元にして、他ノードにルーティングして検索します。 計算量はO(logN)になり(Nはノード数)、これによって大幅にスケーラビリティを担保できるようになります。
ノード参画、離脱時に各ノードが独立して経路表を更新する仕組み
Chord Protocolでは、ノードの参画、離脱時に各ノードがそれぞれ安定化させるためのルールを規定しています。 このルールに従った非同期プロセス、ないしスレッドが一定間隔で動作していて、経路表のメンテナンスを行います。 このメンテナンスは、ノードの離脱、参画に対して、メッセージ数がO(log2N)程度で、そこそこ高速に実行されます。
経路表が最新化されていない場合のためのFallback手段としてのSuccessorList
ノードが参加した直後などは当然経路表は最新化されていません。 よって一時的に正しい結果を返せない可能性もあります。 そこで、この資料のスライド131ページあたりに記載されているように、 Successor Listというリストも保持しておき、経路表による検索に失敗した場合はこのリストを使ってFallbackすることができます。
実際に実装してみた
ここまでがNaming Service及び、Chord Protocolの説明でした。 今回は、これをもとに実際にNaming ServiceをGoで実装してみました。 Goで書いたChordの参照実装なので名前はgordです。(安直)
https://github.com/taisho6339/gord
gordの概要
これはどういう実装かというと、 GordがChord Protocolのノード郡を管理するためのプロセスとして常駐し、 別途ストレージを管理するソフトウェアがgRPCでGordに対してアクセスし、 特定のキーがどのノードに存在するかを検索したり、 自分たちが管理するべきキーを判別したりする、といった機能を提供します。 k8sであればサイドカーとして各Podにくっついているイメージになります。 この構成は実際に論文でもサンプルとして提案されている構成になります。
 |
|---|
| 論文で提案されている構成 |
| |
|---|
| 実際に落とし込んだ構成 |
実装に対する検証
実際に実装に落とし込んだところで、ちゃんと実装できているのかを検証したいと思います。 機能的な観点は、単体テストにて実装しているので今回はパフォーマンス、耐障害性について検証してみます。 ただし、ローカルマシンでの検証につき、プロセッサ数に限度があるため、 お遊び程度の検証しかできないのはあしからず...
パフォーマンスに関する検証
探索のパフォーマンスを測定してみます。
ノード数を1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024と増やしていったときに特定キーの検索にかかる時間を計算してみましょう。
[ベンチマークテストの実装は雑ですがこの辺です。] (https://github.com/taisho6339/gord/blob/master/chord/bench_search_test.go)
すでにStabilizationを完了したノードを指定数用意し、検索のパフォーマンスの違いを見ていきます。
実験にした私のマシンは下記のスペックになります。
OS: MacOS Catalina 10.15.5 プロセッサ: 2.4 GHz 8コア/16スレッド Intel Core i9 メモリ: 64 GB 2667 MHz DDR4
結果はこんな感じになりました。
| ノード数 | 検索にかかった時間 |
|---|---|
| 1 | 20.1 ns/op |
| 2 | 4440 ns/op |
| 4 | 4450 ns/op |
| 8 | 4644 ns/op |
| 16 | 4644 ns/op |
| 32 | 6473 ns/op |
| 64 | 19778 ns/op |
| 128 | 25808 ns/op |
| 256 | 35940 ns/op |
| 512 | 35825 ns/op |
| 1024 | 36940 ns/op |
ローカルマシンでの検証なので32ノード以上になってくると、 ノードが実行している大量のゴルーチンを限られたプロセッサで共有せざるを得なくなってくるため、アルゴリズム以外の要因で遅くなっていそうです。 少なくともノード数によって線形に増加している傾向は見られませんでした。
耐障害性に関する検証
docker-compose build && docker-compose up gord1_1 | time="2020-07-22T06:59:08Z" level=info msg="Running Gord server..." gord1_1 | time="2020-07-22T06:59:08Z" level=info msg="Gord is listening on gord1:26041" gord1_1 | time="2020-07-22T06:59:08Z" level=info msg="Running Chord server..." gord1_1 | time="2020-07-22T06:59:08Z" level=info msg="Chord listening on gord1:26040" gord1_1 | time="2020-07-22T06:59:09Z" level=info msg="Host[gord1] updated its successor." gord2_1 | time="2020-07-22T06:59:09Z" level=info msg="Running Gord server..." gord2_1 | time="2020-07-22T06:59:09Z" level=info msg="Gord is listening on gord2:26041" gord3_1 | time="2020-07-22T06:59:09Z" level=info msg="Running Gord server..." gord3_1 | time="2020-07-22T06:59:09Z" level=info msg="Gord is listening on gord3:26041" gord2_1 | time="2020-07-22T06:59:09Z" level=info msg="Running Chord server..." gord2_1 | time="2020-07-22T06:59:09Z" level=info msg="Chord listening on gord2:26040" gord3_1 | time="2020-07-22T06:59:09Z" level=info msg="Running Chord server..." gord3_1 | time="2020-07-22T06:59:09Z" level=info msg="Chord listening on gord3:26040" gord2_1 | time="2020-07-22T06:59:09Z" level=info msg="Host[gord2] updated its successor."
すぐにStabilizerがノード間連携をし、経路表を更新することでどのノードも一貫した結果を返しています。
grpcurl -plaintext -d '{"key": "gord1"}' localhost:26041 server.ExternalService/FindHostForKey \
&& grpcurl -plaintext -d '{"key": "gord1"}' localhost:36041 server.ExternalService/FindHostForKey \
&& grpcurl -plaintext -d '{"key": "gord1"}' localhost:46041 server.ExternalService/FindHostForKey
{
"host": "gord1"
}
{
"host": "gord1"
}
{
"host": "gord1"
}
つぎに試しに1ノード退場させてみます。
docker stop 1a3bf85b693b
gord3_1 | time="2020-07-22T07:04:43Z" level=error msg="successor stabilizer failed. err = &errors.errorString{s:\"NodeUnavailable\"}"
gord2_1 | time="2020-07-22T07:04:43Z" level=warning msg="Host:[gord1] is dead."
gord3_1 | time="2020-07-22T07:04:43Z" level=warning msg="Host:[gord1] is dead."
gord_gord1_1 exited with code 0
すぐにノードのダウンを検知し、更新に入っています。
grpcurl -plaintext -d '{"key": "gord1"}' localhost:36041 server.ExternalService/FindHostForKey \ ✘ 1
&& grpcurl -plaintext -d '{"key": "gord1"}' localhost:46041 server.ExternalService/FindHostForKey
{
"host": "gord2"
}
{
"host": "gord2"
}
ノード1がダウンしてもすぐに経路表が更新され、さらにノード1に本来属していた"gord1"というキーが別のノードに移っていることがわかります。
まとめ
実際にChord Protocolを実装することで、 実装としては、未熟な点やバグなど残っていると思いますが、何が優れていて、既存の手法とは何が違うのかを実際に理解することができました。 また付加価値として256ビットにもなる大きな数値をGolangでどう計算するのか、 Golangでの並行処理についても勉強することができました。 こういったことが直接お仕事の役に立つケースは多くはないかもしれませんが、実装力のレベルを一段引き上げてくれる良い機会になり、楽しむことができました。 今度はもっと身近なOSSなどで利用されているアルゴリズムなども実装してみたいと思います。
