HK1215974B - Managing operations on stored data units - Google Patents

Description

Manage operations on storage data units

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims priority to U.S. patent application No. 13/787,203, filed March 6, 2013.

Technical Field

The present application relates to managing operations on storage data units.

Background Art

Data storage systems provide various operations for storing, retrieving, or deleting data units. A "data unit" is a unit of information represented by retrievable stored data (e.g., a data unit may represent a single record). Different systems may employ different storage formats and techniques to perform the above operations. For example, for some systems, deleting a data unit may involve deleting a pointer or index entry used to locate the data unit, or may involve overwriting the data unit. Data units may be stored individually or within "data blocks" (or "data blocks" or "compressed blocks") that include multiple data units (in the same or different representations). Some systems provide features such as data compression and data encryption that may affect the implementation of, or even support, the above operations. For example, a storage format that includes multiple data units compressed into a single data block may support the deletion of groups of compressed blocks (e.g., old or expired blocks), but may not support the deletion of individual data units within those blocks.

Summary of the Invention

In one aspect, generally, a system for managing storage of data units includes a data storage system configured to store a plurality of data blocks, at least some of the data blocks including a plurality of data units, at least one group of the data blocks being stored contiguously to support a first read operation that retrieves a data unit from at least two adjacent data blocks in the group (e.g., the first read operation may be a type of function or procedure executed by a storage interface module 104 or another interface of the data storage system). The system also includes an interface comprising at least one processor coupled to the data storage system and configured to perform one or more operations on the data units, the operations including a delete operation that replaces a first data block including a data unit to be deleted with a second data block that does not include the deleted data unit, the second data block having the same size as the first data block.

These aspects may include one or more of the following features.

The second data block is adjacent to a data block, and the data block is adjacent to the first data block in the data storage system.

The second data block is stored in the same storage space as the first data block.

The deletion operation causes data blocks other than the first data block to be maintained in the same storage location within the data storage system where the data blocks were stored before the deletion operation was performed.

The data storage system is configured to store, for at least some of the data blocks, corresponding history information regarding a previous deletion of one or more data units from the data block, the deletion affecting at least some addresses of the plurality of data units in the data block.

The operations include a second read operation, different from the first read operation, that accesses at least a first data unit stored in a particular data block based on address information interpreted based on any stored history information corresponding to the particular data block.

The deletion operation stores information related to the deleted data unit in history information corresponding to the second data block.

At least some of the historical information is stored in the data storage system.

At least a portion of the historical information is interleaved between different data blocks.

At least a portion of the history information corresponding to a specific data block is stored in a predetermined portion of the specific data block.

At least some of the data blocks are compressed data blocks.

The second read operation decompresses a specific compressed data block to recover a set of decompressed data units, and retrieves the data unit to be read at a specific offset from a reference position based at least in part on the history information corresponding to the specific compressed data block.

The first reading operation decompresses a plurality of compressed data blocks and sequentially reads a plurality of decompressed data units.

The deletion operation expands the storage size of the second compressed data block to account for the size difference between the second compressed data block and the first compressed data block.

The storage size of the second compressed data block is extended by storing additional information associated with the second compressed data block in addition to the history information corresponding to the second compressed data block.

The deletion operation stores a new error detection code associated with the second compressed data block in place of the error detection code associated with the first compressed data block.

The operations include an add operation that stores a to-be-added data unit in association with a set of most recently added data units.

The processor is further configured to compress the set of most recently added data units into a compressed data block stored in the storage medium.

The data storage system is configured to store additional information identifying the plurality of data blocks in the group as conforming to a predetermined storage format.

The additional information includes an identifier in a data header of each data block in the group for identifying the predetermined storage format.

The first read operation is compatible with the predetermined storage format.

In another aspect, in general, a system for managing storage of data units includes means for storing a plurality of data blocks, at least some of the data blocks including a plurality of data units, at least one group of the data blocks being stored contiguously to support a first read operation that retrieves a data unit from at least two adjacent data blocks in the group. The system also includes means for performing one or more operations on the data units, the operations including a delete operation that replaces a first data block including a data unit to be deleted with a second data block that does not include the deleted data unit, the second data block having the same size as the first data block.

In another aspect, in general, a method for managing data unit storage includes storing a plurality of data blocks in a data storage system, at least some of the data blocks including a plurality of data units, at least one group of the data blocks being stored contiguously to support a first read operation that retrieves a data unit from at least two adjacent data blocks in the group. The method also includes using at least one processor to perform one or more operations with respect to the data units, the operations including a delete operation that replaces a first data block including a data unit to be deleted with a second data block that does not include the deleted data unit, the second data block having the same size as the first data block.

In another embodiment, software is stored on a computer-readable medium to manage storage of data units. The software includes instructions for causing a computing system to: store a plurality of data blocks in a data storage system, at least some of the data blocks including a plurality of data units, at least one group of the data blocks being stored contiguously to support a first read operation that retrieves a data unit from at least two adjacent data blocks in the group; and perform two or more operations on the plurality of data units, the operations including a delete operation that replaces a first data block including a data unit to be deleted with a second data block that does not include the deleted data unit, the second data block having the same size as the first data block.

In another embodiment, a system for managing data unit storage includes a data storage system configured to store a plurality of data blocks, at least some of the data blocks including a plurality of data units, at least one group of the data blocks being stored contiguously to support a first read operation that retrieves a data unit from at least two adjacent data blocks in the group (e.g., the first read operation may be a function or procedure executed by a storage interface module 104 or another interface of the data storage system). The system also includes an interface comprising at least one processor coupled to the data storage system and configured to perform two or more operations on the data units. The operations include: a second read operation that, unlike the first read operation, retrieves a data unit to be read based at least in part on an address of the data block containing the data unit to be read; and a delete operation that replaces a first data block containing the data unit to be deleted with a second data block that does not include the deleted data unit.

