US20220342750A1

Movatterモバイル変換

Info

Publication number: US20220342750A1
Application number: US17/236,526
Authority: US
Inventors: Shu Li
Original assignee: Alibaba Singapore Holdings Pte Ltd
Current assignee: Alibaba Innovation Private Ltd
Priority date: 2021-04-21
Filing date: 2021-04-21
Publication date: 2022-10-27
Anticipated expiration: 2041-04-21
Also published as: US11461173B1

Abstract

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.

Description

BACKGROUNDField

This disclosure is generally related to the field of data storage. More specifically, this disclosure is related to a method and system for facilitating efficient data compression based on error correction code encoding and reorganization of data placement.

One existing solution which addresses the burden to the SSD is to send data blocks to the SSD with their corresponding logical block addresses (LBAs). The SSD can perform compression on the data block and send the compressed block size to the flash translation layer (FTL), which can merge multiple compressed data blocks of varying sizes into a physical page of the NAND flash. The FTL can maintain mapping information between the logical address of the original data block and the compressed data stored at the physical address. After accumulating sufficient compressed data blocks to be programmed, the SSD can perform an error correction code (ECC)-encoding on fixed-length portions of user data. Due to the varying sizes of the multiple compressed data blocks, some data blocks may be in the same ECC codeword, while other data blocks may be split across two ECC codewords.

This existing solution is limited by the following constraints: the FTL mapping table must store more information due to the varying sizes of the multiple compressed data blocks; a compressed data block which is split across two ECC codewords requires two separate ECC decodings; when a requested data block is stored at a physical block address (PBA) shared by other compressed data blocks, the system must read and decode the other compressed data blocks, which can lead to read amplification; and when a requested data block covers two physical NAND pages, two separate read operations are required, which can result in a non-trivial impact on the access latency.

Thus, while moving data compression to the SSD can provide transparent compression to a host, some challenges remain which affect the efficiency and performance of the overall storage system.

SUMMARY

In some embodiments, the plurality of data blocks are associated with logical block addresses (LBAs). The system stores, 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.

In some embodiments, 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. The header and the tail comprise a repeated pattern which is based on the index for the respective ECC-encoded data block.

In some embodiments, the system performs ECC-encoding on a respective compressed data block to obtain a respective ECC-encoded data block by: 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.

In some embodiments, the respective obtained ECC-encoded data block is written to the non-volatile memory as part of the first physical page. The system receives 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 written to the non-volatile memory. The system determines, 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. The system retrieves the requested data block from the determined PPA based on the index. The system performs ECC-decoding on the retrieved data block, and returns the ECC-decoded data block to a requesting application.

In some embodiments, 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. A user portion of the parity check matrix corresponds to the shortened user portion of the requested data block appended with user-associated zeros, e.g., a sufficient number of appended user-associated zeros to meet a full size of the user portion of the parity check matrix. A parity portion of the parity check matrix corresponds to the punctured parity of the requested data block appended with parity-associated zeros, e.g., a sufficient number of appended parity-associated zeros to meet a full size of the parity portion of the parity check matrix. 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. 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.

In some embodiments, performing 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.

In some embodiments, performing ECC-decoding is further based on bypassing the third portion based on a maximal confidence of all-zero circulants comprising the third portion.

BRIEF DESCRIPTION OF THE FIGURES

FIG. 1 illustrates an exemplary environment for facilitating data compression and placement, in accordance with the prior art.

FIG. 2 illustrates an exemplary environment for facilitating data compression and placement, in accordance with an embodiment of the present application.

FIG. 3A illustrates an exemplary NAND page which stores compressed data blocks, in accordance with an embodiment of the present application.

FIG. 3B illustrates an exemplary table which maps LBAs to PPA and an index, in accordance with an embodiment of the present application.

FIG. 4A illustrates an exemplary block diagram of an ECC encoding, including a shortened codeword, in accordance with an embodiment of the present application.

FIG. 4B illustrates an exemplary block diagram of an ECC encoding, including a punctured codeword, in accordance with an embodiment of the present application.

FIG. 4C illustrates an exemplary block diagram of an ECC encoding, corresponding toFIGS. 4A and 4B, in accordance with an embodiment of the present application.

FIG. 5 illustrates an exemplary block diagram of an ECC decoding, in accordance with an embodiment of the present application.

FIG. 6A presents a flowchart illustrating a method for facilitating data compression and placement, in accordance with an embodiment of the present application.

FIG. 6B presents a flowchart illustrating a method for facilitating data compression and placement, including ECC-encoding, in accordance with an embodiment of the present application.

