Flash Translation Layer

Before I introduce The Flash Translation Layer, I’d like to introduce some basic information and characteristics of Solid-State Disks (SSDs).

SSDs are storage devices that use flash chips (usually NAND chips) to store information. The architecture of an SSD consists of multiple tiers, which are packages, dies, planes, blocks, and pages. Moreover, the typical size of a block is 128 KB, and the typical size of a page is 4KB. The granularity of each read and write is one page, and the granularity of each erase is one block. Each block can only be erased at certain times.

The blocks of the first part are called data blocks, and the blocks of the second part are called log-reservation blocks. (In my design, conceptually there is no difference between log-reservation blocks and clean-reservation blocks). I’ve designed two data structures for each part, and these two classes are Data Table and Log Table respectively. Besides that, I also created some classes to store other information. These are Pages, BlockMetaData, EraseInfo, and AgeInfo.

Class Pages uses two bool arrays to store the page state of each page. There are three states for each page, that are valid state, invalid state, and empty state. The valid state means that this page contains valid information. The invalid state means that this page no longer contains any valid information, but there is some content inside of it that needs to be erased. The empty state means this page is ready for writing any information into it.

Class BlockMetaData is used to store information on log reservation blocks. Because the pages in log reservation blocks must be written after the last written page within that block. So, there are two member variables for this class. One is Current Page Number, which is the index of the page in that block could be written. Another one is Block Number, which is the log block number. This class is only for each log block and is used to store the mapping between Data Block and Log Block. I will discuss this class later in the Log Table.

Class EraseInfo is used to store how many times each block has been erased. It only has one member variable, that is Erase Time.

Class AgeInfo is used to store the age of each block, and it can be used to decide which block that was least recently used in my FTL’s garbage collection policy decision.

Class DataTable contains the actual capacity that SSDs can use to store data.

The most important member variable is Data Map, it maps from logical data block to physical data block. Hence, a certain data block can be anywhere in SSDs instead of a fixed position. This design greatly helps write amplification and wear leveling, because each time one SSD erases a data block and its corresponding log block, then copies the valid pages into a clean block. Then this clean block is treated as a data block as the previous one, and the original data block and log block are garbage collected as log blocks. In this way, it only needs two erases to finish garbage collection. Moreover, if this data block is a hot block, with this remapping, it writes to other locations and performs great wear leveling.

DataTable also contains DataList, which stores data block numbers in a list in increasing order by erased times.

Class LogTable has four important member variables. They are Allocation Poll, Allocated Poll, Log Map, and Fast Map.

Allocation Poll is to allocate free blocks, and these blocks are arranged in increasing order by erased times, so each time it can be sure that the least erased free block is obtained.

Allocated Poll is over-provisioning capacity that is already allocated as log blocks. These blocks in Allocated Poll are also arranged in increasing order by erased times, so each time one log block is chosen to be erased, just hope it is the least erased one.

Log Map is to store the mapping from physical block number to BlockMetaData.

Fast Map is to store the mapping from LBA to PPN in log blocks because I want to reduce the time to find where the page is in the log block instead of traversing all the pages in that log block. Moreover, the space to store Fast Map shouldn't be big, because it only stores valid page mapping.

Even though the cleaning algorithm is written in the class-FTL. However, the LogTable is responsible for providing a log-reservation block number and the corresponding data block number that needs to be clean out of the garbage clean policy, and clean block number.

Round Robin:

In this policy, the log-reservation block chosen to clean is in a Round Robin manner. This is the simplest cleaning policy independent of the workload and recycles log-reservation blocks in the order that they are used.

Least Recent Used (LRU) Block:

This policy cleans the block that was least recently used (i.e. the block whose latest page was written farthest back in time). Note that a block whose pages are written multiple times need not necessarily have its latest written page in its mapped log-reservation block.

Greedy by Minimum Effort:

This policy chooses its target block from the point of view of minimum effort. The effort is decided based on the number of live pages that need to be copied in the multi-fold cleaning process described above.

LFS Cost-Benefit:

This is an implementation of the LFS cost-benefit policy [1]. The age of a block is how long it has been since a page in the block was last modified. That is, the age of a block is the current timestamp minus the timestamp of the most recently written page of the block. Note that timestamp can simply be a monotonically increasing integer value. The utilization is the fraction of the number of valid pages present in the mapped log-reservation block and the data block,

The cost-benefit ratio is calculated as follows:

There are some crucial points I’ve mentioned above for my FTL design. I’ll reiterate here.

Mapping

I designed two mappings. One is for DataTable, another one is for LogTable.

Data Map: (Logical Data Block Number, Physical Data Block Number).

Log Map: (Physical Data Block Number, Log Block Number). Note that this logical data block number is not LBA, it is the block number that this LBA fixed mapping to a data block. For example, LBA 0 always maps to Logical Data Block Number 0, because LBA / Block Size = 0.

This flexible mapping scheme amazingly helps to reduce write amplification and wear leveling. Each time when it executes garbage collection, there would be three different types of blocks conceptually. These are data block (physical data block), log-reservation block, and clean-reservation block. The clean-reservation block is always the first block of the allocation poll. After erasing the data block and log-reservation block, these two blocks are put into the allocation poll at certain positions by their erase times. The clean-reservation block then maps as the original data block.

In order to find one page in log-reservation block that maps from LBA quickly. I use a fast map to implement it: (LBA, PPN). PPN stands for physical page number. Therefore, log-reservation blocks only need to know the state of each page from class EraseInfo, which greatly reduces memory usage and quickly finds the target address.

Garbage Collection

My garbage collection policy is the cost-benefit policy. However, to proceed garbage collection procedure, one must provide a clean-reservation block. The chosen clean-reservation block is always the least erased free block in the allocation poll.

Wear Leveling