Deep Store: An Archival
Storage System
Architecture
Lawrence [Link], Kristal T. Pollack, Darrell D. E. Long
Slides by: Brian Madden
Friday, May 7, 2010
Motivation
• Estimated that over five exabytes of data
produced in 2002
• Over 30% increase from previous year
• 37% of stored data is immutable
• Expected to grow to more than 50% in
the next year (2003)
• Federal regulations (Sarbanes-Oxley, etc)
Friday, May 7, 2010
Challenges
• Cost - Must be space efficient to reduce
cost
• Scalability - Must scale to accommodate
new data
• Reliability - Data has to be there later
• Retrieval - Data is useless if it can’t be
found
Friday, May 7, 2010
Desired Properties
• Reduced storage cost
• Immutability of data
• Dynamically scalable
• Highly reliable
• Archival compliance
Friday, May 7, 2010
Architecture Overview
• Primary Abstractions:
• Storage objects
• Physical storage components
• Software architecture
• Storage interface
Friday, May 7, 2010
Primary Abstractions
• Storage objects
• File - single contiguous stream of binary
data
• Identified by content; hash used as
content address
• Metadata - filename, length, etc
• Also identified by content address
Friday, May 7, 2010
Storage Nodes
• Nodes - the primary storage unit:
• Contains a processor, memory, and low-
cost disk
• Nodes connect to form a storage cluster
Friday, May 7, 2010
Software Architecture
• Consists of:
• Archival storage service
• Temporary storage buffer
• Content analyzer
• Content addressable store
Friday, May 7, 2010
Interface
• Interface should be simple
• Store object
• Retrieve object
• Delete object
• Verify object
Friday, May 7, 2010
PRESIDIO
• Progressive Redundancy Elimination of
Similar and Identical Data In Objects
• Uses various compression and delta
encoding schemes to reduce on disk data
size
Friday, May 7, 2010
PRESIDIO
• Virtual Object:
• Handle - contains content address
• Constant data block - Binary data
• Virtual data block - Polymorphically
constructed data block
Friday, May 7, 2010
PRESIDIO
Friday, May 7, 2010
PRESIDIO
• Objects are encapsulated by...
• Group: contain a number of megablocks
• Megablock: 16mb-4gb groups of data
• Maximizes contiguous writes
Friday, May 7, 2010
PRESIDIO
• Each group stored on a node
• Groups can have varying levels of
replication and coding for reliability
• A DHT is maintained mapping nodes to
group numbers
Friday, May 7, 2010
Metadata
• Current metadata is kind of lame...
• A rich, extensible metadata is much more
useful!
• For search
• To help future consumers understand the
data, formats, etc
Friday, May 7, 2010
Metadata
• Extended/Rich metadata counter
productive to space efficiency
• Don’t want to compress it
• Instead store metadata according to its role
in the system
Friday, May 7, 2010
Metadata
• Search metadata stored in query-enabled
structure
• System metadata store in fast lookup
structure
• Archival metadata stored in system itself
• Versioned, compressed losslessly
Friday, May 7, 2010
Metadata
• To enable space efficient versioning
• Delta compression
• XML tree merging
Friday, May 7, 2010
Metadata
Using XML tree
merging and
compressing the
result yielded the best
space savings
Friday, May 7, 2010
Execution
• File is chunked and hashed (Feature
selection)
• Similarity detection
• Redundancy elimination (Delta
compression)
• Recording
Friday, May 7, 2010
Evaluation
• Feature selection program runs at 19.7MB/s
on P4 2.66GHz
• Delta encoding ran at 8.7MB/s
Friday, May 7, 2010
Evaluation
Friday, May 7, 2010
Bottom Line
• Using a compression technique that best
fits the data yields better results
Friday, May 7, 2010
Uh-Oh!
• By compressing all of the data redundancy
is removed
• This is counter productive to data
longevity
• Solution: Store more valuable chunks/files
with more redundancy
Friday, May 7, 2010
Conclusions
• Deep store...
• is an archival storage framework
consisting of abstractions for data objects
• includes content analysis and PRESIDIO
• proposes rich, extensible metadata
• proposes value based chunk redundancy
Friday, May 7, 2010