Fire Engine

消防士→ITエンジニア→研究者

遺伝的アルゴリズムを用いてコンテナの配置を最適化する論文：「Genetic Algorithm for Multi-Objective Optimization of Container Allocation in Cloud Architecture」

データサイエンス 論文

ふとタイトルが目に入ってきて気になって読んでみた。私自身そんなにコンテナ技術を触ってないけど、前から遺伝的アルゴリズムが気になっていた。 ちょいちょい知識が足りずに理解しきれないところ出てきたけど、とりあえず最後まで読んだのでざっくりまとめを書いてみる。

読んだ論文

pdfはダウンロードできなかったけど、ここからOnlineで読めた。

所感

先に論文を読んだ所感を書いておく。

  • コンテナのリソース割り当ての最適化問題を遺伝的アルゴリズム（GA）を使って解くというコンセプトが面白かった。Related Workとして多くの論文が挙げられていた（Table 1およびTable2）ので、この辺りは追っていくと面白そう。

  • GAはパラメータの全検索が不可能と思われるくらい膨大な組み合わせがあって、かつ有効な探索方法が定かでないパターンに有効っぽい。さらに、論文内で用いているNon-dominated Sorting Genetic Algorithm Ⅱ（NSGA-Ⅱ）などの手法は、多目的最適化に有効な手法だから、けっこう応用の幅が広そうだなぁと思った。

  • いかに最適化したいものを目的関数として定式化するかっていうところが大変で重要なところなんだろうけど、それができるならば、目的は複数あっても、目的同士が相関関係にあっても、近似解をヒューリスティックに探索してくれるから、GAという手法は学んでいくといろんな問題に適用できそう。

  • 遺伝的アルゴリズムを始めとした進化的計算という分野に興味が湧いたのでやっていきたい。

概要

クラスター内の物理ノード群に対するコンテナの配置は、システム全体のパフォーマンスや信頼性、スケーラビリティに大きな影響を与えるため、システム設計において重要な要素である。Kubernetesのような既存のコンテナクラスター管理は、コンテナのオートスケールや物理マシンへのコンテナの配置に対して単純な実装しかされておらず、それらは物理的なリソースの使用率や閾値にのみ焦点を当てている。

このようなリソース最適化はNP完全問題であり、メタヒューリスティックなアプローチが有効である。中でも、GAのような進化的アプローチはリソース最適化問題に非常に有効な解法の一つである。本論文では、コンテナのリソース割り当てに対してNon-dominated Sorting Genetic Algorithm Ⅱ（NSGA-Ⅱ）というアルゴリズムで最適化している。NSGA-Ⅱという手法はMulti-Objective（多目的）な最適化に有効であるため、今回のように最適化したい目的関数が複数あって、それぞれの目的関数同士が独立でない場合でも適用可能である。

提案手法を用いて最適化したコンテナ配置は、Kubernetesによるコンテナ管理のアプローチよりも、論文中に定義した目的（後述）において、優位な結果が出ることが実験的に示されている。

遺伝的アルゴリズム（GA）

GAとは何か？という問いに対する答えとして「遺伝的アルゴリズム（Genetic Algorithm）を始めよう！」の7枚目のスライドがわかりやすかった。

生物進化における遺伝と適者生存による自然淘汰の仕組みをソフトウェア的に模すことで複雑な問題に対する最適解を探索する手法

私の印象としては、まじめに解こうとしても解けないくらい解の組み合わせの数が膨大なときに、実用的な時間スケールで近似的な解を探索できる点が大きな特徴だと思った。
また、実際に論文内の最適化で用いているNSGA-Ⅱについてもいくつか解析記事があった。

http://mikilab.doshisha.ac.jp/dia/research/mop_ga/moga/3/3-5-5.html

この辺りはこれから学んで数学的な背景からしっかり押さえていくので、また詳しくブログに書こうと思う。

システムのモデル化

最適化問題として解くためには、当然ながら何が最適化を評価できなければならない。さらに出てきた解（GA的には染色体）の候補同士に優劣をつけるために、定量的に評価できる形、つまり定式化しておく必要がある。

本論文ではコンテナのリソース割り当てに対して、以下の４つの目的を置いて定式化している。式中の変数についてはTable3を、定式化の詳細については「3.1 Optimization Objectives」を参照。

これらの定式化したものは、個体（解の候補）の適応度（fitness）を定量的に評価するために用いられる。

１. ボトルネックを回避するためにクラスタ全体でワークロードを均等に分散させる（Threshold Distance）

f:id:hirotsuru314:20190328222537p:plain

２. 新しいアプリケーションの追加を考慮した上で、クラスタのリソースをバランスよく利用する（Balanced Cluster）

f:id:hirotsuru314:20190328222715p:plain

３. クラスタ内のノードに適切にコンテナを分散させることによってマイクロサービスの信頼性を高める（System Failure）

f:id:hirotsuru314:20190328222655p:plain

４. 関連するマイクロサービスのコンテナを短いネットワーク距離の物理マシンに配置することによって、マイクロサービス間の通信のオーバーヘッドを小さくする（Network Distance）

f:id:hirotsuru314:20190328222846p:plain

実験と結果

実験については、GAで最適化したコンテナの配置とKubernetesのアロケーションポリシーによるアプローチのそれぞれをサンプルアプリケーションを使ってベンチマークを取って比較している。

比較対象のKubernetesについては以下のように説明されている（私はKubernetesを触ったことないのでピンときていない）
KubernetesはコンテナやPodの配置を管理するために2つのポリシーを採用している。

  1. PodFitResources：物理マシンへのリソース要求の合計がマシンのキャパシティを超えないようにする

  2. LeastRequestPriority：コンテナは一番リソース消費が少ないマシンに配置される

Kubernetesの実装についてはよく知らないが、これを見るだけでも、論文中の目的関数4つの方が多くのことを考慮して最適化しようとしているのがわかる。
論文中では、GAの世代ごとの成長過程についても色々と議論されている。結論としてはGenerations 100、Population size 200というリーズナブルな値で最適化された解が得られたと述べられている。

Kubenetesとの比較の結果については、前述の4つの目的関数全てにおいて、提案手法のアプローチの方が優位な結果が出たと述べられている。例えば、一つの目的関数をピックアップすると以下のような感じ

f:id:hirotsuru314:20190328225640p:plain

変数として、物理マシンの台数を250・300・350・400台と降っている。こんな規模で実験やるんだなぁ。

さいごに

GAのこともKubernetesのこともよく知らないから、へーって感じだったけど、こういったインフラ周りで機械学習を適用している事例は面白いなと思った。GAについては数学的な理論からしっかり学んでいく。