With the recent increase of cloud computing's prevalence, the number of online services deployed over virtualized infrastructures has experienced a tremendous growth. At the same time, however, the latest hardware trend of growing component number in current computing systems (e.g., data-centers, high-end computer clusters, etc.) renders hardware failures common place rather than exceptional.Hardware failures can lead to a degradation in performance to end-users due to service unavailability and can result in losses to the business, both in immediate revenue as well as in longterm reputation. Thus, software solutions capable of masking hardware failures in a transparent manner are becoming more and more important. Replication at the Virtual Machine (VM) layer is an attractive technique towards accommodating VM installations with high availability, primarily, because it provides seamless failover for the entire software stack executed inside the virtual machine, regardless the application or the underlying Operating System (OS).

One particular approach, checkpoint-recovery based VM replication has received a lot of attention during the last few years. Checkpoint-recovery based replication of virtual machines is attained by capturing the entire execution state of the running VM at relatively high frequency in order to propagate changes to the backup machine almost instantly. This solution, essentially, keeps the backup machine nearly up-to-date with the latest execution state of the primary machine so that the backup can take over the execution in case the primary fails. While checkpoint-recovery based replication is inherently capable of tackling with symmetric multiprocessing (SMP) VMs, i.e., virtual machines with multiple virtual CPUs (vCPUs), due to the large amount of state that needs to be synchronized between the primary and the backup machines, performance degradation of the applications executed in replicated VMs can be significant even on uni-processor setups.

This dissertation makes four main contributions towards providing good performance and ensuring high availability at the same time. As one of the major factors of replication overhead is the large amount of state that needs to be transferred over the network, efficient data compression can potentially mitigate overhead. First, this thesis presents a novel approach for decreasing network traffic during synchronization between the primary and backup machines by a lightweight compression method that exploits data self-similarity inside the virtual machine's memory image. A bit-projection based hash function is proposed, upon which, a content based hash table is built for the purpose of finding memory areas that are similar to the dirtied memory. The similar memory areas are then utilized to obtain and transfer only differences, instead of entire memory pages.

Second, the potential advantages of utilizing features of high-performance interconnects, such as Remote Direct Memory Access (RDMA) and OS-bypass communication, are explored in the context of VM replication.

Naturally, different workloads exhibit different behavior in terms of memory usage and I/O patterns. When exactly checkpoints are taken has substantial impact on the efficiency of the replicated virtual machine. As opposed to previous studies, which employ fixed checkpoint frequency, this thesis investigates the impact of dynamic checkpoint scheduling. Our third contribution, workload adaptive checkpoint scheduling, initiates checkpoints with respect to the memory and I/O behavior of the given workload, as well as to the network bandwidth available for replication.

Finally, TCP transmission performance of replication virtual machines is considered. We revisit the basic replication protocol and extend it with speculative communication. Speculative communication fabricates and delivers speculative acknowledgments to the VM in response to its TCP packets so that the guest's TCP stack can progress with TCP transmission. Furthermore, we propose replication aware congestion control, an extension to the guest OS' TCP stack that aggressively fills up the replication buffer of the VMM so that a large amount of speculative packets can be sent to the backup host and released earlier to the clients.

These improvements, which have been implemented in the Linux Kernel Virtual Machine (KVM), are evaluated under a variety of workloads that show superior performance compared to existing replication solutions.

インターネット上のサーバは仮想計算機上で実現されるようになった。これらサーバ群の可用性を向上させるために仮想計算機上のシステムの複製を取る手法が取られている。しかし、従来の手法では複製のためのデータ転送容量が大きく高性能ネットワークを必要としている、クライアントとTCP接続しているサーバの通信状態を効率よく複製する手法が確立していない、という問題がある。本論文では、これら問題点を解決する手法を提案、実装、評価し、その有効性を示しおり、以下のとおり8章から構成される。

第1章では、背景として従来の可用性向上技術を俯瞰し、本論文で取り組む仮想計算機を用いた可用性向上技術を明確に位置づけしている。仮想計算機上のシステムの可用性を上げるために定期的にシステムの複製(チェックポイント)を行う。システムチェックポイント時に解決されていない問題点として、i)チェックポイント時のデータ転送容量削減、ii)チェックポイントタイミング、iii)外部とTCP接続している時のTCP状態の一貫性維持があり、本論文はこれら3つの課題に対する新しい手法を提案している。

