Home | english  | Impressum | KIT

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.

Hints for Memory Scanners

   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)[1]. 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[2] caused by the isolation of VMs.

Memory scanners mitigate the semantic gap by scanning for duplicate content in guest pages[6,7]. 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.

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.

Publications
Author Title Source

Konrad Miller, Fabian Franz, Thorsten Groeninger, Marc Rittinghaus, Marius Hillenbrand, and Frank Bellosa

Proceedings of the ASPLOS Workshop on Runtime Environments, Systems, Layering and Virtualized Environments (RESoLVE'12), London, UK, March 3, 2012

Konrad Miller, Fabian Franz, Marc Rittinghaus, Marius Hillenbrand, and Frank Bellosa

Proceedings of the 2013 USENIX Annual Technical Conference, San Jose, CA, June 26-28, 2013



Student Projects
Author Title Type Date Advisor
Fabian Franz Diplomarbeit 29.07.2012

Prof. Dr. Frank Bellosa, Konrad Miller

Marc Rittinghaus Diplomarbeit 05.07.2012

Prof. Dr. Frank Bellosa, Konrad Miller

Thorsten Gröninger Studienarbeit 21.11.2011

Prof. Dr. Frank Bellosa, Konrad Miller



Memory Deduplication for Native Applications

Traditional memory sharing mechanisms and newer deduplication mechanisms for virtualized environments make assumptions that do not hold in all environments. Our benchmarks indicate that memory deduplication can be improved significantly for native applications.

Student Projects
Author Title Type Date Advisor
Philipp Kern Diplomarbeit 30.04.2013

Prof. Dr. Frank Bellosa, Konrad Miller

Jonas Julino Studienarbeit 27.03.2012

Prof. Dr. Frank Bellosa, Konrad Miller



Bibliography

[1] Barker, S. et al. An empirical study of memory sharing in virtual machines. USENIX ATC 2012

[2] Chen and Noble. When virtual is better than real. HotOS 2001

[3] Bugnion, Devine, Govil, and Rosenblum. Disco: running commodity operating systems on scalable multiprocessors. Transactions on Computer Systems 1997

[4] Milos, Murray, Hand, and Fetterman. Satori: Enlightened page sharing. USENIX ATC 2009

[5] Barham, Dragovic, Fraser, et al. Xen and the art of virtualization. SOSP 2003

[6] Waldspurger. Memory resource management in VMware ESX server. SIGOPS Operating System Review 2002

[7] Arcangeli, Eidus, and Wright. Increasing memory density by using KSM. Linux Symposium 2009