FIG. 6C presents a flowchart illustrating a method for facilitating data compression and placement, including ECC-decoding, in accordance with an embodiment of the present application.

FIG. 7 illustrates an exemplary computer system that facilitates data compression and placement, in accordance with an embodiment of the present application.

FIG. 8 illustrates an exemplary apparatus that facilitates data compression and placement, in accordance with an embodiment of the present application.

In the figures, like reference numerals refer to the same figure elements.

DETAILED DESCRIPTION

The following description is presented to enable any person skilled in the art to make and use the embodiments, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present disclosure. Thus, the embodiments described herein are not limited to the embodiments shown, but are to be accorded the widest scope consistent with the principles and features disclosed herein.

Overview

The embodiments described herein provide a system which facilitates efficient data compression based on error correction code (ECC)-encoding and reorganization of data placement.

As described above, given the large amount of data to be processed and managed in a storage system, data compression is used increasingly in real-time applications. Because data compression can consume CPU core resources and affect online performance, data compression is sometimes offloaded using hardware acceleration. One current approach to reduce the access latency is for an application to send an original block of data to an SSD, where the SSD handles the data compression and metadata management. While this approach may make compression invisible to the host application, it can also result in a high burden to the SSD hardware and software.

One existing solution which addresses the burden to the SSD is to send data blocks to the SSD with their corresponding logical block addresses (LBAs). The SSD can perform compression on the data block and send the compressed block size to the flash translation layer (FTL), which can merge multiple compressed data blocks of varying sizes into a physical page of the NAND flash. The FTL can maintain mapping information between the logical address of the original data block and the compressed data stored at the physical address. After accumulating sufficient compressed data blocks to be programmed, the SSD can perform an error correction code (ECC)-encoding on fixed-length portions of user data. Due to the varying sizes of the multiple compressed data blocks, some data blocks may be in the same ECC codeword, while other data blocks may be split across two ECC codewords. An exemplary prior art environment is described below in relation toFIG. 1.

This existing solution is limited by the following constraints: the FTL mapping table must store more information due to the varying sizes of the multiple compressed data blocks; a compressed data block which is split across two ECC codewords requires two separate ECC decodings; when a requested data block is stored at a PBA shared by other compressed data blocks, the system must read and decode the other compressed data blocks, which can lead to read amplification; and a requested data block which covers two physical NAND pages, two separate read operations are required, which can result in a non-trivial impact on the read latency. These constraints are described further below in relation toFIG. 1.

The embodiments described herein provide a system which addresses these constraints by compressing incoming data blocks, performing ECC-encoding on each of the data blocks to obtain ECC-encoded data blocks (of varying sizes), and reorganizing the varyingly sized ECC-encoded data blocks to fit into a single programming unit of the physical media, such as a physical page of NAND flash in an SSD. An exemplary environment which facilitates data compression, ECC-encoding, and data placement is described below in relation toFIG. 2.

The system can maintain a data structure (such as a mapping table) which stores a mapping between: an LBA for a respective ECC-encoded data block; a physical page address (PPA) in a physical page at which the respective ECC-encoded data block is stored; and an index which indicates a location or offset for the respective ECC-encoded data block in the physical page. An exemplary NAND page and mapping table is described below in relation toFIGS. 3A and 3B.

The system can also perform ECC-encoding based on the varyingly sized compressed data blocks, by generating a shortened user portion and a punctured parity, which results in consuming less storage space in the storage drive, as described below in relation toFIGS. 4A-4C. In addition, the system can perform ECC-decoding based on this ECC-encoding, as described below in relation toFIG. 5.

Thus, the described embodiments provide a system which can compress, encode, and place data of varying lengths in order to reduce access latency, mitigate read amplification, and improve the quality of service (QoS). By protecting each individual compressed data block with its own ECC capsule, and by using the mapping table and data placement reorganization (to fit into and fill a single physical NAND page), the system can achieve an improvement in the efficiency and performance of the storage drive and the overall storage system. The described embodiments thus solve the technological problem of improving the efficiency and performance of a storage system by providing a technological solution based on space adjustment, block isolation, and a simplified representation.

A “distributed storage system” or a “storage system” can include multiple storage servers. A “storage server” or a “storage system” can refer to a computing device which can include multiple storage devices or storage drives. A “storage device” or a “storage drive” refers to a device or a drive with a non-volatile memory which can provide persistent storage of data, e.g., a solid-state drive (SSD), or a flash-based storage device. A storage system can also be a computer system.

