## 4 Asymmetric Programming: A Reliability Enhancement Scheme for Metadata
### Asymmetric Garbage Collection  
In NAND flash memory storage systems, a garbage collection operation normally includes the following three steps:  
* Step 1: The garbage collector picks up the victim block;
* Step 2: The garbage collector copies the valid pages of the victim block into a free block;
* Step 3: The garbage collector erases the victim block and adds the victim block into the free block pool.  
```
1:Valid pages in the valid page buffer. \(N_{p}\): The count of physical pages in one physical block.
2:Write the valid pages in the valid page buffer into a free physical block
3:for\(i=0\); \(i<N_{p}\), \(i++\)do
4:ifPPN #L (the Physical Page Number of page \(i\)) is LSB page then
5:Fetch one uncritical page (LPN #K ) from the valid page buffer
6:if there's no uncritical page in the valid page buffer then
7: Do nothing.
8:else
9: Write LPN #K into PPN #L
10: Kick LPN #K out of the valid page buffer
11: Update the mapping table
12:endif
13:endif
14:endif
15:endfor
```  
**Algorithm 2**Valid page copies in garbage collection for Asymmetric Programming.  
Steps 1 and 3 will not influence the location of critical pages in the MLC NAND flash memory. However, when the garbage collector copies valid pages from the victim block to a free block, we need to make sure that the critical pages are still stored in the MSB physical pages. To achieve this objective, step 2 of the garbage collection process has to be modified. We propose the asymmetric garbage collection strategy to handle this issue. Our basic idea is to use a small buffer to reorganize write requests. Algorithm 2 presents the basic procedures of the garbage collection operations in Asymmetric Programming.  
In Algorithm 2, a small buffer is used to store all valid pages from the victim block. Our strategy issues write operations for critical pages to the free block. For the LSB page of the free block, the asymmetric garbage collection strategy will look up the valid page buffer and fetch one uncritical page and write it into this physical LSB page (lines 2-10). If the writing process is finished successfully, the fetched uncritical page will be kicked out from the valid page buffer. For the MSB page of the free block, the asymmetric garbage collection strategy will try to fetch one critical page from the valid page buffer and write it into this physical MSB page then kick out the copied critical page out of the valid page buffer (lines 24-27). Thus, critical pages can still be ensured to be stored in physical MSB pages after the garbage collection process. If there's no critical pages left in the valid page buffer, then the asymmetric garbage collection strategy will fetch one uncritical page and copy it into this physical MSB page (lines 14-22). The garbage collection is done when all the valid pages in the valid page buffer are copied into the free block (line 30).  
We also use an example to illustrate the asymmetric garbage collection strategy. Figure 8 shows the example. For the purpose of illustration, we assume that there are eight pages in a physical block. One physical block is selected as the victim block. In this block, four pages are valid pages, and pages C and E belong to critical pages. These four valid pages will be copied to the buffer. Our strategy will first issue write operations for the uncritical page (_i.e._, page A). Similarly, another uncritical page will be written to page 1 following the sequential manner of programming in MLC NAND flash memory. For the physical page 2 and 3 which are MSB pages, our strategy will issue write operations for critical pages (_i.e._, pages C and E).  
Figure 8: An example of the valid page copy strategy of the asymmetric garbage collection.