# Compression-Assisted Adaptive ECC and RAID Scattering for NAND Flash Storage Devices
## 3 Compression-Assisted Adaptive ECC and RAID Scattering
### RAID Scattering  
If data are compressed by the compression module, the size of the compressed data would be smaller than the original size, so it occupies only a specific part of the page. In our system, when the compressed data are stored in the flash memory, it is not stored from the beginning of the page but in a specific position in the page. This position is determined according to the stripe number where the page is located in the stripe. Therefore, RAID scattering is defined as positioning compressed data in a specific location on the page according to the position in the corresponding stripe. For instance, the architecture of RAID scattering with a stripe size four times larger than the page size is described in Figure 4. In the RAID configuration, \(SG\) (Stripe Group) is a group of blocks belonging to a stripe, and the notation \(BI\) (block index) is a block number in the stripe group; \(SB\) (Scatter Base) is a page size divided by the number of blocks in a stripe, and \(SI\) (Scatter Index) is the offset for the placement of each compressed data unit in a stripe group, calculated as \(SB\) multiplied by \(BI\). For each write request, the compressed data are placed at the offset value \(SI\) calculated by \(SB\) and \(BI\). If the data do not exceed the page size starting from a specific position, i.e., \(SI\), all of the compressed data can be stored on the page, as appropriate. If the amount of data exceeds the limit of the page, the remaining data are placed from zero offset at the page, in circular manner. For example, as shown in Figure 4, if the number of blocks in a stripe group is four and the page size is 8 KB, data \(D5\) are placed at offset zero in the page, data \(D6\) are placed at offset 2 KB, data \(D7\) is placed from offset 4 KB, and data \(D8\) is placed offset by 6 KB in the page, respectively. As a result, all compressed data can be placed at different positions within their stripes by the RAID scattering scheme. Then, RAID parity is created by xor operation of all data in the stripe. In Figure 4, \(P2\) is the RAID parity created through the xor operation of \(D5\), \(D6\), \(D7\), and \(D8\). In our system, if data cannot be recovered by in-page ECC, it will be recovered via the outer-page error recovery, i.e., RAID parity. In an existing RAID system, when attempting to recover an error page by using the RAID parity of the stripe group containing the page where the error occurred, all pages in the stripe group must be read to perform the xor operation. However, in the RAID scattering system, it is not necessary to read all pages of the stripe group. Instead of reading all the pages in the stripe group, it is only necessary to read the pages that overlap the actual valid area of the compressed data of the page where the error occurred. For instance, in Figure 4, let us assume errors occur during the read of data \(D5\), which means error is not recovered by in-page ECC. In this case, to recover data with RAID parity, the RAID scattering system reads only \(D6\) and \(D8\) and performs the xor operation to recover \(D5\). \(D7\) does not overlap with \(D5\), and hence reading for the recovery operation is unnecessary. To identify overlap information of pages in a stripe group, the length of the compressed data is added in a mapping-table in the FTL metadata. The compressed length is an important parameter to determine which pages are overlapped for recovery, as well as to decompress data for the read operation. The added length information is depicted in Figure 4. The length of valid data is represented by the actual length of the compressed data. In our implementation, the length field has a compact size for reducing metadata space overhead. For instance, a 12-bit field is required to represent a maximum length of 4 KB page, and a 13-bit field is required to represent a maximum length of 8 KB page. So maximum 3 bytes per entry is required for that.