Compression of Stream Data Using a Hierarchically-Indexed Database

• US 20090019345A1
• Filed: 09/18/2008
• Published: 01/15/2009
• Est. Priority Date: 02/13/2007
• Status: Active Grant

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: Packeteer Incorporated (Gen Digital Inc.)
• Inventors: Kaufman, Lev S., Phatak, Shirish H., Rangarajan, Murali
• Granted Patent: US 8,115,660 B2
• Time in Patent Office: Days
• US Class Current: 714/807
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/096 Checksums
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

Abstract

The present invention, in particular embodiments, is directed to methods, apparatuses and systems that provide an efficient compression technique for data streams transmitted to storage devices or over networks to remote hosts. Local storage as well as network transmission of streams is made more efficient by awareness and utilization of repeated sequences of data blocks. Such data blocks can be placed in a dictionary on persistent storage and shared across all streams. The dictionary is hierarchically indexed (two or more levels of indexing) to combine high efficiency search with efficient access to the stored data blocks. Additionally, data blocks, in particular implementations, are stored sequentially in order to improve overall performance.

Claims

1. A method for compressing data using a hierarchically-indexed database comprising:

accessing a contiguous block of data in an input data stream;

computing a weak checksum of the contiguous block of data;

accessing a first memory storing a first level index of a compression dictionary against the weak checksum to identify an entry associated with a bucket of one or more data block records;

if an entry in the first level index is identified, computing a strong checksum of the block of data and accessing a second level index stored in a second memory to identify a data block record of the identified bucket of data block records having a strong checksum matching the strong checksum of the block of data, wherein the second level index comprises one or more entries, wherein each entry of the second level index maps to a data block record, each data block record comprising a strong checksum and a pointer to a literal data block stored in the second memory; and

if a data block record is identified, outputting a reference value for the contiguous block of data.

2. The method of claim 1 wherein the reference value comprises the weak and strong checksums of the contiguous block of data.

3. The method of claim 1 wherein the first memory is dynamic, random access memory and the second memory is a mass storage device.

4. The method of claim 1 wherein the first level index is a hash table.

5. The method as recited in claim 1 further comprising caching one or more entries of the second level index in the first memory.

6. The method of claim 1 wherein accessing the contiguous block is done via a sliding window such that a first byte of the contiguous block is transferred to a pending buffer if the weak checksum does not match the one or more data block records and a new byte of the input data stream is added to an end of the contiguous block from an input buffer.

7. The method of claim 6 wherein bytes in the pending buffer are transmitted as a literal block if a size of the pending buffer meets a block size threshold.

8. The method of claim 1 wherein literal data of the data blocks is stored in a single file space and the pointers of the data block records identify corresponding locations in the single file space.

9. The method of claim 1 wherein each entry of the second level index includes a pointer field for another entry in the second level index.

10. A method for compressing data using a hierarchically-indexed database comprising:

accessing a contiguous block of data in an input data stream;

computing a weak checksum of the contiguous block of data;

accessing a first memory storing a first level index of a compression dictionary against the weak checksum to identify an entry associated with a bucket of one or more data block records;

if an entry in the first level index is identified, computing a strong checksum of the block of data and accessing a second level index of the compression dictionary to locate a data block record of the identified bucket of data block records having a strong checksum matching the strong checksum of the block of data, wherein the second level index comprises one or more entries, wherein each entry of the second level index maps to a data block record, each data block record comprising a strong checksum and a pointer to a literal data block stored in a second memory;

collecting a sequence of contiguous data blocks in the input data stream for which no data block records have been identified; and

inserting the contiguous data blocks of the sequence into the compression dictionary, wherein the inserting the contiguous data blocks in the compression dictionary comprises writing literal data of the contiguous data blocks of the sequence to the second memory in proximity.

11. The method of claim 10 wherein the inserting the contiguous data blocks of the sequence is conditionally executed in response to collecting a threshold number of contiguous data blocks.

12. The method of claim 10 wherein the inserting the contiguous data blocks of the sequence is conditionally executed in response to a time out.

13. The method of claim 10 wherein the inserting the contiguous data blocks of the sequence comprises

for each contiguous data block in the collected sequence:

computing weak and strong checksums for the contiguous data block;

creating a data block record for the contiguous data block in a buffer space;

then, for all contiguous data blocks of the sequence, writing the data block records in the buffer space and the literal data of the contiguous data block in the second memory.

