TEA: A Traic-eicient Erasure-coded Archival Scheme for
In-memory Stores
Bin Xu
binxu@hust.edu.cn
Huazhong University of Sci.& Tech.
Wuhan, Hubei, China
Jianzhong Huang
∗
Qiang Cao
∗
Huazhong University of Sci.& Tech.
Wuhan, Hubei, China
Xiao Qin
xqin@auburn.edu
Auburn University
Auburn, AL 36849, USA
ABSTRACT
To achieve good trade-o between access performance and mem-
ory eciency, it is appropriate to adopt replication and erasure
coding to keep popular and unpopular in-memory datasets, re-
spectively. An issue of redundancy transition from replication to
erasure coding (a.k.a., erasure-coded archival) should be addressed
for unpopular in-memory datasets, since caching workloads exhibit
long-tail distributions and most in-memory data are unpopular.
In this paper, we propose an encoding-oriented replica placement
policy - ERP - by incorporating an interleaved declustering mecha-
nism, and design a trac-ecient erasure-coded archival schemes
-TEA - for ERP-powered in-memory stores. With ERP in place, TEA
embraces three salient features: (i) it alleviates cross-rack trac
raised by retrieving data-block replicas, (ii) it improves rack-level
load balancing by distributing replicas via load-aware primary-rack-
selection approach, and (iii) it mitigates block-relocation operations
launched to sustain rack-level fault-tolerance. The empirical results
show that TEA not only brings forth lower cross-rack trac than
four candidate encoding schemes, but also exhibits superb archival-
throughput and rack-level-balancing performance. In particular,
TEA accelerates archival throughput by at least 70.8%; and improves
rack-level load-balancing by a factor of more than 1.58x relative to
the four competitors.
CCS CONCEPTS
• Information systems →
Distributed storage;
• Computer sys-
tems organization → Re dundancy.
KEYWORDS
In-memory store, Erasure encoding, Replication, Archival
ACM Reference Format:
Bin Xu, Jianzhong Huang, Qiang Cao, and Xiao Qin. 2019. TEA: A Trac-
ecient Erasure-coded Archival Scheme for In-memory Stores. In 48th
International Conference on Parallel Processing (ICPP 2019), August 5–8, 2019,
Kyoto, Japan. ACM, New York, NY, USA, 10 pages. https://doi.org/10.1145/
3337821.3337826
∗
Jianzhong Huang (hjzh@hust.edu.cn) and Qiang Cao (caoqiang@hust.edu.cn) are the
joint corresponding authors.
Permission to make digital or hard copies of all or part of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for prot or commercial advantage and that copies bear this notice and the full citation
on the rst page. Copyrights for components of this work owned by others than ACM
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specic permission and/or a
fee. Request permissions from permissions@acm.org.
ICPP 2019, August 5–8, 2019, Kyoto, Japan
© 2019 Association for Computing Machinery.
ACM ISBN 978-1-4503-6295-5/19/08... $15.00
https://doi.org/10.1145/3337821.3337826
1 INTRODUCTION
1.1 Motivation
The following three aspects motivate us to delve in the development
of an erasure-coded archival scheme for in-memory stores.
Aspect #1
–low access latency in in-memory stores. We are in
an era of data-driven business world. For example, data-intensive
analytics has become indispensable since enterprises want to gain
insights to products, services and marketing strategies from in-
creasing volumes of data. Commonly, a data-intensive application
is supported by a cluster consisting of hundreds of nodes and peta-
bytes of data. It is a technology trend to constitute an in-memory
store upon the cluster to achieve low-latency performance. A tra-
ditional case is that Facebook leverages Memcached as a building
block to construct a distributed key-value store facilitating the
world’s largest social network [19].
Aspect #2
–demands for redundancy strategies. Since volatile
DRAM only maintains data while it is powered, existing in-memory
stores accomplish memory-level fault-tolerance by applying repli-
cation and/or erasure coding. Replication is a simple yet eective
redundancy scheme. For instance, Repcached [
15
] and Bigmem-
ory [
28
] keep two replicas in memory among nodes. Compared
to the replication, erasure coding achieves higher space eciency
dened as a ratio of user data to the combination of user data
and redundancy data [
12
]. Unsurprisingly, space-ecient erasure
codes are also adopted by in-memory stores, e.g.,
EC-cache
[
21
],
Cocytus [31], MemEC [30], and Ring [24].
Aspect #3
–necessity of erasure-coded archival. An analysis of
traces collected from Facebook’s Memcached deployment shows
that caching workloads exhibit long-tail distributions, in which a
small percentage of keys appeared in most of the requests whereas
most keys repeated only a handful of times [
3
]. Therefore, it is not
economical to employ a single redundancy scheme for the entire
in-memory data (i.e., metadata, key and value in in-memory key-
value stores) within the data lifetime. Nowadays, some key-value
stores (e.g., Memcached in Facebook [
19
], Ring [
24
]) adopt a hybrid
redundancy strategy, where replication is applied to popular data,
while erasure codes are employed for unpopular data.
Generally, newly-loaded data is kept in a replication manner to
support high access parallelism. Since most of the new data are
infrequently accessed, it is wise to encode unpopular data replicas
using erasure codes to achieve high space eciency. We refer to
such an encoding process as ‘erasure-coded archival’.
1.2 Challenges and Strategies
We face two challenges during the course of designing an erasure-
coded archival scheme for in-memory stores.
剩余9页未读，继续阅读
资源评论
