CMD: classification-based memory deduplication through page access characteristics

ABSTRACT

Limited main memory size is considered as one of the major bottlenecks in virtualization environments. Content-Based Page Sharing (CBPS) is an efficient memory deduplication technique to reduce server memory requirements, in which pages with same content are detected and shared into a single copy. As the widely used implementation of CBPS, Kernel Samepage Merging (KSM) maintains the whole memory pages into two global comparison trees (a stable tree and an unstable tree). To detect page sharing opportunities, each tracked page needs to be compared with pages already in these two large global trees. However since the vast majority of compared pages have different content with it, that will induce massive futility comparisons and thus heavy overhead.

In this paper, we propose a lightweight page Classification-based Memory Deduplication approach named CMD to reduce futile page comparison overhead meanwhile to detect page sharing opportunities efficiently. The main innovation of CMD is that pages are grouped into different classifications based on page access characteristics. Pages with similar access characteristics are suggested to have higher possibility with same content, thus they are grouped into the same classification. In CMD, the large global comparison trees are divided into multiple small trees with dedicated local ones in each page classification. Page comparisons are performed just in the same classification, and pages from different classifications are never compared (since they probably result in futile comparisons). The experimental results show that CMD can efficiently reduce page comparisons (by about 68.5%) meanwhile detect nearly the same (by more than 98%) or even more page sharing opportunities.

References