“Non-volatile memory” refers to storage media which may be used for persistent storage of data, e.g., flash memory of a NAND die of an SSD, magnetoresistive random access memory (MRAM), phase change memory (PCM), resistive random access memory (ReRAM), or another non-volatile memory.

“Volatile memory” refers to media which may be used to store data temporarily and in which power is required to maintain the stored data. Examples of volatile memory include DDR DRAM.

A “computing device” refers to any server, device, node, entity, drive, or any other entity which can provide any computing capabilities.

The term “read amplification” refers to the situation in which the size or granularity of requested data is smaller than the size or granularity of the overall returned or retrieved data (e.g., from a basic physical unit of NAND flash in a read operation).

Exemplary Environment for Data Compression and Placement in the Prior Art

FIG. 1 illustrates anexemplary environment100 for facilitating data compression and placement, in accordance with the prior art.Environment100 can include ahost110 and a (storage)drive120. Host110 can include alocal file system112, ablock device layer114, and a driver116 (such as a non-volatile memory express (NVMe) driver). Drive120 can include a compression/decompression module orengine122, a flash translation layer (FTL)124, and a mapping table140. Drive120 can also include data stored in physical media, e.g., in aphysical page130.

During operation,driver116 can send a data block with its corresponding LBA (e.g., a data chunk and LBA150).Compression engine122 can compress the data block and generate a compressed data block152 (e.g., A132,B134,C136, etc.).Compression engine122 can also send the size of the compressed block (e.g., a size154) toFTL124, which can merge multiple compressed data blocks into a physical page of the NAND flash (e.g., via a merge data/mapping156 function into physical page130).

FTL

124 can create and maintain mapping information between the logical address of the original data block and the physical address at which the compressed data is stored. The physical address can include information mapped to each LBA, such as the corresponding PBAs, an offset, and a length. This information can be stored in mapping table140 (via a communication or operation158). For example, mapping table140 can store entries for each LBA, such as: an LBA x142 which is mapped to PBA information144 {PBA i, PBA i+1, offset, length}; andLBA y146 which is mapped to PBA information148 {PBA j, PBA j+1, offset, length}. Note that while only two PBAs are depicted as mapped to each of these exemplary LBAs, an LBA can be mapped to a greater or smaller number of PBAs than depicted inFIG. 1.

After the compressed data blocks (e.g., A132,B134,C136, etc.) accumulate to a size of a programming unit of the NAND flash (e.g., the size of a physical page), the system (e.g., by an ECC encoder, not shown) can perform an ECC encoding on the compressed data blocks. The ECC encoder can perform the ECC encoding on fixed-length blocks of user data, which results in the merged data blocks being divided or cut into multiple parts during the ECC-encoding. Thus, multiple compressed data blocks may be in the same ECC codeword, and some data blocks may be divided across or into two different ECC codewords. For example, anECC codeword 1160 can be based on compressed data blocks A132 andB134, as well as part of compresseddata block C136, and anECC codeword 2 can be based on a remaining portion of compresseddata block C136 and other compressed data blocks (not shown). Thus, compressed data blocks A132 andB134 are associated with thesame ECC codeword 1160, while compresseddata block C136 is divided across or associated with two different ECC codewords (ECC codeword 1160 andECC codeword 2162). In addition, certain blocks may be spread or divided across or into two different NAND pages (e.g., at the start or the end of a NAND page).

As described above, the prior art environment ofFIG. 1 is limited by certain constraints. First, due to the varying sizes of the multiple compressed data blocks, the FTL table must store a considerable amount of information, as shown in mapping table140. For example, a compressed data block which has a variable length (e.g., spans two or more PBAs) can require much more information to be recorded as compared to the scenario where only one PBA is required to be stored. Second, a compressed data block which is split across two ECC codewords (e.g., compresseddata block C136 which is split acrossECC codeword 1160 andECC codeword 2162) can require two separate ECC decodings, which can consume the resources ofdrive120 and thus negatively affect the quality of service (QoS). Third, when a requested data block is stored at a PBA which is shared by other compressed data blocks, the system must read and decode those other compressed data blocks, even though they are not part of the actual requested data. This can lead to a read amplification, which can reduce the read latency associated with the storage drive and with the overall storage system. Fourth, when a requested data block covers or spans two physical NAND pages, the system must perform two separate read operations, which can result in a non-trivial impact on the read latency, and can further result in a decreased performance and efficiency for the overall storage system.

Exemplary Environment for Multi-Stream Sequential Read Using Assigned Queues and LBA Comparator

