Optimizing Flash-based Key-value Cache Systems
Zhaoyan Shen
†
Feng Chen
‡
Yichen Jia
‡
Zili Shao
†
†
Department of Computing
‡
Computer Science & Engineering
Hong Kong Polytechnic University Louisiana State University
Abstract
Flash-based key-value cache systems, such as Face-
book’s McDipper [1] and Twitter’s Fatcache [2], pro-
vide a cost-efficient solution for high-speed key-value
caching. These cache solutions typically take commer-
cial SSDs and adopt a Memcached-like scheme to store
and manage key-value pairs in flash. Such a practice,
though simple, is inefficient. We advocate to recon-
sider the hardware/software architecture design by di-
rectly opening device-level details to key-value cache
systems. This co-design approach can effectively bridge
the semantic gap and closely connect the two layers to-
gether. Leveraging the domain knowledge of key-value
caches and the unique device-level properties, we can
maximize the efficiency of a key-value cache system on
flash devices while minimizing its weakness. We are im-
plementing a prototype based on the Open-channel SSD
hardware platform. Our preliminary experiments show
very promising results.
1 Introduction
High-speed key-value caches, such as Memcached and
Redis, are the “first line of defense” in today’s low-
latency Internet services. Traditionally, these in-memory
key-value caches heavily rely on large amount of expen-
sive and power-hungry DRAM. In order to lower the To-
tal Cost of Ownership (TCO), a more cost-efficient alter-
native, flash-based key-value cache, has recently raised a
high interest in the industry [1, 2]. Facebook, for exam-
ple, deploys a flash-based Memcached-compatible key-
value cache system, called McDipper [1]. It is reported
that McDipper allows Facebook to reduce the number of
deployed servers by as much as 90% while still deliver-
ing more than 90% “get responses” with sub-millisecond
latencies [3]. Twitter also has a similar flash-based key-
value cache solution, called Fatcache [2].
Typically, these flash-based key-value cache sys-
tems directly use commercial flash SSDs and adopt a
Memcached-likescheme to manage key-value cache data
in flash, such as organizing key-values into slabs of dif-
ferent size classes, and using in-memory hash table to
maintain the key-to-value mapping, etc. Such a design,
though simple, disregards an important fact – The key-
value cache system and the underlying flash storage both
have very unique properties. Simply treating the flash
SSD as a faster storage and the key-value cache as a
regular application not only fails to exploit various op-
timization opportunities but also raises several critical
problems, namely redundant mapping, double garbage
collection, and over-overprovisioning. In this study, we
advocate to reconsider the current software/hardware ar-
chitecture for designing an efficient key-value cache sys-
tem, highly optimized for flash.
2 Background and Motivation
2.1 Flash-based key-value caches
The existing flash-based key-value cache system design
is fairly similar to its in-memory counterpart – both use
a slab-based space management. Here we use Twitter’s
Fatcache [2] as an example for explanation:
The flash SSD space is first segmented into slabs.
Each slab is often of several Megabytes and further di-
vided into an array of slots (a.k.a. chunks) of equal size.
Each slot stores a “value” item. Slabs are logically orga-
nized into different slab classes based on the slot sizes.
An incoming value item is stored in a slab whose slot size
is the best fit of its size. For quick accesses, a hash map-
ping table is maintained in memory to map the keys to
the slabs that contain the corresponding values. Query-
ing a key-value pair (get) is accomplished by searching
the in-memory hash table and loading the correspond-
ing slab block from flash into memory. Updating a key-
value pair (set) is realized by writing the updated value
to a new location and updating the mapping table entry.
Deleting a key-value pair (delete) simply removes the
mapping from the hash table. The deleted or obsolete
value items are left for garbage collection (GC) later. The
current design has three critical problems, which have
motivated us to perform this study.
2.2 Critical Issues
• Problem 1: Redundant mapping. Modern flash
SSDs implement a complex Flash Translation Layer
(FTL) in the firmware. A key function of FTL is to trans-
late Logical Block Addresses (LBA) to Physical Flash
Memory Pages. Although a variety of mapping schemes
exist [8], for performance reasons, high-end SSDs often
adopt page-level mapping for a fine-grained logical-to-
physical address translation. As a result, for a 1TB SSD
with a 4KB page size, a page-level mapping table could
be as large as 1GB. Integrating such a large DRAM on