Using vector interfaces to deliver millions of IOPS from a networked key-value storage server

ABSTRACT

The performance of non-volatile memories (NVM) has grown by a factor of 100 during the last several years: Flash devices today are capable of over 1 million I/Os per second. Unfortunately, this incredible growth has put strain on software storage systems looking to extract their full potential.

To address this increasing software-I/O gap, we propose using vector interfaces in high-performance networked systems. Vector interfaces organize requests and computation in a distributed system into collections of similar but independent units of work, thereby providing opportunities to amortize and eliminate the redundant work common in many high-performance systems. By integrating vector interfaces into storage and RPC components, we demonstrate that a single key-value storage server can provide 1.6 million requests per second with a median latency below one millisecond, over fourteen times greater than the same software absent the use of vector interfaces. We show that pervasively applying vector interfaces is necessary to achieve this potential and describe how to compose these interfaces together to ensure that vectors of work are propagated throughout a distributed system.

References

1. FAWN-KV: A distributed key-value store for FAWN. http://github.com/vrv/FAWN-KV.
2. Apache Thrift. https://thrift.apache.org/, 2011.
3. A. Akel, A. M. Caulfield, T. I. Mollov, R. K. Gupta, and S. Swanson. Onyx: A prototype phase change memory storage array. In Proc. HotStorage, Portland, OR, June 2011.
4. A. Anand, C. Muthukrishnan, S. Kappes, A. Akella, and S. Nath. Cheap and large CAMs for high performance data-intensive networked systems. In Proc. 7th USENIX NSDI, San Jose, CA, Apr. 2010.
5. D. G. Andersen, J. Franklin, M. Kaminsky, A. Phanishayee, L. Tan, and V. Vasudevan. FAWN: A fast array of wimpy nodes. In Proc. 22nd ACM Symposium on Operating Systems Principles (SOSP), Big Sky, MT, Oct. 2009.
6. A. M. Caulfield, A. De, J. Coburn, T. Mollov, R. Gupta, and S. Swanson. Moneta: A high-performance storage array architecture for next-generation, non-volatile memories. In IEEE Micro, Dec. 2010.
7. B. Debnath, S. Sengupta, and J. Li. FlashStore: high throughput persistent key-value store. Proc. VLDB Endow., 3: 1414--1425, Sept. 2010.
8. B. Debnath, S. Sengupta, and J. Li. SkimpyStash: RAM space skimpy key-value store on flash. In Proc. ACM SIGMOD, Athens, Greece, June 2011.
9. M. Dobrescu, N. Egi, K. Argyraki, B.-G. Chun, K. Fall, G. Iannaccone, A. Knies, M. Manesh, and S. Ratnasamy. Route-Bricks: Exploiting parallelism to scale software routers. In Proc. 22nd ACM Symposium on Operating Systems Principles (SOSP), Big Sky, MT, Oct. 2009.
10. R. Freitas, J. Slember, W. Sawdon, and L. Chiu. GPFS scans 10 billion files in 43 minutes. IBM Whitepaper, http://www.almaden.ibm.com/storagesystems/resources/GPFS-Violin-white-paper.pdf, 2011.
11. fusion-io. Fusion-IO. http://www.fusionio.com.
12. M. Garland and D. B. Kirk. Understanding throughput-oriented architectures. Communications of the ACM, 53(11): 58--66, Nov. 2010.
13. J. Hamilton. Scaling at MySpace. http://perspectives.mvdirona.com/2010/02/15/ScalingAtMySpace.aspx, 2010.
14. S. Han, K. Jang, K. Park, and S. Moon. PacketShader: a GPU-accelerated software router. In Proc. ACM SIGCOMM, New Delhi, India, Aug. 2010.
15. R. Johnson, S. Harizopoulos, N. Hardavellas, K. Sabirli, I. Pandis, A. Ailamaki, N. G. Mancheril, and B. Falsafi. To share or not to share? In Proc. VLDB, Vienna, Austria, Sept. 2007.
16. M. Krohn, E. Kohler, and M. F. Kaashoek. Events can make sense. In Proc. USENIX Annual Technical Conference, Santa Clara, CA, June 2007.
17. J. R. Larus and M. Parkes. Using cohort scheduling to enhance server performance. In Proc. USENIX Annual Technical Conference, Berkeley, CA, June 2002.
18. H. Lim, B. Fan, D. G. Andersen, and M. Kaminsky. SILT: A memory-efficient, high-performance key-value store. In Proc. 23rd ACM Symposium on Operating Systems Principles (SOSP), Cascais, Portugal, Oct. 2011.
19. T. Marian. Operating Systems Abstractions for Software Packet Processing in Datacenters. PhD thesis, Cornell University, Jan. 2011.
20. J. C. McCullough, J. Dunagan, A. Wolman, and A. C. Snoeren. Stout: An adaptive interface to scalable cloud storage. In Proc. USENIX Annual Technical Conference, Boston, MA, June 2010.
21. G. Memik, M. T. Kandemir, W. Liao, and A. Choudhary. Multicollective i/o: A technique for exploiting inter-file access patterns. volume 2, Aug. 2006.
22. J. Ousterhout, P. Agrawal, D. Erickson, C. Kozyrakis, J. Leverich, D. Mazières, S. Mitra, A. Narayanan, G. Parulkar, M. Rosenblum, S. M. Rumble, E. Stratmann, and R. Stutsman. The case for RAMClouds: Scalable high-performance storage entirely in DRAM. In Operating Systems Review, volume 43, pages 92--105, Jan. 2010.
23. M. Polte, J. Simsa, and G. Gibson. Enabling enterprise solid state disks performance. In Proc. Workshop on Integrating Solid-state Memory into the Storage Hierarchy, Washington, DC, Mar. 2009.
24. N. Provos. libevent. http://monkey.org/~provos/libevent/.
25. J. M. Pujol, V. Erramilli, G. Siganos, X. Yang, N. Laoutaris, P. Chhabra, and P. Rodriguez. The little engine(s) that could: Scaling online social networks. In Proc. ACM SIGCOMM, New Delhi, India, Aug. 2010.
26. A. Purohit, C. P. Wright, J. Spadavecchia, and E. Zadok. Cosy: Develop in user-land, run in kernel-mode. In Proc. HotOS IX, Lihue, Hawaii, May 2003.
27. M. Rajagopalan, S. K. Debray, M. A. Hiltunen, and R. D. Schlicting. Cassyopia: Compiler assisted system optimization. In Proc. HotOS IX, Lihue, Hawaii, May 2003.
28. E. Seppanen, M. T. O'Keefe, and D. J. Lilja. High performance solid state storage under linux. In 26th IEEE Symposium on Massive Storage Systems and Technologies, May 2010.
29. L. Soares and M. Stumm. FlexSC: Flexible system call scheduling with exception-less system calls. In Proc. 9th USENIX OSDI, Vancouver, Canada, Oct. 2010.
30. J. Sugerman, K. Fatahalian, S. Boulos, K. Akeley, and P. Hanrahan. GRAMPS: A programming model for graphics pipelines. In ACM Transactions on Graphics, Jan. 2009.
31. V. Vasudevan, D. G. Andersen, M. Kaminsky, L. Tan, J. Franklin, and I. Moraru. Energy-efficient cluster computing with FAWN: Workloads and implications. In Proc. e-Energy 2010, Passau, Germany, Apr. 2010. (invited paper).
32. V. Vasudevan, D. G. Andersen, and M. Kaminsky. The case for VOS: The vector operating system. In Proc. HotOS XIII, Napa, CA, May 2011.
33. S. Venkataraman, N. Tolia, P. Ranganathan, and R. Campbell. Consistent and Durable Data Structures for Non-Volatile Byte-Addressable Memory. In Proceedings of the 9th USENIX Conference on File and Storage Technologies (FAST '11), San Jose, CA, Feb. 2011.
34. M. Welsh, D. Culler, and E. Brewer. SEDA: An architecture for well-conditioned, scalable Internet services. In Proc. 18th ACM Symposium on Operating Systems Principles (SOSP), Banff, Canada, Oct. 2001.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Measurement

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles