Workshop Program

Most storage systems come with large set of parameters to directly or indirectly control a specific set of metrics that may include performance, energy, etc. Often, storage systems are deployed with default configurations, rendering them sub-optimal. Finding optimal configurations is difficult due to the numerous combinations of parameters and parameter sensitivity to workloads and deployed environments. Previous research on parameter optimization was either limited to narrow problems or not widely applicable to storage stack parameter optimization in general. Based on promising early results, we propose using meta-heuristic techniques such as genetic algorithms to efficiently find nearoptimal configurations for storage systems.

Modern flash devices, which perform updates ‘out of place’, require different optimization strategies than hard disks. The focus for flash devices is on optimizing data movement, rather than optimizing data placement. An understanding of the processes that cause data movement within a flash drive is crucial for analyzing and managing it.

While sequentiality on hard drives is easy to visualize, as is done by various defragmentation tools, data movement on flash is inherently dynamic. With the lack of suitable visualization tools, researchers and developers must rely on aggregated statistics and histograms from which the actual movement is derived. The complexity of this task increases with the complexity of state-of-the-art FTL production and research optimizations.

Adding visualization to existing research and analysis tools will greatly improve our understanding of modern, complex flash-based systems. We developed SSDPlayer, a graphical tool for visualizing the various processes that cause data movement on SSDs. We use SSDPlayer to demonstrate how visualization can help us shed light on the complex phenomena that cause data movement and expose new opportunities for optimization.

This paper presents a method to implement delta compression for metadata storage in flash memory. With the abundant temporal redundancy in metadata, it is very intuitive to expect flash-based metadata storage can significantly benefit from delta compression. However, straightforward realization of delta compression demands the storage of the original data and the deltas among different versions in different flash memory physical pages, which leads to significant overhead in terms of read/write latency and data management complexity. Through experiments with 20nm NAND flash memory chips, we observed that, when operating in SLC mode, flash memory page can be programmed in a progressive manner, i.e., different portion of the same SLC flash memory page can be programmed at different time. This motivates us to propose a simple design approach that can realize delta compression for metadata storage without latency and data management complexity overheads. The key idea is to allocate SLC-mode flash memory pages for metadata, and store the original data and all the subsequent deltas in the same physical page through progressive programming. Experimental results show that this approach can significantly reduce the metadata write traffic without any latency overhead.

Delta compression, a promising data reduction approach capable of finding the small differences (i.e., delta) among very similar files and chunks, is widely used for optimizing replicate synchronization, backup/archival storage, cache compression, etc. However, delta compression is costly because of its time-consuming word-matching operations for delta calculation. Our in-depth examination suggests that there exists strong word-content locality for delta compression, which means that contiguous duplicate words appear in approximately the same order in their similar versions. This observation motivates us to propose Edelta, a fast delta compression approach based on a word-enlarging process that exploits word-content locality. Specifically, Edelta will first tentatively find a matched (duplicate) word, and then greedily stretch the matched word boundary to find a likely much longer (enlarged) duplicate word. Hence, Edelta effectively reduces a potentially large number of the traditional time-consuming word-matching operations to a single word-enlarging operation, which significantly accelerates the delta compression process. Our evaluation based on two case studies shows that Edelta achieves an encoding speedup of 3X10X over the state-of-the-art Ddelta, Xdelta, and Zdelta approaches without noticeably sacrificing the compression ratio.

Current web infrastructure relies increasingly on distributed in-memory key-value stores such as memcached whereby typical x86-based implementations of TCP/IP compliant memcached yield limited performance scalability. FPGA-based data-flow architectures overcome and exceed every other published and fully compliant implementation in regards to throughput and provide scalability to 80Gbps, while offering much higher power efficiency and lower latency. However, value store capacity remains limited given the DRAM support in today’s devices.

In this paper, we present and quantify novel hybrid memory systems that combine conventional DRAMs and serial-attached flash to increase value store capacity to 40Terabytes with up to 200 million entries while providing access at 80Gbps. This is achieved by an object distribution based on size using different storage devices over DRAM and flash and data-flow based architectures using customized memory controllers that compensate for large variations in access latencies and bandwidths. We present measured experimental proofpoints, mathematically validate these concepts for published value size distributions from Facebook, Wikipedia, Twitter and Flickr and compare to existing solutions.

The long-expected convergence of High Performance Computing and Big Data Analytics is upon us. Unfortunately, the computing environments created for each workload are not necessarily conducive for the other. In this paper, we evaluate the ability of traditional high performance computing architectures to run big data analytics. We discover and describe limitations which prevent the seamless utilization of existing big data analytics tools and software. Specifically, we evaluate the effectiveness of distributed key-value stores for manipulating large data sets across tightly coupled parallel supercomputers. Although existing distributed key-value stores have proven highly effective in cloud environments, we find their performance on HPC clusters to be degraded. Accordingly, we have built an HPC specific key-value stored called the Multi-Dimensional Hierarchical Indexing Middleware (MDHIM). Using standard big data benchmarks we find that MDHIM performance more than triples that of Cassandra on HPC systems.

We are in the midst of an important shift to higher levels of abstraction than virtual machines. Kubernetes aims to simplify the deployment and management of services, including the construction of applications as sets of interacting but independent services. We explain some of the key concepts in Kubernetes and show how they work together to simplify evolution and scaling.

Eric Brewer is a vice president of infrastructure at Google. He pioneered the use of clusters of commodity servers for Internet services, based on his research at Berkeley. His “CAP Theorem” covers basic tradeoffs required in the design of distributed systems and followed from his work on a wide variety of systems, from live services, to caching and distribution services, to sensor networks. He is a member of the National Academy of Engineering, and winner of the ACM Infosys Foundation award for his work on large-scale services.

Deduplication is widely used to improve space efficiency in storage systems. While much attention has been paid to making the process of deduplication fast and scalable, the effectiveness of deduplication can vary dramatically depending on the data stored. We show that many file formats suffer from a fundamental design property that is incompatible with deduplication: they intersperse metadata with data in ways that result in otherwise identical data being different. We examine three models for improving deduplication in the presence of embedded metadata: deduplicationfriendly data formats, application-level post-processing, and format-aware deduplication. Working with realworld file formats and datasets, we find that by separating metadata from data, deduplication ratios are improved significantly—in some cases as dramatically as 5.6.

A recipe is metadata that describes the contents of a file as a sequence of blocks identified by their hash. Using recipes, one can rapidly compare the contents of two files without reading the files themselves. Unfortunately, recipes present a space/precision tradeoff: small block sizes will maximize the duplication that is discoverable, but large block sizes produce small recipes that can be compared more quickly. In this paper, we present Accordion, a toolset for the creation and use of multi-scale recipes—that is, recipes that include blocks at several different scales. We demonstrate two duplication-detection algorithms—one optimized for situations where lots of duplication is expected, and another for those where the existence of duplication is uncertain.

Cache replacement algorithms have focused on managing caches that are in the datapath. In datapath caches, every cache miss results in a cache update. Cache updates are expensive because they induce cache insertion and cache eviction overheads which can be detrimental to both cache performance and cache device lifetime. Nondatapath caches, such as host-side flash caches, allow the flexibility of not having to update the cache on each miss. We propose the multi-modal adaptive replacement cache (mARC), a new cache replacement algorithm that extends the adaptive replacement cache (ARC) algorithm for non-datapath caches. Our initial trace-driven simulation experiments suggest that mARC improves the cache performance over ARC while significantly reducing the number of cache updates for two sets of storage I/O workloads from MSR Cambridge and FIU.

In this paper we will present a simple model for Host- Managed Caveat-Scriptor, describe a simple FUSE-based file system for Host-Managed Caveat-Scriptor, construct and describe a file system aging tool and report initial performance comparisons between Strict-Append and Caveat-Scriptor. We will show the potential for Caveat-Scriptor to help limit heavy tail response times for shingled disks.

Web-scale applications are heavily reliant on memory cache systems such as Memcached to improve throughput and reduce user latency. Small performance improvements in these systems can result in large end-to-end gains, for example a marginal increase in hit rate of 1% can reduce the application layer latency by over 25%. Yet, surprisingly many of these systems use generic firstcome- first-serve designs with simple fixed size allocations that are oblivious to the application’s requirements. In this paper, we use detailed empirical measurements from a widely used caching service, Memcachier to show that these simple default policies can lead to significant performance penalties, in some cases increasing the number of cache misses by as much as 3x.

Motivated by these empirical analyses, we propose Dynacache, a cache controller that significantly improves the hit rate of web applications, by profiling applications and dynamically tailoring memory resources and eviction policies. We show that for certain applications in our real-world traces from Memcachier, Dynacache reduces the number of misses by more than 65% with a minimal overhead on the average request performance. We also show that Memcachier would need to more than double the number of Memcached servers in order to achieve the same reduction of misses that is achieved by Dynacache. In addition, Dynacache allows Memcached operators to better plan their resource allocation and manage server costs, by estimating the cost of cache hits as a function of memory.

The Internet of Things (IoT) represents a new class of applications that can benefit from cloud infrastructure. However, the current approach of directly connecting smart devices to the cloud has a number of disadvantages and is unlikely to keep up with either the growing speed of the IoT or the diverse needs of IoT applications.

In this paper we explore these disadvantages and argue that fundamental properties of the IoT prevent the current approach from scaling. What is missing is a wellarchitected system that extends the functionality of the cloud and provides seamless interplay among the heterogeneous components in the IoT space. We argue that raising the level of abstraction to a data-centric design—focused around the distribution, preservation and protection of information—provides a much better match to the IoT.We present early work on such a distributed platform, called the Global Data Plane (GDP), and discuss how it addresses the problems with the cloud-centric architecture.