The embodiments described herein address the challenges associated with the prior art environment ofFIG. 1 by providing a system which performs an optimization for compression in a storage drive, by using an ECC encoding and decoding (or “codec”) module and reorganizing the placement of data.

FIG. 2 illustrates anexemplary environment200 for facilitating data compression and placement, in accordance with an embodiment of the present application.Environment200 can include a plurality of data blocks A211,B212,C213,D214,E215, andF216. The system can receive these data blocks (via a communication250), and, the system, via acompression module220, can compress each of these data blocks and place the compressed data blocks in a compression buffer228 (via a communication252) as compressed data blocks A221,B222,C223,D224,E225, andF226.

Subsequently, anECC encoder230 can receive the compressed data blocks (via a communication254), perform ECC-encoding on each data block, and place these compressed and ECC-encoded data blocks into a backend buffer238 (via a communication256) (referred to also as “ECC-encoded data blocks”). The ECC-encoded data blocks can include A231,B232,C233,D234,E235, and F236 (as shown in backend buffer238). Note thatcompression buffer228 andbackend buffer238 can be a volatile memory associated with a storage drive, such as a dynamic random access memory (DRAM) associated with an SSD. In some embodiments,

buffers

228 and238 may be stored on DRAM associated with a host or entity other than the storage drive or storage device.

Once these compressed and ECC-encoded data blocks are placed inbackend buffer238, the system can reorganize the order of the ECC-encoded data blocks to match the size of a programming unit of the physical media (e.g., apage size240 of NAND flash memory). The system can perform this reordering based on the mapping of the logical addresses to the physical addresses. For example, the system can determine that ECC-encodeddata block C233 is too long to be stored together with ECC-encoded data blocks A231 andB232. Instead of splitting ECC-encodeddata block C233 across two different NAND pages (as in the prior art), the system can reorganize the blocks and place ECC-encoded data block D234 (which is of a shorter length than ECC-encoded data block C233) in the same page with A231 andB232 to match the page size by filling in the data as depicted.

When the system detects that a set of the reorganized ECC-encoded data blocks fill a physical page, the system can write the set of the ECC-encoded data blocks to the non-volatile memory. For example, the system can reorganize ECC-encoded data blocks A231,B232, andD234 to fill a physical page, and write these data blocks to a page_1242 of the non-volatile memory. Similarly, the system can reorganize ECC-encoded data blocksC233,E235, andF236 to fill a physical page, and write these data blocks to a page_2244 of the non-volatile memory.

Thus, in the embodiments described herein, the system performs ECC-encoding directly on each individual compressed data block, which avoids and eliminates splitting compressed data blocks across multiple ECC codewords. Furthermore, because compressed and ECC-encoded data blocks are stored in a same physical page, the FTL mapping table can store a reduced amount of information, as described below in relation toFIGS. 3A and 3B. These improvements can result in a reduced read latency, as well as an increase in the efficiency and performance of the storage drive and the overall storage system.

Exemplary NAND Page and Mapping Table

FIG. 3A illustrates anexemplary NAND page310 which stores compressed data blocks, in accordance with an embodiment of the present application.NAND page310 can store three compressed and ECC-encoded data blocks (A231,B232, and D234), as well as corresponding head and tail information for each of these data blocks. That is, each ECC-encoded data block can include: a head (H) prepended to the respective ECC-encoded data block; and a tail (T) appended to the respective ECC-encoded data block. The head and the tail can include a repeating pattern which is based on an index for the respective ECC-encoded block. The index can indicate a location or offset for the respective ECC-encoded data block within a given physical page, as depicted below in relation toFIG. 3B. For example, ECC-encodeddata block A231 can include ahead312 and atail314, which each have a samerepeating pattern330 of “b1b1b1b1b1b2b2b2b2b2b3b3b3b3b3,” based off of an index value of “b1b2b3.” Similarly, ECC-encodeddata block B232 can include ahead316 and atail318, which each have a same repeating pattern332 (based off of a corresponding index value for ECC-encoded data block B232). Finally, ECC-encodeddata block D234 can include ahead320 and atail322, which each have a same repeating pattern334 (based off of a corresponding index value for ECC-encoded data block D234).

FIG. 3B illustrates an exemplary table340 which maps LBAs to PPA and an index, in accordance with an embodiment of the present application. Table340 can be a data structure which is maintained by an FTL layer or module. Table340 can include entries which indicate, in multiple columns for a respective ECC-encoded data block, a mapping between: anLBA342 for the respective ECC-encoded data block; a physical page address (PPA)344 at which the respective ECC-encoded data block is written; and anindex346 which indicates a location or offset for the respective ECC-encoded data block in the physical page.

