Efficient Live Deduplication Storage for VM Images in Open-Source Cloud
1
L
i
v
e
D
e
d
u
p
l
i
c
a
t
i
o
n
S
t
o
r
a
g
e
o
f
V
i
r
t
u
a
l
M
a
c
h
i
n
e
I
m
a
g
e
s
i
n
a
n
O
p
e
n
-
S
o
u
r
c
e
C
l
o
u
d
C
h
u
n
-
H
o
N
g
,
M
i
n
g
c
a
o
M
a
,
T
s
z
-
Y
e
u
n
g
W
o
n
g
,
P
a
t
r
i
c
k
P
.
C
.
L
e
e
,
J
o
h
n
C
.
S
.
L
u
i
The Chinese University of Hong Kong
Middleware’11
U
s
i
n
g
C
l
o
u
d
C
o
m
p
u
t
i
n
g
Cloud computing is real…
But many companies still hesitate to use public
clouds
•
e.g., security concerns
O
p
e
n
-
s
o
u
r
c
e
c
l
o
u
d
p
l
a
t
f
o
r
m
s
•
Self-manageable
with cloud-centric features
•
Extensible
with new functionalities
•
Deployable
with
low-cost
commodity hardware
•
Examples:
•
Eucalyptus, OpenStack
2
H
o
s
t
i
n
g
V
M
I
m
a
g
e
s
o
n
t
h
e
C
l
o
u
d
A private cloud should host a variety of
virtual
machine (VM)
images for different needs
•
Common for commercial clouds
3
Example:
Amazon EC2
P
r
i
v
a
t
e
C
l
o
u
d
D
e
p
l
o
y
m
e
n
t
4
Huge storage space
needed to host all VM
image files
•
Each VM image has
few GB of storage
Question: How to
scale up storage with
low-cost commodity
hardware?
•
O
n
e
o
p
t
i
o
n
:
d
e
d
u
p
l
i
c
a
t
i
o
n
VM Image Storage
Pool of Compute Nodes
W
h
a
t
i
s
D
e
d
u
p
l
i
c
a
t
i
o
n
?
5
T
r
a
d
i
t
i
o
n
a
l
F
i
l
e
s
y
s
t
e
m
copy
copy
D
e
d
u
p
l
i
c
a
t
i
o
n
copy
No new
blocks!
U
s
e
r
’
s
p
o
i
n
t
o
f
v
i
e
w
W
h
a
t
i
s
D
e
d
u
p
l
i
c
a
t
i
o
n
?
Block-level deduplication
6
Example: storage space
reduced by 5/12 = 42%!
C
h
a
l
l
e
n
g
e
s
Deployment issues of deduplication in VM image
storage in an open-source cloud:
•
Can we preserve the performance of VM operations?
•
e.g., inserting VM images, VM startup
•
Can we support general file system operations?
•
e.g., read, write, modify, delete
•
Can we deploy deduplication on low-cost commodity
systems?
•
e.g., a few GB of RAM, 32/64-bit CPU, standard OS
7
R
e
l
a
t
e
d
W
o
r
k
Deduplication backup systems
•
e.g., Venti
[Quinlan & Dorward ’02]
, Data Domain
[Zhu et al. ’08]
,
Foundation
[Rhea et al. ’08]
•
Assume data is not modified or deleted
Deduplication file systems
•
e.g., OpenSolaris ZFS, OpenDedup SDFS
•
Consume significant memory space, not for
commodity systems
VM image storage
•
e.g., Lithium
[Hansen & Jul ’10]
, mainly on fault tolerance,
but not on deduplication
8
O
u
r
W
o
r
k
9
Design goals of LiveDFS:
•
Target open-source clouds deployed on low-cost
commodity hardware and OSs
•
Support basic file system operations, while allowing
inline (on-the-fly) deduplication while data being
written
O
u
r
W
o
r
k
Design features of LiveDFS:
•
Spatial locality
: store partial metadata in memory,
while storing full metadata on disk with respect to file
system layout
•
Prefetching metadata
: store metadata of same block
group into page cache
•
Journaling
: enable crash recovery and combine block
writes in batch
•
Kernel-space design
: built on Ext3, and follow Linux
file system layout
10
O
u
r
W
o
r
k
Deploy LiveDFS on
OpenStack testbed
•
L
i
v
e
D
F
S
s
e
r
v
e
s
a
s
a
s
t
o
r
a
g
e
l
a
y
e
r
b
e
t
w
e
e
n
c
o
m
p
u
t
e
n
o
d
e
s
a
n
d
V
M
i
m
a
g
e
s
t
o
r
a
g
e
Evaluate the
performance of VM
operations and
compare with Ext3
11
B
a
s
i
c
s
:
L
a
y
o
u
t
LiveDFS uses a
block-level
design
•
Organizes data into
fixed-size blocks
•
Blocks are organized into
block groups
, as in Linux
file system
12
…
…
metadata
block pointers
Super
block
Inode
bitmap
Block
bitmap
Inode
Layout of an
inode
Group 0
Group 2
Group 1
Layout of a
block group
Layout of a
partition
File system layout
of LiveDFS
B
a
s
i
c
s
:
L
a
y
o
u
t
Deduplication operates on fixed-size blocks
•
Saves one copy if two fixed-size blocks have the
same content
For VM image storage, deduplication efficiencies
similar for fixed-size blocks and variable-size
blocks
[Jin & Miller, ’09]
13
B
a
s
i
c
s
:
F
i
n
g
e
r
p
r
i
n
t
s
How to compare blocks?
S
o
l
u
t
i
o
n
:
U
s
e
c
r
y
p
t
o
g
r
a
p
h
i
c
h
a
s
h
e
s
(
o
r
f
i
n
g
e
r
p
r
i
n
t
s
)
14
New block
MD5 or SHA-1
4K Bytes
MD5
16 Bytes
SHA-1
20 Bytes
Hash-based comparisons
•
Same content
same hash
•
Different content
different
hashes with high probability
Pros: block comparison
reduced to hash comparison
Cons: collision may occur, but
with negligible probability
[Quinlan & Dorward, ’02]
B
a
s
i
c
s
:
R
e
f
e
r
e
n
c
e
C
o
u
n
t
s
How to know if a block is deleted?
S
o
l
u
t
i
o
n
:
K
e
e
p
a
r
e
f
e
r
e
n
c
e
c
o
u
n
t
f
o
r
e
a
c
h
b
l
o
c
k
.
Z
e
r
o
m
e
a
n
s
t
h
e
b
l
o
c
k
i
s
n
o
l
o
n
g
e
r
r
e
f
e
r
e
n
c
e
d
.
15
2
2
2
1
1
2
1
New block
3
I
n
l
i
n
e
D
e
d
u
p
l
i
c
a
t
i
o
n
How to check if a block being written and can be
deduplicated with existing blocks?
S
o
l
u
t
i
o
n
:
m
a
i
n
t
a
i
n
a
n
i
n
d
e
x
s
t
r
u
c
t
u
r
e
•
Keep track of fingerprints of existing blocks
G
o
a
l
:
d
e
s
i
g
n
o
f
i
n
d
e
x
s
t
r
u
c
t
u
r
e
m
u
s
t
b
e
e
f
f
i
c
i
e
n
t
i
n
s
p
a
c
e
a
n
d
s
p
e
e
d
Two options of keeping an index structure:
•
Putting whole index structure in RAM
•
Putting whole index structure on disk
16
O
p
t
i
o
n
1
:
I
n
d
e
x
S
t
r
u
c
t
u
r
e
i
n
R
A
M
How about putting whole index structure
in RAM
?
•
Used in existing dedup file systems (e.g., ZFS, OpenDedup)
Challenge: need large amount of RAM
Example: per 1TB of disk content
17
O
p
t
i
o
n
2
:
I
n
d
e
x
S
t
r
u
c
t
u
r
e
o
n
D
i
s
k
How about putting whole index structure
on disk
?
Challenge: updating each data block and its index keeps
the disk head moving, which hurts performance.
18
Search for
duplicated block.
Indexing
Structure
Remaining File System
If not found, write to
file system.
For each
write
request…
L
i
v
e
D
F
S
D
e
s
i
g
n
Store partial fingerprints in memory
•
Infer if same block exists, and where it is “potentially” located
19
Checksum of incoming block
Partial hash
N Bits
Partial hash 0
Block #
Partial hash 1
Block #
Partial hash n
Block #
......
matching
C
u
r
r
e
n
t
I
m
p
l
e
m
e
n
t
a
t
i
o
n
N=43, error rate = 2
-15
i.e., on average every
128MB of data, one partial
hash mapped to two block
locations.
P
e
r
1
T
B
o
f
d
i
s
k
,
r
e
d
u
c
e
m
e
m
o
r
y
u
s
a
g
e
f
r
o
m
p
r
e
v
i
o
u
s
4
G
B
t
o
1
.
6
G
B
I
n
c
o
m
i
n
g
w
r
i
t
e
r
e
q
u
e
s
t
F
i
n
g
e
r
p
r
i
n
t
f
i
l
t
e
r
L
i
v
e
D
F
S
D
e
s
i
g
n
S
t
o
r
e
f
u
l
l
f
i
n
g
e
r
p
r
i
n
t
s
o
n
d
i
s
k
,
w
i
t
h
s
p
a
t
i
a
l
l
o
c
a
l
i
t
y
•
Verify whether the same block is actually located
20
Partition index structure according to block groups
•
E
a
c
h
b
l
o
c
k
g
r
o
u
p
h
a
s
a
f
i
n
g
e
r
p
r
i
n
t
s
t
o
r
e
•
Each fingerprint store keeps fingerprints and reference counts for
the respective data blocks in the same block group
Writing with close proximity incurs minimal seeks
I
N
D
E
X
Data
I
N
D
E
X
Data
I
N
D
E
X
......
I
N
D
E
X
Data
Full checksum
Reference Count
L
i
v
e
D
F
S
D
e
s
i
g
n
T
a
k
e
-
a
w
a
y
:
L
i
v
e
D
F
S
a
r
r
a
n
g
e
s
f
i
n
g
e
r
p
r
i
n
t
s
i
n
m
e
m
o
r
y
a
n
d
o
n
d
i
s
k
a
c
c
o
r
d
i
n
g
t
o
u
n
d
e
r
l
y
i
n
g
f
i
l
e
s
y
s
t
e
m
l
a
y
o
u
t
o
n
d
i
s
k
Other features:
•
Prefetching of fingerprint store
:
•
load entire fingerprint store of same block group into page cache
•
subsequent writes updates fingerprint store directly in page cache.
•
Journaling
:
•
follow Linux file system journaling design
•
enable crash recovery and enhance write performance by
combining block writes in batch
Details in the paper
21
E
x
p
e
r
i
m
e
n
t
s
OpenStack Deployment
•
1 compute node
•
1 storage node
•
Gigabit switch connection
Datasets
•
42 VM images of diff. dists (e.g.,
Fedora, Ubuntu) compliant with
Amazon EC2
•
Each VM image is of size 2GB
VM operations via
euca2tools
:
•
Inserting VM images
•
Launch VM instances
22
VM Image Storage
S
p
a
c
e
U
s
a
g
e
23
LiveDFS saves 40% storage over Ext3
S
p
a
c
e
U
s
a
g
e
Space saving ranges from 33% to 60% from
each Linux distribution
24
I
n
s
e
r
t
i
n
g
V
M
I
m
a
g
e
s
LiveDFS uses less insertion time than Ext3,
mainly because it doesn’t write duplicate blocks
25
V
M
S
t
a
r
t
u
p
Tradeoff: LiveDFS uses 30% more startup time
Main reason: internal fragmentation due to deduplication
(read may access duplicate blocks in different locations)
26
V
M
S
t
a
r
t
u
p
Overhead remains at the same percentage even
when multiple instances started in parallel
27
S
u
m
m
a
r
y
o
f
R
e
s
u
l
t
s
LiveDFS saves 40% storage via deduplication
LiveDFS uses less VM insertion time, with a
tradeoff of more VM startup time
Microbenchmark experiments to study impact of
each design features
•
See details in paper
28
F
u
t
u
r
e
W
o
r
k
Reduce read time due to fragmentation
introduced by deduplication?
•
e.g., read cache to cache duplicate blocks
Compare LiveDFS with other deduplication file
systems (e.g., ZFS, OpenDedup SDFS)?
Explore other storage applications
29
C
o
n
c
l
u
s
i
o
n
s
Deploy live (inline) deduplication in an open-
source cloud platform with commodity settings
P
r
o
p
o
s
e
L
i
v
e
D
F
S
,
a
k
e
r
n
e
l
-
s
p
a
c
e
f
i
l
e
s
y
s
t
e
m
•
Spatial locality of fingerprint management
•
Prefetching of fingerprints into page cache
•
Journaling to enable crash recovery and combine
writes in batch
Source code:
•
h
t
t
p
:
/
/
a
n
s
r
l
a
b
.
c
s
e
.
c
u
h
k
.
e
d
u
.
h
k
/
s
o
f
t
w
a
r
e
/
l
i
v
e
d
f
s
30
Explore the implementation of live deduplication storage for virtual machine images in open-source cloud environments to optimize storage space utilization and enhance performance. The focus is on addressing challenges related to deploying deduplication in VM image storage while maintaining performance, supporting file system operations, and utilizing low-cost commodity hardware effectively. Discover the potential of deduplication for scalable storage solutions in private cloud deployments.
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
Live Deduplication Storage of Virtual Machine Images in an Open-Source Cloud Chun-Ho Ng, Mingcao Ma, Tsz-Yeung Wong, Patrick P. C. Lee, John C. S. Lui The Chinese University of Hong Kong Middleware 11 1
Using Cloud Computing Cloud computing is real But many companies still hesitate to use public clouds e.g., security concerns Open-source cloud platforms Self-manageable with cloud-centric features Extensible with new functionalities Deployable with low-cost commodity hardware Examples: Eucalyptus, OpenStack 2
Hosting VM Images on the Cloud A private cloud should host a variety of virtual machine (VM) images for different needs Common for commercial clouds Example: Amazon EC2 3
Private Cloud Deployment Huge storage space needed to host all VM image files Each VM image has few GB of storage VM Image Storage Question: How to scale up storage with low-cost commodity hardware? One option: deduplication Pool of Compute Nodes 4
What is Deduplication? User s point of view Traditional File system copy copy Idea. Eliminate storage of data with same content Deduplication No new blocks! copy 5
What is Deduplication? Block-level deduplication Example: storage space reduced by 5/12 = 42%! 6
Challenges Deployment issues of deduplication in VM image storage in an open-source cloud: Can we preserve the performance of VM operations? e.g., inserting VM images, VM startup Can we support general file system operations? e.g., read, write, modify, delete Can we deploy deduplication on low-cost commodity systems? e.g., a few GB of RAM, 32/64-bit CPU, standard OS 7
Related Work Deduplication backup systems e.g., Venti [Quinlan & Dorward 02], Data Domain [Zhu et al. 08], Foundation [Rhea et al. 08] Assume data is not modified or deleted Deduplication file systems e.g., OpenSolaris ZFS, OpenDedup SDFS Consume significant memory space, not for commodity systems VM image storage e.g., Lithium [Hansen & Jul 10], mainly on fault tolerance, but not on deduplication 8
Our Work LiveDFS: a live deduplication file system tailored for VM image storage Design goals of LiveDFS: Target open-source clouds deployed on low-cost commodity hardware and OSs Support basic file system operations, while allowing inline (on-the-fly) deduplication while data being written 9
Our Work Design features of LiveDFS: Spatial locality: store partial metadata in memory, while storing full metadata on disk with respect to file system layout Prefetching metadata: store metadata of same block group into page cache Journaling: enable crash recovery and combine block writes in batch Kernel-space design: built on Ext3, and follow Linux file system layout 10
Our Work Deploy LiveDFS on OpenStack testbed LiveDFS serves as a storage layer between compute nodes and VM image storage VM Image Storage LiveDFS Evaluate the performance of VM operations and compare with Ext3 Pool of Compute Nodes 11
Basics: Layout File system layout of LiveDFS metadata block pointers Layout of an inode Layout of a block group Super block Inode bitmap Block bitmap Inode Layout of a partition Group 0 Group 1 Group 2 LiveDFS uses a block-level design Organizes data into fixed-size blocks Blocks are organized into block groups, as in Linux file system 12
Basics: Layout Deduplication operates on fixed-size blocks Saves one copy if two fixed-size blocks have the same content For VM image storage, deduplication efficiencies similar for fixed-size blocks and variable-size blocks [Jin & Miller, 09] 13
Basics: Fingerprints How to compare blocks? Solution: Use cryptographic hashes (or fingerprints) Hash-based comparisons Same content same hash Different content different hashes with high probability 4K Bytes New block Pros: block comparison reduced to hash comparison MD5 or SHA-1 Cons: collision may occur, but with negligible probability [Quinlan & Dorward, 02] MD5 SHA-1 16 Bytes 20 Bytes 14
Basics: Reference Counts How to know if a block is deleted? Solution: Keep a reference count for each block. Zero means the block is no longer referenced. New block 3 2 2 2 1 1 2 1 15
Inline Deduplication How to check if a block being written and can be deduplicated with existing blocks? Solution: maintain an index structure Keep track of fingerprints of existing blocks Goal: design of index structure must be efficient in space and speed Two options of keeping an index structure: Putting whole index structure in RAM Putting whole index structure on disk 16
Option 1: Index Structure in RAM How about putting whole index structure in RAM? Used in existing dedup file systems (e.g., ZFS, OpenDedup) Challenge: need large amount of RAM Example: per 1TB of disk content Block Size 4KB Using MD5 checksum 16 bytes per block Size of Index 1TB / 4KB x 16 bytes = 4GB. 17
Option 2: Index Structure on Disk How about putting whole index structure on disk? Indexing Structure Remaining File System 1 2 Search for duplicated block. If not found, write to file system. For each write request Challenge: updating each data block and its index keeps the disk head moving, which hurts performance. 18
LiveDFS Design Store partial fingerprints in memory Infer if same block exists, and where it is potentially located Checksum of incoming block Incoming write request N Bits Current Implementation Partial hash N=43, error rate = 2-15 matching i.e., on average every 128MB of data, one partial hash mapped to two block locations. Partial hash 0 Block # Fingerprint filter Partial hash 1 Block # ...... Per 1TB of disk, reduce memory usage from previous 4GB to 1.6GB Partial hash n Block # 19
LiveDFS Design Store full fingerprints on disk, with spatial locality Verify whether the same block is actually located I I I I N D E X N D E X N D E X N D E X Data Data ...... Data Full checksum Reference Count Partition index structure according to block groups Each block group has a fingerprint store Each fingerprint store keeps fingerprints and reference counts for the respective data blocks in the same block group Writing with close proximity incurs minimal seeks 20
LiveDFS Design Take-away: LiveDFS arranges fingerprints in memory and on disk according to underlying file system layout on disk Other features: Prefetching of fingerprint store: load entire fingerprint store of same block group into page cache subsequent writes updates fingerprint store directly in page cache. Journaling: follow Linux file system journaling design enable crash recovery and enhance write performance by combining block writes in batch Details in the paper 21
Experiments OpenStack Deployment 1 compute node 1 storage node Gigabit switch connection VM Image Storage Datasets 42 VM images of diff. dists (e.g., Fedora, Ubuntu) compliant with Amazon EC2 Each VM image is of size 2GB VM operations via euca2tools: Inserting VM images Launch VM instances 22
Space Usage LiveDFS saves 40% storage over Ext3 23
Space Usage Space saving ranges from 33% to 60% from each Linux distribution 24
Inserting VM Images LiveDFS uses less insertion time than Ext3, mainly because it doesn t write duplicate blocks 25
VM Startup Tradeoff: LiveDFS uses 30% more startup time Main reason: internal fragmentation due to deduplication (read may access duplicate blocks in different locations) 26
VM Startup Overhead remains at the same percentage even when multiple instances started in parallel 27
Summary of Results LiveDFS saves 40% storage via deduplication LiveDFS uses less VM insertion time, with a tradeoff of more VM startup time Microbenchmark experiments to study impact of each design features See details in paper 28
Future Work Reduce read time due to fragmentation introduced by deduplication? e.g., read cache to cache duplicate blocks Compare LiveDFS with other deduplication file systems (e.g., ZFS, OpenDedup SDFS)? Explore other storage applications 29
Conclusions Deploy live (inline) deduplication in an open- source cloud platform with commodity settings Propose LiveDFS, a kernel-space file system Spatial locality of fingerprint management Prefetching of fingerprints into page cache Journaling to enable crash recovery and combine writes in batch Source code: http://ansrlab.cse.cuhk.edu.hk/software/livedfs 30
