Compressing data in line using weighted compression budgets

A technique for performing in-line compression includes receiving data into a data log that temporarily holds the data and aggregating the data into batches, where each batch includes multiple blocks of received data. For each batch of data, a storage system performs a compression operation, which proceeds block-by-block, compressing each block and comparing a total compressed size of all blocks compressed so far against a budget. The storage system increments the budget for successive blocks, such that a per-block budget is greater for a first block in the batch than it is for a last block in the batch, thus allowing earlier blocks to meet budget even if they are relatively incompressible.

BACKGROUND

Data storage systems are arrangements of hardware and software that include storage processors coupled to arrays of non-volatile storage devices, such as magnetic disk drives, electronic flash drives, and/or optical drives, for example. The storage processors service storage requests, arriving from host machines (“hosts”), which specify files or other data elements to be written, read, created, deleted, and so forth. Software running on the storage processors manages incoming storage requests and performs various data processing tasks to organize and secure the data elements stored on the non-volatile storage devices.

Some data storage systems employ data compression to improve storage efficiency. For example, a software program running on a data storage system may read data from disk, compress the data, and write the compressed data back to disk. To read data that has been compressed, the program may work in the opposite direction, e.g., by fetching compressed data from disk, decompressing the data, and presenting the decompressed data to a requesting program.

SUMMARY

Data storage systems that employ compression generally do so in the background, such as by running a background process or daemon that acts upon already-stored data. Performing compression in the background may result in an over-commitment of storage resources, however, as more storage space than necessary may be required to accommodate initial writes. Also, background compression may entail reading previously-written data from persistent storage and rewriting compressed data back to persistent storage, resulting in a significant increase in disk traffic.

Recent improvements in data storage systems perform data compression in line with storage requests, such that incoming data are compressed prior to the first time they are stored on disk. This arrangement helps to avoid over-commitment of storage resources and to avoid increases in disk traffic.

As in-line compression takes place in real time, or nearly so, there is a need for in-line compression to proceed quickly and efficiently, so as not to interfere with other real-time activities. One approach has been to cache incoming data and to compress the data in batches of several blocks each. A storage system compresses a first block in the batch and tests the compressed block to determine whether its compressed size falls within an initial budgeted size. If it does, the storage system proceeds to the next block in the batch and repeats the same activities, doubling the budgeted size and confirming that both compressed blocks together fall within the new budgeted size. Operation proceeds in this fashion, with additional blocks being compressed and the total compressed size being tested against an increasing budget, with the budget increasing for each block as a multiple of the initial budgeted size.

The above-described approach can be improved, however, by allowing earlier-tested blocks in a batch to compress to larger sizes than the prior budgeting arrangement would allow, as long as all blocks in the batch can be compressed to a target size for the batch as a whole. For example, an improved technique for performing in-line compression includes receiving data into a data log that temporarily holds the data and aggregating the data into batches, where each batch includes multiple blocks of received data. For each batch of data, the data storage system performs a compression operation, which proceeds block-by-block, compressing each block and comparing a total compressed size of all blocks compressed so far against a budget. The storage system increments the budget for successive blocks, but the amount of budget per-block is larger for a first block in the batch than it is for a later block in the batch. In this manner, the storage system is made less sensitive to compressibility of initial blocks in a batch, allowing the batch as a whole to be compressed and stored in compressed form even if initial blocks in the batch are relatively incompressible. The improved technique therefore enables more data to be compressed in line than did the prior technique, without sacrificing the efficiency of real-time activities.

Certain embodiments are directed to a method of storing data. The method includes receiving data into a data log of a data storage system, the data log providing temporary storage for the data in units of blocks, aggregating blocks of the data in the data log into multiple batches, each batch including multiple blocks, and performing a compression operation on each batch. Performing the compression operation on each batch includes processing a current block in the batch by (i) compressing the current block and (ii) performing a testing operation for the current block. The testing operation is configured to (a) produce a first result in response to determining that an accumulated compressed size of all compressed blocks in the batch processed so far exceeds a compression budget and (b) produce a second result in response to determining that the accumulated compressed size of all compressed blocks in the batch processed so far does not exceed the compression budget. The compression operation proceeds to a next block in the batch in response to the testing operation producing the second result for the current block. Increasing the compression budget is performed such that a per-block value of the compression budget is greater when testing a first block in the batch than it is when testing a later block in the batch. In response to the testing operation producing the second result for all blocks in a batch, the method still further includes storing the data of all blocks in the batch in compressed form in a set of non-volatile storage devices of the data storage system.