For example, for ECC-encoded data block A231 ofNAND page310, FTL mapping table can include anentry350, which maps anLBA_A352 to aPPA354 and an index value of “000.” Similarly, for ECC-encodeddata block B232 ofNAND page310, FTL mapping table340 can include anentry360, which maps anLBA_B362 to a physical address, which can be indicated by aPPA364 and an index value of “001.” Based on the value of the index, the system can create the repeating pattern of the head and tail for a given ECC-encoded data block. For example, if one NAND page can store eight compressed and ECC-encoded data blocks, a 3-bit index can indicate the requested LBA which corresponds to data blocks stored at the PPA in an order from left to right. For ECC-encodeddata block B232, based on the index value of “001” inentry360 of FTL mapping table340, the system can create a repeating pattern of “000000000011111” forhead316 andtail318 of ECC-encodeddata block B232 inNAND page310. The system can repeat each bit an odd number of times, such as five or seven, or can use any basis for the repeating pattern.

ECC Encoding with Shortened User Data and Punctured Parity

Because the compressed data blocks may be of varying sizes, as depicted above in relation toFIG. 2, the system can implement ECC-encoding to handle user bits within a range of lengths. Given a respective compressed data block, the system can reduce 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, as described below in relation toFIG. 4A. The system can perform an ECC encoding on the shortened user portion appended with or by zeros to obtain parity bits. The system can puncture the parity bits to obtain a punctured parity, as described below in relation toFIG. 4B. The system can write only the shortened user portion and the punctured parity to the non-volatile memory, as described below in relation toFIG. 4C. This can result in consuming a reduced amount of storage capacity for storing the data, which in turn can result in an increase in the available storage capacity as well as an increased efficiency and performance of the overall storage drive and storage system.

FIG. 4A illustrates an exemplary block diagram400 of an ECC encoding, including a shortened codeword, in accordance with an embodiment of the present application. Diagram400 depicts a conventional ECC codeword, including a user data (U)410 portion and a parity (P)412 portion, which corresponds to a full parity check matrix402 (e.g., the size of a full parity check matrix). The system can shorten user data (U)410 (via a shorten406 operation), which can result in a shortenedcodeword404, including a shortened user data (Us)414 portion and the parity (P)412 portion.

FIG. 4B illustrates an exemplary block diagram430 of an ECC encoding, including a punctured codeword, in accordance with an embodiment of the present application. Diagram430 depicts a conventional ECC codeword similar to diagram400, including user data (U)410 portion and a parity (P)412 portion, which corresponds to the size of a fullparity check matrix402. The system can “puncture” parity (P) bits412 (via apuncture436 operation, e.g., by removing a portion of the generated parity bits of parity (P)412). This can result in a puncturedcodeword434, including user data (U)410 and a punctured parity (Pc)portion432.

When the user data (U)410 (i.e., the compressed data bock) is shorter than the user submatrices of the full matrix, the system can chose the code with the closest approach. The ECC encoding can be based only on the user submatrix which is aligned with the incoming vector, since the remaining columns (corresponding to the appended zeros) are invalid and result in an equivalent zero effect. Shortenedcodeword404 can thus maintain the same error correction strength as the full codeword (which is of the size of full matrix402). The system can also puncture or remove a portion of the generated parity bits in order to reduce the ECC codeword to a size or a length which matches the variable lengths of incoming data blocks in one NAND page. The system may not use puncturedcodeword434 if it is not necessary, because thepuncture436 operation may be considered as erasure coding which can also consume part of the capability and resources for error correction.

FIG. 4C illustrates an exemplary block diagram of an ECC encoding, corresponding toFIGS. 4A and 4B, in accordance with an embodiment of the present application. During operation, the system can generate shortened user data (Us)414 (as depicted above in relation toFIG. 4A), and can append zeros442 (e.g., “user-associated zeros”) to shortened user data (Us)414 to match the size of the user portion of a full parity check matrix. The system, by anECC encoder450, can perform ECC-encoding on shortened user data (Us)414 appended with zeros, and can also puncture the generated and corresponding parity bits (as depicted above in relation toFIG. 4B) to obtain shortened user data (Us)414 and punctured parity (Pc)432, which the system can subsequently write as the respective compressed and ECC-encoded data block to the non-volatile memory. Note that the length or size of shortened user data (Us)414 and punctured parity (Pc)432 is less than or smaller than the length or size of the full parity check matrix, which is indicated by user data410 andparity412 with dashed border lines. Thus, diagrams400,430, and440 depict how the described embodiments can result in consuming a reduced amount of storage capacity, which can result in an increased overall storage capacity, increased efficiency, and improved performance for the overall storage system.

