Answer questions

USENIX Association 11th USENIX Conference on File and Storage Technologies (FAST ’13) 229

To Zip or not to Zip: Effective Resource Usage for Real-Time Compression∗

Danny Harnik, Ronen Kat, Oded Margalit, Dmitry Sotnikov, Avishay Traeger IBM Research–Haifa

{dannyh,ronenkat,odedm,dmitrys,avishay}@il.ibm.com

Abstract Real-time compression for primary storage is quickly

becoming widespread as data continues to grow exponen- tially, but adding compression on the data path consumes scarce CPU and memory resources on the storage sys- tem. Our work aims to mitigate this cost by introducing methods to quickly and accurately identify the data that will yield significant space savings when compressed.

The first level of filtering that we employ is at the data set level (e.g., volume or file system), where we estimate the overall compressibility of the data at rest. Accord- ing to the outcome, we may choose to enable or disable compression for the entire data set, or to employ a sec- ond level of finer-grained filtering. The second filtering scheme examines data being written to the storage system in an online manner and determines its compressibility.

The first-level filtering runs in mere minutes while providing mathematically proven guarantees on its esti- mates. In addition to aiding in selecting which volumes to compress, it has been released as a public tool, allow- ing potential customers to determine the effectiveness of compression on their data and to aid in capacity plan- ning. The second-level filtering has shown significant CPU savings (up to 35%) while maintaining compression savings (within 2%).

1 Introduction Data continues to grow at an exponential rate, outpacing the growth of storage capacity [9]. Data is also growing faster than IT budgets are, making it difficult to purchase and maintain the disk drives required to store necessary data [8]. Historically, compression has been widely used in tape systems, desktop storage, WAN optimization, and within applications such as databases. In the past few years, deduplication and compression have been widely adopted in backup and archive storage. More recently, enterprise storage solutions have been adopting compres- sion for primary storage.

In practice, primary storage compression comes in three main flavors: real-time or inline compression [2, 15, 21–23], offline compression [6], and a mix of real-time and offline [18]. Our work focuses on real-time compres- sion for block and file primary storage systems. However, its basic principles are general and can be applied to other compression use cases as well.

∗This research was partially supported by the European Commu- nity’s Seventh Framework Programme (FP7/2001-2013) under grant agreement number 257019 - VISION Cloud.

Compression does not come for free: it consumes sys- tem resources, mainly CPU time and memory. It may also increase latency for both write and read operations, where data must be compressed and decompressed, re- spectively. On the other hand, if compression reduces the data size substantially, performance can improve; disk I/O time is reduced, and the system’s cache can hold more data. These benefits can neutralize the compres- sion overheads, and in some cases overall performance may even improve substantially.

But what if the compression yields little or no benefit for a given data set? In such cases, not only are there no capacity savings (and associated cost savings), but also degraded performance and wasted resources. Worse yet, standard LZ type compression algorithms incur higher performance overheads when the data does not compress well. Figure 1 shows that with the standard zlib library [5, 7], one invests 3.5X (or more) as much time when com- pressing data that compresses to 90% of its original size as it does when compressing data that reduces to 20%. These observations indicate that it is advisable to avoid compressing what we refer to as “incompressible” data.

Our work addresses the problem of identifying incom- pressible data in an efficient manner, allowing systems to effectively utilize their limited resources: compressing only data that will yield benefits, and not compressing data that will cause the system to needlessly waste re- sources and incur unnecessary overheads. Our solution is comprised of two components: a macro-scale com- pression estimation for the data set, and a micro-scale compressibility test for individual write operations.

Our macro-scale estimation tool is an efficient offline method for accurately determining the overall compres- sion ratio and distribution of compression ratios for a data set (e.g., volume or file system). It runs in a matter of minutes and provides tight statistical guarantees on its estimates. The output of the estimate can result in three main actions. First, if the estimate shows that the data is highly compressible overall, compression can be en- abled with confidence that little-to-no resources will be wasted. Second, if the output indicates that compression will yield little benefit, compression can be disabled, al- lowing resources to be directed to more beneficial tasks. Third, if the data set contains data of varying compress- ibility which has the potential to yield significant savings, but where compressing all data would be wasteful, the micro-scale test can be enabled to safely enable compres- sion on a finer granularity.

230 11th USENIX Conference on File and Storage Technologies (FAST ’13) USENIX Association

The micro-scale test examines data as it is written and for each write buffer, quickly determines the effective- ness of compressing it. This online test must be quick and accurate to maximize the benefits of compression. If it is not significantly faster than compression, perfor- mance will be similar to compressing all data. If it is not accurate, we may miss opportunities to compress data or waste resources on incompressible data. A common method to determine if a write buffer is compressible is to compress the first portion and see how well it com- presses. We call this prefix estimation. If the prefix com- presses well enough, the remainder of the buffer will then be compressed, and so there is no overhead because no extra work is done. However, the micro-scale test is most important when there is a significant amount of incom- pressible data, and here prefix estimation has a high over- head (recall that compression is most expensive for in- compressible data). We have developed a method to com- plement prefix estimation that samples the data buffer and employs heuristics to determine its compressibility. For incompressible data, it has 2–6X less performance over- head, and overall incurs less capacity overhead due to missed compression opportunities.

Our contributions: The contributions of this paper are the designs and implementations of the macro- and micro-scale tests, along with thorough experimentation and analysis on real-world data.

The macro-scale test provides a quick and accurate es- timate for which data sets to compress. It has been re- leased to the public as a tool for use with real-time com- pression on the IBM Storwize V7000 and SAN Volume Controller [13]; it has been proven in the field to be an effective tool for customers to determine the effective- ness of compression on their data, the amount of stor- age to purchase, and which volumes to compress. It is also being used in a cloud storage prototype to selec- tively enable compression for large data transfers over the WAN. The results are mathematically proven to pro- vide a well-defined degree of accuracy, so its estimates can be trusted.

The micro-scale test heuristics have proved critical in reducing resource consumption while maximizing com- pression for volumes containing a mix of compressible and incompressible data. The heuristic method managed to reduce CPU usage by up to 35% on a representative data set, providing a significant improvement to a storage system, which must effectively use its generally scarce resources to serve I/Os.

Paper organization:Section 2 provides technical and performance background on compression. We discuss the macro-scale estimation in Section 3 and the micro- scale in Section 4. Section 5 describes related work and Section 6 provides concluding remarks.