Other embodiments are directed to a data storage system constructed and arranged to perform a method of storing data, such as the method described above. Still other embodiments are directed to a computer program product. The computer program product stores instructions which, when executed on control circuitry of a data storage system, cause the data storage system to perform a method of storing data, such as the method described above.

The foregoing summary is presented for illustrative purposes to assist the reader in readily grasping example features presented herein; however, the foregoing summary is not intended to set forth required elements or to limit embodiments hereof in any way. One should appreciate that the features described above can be combined in any manner that makes technological sense, and that all such combinations are intended to be disclosed herein, regardless of whether such combinations are identified explicitly or not.

DETAILED DESCRIPTION OF THE INVENTION

Embodiments of the invention will now be described. It should be appreciated that such embodiments are provided by way of example to illustrate certain features and principles of the invention but that the invention hereof is not limited to the particular embodiments described.

An improved technique for performing in-line compression includes receiving data into a data log and aggregating the data into batches, where each batch includes multiple blocks of received data. For each batch, the data storage system performs a compression operation, which proceeds block-by-block, compressing each block and comparing a total compressed size against a budget. The storage system increases the budget for successive blocks, but does so such that the budget per block for successive blocks decreases. In this manner, the storage system is made less sensitive to incompressibility of initial blocks in a batch.

FIG. 1shows an example environment100in which embodiments of the improved technique hereof can be practiced. Here, multiple host computing devices (“hosts”)110access a data storage system116over a network114. The data storage system116includes a storage processor, or “SP,”120and storage180. In an example, the storage180includes multiple disk drives, such as magnetic disk drives, electronic flash drives, optical drives, and/or other types of drives.

The data storage system116may include multiple SPs like the SP120(e.g., a second SP120a). In an example, multiple SPs may be provided as circuit board assemblies, or “blades,” which plug into a chassis that encloses and cools the SPs. The chassis has a backplane for interconnecting the SPs, and additional connections may be made among SPs using cables. It is understood, however, that no particular hardware configuration is required, as any number of SPs may be provided, including a single SP, and the SP120can be any type of computing device capable of processing host IOs.

The network114may be any type of network or combination of networks, such as a storage area network (SAN), a local area network (LAN), a wide area network (WAN), the Internet, and/or some other type of network or combination of networks, for example. The hosts110may connect to the SP120using various technologies, such as Fibre Channel, iSCSI, NFS, and CIFS, for example. Any number of hosts110may be provided, using any of the above protocols, some subset thereof, or other protocols besides those shown. As is known, Fibre Channel and iSCSI are block-based protocols, whereas NFS and CIFS are file-based protocols. The SP120is configured to receive IO requests112according to block-based and/or file-based protocols and to respond to such IO requests112by reading or writing the storage180.

The SP120includes one or more communication interfaces122, a set of processing units124, and memory130. The communication interfaces122include, for example, SCSI target adapters and network interface adapters for converting electronic and/or optical signals received over the network114to electronic form for use by the SP120. The set of processing units124includes one or more processing chips and/or assemblies. In a particular example, the set of processing units124includes numerous multi-core CPUs. The memory130includes both volatile memory (e.g., RAM), and non-volatile memory, such as one or more ROMs, disk drives, solid state drives, and the like. The set of processing units124and the memory130together form control circuitry, which is constructed and arranged to carry out various methods and functions as described herein. Also, the memory130includes a variety of software constructs realized in the form of executable instructions. When the executable instructions are run by the set of processing units124, the set of processing units124are caused to carry out the operations of the software constructs. Although certain software constructs are specifically shown and described, it is understood that the memory130typically includes many other software constructs, which are not shown, such as an operating system, various applications, processes, and daemons.

As further shown inFIG. 1, the memory130“includes,” i.e., realizes by operation of software instructions, a data log140and a file system170. The data log140includes a buffer142, an aggregator150, and an in-line compressor160.

