Opportunistic Spinlocks: Achieving Virtual Machine Scalability in the Clouds

Abstract

With increasing demand for big-data processing and faster in-memory databases, cloud providers are moving towards large virtualized instances besides focusing on the horizontal scalability.

However, our experiments reveal that such instances in popular cloud services (e.g., 32 vCPUs with 208 GB supported by Google Compute Engine) do not achieve the desired scalability with increasing core count even with a simple, embarrassingly parallel job (e.g., Linux kernel compile). On a serious note, the internal synchronization scheme (e.g., paravirtualized ticket spinlock) of the virtualized instance on a machine with higher core count (e.g., 80-core) dramatically degrades its overall performance. Our finding is different from the previously well-known scalability problem (i.e., lock contention problem) and occurs because of the sophisticated optimization techniques implemented in the hypervisor---what we call sleepy spinlock anomaly. To solve this problem, we design and implement OTICKET, a variant of paravirtualized ticket spinlock that effectively scales the virtualized instances in both undersubscribed and oversubscribed environments.

References

1. Paravirtualized Spinlocks, 2008. http://lwn.net/Articles/289039/.
2. The CPU Scheduler in VMware ESX 4.1.
3. MCS locks and qspinlocks, 2014. https://lwn.net/Articles/590243/.
4. Exim Internet Mailer, 2015. http://www.exim.org/.
5. SAP HANA, 2015. http://hana.sap.com/abouthana.html.
6. ADAMS, K., AND AGESEN, O. A Comparison of Software and Hardware Techniques for x86 Virtualization. In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems (2006), ASPLOS.
7. AHN, J., PARK, C. H., AND HUH, J. Micro-Sliced Virtual Processors to Hide the Effect of Discontinuous CPU Availability for Consolidated Systems. In Proceedings of the 47th Annual IEEE/ACM International Symposium on Microarchitecture (2014), MICRO.
8. BARHAM, P., DRAGOVIC, B., FRASER, K., HAND, S., HARRIS, T., HO, A., NEUGEBAUER, R., PRATT, I., AND WARFIELD, A. Xen and the Art of Virtualization. In Proceedings of the 19th ACM Symposium on Operating Systems Principles (SOSP) (Bolton Landing, NY, Oct. 2003).
9. BARR, J. EC2 Instance Update -- X1 (SAP HANA) & T2.Nano (Websites), 2015. https://aws.amazon.com/blogs/aws/ec2-instance-update-x1-sap-hana-t2-nano-websites/.
10. BOYD-WICKIZER, S., CLEMENTS, A. T., MAO, Y., PESTEREV, A., KAASHOEK, M. F., MORRIS, R., AND ZELDOVICH, N. An Analysis of Linux Scalability to Many Cores. In Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation (2010), OSDI.
11. BOYD-WICKIZER, S., KAASHOEK, M. F., MORRIS, R., AND ZELDOVICH, N. Non-scalable locks are dangerous. In Ottawa Linux Symposium (2012), OLS.
12. BUESO, D. Scalability Techniques for Practical Synchronization Primitives, 2014. https://queue.acm.org/detail.cfm?id=2698990.
13. CLEMENTS, A. T., KAASHOEK, M. F., AND ZELDOVICH, N. RadixVM: Scalable Address Spaces for Multithreaded Applications. In Proceedings of the ACM EuroSys Conference (Prague, Czech Republic, Apr. 2013), pp. 211--224.
14. CLEMENTS, A. T., KAASHOEK, M. F., ZELDOVICH, N., MORRIS, R. T., AND KOHLER, E. The Scalable Commutativity Rule: Designing Scalable Software for Multicore Processors. In Proceedings of the 24th ACM Symposium on Operating Systems Principles (SOSP) (Farmington, PA, Nov. 2013), pp. 1--17.
15. DING, X., GIBBONS, P. B., KOZUCH, M. A., AND SHAN, J. Gleaner: Mitigating the Blocked-waiter Wakeup Problem for Virtualized Multicore Applications. In Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference (2014), USENIX ATC.
16. FRIEBEL, T. How to Deal with Lock-Holder Preemption. In Xen Summit North America (2008), XenSummit.
17. GORDON, A., AMIT, N., HAR'EL, N., BEN-YEHUDA, M., LANDAU, A., SCHUSTER, A., AND TSAFRIR, D. Eli: Baremetal performance for i/o virtualization. In Proceedings of the 17th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) (London, UK, Mar. 2012), ASPLOS XVII, pp. 411--422.
18. INC., E.-S. Mail (MX) Server Survey, 2014. http://www.securityspace.com/s_survey/data/man.201404/mxsurvey.html.
19. KIM, H., KIM, S., JEONG, J., LEE, J., AND MAENG, S. Demand-based Coordinated Scheduling for SMP VMs. In Proceedings of the Eighteenth International Conference on Architectural Support for Programming Languages and Operating Systems (2013), ASPLOS.
20. LONG, W. locking/qspinlock: Enhance pvqspinlock & introduce queued unfair lock, 2015. https://lwn.net/ Articles/650776/.
21. LONG, W. qspinlock: a 4-byte queue spinlock with PV support, 2015. https://lkml.org/lkml/2015/4/24/631.
22. MAO, Y., MORRIS, R., AND KAASHOEK, F. M. Optimizing MapReduce for Multicore Architectures. In MIT CSAIL, Technical Report (2010).
23. MCKENNEY, P. E., APPAVOO, J., KLEEN, A., KRIEGER, O., RUSSELL, R., SARMA, D., AND SONI, M. Read-Copy Update. In Ottawa Linux Symposium (2002), OLS.
24. MENON, A., SANTOS, J. R., TURNER, Y., JANAKIRAMAN, G. J., AND ZWAENEPOEL, W. Diagnosing Performance Overheads in the Xen Virtual Machine Environment. In Proceedings of the 1st ACM/USENIX International Conference on Virtual Execution Environments (2005), VEE.
25. MICROSOFT. SQL Server 2014, 2014. http://www. microsoft.com/en-us/server-cloud/products/sqlserver/ features.aspx.
26. OUYANG, J., AND LANGE, J. R. Preemptable Ticket Spinlocks: Improving Consolidated Performance in the Cloud. In Proceedings of the 9th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments (2013), VEE.
27. PHILLIPS, S. M7: Next Generation SPARC.
28. RAGHAVENDRA, K., VADDAGIRI, S., DADHANIA, N., AND FITZHARDINGE, J. Paravirtualization for Scalable Kernel- Based Virtual Machine (KVM). In Cloud Computing in Emerging Markets (CCEM) (2012).
29. RIGHINI, M. Enabling Intel Virtualization Technology Features and Benefits, 2010.
30. SONG, X., CHEN, H., AND ZANG, B. Characterizing the Performance and Scalability of Many-core Applications on Virtualized Platforms. In Fudan University - Technical Report (2010).
31. SONG, X., SHI, J., CHEN, H., AND ZANG, B. Schedule Processes, Not VCPUs. In Proceedings of the 4th Asia-Pacific Workshop on Systems (2013), APSys.
32. SUKWONG, O., AND KIM, H. S. Is Co-scheduling Too Expensive for SMP VMs? In Proceedings of the ACM EuroSys Conference (Salzburg, Austria, Apr. 2011).
33. UHLIG, V., LEVASSEUR, J., SKOGLUND, E., AND DANNOWSKI, U. Towards Scalable Multiprocessor Virtual Machines. In Proceedings of the 3rd Conference on Virtual Machine Research And Technology Symposium - Volume 3 (2004), VM.
34. WENG, C., LIU, Q., YU, L., AND LI, M. Dynamic Adaptive Scheduling for Virtual Machines. In Proceedings of the 20th International Symposium on High Performance Distributed Computing (2011), HPDC.
35. ZAHARIA, M., CHOWDHURY, M., FRANKLIN, M. J., SHENKER, S., AND STOICA, I. Spark: Cluster Computing with Working Sets. In Proceedings of the 2Nd USENIX Conference on Hot Topics in Cloud Computing (2010), Hot-Cloud'10.