Figure 1: The average times to compress 32KB of data for each compression ratio, as collected by compressing the Benchmark data set described in Table 3. 2 Preliminaries The vast majority of lossless compression algorithms are based either on Huffman encodings [12] or the Lempel- Ziv algorithms [24, 25]. Huffman codes make use of the fact that in most data not all symbols are equally popu- lar, and encodes the most frequent symbols by the short- est bit representations. The Lempel-Ziv methods look for repeating strings in the data and store back-pointers to long repetitions, thus avoiding the need to repeat data and ultimately shortening the representation. Perhaps the most widely used method is the DEFLATE framework which combines the two aforementioned methodologies (namely a Huffman encoding on top of an LZ77 encod- ing). Our study is centered around this framework which is relevant to IBM’s Real-time Compression [22], but it’s general concepts are applicable for many other compres- sion methods.

By compression ratio, we refer to the ratio between the size of the compressed data to the size of the original data. We present the compression ratio on a scale from 0 to 1, where compression savings are greater as the ratio is closer to zero. Alternatively we sometimes use percent- age to present this ratio.

In our tests we use the popular zlib open source com- pression library [5, 7] that implements the DEFLATE al- gorithm. zlib implements a number of different compres- sion levels – numbered between 0 and 9: 1 gives the best speed, while 9 attempts to give the best compression ra- tio, and 0 gives no compression at all (the input data is simply copied). In this work we use level 1 as it pro- vides the fastest compression, which is an important fac- tor for real-time compression, which is our focus. Our implementation disabled compression by using zlib level 0, and set the HUFFMAN ONLY flag to disable the LZ77 algorithm and use only the Huffman coding.

Figure 1 shows the impact of varying compressibility on the CPU time (for zlib level 1 and Huffman coding on 32KB data blocks). Note that compression time for zlib level 1 varies linearly by more than a factor of 8,

USENIX Association 11th USENIX Conference on File and Storage Technologies (FAST ’13) 231

performing worst for data that does not compress well (what we refer to as incompressible). The run time of the Huffman-only coding option is also influenced linearly by compression ratio, and is faster than zlib level 1 for compression ratios higher than 0.5.

3 The Macro-scale Solution The macro-scale solution is appropriate for scenarios that consider compression on a large scale; for example, an entire volume or file system of a storage system, or a large data transfer. The solution constitutes an efficient estimation mechanism for the aggregate compression ra- tio over the entire data set. The input to the procedure is a pointer to the data set (e.g., a physical volume, a file system, or a list of objects) and the output is an overall compression ratio, histogram, and an accuracy range.

We implemented our estimator with two basic inter- faces. The first is a block device interface, which is tai- lored for a specific real-time compression product that compresses data stored on a block storage system. The second is a file and object storage interface. The input here is a list of files or objects and their sizes. In this model each object is compressed independently using a standard compression mechanism (we use zlib with com- pression level 1). This implementation can estimate com- pression for both a file system and a collection of objects.

Our solution possesses two key properties that make it particularly useful: speed and accuracy. Speed: The test runs very fast, especially when con- trasted with the time an exhaustive compression would take on a large volume (improvements of up to 300X over an exhaustive run are not uncommon). The run time de- pends on the underlying platform and storage speed, but is typically under two minutes, regardless of the volume size. Performance results are described in Section 3.3. Accuracy: The estimation comes with a statistical accu- racy guarantee of the following form: the probability that the estimation will be off by an additive error of A (the accuracy) is no more than 1 − C (the confidence). In a typical example, A could be 5% of the volume size, and the guarantee would be that the test would be off by more than A only once in 10 million tries (here C = 10−7). This guarantee is backed up by a mathematical analysis (see Section 3.2).

3.1 Motivation and Use Cases Our estimation tool has proved most useful in a variety of use cases which rely on its speed and accuracy.

Per-volume decisions: It is common to build a storage system of multiple volumes, with each volume serving a specific application. When configuring a system to in- clude compression, one can run a quick per-volume es- timation to decide whether or not to compress each vol-

ume. Determining when to compress is critical, as every system has limited resources, and so it is unwise to direct resources to compressing data where there is little or no benefit. In many cases, the volume will contain data with homogeneous compression characteristics, and compres- sion can be enabled or disabled for the entire volume. Of- ten, however, the volume will contain data with varying degrees of compressibility. The macro-scale test provides a histogram of compression ratios that clearly shows this case and allows enabling the micro-scale test described in Section 4 to compress only the portions of the volume where it is beneficial. New volumes with little data can initially be saved in uncompressed form and periodically tested with the estimation tool. Once the volume’s char- acteristics are clear, a decision can be made.

Sizing and pre-sales: The high accuracy provided by the estimation allows determining what the expected size of a storage system would be if it has compression included. This is instrumental in two key junctures: 1) Evaluating the overall cost savings that can be achieved by integrat- ing compression into a system—naturally, this provides a powerful selling tool for systems with compression, and 2) Deciding how many disks to buy for a system with compression. The more accurate the estimation, the more money customers can save by not purchasing extra disks to over-provision their systems. Indeed, our implementa- tion is an official planning and pre-sales tool for two IBM storage systems that support real-time compression.

Large data transfers: Large data transfers between hosts with limited bandwidth are typical in cloud stor- age scenarios. For example, in large multi-site storage clouds, large amounts of data need to be transferred over a wide area network (WAN) when ingesting data from cloud users or when recovering from a site failure. Com- pressing data can reduce transfer time, but unless the compression provides enough benefit, it may actually be slower than transmitting the uncompressed data. By run- ning our estimation method, one can quickly and accu- rately compute the benefits of compression. Our estima- tion in this case also takes the connection speed into ac- count to determine the effectiveness of compression in improving transfer time. The macro-scale test generally completes in under two minutes, while the data transfers may take hours or even days to complete, and can be cru- cial in reducing transfer time as well as limiting resources used for compression. The resulting decision is similar to the case of per-volume decisions: enable or disable com- pression completely, or decide on smaller granularities using the micro-scale test.

232 11th USENIX Conference on File and Storage Technologies (FAST ’13) USENIX Association

3.2 The General Method Our method is based on random sampling, within the fol- lowing natural and general framework:

1. Choose m random locations in the data, where m is a predefined sample size (see Section 3.2.1).

