Compression and Decompression of Data at High Speed in Solid State Storage

Abstract

Compression and decompression of data at high speed in solid state storage is described, including accessing a compressed data comprising a plurality of blocks of the compressed data, decompressing each of the plurality of blocks in a first stage of decompression to produce a plurality of partially decompressed blocks, and reconstructing an original data from the partially decompressed blocks in a second stage of decompression.

What is claimed is: 
     
         1 . A method, comprising:
 compressing data until a compressed portion of data approaches a limit associated with a predetermined block size, the limit being detected by a compressor;   padding the compressed portion up to the predetermined block size;   determining whether there is an uncompressed portion of data;   compressing the uncompressed portion, after determining there is the uncompressed portion, until another compressed portion of data approaches the limit; and   padding the another compressed portion up to the predetermined block size.   
     
     
         2 . The method of  claim 1 , further comprising, after determining there is no uncompressed portion:
 storing the compressed portion in a Flash memory chip; and   storing the another compressed portion in another Flash memory chip.   
     
     
         3 . The method of  claim 1 , wherein the padding the compressed portion comprises adding an arbitrary data portion and a code indicating where the arbitrary data portion begins. 
     
     
         4 . The method of  claim 1 , wherein the predetermined block size is associated with an error correction code block. 
     
     
         5 . The method of  claim 1 , wherein the predetermined block size is 512 bytes. 
     
     
         6 . The method of  claim 1 , wherein the compressing data is conducted using a lossless compression algorithm. 
     
     
         7 . The method of  claim 6 , wherein the lossless compression algorithm comprises Lempel-Ziv compression and variable length encoding. 
     
     
         8 . A system, comprising:
 a plurality of Flash chips;   a compression engine configured to compress data until a compressed portion of data approaches a limit of a predetermined block size, to pad the compressed portion up to the predetermined block size, to determine whether there is an uncompressed portion of data, to compress the uncompressed portion until another compressed portion of data approaches the limit of the predetermined block size, after determining there is the uncompressed portion, and to pad the another compressed portion up to the predetermined block size.   
     
     
         9 . The system of  claim 8 , wherein the plurality of Flash chips comprises 16 Flash chips. 
     
     
         10 . The system of  claim 8 , further comprising a plurality of buffers coupled to the plurality of decoders and configured to temporary buffer the partially decompressed data generated by the plurality of decoders. 
     
     
         11 . The system of  claim 10 , wherein each of the plurality of buffers includes an input and an output wherein the input is coupled to a decoder output of one of the plurality of decoders and the output is coupled to a multiplexer input of the multiplexer. 
     
     
         12 . The system of  claim 8 , further comprising a reverse Lempel-Ziv unit coupled to the multiplexer for providing decompressed data which is substantially similar to original data. 
     
     
         13 . A system, comprising:
 a plurality of Flash chips;   a decompression engine configured to access a compressed data comprising a plurality of blocks, each of plurality of blocks corresponding to a predetermined block size, to decompress each of plurality of blocks in a first stage of decompression to produce a plurality of partially decompressed blocks, and to reconstruct an original data from partially decompressed blocks in a second stage of decompression;   a decompression engine, decompression engine being configured to decompress said compressed data, said compressed data comprising a plurality of blocks, each of plurality of blocks corresponding to a predetermined block size, said decompression engine being further configured to decompress each of plurality of blocks in a first stage of decompression to produce a plurality of partially decompressed blocks, and to reconstruct an original data from partially decompressed blocks in a second stage of decompression; and   a decompression unit, wherein said decompression unit being configured to reconstruct said original data from partially decompressed blocks in said second stage of decompression.   
     
     
         14 . The system of  claim 13 , wherein the decompression engine comprises a variable length decoder, a FIFO, a multiplexer, and a reverse Lempel-Ziv unit. 
     
     
         15 . A memory system capable of storing data persistently, comprising:
 a plurality of nonvolatile memory (“NVM”) chips capable of storing data persistently, the plurality of NVM chips operable to store compressed data across multiple blocks between different NVM chips;   a plurality of decoders coupled to the plurality of NVM chips wherein each of the plurality of decoders is able to decompress a block of at least partially compressed data received from a designated NVM chip; and   a multiplexer coupled to the plurality of decoders and able to restore data from at least two blocks of partially decompressed data generated by different decoders,   wherein the plurality of NVM chips includes flash memory chips organized into multiple storage blocks.   
     
     
         16 . The system of  claim 15 , further comprising a plurality of buffers coupled to the plurality of decoders and configured to temporary buffer the partially decompressed data generated by the plurality of decoders. 
     
     
         17 . The system of  claim 16 , wherein each of the plurality of buffers includes an input and an output wherein the input is coupled to a decoder output of one of the plurality of decoders and the output is coupled to a multiplexer input of the multiplexer. 
     
     
         18 . The system of  claim 15 , further comprising a reverse Lempel-Ziv unit coupled to the multiplexer for providing decompressed data which is substantially similar to original data. 
     
     
         19 . The system of  claim 15 , wherein the plurality of decoders includes sixteen (16) variable length decoders (“VLDs”) wherein each of the sixteen (16) VLDs is dedicated to one of the sixteen (16) flash memory chips via a connection for providing a first stage of decompression. 
     
     
         20 . The system of  claim 15 , further includes sixteen (16) first-in-first-out circuits (“FIFOs”) situated between the sixteen (16) VLDs and the multiplexer for providing temporarily storage.