See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/313552454

Towards Scalable and Reliable In-Memory Storage System: A Case Study with
Redis

Conference Paper · August 2016

DOI: 10.1109/TrustCom.2016.0255

CITATIONS READS
37 7,699

5 authors, including:

Hongwei Wang
Stanford University
38 PUBLICATIONS 5,224 CITATIONS

SEE PROFILE

All content following this page was uploaded by Hongwei Wang on 02 September 2020.

The user has requested enhancement of the downloaded file.

 2016 IEEE TrustCom-BigDataSE-ISPA
TrustCom/BigDataSE/ISPA

Towards Scalable and Reliable In-Memory Storage

System: A Case Study with Redis
Shanshan Chen∗† , Xiaoxin Tang∗ , Hongwei Wang∗ , Han Zhao‡ and Minyi Guo∗
∗ Department of Computer Science and Engineering, Shanghai Jiao Tong University, China
† Schoolof Overseas Education, Nanjing University of Posts and Telecommunications, China
‡ School of Computer Science & Technology, Huazhong University of Science and Technology, China
Email: ∗ {moistcss, tang.xiaoxin, 77877156, myguo}@sjtu.edu.cn, ‡ [email protected]

Abstract—In recent years, in-memory key-value storage sys- systems do not have a big enough capacity for today’s Big
tems have become more and more popular in solving real-time Data challenge. Although key-value storage model, or non-
and interactive tasks. Compared with disks, memories have much relational database (or NoSQL, not only SQL), has made
higher throughput and lower latency which enables them to
process data requests with much higher performance. However, it easy to scale the storage systems out, they still face the
since memories have much smaller capacity than disks, how to challenges like single-node failure, data non-consistency, etc.
expand the capacity of in-memory storage system while maintain To overcome these limitations, the systems have to make
its high performance become a crucial problem. At the same time, tradeoffs in their design and implementation.
since data in memories are non-persistent, the data may be lost Meanwhile, since data in main memories are non-persistent,
when the system is down.
In this paper, we make a case study with Redis, which is
data may be lost during unexpected system crash, which
one popular in-memory key-value storage system. We find that makes the system unreliable. To overcome this problem, there
although the latest release of Redis support clustering so that data are several techniques that can be applied. For example, the
can be stored in distributed nodes to support a larger storage system can periodically save the data as image files, or save
capacity, its performance is limited by its decentralized design update logs onto disks to ensure data safety. However, disk
that clients usually need two connections to get their request
served. To make the system more scalable, we propose a Client-
operations may significantly hurt the performance. The system
side Key-to-Node Caching method that can help direct request can also use data replication which duplicates data on other
to the right service node. Experimental results show that by nodes to improve system reliability. Nevertheless, the data
applying this technique, it can significantly improve the system’s consistency issue between master and slave nodes could also
performance by near 2 times. cause performance degradation.
We also find that although Redis supports data replication In this paper, we make a case study with Redis[9], which
on slave nodes to ensure data safety, it still gets a chance of
losing a part of the data due to a weak consistency between is a very popular in-memory key-value storage system[1],
master and slave nodes that its defective order of data replication [2], [3], [5], [7], [8]. Although Redis can provide stable
and request reply may lead to losing data without notifying the performance as a single-node service, its clustering service
client. To make it more reliable, we propose a Master-slave Semi still faces the problems of low scalability and reliability. By
Synchronization method which utilizes TCP protocol to ensure adding more nodes to the clustering service, we expect the
the order of data replication and request reply so that when a
client receives an “OK” message, the corresponding data must system’s performance to be improved linearly. However due
have been replicated. With a significant improvement in data to a decentralized design, it may also hurt the performance
reliability, its performance overhead is limited within 5%. because of an inefficient data indexing mechanism. As in a
Index Terms—In-Memory, Key-Value, Storage System, Scala- distributed environment, node failure could happen quite easily
bility, Reliability, Key-to-Node Caching, Semi Synchronization. and the system has to take it into considerations carefully.
Yet we still find that the current design get a high chance
of losing data during system crash. This paper addresses the
I. I NTRODUCTION
above problems with the following novel contributions:
Due to the increasing capacity and high throughput of • We propose a Client-side Key-to-Node Caching method
main memory, in-memory computing has become a new which enables clients to cache the key-to-node mapping
trend for today’s Big Data processing. Especially in recent status. This can help direct data requests to the right
years, in-memory key-value storage systems have been widely service node and reduce the overhead caused by false
deployed in many real-time and interactive tasks, e.g., context- connections. Experimental results show that it can im-
aware peer classification[1], geographical feature analysis[2], prove the system’s throughput by up to 2 times;
program constraints analysis[3], [4], cloud-based evolutionary • We propose a Master-slave Semi Synchronization
algorithms[5], social graph analysis[6], presidential election method to ensure reliable data replication with limited
analysis[7], wireless communications[8], etc. overhead. This method can not only guarantee that no
However, due to the relatively smaller capacity of main data would be lost during system crash, but also can limit
memory compared with disks, single-node in-memory storage the performance overhead by no more than 5%;