2. For each location compute a compression ratio. 3. The overall estimation is an average of the m com-

pression ratios.

While the above process is very simple and expected, the devil lies in the details. There are two main issues that must be addressed:

• How to choose the number of samples m? • How to compute the local compression ratios for

each sampled location?

Our method is complemented with an analytical proof of accuracy that answers both of the above questions. Our method is guided by the proof, which dictates valid sam- pling methods, as well as how many samples are required to achieve a desired level of accuracy.

3.2.1 Proof of Accuracy and Choosing the Sample Size

In a nutshell, we look at the total compression ratio as an average of the compression ratio of each byte in the data set. This is tricky, however, as bytes are not com- pressed independently and there is no meaning to the compression ratio of a single byte. Instead, we view the contribution of a single input byte to the output of the compressed stream as an average of the compression rate in its locality (we define locality in Section 3.2.2). Let contributioni denote the contribution of the ith byte in the volume. Our goal is to define contribution so that the overall compression ratio could be presented in this form:

Compression Ratio = 1

n

n−1∑ i=0

contributioni

The benefit of this representation is that estimating an av- erage over a large population is a well studied problem in statistics. Specifically, we know that the average of a random sample of the population is a good estimator and can bound the variance of this estimator as a function of the number of samples. We do this using the Hoeffding inequality [11] which relates between three parameters: Accuracy, Confidence and the sample size m. The analy- sis states that if

Confidence = 2e−2m∗Accuracy2

Then

Prob(|Estimation−Ratio| > Accuracy)

< Confidence

Accuracy Confidence Sample Size 0.05 10−7 3363 0.02 10−7 21015 0.01 10−7 84057 0.05 10−3 1521 0.05 10−6 2902 0.05 10−9 4284

Table 1: Sample size examples for different values of accuracy and confidence.

Figure 2: Accuracy as a function of sample size for 3 levels of confidence.

That is, the estimation will stray by more than Accuracy with probability at most confidence.

From this analysis we deduce the number of samples that should be used in the sampling mechanism as a func- tion of the accuracy and confidence parameters, as stated in the following formula:

m ≥ 1

2 ·Accuracy2 ln

( 2

Confidence

)

Note that the confidence parameter appears inside a logarithm and does not influence the result greatly. In fact one can greatly improve the confidence with little ef- fort (see example in Table 1). On the other hand, the ac- curacy parameter is squared and dominates this equation, and therefore improving the accuracy is costly, as seen in the table. Improving accuracy by a factor of 2 requires 4 times as many samples (or in general, any improvement by a k factor requires k2 as many samples). This effect is seen in Figure 2 for different confidence levels. While achieving an accuracy bound of up to 5% is fairly easy, achieving a 2% bound requires significantly more sam- ples, and achieving a 1% assurance while providing an answer within the time constraints set by the use cases is unrealistic. The above formulation gives only a simple bound on the error, but in fact we know that for every fixed sample size the distribution of results will form a normal distribution around the actual ratio. Therefore, most results will actually lie very close to the actual re- sult, far better than what the accuracy bound guarantees.

USENIX Association 11th USENIX Conference on File and Storage Technologies (FAST ’13) 233

Note that if the data is mostly uniform in its compres- sion ratio then we can stop the execution earlier (once it has been established that the observed samples have low variance). In real life however, the estimation was quick enough so that this additional test could be avoided.

Histograms and other estimations: The accuracy guar- antees rely on the fact that the estimated value lies in a bounded range (in this case, between 0 and 1). Accurate estimation can therefore be assured also for other metrics that are similarly bounded. For instance, we can also esti- mate the fraction of the data that has a compression ratio within a certain range or the fraction of zero blocks in a volume. Indeed our tool outputs such histograms on com- pression ratio distribution within a volume (see Figure 5). On the other hand, if the estimation target is unbounded, then we cannot guarantee useful estimations. This is the case with the running time of compression, which has a high variance and is harder to estimate in a useful man- ner.

3.2.2 What to Sample and Compute For the above accuracy analysis to be useful, we must be able to efficiently sample and compute the “contribu- tion” of random bytes in the data set. To compute the contribution of a byte, or even to define it properly, the compression method must have some bounded locality properties; the compression of a given byte must be in- fluenced by a limited number of other bytes. These other bytes should generally small in number and have offsets close to the byte in question. While straightforward for some methods, it is trickier for others, and may be alto- gether impossible for some compression techniques. To demonstrate this principle we give examples for the two types of compression that we handle:

Sampling in real-time compression: Real-time com- pression systems typically divide the data into chunks and compress each chunk separately. This is advanta- geous when data needs to be accessed randomly. Rather than decompress entire large files or large data segments, the decompression may be done locally on small chunks. Depending on the technique, these chunks may be fixed- size input chunks or alternatively may be defined by the actual data and/or its compression rate. Either way, the contribution of a specific byte is defined as the average contribution of the chunk that it belongs to. Accordingly, the sample phase will choose a random location and find the compression chunk surrounding it. The compression is then carried out only for this chunk, and the average compression for the chunk is the value added as the sam- ple’s contribution.

Sampling for zlib compression on objects: Another ex-

ample of locality appears when running the DEFLATE algorithm on large data objects. Lempel-Ziv encodings are locally bounded due to practical considerations— back pointers are limited to 15 bits, allowing them to point to a window of only 32KB, and each repeating stream is limited to 256 bytes only in length (represented by 1 byte). Thus the compression ratio of a byte can be determined by examining a range of 32KB+256 bytes. Huffman coding, is also computed on a local window (de- termined by the space usage of the compression stream). Lower levels of DEFLATE will use a smaller window and thus easier to samlpe. In our estimation algorithm for the object interface we use the window size induced by the Lempel-Ziv encoding.

Once locality is understood for the particular algo- rithm, the question of how to define the contribution of a certain location remains. We first note that simply taking the average compression over a window of 32KB+256B does not fulfill our basic requirement that the overall ratio is an average of all the contributions. Indeed, this simple approach is misleading and can give gross miscalcula- tions. The problem stems from the fact that a repeating string should be counted in full only on its very first ap- pearance, as it has a very succinct representation on its second appearance. Therefore, given a chosen offset in- side an object, we start running the compression process 32KB before this location, but discard the output. This pre-run serves as a warm-up to initialize the compres- sion data structures to the state they would be at during compression of the object or volume. The contribution of the chosen offset is computed by the output size of compressing the next 256 bytes, divided by 256 (in other words, the average contribution to the output). Under this definition the average of contribution indeed sums up to the total compression ratio. Note: Unlike the above mentioned compression exam- ples, deduplication has no locality properties. In fact it can be viewed as a global version of compression, seek- ing repetitions across the entire data set. Indeed it was observed by Harnik et al. that deduplication ratios cannot be accurately estimated using sampling [10].