1. ab - apache http server benchmarking tool. http://httpd.apache.org/docs/2.2/programs/ab.html.
2. Kvm-kernel based virtual machine. http://www.linux-kvm.org/page/Main_Page.
3. Linux 2 6 32 - linux kernel newbies. http://kernelnewbies.org/Linux_2_6_32.
4. Sysbench: a system performance benchmark. http://sysbench.sourceforge.net/.
5. Tcpdump and libpcap. http://www.tcpdump.org/.
6. A. Arcangeli, I. Eidus, and C. Wright. Increasing memory density by using ksm. In Proceedings of the Linux Symposium (OLS'09), pages 19--28, 2009.
7. Y. Bao, M. Chen, Y. Ruan, L. Liu, J. Fan, Q. Yuan, B. Song, and J. Xu. Hmtt: a platform independent full-system memory trace monitoring system. In Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, SIGMETRICS '08, pages 229--240, 2008.
8. S. Barker, T. Wood, P. Shenoy, and R. Sitaraman. An empirical study of memory sharing in virtual machines. In Proceedings of the 2012 USENIX conference on Annual Technical Conference, USENIX ATC'12, pages 273--284, 2012.
9. F. Bellard. Qemu, a fast and portable dynamic translator. In Proceedings of the annual conference on USENIX Annual Technical Conference, ATEC '05, pages 41--46, 2005.
10. E. Bugnion, S. Devine, K. Govil, and M. Rosenblum. Disco: running commodity operating systems on scalable multiprocessors. ACM Trans. Comput. Syst., 15(4):412--447, Nov. 1997.
11. R. Ceron, R. Folco, B. Leitao, and H. Tsubamoto. Power systems memory deduplication. In IBM Redbooks, 2012. http://www.redbooks.ibm.com/abstracts/redp4827.html.
12. C.-R. Chang, J.-J. Wu, and P. Liu. An empirical study on memory sharing of virtual machines for server consolidation. In Parallel and Distributed Processing with Applications (ISPA), 2011 IEEE 9th International Symposium on, pages 244--249, 2011.
13. L. Chen, Z. Cui, Y. Bao, M. Chen, Y. Huang, and G. Tan. A lightweight hybrid hardware/software approach for object- relative memory profiling. In Performance Analysis of Systems and Software (ISPASS), 2012 IEEE International Symposium on, pages 46--57, 2012.
14. J.-H. Chiang, H.-L. Li, and T.-c. Chiueh. Introspection-based memory de-duplication and migration. In Proceedings of the 9th ACM SIGPLAN/SIGOPS international conference on Virtual execution environments, VEE '13, pages 51--62, 2013.
15. Y. Deng, C. Hu, T. Wo, B. Li, and L. Cui. A memory deduplication approach based on group in virtualized environments. In Proceedings of the 2013 IEEE Seventh International Symposium on Service-Oriented System Engineering, SOSE '13, pages 367--372.
16. R. P. Goldberg. Survey of virtual machine research. Computer, 7(9):34--45, Sept. 1974.
17. D. Gupta, S. Lee, M. Vrable, S. Savage, A. C. Snoeren, G. Varghese, G. M. Voelker, and A. Vahdat. Difference engine: harnessing memory redundancy in virtual machines. In 8th USENIX Symposium on Operating Systems Design and Implementation, OSDI'08, pages 309--322, 2008.
18. Y. Huang, Z. Cui, L. Chen, W. Zhang, Y. Bao, and M. Chen. Halock: hardware-assisted lock contention detection in multithreaded applications. In Proceedings of the 21st international conference on Parallel architectures and compilation techniques, PACT '12, pages 253--262, 2012.
19. S. Kim, H. Kim, and J. Lee. Group-based memory deduplication for virtualized clouds. In 6th Workshop on Virtualization in High-Performance Cloud Computing, VHPC 2011, pages 387--397, 2011.
20. J. F. Kloster, J. Kristensen, and A. Mejlholm. Determining the use of interdomain shareable pages using kernel introspection. In Tech. rep., Aalborg University, 2007. http://mejlholm.org/uni/pdfs/dat7_introspection.pdf.
21. K. Miller, F. Franz, T. Groeninger, M. Rittinghaus, M. Hil-lenbrand, and F. Bellosa. Ksm++: Using i/o-based hints to make memory-deduplication scanners more efficient. In Proceedings of the ASPLOS Workshop on Runtime Environments, Systems, Layering and Virtualized Environments (RESoLVE'12), 2012. http://www.dcs.gla.ac.uk/conferences/resolve12/papers/session3_paper2.pdf.
22. K. Miller, F. Franz, M. Rittinghaus, M. Hillenbrand, and F. Bellosa. Xlh: More effective memory deduplication scanners through cross-layer hints. In Proceedings of the 2013 USENIX conference on Annual Technical Conference, USENIX ATC'13, pages 279--290, 2013.
23. G. Miós, D. G. Murray, S. Hand, and M. A. Fetterman. Satori: enlightened page sharing. In Proceedings of the 2009 conference on USENIX Annual technical conference, USENIX'09, pages 1--14, 2009.
24. S. Rachamalla, D. Mishra, and P. Kulkarni. All page sharing is equal, but some sharing is more equal than others. 2013. http://www.cse.iitb.ac.in/internal/techreports/reports/TR-CSE-2013--49.pdf.
25. M. Rosenblum and T. Garfinkel. Virtual machine monitors: current technology and future trends. Computer, 38(5):39--47, 2005.
26. S. Sha, J. Li, N. Li, W. Ju, L. Cui, and B. Li. Smartksm: A vmm-based memory deduplication scanner for virtual machines. http://act.buaa.edu.cn/lijx/pubs/sosp2013.smartksm.pdf.
27. P. Sharma and P. Kulkarni. Singleton: system-wide page deduplication in virtual environments. In Proceedings of the 21st international symposium on High-Performance Parallel and Distributed Computing, HPDC '12, pages 15--26, 2012.
28. M. Sindelar, R. K. Sitaraman, and P. Shenoy. Sharing-aware algorithms for virtual machine colocation. In Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures, SPAA '11, pages 367--378, 2011.
29. C. A. Waldspurger. Memory resource management in vmwareesx server. SIGOPS Oper. Syst. Rev., 36(SI):181--194, Dec. 2002.
30. T. Wood, G. Tarasuk-Levin, P. Shenoy, P. Desnoyers, E. Cecchet, and M. D. Corner. Memory buddies: exploiting page sharing for smart colocation in virtualized data centers. In Proceedings of the 2009 ACM SIGPLAN/SIGOPS international conference on Virtual execution environments, VEE '09, pages 31--40, 2009.
31. L. Xia and P. A. Dinda. A case for tracking and exploiting inter-node and intra-node memory content sharing in virtualized large-scale parallel systems. In Proceedings of the 6th international workshop on Virtualization Technologies in Distributed Computing Date, VTDC '12, pages 11--18, 2012.
32. X. Yang, C. Ye, and Q. Lin. Evaluation and enhancement to memory sharing and swapping in xen 4.1. In XenSubmitt 2011 http://www-archive.xenproject.org/files/xensummit_santaclara11/aug3/3_XiaoweiY_Evaluation_and_Enhancement_to_Memory_Sharing_and_Swapping_in_Xen204.1.pdf

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Measurement

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Main memory