14. The method of claim 13 wherein the data block records are appended in sequence to an end of a first file, and wherein the literal data of the contiguous data blocks are appended in the sequence to an end of a second file.

15. A method comprising:

accessing an input data stream;

matching contiguous data blocks in the input stream to one or more data block entries of a compression dictionary maintained in a memory;

collecting a sequence of contiguous data blocks in the input data stream to which no entries in the compression dictionary have been matched, wherein the sequence of contiguous data blocks matches an order of the contiguous data blocks in the input data stream; and

inserting the contiguous data blocks of the sequence into the compression dictionary maintained in the memory, wherein the inserting the contiguous data blocks in the compression dictionary comprises writing literal data of the contiguous data blocks in proximity according to the collected sequence.

16. The method of claim 15 further comprising if a data block entry is identified, outputting a reference value for the contiguous data block.

17. The method of claim 15 wherein the compression dictionary comprises a first level index, a second level index, one or more data block records and literal data of one or more contiguous data blocks,

wherein the first level index comprises one or more entries, wherein each entry of the first level index includes a weak checksum and is associated with one or more data blocks corresponding to the weak checksum;

wherein the second level index comprises one or more entries, wherein each entry of the second level index is associated with a single data block and maps to a data block record maintained in a file space of the compression dictionary; and

wherein each data block record of the one or more data block records comprises a strong checksum and a pointer to the literal data of a contiguous data block of the one or more contiguous data blocks.

18. The method of claim 17 wherein the first level index is maintained in a second memory.

19. The method of claim 18 wherein the memory is a mass storage device, and the second memory is a dynamic, random access memory.

20. The method of claim 17 wherein each entry of the second level index includes a field reserved for a pointer to another entry in the second level index that corresponds to a data block record sharing the same weak checksum as the data block record of the entry.

21. The method of claim 17 wherein the entries of the second level index comprises one or more linked lists each corresponding to a given weak checksum.

22. The method of claim 17 wherein the first level index is a hash table.

23. The method of claim 15 wherein the inserting the contiguous data blocks of the sequence is conditionally executed in response to collecting a threshold number of contiguous data blocks.

24. The method of claim 15 wherein the inserting the contiguous data blocks of the sequence is conditionally executed in response to a time out.

25. The method of claim 17 wherein the inserting the contiguous data blocks of the sequence comprises

for each contiguous data block in the collected sequence:

computing weak and strong checksums for the contiguous data block;

creating a data block record for the contiguous data block in a buffer space;

then, for all contiguous data blocks of the sequence, writing the data block records in the buffer space and the literal data of the contiguous data block in the memory.

26. The method of claim 25 wherein the data block records are appended to an end of a first file, and wherein the literal data of the contiguous data blocks are appended in the sequence to an end of a second file.

27. The method of claim 26 wherein the data block records are appended to the end of the first file in the order of the corresponding contiguous data blocks in the input data stream.

28. The method of claim 26 wherein the literal data of the contiguous data blocks are appended to the end of the second file in the order of the contiguous data blocks in the input data stream.

29. The method of claim 15 wherein the inserting the contiguous data blocks of the sequence comprises

for each contiguous data block in the collected sequence:

computing one or more checksums for the contiguous data block;

creating a data block record for the contiguous data block in a buffer space;

then, for all contiguous data blocks of the sequence, writing the data block records in the buffer space and the literal data of the contiguous data block in the memory.

30. The method of claim 29 wherein the data block records are appended to an end of a first file, and wherein the literal data of the contiguous data blocks are appended in the sequence to an end of a second file.

31. The method of claim 30 wherein the data block records are appended to the end of the first file in the order of the corresponding contiguous data blocks in the input data stream.

32. The method of claim 30 wherein the literal data of the contiguous data blocks are appended to the end of the second file in the order of the contiguous data blocks in the input data stream.

33. An apparatus comprising:

one or more processors;

one or more network interfaces;

a memory;

a software application, physically stored in the memory, comprising computer readable instructions operable, when executed, to cause the one or more processors and the apparatus to;

access an input data stream;

match contiguous data blocks in the input stream to one or more data block entries of a compression dictionary maintained in a memory;

collect a sequence of contiguous data blocks in the input data stream to which no entries in the compression dictionary have been matched, wherein the sequence of contiguous data blocks matches an order of the contiguous data blocks in the input data stream; and

insert the contiguous data blocks of the sequence into the compression dictionary maintained in the memory, wherein the inserting the contiguous data blocks in the compression dictionary comprises writing literal data of the contiguous data blocks in proximity according to the collected sequence.