These aspects may include one or more of the following features.

The data storage system is configured to store, for at least some of the data blocks, corresponding history information regarding a previous deletion of one or more data units from the data block, the deletion affecting at least some addresses of the plurality of data units in the data block.

The second read operation accesses at least a first data unit stored in a particular data block according to address information interpreted based on any stored history information corresponding to the particular data block.

The deletion operation stores information related to the deleted data unit in history information corresponding to the new data block.

At least some of the historical information is stored in the data storage system.

At least a portion of the historical information is interleaved between different data blocks.

At least a portion of the history information corresponding to a specific data block is stored in a predetermined portion of the specific data block.

At least some of the data blocks are compressed data blocks.

The second read operation decompresses a specific compressed data block to recover a set of decompressed data units, and retrieves the data unit to be read at a specific offset from a reference position based at least in part on the history information corresponding to the specific compressed data block.

The first reading operation decompresses a plurality of compressed data blocks and sequentially reads a plurality of decompressed data units.

The deletion operation expands the storage size of the second compressed data block to account for a size difference between the second compressed data block and the first compressed data block.

The storage size of the second compressed data block is extended by storing additional information associated with the second compressed data block in addition to the history information corresponding to the second compressed data block.

The deletion operation stores a new error detection code associated with the second compressed data block in place of the error detection code associated with the first compressed data block.

The operations include an add operation that stores a to-be-added data unit in association with a set of most recently added data units.

The processor is further configured to compress the set of most recently added data units into a compressed data block stored in the storage medium.

The second read operation locates the data block including the data unit to be read according to an index indicating the data block containing data units with multiple specific identifiers to restore the decompressed data unit set and searches for the data unit to be read within the multiple decompressed data units.

The data storage system is configured to store additional information identifying the plurality of data blocks in the group as conforming to a predetermined storage format.

The additional information includes an identifier in a data header of each data block in the group for identifying the predetermined storage format.

The first read operation is compatible with the predetermined storage format.

In another embodiment, in general, a system for managing data unit storage includes means for storing a plurality of data blocks, at least some of the data blocks including a plurality of data units, at least one group of the data blocks being stored contiguously to support a first read operation that retrieves a data unit from at least two adjacent data blocks in the group. The system also includes means for performing two or more operations on the plurality of data units. The operations include: a second read operation that, unlike the first read operation, retrieves a data unit to be read based at least in part on an address of the data block containing the data unit to be read; and a delete operation that replaces a first data block that includes a data unit to be deleted with a second data block that does not include the deleted data unit.

In another embodiment, in general, a method for managing data unit storage includes storing a plurality of data blocks in a data storage system, at least some of the data blocks including a plurality of data units, and at least one group of the data blocks being stored contiguously to support a first read operation that retrieves a data unit from at least two adjacent data blocks in the group. The method also includes performing, using at least one processor, two or more operations on the plurality of data units. The operations include: a second read operation that, unlike the first read operation, retrieves a data unit to be read based at least in part on an address of the data block containing the data unit to be read; and a delete operation that replaces a first data block that includes a data unit to be deleted with a second data block that does not include the deleted data unit.

In another embodiment, software is stored on a computer-readable medium to manage storage of data units. The software includes instructions for causing a computing system to: store a plurality of data blocks in a data storage system, at least some of the data blocks including a plurality of data units, at least one group of the data blocks being stored contiguously to support a first read operation that retrieves a data unit from at least two adjacent data blocks in the group; and perform two or more operations on the plurality of data units. The operations include: a second read operation that, unlike the first read operation, retrieves a data unit to be read based at least in part on an address of the data block including the data unit to be read; and a delete operation that replaces a first data block including a data unit to be deleted with a second data block that does not include the deleted data unit.

In another aspect, in general, a system for managing data unit storage includes a data storage system configured to store a plurality of data blocks, at least some of the data blocks including a plurality of data units, the data storage system further configured to store, for at least some of the data blocks, corresponding historical information related to a previous deletion of one or more data units from the data block, the deletion affecting at least some addresses of the plurality of data units in the data block. The system also includes an interface comprising at least one processor coupled to the data storage system and configured to perform at least one operation to access at least one first data unit stored in a first data block based on address information interpreted based on any stored historical information corresponding to the first data block.

These aspects may include one or more of the following features.

The history information corresponding to the first data block includes information regarding previous deletions of one or more data units from the first data block, the deletions affecting relative offsets of data units that have been decompressed from the first data block.

At least some of the data blocks are compressed data blocks.

The interface is configured to perform two or more operations on multiple data units, the operations including: a read operation that retrieves a data unit to be read based at least in part on address information, wherein the address information locates the data unit relative to a reference address; and a delete operation that deletes the data unit to be deleted and stores historical information related to the deleted data unit for interpreting address information for other data units to take into account any offset relative to the reference address caused by deleting the data unit to be deleted.

The interface is also configured to perform two or more operations on multiple data units, the operations including: a first read operation, which retrieves the data unit to be read based at least in part on historical information corresponding to the compressed data block; and a delete operation, which replaces the first compressed data block including the data unit to be deleted with a second compressed data block that does not include the deleted data unit, and stores information related to the deleted data unit in the historical information corresponding to the second compressed data block.