3.3 Implementation and Evaluation We implemented the two versions of our estimator (the block device version and the objects version) in C++. The tool can spawn multiple threads, taking advantage of the inherent parallelism in processing random samples.

The block interface [13] estimates the compression ra- tio that would be achieved on a volume by using IBM’s real-time compression product [22]. This is a host-based tool that can run on any storage attached to the host, and estimates two numbers: the percentage of zero blocks in the system, and the compression ratio on the non- zero blocks. We treat zero blocks as a special case, as

234 11th USENIX Conference on File and Storage Technologies (FAST ’13) USENIX Association

Data Type Interface Storage Size Zero Exhaustive Estimator type blocks Run time Ratio (%) Run time Ratio (%)

Development 1 real-time Disk 279 GB 30% 4603 sec 17.28 177 sec 17.25 Development 2 real-time Disk 279 GB 23% 5112 sec 28.20 204 sec 27.45 Development 3 real-time Disk 279 GB 72% 4495 sec 87.09 207 sec 88.15 Development 4 real-time Disk 137 GB 47% 2916 sec 13.45 150 sec 14.00 Hypervisor 1 real-time Disk 3253 GB 49% 13800 sec 33.15 73 sec 32.99 Hypervisor 2 real-time Disk 3253 GB 74% 19573 sec 18.24 140 sec 18.55

File repository real-time RAID5 390 GB 39% 2004 sec 50.16 38 sec 50.53 Object repository 1 object RAID5 266 GB – 6376 sec 40.93 21 sec 42.35 Object repository 2 object RAID5 375 GB – 10333 sec 51.60 44 sec 52.85

Table 2: Examples of estimator runs vs. an exhaustive calculation on various data sets.

Figure 3: A histogram depicting the distance from the actual compression ratio for 300 runs of the macro-scale test.

this is generally free space that will be filled in the fu- ture, and we do not want to over-estimate the effective- ness of compression by including zero blocks that com- press extremely well. Further, zero blocks generally do not take up actual space on modern storage systems due to thin provisioning. The performance of the estimator is highly dependent on the speed of the host machine (the tests were run on various x86 machines with ac- cess to the relevant storage), its connection to the storage, and the amount of parallelism supported by the storage (e.g., a single disk does not benefit from multi-threading, whereas RAID does). One last factor affecting perfor- mance is the fraction of zero blocks in the system. Zero blocks are not counted for the estimation, and therefore many more blocks need to be sampled in sparse volumes than in fuller volumes to achieve the required number of samples. For example, in a volume that is 90% empty, one needs to sample approximately 10x samples in order to find x non-zero blocks.

The object interface implementation takes as input a list of objects and their sizes. With such an interface, there is no issue with zero blocks.

We have tested our implementations on numerous data samples from active real-world machines to evaluate their speed and validate their accuracy. Table 2 presents a partial list of volumes on which our estimator was tested. They include several development machines run-

Figure 4: Three independent executions of the estimator con- verge on the true compression ratio as more samples are col- lected. The boundaries show the accuracy guarantees for each sample size.

ning Linux, and two hypervisors with many virtual ma- chine images that serve as a test bed for a large research project. In addition, we ran tests on an artificial file repos- itory containing data from various applications, includ- ing, among others geo-seismic data, compressed and en- crypted data, and databases to show that the estimator manages to handle highly heterogeneous data with vary- ing compression rates (estimations on homogeneous data is far less challenging). All estimator tests ran within 3 minutes, while exhaustive tests ranged from half an hour to over five hours. Estimator performance greatly im- proves when running on a stronger machine (such as the hypervisors). The difference in running times between the two hypervisors is solely due to the higher fraction of zero blocks in the second machine. The best performance was achieved with RAID5 volumes, which benefit from multi-threading (all tests ran with 10 threads). This is ex- tremely effective when running on enterprise storage sys- tems (in such environments our estimator typically ran in well under one minute).

All tests were run with a minimum of 3,100 samples, enough to ensure an accuracy of 5.2% with confidence of 1 in 10 million (10−7). The error in all tests was far lower than that, as can be seen by comparing the compression ratio achieved by the estimator with that of an exhaustive run. This is what we expect, as our analysis predicts that

USENIX Association 11th USENIX Conference on File and Storage Technologies (FAST ’13) 235

Figure 5: Compression ratio histogram for file server volumes. The histogram was sampled as described in Section 3.

the error is normally distributed around the true value, and most tests are likely to be very close to the center (true value). Figure 3 validates this analysis. This depicts 300 executions of the macro-scale test on the same data set and the result is a Gaussian distribution with nearly all of the mass is within the 1% boundaries. Figure 4 shows the convergence of three estimator executions as the number of samples increases. Theoretical accuracy bounds are shown as well, and the runs are well within these boundaries at all times.

Note that for the object interface, our sampling tech- nique is affected by some implementation quirks in how zlib flushes the compressed data. Rather than modifying zlib, we give an external estimation that incurs a constant shift in the results of just over 1% (the estimator’s results are slightly more pessimistic). This shift is noticeable in the object repository results in presented in Table 2.

4 Micro-Scale Compressibility The decision to enable or disable compression at the level of an entire volume or file system can be too coarse- grained. Volumes containing data with varying levels of compressibility are common [16]. Consider docu- ments with text and graphics; text is highly compress- ible, but graphics are typically pre-compressed. Many other examples are available: databases containing em- bedded BLOBs, virtual machine images, mail data files containing attachments, and Web server data containing both text and graphics.

