System and methods for accelerated data storage and retrieval

• US 8,756,332 B2
• Filed: 10/26/2006
• Issued: 06/17/2014
• Est. Priority Date: 03/11/1999
• Status: Expired due to Fees

• Current Assignee: Realtime Data LLC (Realtime Data Compression Systems, Inc.)
• Original Assignee: Realtime Data LLC (Realtime Data Compression Systems, Inc.)
• Inventors: Fallon, James J
• Primary Examiner(s): Tran, Philip B
• Application Number:
  US11/553,419
• Publication Number:
  US 20070050514A1
• Time in Patent Office: 2,791 Days
• Field of Search: 709/231, 709/233, 709/203, 709/247, 709/224
• US Class Current: 709/231
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/15 by monitoring actual compressed data size at the memory before deciding storage at the transmission buffer
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 5/781 on disks or drums
• CPC Class Codes: H04N 5/843 on film
• CPC Class Codes: H04N 5/85 on discs or drums
• CPC Class Codes: H04N 5/907 using static stores, e.g. storage tubes or semiconductor memories H04N5/91 takes precedence
• CPC Class Codes: H04N 9/8042 involving data reduction
• CPC Class Codes: H04N 9/8227 the additional signal being at least another television signal

Abstract

Systems and methods for providing accelerated data storage and retrieval utilizing lossless data compression and decompression. A data storage accelerator includes one or a plurality of high speed data compression encoders that are configured to simultaneously or sequentially losslessly compress data at a rate equivalent to or faster than the transmission rate of an input data stream. The compressed data is subsequently stored in a target memory or other storage device whose input data storage bandwidth is lower than the original input data stream bandwidth. Similarly, a data retrieval accelerator includes one or a plurality of high speed data decompression decoders that are configured to simultaneously or sequentially losslessly decompress data at a rate equivalent to or faster than the input data stream from the target memory or storage device. The decompressed data is then output at rate data that is greater than the output rate from the target memory or data storage device. The data storage and retrieval accelerator method and system may employed: in a disk storage adapter to reduce the time required to store and retrieve data from computer to disk; in conjunction with random access memory to reduce the time required to store and retrieve data from random access memory; in a display controller to reduce the time required to send display data to the display controller or processor; and/or in an input/output controller to reduce the time required to store, retrieve, or transmit data.

Claims

1. A system comprising:

a memory device; and

a data accelerator coupled to said memory device, wherein;

said data accelerator compresses a data stream that includes a plurality of data blocks to provide a compressed data stream,

said data accelerator stores said compressed data stream on said memory device,

said compression and said storage occurs faster than said data stream is able to be stored on said memory device in uncompressed form, and

said compression of said data stream comprises, for each data block in the plurality of data blocks;

compressing the data block with a plurality of encoding techniques to provide a plurality of compressed data blocks; and

determining one of said plurality of compressed data blocks to provide as part of said compressed data stream.

2. The system of claim 1, wherein said memory device is a magnetic storage device.

3. The system of claim 1, wherein said memory device is an optical storage device.

4. The system of claim 1, wherein said memory device is a solid-state mass storage device.

5. The system of claim 1, wherein said memory device is a volatile storage device.

6. The system of claim 1, wherein said memory device is a non-volatile storage device.

7. The system of claim 1, wherein said memory device comprises a random access memory.

8. The system of claim 1, wherein the size of each data block in said plurality of data blocks is a fixed size.

9. The system of claim 1, wherein the size of each data block in said plurality of data blocks is a variable size.

10. The system of claim 1, wherein said data accelerator receives said data stream at a first rate, said compression and storage of said data stream occurs at a second rate, and said second rate is equal to said first rate.

11. The system of claim 1, wherein said data accelerator receives said data stream at a first rate, said compression and storage of said data stream occurs at a second rate, and said second rate is greater than said first rate.

12. The system of claim 1, wherein said data accelerator receives said data stream and stores said received data stream in a buffer.