The first read operation decompresses a specific compressed data block to recover a set of decompressed data units, and retrieves the data unit to be read at a specific offset from a reference position based at least in part on the history information corresponding to the specific compressed data block.

The first read operation determines whether the history information includes information related to one or more previously deleted data units.

If the history information includes information related to one or more previously deleted data units, the first read operation determines whether to adjust the specific offset based on a comparison of the specific offset and a value in the history information, wherein the history information indicates the offset of at least one previously deleted data unit.

If the specific offset is to be adjusted, the first read operation adjusts the specific offset based on the offset and size of one or more previously deleted data units.

The deletion operation expands the storage size of the second compressed data block to account for the size difference between the second compressed data block and the first compressed data block.

The storage size of the second compressed data block is extended by storing additional information associated with the second compressed data block in addition to the history information corresponding to the second compressed data block.

The deletion operation stores a new error detection code associated with the second compressed data block in place of the error detection code associated with the first compressed data block.

The operations include an add operation that stores a to-be-added data unit in association with a set of most recently added data units.

The processor is further configured to compress the set of most recently added data units into a compressed data block stored in the storage medium.

The operations include a second read operation that, unlike the first read operation, decompresses one or more compressed data blocks and sequentially reads a plurality of decompressed data units.

The operation includes a third read operation, which is different from the first read operation and the second read operation, and decompresses a specific compressed data block indicated by an index as including a data unit with a specific identifier to recover a set of decompressed data units, and searches for the data unit with the specific identifier within the multiple decompressed data units.

At least some of the historical information is stored in the data storage system.

At least a portion of the historical information is interleaved between different data blocks.

At least a portion of the history information corresponding to a specific data block is stored in a predetermined portion of the specific data block.

In another aspect, in general, a system for managing data unit storage includes means for storing a plurality of data blocks, at least some of the data blocks including a plurality of data units, the means for storing the plurality of data blocks being configured to store, for at least some of the data blocks, corresponding historical information related to a previous deletion of one or more data units from the data block, the deletion affecting at least some addresses of the plurality of data units in the data block. The system also includes means for performing at least one operation that accesses at least one first data unit stored in the first data block based on address information interpreted based on any stored historical information corresponding to the first data block.

In another aspect, in general, a method for managing data unit storage includes storing a plurality of data blocks in a data storage system, at least some of the data blocks including a plurality of data units, the data storage system being configured to store, for at least some of the data blocks, corresponding historical information related to a previous deletion of one or more data units from the data block, the deletion affecting at least some addresses of the plurality of data units in the data block. The method also includes executing, using at least one processor, at least one operation of accessing at least one first data unit stored in the first data block based on address information interpreted based on any stored historical information corresponding to the first data block.

In another embodiment, software is stored on a computer-readable medium to manage storage of data units. The software includes instructions for causing a computing system to: store a plurality of data blocks in a data storage system, at least some of the data blocks including a plurality of data units, the data storage system being configured to store, for at least some of the data blocks, corresponding history information related to a previous deletion of one or more data units from the data block, the deletion affecting at least some addresses of the plurality of data units in the data block; and perform at least one operation that accesses at least one first data unit stored in the first data block based on address information interpreted based on any stored history information corresponding to the first data block.

These aspects may include one or more of the following advantages.

A delete operation is provided for completely removing a data unit from a compressed data storage unit, which may be useful, for example, for complying with privacy laws for deleting data at the request of a customer. Deleting the deleted data unit may affect pointers that locate the data unit at a specific address or at a relative offset from a reference address. However, these pointers do not need to be changed, or even located when the delete operation is performed. However, if those data units are actually accessed, the pointers can be corrected later if necessary. For many uses of the data storage unit, correcting the pointers on demand is more efficient than locating and correcting the pointers at the time of deletion. Deleting deleted data units from compressed blocks of a multi-block compressed data storage unit can also be performed in a manner that preserves the compatibility of the delete operation with multiple operations that read the data units by scanning multiple data units recovered from one or more compressed data blocks. For example, the delete operation may be compatible with a scan-read operation that applies a standard decompression function (e.g., gzcat) to a file stored in a known compression format (e.g., gzip) and interprets the decompressed data (e.g., according to the record format) to sequentially restore individual records into data units without relying on indexes or other address information. By ensuring that the file has no gaps between compressed data blocks after the delete operation, the scan-read operation can still correctly parse the compression format without having to move or rewrite the entire file. Furthermore, by using the history information, the delete operation can be performed such that read operations that rely on address information continue to operate normally regardless of whether data units have been previously deleted from the compressed data store.

Other features and advantages of the invention will become apparent from the following description and from the claims.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a block diagram of a data storage system.

FIG2 is a schematic diagram of a data storage format.

3A-3D are flow charts of data operations.

DETAILED DESCRIPTION

FIG1 illustrates an example of a data processing system 100 to which data storage techniques may be applied. An execution environment 102 includes a storage interface module 104 configured to perform data operations on data units stored in a data storage system 106. The execution environment 102 may be hosted, for example, on one or more general-purpose computers controlled by a suitable operating system (e.g., a version of the UNIX operating system). For example, the execution environment 102 may also include a multi-node parallel computing environment, including a configuration of a computer system using multiple central processing units (CPUs) or processor cores. These CPUs or processor cores may be local (e.g., a multi-processor system such as a symmetric multiprocessing (SMP) computer), locally distributed (e.g., multiple processors coupled as a cluster or massively parallel processing (MPP) system), remote, or remotely distributed (e.g., multiple processors coupled via a local area network (LAN) and/or a wide area network (WAN)), or a combination thereof. The data storage system 106 includes one or more storage devices, which may be local to the execution environment 102, for example, connected to the computer hosting the execution environment 102, or remote from the execution environment 102, for example, in communication with the computer hosting the execution environment 102 via a remote connection. The one or more storage devices may include, for example, volatile memory, such as random access memory (RAM), and non-volatile memory, such as magnetic drives or solid-state drives. The data processing system 100 may be configured to receive data from or provide data to other systems via a communication interface 108 coupled to a network 110.