We have identified many real-world use cases where compressing an entire volume would provide good ca- pacity savings, although it contains a substantial amount of incompressible data. Figure 5 depicts examples of some real-world compression ratio histograms: two vol- umes from a file server (from the 42 volumes aggre- gately described in Table 3), as well as two hypervisor volumes and two development volumes (described in Ta-

ble 2). The horizontal axis shows the compression ratio bins (lower is better), and the vertical axis denotes the percentage of samples with a given compression ratio. “Hypervisor 2” and “Development 3” are examples of volumes where most of the data is compressible, and so we would like to compress all data written to them. On the other hand, the other volumes shown contain much compressible data, but also at least 20% incompressible data. One would like to benefit from the capacity reduc- tion of compression on such volumes, but also to manage the compression resources intelligently—compress data where compression provides a benefit, but skip the com- pression wherever it hardly achieves any space reduction.

The granularity at which we work is of single writes to the storage system. While these vary substantially in size, we focus on writes of size 8KB, 16KB and 32KB which are typical in primary storage systems. The most challenging case is of smaller writes (i.e., 8KB) where typically the overheads are higher compared to having few larger writes, and it is harder to evaluate compress- ibility without reading a majority of the write buffer.

The test data: The analysis of the micro-scale solu- tion presented in this section is based on three data sets, whose characteristics are summarized in Table 3. The file server data set contains home or project directories owned by different users, stored in 42 different back- end volumes. The VM images data set is stored on eight back-end volumes. The file server and VM images data sets were sampled from active primary storage using the sampling techniques described in Section 3. The bench- mark data set was artificially gathered to include many types of data with varying compression properties to test our algorithms. It includes images, documents (txt, csv, doc, xml, html, xls, pdf, ps), database files, VMWare im- ages, geo-seismic data, call detail records, archival data,

236 11th USENIX Conference on File and Storage Technologies (FAST ’13) USENIX Association

Data Set Total Size Compressed Size Compression Saving Zero Chunks Comments File server 37TB 15.2TB 17.5TB 4.6TB 42 volumes, 144K samples VM images 6.7TB 1.2TB 1.2TB 4.3TB 8 volumes, 22.9K samples Benchmark 300GB 122.8GB 161.8GB None exhaustive scan

Table 3: Data sets characteristic summary.

compressed and encrypted files, and others.

4.1 Two Basic Approaches We consider two approaches to testing compressibility: Prefix estimation: A common method to estimate com- pression for files or large data chunks is to divide the data into segments and estimate by compressing one of the segments, typically the first one. Such an approach was suggested in [3] albeit at a different scale (consider com- pressing the first 1MB of each file). The decision to com- press the data is based solely on the compressibility of the selected segment, and assumes that the sample is rep- resentative of the whole. Prefix estimation does not incur performance overheads when we decide to compress the data, as compressing the prefix is not wasted work. How- ever, compressing the prefix is very wasteful when the sample is incompressible and we decide not to compress; not only will the compressed version of the sample not be used, but compression consumes the most resources when data is incompressible, as we have shown in in Fig- ure 1. Another glaring shortcoming of this approach is in handling data that changes noticeably from its prefix (consider, for example data with a special header). Heuristic based estimation: This approach refers to col- lecting simple heuristic parameters over the chunk that tend to characterize its compressibility and making the decision solely based on these heuristics. The heuristics must be extremely efficient, much more efficient than ac- tually compressing the chunk. Due to this performance restriction, we collect our heuristics on random samples from the chunk rather than the whole chunk. Note that this efficiency improvement still circumvents the prob- lem of the prefix method (a buffer that changes in the middle) since it samples the entire chunk.

An example of such a natural indicator for data com- pressibility is the byte entropy for the data [19]. Byte entropy is an accurate estimation of the benefits of an op- timized Huffman encoding, and compression is generally more effective on buffers with lower entropy. Figure 6 depicts this correlation for the file server data set, where entropy and compression ratio were computed for 8KB data blocks. For this data set, an entropy of less than 5.5 typically predicts that the data will be compressible (compression ratio less than 0.8). However, the corre- lation is not ideal, as there is compressible data whose entropy is higher than 5.5. This is mainly due to the fact that entropy does not measure repetitions in the data, and therefore cannot capture all aspects of compression.

We have developed an estimation method that uses var-

Figure 6: Byte Entropy as a function of the compression ratio of the file server data set.

ious heuristics to provide a more precise indication of compressibility, which we present in Section 4.2. In Sec- tion 4.5, we show how to combine this method with pre- fix estimation to exploit the best properties of each of the two approaches.

4.2 Our Heuristics In this section we present our heuristic approach to deter- mining compressibility. We considered a static threshold for the compression ratio above which data should not be compressed: 0.8. This threshold represents the trade-off between resource utilization and compression savings, and can be easily changed according to the amount of resources and expected load on the storage system. We use the following heuristics in our decision algorithm: Data coreset size: We define the coreset to be the set of unique symbols that compose the majority (e.g., 90%) of the data. Logically, if the size of the coreset is small, we can expect benefits from the Huffman encoding as well as more repetitions and therefore the data is potentially a good candidate for compression. In contrast, a large coreset size indicates lower potential for obtaining bene- fits from compression. Byte entropy: As mentioned above, byte entropy is a good indicator for compressibility of certain types. Pairs distance from random distribution: The L2 dis- tance heuristic looks at pairs of symbols and the proba- bility that the two symbols appear consecutively in the coreset. The distance is calculated as the (Euclidian) dis- tance between the vector of the observed probability of a pairs of symbols appearing in the data, and the vector of the expected pair probabilities based on the (single) symbol histogram, assuming no correlation between sub- sequent pairs of symbols. The equation for calculating

USENIX Association 11th USENIX Conference on File and Storage Technologies (FAST ’13) 237

the L2 is as follows:

∑ ∀a̸=b∈coreset

( freq(a) ∗ freq(b)

size of sample2 − freq(a, b)

number of pairs

)2

This heuristic aims at distinguishing between randomly ordered data and data that contains repetitions. This al- lows us to distinguish between compressible and non- compressible data in cases where single byte heuristics such as entropy and coreset fails to do so.

Figures 7, 8 and 9 show each of the heuristics’ po- tential thresholds for differentiating between compress- ible and incompressible data based on the data sets de- scribed in Table 3. We use this information to formulate the thresholds used in our algorithm.