第2章は、本論文が対象とする仮想計算機の技術的背景とチェックポイント手法の基本について述べている。第3章では、チェックポイント対象であるシステムメモリ上のメモリ領域類似性を利用したデータ転送容量削減手法を提案している。メモリ領域類似性を示すために以下の実験を行っている。複数の実アプリケーションベンチマークプログラムを10分間連続して実行する。この間に100msec間隔での定期的チェックポイントにおいて直前のチェックポイントから書き変わったメモリ領域を比較すると、2Kバイトのメモリ領域で77%程度、64倍のメモリ領域で85%程度の類似性を有するという事実を示す。この事実をもとに、チェックポイント時にメモリ領域の類似性を調べるための機構として密度ハッシュ関数(Density based hash function)を用いた連想ハッシュテーブル(Content Addressable Hash Table)と類似性を持つメモリとの差分のみを転送することによりデータ転送容量を削減する手法を提案している。本提案手法の有効性を示すために、Linuxカーネルコンパイル、SPECweb、Microsoft Exchange Serverベンチマークを用いて通常チェックポイント方式と比較している。これらベンチマークの実行結果、最大で通常のチェックポイントデータ転送容量の20%を削減していることが示されている。また、Microsoft Exchange Serverベンチマークの実行結果として通常チェックポイント方式に比べて約1.8倍の性能向上を得たことを示している。

第4章では、高速チェックポイントデータ転送手法として、Infinibandネットワークが有する遠隔直接メモリアクセス(RDMA: Remote Direct Memory Access)機構を書き込み時コピー(Copy on Write)手法と組み合わせた手法を提案実装し評価している。RDMA機構を用いることによりデータ転送時のCPU介在コストが削減され、Linuxカーネルコンパイルでは高々34%の性能減でチェックポイント可能となったことを示している。

第5章では、サーバの負荷状況に応じたチェックポイントタイミング調整手法を提案している。チェックポイント後に変更されるメモリ領域はアプリケーションレベルでのメモリ変更以外にネットワークバッファ、ディスクI/Oバッファなどのカーネル内バッファのメモリ変更がある。本章では、これらメモリの変更度合いを動的に調べ、チェックポイントタイミングを決めるという新しい手法を提案している。Hadoop MR/DBベンチマークによる評価で、本手法を用いることによる5%の性能劣化だけでチェックポイント可能であることを示している。

第6章では、サーバがダウンしチェックポイント時の状態を用いて再開する場合においてもクライアントとのTCP接続状態を保つために用いられている仮想計算機内通信バッファを用いてTCP通信の高速化手法を提案している。仮想計算機上のシステムと本バッファ領域をチェックポイントし、その後バッファに格納されているパケットをクライアントに送信する。これにより、仮想計算機がダウンしてもチェックポイント時点から再開を行い、クライアントに対しては格納された通信パケットを用いてTCP通信を再開できる。さらに提案手法では、クライアントからのACKを待たずに仮想計算機内でACKを送信するため、見かけのRTT(往復遅延)が短くなり高速化に寄与する。クライアントからのACKを待たずにTCP通信経路の途中でACKを返す手法はTCP通信の高速化技法のひとつとして知られている。本論文では、TCP通信状態とともに一貫性のあるチェックポイントを実現するための技法と組み合わせて仮想計算機に実現しており、従来の研究とは異なった視点での応用であるといえる。本手法の有効性を示すため、SPECwebベンチマークを用いて比較した。本手法によりチェックポイントしないときの実行性能の90%の性能を達成したことが示されている。

第7章において、それぞれの提案手法に関連する既存研究を紹介し、提案手法の違いならびに新規性について議論し、第8章において本論文をまとめている。

このように本論文では、仮想計算機の複製を効率よく取得する手法としてメモリ領域の同一性に着目してデータ転送量を削減する手法、仮想計算機の負荷状況に依存した複製タイミング手法の2つを提案しその有効性を多くの実際に使われているアプリケーションベンチマークプログラムを用いて評価することによって示した。さらに、サーバが外部とTCP接続して通信している最中にサーバがダウンしても再実行可能とするための通信層を提案した。これら本研究の成果は、仮想計算機の高可用化に多大な貢献を行っており、仮想計算機ソフトウェアの発展に顕著な貢献をしたといえる。

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。