Individually accessible data units received from various storage sources in the data storage system 106 may be organized into records having values for various fields (also referred to as "attributes" or "columns"), including possible null values. For example, a credit card company may receive data representing individual transactions from various retail companies. Each transaction is associated with a value representing an attribute (e.g., customer name, date, purchase amount, etc.). The storage interface module 104 may ensure that the data is formatted according to a predetermined record format so that the values associated with the transaction are stored in the record. In some cases, this may include converting data from multiple sources according to the record format. In other cases, one or more sources may provide formatted data according to the record format. In some cases, the record format may not be initially known and may be determined only after analysis of the source or data.

The storage interface module 104 provides a set of data operations for managing data stored in the data storage system 106. For example, the processor is configured to execute storage instructions for a particular data operation in response to a request to perform the particular data operation. The data operations include an add operation for adding a new data unit, a delete operation for deleting a stored data unit, and a plurality of read operations for retrieving a stored data unit using different read modes (described in more detail below) and returning the retrieved data unit requested to be read. The data operations are performed in response to another portion of the data processing system 100, including a user interface for receiving input from a user.

In some embodiments, the data storage system 106 includes a compressed data storage unit 112 that stores data in a storage format where each compressed data block is formed by compressing multiple data units. The data blocks generated by the compression typically include compressed data representing the multiple data units in compressed form, as well as overhead information, which refers to any other information that is part of the data block but not the compressed data itself. The overhead information is referred to as a "header" if it appears before the compressed data, and as a "footer" if it appears after the compressed data. In some embodiments, the data storage system 106 stores a collection of data units that are not necessarily compressed but are associated with each other, such as a collection of data units stored at a specified offset relative to a common reference location. In some embodiments, the storage interface module 104 can use any of a variety of techniques to process the data units in some manner in conjunction with records to generate data blocks (e.g., so that the block is more than just a concatenated collection of records). Data blocks containing multiple data units can be processed to recover the individual data units by applying supplementary functions (e.g., decompression). The data units contained in a data block may not be stored in their original form (e.g., the data units may be represented by different bits), and the data units may not be individually represented with a one-to-one correspondence between each data unit and the bits stored in the data block (e.g., any particular bit within a compressed data block may be a function of multiple data units). If compression is employed, the compression may be part of performing the intended function. For example, in some embodiments, module 104 processes a set of records to generate an encrypted data block. The compression ratio (i.e., the compressed size divided by the decompressed size) for different data blocks will typically vary, and in some cases, the compression ratio for some data blocks may be greater than 1.

An example of a storage format is a compressed record file with optional indexing for locating individual stored data units, as described in detail in U.S. Patent No. 7,885,932, which is incorporated herein by reference. For example, to generate a compressed record file, the storage interface module 104 sorts the received records by a primary key value that identifies each record (e.g., a unique key that identifies an individual record or a key that identifies multiple updated versions of a record) and groups the records into record sets corresponding to non-overlapping ranges of primary key values, each record set potentially corresponding to a predetermined number of records (e.g., 100 records). The module 104 compresses each record set into compressed data blocks. These compressed blocks are collected to form a compressed record file (e.g., by appending consecutive blocks to the file), which is stored in the compressed data storage unit 112 (e.g., hosted on a non-volatile storage medium, such as one or more hard drives). Any number of compressed record files can also be merged to form a composite compressed record file. In some embodiments, the storage interface module 104 manages an index that includes an entry for each of the blocks. The index can be used to locate the block containing a given record by listing a series of primary keys of the records that may be included in the block, as described in more detail in U.S. Patent No. 7,885,932. Although the index can be stored in the same storage medium as the compressed record file, it is preferably stored in a relatively faster memory (e.g., a volatile storage medium such as dynamic random access memory) because the index is typically much smaller than the compressed record file.

As new data units are received and stored in the data storage system 106 (via an append operation), the data units are first stored in an uncompressed form in the input buffer 114. After a predetermined threshold, for example, after a certain number of data units have been stored in the input buffer 114, after the input buffer 114 reaches a certain size, or after a certain time interval, the multiple data units can be compressed together into a single compressed data block using any of a variety of compression formats (e.g., gzip format). The compressed data block is then added to one of the compressed record files in the compressed data storage unit 112.

In some embodiments, different read operations are used for different read modes to provide flexibility in how data can be retrieved. For each read mode, one or more compressed data blocks identified by the read mode are decompressed to generate a set of data units. However, different read modes employ different techniques to retrieve one or more data units to be returned from the set of data units recovered from the data block in response to the read operation. For example, in a first read mode (referred to as "direct addressing mode"), specific data units are retrieved based on address information that specifies: the data block containing the data unit, an offset of the beginning of the data unit (relative to the beginning of the recovered set), and the length of the data unit. In some cases, the offset may need to be modified based on historical information that includes information related to a previous deletion of one or more data units from the data block, which is sufficient to correct potential changes caused by the previous deletion, as described in more detail below. The data unit length specification supports data units with variable lengths and/or unspecified lengths. Alternatively, in some embodiments, if all data units have the same specified fixed length, the length need not be included in the direct address. In some embodiments, the direct address can implicitly indicate the relative offset of the data unit based on auxiliary information. For example, the direct address can specify: the data block containing the data unit, and the record identifier that maps to the offset of the beginning of the data unit (e.g., based on a mapping stored in association with the data block).