2324-9013/16 $31.00 © 2016 IEEE 1661

1660
DOI 10.1109/TrustCom.2016.253
10.1109/TrustCom/BigDataSE/ISPA.2016.253
 

Fig. 1. Overview of a typical client-server structure for Redis distributed storage service.

This paper is organized as follows: Section II gives an A. Data Distribution Design of Redis
introduction to the background of Redis and explains our mo-
tivation in detail; Section III describes our proposed methods For a given distributed storage system, we need to first
and explains how we are able to improve system scalability solve how data are distributed on different nodes. Since Redis
and reliability; Section IV gives the experimental results of is a key-value storage system, the main problem becomes
our methods; Section V introduces the related work of this how to schedule different keys to nodes. To build a stable
paper; Finally, Section VI concludes this paper. and dynamically adjustable system, Redis uses a key-slot-node
mapping strategy to maintain the data distribution status.

II. BACKGROUND
node
mapping
According to the famous CAP theory[10], a system can Node 1
only hold two of the three properties at the same time:
slot slot 1
mapping
consistency, availability and partition-tolerance. Although a key hash hash slot 2
value Node 2
distributed design of a storage system is the key to its scalable
capacity, its performance scalability and data reliability are slot N
very challenging to handle properly. It is very important to
achieve a good balance between the CAP properties. But not Node C
until recently does Redis release its stable cluster version
(Redis 3.0 Beta), which shows how hard it is.
Fig. 2. A three stage mapping from key to node.
Fig. 1 gives a typical topology of a distributed Redis storage
service, in which we mainly focus on how the system can be
scaled out with good performance and how the system can Fig. 2 shows how the keys are mapped to each node. In the
ensure data safety. There are usually multiple machines that hash stage, for a given key, Redis will calculate its hash value.
are providing data storage services together, which are called In Redis, all hash values are evenly assigned to each slot and
“Node”. Each node may take certain amount of memory space there are 16382 slots in total. Then in the slot mapping stage,
on each machine and is responsible for storing parts of the we can find the corresponding slot for the key based on its
data. Different clients can visit these nodes to get and set (read hash value. In Redis, all slots can be dynamically assigned
and write) data independently. To ensure data safety, there are to different nodes. In this case, if any node is under heavy
also at least one slave node (two in the figure) for each master workloads, we can move parts of its slots to other nodes
node to replicate data so that when the master is down, the or even new nodes to improve system’s overall performance.
slave node can replace it to restore the service. We will give Thus in the third step, we can find the corresponding node of
a more detailed description in the following sub-sections. the given key based on the slot-node mapping status.

