Method and system for facilitating efficient data compression based on error correction code and reorganization of data placement
View Patent ↗One embodiment provides a system which facilitates data management. During operation, the system receives, by a storage device, a plurality of data blocks. The system compresses the data blocks to obtain compressed data blocks, and performs error correction code (ECC)-encoding on the compressed data blocks to obtain ECC-encoded data blocks. The system stores the ECC-encoded data blocks in a buffer prior to writing the ECC-encoded data blocks in a non-volatile memory of the storage device, and reorganizes an order of the ECC-encoded data blocks in the buffer to match a size of a physical page of the non-volatile memory. Responsive to a first set of the reorganized ECC-encoded data blocks filling a first physical page, the system writes the first set of the reorganized ECC-encoded data blocks to the first physical page.
1. A computer-implemented method, comprising:
receiving, by a storage device, a plurality of data blocks;
compressing the data blocks to obtain compressed data blocks;
performing error correction code (ECC)-encoding on the compressed data blocks to obtain ECC-encoded data blocks, wherein performing ECC-encoding on a respective compressed data block to obtain a respective ECC-encoded data block comprises:
reducing a size of a user portion which corresponds to a full parity check matrix to obtain a shortened user portion which corresponds to a size of the respective compressed data block;
performing ECC-encoding on the shortened user portion appended by zeros to obtain parity bits; and
puncturing the parity bits to obtain a punctured parity, wherein the respective obtained ECC-encoded data block comprises the shortened user portion and the punctured parity;
storing the ECC-encoded data blocks in a buffer prior to writing the ECC-encoded data blocks in a non-volatile memory of the storage device;
reorganizing an order of the ECC-encoded data blocks in the buffer to match a size of a physical page of the non-volatile memory;
responsive to a first set of the reorganized ECC-encoded data blocks filling a first physical page, writing the first set of the reorganized ECC-encoded data blocks to the first physical page;
receiving a request to read a data block in the first physical page from the non-volatile memory, wherein the requested data block comprises the respective obtained ECC-encoded data block; and
performing ECC-decoding on the requested data block,
wherein a parity check matrix for the requested data block comprises a plurality of circulants,
wherein a respective circulant comprises an all-zero square matrix or a non-zero square matrix,
wherein a user portion of the parity check matrix corresponds to the shortened user portion of the requested data block appended with user-associated zeros,
wherein a parity portion of the parity check matrix corresponds to the punctured parity of the requested data block appended with parity-associated zeros,
wherein the user portion of the parity check matrix comprises one or more of:
a first portion which includes full circulants and corresponds to the shortened user portion;
a second portion which includes partial circulants and corresponds to both the shortened user portion and a first part of the appended user-associated zeros; and
a third portion which includes full circulants and corresponds to a second part of the appended user-associated zeros; and
wherein the parity portion of the parity check matrix comprises one or more of:
a fourth portion which includes full circulants and corresponds to the punctured parity; and
a fifth portion which includes full circulants and corresponds to the appended parity-associated zeros.
2. The method of claim 1 , wherein the plurality of data blocks are associated with logical block addresses (LBAs), and wherein the method further comprises:
storing, in a data structure, a mapping between:
a logical block address (LBA) for a respective ECC-encoded data block;
a physical page address in the first physical page at which the respective ECC-encoded data block is written; and
an index which indicates a location or offset for the respective ECC-encoded data block in the first physical page.
3. The method of claim 2 , wherein the first set of the reorganized ECC-encoded data blocks written to the first physical page comprises:
a header prepended to a respective ECC-encoded data block; and
a tail appended to the respective ECC-encoded data block,
wherein the header and the tail comprise a repeated pattern which is based on the index for the respective ECC-encoded data block.
4. The method of claim 1 , wherein the respective obtained ECC-encoded data block is written to the non-volatile memory as part of the first physical page, and wherein the method further comprises:
determining, based on a logical block address (LBA) associated with the requested data block, a physical page address (PPA) at which the requested data block is stored by searching a data structure which stores a mapping between the LBA, the PPA, and an index for the requested data block;
retrieving the requested data block from the determined PPA based on the index to obtain the requested data block;
and
subsequent to performing the ECC-decoding on the requested data block, returning the ECC-decoded data block to a requesting application.
5. The method of claim 1 , wherein performing the ECC-decoding is based on:
the first portion;
the second portion and further based on a maximal confidence of the partial circulants which correspond to the second part of the appended user-associated zeroes;
the fourth portion; and
the fifth portion and further based on a minimal confidence of the full circulants which correspond to the appended parity-associated zeros.
6. The method of claim 5 , wherein performing the ECC-decoding is further based on bypassing the third portion based on a maximal confidence of all-zero circulants comprising the third portion.
7. A computer system, comprising:
a processor; and
a memory coupled to the processor and storing instructions which, when executed by the processor, cause the processor to perform a method, the method comprising:
receiving, by a storage device, a plurality of data blocks;
compressing the data blocks to obtain compressed data blocks;
performing error correction code (ECC)-encoding on the compressed data blocks to obtain ECC-encoded data blocks, wherein performing ECC-encoding on a respective compressed data block to obtain a respective ECC-encoded data block comprises:
reducing a size of a user portion which corresponds to a full parity check matrix to obtain a shortened user portion which corresponds to a size of the respective compressed data block;
performing ECC-encoding on the shortened user portion appended by zeros to obtain parity bits; and
puncturing the parity bits to obtain a punctured parity, wherein the respective obtained ECC-encoded data block comprises the shortened user portion and the punctured parity;
storing the ECC-encoded data blocks in a buffer prior to writing the ECC-encoded data blocks in a non-volatile memory of the storage device;
reorganizing an order of the ECC-encoded data blocks in the buffer to match a size of a physical page of the non-volatile memory;
responsive to a first set of the reorganized ECC-encoded data blocks filling a first physical page, writing the first set of the reorganized ECC-encoded data blocks to the first physical page;
receiving a request to read a data block in the first physical page from the non-volatile memory, wherein the requested data block comprises the respective obtained ECC-encoded data block; and
performing ECC-decoding on the requested data block,
wherein a parity check matrix for the requested data block comprises a plurality of circulants,
wherein a respective circulant comprises an all-zero square matrix or a non-zero square matrix,
wherein a user portion of the parity check matrix corresponds to the shortened user portion of the requested data block appended with user-associated zeros,
wherein a parity portion of the parity check matrix corresponds to the punctured parity of the requested data block appended with parity-associated zeros,
wherein the user portion of the parity check matrix comprises one or more of:
a first portion which includes full circulants and corresponds to the shortened user portion;
a second portion which includes partial circulants and corresponds to both the shortened user portion and a first part of the appended user-associated zeros; and
a third portion which includes full circulants and corresponds to a second part of the appended user-associated zeros; and
wherein the parity portion of the parity check matrix comprises one or more of:
a fourth portion which includes full circulants and corresponds to the punctured parity; and
a fifth portion which includes full circulants and corresponds to the appended parity-associated zeros.
8. The computer system of claim 7 , wherein the plurality of data blocks are associated with logical block addresses (LBAs), and wherein the method further comprises:
storing, in a data structure, a mapping between:
a logical block address (LBA) for a respective ECC-encoded data block;
a physical page address in the first physical page at which the respective ECC-encoded data block is written; and
an index which indicates a location or offset for the respective ECC-encoded data block in the first physical page.
9. The computer system of claim 8 , wherein the first set of the reorganized ECC-encoded data blocks written to the first physical page comprises:
a header prepended to a respective ECC-encoded data block; and
a tail appended to the respective ECC-encoded data block,
wherein the header and the tail comprise a repeated pattern which is based on the index for the respective ECC-encoded data block.
10. The computer system of claim 7 , wherein the respective obtained ECC-encoded data block is written to the non-volatile memory as part of the first physical page, and wherein the method further comprises:
determining, based on a logical block address (LBA) associated with the requested data block, a physical page address (PPA) at which the requested data block is stored by searching a data structure which stores a mapping between the LBA, the PPA, and an index for the requested data block;
retrieving the requested data block from the determined PPA based on the index to obtain the requested data block;
and
subsequent to performing the ECC-decoding on the requested data block, returning the ECC-decoded data block to a requesting application.
11. The computer system of claim 7 , wherein performing the ECC-decoding is based on:
the first portion;
the second portion and further based on a maximal confidence of the partial circulants which correspond to the second part of the appended user-associated zeroes;
the fourth portion; and
the fifth portion and further based on a minimal confidence of the full circulants which correspond to the appended parity-associated zeros.
12. The computer system of claim 11 , wherein performing the ECC-decoding is further based on bypassing the third portion based on a maximal confidence of all-zero circulants comprising the third portion.
13. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:
receiving, by a storage device, a plurality of data blocks;
compressing the data blocks to obtain compressed data blocks;
performing error correction code (ECC)-encoding on the compressed data blocks to obtain ECC-encoded data blocks, wherein performing ECC-encoding on a respective compressed data block to obtain a respective ECC-encoded data block comprises:
reducing a size of a user portion which corresponds to a full parity check matrix to obtain a shortened user portion which corresponds to a size of the respective compressed data block;
performing ECC-encoding on the shortened user portion appended by zeros to obtain parity bits; and
puncturing the parity bits to obtain a punctured parity, wherein the respective obtained ECC-encoded data block comprises the shortened user portion and the punctured parity;
storing the ECC-encoded data blocks in a buffer prior to writing the ECC-encoded data blocks in a non-volatile memory of the storage device;
reorganizing an order of the ECC-encoded data blocks in the buffer to match a size of a physical page of the non-volatile memory;
responsive to a first set of the reorganized ECC-encoded data blocks filling a first physical page, writing the first set of the reorganized ECC-encoded data blocks to the first physical page;
receiving a request to read a data block in the first physical page from the non-volatile memory, wherein the requested data block comprises the respective obtained ECC-encoded data block; and
performing ECC-decoding on the requested data block,
wherein a parity check matrix for the requested data block comprises a plurality of circulants,
wherein a respective circulant comprises an all-zero square matrix or a non-zero square matrix,
wherein a user portion of the parity check matrix corresponds to the shortened user portion of the requested data block appended with user-associated zeros,
wherein a parity portion of the parity check matrix corresponds to the punctured parity of the requested data block appended with parity-associated zeros,
wherein the user portion of the parity check matrix comprises one or more of:
a first portion which includes full circulants and corresponds to the shortened user portion;
a second portion which includes partial circulants and corresponds to both the shortened user portion and a first part of the appended user-associated zeros; and
a third portion which includes full circulants and corresponds to a second part of the appended user-associated zeros; and
wherein the parity portion of the parity check matrix comprises one or more of:
a fourth portion which includes full circulants and corresponds to the punctured parity; and
a fifth portion which includes full circulants and corresponds to the appended parity-associated zeros.
14. The storage medium of claim 13 , wherein the respective obtained ECC-encoded data block is written to the non-volatile memory as part of the first physical page, and wherein the method further comprises:
determining, based on a logical block address (LBA) associated with the requested data block, a physical page address (PPA) at which the requested data block is stored by searching a data structure which stores a mapping between the LBA, the PPA, and an index for the requested data block;
retrieving the requested data block from the determined PPA based on the index to obtain the requested data block;
and
subsequent to performing the ECC-decoding on the requested data block, returning the ECC-decoded data block to a requesting application.
15. The storage medium of claim 13 ,
wherein performing the ECC-decoding is based on:
the first portion;
the second portion and further based on a maximal confidence of the partial circulants which correspond to the second part of the appended user-associated zeroes;
the fourth portion; and
the fifth portion and further based on a minimal confidence of the full circulants which correspond to the appended parity-associated zeros; and
wherein performing the ECC-decoding is further based on bypassing the third portion based on a maximal confidence of all-zero circulants comprising the third portion.