In a second read mode (referred to as "scan mode"), data units can be read sequentially from the recovered set as a continuous stream. For a compressed record file comprising multiple compressed data blocks, when the end of a compressed data block is reached, data units from the next compressed data block are decompressed and read until the end of the file is reached. In scan mode, all of the read data units can be returned in response to the read operation, or any subset of the read data units can be returned (e.g., based on a selected filter). In some embodiments of the system 100, the scan mode read operation can be configured to be performed by an interface of the data storage system 106 that is separate from the storage interface module 104 (e.g., by a third-party program running in the execution environment 102 or by a system that can access the data storage system 106 from outside the execution environment 102).

In a third read mode (referred to as "key lookup mode"), records with a specific key(s) are retrieved by accessing an index that identifies a range of possible keys corresponding to each data block. The key specified by the read operation may be a primary key or a secondary key that maps to one or more primary keys of the data unit to be retrieved. The data blocks listed by the index and corresponding to the range that includes the specified primary key are decompressed, and the primary key is searched for from the recovered set of data units. Other read operations may also be supported. For example, a read operation may specify a primary key or a secondary key, which may be mapped to address information for a specific data unit using a primary key-direct address lookup table.

The delete operation causes a specified data unit to be deleted from the compressed data block in the compressed data storage 112 containing the data unit without modifying any other portion of the compressed data storage 112. For example, some embodiments do not require modifying more than a single data block in a compressed record file, nor do they require modifying any indexes to the data blocks or file. This is useful, for example, if a particular data unit contains information that needs to be purged (e.g., customer information that needs to be deleted at a customer's request under privacy laws), but other data units in the same block or compressed record file need to be retained. The delete operation replaces the compressed data block containing the deleted data unit with a new compressed data block that does not include the deleted data unit, and stores information about the deleted data unit in history information associated with the new compressed data block. The history information may be stored with the compressed data block in the compressed data storage 112 (e.g., a predetermined portion of the compressed data block, such as a header or trailer, or other additional information or available interleaving space between different compressed data blocks). The history information may include, for example, a series of offsets to the deleted data units and their lengths.

Utilizing this historical information, other data units remaining in the new compressed data block can subsequently still be accessed by utilizing existing address information interpreted based on the historical information to take into account any offsets caused by any deleted data units. In particular, all existing direct address offsets for data units located in the set recovered from the data block following the deleted data unit do not need to be modified during the deletion operation, which helps to improve efficiency. When it is desired to use a read operation to read a smaller number of stored data units in direct addressing mode, in this case, writing historical information to adjust the offsets as needed may be more efficient than modifying a potentially large number of stored direct address offsets (e.g., stored in an index) for data units that have never been read. In addition, in some embodiments, the storage interface module 104 may not access all locations where direct address offsets can be stored. Therefore, not all of the offsets are modified.

2 , an example of a data storage format for the compressed data storage unit 112 includes a compressed record file 200, which includes a plurality of compressed data blocks, including data blocks 202A-202C. In this example, the data block 202B includes a header 204 and a trailer 206. The header 204 includes fields storing information related to the compression and decompression of the data block 202B, as well as other related information. The trailer 206 includes error detection codes, such as cyclic redundancy checks (CRCs) and other checksums, to detect and/or correct errors during the compression and decompression processes. A portion of the compressed data 208 within the data block 202B can be decompressed to recover a record set 210 stored in the compressed record file 200. For some compression formats, the header 204 has a variable length and therefore includes information indicating where the header 204 ends and where the compressed data 208 begins.

For example, in the gzip compression format, the data header 204 has the fields listed in the following table, including 6 mandatory fields in the first 10 bytes and up to 6 optional fields including variable length fields.

Table 1

The gzip compression format also has an 8-byte trailer that includes a 4-byte CRC code and a 4-byte value that provides the decompressed size of the original data, where the decompressed size is compressed modulo 2 ^32. Two or more compressed data blocks, each with its own gzip header and trailer, and stored adjacent to each other (i.e., the next header begins immediately after the previous trailer), can be identified as a single valid gzip file.

When the storage interface module 104 performs a delete operation in which one or more records to be deleted (e.g., record C and record E) are indicated as being contained in the data block 202B (e.g., by an index), the module 104 decompresses the compressed data 208 to restore the record set 210, generates a new record set 212 that omits the deleted records, and compresses the new record set 212 into modified compressed data 208'. Because the new record set 212 contains less information content than the original record set 210, the size of the modified compressed data 208' will be smaller than the size of the original compressed data 208 (assuming there is a certain minimum information content in any given record that can be deleted). The portion of the data block 202B storing the compressed data 208 is then replaced with the modified compressed data 208′, and the original data header 204 and data footer 206 are replaced with the modified data header 204′ and data footer 206′, which together correspond to the modified data block 202B′. Because the modified data 208′ occupies less storage space than the original data 208, there is storage space available for the modified data header 204′, and the modified data header 204′ occupies more storage space than the original data header 204. This additional storage space is used to store history information 214 in an available variable-length field (e.g., an extra field in the gzip compression format).

For most record formats, the storage space required to accommodate the history information 214 within the modified data header 204' may be less than the expected reduction in size of the modified data 208' after deleting a single record. If the size is not reduced enough to accommodate the history information 214, the associated deletion operation may be canceled and an error message returned. To ensure that the modified data block 202B' has the same total size as the original data block 202B, the header may be extended as needed by writing padding 218, for example, by repeating byte patterns (e.g., a number of bytes containing 0xff) or other additional information in the same or another variable-length field (e.g., the comment field in the gzip compression format). Optionally, for implementations where record deletion may not provide sufficient space for the history information (e.g., for particularly compact record structures), padding may also be included in the header when a compressed data block is first generated. The initial padding may be reduced as needed to provide additional space in the header for the history information.

As described above, the history information 214 summarizes the records deleted from the record set 210, which contains sufficient information about the direct address offsets of the remaining records in the new, smaller set 212 relative to a common reference storage location (e.g., the start address of the address space where the records are subsequently stored in the new, restored record set 212) to be corrected, if necessary. An example of a data structure 215 that can be used to encode the history information 214 is a list of elements 216, each element containing the offset of a deleted record relative to the start of the first record in the original record set (regardless of whether the first record currently exists), and the corresponding length of the record. In the example illustrated in FIG. 2 , there are two elements 216 for each of the deleted records C and E. The encoding of the record length supports records with variable and/or unspecified lengths. Alternatively, in other examples, if all records have the same specified fixed length, the length need not be stored in element 216. The elements 216 are presented in a list ordered by their offset values. As additional delete operations are performed to delete additional records, additional elements 216 are added to or inserted into the list.

Various encoding techniques can be used to efficiently store the data structure 215. For example, any sequence of two or more adjacent deleted records can be collapsed into a single element 216 that includes the offset of the first record in the sequence and a length equal to the sum of the lengths of the records in the sequence. Thus, each element 216 can represent a previously deleted region that stores a number of previously deleted records. In some cases, adjacent deleted records may have been deleted in different deletion operations. Each element 216 can be stored in adjacent bits within the variable-length field of the data header 204', using a predetermined number of bits to store the offset and a predetermined number of bits to store the length. The amount of storage space used to store the offset value is limited to a relatively small number of bits sufficient to store the largest possible offset expected. The amount of storage space used to store the length value can also be limited (e.g., to the same number of bits as used to store the offset to account for collapsed elements). The offset and length values can also be compressed based on assumptions about what values are possible. For example, if it is known that a record will always occupy an even number of bits, then the offset and length values can be interpreted as encoding a specific number of bit pairs. Thus, 8 bits can encode values up to 255 × 2 = 510 bits. Similarly, if it is known that a record will always occupy a multiple of the storage space of a certain number of bits, then the offset and length values can be interpreted as encoding a number times that multiple of the bits, which is completely different from the actual number of bits. Optionally, the data structure 215 can be further compressed (e.g., using run-length encoding).

FIG3A shows a flow chart 300 of an example of a delete operation performed to delete one or more records, each record having a direct address corresponding to a triplet (BLOCK, OFFSET, LENGTH). (In this example, one or more records in a single block are being deleted, but in other examples, records from many blocks may be deleted in the delete operation.) The storage interface module 104 decompresses (302) a block of data in the compressed data storage 112 and stores the identifier BLOCK in an address space that begins at address START. The module 104 deletes (304) the record (having a length of LENGTH) at address START+OFFSET. The module 104 calculates (306) history information that may encode the OFFSET value and the LENGTH value. The module 104 determines (308) whether there are multiple records to be deleted from the block, and if so, repeats the deleting (304) step and the calculating (306) step. After deleting the records, the module 104 writes a new set of records to a portion of the storage space where the remaining records are contiguous without any gaps where the omitted record(s) were previously (e.g., written to a temporary file), and the module 104 compresses (310) the new set of records. The module 104 writes (312) the calculated history information data structure and any necessary padding into the data header of the block BLOCK. The module 104 writes (314) the resulting compressed data into the block BLOCK in the compressed data storage portion 112 so that the compressed data ends at the same position as the original compressed data in the block BLOCK. The module 104 writes (316) a new data trailer for the new compressed data (to replace the previous data trailer) using an error detection code.

In addition to such an "expunging" delete operation that actually deletes the information in the record being deleted, the storage interface module 104 can also be configured to provide other delete operations that simply hide or mark the record to be deleted (without actually deleting the information in the record). These delete operations may not require writing history information or even decompressing blocks, which is very helpful in providing a faster but less secure form of deletion. However, there are also delete operations that can fully erase to meet more stringent requirements for clearing information, such as certain privacy laws that require that deleted information cannot be recovered.

FIG3B shows a flow chart 320 of an example of a first (directly addressed) read operation performed to read one or more records, each record having a direct address corresponding to a triplet of (BLOCK, OFFSET, LENGTH). (In this example, one or more records in a single block are being read, but in other examples, records from many blocks may be read in the read operation.) The storage interface module 104 decompresses (322) the data block in the compressed data storage 112 and stores the identifier BLOCK in an address space that begins at address START. The module 104 calculates (324) the address of the record to be read as START + OFFSET − CORRECTION, where CORRECTION is calculated based on any existing historical information for block BLOCK. For example, the module 104 determines how many previously deleted areas have a value less than the offset value of OFFSET and end before OFFSET. If not, no correction is required and CORRECTION = 0. Otherwise, CORRECTION is equal to the sum of the lengths of each previously deleted region whose offset value is less than OFFSET. Thus, the correction caused by previously deleted regions depends on how many previously deleted records initially existed between the particular record to be read and the start of the set of records. After calculating the address, the module 104 reads (326) the record at the calculated address. If a previously deleted region has an offset value less than or equal to OFFSET but does not end before OFFSET, the calculated address falls within the previously deleted region and the module 104 skips the reading step 326 and reports that the record to be read has been deleted. The module 104 determines (328) whether there are additional records to be read and, if so, repeats the calculation (324) and reading (326) steps. When there are no additional records to be read in the block, the process returns to operation (330).

Other implementations of the first (direct addressing) read operation are possible. For example, rather than calculating a corrected address for each record to be read, the records recovered after decompressing the compressed data block can be written to the address space with appropriate gaps where the deleted records once were. The information needed to determine the location of these gaps can be obtained from the same historical information described above. The read operation then continues to read each record at its uncorrected address START+OFFSET.

FIG3C shows a flowchart 340 of an example of a second (scanning) read operation that scans one or more blocks in a compressed record file from which records are to be read. The storage interface module 104 decompresses (342) the first data block in the compressed data storage unit 112 into an address space. The module 104 scans (344) the address space to read each individual record (e.g., by identifying the beginning of each record and/or the end of each record). The module 104 determines (346) whether there is another data block in the file (e.g., by detecting another gzip magic header) and, if so, decompresses (342) the next data block to read the additional record. If there are no additional data blocks to be read in the file (e.g., by detecting the end of the file), the operation returns (348).

While it is possible to perform an erase operation by completely erasing the record without storing the history information (e.g., by overwriting the deleted record in place with gaps filled with a predetermined pattern, such as all 1 bits or all 0 bits), such an erase operation requires a scan-mode read operation to identify and ignore the deleted record. By deleting the gaps where the deleted record once existed and storing the information in the history information, the scan-mode read operation can be implemented in a flexible manner compatible with any of a variety of techniques for reading the information in the compressed data storage 112, including by modules other than the storage interface module 104 (e.g., by employing third-party software). Furthermore, by filling in the extra space remaining after the smaller, modified compressed data 208' replaces the larger, original compressed data 208 (e.g., by filling in fields in the modified data header 204'), there are no unexpected gaps in the compressed record file, allowing the second (scanning) read operation to successfully identify each compressed data block. For example, in an implementation using the gzip format, after the data tail, the module 104 foresees another beginning of a compressed data block (i.e., another gzip magic header) or an indicator of the end of the compressed record file. Extending the size of a compressed data block modified by a deletion operation in this manner maintains scan mode compatibility without moving the storage location of any compressed data block in the compressed record file that appears after the compressed data block is modified.