ECC Decoding Corresponding to ECC Encoding

The system can perform ECC decoding based on the ECC encoding scheme depicted above inFIGS. 4A-4C. The ECC parity check matrix can include circulants which are either an all-zero square matrix or a non-zero square matrix with a dimension of Qc. Thus, the length of a full ECC codeword is a multiple of Qc, and the length of the user bits and the parity bits are also each a multiple of Qc. The circulants can be either full circulants (e.g., corresponding to data which is of the length of a full Qc) or partial circulants (e.g., corresponding to data which is a fraction of or only makes up a portion of a full circulant). A compressed data block is likely to include both full circulants and a partial or fractional circulant, in that the compressed data may not exactly match the length of a multiple of Qc. Thus, the shortened user bits can correspond to part of a full parity check matrix and can include two portions: a full-circulant portion; and a fractional-circulant portion. In general, the system can control the length of the punctured parity portion as a full-circulant portion, although the punctured parity may also include a fractional-circulant portion for sufficient flexibility. An exemplary ECC decoding is described below in relation toFIG. 5.

FIG. 5 illustrates an exemplary block diagram500 of an ECC decoding, in accordance with an embodiment of the present application. Afull ECC codeword502 can include auser portion504 and aparity portion506.User portion504 can include: a shortened user data (Us′)510 portion; appended user-associated zeros512 (depicted with vertical lines); and appended user-associated zeros514 (depicted with right-slanting diagonal lines).Parity506 portion can include: a punctured parity (Pc′)516 portion; and parity-associated zeros518 (depicted with left-slanting diagonal lines).

Aparity check matrix508 can include auser portion Hu521 ofparity check matrix508 and aparity portion Hp531 ofparity check matrix508. Adetailed view509 ofparity check matrix508 can include non-zero circulants (indicated by a box with a solid shaded background and a “C”) as well as all-zero circulants (indicated by a box with a white background without a “C”).Detailed view509 ofparity check matrix508 can depict: a user portion520 (corresponding to Hu521) and a parity portion530 (corresponding to Hp531).User portion520 can include: afirst portion522 which includes full circulants and corresponds to shortened user data (Us′)510; asecond portion524 which includes partial circulants and corresponds to both the shortened user portion (portion525, corresponding to part of shortened user data (Us′)510) and part of the appended user-associated zeros (portion526, depicted with vertical lines and corresponding to appended user-associated zeros512); and athird portion528 which includes full circulants and corresponds to appended user-associated zeros514 (depicted with right-slanting diagonal lines).Parity portion530 can include: afourth portion532 which includes full circulants and corresponds to punctured parity (Pc′)516; and afifth portion534 which includes full circulants and corresponds to appended parity-associated zeros518 (depicted with left-slanting vertical lines).

During operation, the system can perform ECC-decoding based on: thefirst portion522; and thesecond portion524, further based on a maximal confidence of the partial circulants which correspond to the part (526) of the appended user-associated zeros; thefourth portion532; and the fifth portion, further based on a minimal confidence of the full circulants which correspond to the appended parity-associated zeros (534). The system can thus bypass thethird portion528 based on a maximal confidence of the zero-square circulants comprising thethird portion528.

Anindex540 can indicate three different scenarios for handling the zeros appended to the shortened user portion as well as the zeros appended as a result of puncturing the parity. In a first scenario, portion528 (depicted with right-slanting diagonal lines) can bypass ECC-decoding with a maximal confidence based on the all-zero bits of the full circulants. In a second scenario, portion534 (depicted with left-slanting diagonal lines) can join the ECC decoding with a minimal confidence, as the system does not know which bits of the parity were removed or punctured. The initial likelihood of a bit having a value of “0” is only 50% (or 0.5) probability, and there also exists a 50% (or 0.5) probability that the bit has a value of “1.” In the iterations of ECC-decoding, the value of the bit may evolve until it reaches a value which satisfies the parity check matrix, regardless of whether the parity portion includes full circulants or partial circulants.