In example operation, hosts110issue IO requests112to the data storage system116to perform reads and writes of one or more data objects stored in the data storage system116. SP120receives the IO requests112at communication interface(s)122and passes them to memory130for further processing. Some of the IO requests112specify data writes112W. Data log140receives data writes112W and stores data specified therein in blocks144of buffer142. In an example, blocks144are storage units of uniform size, such as 4 KB, 8 KB, and so forth. In a further example, the size of blocks144may correspond to the size of allocation units (AUs) of the file system170, where an AU is the smallest unit of storage that the file system170can allocate. In some examples, buffer142is arranged as a circular buffer having a head and a tail (not shown). The data log140may append blocks144of data specified by newly-arriving write requests112W to the head of buffer142and may flush blocks144from the tail of buffer142, for further processing by the file system170. A flushing operation162is illustrated.

In an example, the buffer142is implemented in DRAM (Dynamic Random Access Memory), the contents of which are mirrored between SPs120and120aand persisted using batteries. In an example, SP120may acknowledge writes112W back to originating hosts110once the data specified in those writes112W are stored in the buffer142and mirrored to a similar buffer on SP120a.

As the buffer142of data log140accumulates data in blocks144, aggregator150assembles blocks144in batches152. Two batches152A and152B are shown, each having ten blocks. However, batches may include other numbers of blocks and different batches may include different numbers of blocks.

In-line compressor160accesses batches152from aggregator150and performs a compression operation on each batch152. For example, each compression operation compresses a first block144in the batch152and tests the resulting compressed block to determine whether its compressed size falls within a budgeted size. If it does, the in-line compressor160proceeds to the next block in the batch152and repeats the same activities, increasing the budgeted size and confirming that both compressed blocks together fall within the new budgeted size. Operation proceeds in this fashion, with additional blocks144being compressed and the total compressed size being tested against the increasing budget. However, the budget increases non-uniformly, by smaller amounts each time it is increased. Thus, for example, the budget may start out relatively large for the first block but may increase by smaller amounts for each successive block. By the time later blocks in the batch are tested, the per-block budget has become smaller than it was for the first block. This arrangement allows earlier-tested blocks to be poorly compressible without exceeding the budget.

In some examples, the in-line compressor160is configured to flush data from the data log140to the file system170in batches152, with each batch152either being entirely compressed or not being compressed at all. For example, the in-line compressor160may flush batch152A entirely in compressed form, but only if all blocks of batch152A compress within budget. Likewise, the in-line compressor160may flush batch152B entirely in uncompressed form, even if only a single block of batch152B fails to compress within budget. As further shown inFIG. 1, the file system170stores compressed batch152A in storage region172A and stores uncompressed batch152B in storage region172B. These regions172A and172B are backed by physical storage180at locations182A and182B, respectively.

As entire batches152may be flushed either all-compressed or all-uncompressed, the benefits of providing additional budget for initial blocks in a batch152can plainly be seen, as batches with one or two early incompressible blocks can still be candidates for compressed flushing. Entire batches152, which might otherwise be abandoned and left uncompressed, can thus be flushed in compressed form and stored in compressed form, provided that later blocks in those batches are compressible enough that the batches as a whole are able to meet budget.

In some examples, aggregator150assembles batches152based at least in part on data objects. For example, buffer142may accumulate writes that are directed to multiple data objects hosted by the data storage system116. By aggregating based on data objects, the aggregator150tends to group together like types of data in respective batches152. Aggregating based on data objects thus tends to promote consistency in data within each batch152, as all the data in each batch152belongs to the same data object. Consistency in data suggests consistency in compressibility, and this provides a basis for the in-line compressor160to terminate compression of an entire batch based on a failure to meet budget in response to testing any of its blocks.

In some examples, aggregator150also assembles batches152based on logical address into a data object. As is known, data objects have logical address ranges. For example, a file has a logical address range that defines different offsets into the file. Also, a LUN (Logical UNit) may have a logical address range that specifies offsets from a starting point. By aggregating based on logical address, the aggregator150still further tends to group together like types of data in respective batches152.

FIG. 2shows an example compression200operation on a batch152of blocks144. In an example, the compression operation200is performed by the in-line compressor160and may be repeated for each batch152of blocks144aggregated by aggregator150. The particular acts of the compression operation200may be ordered in any suitable way, including performing some acts simultaneously.

