## 4 Asymmetric Programming: A Reliability Enhancement Scheme for Metadata
### MSB Allocation  
Our MSB allocation strategy issues write operations based on the content stored in a page. Algorithm 1 describes the process of a write operation. Algorithm 1 has two inputs: a logical page number (LPN) and its content. The algorithm will first distinguish critical pages, which contains metadata of the system, from non-critical pages. If the request is a critical page, the FTL allocates one physical page for the request (line 1). The MSB allocation strategy tries to allocate critical pages to MSB pages. It will look up the shared pages mapping table, which is configured by the chip manufacturer, to check the allocated physical page whether a MSB page or not. To the best of our knowledge, this is the first work that utilizes the shared pages mapping table to achieve the recognition of the LSB page and the MSB page in the FTL. ```
0: A logical page number (_LPN_ #_M), LPN page content. 0: Write the content to one physical page
1: FTL allocates a PPN #_N for LPN #_M
2:ifLPN #_M is a critical page then
3: Query the shared pages mapping table to check if PPN #_N is MSB page
4:ifPPN #_N is MSB page then
5: Write LPN #_M into PPN #_N
6:else
7: Invalidate the mapping <_LPN #_M, PPN #_N>
8: Send a signal to Request Queue Scheduler to delay the current request
9:if there's no uncritical page request then
10: Find the nearest MSB page
11: Invalidate all the pages between the current page and the nearest MSB physical page
12:endif
13:endif
14: Finish
15:endif
16: Update the mapping table
17: Write the content into NAND flash
```  
**Algorithm 1** Write operation for Asymmetric Programming. If the page does not contain metadata (lines 16-17), the MSB allocation strategy will bypass the shared pages mapping table. Such write requests will be directly issued to available free pages in the sequential manner of programming. Both the LSB and MSB pages can be utilized to store normal data. Figure 6 shows an example of the MSB allocation strategy. For the write request (LPN #2, A), where A is the content to be written in the NAND flash and LPN #2 belongs to a critical page, the MSB allocation strategy will search the logical page number to the physical page number (PPN) addressing mapping table maintained by the FTL and find the corresponding PPN (PPN #4). It will further check the shared pages mapping table provided by the chip manufacturer. This table indicates that PPN #4 belongs to MSB pages. The MSB allocation strategy will then write content A to the MSB page. For the write request (LPN #4, B), which denotes a non-critical page, our strategy will bypass the search operation in the shared pages mapping table and issue a write operation to the PPN provided by the FTL (_i.e._, PPN #7). If the FTL assigns an LSB page to a critical page, the MSB allocation strategy will send a signal to the Request Queue Scheduler to delay this request. The next uncritical page write request will be kicked out to fit this LSB page. Then the Request Queue Scheduler will serve the delayed request again and repeat the above operations to allocate a MSB physical page for the critical write request. This procedure is called a request feedback operation. If no non-critical page is available in the request queue (lines 9-12), the next available MSB page will be found directly. The pages between the current page and the next available MSB page will be marked as invalid. In this way, the MSB strategy can guarantee that the next critical page will be served by an MSB page. Figure 7 shows an example of request feedback operation where W0 is a critical page write request and W1-4 are three uncritical page requests. Pure page-level FTL is adopted in this example. In the first step, the FTL allocate PPN0 for the request W0. But as W0 is a critical page request and PPN0 is a LSB physical page, our asymmetric programming strategy invalidates this mapping, and delays W0. Then it will allocate W1 which is an uncritical page request to PPN0. This process is a request feedback operation.