In a third scenario, portion524 (including bothdata portion525 and appended user-associated zeros portion526) can join the ECC decoding. Becauseportion526 includes all zeros which were appended to align the codeword size with the size of the full parity check matrix, the system can set the value of those bits to zero with a maximal confidence (e.g., that the likelihood of those bits being zero is 100% (or 1.0). The appended zeros only join the ECC decoding to assist the decoding to converge.

Exemplary Method for Facilitating a Multi-Stream Sequential Read

FIG. 6A presents aflowchart600 illustrating a method for facilitating data compression and placement, in accordance with an embodiment of the present application. During operation, the system receives, by a storage device, a plurality of data blocks (operation602). The system compresses the data blocks to obtain compressed data blocks (operation604). The system performs error correction code (ECC)-encoding on the compressed data blocks to obtain ECC-encoded data blocks (operation606). 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 (operation608). The system 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 (operation610). 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 (operation612). The operation continues at Label A ofFIG. 6C.

FIG. 6B presents aflowchart620 illustrating a method for facilitating data compression and placement, including ECC-encoding, in accordance with an embodiment of the present application.Flowchart620 corresponds to the communications described above in relation toFIGS. 4A-4C. Given a respective compressed data block, the system reduces 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 (operation622). The system performs ECC-encoding on the shortened user portion appended by zeros to obtain parity bits (operation624). These “user-associated zeros” are appended so that the user portion meets the size of the user portion of the full parity check matrix. The system punctures the parity bits to obtain a punctured parity (operation626). The system generates the respective ECC-encoded data block which comprises the shortened user portion and the punctured parity (operation628).

FIG. 6C presents aflowchart640 illustrating a method for facilitating data compression and placement, including ECC-decoding, in accordance with an embodiment of the present application.Flowchart640 corresponds to the communications and operations described above in relation toFIG. 5. The system receives 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 written to the non-volatile memory, and wherein a parity check matrix for the requested data block comprises a plurality of circulants (operation642). The system determines, based on an LBA associated with the requested data block, a physical page address 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 (operation644). The system retrieves the requested data block from the determined physical page address based on the index (operation646) (e.g., as described above in relation toFIGS. 3A and 3B, including using the index in the data structure to determine and identify a corresponding repeating pattern in the header and tail of the respective ECC-encoded data block).

The system performs ECC-decoding on the retrieved data block based on a user portion of the parity check matrix and a parity portion of the parity check matrix, wherein the user portion includes 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 part of the appended user-associated zeros; and a third portion which includes full circulants and corresponds to the appended user-associated zeros, and wherein the parity portion includes 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 (operation648). Performing ECC-decoding on various portions of a retrieved data block is described above in relation toFIG. 5. The system returns the ECC-decoded data to a requesting application (operation650).

Exemplary Computer System and Apparatus

FIG. 7 illustrates anexemplary computer system700 that facilitates data compression and placement, in accordance with an embodiment of the present application.Computer system700 includes aprocessor702, avolatile memory706, and astorage device708. In some embodiments,computer system700 can include a controller704 (indicated by the dashed lines).Volatile memory706 can include, e.g., random access memory (RAM), that serves as a managed memory, and can be used to store one or more memory pools.Storage device708 can include persistent storage which can be managed or accessed via processor702 (or controller704). Furthermore,computer system700 can be coupled to peripheral input/output (I/O)user devices710, e.g., adisplay device711, akeyboard712, and apointing device714.Storage device708 can store anoperating system716, a content-processing system718, anddata736.

Content-processing system718 can include instructions, which when executed bycomputer system700, can causecomputer system700 orprocessor702 to perform methods and/or processes described in this disclosure. Specifically, content-processing system718 can include instructions for receiving and transmitting data packets, including data to be written or read, a data block, a compressed data block, an encoded data block, an LBA, and an input/output (I/O) request (e.g., a read request or a write request) (communication module720).

Content-processing system718 can further include instructions for receiving, by a storage device, a plurality of data blocks (communication module720). Content-processing system718 can include instructions for compressing the data blocks to obtain compressed data blocks (data-compressing module722). Content-processing system718 can include instructions for performing ECC-encoding on the compressed data blocks to obtain ECC-encoded data blocks (ECC-encoding module724). Content-processing system718 can include instructions for 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 (data-writing module726). Content-processing system718 can include instructions for 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 (buffer-managing module730). Content-processing system718 can include instructions for, responsive to a first set of the reorganized ECC-encoded data blocks filling a first physical page (buffer-managing module732), writing the first set of the reorganized ECC-encoded data blocks to the first physical page (data-writing module726).

Content-processing system718 can include instructions for 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 written to the non-volatile memory (communication module720). Content-processing system718 can include instructions for 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 (table-managing module732). Content-processing system718 can include instructions for retrieving the requested data block from the determined PPA based on the index (data-reading module734). Content-processing system718 can include instructions for performing ECC-decoding on the retrieved data block (ECC-decoding module728). Content-processing system718 can include instructions for returning the ECC-decoded data block to a requesting application (communication module720).

Data

736 can include any data that is required as input or generated as output by the methods and/or processes described in this disclosure. Specifically,data736 can store at least: data; a data block; a request; a read request; a write request; a logical block address (LBA); a physical block address (PBA); a physical page address (PPA); an index; a location or an offset; a data structure; a mapping table; compressed data; a compressed data block; encoded/decoded data; an encoded/decoded data block; ECC-encoded/decoded data; an ECC-encoded/decoded data block; an order of data blocks; a reorganized order; an indicator of a buffer; a set of reorganized ECC-encoded data blocks; data sufficient to fill a physical page; a header; a tail; a repeating pattern; a user portion; a shortened user portion; a parity portion; a punctured parity; a full parity check matrix; user-associated zeros; parity-associated zeros; a circulant; an all-zero square matrix; a non-zero square matrix; a full circulant; a partial or fractional circulant; a portion of an ECC codeword or a parity check matrix; and an indicator of whether a portion of data will join or bypass ECC-decoding.

FIG. 8 illustrates an exemplary apparatus800 that facilitates data compression and placement, in accordance with an embodiment of the present application. Apparatus800 can comprise a plurality of units or apparatuses which may communicate with one another via a wired, wireless, quantum light, or electrical communication channel. Apparatus800 may be realized using one or more integrated circuits, and may include fewer or more units or apparatuses than those shown inFIG. 8. Furthermore, apparatus800 may be integrated in a computer system, or realized as a separate device or devices capable of communicating with other computer systems and/or devices.

Apparatus800 can comprise modules or units802-816 which are configured to perform functions or operations similar to modules720-734 ofcomputer system700 ofFIG. 7, including: acommunication unit802; a data-compressingunit804; an ECC-encodingunit806; a data-writingunit808; an ECC-decodingunit810; a data-reorganizingunit812; a buffer-managingunit814; and a data-reading unit816.

The data structures and code described in this detailed description are typically stored on a computer-readable storage medium, which may be any device or medium that can store code and/or data for use by a computer system. The computer-readable storage medium includes, but is not limited to, volatile memory, non-volatile memory, magnetic and optical storage devices such as disk drives, magnetic tape, CDs (compact discs), DVDs (digital versatile discs or digital video discs), or other media capable of storing computer-readable media now known or later developed.

The methods and processes described in the detailed description section can be embodied as code and/or data, which can be stored in a computer-readable storage medium as described above. When a computer system reads and executes the code and/or data stored on the computer-readable storage medium, the computer system performs the methods and processes embodied as data structures and code and stored within the computer-readable storage medium.

Furthermore, the methods and processes described above can be included in hardware modules. For example, the hardware modules can include, but are not limited to, application-specific integrated circuit (ASIC) chips, field-programmable gate arrays (FPGAs), and other programmable-logic devices now known or later developed. When the hardware modules are activated, the hardware modules perform the methods and processes included within the hardware modules.

The foregoing embodiments described herein have been presented for purposes of illustration and description only. They are not intended to be exhaustive or to limit the embodiments described herein to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the embodiments described herein. The scope of the embodiments described herein is defined by the appended claims.

Claims

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 ofclaim 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 ofclaim 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. (canceled)

5. The method ofclaim 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.

6. (canceled)

7. The method ofclaim 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.

8. The method ofclaim 7, 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.

9. 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 ECC-decoding on the requested data block,

wherein the user portion of the parity check matrix comprises one or more of:

wherein the parity portion of the parity check matrix comprises one or more of:

10. The computer system ofclaim 9, 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;

11. The computer system ofclaim 10, 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,

12. (canceled)

13. The computer system ofclaim 9, 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:

and

14. (canceled)

15. The computer system ofclaim 9, wherein performing the ECC-decoding is based on:

the first portion;

the fourth portion; and

16. The computer system ofclaim 15, 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.

17. 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 ECC-decoding on the requested data block,

wherein the user portion of the parity check matrix comprises one or more of:

wherein the parity portion of the parity check matrix comprises one or more of:

18. (canceled)

19. The storage medium ofclaim 17, 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:

and

20. The storage medium ofclaim 17,

wherein performing the ECC-decoding is based on:

the first portion;

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.