In Figure 7 we see that for all three data sets, coreset size is directly related to compressibility. Based on this data we can set conservative values for when to compress (coreset size smaller than 50) and when not to compress (coreset size larger than 200). Figure 8 shows that an en- tropy lower than 6 is generally a good indication for com- pressible data. However, there is a portion of data with high entropy that compresses well. Figure 9 shows the distance from random distribution heuristic for data with an entropy higher than 5.5. This metric can be used to- gether with entropy to further differentiate between com- pressible and incompressible data. Most of the incom- pressible data has a distance of less than 0.001 from the random distribution, while most of the compressible data has distance greater than 0.001 from it.

4.3 Implementation The micro-scale approach works inside the storage I/O path and must incur very little overhead. To achieve the required low overhead we actually compute the heuris- tics on a sampled subset of the write buffer. In fact, this practice was also used when creating Figures 7, 8 and 9.

The size of the sample is based on a statistical sam- pling rule of thumb. It is common to perform sampling tests as long as the average number of elements in each bin (i.e., symbol) is at least five (for example, Chi-square tests). Instead of five, we choose eight as a more conser- vative value to obtain more accurate results. If the data contains the maximum number of symbols, which is 256, we obtain a sample size bound of 2048. Therefore, we sample at most 2KB of data per write buffer: 16 consec- utive bytes from up to 128 randomly chosen locations. In practice, in most cases data write operations include far less than 256 unique symbols, allowing us to sample less data and improve the run time of the heuristics.

Our solution framework is composed of (1) random sampling a small subset of the write operation data, and (2) providing a recommendation on whether to compress

data size

compress

compress

compress

compress

store

store

(1)

(2)

close

small

minimal size

large

small

(3)

(4) entropy

coreset size

symbol set size

distance from random

low

Huffman only

compressstore

compress

distance from random (5b)

(5a)

medium

close far

Figure 10: The algorithm for estimating data compressibility using heuristics.

or not compress the data based on the heuristics in Sec- tion 4.2. The recommendation algorithm is outlined in Figure 10. The algorithm flow is from top to bottom, and at each step one parameter or heuristic is examined. A recommendation is made if the heuristic satisfies the given thresholds. The horizontal arrows represent rec- ommendations and the downward arrows represent mov- ing to the next heuristic computation. The vertical bars represent the thresholds for making the recommenda- tion at each step. The algorithm is designed for speed, the heuristics are ordered according to their computation time, from light to heavy calculation and a recommen- dation is made as early as possible, reducing the compu- tation overhead. The algorithm is outlined top to bot- tom follows: (1) Small amounts of data (smaller than 1KB) should always be compressed, as calculating the heuristics will generally take longer than compressing. (2) If the total number of symbols in the data is very small, e.g., 50, then compress. (3) If the coreset size is very small (e.g., smaller than 50), compress, and if it is very large (e.g., larger than 200), store (do not com- press). (4) If the entropy is reasonably low (e.g., smaller than 5.5), compress. (5a) Data with medium entropy (e.e., 5.5–6.5) and a small distance from random distribu- tion (e.g., 0.001) should be stored; for higher distances, compress. (5b) Data with higher entropy (e.g., greater than 6.5) and a small distance from random distribution

238 11th USENIX Conference on File and Storage Technologies (FAST ’13) USENIX Association

0 50 100 150 200 2500

20%

40%

60%

80%

100%

Coreset size

C D

F of

s am

pl es

compressible data incompressible data 44.8K samples

99.5K samples

(a) File server data set.

0 50 100 150 200 2500%

20%

40%

60%

80%

100%

Coreset size

C D

F of

s am

pl es

compressible data incompressible data

13940 samples

8984 samples

(b) VM images data set.

0 50 100 150 200 2500%

20%

40%

60%

80%

100%

Coreset size

C D

F of

s am

pl es

compressible data incompressible data

25.9M samples

8.7M samples

(c) Benchmark data set.

Figure 7: Coreset size CDFs for compressible and incompressible data.

0 2 4 6 80%

20%

40%

60%

80%

100%

Entropy

C D

F of

s am

pl es

compressible data incompressible data

(a) File server data set.

0 2 4 6 80%

20%

40%

60%

80%

100%

Entropy

C D

F of

s am

pl es

compressible data incompressible data

(b) VM images.

0 2 4 6 80%

20%

40%

60%

80%

100%

Entropy

C D

F of

s am

pl es

compressible data incompressible data

(c) Benchmark data set.

Figure 8: Entropy CDFs for compressible and incompressible data.

0 0.005 0.01 0.015 0.020%

20%

40%

60%

80%

100%

Distance from random data

C D

F of

s am

pl es

compressible data incompressible data

(a) File server data set.

0 0.005 0.01 0.015 0.020%

20%

40%

60%

80%

100%

Distance from random data

C D

F of

s am

pl es

compressible data incompressible data

(b) VM images data set.

0 0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.040%

20%

40%

60%

80%

100%

Distance from random data

C D

F of

s am

pl es

compressible data incompressible data

(c) Benchmark data set.

Figure 9: Distance from random distribution CDFs for compressible and incompressible data with entropy higher than 5.5.

(e.g., 0.001) should not be compressed; data relatively far enough from random distribution (e.g., 0.02) should be compressed. Data in between the distance thresholds should be compressed using Huffman coding; it provides a balance when the heuristics do not provide a clear de- cision. We can see that the majority of the data for which the heuristics recommend to use Huffman coding falls into the incompressible bins, or very close to the incom- pressible bins.

4.4 Evaluation We evaluated the run time and compression performance of the prefix estimation and the heuristics method on a dual processor Intel Xeon L5410 (2.33Ghz) Linux server. Note that our implementation is single threaded and did not exploit the system parallelism. The methods’ output is either to compress the data (we used zlib level 1 for this) or store it without compression (using zlib level 0 to copy it). The heuristic method can also recommend using Huffman coding only (using the appropriate zlib flag). Our measurements do not include the time for per- forming the disk read and write operations, as our focus

is on the CPU resources for compression and the result- ing capacity impact. The evaluation focuses on two cat- egories: (1) accuracy of compressibility estimation, and (2) time and capacity impacts.

Figure 11 shows the heuristic method’s recommenda- tions for each compression ratio bins for the three test data sets listed in Table 3. We see that the overwhelming majority of the incompressible data with compression ra- tio higher than 0.9 are identified as such. Compressible data (with compression rate under 0.8) is identified al- most always as compressible. For compression ratios be- tween 0.8 and 0.9 the recommendations are mixed. Re- call that the intention was to categorize such data as in- compressible but data in this range turns out to be difficult to identify accurately (especially for 8KB blocks).