3D shows a flow chart 360 of an example of a third (key lookup) read operation performed to read one or more records, each record having an identifying key value. The storage interface module 104 decompresses (362) a data block from the compressed data storage unit 112 into an address space using the identifier BLOCK. The module 104 searches (364) for records in the address space to locate any record having the provided key value.

In order to enable multiple concurrent data operations to be performed by the storage interface module 104, or other modules or systems that access the compressed data storage unit 112, techniques can be used to avoid conflicts between two data operations. If the expected deletion operation does not occur frequently, the error detection code in the data tail of the compressed data block can be used by the data operation after decompression to detect the data block in the process of updating the compressed data during the deletion operation. For example, after an invalid checksum, the data operation can output an error message or try again after a delay to allow the deletion operation to be completed. If the expected deletion operation occurs relatively frequently, a locking mechanism can be used to avoid such conflicts.

The above-mentioned data storage technology can be implemented using a computing system that executes appropriate software. For example, the software includes a process in one or more computer programs that are executed on one or more programmed or programmable computer systems (which can have various architectures, such as distributed, client/server, or network formats), each of which includes at least one processor, at least one data storage system (including volatile and/or non-volatile memory and/or storage element), and at least one user interface (for receiving input using at least one input device or port, and for providing output using at least one output device or port). The software may include one or more modules of a large program, for example, the large program provides other services related to the design, configuration, and execution of a data flow graph. The modules of the program (for example, elements of a data flow graph) may be implemented as data structures or other organized data that conform to the data model stored in a database.

