Parity-Only Caching for Robust Straggler Tolerance in Large-Scale Storage Systems
P
a
r
i
t
y
-
O
n
l
y
C
a
c
h
i
n
g
f
o
r
R
o
b
u
s
t
S
t
r
a
g
g
l
e
r
T
o
l
e
r
a
n
c
e
M
i
Z
h
a
n
g
,
Q
i
u
p
i
n
g
W
a
n
g
,
Z
h
i
r
o
n
g
S
h
e
n
,
P
a
t
r
i
c
k
P
.
C
.
L
e
e
The Chinese University of Hong Kong
MSST 2019
B
a
c
k
g
r
o
u
n
d
S
t
r
a
g
g
l
e
r
s
e
x
i
s
t
i
n
l
a
r
g
e
-
s
c
a
l
e
s
t
o
r
a
g
e
s
y
s
t
e
m
s
•
Nodes operate with slow performance
•
Also known as
gray failures
[Huang, HotOS’17]
or
fail-slow failures
[Gunawi, FAST’16]
Stragglers introduce latency variation
[Dean, Comm.’13]
•
Long tail in latency distribution
Hard to pinpoint stragglers
[Huang, HotOS’17; Gunawi, FAST’16]
•
Varying root causes
•
Long time to detect
2
B
a
c
k
g
r
o
u
n
d
C
a
c
h
i
n
g
a
c
c
e
s
s
e
d
d
a
t
a
t
o
b
y
p
a
s
s
s
t
r
a
g
g
l
e
r
s
•
Cache space is limited
•
Only caching popular data inevitably hits stragglers
S
e
l
e
c
t
i
v
e
r
e
p
l
i
c
a
t
i
o
n
c
r
e
a
t
e
s
m
o
r
e
r
e
p
l
i
c
a
s
f
o
r
h
o
t
d
a
t
a
•
High redundancy overhead
•
Data popularity can change sharply
[Huang, HotNets’14]
3
E
r
a
s
u
r
e
C
o
d
i
n
g
4
O
u
r
C
o
n
t
r
i
b
u
t
i
o
n
s
Conduct mathematical analysis
D
e
s
i
g
n
P
O
C
a
c
h
e
,
a
p
a
r
i
t
y
-
o
n
l
y
c
a
c
h
i
n
g
s
c
h
e
m
e
f
o
r
r
o
b
u
s
t
s
t
r
a
g
g
l
e
r
t
o
l
e
r
a
n
c
e
•
Mitigate coding overhead via two mechanisms
•
Straggler-aware cache algorithm
Implement POCache atop Hadoop 3.1 HDFS
Evaluate POCache on a local cluster and Amazon EC2
•
Compare POCache with hedge reads and selective replication
5
M
a
t
h
e
m
a
t
i
c
a
l
A
n
a
l
y
s
i
s
Retrieve data from 𝑘 storage nodes
6
…
client
𝑘
data nodes
𝑐 cache nodes
•
Assume every node has a probability of 0.5% to become a straggler
•
What is the
probability of hitting a straggler
for a read request?
M
a
t
h
e
m
a
t
i
c
a
l
A
n
a
l
y
s
i
s
7
M
a
t
h
e
m
a
t
i
c
a
l
A
n
a
l
y
s
i
s
8
M
a
i
n
F
i
n
d
i
n
g
s
Caching parity blocks is more effective than caching data
blocks to bypass stragglers
Caching
only one parity block
can effectively eliminate the
impact of stragglers
Even with slowdown of cache nodes, caching parity blocks still
maintains straggler tolerance
9
C
h
a
l
l
e
n
g
e
s
Large encoding/decoding overhead
•
Decoding time takes about 30% of read time
[Rashmi, OSDI ’16]
•
Degrade normal read/write performance
What parity blocks to cache?
•
Manage cache space with considering stragglers
Can we support general deployment?
•
Support general storage systems and protocols
•
Support upper-layer applications
10
P
O
C
a
c
h
e
D
e
s
i
g
n
Block slicing
11
data blocks
parity block
…
subblock
substripe
D
0
D
1
D
k-1
C
0
•
Slice blocks into smaller-size subblocks
•
Cache parity subblocks
rather than the whole block
•
Parallelize coding across different substripes
•
Pipeline the process of caching parity blocks
P
O
C
a
c
h
e
D
e
s
i
g
n
Incremental encoding
12
C
0
’
C
0
’’
C
0
’’’’
C
0
…
data subblocks
Parity subblock
…
D
1
D
k-1
C
0
D
0
•
Addition operations are associative in a linear combination
•
Compute parity subblocks one by one incrementally
P
O
C
a
c
h
e
D
e
s
i
g
n
How to minimize straggler hit ratio?
•
Avoid accessing stragglers
•
Consider file popularity
Straggler-aware cache algorithm
•
Admit
caching parities for
blocks on stragglers
•
Collect each node’s
service rate
•
Identify stragglers according to
three-sigma rule
•
Compose a
straggler list
•
Evict
least-recently-accessed files
•
75% of re-accesses occur within 6 hours
[Chen, VLDB’12]
Details referred to the paper
13
I
m
p
l
e
m
e
n
t
a
t
i
o
n
Implement POCache on Hadoop 3.1 HDFS
•
Use Redis to build cache nodes
•
Add Manager on NameNode for cache management
•
Modify HDFS client
14
…
client
…
parity
Architecture of POCache
data
DataNode
Cache Node
E
v
a
l
u
a
t
i
o
n
S
e
t
u
p
Local cluster
•
15 commodity machines
•
Intel core i5, 16 GiB RAM, 1 TiB SATA disk
•
10 Gbps Ethernet switch
•
Employ benchmark tool
DFS-Perf
•
Inject stragglers by running Linux
stress
•
64-MiB block, 256-MiB file (4 blocks) by default
Amazon EC2
•
30 m5.large instances, 2 m5.2xlarge instances
•
Magnetic storage
•
5 Gbps network bandwidth
15
E
v
a
l
u
a
t
i
o
n
R
e
s
u
l
t
s
Effectiveness of block slicing
•
Cache one parity block for a file
•
Lowest latency when subblock is of 1 MiB
16
E
v
a
l
u
a
t
i
o
n
R
e
s
u
l
t
s
Single-client reads
•
Read mechanisms
•
Vanilla, read sequentially
•
HR, hedged read
•
PR, read blocks in parallel
•
Evaluate different file sizes
•
POCache reduces the
latency with straggler to the
latency in normal case
17
E
v
a
l
u
a
t
i
o
n
R
e
s
u
l
t
s
Multi-client reads
•
Read mechanisms in comparison
•
Vanilla, read blocks sequentially
•
HR, hedged read
•
SR, cache popular data blocks
•
Evaluate with 4, 8, 12 clients
•
POCache achieves low mean and
tail latencies
18
With one straggler
E
v
a
l
u
a
t
i
o
n
R
e
s
u
l
t
s
Cache efficiency of Straggler-aware cache algorithm (SAC)
19
Straggler hit ratio under different cache sizes
Latencies under different cache sizes
E
v
a
l
u
a
t
i
o
n
R
e
s
u
l
t
s
Experiments on Amazon EC2
•
Read mechanisms
•
Vanilla, read sequentially
•
HR, hedged read
•
PR, read blocks in parallel
•
Stragglers naturally appear in cloud
•
POCache achieves lowest latency
among all four read policies
20
C
o
n
c
l
u
s
i
o
n
P
r
e
s
e
n
t
P
O
C
a
c
h
e
,
a
p
a
r
i
t
y
-
o
n
l
y
c
a
c
h
i
n
g
d
e
s
i
g
n
f
o
r
r
o
b
u
s
t
s
t
r
a
g
g
l
e
r
t
o
l
e
r
a
n
c
e
•
Minimize coding overhead
•
Straggler-aware cache algorithm
•
Preserve original workflow and performance
Implement POCache on Hadoop 3.1 HDFS
Conduct experiments on a local cluster and Amazon EC2
Source code
•
h
t
t
p
:
/
/
a
d
s
l
a
b
.
c
s
e
.
c
u
h
k
.
e
d
u
.
h
k
/
s
o
f
t
w
a
r
e
/
p
o
c
a
c
h
e
21
Thank you!
Q&A
22
B
a
c
k
g
r
o
u
n
d
a
n
d
M
o
t
i
v
a
t
i
o
n
Stragglers affect both data layouts
•
Contiguous layout
•
Striping layout
23
Contiguous layout
Striping layout
N
u
m
e
r
i
c
a
l
A
n
a
l
y
s
i
s
Probability of hitting straggler
24
M
o
t
i
v
a
t
i
o
n
Stragglers slow down read request
•
R
e
a
d
a
f
i
l
e
f
,
c
o
n
s
i
s
t
i
n
g
o
f
k
b
l
o
c
k
s
r
e
s
i
d
i
n
g
o
n
k
n
o
d
e
s
•
E
a
c
h
n
o
d
e
b
e
h
a
v
e
s
a
b
n
o
r
m
a
l
l
y
w
i
t
h
p
r
o
b
a
b
i
l
i
t
y
p
s
25
client
k
M
a
t
h
e
m
a
t
i
c
a
l
A
n
a
l
y
s
i
s
Two caching strategies
•
Data-only cache
•
c
d
a
t
a
b
l
o
c
k
s
o
u
t
o
f
k
d
a
t
a
b
l
o
c
k
s
•
Parity-only cache
•
c
p
a
r
i
t
y
b
l
o
c
k
s
g
e
n
e
r
a
t
e
d
f
r
o
m
k
d
a
t
a
b
l
o
c
k
s
26
…
client
k
I
m
p
l
e
m
e
n
t
a
t
i
o
n
Add
Manager
on NameNode
•
Store metadata on cached parities
•
Support different cache algorithms via two primitives:
•
Query
, return admission decision
•
Update
, update related information and return eviction decision if needed
27
…
client
…
parity
Architecture of POCache
data
E
v
a
l
u
a
t
i
o
n
R
e
s
u
l
t
s
Experiments on Amazon EC2 cloud
28
E
v
a
l
u
a
t
i
o
n
R
e
s
u
l
t
s
Single-client reads under striping layout
29
Good afternoon, everyone! I’m Mi Zhang from The Chinese University of Hong Kong. I’m glad to present our work, “parity-only caching for robust straggler tolerance”.
Addressing the challenge of stragglers in large-scale storage systems, this research introduces a Parity-Only Caching scheme for robust straggler tolerance. By combining caching and erasure coding techniques, the aim is to mitigate latency variations caused by stragglers without the need for accurate straggler detection. The proposed scheme, POCache, is designed to reduce coding overhead and improve system reliability against various failures. Mathematical analysis and experimental evaluations on Hadoop and Amazon EC2 platforms demonstrate the effectiveness of POCache in bypassing stragglers and enhancing system performance.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Parity-Only Caching for Robust Straggler Tolerance Mi Zhang, Qiuping Wang, Zhirong Shen, Patrick P. C. Lee The Chinese University of Hong Kong MSST 2019
Background Stragglers exist in large-scale storage systems Nodes operate with slow performance Also known as gray failures [Huang, HotOS 17] or fail-slow failures [Gunawi, FAST 16] Stragglers introduce latency variation [Dean, Comm. 13] Long tail in latency distribution Hard to pinpoint stragglers [Huang, HotOS 17; Gunawi, FAST 16] Varying root causes Long time to detect 2
Background Caching accessed data to bypass stragglers Cache space is limited Only caching popular data inevitably hits stragglers Selective replication creates more replicas for hot data High redundancy overhead Data popularity can change sharply [Huang, HotNets 14] 3
Erasure Coding (?, ?) erasure coding Encodes ?data blocks to generate ?parityblocks (? < ?) Any ? blocks suffice to reconstruct original content Erasure coding is a promising redundancy technique Storage efficiency Reduce storage overhead from 3x to 1.33x in Azure [Huang, ATC 12] High reliability against fail-stop failures Can we combine caching and erasure coding to achieve robust straggler tolerance? By robust, we mean straggler tolerance does not rely on accurate detection of stragglers 4
Our Contributions Conduct mathematical analysis Design POCache, a parity-only caching scheme for robust straggler tolerance Mitigate coding overhead via two mechanisms Straggler-aware cache algorithm Implement POCache atop Hadoop 3.1 HDFS Evaluate POCache on a local cluster and Amazon EC2 Compare POCache with hedge reads and selective replication 5
Mathematical Analysis Retrieve data from ? storage nodes ? data nodes ? cache nodes client Assume every node has a probability of 0.5% to become a straggler What is the probability of hitting a straggler for a read request? 6
Mathematical Analysis Probability of hitting a straggler When reading from ? = 4 data nodes No-caching Caching data Caching parity Number of cached blocks 7
Mathematical Analysis Probability of hitting a straggler When caching only ? = 1 block No-caching Caching data Caching parity Different number of data blocks 8
Main Findings Caching parity blocks is more effective than caching data blocks to bypass stragglers Caching only one parity block can effectively eliminate the impact of stragglers Even with slowdown of cache nodes, caching parity blocks still maintains straggler tolerance 9
Challenges Large encoding/decoding overhead Decoding time takes about 30% of read time [Rashmi, OSDI 16] Degrade normal read/write performance What parity blocks to cache? Manage cache space with considering stragglers Can we support general deployment? Support general storage systems and protocols Support upper-layer applications 10
POCache Design Block slicing data blocks parity block subblock substripe D0 D1 Dk-1 C0 Slice blocks into smaller-size subblocks Cache parity subblocks rather than the whole block Parallelize coding across different substripes Pipeline the process of caching parity blocks 11
POCache Design Incremental encoding data subblocks Parity subblock C0 D1 Dk-1 D0 C0 C0 C0 C0 Addition operations are associative in a linear combination Compute parity subblocks one by one incrementally 12
POCache Design How to minimize straggler hit ratio? Avoid accessing stragglers Consider file popularity Straggler-aware cache algorithm Admit caching parities for blocks on stragglers Collect each node s service rate Identify stragglers according to three-sigma rule Compose a straggler list Evict least-recently-accessed files 75% of re-accesses occur within 6 hours[Chen, VLDB 12] Details referred to the paper 13
Implementation Implement POCache on Hadoop 3.1 HDFS Use Redis to build cache nodes Add Manager on NameNode for cache management Modify HDFS client Manager NameNode client DataNode Cache Node Architecture of POCache 14
Evaluation Setup Local cluster 15 commodity machines Intel core i5, 16 GiB RAM, 1 TiB SATA disk 10 Gbps Ethernet switch Employ benchmark tool DFS-Perf Inject stragglers by running Linux stress 64-MiB block, 256-MiB file (4 blocks) by default Amazon EC2 30 m5.large instances, 2 m5.2xlarge instances Magnetic storage 5 Gbps network bandwidth 15
Evaluation Results Effectiveness of block slicing Cache one parity block for a file Lowest latency when subblock is of 1 MiB 16
Evaluation Results Single-client reads Read mechanisms Vanilla, read sequentially HR, hedged read PR, read blocks in parallel Evaluate different file sizes POCache reduces the latency with straggler to the latency in normal case 17
Evaluation Results Multi-client reads Read mechanisms in comparison Vanilla, read blocks sequentially HR, hedged read SR, cache popular data blocks Evaluate with 4, 8, 12 clients POCache achieves low mean and tail latencies With one straggler 18
Evaluation Results Cache efficiency of Straggler-aware cache algorithm (SAC) Straggler hit ratio under different cache sizes Latencies under different cache sizes 19
Evaluation Results Experiments on Amazon EC2 Read mechanisms Vanilla, read sequentially HR, hedged read PR, read blocks in parallel Stragglers naturally appear in cloud POCache achieves lowest latency among all four read policies 20
Conclusion Present POCache, a parity-only caching design for robust straggler tolerance Minimize coding overhead Straggler-aware cache algorithm Preserve original workflow and performance Implement POCache on Hadoop 3.1 HDFS Conduct experiments on a local cluster and Amazon EC2 Source code http://adslab.cse.cuhk.edu.hk/software/pocache 21
Thank you! Q&A 22
Background and Motivation Stragglers affect both data layouts Contiguous layout Striping layout node0 node1 node2 file 2~4MiB 4~6MiB 0~2MiB Contiguous layout 6MiB node0 node1 node2 0~1MiB 3~4MiB 1~2MiB 4~5MiB 2~3MiB 5~6MiB Striping layout 23
Numerical Analysis Probability of hitting straggler 24
Motivation Stragglers slow down read request Read a file f, consisting of k blocks residing on k nodes Each node behaves abnormally with probability ps k data block storage node client 25
Mathematical Analysis Two caching strategies Data-only cache c data blocks out of k data blocks Parity-only cache c parity blocks generated from k data blocks k data block storage node cached block cache node c client 26
Implementation Add Manager on NameNode Store metadata on cached parities Support different cache algorithms via two primitives: Query, return admission decision Update, update related information and return eviction decision if needed Manager NameNode client Architecture of POCache 27
Evaluation Results Experiments on Amazon EC2 cloud 28
Evaluation Results Single-client reads under striping layout 29