Next we examine the run time of the different methods as tested on 8KB blocks. Figure 12 shows the run time of the prefix method on a 1KB prefix, of the heuristic method and this is contrasted with compression time of the entire 8KB data block. The heuristic approach is very fast both for data with very good compression and for highly non-compressible data. For mid-way data, with

USENIX Association 11th USENIX Conference on File and Storage Technologies (FAST ’13) 239

(a) File server data set. (b) VM images data set. (c) Benchmark data set.

Figure 11: The heuristic approach recommendation by compression ratio for 8KB data blocks.

Figure 12: Comparison of average compression time of com- pressing a 1KB prefix, compressing the whole 8KB data, and the heuristics approach for data of various compression ratio.

Figure 13: Time and capacity impact of compressing 8KB data blocks from the benchmark data set using prefix estimation with different compression ratio compressibility thresholds.

compression ratios of 0.4 through 0.9, it needs to review all (or almost all) the heuristics to reach a recommenda- tion and thus requires a longer running time. For all com- pression ratios, the heuristic approach is much faster than running the prefix estimation. However, for compressible data (whenever the correct decision is made) the prefix estimation essentially comes for free, as we can just con- tinue to compress the data from the 1KB point. For in- compressible data, on the other hand, the prefix compres- sion estimation is plainly an overhead. We can therefore conclude that that the prefix method is slightly better for compressible data, while the heuristic method is faster by 2X to 6X for non-compressible data.

Figure 13 focuses on the prefix method and exam-

ines the impact of selecting different compression ratio thresholds for differentiating between compressible and incompressible 8KB data blocks. For each such choice we depict the impacts on capacity and CPU time as mea- sured on the benchmark data set. The horizontal axis is the threshold used to identify incompressible data; for example 0.9 means that if the compression ratio of the prefix was higher than 0.9 the data will not be com- pressed. Selecting a threshold of 0.99 inflates the ca- pacity by 3.6% yet utilizes only 92% of the CPU time required had all the data been compressed.

In Table 4 we compare the CPU and capacity impacts of the the heuristic method versus the prefix estimation when compressing block sizes of 8KB, 16KB and 32KB from our benchmark data set. For the prefix estimation we present two different thresholds: the first matches the capacity impact of the heuristic method and then the CPU savings can be measured on equal terms. The second matches the CPU savings of the heuristic and then the capacity can be examined. Note that there was no sin- gle threshold for the prefix estimation that could match or surpass both the CPU time and capacity overhead.

The heuristic approach manages to consistently limit the impact on capacity (about 2%) for all block size and shows a reduction of CPU time as the block sizes in- crease. On the other hand, the prefix estimation needs to sacrifice either capacity or CPU time to match the heuris- tics approach. To match the CPU time, the prefix estima- tion loses between 10.4% (for 8KB) to 4.4% (for 32KB) of capacity compared to only about 2%. To match the 2% capacity overhead, the prefix estimation speedup is between 92% (for 8KB) and 74% (for 32KB) compared to a speedup of between 85% (for 8KB) and 65% (for 32KB) when using the heuristic approach.

It is important to note that the benchmark data set con- tain about 30% incompressible data and 70% compress- ible data (the compression ratio histogram are available in Figure 5). For data sets with higher portion of in- compressible data, the heuristics approach will provide greater benefit and will in fact increase the performance gap between the prefix estimation and the heuristics ap- proach. On the other hand, as the portion of compressible data grows, the prefix method will become more suitable.

240 11th USENIX Conference on File and Storage Technologies (FAST ’13) USENIX Association

Block Method Capacity CPU Time Size Overhead

8K Heuristics 2.0% 85% 1K prefix w/ 0.99 3.6% 92% 1K prefix w/ 0.92 10.4% 85%

16K Heuristics 2.3% 74% 2K prefix w/ 0.95 1.8% 86% 2K prefix w/ 0.87 7.0% 74%

32K Heuristics 2.3% 65% 4K prefix w/ 0.88 2.2% 74% 4K prefix w/ 0.82 4.4% 65%

Table 4: Comparing CPU time ratio and capacity impact of prefix estimation versus the heuristics approach on the bench- mark data set. 4.5 Putting it All Together While the heuristic approach has noticeable advantages when there is a significant amount of incompressible data on the storage volume, this is not the case when nearly all of the data is compressible. In such cases the heuristic only adds an overhead to the run time without any gain.

This calls for an adaptive on-demand deployment of the estimation techniques. We propose to employ both methods, the prefix estimation and the heuristics method, within a single solution. Basically, employ the prefix method when all or most of the data is compressible, but switch to the heuristics approach whenever enough non-compressible data is encountered. This mixed ap- proach introduces only minimal overheads when han- dling mostly compressible data, but will provide great CPU relief once incompressible data is encountered.

Moreover, consider workloads for which there is a clear distinction between times when incompressible data is written to periods of compressible data writes. For ex- ample, periods during which encrypted or zipped data are written. In such scenarios, switching back and forth be- tween prefix estimation and heuristics will deliver opti- mal performance.

An additional opportunity for adaptiveness is in the heuristics thresholds. We strived to collect as many real world data types in our benchmark data set and suggested thresholds that perform well on the various data sets. However, we suggest that the thresholds be adaptive to the data encountered and fine tuned during execution to optimize usage of both capacity and CPU time.

5 Related Work NetApp provides the Space Savings Estimation Tool (SSET) to estimate the benefits of deduplication and compression on a portion of a file system. Whereas our macro-scale solution provides accuracy guarantees nec- essary for making decisions with confidence, NetApp claims that “in general, the actual results are within ±5% of the space savings that the tool predicts” [18].

Estimating overall compression savings when com- pressing each file has been explored in [3]. The au-

thors experimented with compressing a set of randomly- sampled files, but saw that this resulted in a high vari- ance between sample sets. The method they chose is to compress the first megabyte of the largest files in the file system, which comprise some percentage of the total ca- pacity. Their method requires a full file system scan and sort, and results show that between 0.02% and 1.93% of the file system needs to be compressed for stable results. They do not provide any statistical guarantees.

There is a procedure in Microsoft SQL Server called sp estimate data compression savings that esti- mates the compression savings for a given table [17]. Lit- tle is stated about its implementation, other than that a sample is compressed. No accuracy guarantees are given, and some users report up to a 20% error [1].