At210, an index variable (i) may be set to one and a total size of all compressed blocks in the current batch152(TotSize) may be set to zero. Other implementations may initialize these terms to different values or may use different terms.

At220, a first block144(Blocki) in the batch152is compressed. Blocks144in batch152may be compressed in any order. No special significance is implied by a block being selected as the first block; rather, the first block may be any block144in the batch152.

At230, the compressed size of Blockiis added to TotSize. For example, if Blockiis initially 8 KB and Blockicompresses down to 7 KB, then the compressed size of Blockiwould be 7 KB and TotSize would initially be 7 KB.

At240, a compression budget Biis generated for the current value of i. In the example, shown, the current budget Bi=K*i+K−K*i/N, where N is the number of blocks144in the current batch152and K is a constant equal to a maximum allowed compression ratio for the current batch as a whole. For example, K=0.75 means that the total maximum compression ratio of the batch, assuming all blocks are compressed, must not exceed 75% of the initial, uncompressed size of that batch. As a further example, assume that the current batch has ten blocks (N=10), each being 8 KB in size, and that K=0.75. With these example figures, the overall budget for the batch, assuming that operation proceeds that far, would be 0.75*8 KB*10, or 61,440 bytes. As shown at240, the budget Biis updated for each value of i (i.e., for each iteration of loop202).

Act250designates a testing operation, in which the current TotSize is compared to the current budget Bi. If TotSize exceeds the current budget, the testing operation produces a first value252(Yes). If TotSize is less than or equal to the current budget, the testing operation produces a second value254(No).

If the testing operation produces the second value254, operation proceeds to260, where i is incremented for the next iteration of the loop202. If incrementing i would cause i to exceed N (at270), the compression operation200completes and, at290, the compressed blocks in the current batch are flushed from the data log140, e.g., to the file system170(FIG. 1), where the compressed blocks are eventually placed in storage180, e.g., at location182A. Otherwise, operation returns to220, where a next block144in the current batch152is compressed and the above-described acts are repeated.

For any iteration of the loop202, if the testing operation at250produces the first value252, indicating that the current budget Bihas been exceeded, operation proceeds to280, whereupon the compression operation200may be terminated for the current batch, e.g., without compressing or testing any remaining blocks in the batch. The data log140may then flush the current batch, e.g., entirely in uncompressed form, to the file system170, where the uncompressed data are eventually placed in storage180, e.g., at location182B.

One should appreciate that particular acts of compression operation200may be varied in different embodiments. For example, the calculation of the current budget at240may be performed in a variety of ways. For instance, the budget Bimay be calculated using a logarithmic function, a pseudo-logarithmic function, using a differently-weighted formula, a series of predetermined values, or any other method that provides a greater amount of budget per block for earlier-compressed blocks than for later-compressed blocks in a batch. A per-block compression budget242may be provided as Bi/i. A minimum requirement for any calculation of Bishould ensure that per-block compression budget242is greater for the first block144in a batch than it would be for the last block in that batch. In addition, while the illustrated embodiment updates Bifor each iteration through the loop202, the compression operation200may alternatively update Bion some other basis, such as for every second block, every third block, or even at non-uniform intervals.

In some examples, upon reaching step280, the data log140may salvage already-compressed blocks in the current batch, even though compression does not proceed to remaining blocks in the batch. For example, the data log140may flush already-compressed blocks in the current batch in compressed form, but may flush any remaining blocks in the batch (those which have not been compressed) in uncompressed form.

FIG. 3shows a graph300, which compares uniform budgets310with weighted budgets320. The graph300illustrates block indices (e.g., value of i) along the horizontal axis and budget along the vertical axis. In the example shown, axis lines along the vertical axis indicate block-size increments of budget. For instance, the first axis line above the baseline corresponds to one block increment (e.g., 8 KB), the second axis line corresponds to two block increments (e.g., 16 KB), and so forth.

Uniform budgets310provide a constant amount of budget per block. For example, if the first block (i=1) has a budget of 0.75 block increments (e.g., 6 KB), then the second block (i=2) has a budget of 1.5 block increments (e.g., 12 KB). Likewise, the third block (i=3) has a budget of 2.25 block increments (e.g., 18 KB), and so on, with each i-th block having a budget of 0.75*i block increments. If the uniform budget310were to be used in place of the one shown in240ofFIG. 2, then the compression operation200might terminate if the first or second block was relatively incompressible compared with later blocks.