1661
1662
B. System Scalability Design of Redis disaster recovery and fast service restart since the compact
In addition to the data distribution status, there are other file can be transferred easily. It also brings less overhead
important info that needs to be maintained like number of during persistence since Redis can fork one child process to
nodes, their IP address and port numbers, current working do the job and the father process would never involve any
status, etc. These info can be stored on a central node of disk I/O operations. However, since Redis can not frequently
the cluster, which could simplify the design of the distributed do snapshot, it still get the chance of losing data after the last
system. But when this node is down or its performance is slow, snapshot.
the whole cluster may fall in trouble. The AOF persistence logs every write operation received
by the server. During restoring the service, these operations
will be played again. The main advantage of AOF over RDB
is that it is more flexible since the system can do logging
more frequently than snapshot. The disadvantage is that AOF
may brings more overhead since the main process needs to do
logging by itself. It also takes more space for logs and cost
longer time to restore the service.
Compared with data persistence on disks, data replication
gets the following advantages: first, since data is replicated on
another node, the crashed service can be restored very quickly
by simply replacing the master node with the slave node while
for data persistence it takes longer time to read data from disks
especially when the data size is big; second, data replication
mainly involves network I/O, which has advantages on latency
Fig. 3. A decentralized design for Redis by using Gossip protocol. and bandwidth over disks, especially for small and random
data read and write. However, data replication still faces the
To avoid this single-node failure issue, Redis takes a fully tradeoff between data reliability and performance since it will
decentralized design, which uses the Gossip protocol[11] to cost longer time to ensure that all data are fully replicated.
maintain these important info on all nodes. As shown in Fig. The current design of Redis takes an asynchronous replication
3, all nodes in the system are fully connected and know the strategy and we find that it still has the risk of losing data.
current state of the system. Every time when the system’s
status is changed, this new info will be propagated to every
node. Nodes will also randomly send PING messages to other D. Motivation
nodes and expect to receive PONG messages to prove that the
cluster is working correctly. If any node is found not working Based on the above introduction, we can find two major
properly, all other nodes will start a vote to use a slave node problems for Redis. One is caused by the decentralized design
to replace the crashed master node. that a client needs to take two connections to get its request
With this design, the system is highly reliable and clients served: one connection to ask which node the key belongs to
can connect to any of the master nodes for data storage service. and the other connection to send the request to the right node
When a master node receives a key-value request from a client, and get it served. If the client is lucky, it can get the request
it will check whether this key belongs to this node by checking served by using the first connection only if the key belongs
the key-slot-node mapping mentioned above. If yes, it will to the first node. However, when there are many nodes in the
process this request and return the results back to the client. cluster, the chance for the first node to own that key is quite
Otherwise, it will return a MOVED error which contains the low. In order to improve the performance, we need to find a
right node for this request. Then after receiving this error, the way to help the client so that it can have a better chance to
client will know which node it should send the request to. get the request served in the first connection.
The second problem is how to ensure that no data would
C. Data Reliability Design of Redis be lost without signicantly hurting the performance. AOF is a
Due to many possible failures in a distributed environment, candidate solution for this problem. However, it involves too
Redis has to ensure that the data would not be lost during node many disk I/O operations that can bring more performance
crash. There are mainly two ways to keep data safe in Redis: overhead and may take longer time to restore the service.
data persistence and data replication. Data persistence keeps Thus in this paper, we mainly consider data replication as a
data safe by writing the data onto disks while data replication possible solution for this problem. The current implementation
keeps data safe by replicating the data on other nodes. of Redis is a good start point since its master-slave synchro-
Redis supports two types of data persistence: RDB and nization method can partly ensure data safety. However, due
AOF. The RDB persistence performs point-in-time snapshots to performance consideration, it may still lose data during our
the data in Redis memory at specified intervals and put the test. We will try to find a way to modify the codes to achieve
compact file on disk. RDB is a good choice for data backups, our goal without making too many changes to Redis.

1662
1663
 III. D ESIGN AND I MPLEMENTATION the table to remember that slot “12345” belongs to “node3”
In this section, we will give details on how we solve in step 5; Finally, the client sends the request to “node3” to
the problems mentioned above. We propose two new de- gets it served.
signs, which are called Client-side Key-to-Node Caching Although it takes two connections for the client to get the
and Master-slave Semi Synchronization. We will show their request served for the first time, it only takes one connection
details and how they are implemented in the following sub- for all keys that belong to this slot to get served in the next time
sections. until this slot is moved to another node. The pseudocode for
the caching method is shown in Algorithm 1. Since network
A. Client-side Key-to-Node Caching communication takes most of the time for each request, our
Since each time when client send a key to a service node, the caching method is expected to improve the performance by
node will check whether this key belongs to it or not. If not, it up to 2 times while it only takes very little extra space and
will send a MOVED error back which could guide the client computation to do the caching job. Thus, this method is a
to the right node. Thus, if we can cache this mapping status lightweight but useful supplement to the decentralized design
after receiving this error, then next time this client should be of Redis.
able to find the service node correctly for all keys belong to
the same slot. B. Master-slave Semi Synchronization
In this paper, we mainly consider the problems of using
"

data replication to keep data safe. Different synchronization
"

strategies may have influences on the system performance and



!"
data reliability. Here we give an introduction to three possible
strategies.

%
+),


%
+),

!%
accept client’s send request to

request slave

&%
$
'&
!
!
Master Slave
Client
%
$"%
+),



Node Node
return reply to