Harnik et al. discuss how to piggyback compression estimation to a process of estimating deduplication ra- tios [10]. However, the authors do not discuss a stand- alone algorithm for compression estimation.

Several works attempt to determine the most suitable compression algorithm for a given chunk of data. One such work concluded that the standard deviation of the bytes is a good predictor for Huffman encoding effec- tiveness, while the standard deviations of the difference of consecutive bytes and XORed value of consecutive bytes can be used to predict the effectiveness of 12-bit LZW [4]. However, statistics were gathered on entire files, and only correlations were shown, with no discus- sion on performance or using the metrics together to de- termine compression effectiveness. Another uses genetic programming to attempt to predict exact compression ra- tios using the byte frequency distribution and features ex- tracted from the data stream [14]. This method is not suit- able for our use case, as it spends a significant amount of time finding an exact answer, whereas we require a fast indication of compression effectiveness.

6 Concluding Remarks We have shown how to effectively utilize storage system resources for real-time compression by efficiently and accurately filtering out incompressible data. The tech- niques we demonstrated allow the storage system to in- vest its valuable resources only in data that compresses well. Rather than compressing incompressible data, the resources are now free to compress other data as well as to serve I/O requests, thus improving both cost savings and performance.

Acknowledgments: We would like to thank our colleagues at the IBM Real-time Compression team and the Haifa Research lab for their involvement and support of this work. Specifi- cally we thank Jonathan Amit, Lilia Demidov, Olga Dodin, Nir Friedman, George Goldberg, Nir Halowani, Chaim Koifman, Ido Levy, Sergey Marenkov, Dalit Naor, Orit Nissan, Tzahi Shahak and Assaf Yaari.

USENIX Association 11th USENIX Conference on File and Storage Technologies (FAST ’13) 241

References [1] E. Bertrand. Playing with page compression -

for real. http://sqlblog.com/blogs/ aaron_bertrand/archive/2009/12/29/ playing-with-page-compression-for-real. aspx.

[2] Michael Burrows, Charles Jerian, Butler W. Lamp- son, and Timothy Mann. On-line data compression in a log-structured file system. In Barry Flahive and Richard L. Wexelblat, editors, ASPLOS, pages 2–9. ACM Press, 1992.

[3] C. Constantinescu and M. Lu. Quick Estima- tion of Data Compression and De-duplication for Large Storage Systems. In Proceedings of the 2011 First International Conference on Data Compres- sion, Communications and Processing, pages 98– 102. IEEE, 2011.

[4] W. Culhane. Statistical Measures as Predictors of Compression Savings. The Ohio State University, Department of Computer Science and Engineering, Honors Thesis, May 2008.

[5] P. Deutsch and J. L. Gailly. Zlib Compressed Data Format Specification version 3.3. Technical Report RFC 1950, Network Working Group, May 1996.

[6] EMC. EMC Data Compression: A Detailed Re- view. Technical Report h8045.1, EMC, September 2010.

[7] J. L. Gailly and M. Adler. The Zlib home page. www.gzip.org/zlib, 1998.

[8] J. Gantz and D. Reinsel. 2009 Digital Universe Study: As the Economy Contracts, the Digital Uni- verse Expands. Technical Report White paper, In- ternational Data Corporation, May 2009.

[9] J. Gantz and D. Reinsel. 2011 Digital Universe Study: Extracting Value from Chaos. Technical Re- port White paper, International Data Corporation, June 2011.

[10] D. Harnik, O. Margalit, D. Naor, D. Sotnikov, and G. Vernik. Estimation of Deduplication Ratios in Large Data Sets. In Proceedings of the 18th In- ternational IEEE Symposium on Mass Storage Sys- tems and Technologies (MSST), pages 1–11. IEEE, 2012.

[11] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 301(58):13– 30, 1963.

[12] D. A. Huffman. A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the Institute of Radio Engineers, 40(9):1098–1101, September 1952.

[13] IBM. IBM Comprestimator Utility V1.2.0.2 - United States. http://www-01.ibm. com/support/docview.wss?uid= ssg1S4001012.

[14] A. Kattan and R. Poli. Genetic-Programming Based Prediction of Data Compression Saving. Lecture Notes in Computer Science, 5975/2010:182–193, 2010.

[15] D. Kay. Oracle Solaris ZFS Storage Manage- ment. Technical Report 507914, Oracle Corpora- tion, November 2011.

[16] M. Lu, D. Chambliss, J. Glider, and C. Constanti- nescu. Insights for Data Reduction in Primary Stor- age: a Practical Analysis. In Proceedings of the 5th Annual International Systems and Storage Confer- ence (SYSTOR 2012). ACM, 2012.

[17] Microsoft. sp estimate data compression savings (Transact-SQL). http://msdn.microsoft. com/en-us/library/cc280574.aspx.

[18] S. Moulton and C. Alvarez. NetApp Data Compres- sion and Deduplication Deployment and Implemen- tation Guide: Data ONTAP Operating in Cluster- Mode. Technical Report TR-3966, NetApp, June 2012.

[19] C. E. Shannon. A Mathematical Theory of Commu- nication. Bell System Technical Journal, 27:379– 423, 1948.

[20] K. Srinivasan, T. Bisson, G. Goodson, and K. Voru- ganti. iDedup: Latency-aware, inline data dedupli- cation for primary storage. In Proceedings of the 10th USENIX conference on File and Storage Tech- nologies (FAST 2012). USENIX Association, 2012.

[21] Nimble Storage. Nimble Storage: Engineered for Efficiency. Technical Report WP-EFE-0812, Nim- ble Storage, 2012.

[22] J. Tate, B. Tuv-El, J. Quintal, E. Traitel, and B. Whyte. Real-time Compression in SAN Volume Controller and Storwize V7000. Technical Report REDP-4859-00, IBM, August 2012.

[23] R. Tretau, M. Miletic, S. Pemberton, T. Provost, and T. Setiawan. Introduction to IBM Real-time Com- pression Appliances. Technical Report SG24-7953- 01, IBM, January 2012.

[24] J. Ziv and A. Lempel. A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory, 23(2):337–343, May 1977.

[25] J. Ziv and A. Lempel. Compression of Individ- ual Sequences via Variable-Rate Coding. IEEE Transactions on Information Theory, 24(5):530– 536, September 1978.