In contrast, weighted budgets320provide additional budget (see bar graph) for initial blocks to be compressed. For instance, using the expression of act240, a first block can actually “compress” to a larger size than it originally occupies. The weighted budget320is increased for each successive block, but the amount of increase is smaller each time than it was the previous time. Assuming that the compression operation200gets to the last block in the batch (e.g., to block10), then the value of the weighted budget320, which is used in the testing operation at250, converges with the uniform budget310for the same block. In this example, both approaches test TotSize against a budget of 7.5 block increments (60 KB for an 8 KB block size) when testing the last block in the batch. Overall budgets for an entire batch may thus be the same for both approaches. However, the distribution of budgets in weighted budgets320is skewed relative to the uniform budgets310, with additional budget being provided for early blocks to be tested and budget increases reduced for later blocks.

FIG. 4shows example metadata structures that support storage of both compressed storage extents172A and of uncompressed storage extents172B in the file system170. Here, a file404resides within the file system170and stores a complete realization of a data object to which write requests112W (FIG. 1) are directed. The file404has a leaf D3(Indirect Block)410, which includes block pointers412that map logical addresses of the file402to corresponding physical addresses in the file system170. For example, block pointer412A maps logical address A, block pointer412B maps logical address Biblock pointer412C maps logical address C, and block pointer412X maps logical address X. Although only four block pointers412(1-3 and X) are shown, leaf D3410may include any number of block pointers412, a typical number of block pointers per D3being 1024, for example. The file404may have many leaf IBs, which may be arranged in an D3tree for mapping a logical address range of the file404to corresponding physical addresses in the file system170. A “physical address” is a unique address within a physical address space402of the file system170. Although not shown, the file system170may further include an inode (index node) table, which provides a unique inode for each file in file system170. The inode of each file provides a set of block pointers, which includes pointers to IBs. By accessing a file's inode, the file system170can traverse the D3tree to access any data block storing data of that file.

Each block pointer412include a weight (WA, WB, WC, . . . , WX), a Z-bit (ZA, ZB, ZC, ZX) and a pointer (PA, PB, PC, . . . , PX). The weight in each block pointer412indicates the number of other block pointers in the file system170that point to that block pointer. The Z-bit indicates whether the pointed-to data is compressed, and the pointer provides a physical address to be inspected for locating the pointed-to data. The block at the indicated physical address may contain the pointed-to data itself (e.g., for uncompressed data) or it may provide a segment VBM (virtual block map)440(e.g., for compressed data). The segment VBM440points to a segment450, which stores compressed data. In an example, segment450is composed of data blocks460(i.e., blocks460(1) through460(8)), which have contiguous physical addresses in the file system400). For purposes of storing compressed data, boundaries between blocks460(1) through460(8) are ignored and the segment450is treated as one contiguous space.

The segment VBM440itself has a weight WS and a pointer PS. The weight WS indicates the number of block pointers (e.g.,412) that point to the segment VBM440, and the pointer PS points to the physical address of the segment450, which by convention may be selected to be the address of the first data block460(e.g., that of block460(1)). The segment VBM440also includes an extent list442. Extent list442describes the contents of segment450and relates, for each item of compressed data, the logical address of that item in the file (e.g., A, B, and C), the location (e.g., byte offset) of that data in the segment450(e.g., Loc-A, Loc-B, and Loc-C), and a weight (Wa, Wb, and Wc). In an example, the sum of weights of extents in the extent list442equals the total weight WS of the segment VBM440.

The detail shown in segment450indicates an example layout452of data items. For instance, Header-A can be found at Loc-A and is immediately followed by compressed Data-A. Likewise, Header-B can be found at Loc-B and is immediately followed by compressed Data-B. Similarly, Header-C can be found at Loc-C and is immediately followed by compressed Data-C. In an example, each compression header is a fixed-size data structure that includes fields for specifying compression parameters, such as compression algorithm, length, CRC (cyclic redundancy check), and flags.

