KVM ライブマイグレーションの仕組み

# はじめに
本記事では、以下に示す KVM(QEMU) でライブマイグレーションを行う際の代表的な3つの方式とそれぞれの特徴について説明する。

- Pre-Copy ライブマイグレーション
- Post-Copy ライブマイグレーション
- Hybrid-Copy ライブマイグレーション

実際に商用環境で VM を使用する状況において、場合によっては dirty ページ率の高い VM やメモリサイズの大きい VM は、アプリケーション特性に合わせて、マイグレーション方式の変更やチューニングの検討を行うことも必要となってくる。
その際に、本記事で記載しているような基本的なライブマイグレーションの内部処理については抑えておいた方が検討や対応スムーズに行えると思う。

## VM ライブマイグレーションとは
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/34c58166-e042-fb0e-588c-79c6816384ab.png" width=350px>

VM ライブマイグレーションとは、VM 上のアプリケーションを停止することなく、VM を自身が配置されている物理マシンから他の物理マシンへ移動することを指し、以下のような処理が行われる。

- メモリ状態の移行
- CPU state の移行
- (任意) 仮想ディスクの状態の移行

実際にマイグレーション処理を行なうマイグレーション・マネージャは、以下の特徴を持つ。
- マイグレーション・マネージャ同士は、TCP 接続をする。
- 移行元のマイグレーション・マネージャは、ゲスト VM のメモリと実行状態をマッピングし、VM のページを TCP 接続で移行先のマイグレーション・マネージャに転送する。
- 移行先のマイグレーション・マネージャは VM の状態を復元し、実行を再開する。

マイグレーション・マネージャの代表例としては、xend (Xen) や QEMU (KVM) が上げられる。

# 移行方式
ライブマイグレーションする方式としては、デフォルトで使用される「Pre-Copy Live Migration」と、ダウンタイムの最小化などを目的に使用される「Hybrid Pre/Post-Copy Live Migration」の2種類が存在する。
また、この他にも、両者のメリットを併せ持つ「Hybrid Pre/Post-Copy Live Migration」もある。

## Pre-Copy ライブマイグレーション

移行元に配置されている VM を稼働させたまま、VM の仮想メモリの内容を複数回繰り返して移行先にコピーする方法で一般的にこの方式が使用される。
  - 初回 → 全ページをコピー
  - 2回目以降 → 前の反復処理の間に dirty 状態となった page をコピー

dirty ページの数が "十分小さい" 場合は、停止やコピーは短時間で終了するが、dirty ページ数が閾値以下に収束しない場合は、一定回数反復した後にタイムアウトで強制終了する。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/0c11a3a3-e4bd-1b1a-37a2-ad3e22be972f.png" width=600px>

### 処理ステップ

**Step 1:** 移行元のマイグレーション・マネージャで dirty ページのトラッキングを有効化し、マイグレーション・マネージャを介して移行先へメモリページをコピーする。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/55f39cf9-6e37-4ff0-b9e3-df43a8b3e626.png" width=800px>

**Step 2:** 前回のコピー処理の間に更新が行われ、dirty 状態となったメモリページをコピーするステップを繰り返す。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/e0054d8e-f436-028e-e380-004c2916a5d8.png" width=800px>

**Step 3:** 移行元の VM を停止する。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/513e8fd7-d637-8f86-8f1b-ae98e835900e.png" width=800px>

**Step 4:** 移行先 VM へ残りのメモリページおよびメモリ以外の VM 状態をコピーする。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/a3197aec-d4b9-4c93-1a1e-01522934bd14.png" width=800px>

**Step 5:** 移行先の VM を起動する。
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/820ccea1-2528-4e3f-fe3a-c81a68210c3e.png" width=800px>

### マイグレーションに要する総時間

Pre-Copy ライブマイグレーションを $n$ 回実施した場合に所用する時間（$T_{mig}$）は次式で表される。

```math
T_{mig}=\frac{V_{mem}}{R}\frac{1-\lambda^n}{1-\lambda}+\tau\frac{n(1-\lambda)-\lambda(1-\lambda^n)}{(1-\lambda)^2}
```
- $R$: 帯域幅
- $V_{mem}$: マイグレーション中の VM の総メモリサイズ
- $\lambda$: メモリの dirty 率 "$D_{mem}$" と帯域幅 "$R$" の比率（$\lambda=\frac{D_{mem}}{R}$）
- $\tau$: 反復間の遅延時間