The software can be provided on a tangible permanent storage medium such as a CD-ROM or other computer readable medium (which can be read by a general or special computer system or device), or a tangible permanent medium delivered (encoded into a propagation signal) to a computer system that executes the software via a communication medium of a network. Some or all of the processing can be performed on a dedicated computer, or performed using dedicated hardware such as a coprocessor or a field programmable gate array (FPGA) or an application specific integrated circuit (ASIC). The processing can be implemented in a distributed manner in which different computing parts specified by the software are performed by different computing elements. Each such computer program is preferably stored in or downloaded to a computer readable storage medium (e.g., a solid-state memory or medium, or a magnetic or optical medium) of a storage device that can be read by a general or special programmable computer, for configuring and operating the computer when the computer reads the storage medium or device to perform the processing described herein. It is also contemplated that the system of the present invention can be implemented as a tangible permanent storage medium configured with a computer program, wherein the storage medium so configured causes the computer to operate in a specific and predefined manner to perform one or more processing steps described herein.

Several embodiments of the present invention have been described. However, it should be understood that the foregoing description is intended to illustrate, not to limit, the scope of the present invention, which is defined by the following claims. Therefore, other embodiments are also within the scope of the following claims. For example, various modifications may be made without departing from the scope of the present invention. Furthermore, some of the steps described above may be sequence-independent and, therefore, may be performed in an order different from that described.

Claims (23)

