Memory Deduplication

Limited memory sizes and latencies have become a primary bottleneck. In cloud-computing scenarios, the number of virtual systems that can be co-located on a physical system mainly depends on the amount of available memory on the hosting server. In this project, we research novel methods for main memory deduplication as well as techniques that make memory deduplication more efficient.

In cloud computing, virtual machines (VMs) permit the flexible allocation and migration of services as well as the consolidation of systems onto fewer physical machines, while preserving strong service isolation. However, in that scenario the available main memory size limits the number of VMs that can be co-located on a single machine.

Prior work has shown great opportunity for memory deduplication. There may be plenty of redundant data between VMs (inter-VM sharing), e.g., if similar operating systems (OSes) or applications are used in different VM instances. Moreover, previous studies have shown that the memory footprint of VMs often contains a significant amount of pages with equal content within a single instance (self-sharing). In both cases, memory can be freed by collapsing redundant pages to a single page and sharing it in a copy-on-write fashion. However, such pages cannot be identified using traditional sharing mechanisms due to the semantic gap caused by the isolation of VMs.

Memory scanners mitigate the semantic gap by scanning for duplicate content in guest pages. They index the contents of memory pages at a certain rate, regardless of their usage semantics. Memory scanners trade computational overhead and memory bandwidth with deduplication success and latency. Current scanners need a considerable amount of time to detect new sharing opportunities (e.g., 5 min) and therefore do not exploit the full sharing potential.

XLH is our contribution that augments memory scanners with cross layer hints. We have observed that:

• All types of memory contents (named and anonymous) contribute to memory redundancy.
• Many shareable pages in the host's main memory originate from accesses to background storage: when multiple VMs create or use the same programs, shared libraries, configuration files, and data from their respective virtual disk images (VDIs).

XLH observes guest I/O in the host and to use it as a trigger for memory scanners in order to speed up the identification of new sharing opportunities. XLH indexes I/O pages soon after their content has been established and thus moves them earlier into the merging stage. In consequence, XLH can find short-lived sharing opportunities and shares redundant data longer than regular, linear memory scanners without raising the overall scan rate.

We have shown that XLH is able to quickly deduplicate the memory of newly booted VMs, which is especially beneficial when sandboxing short-running jobs or migrating many VMs at once. Measurements of kernel build and web server scenarios show that XLH deduplicates equal pages that stem from the VDI earlier by 2-4 minutes and is capable of merging between up to 10x as many sharing opportunities as the baseline system. For the kernel build benchmark, XLH performs constantly better than KSM even if the scan rate is set 5x lower. We have also evaluated XLH in an unfavorable scenario and found that it did not worsen the sharing performance compared to KSM. XLH reaches its effectiveness with little to no additional CPU overhead or loss in I/O throughput compared with KSM. Initial benchmarks in native environments indicate that memory deduplication could also be improved significantly for native applications.

Our XLH prototype, based on Linux 3.4-rc3 (commit: e816b57a337ea3b755de72bec38c10c864f23015) and can be obtained here. We have stripped the debug and statistics code. The hash table implementation was omitted as well, due to Patent 6789156 B1.

Contact: Prof. Dr.-Ing. Frank Bellosa