### ダウンタイム
ダウンタイム（$T_{down}$）は次式で表される。

```math
T_{down} = \frac{V_{mem}}{R}\lambda^n+\lambda\tau\frac{1-\lambda^n}{1-\lambda}+T_{net}
```
- $T_{net}$: VM の移行先へネットワーク接続を切り替えるのに要する時間

### 転送データの総サイズ
転送データの総サイズ（$M$）は次式で表される。

```math
M = V_{mem} + V_{mem}\lambda\frac{1-\lambda^n}{1-\lambda}+\tau D_{mem}\frac{n(1-\lambda)-\lambda(1-\lambda^{n+1})}{(1-\lambda)^2}
```

## Post-Copy ライブマイグレーション

1. 最初に移行元の VM を停止させ、CPU と必要最低限の状態を移行先にマイグレーションする
2. 移行先で VM を起動する（この時メモリはまだコピーされていない状態）
1. 以下の処理を同時に行い、メモリを転送する。
  - 移行先からのページング要求によるフェッチ方式での転送
  - 移行元からの push 方式での一括転送

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/49461ee5-3495-dd6f-4136-6dbb43b82eb8.png" width=600px>

この方法はダウンタイムが少ないように見えるが、ページフォルトが多発するような状況の場合、マイグレーション・マネージャで追加的に処理を行うことになり、
- ネットワークトラフィックが増加
- マイグレーションに要する時間の長期化
- アプリケーション中断時間の増加し、結果として VM の性能が低下
- 移行元からのコピー中に異常が生じた場合、移行先の VM は停止するため、再起動して対応する必要がある。

### 処理ステップ

**Step 1:** 初期状態
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/c0a3a0ae-b36f-921d-545a-0f6bf5cbe06c.png" width=800px>

**Step 2:** 移行元の VM を停止
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/8b256d98-941d-556a-361f-3168df158322.png" width=800px>

**Step 3:** 移行先へメモリ以外の VM 状態をコピー
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/bb84ef40-e9c9-bf0f-8abe-2453475b3e39.png" width=800px>

**Step 4:** 移行先の VM を起動
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/8c0ced27-6d91-b210-b45d-b84f38c29ed9.png" width=800px>

**Step 5:** 移行先からのページング要求によるフェッチ方式、および移行元からの push 方式での一括転送によるメモリ転送
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/3f32d462-079f-a458-80e6-bfc11627862d.png" width=800px>

### マイグレーションに要する総時間
Post-Copy ライブマイグレーションに所用する総時間は、次式で表される。

```math
T_{mig}=(1-wP_f)(\frac{V_{mem}-V_c}{R})+P_f(T_f+\frac{(w-1)P_z}{R})(\frac{V_{mem}-V_c}{P_z})
```

- $P_f$:ページフォルトの確率
- $w$: プリフェッチ window サイズ
- $V_c$: CPU state のサイズ
- $P_z$: メモリページサイズ
- $T_f$: 1つのメモリページをコピーする時間
　　$T_f=\frac{P_z}{R}+T_{f_p}$
　　※ $T_{f_p}$: ページフォルトをキャッチし、移行元にページを要求するための処理時間

### ダウンタイム
ダウンタイム（$T_{down}$）は、マイグレーションで使用される帯域幅に比例しており、次式で表される。

```math
T_{down}=\frac{V_c}{R}+T_{net}
```

### 転送データの総サイズ
転送データの総サイズ（$M$）は、常にメモリサイズと等しくなり、次式で表される。

```math
M=V_{mem}
```

## Hybrid-Copy ライブマイグレーション

Hybrid-Copy ライブマイグレーションは、Pre-Copy と Post-Copy の長所を組み合わせた方式であり、以下のステップで実行される。

1. 移行元で VM が稼働した状態で、Pre-Copy ライブマイグレーションを1サイクル行ない、VM メモリをすべてコピー
2. 移行元の VM を停止させ、CPU state をコピー後、移行先の VM を起動
3. Post-Copy のプリページング・メモリ・フェッチ手法を使用し、移行元の　VM から残りの dirty ページを転送

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/330e6664-e336-a8de-f9e8-79784afcd533.png" width=600px>

### 処理ステップ

