Efficient techniques for aligned fixed-length compression
AssigneePure Storage, Inc.
InventorsEthan Miller, John Colgrove, John Hayes
Life of this patent
Estimating the term…
Abstract
Systems and methods for performing compression of data. A data buffer is separated into equal-sized segments of data. A frequency count is performed to determine how often each segment of data appears in the data buffer. Frequently occurring segments are encoded with unique compression codes, while all other infrequently occurring segments are encoded with a common compression code. The compressed data buffer includes the compression codes, which are all of the same bit-length, and the uncompressed segments. The compression codes and the uncompressed segments are stored in the compressed data buffer in the order in which the corresponding segments appear in the original data buffer.
Claims21
A method comprising:
- partitioning a data buffer into a plurality of segments;
- determining how often each distinct segment value occurs within the data buffer;
- generating a fixed-length compression code for each segment of the plurality of segments, wherein said generating comprises:
- assigning a unique compression code for each value which occurs at least a given number of times;
- and
- assigning a common compression code to represent values which occur fewer than the given number of times;
- storing the generated compression codes and values which occur fewer than the given number of times consecutively in a compressed data buffer.
A method comprising:
- encoding each data segment of a plurality of data segments in a buffer with a fixed-length compression code, wherein a common fixed-length compression code is utilized to encode each of a plurality of infrequently occurring data segments;
- and
- appending the plurality of infrequently occurring data segments to the plurality of fixed-length compression codes.
A non-transitory computer readable storage medium comprising program instructions, wherein said program instructions are executable to:
- partition a data buffer into a plurality of segments, wherein the plurality of segments are of equal size;
- determine how often each distinct segment value occurs within the data buffer;
- generate a fixed-length compression code for each segment of the plurality of segments, wherein each frequently occurring segment value is assigned a unique fixed-length compression code, and wherein infrequently occurring segment values are assigned a common fixed-length compression code;
- store the generated compression codes and values which occur fewer than the given number of times consecutively in a compressed data buffer.
A system comprising:
- a storage medium;
- and
- an encoder configured to compress data, wherein said encoder is configured to:
- partitioning a data buffer into a plurality of segments;
- determining how often each distinct segment value occurs within the data buffer;
- generating a fixed-length compression code for each segment of the plurality of segments, wherein said generating comprises:
- assigning a unique compression code for each value which occurs at least a given number of times;
- and
- assigning a common compression code to represent values which occur fewer than the given number of times;
- storing the generated compression codes and values which occur fewer than the given number of times consecutively in a compressed data buffer.
Dependencies are inferred from the claim text.