1. A system for managing data unit storage, the system comprising: A data storage system configured to store multiple data blocks, at least some of which comprise multiple data units, and at least one group of data blocks stored contiguously, thereby supporting a first read operation that retrieves data units from at least two adjacent data blocks in the group; and An interface, including at least one processor, coupled to the data storage system and configured to perform one or more operations relating to data units, including a deletion operation that replaces a first data block containing the data unit to be deleted with a second data block that does not include the deleted data unit, and stores historical information and additional information related to the previous removal of the deleted data unit, both of which are stored in the second data block, and the size of the additional information depends on the size of the historical information related to the previous removal of the deleted data unit, such that after the historical information and additional information related to the previous removal of the deleted data unit are stored in the second data block, the second data block has the same size as the first data block. 2. The system according to claim 1, wherein the second data block is adjacent to a data block that was previously adjacent to the first data block in the data storage system. 3. The system according to claim 1 or 2, wherein the second data block is stored in the same storage space as the first data block. 4. The system according to claim 1 or 2, wherein the deletion operation causes data blocks that are not the first data block to remain in the same storage location within the data storage system, and the data blocks that are not the first data block were stored in the storage location before the deletion operation was performed. 5. The system of claim 1 or 2, wherein the data storage system is configured to store, for at least some of the data blocks, corresponding historical information relating to the previous removal of one or more data units from the data block, the removal affecting the addresses of at least some data units in the data block. 6. The system of claim 5, wherein the operation includes a second read operation, distinct from the first read operation, which accesses at least one first data unit stored in the specific data block based on address information interpreted from historical information corresponding to any storage of the specific data block. 7. The system of claim 5, wherein at least some of the historical information is stored in the data storage system. 8. The system of claim 7, wherein at least a portion of the historical information is cross-accessed between different data blocks. 9. The system of claim 7, wherein at least a portion of historical information corresponding to a particular data block is stored in a predetermined portion of that particular data block. 10. The system of claim 6, wherein at least some of the data blocks are compressed data blocks. 11. The system of claim 10, wherein the second read operation decompresses a specific compressed data block to recover a set of decompressed data units, and retrieves the data unit to be read at a specific offset from a reference position based at least in part on the historical information corresponding to the specific compressed data block. 12. The system according to claim 10 or 11, wherein the first read operation decompresses a plurality of compressed data blocks and sequentially reads a plurality of decompressed data units. 13. The system according to any one of claims 10 or 11, wherein the first data block and the second data block are compressed data blocks, and the deletion operation expands the storage size of the second data block to fill the size difference between the second data block and the first data block. 14. The system of claim 13, wherein the storage size of the second data block is expanded by storing additional information in the second data block in addition to historical information. 15. The system of claim 10 or 11, wherein the deletion operation stores a new error detection code associated with the second data block to replace the error detection code associated with the first data block. 16. The system according to any one of claims 10 or 11, wherein the operation includes an add operation that stores data units to be added associated with a set of recently added data units. 17. The system of claim 16, wherein the processor is further configured to compress the recently added set of data units into compressed data blocks stored in a storage medium. 18. The system of claim 10 or 11, wherein the data storage system is configured to store additional information that identifies the plurality of data blocks in the group as conforming to a predetermined storage format. 19. The system of claim 18, wherein the additional information includes an identifier in the header of each data block in the group for identifying the predetermined storage format. 20. The system of claim 18, wherein the first read operation is compatible with the predetermined storage format. 21. A system for managing data unit storage, the system comprising: A means for storing multiple data blocks, wherein at least some of the multiple data blocks comprise multiple data units, and at least one group of data blocks is stored contiguously, thereby supporting a first read operation that retrieves data units from at least two adjacent data blocks in the group; and An apparatus for performing one or more operations relating to a data unit, the operations including a deletion operation that replaces a first data block containing the data unit to be deleted with a second data block that does not include the deleted data unit, and stores historical information and additional information relating to the previous removal of the deleted data unit, both of which are stored in the second data block, and the size of the additional information depends on the size of the historical information relating to the previous removal of the deleted data unit, such that after the historical information and additional information relating to the previous removal of the deleted data unit are stored in the second data block, the second data block has the same size as the first data block. 22. A method for managing data unit storage, the method comprising: Multiple data blocks are stored in a data storage system, at least some of the data blocks comprising multiple data units, and at least one group of the data blocks are stored contiguously, thereby supporting a first read operation that retrieves data units from at least two adjacent data blocks in the group; and At least one processor is used to perform one or more operations on a data unit, the operations including a deletion operation that replaces a first data block containing the data unit to be deleted with a second data block that does not include the deleted data unit, and stores historical information and additional information related to the previous removal of the deleted data unit, both of which are stored in the second data block, and the size of the additional information depends on the size of the historical information related to the previous removal of the deleted data unit, such that after the historical information and additional information related to the previous removal of the deleted data unit are stored in the second data block, the second data block has the same size as the first data block. 23. A computer-readable medium storing software for managing data units, the software including instructions for causing a computing system to perform the following operations: Multiple data blocks are stored in a data storage system, at least some of the data blocks comprising multiple data units, and at least one group of data blocks are stored contiguously, thereby supporting a first read operation that retrieves data units from at least two adjacent data blocks in the group; and Perform one or more operations on a data unit, including a deletion operation that replaces a first data block containing the data unit to be deleted with a second data block that does not include the deleted data unit, and stores historical information and additional information related to the previous removal of the deleted data unit, both of which are stored in the second data block, and the size of the additional information depends on the size of the historical information related to the previous removal of the deleted data unit, such that after the historical information and additional information related to the previous removal of the deleted data unit are stored in the second data block, the second data block has the same size as the first data block.