Improving Content Addressable Storage for Databases Vandhana Selvaprakash Brandon M Smith Department of Computer Sciences University of Wisconsin Madison WI 53706 E mail vandhana bmsmith cs wisc edu Abstract Recent trends have seen database clients use content addressable storage systems CASs for nearline storage While CASs have many attractive properties such as storage space savings data integrity and low network bandwidth requirements CASs are not well suited for databases mainly because of the rigid structure of databases and the way databases intersperse metadata with data In this paper we evaluate where current CAS techniques fail for databases and identify properties of database systems that can be leveraged for potential improvements to CAS techniques specific to databases We propose fives ways in which CAS systems can be made database aware and evaluate the potential strengths and weakness of each approach We find that our techniques improve memory savings but at the expense of coupling the solution too closely to particular database vendors 1 Introduction CAS divides files into chunks other names include segments 3 blocks 1 atomics 7 or fragments 6 Each chunk is indexed by a descriptor or fingerprint that uniquely identifies its contents Files are hence content addressable rather than location addressable Identical chunks have the same fingerprint which insures that redundant data is never stored twice This technique substantially reduces the amount of storage space required provided that duplicate information exists in the file system Virtually all the systems we study use the cryptographic SHA 1 hash function 5 to calculate the fingerprint for each chunk One of the most desirable properties of this hash function is that it is very efficient to compute Yet another desirable property is its strong collision resistance With extremely high probability1 1 Assuming random hash values and a uniform distribution a fingerprint collision for an exabyte 10 18 bytes of data divided into 8 kilobyte chunks will occur with probability less than 10 20 which is many orders of magnitude less than hardware error rates 1 CS 736 each fingerprint will uniquely describe the contents of its corresponding chunk A three way distinction can be made between chunking techniques Data can be chunked based on 1 whole file content 2 fixed size chunks or 3 variable size content based chunks In 1 the chunk boundaries are simply determined by the beginning and ending of the files being stored Techniques based on 2 determine chunk boundaries by fixed offsets from the beginning of each file Techniques based on 3 are more complicated and typically involve discovering anchor points throughout each file based on its contents This is usually accomplished using some variant of the Rabin fingerprinting technique described by Udi Manber in 4 Although 1 and 2 are simple in most situations they effectively make files stored on the system immutable Variable size chunking techniques do not suffer from this problem 2 Motivation Content addressable storage systems CASs are primarily used to store data that changes rarely and is accessed infrequently write once read many Databases increasingly use CASs for storing backup information and snapshots Unlike traditional CAS data business data MRI Images which are loosely coupled with metadata if any databases are not well suited for CAS The problem with database storage structures is that metadata is A substantial and B tightly interspersed with data It is therefore difficult to exploit data redundancy for space savings Another limitation of current CAS techniques is that they only exploit identical files blocks or chunks Typically many pages within database storage structures are similar but very few are identical Databases make up a significant portion of storage system clients Simply said they are too important to ignore Given the increasing use of CASs by database systems we aim to improve CAS techniques specifically for the database domain Conference on Reliable Awesome Projects no acronyms please 2008 1 Table 1 target chunk size vs actual average chunk size Data type Target Chunk Size bytes Actual Average Size bytes 128 256 512 1024 2048 4096 8192 16384 32768 175 303 559 1070 2094 4137 8220 16413 32848 330 MB Sparse Oracle Tablespace 8192 21335 5 MB Sparse PostgreSQL Tablespace 8192 15443 560 MB Mix of Files pdf txt doc mpg jpg etc 4096 8192 16384 1100 1849 2062 1 GB Music Data mp3 wma wav m4a Our approach to this problem is as follows We implement several key features of state of the art CASs and evaluate these features on different kinds of data including music files text data and database data Oracle 10 and PostgreSQL 9 We determine quantitatively that recent variable sized chunking techniques perform poorly on database data We then study the low level storage structure of databases mainly Oracle and PostgreSQL and identify properties that can be leveraged for potential improvements to CAS techniques We propose five ways in which CAS systems can be made database aware and evaluate the potential strengths and weakness of each approach We find that our techniques improve memory savings but at the expense of coupling the solution too closely to particular database vendors The rest of the paper is organized as follows Section 3 current state of the art CAS techniques Section 4 discusses database semantics Section 5 discusses five approaches to improve CAS techniques for databases Section 6 discusses related work finally we end with some conclusions 3 Evaluation of State of the Art CAS techniques 3 1 Implementation To evaluate state of the art CASs 3 we implement the following Variable size chunking based on Rabin fingerprinting An efficient SHA 1 hash chunk fingerprint index storage structure based on a binary search tree 2 CS 736 A summary vector to further optimize the speed of chunk lookup We implement a variable size chunking tech nique based on a widely cited paper by Udi Manber 4 The technique is based on using Rabin fingerprints to discover anchor points within each file A sliding 48byte2 window scans through each file At each new byte the fingerprint is updated and the last N bits are compared to zero The average chunk size is then 2 N bytes based on the probability of the last N bits of the fingerprint being a certain value zero is usually chosen We then implement a binary search tree for efficient hash lookup Finally we implement a summary vector to further