[talks] Linpeng Tang: General Exam Monday, May 12, 2014 at 10am in Room 402

[Nicki Gotsis]

Linpeng Tang will present the General Exam on Monday, May 12, 2014 at 10am in Room 402.  The members of Linpeng's committee are Kai Li, Mike Freedman and Vivek Pai. 
Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so.  Linpeng's abstract and reading list follow below.

Abstract

An effective approach to improve the throughput of a static content delivery system, such as the Facebook’s photo-serving stack, is to build read-only storage caches on flash devices because they provide much higher random read throughput than disk drives and much larger capacity than DRAM. The key design challenge for these flash-based static content caches is that advanced caching algorithms generate many small random writes, even though all requests are reads, and the Flash Translation Layer on flash devices performs poorly with random writes, lowering throughput and decreasing device life- time. Coping strategies include under-utilizing the space on the device, which yields a smaller cache, or only using simple caching algorithms like FIFO, which yields lower hit ratios and decreases the utility of the cache. In this paper, we propose the novel RIPQ (Restricted Insertion Priority Queue) framework that solves this dilemma, allowing advanced caching algorithms with large cache sizes, high throughput, and long de- vice lifetime. RIPQ maintains an approximate priority queue efficiently on flash by aggregating small random writes into large writes to a restricted set of insertion points, lazily moving items, and co-locating items with similar priorities. We show that two families of advanced caching algorithms, Segmented-LRU and GDSF (Greedy-Dual-Size-Frequency), can be easily implemented with RIPQ. Our evaluation results on traces from Facebook’s photo-serving stack show that GDSF algorithms with RIPQ can improve cache hit ratios by ~20% over the current production system.


Reading List

Papers
Beaver, Doug, et al. "Finding a Needle in Haystack: Facebook's Photo Storage." OSDI. Vol. 2010. 2010.
Huang, Qi, et al. "An analysis of Facebook photo caching." Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles. ACM, 2013.
Zhou, Yuanyuan, James Philbin, and Kai Li. "The Multi-Queue Replacement Algorithm for Second Level Buffer Caches." USENIX Annual Technical Conference, General Track. 2001.
Min, Changwoo, et al. "SFS: Random write considered harmful in solid state drives." Proc. of the 10th USENIX Conf. on File and Storage Tech. 2012.
Badam, Anirudh, et al. "HashCache: Cache Storage for the Next Billion." NSDI. Vol. 9. 2009.
Lim, Hyeontaek, et al. "SILT: A memory-efficient, high-performance key-value store." Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles. ACM, 2011.
Lee, Sang-Won, et al. "A log buffer-based flash translation layer using fully-associative sector translation." ACM Transactions on Embedded Computing Systems (TECS) 6.3 (2007): 18.
Breslau, Lee, et al. "Web caching and Zipf-like distributions: Evidence and implications." INFOCOM'99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. Vol. 1. IEEE, 1999.
Rosenblum, Mendel, and John K. Ousterhout. "The design and implementation of a log-structured file system." ACM Transactions on Computer Systems (TOCS) 10.1 (1992): 26-52.
Cao, Pei, and Sandy Irani. "Cost-Aware WWW Proxy Caching Algorithms."Usenix symposium on internet technologies and systems. Vol. 12. No. 97. 1997.


Book
Tanenbaum, Andrew S. Modern operating systems. Prentice Hall Press, 2007.

Chapter 2 Processes and Threads
Chapter 3 Memory Management
Chapter 4 File Systems
Chapter 5 Input/Output