!
"&%
(
!"
"$
$"%




*
!"
client

"!
%"


(a) Partial Synchronization

#%
##!
!"



accept client’s send request to
request slave

Fig. 4. A use case for client-side key-to-node caching. Master Slave

Client
Node Node
return reply to check replication
client
Fig. 4 shows how this method works. Initially, we set up a offset with master
(b) Full Synchronization
table which stores the slot-to-node mapping status. An initial
node is set as the default node for all slots. For a given accept client’s send request to
request slave
“key1”, the client calculates its hash value and then decide Master Slave
Client
which slot this key belongs to in step 1. Here let us assume it Node Node
return client’s
belongs to slot “12345”; then the client searches the table to reply

see which node this slot belongs to in step 2. Here the table (c) Semi Synchronization

shows it belongs to “node1”; Then the client sends the request

to “node1” in step 3; However, “node1” finds that this slot Fig. 5. Master-slave synchronization strategies.
actually belongs to “node3” and send back a MOVED error
to the client in step 4; the client receives this error and update As shown in Fig. 5(a), Redis currently uses the partial
synchronization strategy. For a given data write request from
the client in step ,
1 the master node processes the request
Algorithm 1 Pseudocode for client-side key-to-node caching.
immediately and then returns the reply back to client in step
Require: Node cache[16384]; .
2 After that, the master node sends the replicating request to
Ensure: reply the slave in step .
3 The advantage of this strategy is that its
slot = getSlotByKey(cmd); performance is higher since data service and data replication
node = cache[slot]; can be processed independently. The client can get the reply as
reply = send(cmd, node); soon as possible without being influenced by data replication.
if reply is a MOVED error then The disadvantage is that it may bring the risk of losing data.
extract slot and node from reply; For example, if the system crashes after step 2 but before step
cache[slot] = node; ,
3 the client would think that its request has been processed
reply = send(cmd, node); and stored properly but the truth is the request data has not
end if been replicated yet! In this case, this request data is lost.

1663
1664
 To avoid this problem, a full synchronization strategy shown TABLE I
H ARDWARE AND S OFTWARE C ONFIGURATIONS .
in Fig. 5(b) could ensure that when the client gets the reply,
the request data has already been properly replicated. Instead CPU Intel(R) Xeon(R) E5645 CPU 2 X 6 @ 2.40 GHz
of sending reply back to client immediately after the request
Memory 64 GB DDR3 @ 1333 MHz
is processed, master node sends the request to slave node in
Disk 3 x 1 TB SATA disk
step .
2 Then, the slave node would process this request and
check replication offset with master node in step . 3 If their Network Intel(R) PRO/1000 Network Connection @ 1 Gbps
offsets are not the same, it means there are still unprocessed OS CentOS 6.2
requests in slave node. The master node will wait until its
offset is the same as the slaves’. Finally, the master sends the
reply back to client in step .
4 With this strategy, if the system B. Client-side Key-to-Node Caching
crashes, the client would not receive any reply, in which case
client would be able to handle this error. However, due to a 
[
full synchronization between master and slave, the system’s 
performance would be significantly influenced.
To ensure data safety while minimize the performance

influence, we propose the semi synchronization strategy which
is shown in Fig. 5(c). Unlike the full synchronization strategy
which needs to check the synchronization status between

master and slave to ensure they are fully synchronized, semi

436
synchronization only ensures that all latest requests have been
sent to the slave nodes in step , 2 which is guaranteed by 
reliable TCP data transferring. When this is done, the master
would send the reply back to the client. The assumption behind
this strategy is that as long as all latest requests have been  RQHQRGH
received by slaves, we can treat them as having already been WZRQRGHV
WKUHHQRGHV
replicated properly since these requests have already been
successfully processed on the master node and it is just a 
      
matter of time for the slaves to process them. This strategy 1XPEHURI&OLHQWV

combines the advantages in performance and data reliability

of both partial and full synchronization strategy, which is why Fig. 6. System throughput of the original Redis cluster.
we call it semi synchronization.
The detailed implementation of semi synchronization strat- In this experiment, we set the read-to-write ratio as 9:1,
egy depends on the event processing framework of Redis which means there are 9 “get” queries and 1 “set” query
which is responsible for handling the time events and file among every 10 queries. Data replication is disabled in this
events in the system. We have reused many existing APIs and test. Fig. 6 shows the system throughput of the original Redis
added no more than 50 lines of codes to Redis. Due to space cluster. Here we build three clusters which contains one, two
limitation, we do not give the details on how it is implemented. and three nodes respectively. As we can find, there is no
performance improvement at all when the cluster contains
IV. E XPERIMENTAL R ESULTS more nodes. Meanwhile, the performance is even slightly
worse when using two or three nodes in the cluster, which
A. Test Environment shows a poor scalability in performance of the system. This
In our experiment, we use Redis 3.0.3 as a baseline for result is caused by the default setting of clients since each
performance evaluation. Our proposed methods are also im- client is set to connect to one default node at the beginning.
plemented based on this version of Redis. We use our own In this case, this default node becomes the bottleneck of the
benchmark implemented in C which is similar to YCSB (Ya- system.
hoo! Cloud Serving Benchmark)[12] to test the performance To avoid this problem, we apply our proposed Client-
of Redis and evaluate our proposed methods. side Key-to-Node Caching method, whose results are shown
The hardware and software configurations for each service in Fig. 7. As we can find, when there is one node in the
node are listed in Table I. During the experiment, we mainly cluster, there is no performance improvement compared with
use QPS (Queries per Second) to evaluate the throughput. the original Redis cluster. This is because in this case all
Here, QPS represents the average number of queries processed data belongs to the same node which makes the caching
by the system in each second. We set the length of each query method meaningless. However, when there are more nodes
as 100 bytes and set each client to send 10,000 queries to in the system, the performance improvement becomes quite
the server node. Then, we observe how the performance is significant. For example, the throughput with two nodes is
changed when the number of clients vary from 1 to 512. almost 1.7 times over that with one node after using more

1664
1665
  
[ [
 






436

436


 RQHQRGH
WZRQRGHV SDUWLDOV\QF

WKUHHQRGHV VHPLV\QF
IXOOV\QF

       
1XPEHURI&OLHQWV       
1XPEHURI&OLHQWV

Fig. 7. System throughput of Redis cluster after applying client-side caching.

Fig. 8. System throughput of Redis with different synchronization strategies.

than 64 clients. When there are three nodes in the cluster, the
throughput becomes 2 times over that with one node. Fig. 8 gives the system throughput results with different
This result shows our caching method can improve system synchronization strategies. Compared with the original syn-
performance not only by reducing connection times but also chronization strategy used in Redis (partial sync), our proposed
by improving the scalability of the system since it can avoid semi synchronization achieves a very similar performance.
the single-node bottleneck problem. Notice that when using However for full synchronization, its throughput is almost
more than 128 clients, the system’s throughput becomes flat. reduced by half. Fig. 9 further gives the performance ratio of
This is due to the limitation that currently we put all clients on the two synchronization strategies over partial synchronization.
one node. Thus, the network I/O of the client node becomes As we can find, semi synchronization can limit its overhead
the bottleneck. In our future work we will try to distribute the within 5%, which is much better than that of full synchro-
clients to different nodes to avoid this problem. nization, i.e. 50%. These results have proved that our semi
synchronization can ensure data safety with a very limited
C. Master-slave Semi Synchronization performance overhead.

In order to show that our Master-slave Semi Synchroniza-

tion method is able to ensure data safety with limited overhead, 
we also implement the full synchronization strategy to make a
comparison. During the test, we set read-to-write ratio as 0:10,

which means all queries are “set” operations. In this worst case
VHPLV\QF
scenario, we should be able to test the system’s reliability to IXOOV\QF
the limit. We let the system to have one master node and two 
3HUIRUPDQFH5DWLR

slave nodes, as it is a common practice and the possibility for

all three nodes to crash is very small. 
To test whether the synchronization strategies are able to
ensure data safety, we set up an experiment as follows: at 
the beginning we use 50 clients to continuously send “set”
queries to the master node; then in the middle of the test, we

use Linux’s “kill” command to stop master node’s process to
simulate system crash; once the clients find that the master
node is down due to the failed TCP connection, they will 
      
connect to the slave nodes to check whether the previously 1XPEHURI&OLHQWV
processed queries have been correctly replicated or not by
comparing their values. We find that both full synchronization Fig. 9. Performance ratio of semi and full synchronization over partial
and semi synchronization have passed the test but partial synchronization.
synchronization has failed, which proves our previous analysis.

1665
1666
 V. R ELATED W ORK Masstree[27] uses logging and check pointing with SSDs to
A. In-memory Storage Survey ensure system consistency and durability.
There are several survey papers that readers can refer to
E. Multicore and Manycore In-memory Store
to have an overview of in-memory storage systems. Tan et
al.[13] have summarized the primary challenges and potential Masstree[27] is a fast key-value database designed for SMP
solutions from both software and hardware perspectives for in- machines. It uses optimistic concurrency control which is a
memory databases. Zhang et al.[14] have provided a thorough read-copy-update-like technique for lookup and local locking
review of a wide range of in-memory data management, for updates. MICA[28] takes a holistic approach for multicore
processing proposals, systems and important technology in system that encompasses all aspects of request handling,
memory management. Cattell[15] have examined a number including parallel data access, network request handling, and
of SQL and NoSQL data stores on multiple dimensions. data structure design, which provide high throughput over a
Carlson[9] gives a detailed introduction on how to use Redis. variety of mixed read and write workloads. Berezecki et al.[29]
shows that the throughput, response time, and power consump-
B. System Analysis
tion of a high-core-count processor operating at a low clock
System analysis is also very important for in-memory rate and very low power consumption can perform well when
key-value storage studies. Atikoglu et al.[16] have collected compared to a platform using faster but fewer commodity
detailed traces from Facebook’s Memcached deployment and cores. Mega-KV[30] and MemcachedGPU[31] are two GPU-
given a detailed analysis on many characteristics of these based high performance KVS systems. MASCOT[32] uses
caching workload. Cooper et al.[12] present the Yahoo! Cloud both CPU memory extended by SSDs and GPU memory as
Serving Benchmark (YCSB) framework with the goal of facili- cache to accelerate SVM cross-validation problem and it also
tating performance comparisons of the new generation of cloud uses a caching strategy well-suited for its storage framework.
data serving systems. Zhang et al.[17] analyze the performance With the support of these high performance processors, it
of three in-memory systems including Memcached, Redis and should be interesting to see how to maintain a good scalability
Spark. and reliability for these systems.
C. Optimizations for Performance
VI. C ONCLUSIONS
Performance design and optimization is one key to improve
throughput for all these systems. A strategy[18] is imple- In this paper, we make a case study with Redis, which is
mented in Redis that epoll system call can be invoked to one popular in-memory key-value storage system widely used
inform the kernel of the interest events in a manner adaptive in academic research and enterprise environment. Despite its
to the current network load so that epoll system calls can be success in providing single-node service, we find two major
reduced and the events can be efficiently delivered. Thongpr- problems in its cluster deployment. The first one is caused
asit et al.[19] proposes a user-space TCP/IP stack that works by its decentralized design that a client usually needs two
on top of Intel DPDK for high performance KVS systems. connections to get its request served. To avoid this problem,
Succinct[20] enables efficient queries directly on a compressed we propose a lightweight Client-side Key-to-Node Caching
representation of input data and natively supports a wide method that can help the client to find the right node to
range of queries. Zing Database[21] is presented as a high- connect to. Our experimental results show that this method has
performance persistent key-value store designed for optimizing made Redis more scalable and can improve its performance
reading and writing operations. Pilaf[22] is designed to take by up to 2 times. The second problem is caused by Redis’s
advantage of RDMA (Remote Direct Memory Access) to partial synchronization strategy which has the risk of losing
achieve high performance with low CPU overhead. Li et data during system crash. To avoid this problem, we propose
al.[23] even seeks for architecting solutions for high perfor- a Master-slave Semi Synchronization method that can ensure
mance and efficient KVS platforms. HV-tree[24] uses a novel data safety with a limited overhead less than 5%.
index structure that contains nodes of different sizes optimized
for a level of memory hierarchy. It can dynamically adjust the VII. ACKNOWLEDGMENT
node size to automatically exploit the best performance of all
levels of different storage systems. The authors would like to thank the anonymous reviewers
for their valuable comments. This work is partially sponsored
D. Data Reliability by the National Basic Research 973 Program of China (No.
HyperDex[25] employs a novel technique called value- 2015CB352403), the National Natural Science Foundation
dependent chaining and additional replication to provide of China (NSFC) (No. 61261160502, No. 61272099, No.
strong consistency and fault tolerance of objects in the pres- 61572263, No. 61272084), the Program for Changjiang Schol-
ence of concurrent updates. In ZHT[26] the primary replica ars and Innovative Research Team in University (IRT1158,
and secondary replica are strongly consistent while other repli- PCSIRT), the Scientific Innovation Act of STCSM (No.
cas are asynchronously updated after the secondary replica is 13511504200), and the EU FP7 CLIMBER project (No.
complete, causing ZHT to follow a weak consistency model. PIRSES-GA-2012-318939).

1666
1667
 R EFERENCES [18] X. Wu, X. Long, and L. Wang, “Optimizing event polling for network-
intensive applications: A case study on redis,” in Parallel and Distributed
Systems (ICPADS), 2013 International Conference on, Dec 2013, pp.
[1] M. Bardac, G. Milescu, and A. M. Florea, “Deploying a high-
687–692.
performance context-aware peer classification engine,” in The Sev-
[19] S. Thongprasit, V. Visoottiviseth, and R. Takano, “Toward fast
enth International Conference on Networking and Services-ICNS2011,
and scalable key-value stores based on user space tcp/ip stack,”
Venice/Mestre, Italy, 2011, pp. 268–273.
in Proceedings of the Asian Internet Engineering Conference, ser.
[2] H. Yu, Y. Liu, C. Tian, L. Liu, M. Liu, and Y. Gao, “A cache framework
AINTEC ’15. New York, NY, USA: ACM, 2015, pp. 40–47. [Online].
for geographical feature store,” in Geoinformatics (GEOINFORMAT-
Available: http://doi.acm.org/10.1145/2837030.2837036
ICS), 2012 20th International Conference on, June 2012, pp. 1–4.
[20] R. Agarwal, A. Khandelwal, and I. Stoica, “Succinct: Enabling
[3] W. Visser, J. Geldenhuys, and M. B. Dwyer, “Green: Reducing, queries on compressed data,” in 12th USENIX Symposium
reusing and recycling constraints in program analysis,” in Proceedings on Networked Systems Design and Implementation (NSDI 15).
of the ACM SIGSOFT 20th International Symposium on the Oakland, CA: USENIX Association, May 2015, pp. 337–350. [On-
Foundations of Software Engineering, ser. FSE ’12. New York, line]. Available: https://www.usenix.org/conference/nsdi15/technical-
NY, USA: ACM, 2012, pp. 58:1–58:11. [Online]. Available: sessions/presentation/agarwal
http://doi.acm.org/10.1145/2393596.2393665 [21] T. Nguyen and M. Nguyen, “Zing database: high-performance key-
[4] X. Jia, C. Ghezzi, and S. Ying, “Enhancing reuse of constraint solutions value store for large-scale storage service,” Vietnam Journal of
to improve symbolic execution,” CoRR, vol. abs/1501.07174, 2015. Computer Science, vol. 2, no. 1, pp. 13–23, 2015. [Online]. Available:
[Online]. Available: http://arxiv.org/abs/1501.07174 http://dx.doi.org/10.1007/s40595-014-0027-4
[5] M. Garcia-Valdez, A. Mancilla, L. Trujillo, J.-J. Merelo, and [22] C. Mitchell, Y. Geng, and J. Li, “Using one-sided rdma reads to build
F. Fernandez-de Vega, “Is there a free lunch for cloud-based evolutionary a fast, cpu-efficient key-value store.” in USENIX Annual Technical
algorithms?” in Evolutionary Computation (CEC), 2013 IEEE Congress Conference, 2013, pp. 103–114.
on, June 2013, pp. 1255–1262. [23] S. Li, H. Lim, V. W. Lee, J. H. Ahn, A. Kalia, M. Kaminsky,
[6] N. Bronson, Z. Amsden, G. Cabrera, P. Chakka, P. Dimov, H. Ding, D. G. Andersen, O. Seongil, S. Lee, and P. Dubey, “Architecting
J. Ferris, A. Giardullo, S. Kulkarni, H. Li, M. Marchukov, D. Petrov, to achieve a billion requests per second throughput on a single
L. Puzar, Y. J. Song, and V. Venkataramani, “Tao: Facebook’s key-value store server platform,” in Proceedings of the 42Nd Annual
distributed data store for the social graph,” in Proceedings of the 2013 International Symposium on Computer Architecture, ser. ISCA ’15.
USENIX Conference on Annual Technical Conference, ser. USENIX New York, NY, USA: ACM, 2015, pp. 476–488. [Online]. Available:
ATC’13. Berkeley, CA, USA: USENIX Association, 2013, pp. 49–60. http://doi.acm.org/10.1145/2749469.2750416
[Online]. Available: http://dl.acm.org/citation.cfm?id=2535461.2535468 [24] R. Zhang and M. Stradling, “The hv-tree: A memory hierarchy aware
[7] M. Song, M. C. Kim, and Y. K. Jeong, “Analyzing the political landscape version index,” Proc. VLDB Endow., vol. 3, no. 1-2, pp. 397–408, Sep.
of 2012 korean presidential election in twitter,” Intelligent Systems, 2010. [Online]. Available: http://dx.doi.org/10.14778/1920841.1920894
IEEE, vol. 29, no. 2, pp. 18–26, Mar 2014. [25] R. Escriva, B. Wong, and E. G. Sirer, “Hyperdex: A distributed,
[8] Z. Ji, I. Ganchev, M. O’Droma, and T. Ding, “A distributed redis frame- searchable key-value store,” SIGCOMM Comput. Commun. Rev.,
work for use in the ucww,” in Cyber-Enabled Distributed Computing vol. 42, no. 4, pp. 25–36, Aug 2012. [Online]. Available:
and Knowledge Discovery (CyberC), 2014 International Conference on, http://doi.acm.org/10.1145/2377677.2377681
Oct 2014, pp. 241–244. [26] T. Li, X. Zhou, K. Brandstatter, D. Zhao, K. Wang, A. Rajendran,
[9] J. L. Carlson, Redis in Action. Manning Publications Co., 2013. Z. Zhang, and I. Raicu, “Zht: A light-weight reliable persistent dynamic
[10] S. Gilbert and N. Lynch, “Brewer’s conjecture and the feasibility scalable zero-hop distributed hash table,” in Parallel Distributed Pro-
of consistent, available, partition-tolerant web services,” SIGACT cessing (IPDPS), 2013 IEEE 27th International Symposium on, May
News, vol. 33, no. 2, pp. 51–59, Jun. 2002. [Online]. Available: 2013, pp. 775–787.
http://doi.acm.org/10.1145/564585.564601 [27] Y. Mao, E. Kohler, and R. T. Morris, “Cache craftiness for
[11] A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, fast multicore key-value storage,” in Proceedings of the 7th ACM
H. Sturgis, D. Swinehart, and D. Terry, “Epidemic algorithms for European Conference on Computer Systems, ser. EuroSys ’12. New
replicated database maintenance,” in Proceedings of the Sixth Annual York, NY, USA: ACM, 2012, pp. 183–196. [Online]. Available:
ACM Symposium on Principles of Distributed Computing, ser. PODC http://doi.acm.org/10.1145/2168836.2168855
’87. New York, NY, USA: ACM, 1987, pp. 1–12. [Online]. Available: [28] H. Lim, D. Han, D. G. Andersen, and M. Kaminsky, “Mica: A holistic
http://doi.acm.org/10.1145/41840.41841 approach to fast in-memory key-value storage,” in 11th USENIX
[12] B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears, Symposium on Networked Systems Design and Implementation (NSDI
“Benchmarking cloud serving systems with ycsb,” in Proceedings 14). Seattle, WA: USENIX Association, Apr 2014, pp. 429–444. [On-
of the 1st ACM Symposium on Cloud Computing, ser. SoCC ’10. line]. Available: https://www.usenix.org/conference/nsdi14/technical-
New York, NY, USA: ACM, 2010, pp. 143–154. [Online]. Available: sessions/presentation/lim
http://doi.acm.org/10.1145/1807128.1807152 [29] M. Berezecki, E. Frachtenberg, M. Paleczny, and K. Steele, “Many-
[13] K.-L. Tan, Q. Cai, B. C. Ooi, W.-F. Wong, C. Yao, and H. Zhang, core key-value store,” in Green Computing Conference and Workshops
“In-memory databases: Challenges and opportunities from software and (IGCC), 2011 International, July 2011, pp. 1–8.
hardware perspectives,” SIGMOD Rec., vol. 44, no. 2, pp. 35–40, Aug. [30] K. Zhang, K. Wang, Y. Yuan, L. Guo, R. Lee, and X. Zhang, “Mega-kv:
2015. [Online]. Available: http://doi.acm.org/10.1145/2814710.2814717 A case for gpus to maximize the throughput of in-memory key-value
[14] H. Zhang, G. Chen, B. C. Ooi, K.-L. Tan, and M. Zhang, “In-memory stores,” Proc. VLDB Endow., vol. 8, no. 11, pp. 1226–1237, Jul. 2015.
big data management and processing: A survey,” Knowledge and Data [Online]. Available: http://dx.doi.org/10.14778/2809974.2809984
Engineering, IEEE Transactions on, vol. 27, no. 7, pp. 1920–1948, July [31] T. H. Hetherington, M. O’Connor, and T. M. Aamodt, “Memcachedgpu:
2015. Scaling-up scale-out key-value stores,” in Proceedings of the Sixth
[15] R. Cattell, “Scalable sql and nosql data stores,” SIGMOD Rec., ACM Symposium on Cloud Computing, ser. SoCC ’15. New
vol. 39, no. 4, pp. 12–27, May 2011. [Online]. Available: York, NY, USA: ACM, 2015, pp. 43–57. [Online]. Available:
http://doi.acm.org/10.1145/1978915.1978919 http://doi.acm.org/10.1145/2806777.2806836
[16] B. Atikoglu, Y. Xu, E. Frachtenberg, S. Jiang, and M. Paleczny, [32] Z. Wen, R. Zhang, K. Ramamohanarao, J. Qi, and K. Taylor, “Mascot:
“Workload analysis of a large-scale key-value store,” in Proceedings Fast and highly scalable svm cross-validation using gpus and ssds,” in
of the 12th ACM SIGMETRICS/PERFORMANCE Joint International 2014 IEEE International Conference on Data Mining, Dec 2014, pp.
Conference on Measurement and Modeling of Computer Systems, ser. 580–589.
SIGMETRICS ’12. New York, NY, USA: ACM, 2012, pp. 53–64.
[Online]. Available: http://doi.acm.org/10.1145/2254756.2254766
[17] H. Zhang, B. M. Tudor, G. Chen, and B. C. Ooi, “Efficient
in-memory data management: An analysis,” Proc. VLDB Endow.,
vol. 7, no. 10, pp. 833–836, Jun. 2014. [Online]. Available:
http://dx.doi.org/10.14778/2732951.2732956

1667
1668

View publication stats