**Step 1:** 移行元で VM が稼働した状態で、Pre-Copy ライブマイグレーションを1サイクル行ない、VM メモリをすべてコピー
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/96ec4a3c-90e6-f838-4ecb-d71de5bc49aa.png" width=800px>

**Step 2:** 移行元の VM を停止
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/e5d95b40-f3cf-4e01-c125-f12ab1efafc6.png" width=800px>

**Step 3:** CPU state をコピー
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/e1fb89b4-c700-10c8-3fd5-8c1aee224bab.png" width=800px>

**Step 4:** 移行先の VM を起動
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/52252279-ea4a-d3ef-d54e-ff502fb0119a.png" width=800px>

**Step 5:** Post-Copy のプリページング・メモリ・フェッチ手法を使用し、移行元の　VM から残りの dirty ページを転送
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2659159/c2fb84c6-8a17-805c-7b93-67e86e886b3e.png" width=800px>

### マイグレーションに要する総時間
Hybrid-Copy ライブマイグレーションに所用する総時間は、次式で表される。

```math
T_{mig}=T_{mig-Pre-Copy}+T_{mig-Post-Copy}
```

$T_{mig−Pre−Copy}$は、メモリ全体をコピーする Pre-Copy を1サイクル分マイグレーションするのに要する時間で、次式で表される。
```math
T_{mig-Pre-Copy}=\frac{V_{mem}}{R}
```

$T_{mig-Post-Copy}$は、dirty メモリページをコピーする Post-Copy フェーズのマイグレーション時間で、次式で表される。
```math
T_{mig-Post-Copy}=(1-wP_f)(\frac{V'_{mem}-V_c}{R})+P_f(T_f+\frac{(w-1)P_z}{R})(\frac{V_{mem}-V_c}{P_z})
```
  
ここで、$V'_{mem}$は、Pre-Copy の反復を行った後の残りのメモリで、次式で与えられる。
  ```math
  V'_{mem}=D_{mem}\frac{V_{mem}}{R}
  ```

よって、Hybrid-Copy ライブマイグレーションに所用する総時間は、以下の式で表すことができる。

```math
T_{mig}=\frac{V_{mem}}{R}+(1-wP_f)(\frac{V'_{mem}-V_c}{R})+P_f(T_f+\frac{(w-1)P_z}{R})(\frac{V_{mem}-V_c}{P_z})
```

### ダウンタイム
ダウンタイム（$T_{down}$）は、Post-Copy のダウンタイムと同じで、次式で表される。

```math
T_{down}=\frac{V_c}{R}+T_{net}
```

### 転送データの総サイズ
転送データの総サイズ（$M$）は、Pre-Copy を1サイクルと Post-Copy で転送されるメモリページの合計であり、次式で表される。

```math
M=V_{mem}(1+\frac{D_{mem}}{R})
```

## 各ライブマイグレーション方式の比較

| マイグレーション方式 | コピーの反復 | 移行元ホストへの依存 | ダウンタイム | 転送データ量 | マイグレーション時間 |
|:--|:--|:--|:--|:--|:--|
| Pre-Copy | 固定値 | ・コピー反復中: VM は移行元で動作 | CPU/ネットワークの状態、および dirty メモリページの転送遅延 | 多い。<br/>dirty メモリページを反復してコピーする。 | dirty 率、反復回数、帯域幅に依存。 |
| Post-Copy | コピーの反復なし | ・メモリマイグレーション時: VM は移行先で動作 | CPU/ネットワーク状態の転送遅延 | メモリサイズと同等のサイズを転送 | 移行先のページフォルト率に依存。 |
| Hybrid-Copy | 1サイクル | ・コピー反復中: VM は移行元で動作<br/>・コピー後: VM は移行先で動作 | CPU/ネットワーク状態の転送遅延 | dirty 率に依存率に依存。<br/>Pre-Copy フェーズにおける "メモリ＋dirty ページ" のサイズ | dirty 率と帯域幅に依存。 |

# 参考文献
- Kartik Gopalan, "Live Migration of Virtual Machines", https://www.youtube.com/watch?v=4axYrG5QBvY
- Mohammad A. Altahat & Anjali Agarwal & Nishith Goel & Jim Kozlowski, "Dynamic Hybrid-copy Live Virtual Machine Migration: Analysis and Comparison"