To place a compressed segment of file404in file system170(such as region172A ofFIG. 1), the file system170allocates data blocks (such as blocks460) and writes the compressed segment to the newly-allocated blocks. The file system170may allocate a new segment VBM (e.g., segment VBM440), establish its extent list442, its pointer PS to the new data blocks, and its weight WS. The file system may also update block pointers (e.g., those in leaf D3210) to point to the new segment VBM, marking the Z-bit of such block pointers to indicate that the pointed-to data are compressed. Although the leaf D3210tracks logical address ranges of file404in block-denominated sizes (e.g., 4 KB, 8 KB, etc.), the compressed data in blocks460may occupy significantly less space.

To place an uncompressed region of file404in file system170(such as region172B ofFIG. 1), the file system170allocates data blocks and writes the compressed segment to the newly-allocated blocks. However, there is no requirement for the blocks of uncompressed data to be contiguous in the physical address space402. Thus, data blocks for storing uncompressed data may be located anywhere. As with block pointer412X in leaf D3410, the block pointers for uncompressed blocks may point to respective data blocks, which store the uncompressed data, with no requirement for any segment VBM440. The file system170sets the Z-bit to of all block pointers to uncompressed blocks to indicate an uncompressed state.

FIG. 5shows an example method500that may be carried out in connection with the environment100. The method500is typically performed, for example, by the software constructs described in connection withFIG. 1, which reside in the memory130of the storage processor120and are run by the set of processors124. The various acts of method500may be ordered in any suitable way. Accordingly, embodiments may be constructed in which acts are performed in orders different from that illustrated, which may include performing some acts simultaneously.

At510, the data storage system116receives data into a data log140. The data log140provides temporary storage for the received data in units of blocks144.

At520, blocks144of data in the data log140are aggregated into multiple batches152, with each batch including multiple blocks144.

At530, a compression operation200, as described in connection withFIG. 2, is performed for each of the multiple batches using weighted budgets, as described in connection withFIGS. 2 and 3. In response to the testing operation producing the second result (e.g.,254) for all blocks in a batch, the data of all blocks in the batch are stored in compressed form in a set of non-volatile storage devices of the data storage system. It is not required or intended that the compression operation must be performed on every single batch152of aggregated blocks. For example, some implementations may omit the compression operation200for certain batches, e.g., if the data storage system is very busy performing other real-time tasks.

Having described certain embodiments, numerous alternative embodiments or variations can be made. Further, although features are shown and described with reference to particular embodiments hereof, such features may be included and hereby are included in any of the disclosed embodiments and their variants. Thus, it is understood that features disclosed in connection with any embodiment are included as variants of any other embodiment.

Further still, the improvement or portions thereof may be embodied as a computer program product including one or more non-transient, computer-readable storage media, such as a magnetic disk, magnetic tape, compact disk, DVD, optical disk, flash drive, solid state drive, SD (Secure Digital) chip or device, Application Specific Integrated Circuit (ASIC), Field Programmable Gate Array (FPGA), and/or the like (shown by way of example as medium550inFIGS. 2 and 5). Any number of computer-readable media may be used. The media may be encoded with instructions which, when executed on one or more computers or other processors, perform the process or processes described herein. Such media may be considered articles of manufacture or machines, and may be transportable from one machine to another.

As used throughout this document, the words “comprising,” “including,” “containing,” and “having” are intended to set forth certain items, steps, elements, or aspects of something in an open-ended fashion. Also, as used herein and unless a specific statement is made to the contrary, the word “set” means one or more of something. This is the case regardless of whether the phrase “set of” is followed by a singular or plural object and regardless of whether it is conjugated with a singular or plural verb. Further, although ordinal expressions, such as “first,” “second,” “third,” and so on, may be used as adjectives herein, such ordinal expressions are used for identification purposes and, unless specifically indicated, are not intended to imply any ordering or sequence. Thus, for example, a second event may take place before or after a first event, or even if no first event ever occurs. In addition, an identification herein of a particular element, feature, or act as being a “first” such element, feature, or act should not be construed as requiring that there must also be a “second” or other such element, feature or act. Rather, the “first” item may be the only one. Although certain embodiments are disclosed herein, it is understood that these are provided by way of example only and that the invention is not limited to these particular embodiments.