13. The system of claim 1, wherein said data accelerator receives said data stream from a device at a first rate and said accelerator signals said device to provide data to said data accelerator at a second rate.

14. The system of claim 1, wherein said data accelerator receives said data stream from a device at a first rate, said accelerator provides a signal to said device to provide data to said data accelerator at a second rate, and said second rate is less than said first rate.

15. The system of claim 1, wherein said data stream is compressed by compressing a first of said plurality of data blocks and, upon completion of compressing the first of said plurality of data blocks, compressing a second of said plurality of data blocks.

16. The system of claim 1, wherein said data stream is compressed by compressing a first of said plurality of data blocks and a second of said plurality of data blocks, and determining whether said data stream includes an additional data block.

17. The system of claim 1, wherein said compression of said data stream comprises dictionary compression.

18. The system of claim 1, wherein said compression of said data stream comprises run-length compression.

19. The system of claim 1, wherein said compressed data stream that is stored on said memory device is retrieved.

20. The system of claim 1, wherein said compressed data stream that is stored on said memory device is retrieved and decompressed.

21. The system of claim 1, wherein said compressed data stream that is stored on said memory device is retrieved, decompressed, and outputted.

22. The system of claim 1, wherein said data stream is an archive.

23. The system of claim 1, wherein said data stream comprises collections of multiple files.

24. The system of claim 1, further comprising:

determining a first compression ratio associated with the determined one of said plurality of first compressed data blocks;

compressing a second of said plurality of data blocks to provide a second compressed data block; and

determining a second compression ratio associated with said second compressed data block.

25. The system of claim 1, wherein said compression of said data stream includes compressing a first of said plurality of data blocks using a single encoder.

26. The system of claim 1, wherein said compression of said data stream includes compressing a first of said plurality of data blocks using a plurality of encoders.

27. The system of claim 1, wherein said compression of said data stream includes compressing a first of said plurality of data blocks with a plurality of encoders in a sequential configuration.

28. The system of claim 1, wherein said compression of said data stream includes compressing a first of said plurality of data blocks with a plurality of encoders in a parallel configuration.

29. The system of claim 1, wherein said compression of said data stream comprises:

compressing a first of said plurality of data blocks with at least a first encoder to provide a first compressed data block,

compressing a first of said plurality of data blocks with at least a second encoder to provide a second compressed data block,

comparing the size of said first and second compressed data blocks, and

providing either said first or second compressed data block to said compressed data stream as a result of said size comparison.

30. The system of claim 1, wherein said compression of said data stream includes compressing a first of said plurality of data blocks with Huffman encoding.

31. The system of claim 1, wherein said compression of said data stream includes compressing a first of said plurality of data blocks with Lempel-Ziv encoding.

32. The system of claim 1, wherein said compression of said data stream includes compressing a first of said plurality of data blocks with a plurality of encoders in a parallel configuration and said plurality of encoders are of an identical type.

33. The system of claim 1, wherein said compression of said data stream includes compressing a first of said plurality of data blocks with a plurality of encoders in a parallel configuration, said plurality of encoders are of an identical type, and said identical type is Huffman encoding.

34. The system of claim 1, wherein:

said compression of said data stream comprises compressing a first of said plurality of data blocks with a first encoder and compressing a second of said plurality of data blocks with a second encoder; and

said storing said compressed data stream to said memory device further comprises storing a first descriptor indicative of said first encoder and a second descriptor indicative of said second encoder to said memory device.

35. The system of claim 1, wherein:

said compression of said data stream comprises compressing a first of said plurality of data blocks with a first encoder and compressing a second of said plurality of data blocks with a second encoder,

said storing said compressed data stream to said data memory device further comprises storing a first descriptor indicative of said first encoder and a second descriptor indicative of said second encoder, and

said compressed data stream is decompressed using said first and second descriptors.

36. The system of claim 1, wherein:

said compression of said data stream comprises compressing a first of said plurality of data blocks with a first encoding technique to provide a first compressed data block and providing said first compressed data block as a portion of said compressed data stream,

a descriptor is stored on said memory device indicative of said first encoding technique, and

said first compressed data block is decompressed using said descriptor.

37. A system comprising:

a memory device; and

a data accelerator, wherein;

said data accelerator is coupled to said memory device,

a data stream is received by said data accelerator in received form,

said data stream includes a plurality of data blocks,

said data stream is compressed by said data accelerator to provide a compressed data stream,

said compressed data stream is stored on said memory device,

said compression and said storage occurs faster than said data stream is able to be stored on said memory device in said received form, and

said compression of said data stream comprises;

selecting a subset of encoders from a plurality of encoders, and enabling the selected subset of encoders;

for each data block in the plurality of data blocks;

compressing the data block with a plurality of encoding techniques to provide a plurality of compressed data blocks, wherein said compressing is performed using the enabled subset of encoders; and

determining one of said plurality of compressed data blocks to provide as part of said compressed data stream.

39. The system of claim 37, wherein said memory device is a magnetic storage device.

40. The system of claim 37, wherein said memory device is an optical storage device.

41. The system of claim 37, wherein said memory device is a solid-state mass storage device.

42. The system of claim 37, wherein said memory device is a volatile storage device.

43. The system of claim 37, wherein said memory device is a non-volatile storage device.

44. The system of claim 37, wherein said memory device comprises a random access memory.

45. The system of claim 37, wherein said compression of said data stream comprises dictionary compression.

46. The system of claim 37, wherein said compression of said data stream comprises run-length compression.

47. The system of claim 37, wherein said compressed data stream that is stored on said memory device is retrieved.

48. The system of claim 37, wherein said compressed data stream that is stored on said memory device is retrieved and decompressed.

49. The system of claim 37, wherein said compressed data stream that is stored on said memory device is retrieved, decompressed, and outputted.

50. The system of claim 37, wherein said data stream is an archive.

38. A system comprising:

a memory device; and

a data accelerator, wherein;

said data accelerator is coupled to said memory device,

a data stream is received by said data accelerator in received form,

said data stream includes a plurality of data blocks,

said data stream is compressed by said data accelerator to provide a compressed data stream by compressing a first of said plurality of data blocks with a first encoder and a second of said plurality of data blocks with a second encoder,

said first and second encoders are different,

said compressed data stream is stored on said memory device, and

said compression and said storage occurs faster than said data stream is able to be stored on said memory device in said received form, and

said compression comprises;

compressing the first of said plurality of data blocks with a plurality of encoding techniques to provide a plurality of first compressed data blocks;

compressing the second of said plurality of data blocks with the plurality of encoding techniques to provide a plurality of second compressed data blocks; and

determining one of the plurality of first compressed data blocks and one of the plurality of second compressed data blocks to provide as part of said compressed data stream.

51. The system of claim 38, wherein said memory device is a magnetic storage device.

52. The system of claim 38, wherein said memory device is an optical storage device.

53. The system of claim 38, wherein said memory device is a solid-state mass storage device.

54. The system of claim 38, wherein said memory device is a volatile storage device.

55. The system of claim 38, wherein said memory device is a non-volatile storage device.

56. The system of claim 38, wherein said memory device comprises a random access memory.

57. The system of claim 38, wherein said compression of said data stream comprises dictionary compression.

58. The system of claim 38, wherein said compression of said data stream comprises run-length compression.

59. The system of claim 38, wherein said compressed data stream that is stored on said memory device is retrieved.

60. The system of claim 38, wherein said compressed data stream that is stored on said memory device is retrieved and decompressed.

61. The system of claim 38, wherein said compressed data stream that is stored on said memory device is retrieved, decompressed, and outputted.

62. The system of claim 38, wherein said data stream is an archive.