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.
SSDs rely on firmware in the drive to perform multiple functions. When SSDs were first introduced, their radically different architecture, and the asymmetry between reads and writes (due to erase operations), required a completely different way of reading or writing to them. The Flash Translation Layer (FTL) is an abstraction introduced to maintain current file system and driver code as it is. The FTL translates the commands issued by file systems and user programs to an SSD-friendly format. Usually, the FTL is built into the SSD firmware.
Because of the characteristics of read, write, and erase operations and LBA issued by file systems, first, the FTLs need to correctly function, that is, translate an LBA into a correct physical address. Second, the FTLs also need delicate designs in order to increase their lifetime.
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.
Class FTL performs WriteTranslate, ReadTranslate, and Trim. The cleaning algorithm is performed in WriteTranslate when a write failure happens.
Figure 2: Flowchart for FTL read control flow
Figure 3: Flowchart for FTL write control flow
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.
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.
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.
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:
The policy dictates that the block to be cleaned is the one which has the largest cost-benefit ratio.
There are some crucial points I’ve mentioned above for my FTL design. I’ll reiterate here.
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.
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.
As I mentions these mappings above, I implemented I always choose the least erased block as a new log-reservation block or a clean-reservation block in the allocation poll.
Even with the help of my mapping scheme, it is still not enough for all circumstances. For example, if only one fixed LBA is written repeatedly, then only all the log-reservation blocks and this data block are written in cycles.
However, in order to relieve this situation, I use data migration. It will find a data block that doesn’t have a log-reservation block maps to it, and it also has lower erase times than the current clean-reservation block. The data block can be found in DataList in DataTable. The first qualified data block has the fewest erase times in that list. If there has such a data block, then the data block becomes the new clean-reservation block and then the original clean-reservation block has become the new data block. I introduce some fresh blocks beyond the previous range, so it has better wear leveling performance.
Github Repository for This Project: Flash Translation Layer