This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
This paper proposes a Hybrid Flash Translation Layer for flash memory. Flash memory usually suffers a setback, as they employ erase-data before writing-data policy. Flash translation layer is a software layer present in flash memory for block management. Several FTLs proposed are not effective enough to succumb and succeed in real time. Many FTL implementations have minimal utilization of space or high overhead for erasing or inefficient mapping techniques. Hence, an enhanced FTL is proposed to overcome the difficulties faced in maintaining as well using flash memory. This proposed model has efficient mechanisms defined for performing write operations, merging data and erasing data with little overhead. Implementation of this model over FTL, would allow block management in flash memory to be done efficiently.
Flash drives are a fast emerging technology. These drives form the most convenient form of storage for the sophisticated devices. They consist of memory called the flash memory. Flash memory offers non-volatile form of storage. Power failures do not cause any data loss, as the data is retained in the memory. Power consumption of flash memory is low in comparison to traditional hard drives or disks.
Mobile devices like cellular phones, digital cameras have gained great demand in the recent past. These devices are encouraged to be of small size, resistant to shock etc. To satisfy these requirements, the design of the traditional memory devices had to be modified. Flash memory provided the immediate solution to support these mobile devices. They are non -volatile and also could be overwritten once the data is erased. The most common applications of flash memory are the flash drives, iPods, pen drives, solid state drives etc.
NAND flash memory is the latest choice of storage in small configurable consumer applications. With features like less power consumption, high access speed, inexpensive makes it a better choice than hard disks. The memory is usually divided into blocks which in turn consist of pages of data. To manage the data in such flash drives, a software layer called the Flash Translation (FTL) is maintained.
FTL is used for block management, address mapping and also acts as a layer on top of the storage to handle storage necessities . Request for read/write operation is often directed to the FTL which executes the request by mapping to free area in the flash memory. The way heart is to humans, FTL is to flash memory.
A setback in the flash memory is that it supports rewriting of data only after erasing the data present. Erasing of data is usually done in blocks thus decreasing the scope of utilizing spatial locality in memory. And also the numbers of erase operations that can be performed on the memory are limited though large. Another major drawback of flash memory is that it supports sequential access of large amounts of data thus depreciating the overall performance of FTL.
For these reasons, continuous research is being done in improving the FTL of flash memory. Several schemes have been proposed to decrease the overhead of erasing of blocks, improved mapping of the incoming data as well with effective address mapping by implementing better mechanisms over the FTL.
2.1 Flash Translation Layer:
Flash memory is organized as blocks; blocks contain data arranged in pages. The number of pages possessed in a block depends on the architecture of the underlying system. Blocks usually contain pages full of data or free pages. On receiving a request for write operation, the data present in the blocks has to be emptied i.e. erased before writing the new data. Erase operation requires reclamation of the page's memory.
Many advanced FTL schemes have come into existence that support efficient handling of write requests. When data has to be written to the memory, instead of performing the erase operation, the data is redirected to free space on memory and is written there until garbage collection process is done over data. The page which contains the data initially is called the physical level page, and the data written at a redirected location is called the logical level page. Flash translation layer facilitates the mapping between logical level pages to the physical level page.
Mapping can be performed at different levels based on the nature of the FTL defined. The mapping is usually done:
Mapping at page level
Mapping at block level
Mapping at page level: This is the most basic type of mapping that is used. In this type, mapping is done between the logical level page and the physical level page. Every logical level page is mapped to some or the other physical level page. These logical level pages belonging to a common block can be mapped to more than one physical level page.
The main disadvantage of this kind of mapping is that the memory requirement for maintenance of such mapping table is very high. For every logical level page, an entry of the relevant physical level page has to be entered thus increasing the space required.
Mapping at block level: This type of mapping overcomes the setbacks of using page level mapping. Here, mapping is done between the blocks instead between the pages. Logical level blocks are identified and all the pages in the block are mapped to the corresponding physical level block.
Unlike page level mapping, this mapping technique requires less space for maintaining mapping table for logical level blocks to physical level blocks. Despite this advantage, this mechanism offers poor utilization of space. When a logical level block is to be written, the whole logical level block is written to the physical level block. Erasing the whole block before the new block of data is written degrades the overall performance.
Hybrid mapping: Combination of advantages of page level mapping and block level mapping resulted in the development of hybrid mapping techniques schemes on Flash Translation Layer. Data is usually organized in blocks called the 'data blocks' and hence the scheme employed in maintaining the mapping table is block level mapping. Therefore, the requirement of large memory space to support the maintenance of mapping table is minimized.
'Log blocks' consisting of pages that are updated frequently are maintained. These pages are maintained using the page level mapping scheme. Usually, very less number of log blocks is maintained. Whenever erasing operation is performed on data, reclamation of log blocks is done only after the convergence of log blocks with the interrelated data block.
Block management in flash memory deals with the management of mapping between blocks, converging of corresponding blocks while cleaning of data and the methodology for reclamation or erasing of data. Flash translation layer should be defined such that it provides effective block management while focusing on improvement of the overall performance of the underlying flash memory. Large number of read/write operation requests must be handled such that the performance is not affected as well the response time should be very less.
Several models of FTL have already been proposed of which some have gained reputation because of the features they provide. Each of these FTL's employ different methods of handling blocks of data. Some such reputed models to consider are as follows:
3.1 Adaptive flash translation layer (AFTL):
Adaptive flash translation layer is one of the recent proposed FTL for flash memory. This is considered adaptive because it dynamically adapts or switches between different address mapping mechanisms. This type of FTL employs different mechanisms for block write request handling, merging of the data blocks and logical blocks as well the garbage collection approach.
Write request handling: The mapping information is maintained at block level. As is a hybrid mechanism, it also uses page level mechanism to a little extent. Mapping is done using fine-grained address translation and coarse grained address translation. Mapping via the fine-grained address translation takes comparatively less time than coarse grained translation.
In general, for every data block utmost one log block is maintained. All the rewritings that need to be done to a data block are redirected and written to log blocks. Usually, in fine grained mapping and coarse grained mapping, the log blocks and their corresponding data block are managed in linked lists arranged using hash tables and hash function. On a request for write operation on a data block, relevant log block is identified using the hash tables and linked lists. The data is then written to the log block.
Merging operation: Swap merging process is observed in AFTL. When the only log block of a data block is filled up, the pages present in the log block are considered as the active pages and hence information regarding these pages is updated in the page level mapping table. The data block is then considered as dead and hence erase operation can be performed on the data block. But, for performing this operation, mapping information of pages other blocks have to be eliminated as the space for mapping information is limited.
Absence of mapping information allows the garbage collector to clean the absent pages during the erasing process. In general, pages that have been used the least are identified and are replaced by the new active pages information. LRU (Least Recently Used) is the underlying mechanism used for identifying pages that can be displaced.
Garbage collection: Garbage collection is the process of cleaning or erasing data from the blocks. For cleaning data, the blocks need to be identified initially. Blocks are considered for erasing if:
If the number of invalid pages are many, as the pages data need not be copied any where
If the log block already has all the data, data block can be eliminated
Block with least number of valid pages in the log block and data block
Drawbacks: Blocks are repeatedly moved out of mapping table and can be deleted often which degrades the performance, when block information has to be moved to the mapping tables frequently. And also, LRU is not an effective scheme for finding the pages to be replaced.
3.2 Block Effective Sector translation (BAST):
This is the most conventional as well the most accepted form of FTL in existence. BAST mainly focuses on the concept that coarse grained mapping consumes more time than fine grained mapping. BAST based FTL possess the basic techniques employed for block management.
Write request handling: Similar to AFTL, the majority of the mapping information is maintained at block level. Only little page level information is maintained. Utmost one log block can be associated with a given data block and is allotted dynamically.
On a write request for a data block, the data to be written is directed to a free block and hence forms the log block. The writing operation is continued till all the pages in the log block are completely full with the data. For every write operation done, page level mapping table is updated with the latest information and does not require any overhead for doing so.
Merging operation: Complete merging is implemented over FTL. Only one log block is usually associated with a data block. Log block is filled without erasing data in the data block, till the log block is full. Merging of the data block and log block is done at this point and hence erasure of two blocks is made possible.
When the log block is full, a free block is considered and all the data present in both the log block and data block are copied into the free block. The free block is then made to be the new data block and cleaning procedures are applied on both the data block and the free block. To support complete merge at least one slot of free space need to be available. At times, if there are no free blocks, one of the already existing log block is erased to provide room for the new block. Hence, for a write operation on a filled log block, read page operation, write page operation and cleaning operation on two blocks need to be preformed.
Garbage collection: Most simple cleaning operation is adapted by the FTL of BAST. Round robin fashion is used for identifying the blocks followed by erasing of the data present. The order in which the blocks are mapped is considered as the base for executing the round robin algorithm.
The block that is to be used next is identified in the round robin fashion and that block is erased before the presently used block is filled. Garbage collection is done easily but has an overhead because of the need for erasing two blocks to support one write operation.
Drawbacks: For frequent updating of data, a need for many number of log blocks exist. If deficit of free blocks then deletion of existing blocks with less utilization is done, this causes a problem. Need for the deleted blocks might arise, which then should be written again causing extreme degradation of performance.
3.3 Superblock based flash translation layer (SUPERBLOCK):
Superblock is the most modern form of FTL in usage. So far, this type of FTL has proven to yield the best results in terms of performance. Its implementation possesses adaptive and advanced methodologies of handling the blocks in the flash memory. The basic building block of this FTL is that a series of adjacent logical blocks are grouped together to form a superblock. Coarse grained and fine grained mapping strategies are used in this FTL.
Write request handling: Superblock consists of several blocks, share common blocks for storing new data. The blocks that already contain data are called the D-blocks (data blocks) and the block where new data is directed is called the U-block (Update block).
Mapping is done at block level (Superblock) as well page level mapping is done for pages inside each of the Superblock. On receiving a write request for a superblock, a U-block is allocated and writing of data is done from the first page of the U-block. On further write requests, data is sequentially written to the U-block till it is completely filled. When the U-block pages are filled another U-block is allocated and the pages of data are written. This allocation is done only for a limited number of blocks based on the underlying architecture.
Merging operation: In Superblock FTL, separate space for storing page level mapping information is not maintained. Instead, for every update on a page, the page level mapping information is stored in the spare area of the same physical page along with the Error correction code and bad block indicator bits. In general, when the number of U-blocks used by a superblock exceeds the number allowed, then merging operation is performed.
When all the U-blocks are filled, then swap merging is observed with the corresponding D-block. The U-block would then be declared as the new data block. In case the data block has free pages to accommodate the data in U-block, then partial merging between the U-block and the D-block is done. Hence, based on the availability of space, merging is chosen adaptively.
Garbage collection: Clever mechanism is employed for cleaning of data blocks. Generally, when the U-block is filled swap merging is observed with the data block. Erasing the old data block is done to free the pages of the block. In general, the superblocks with at least one U-block are checked thus decreasing the time for searching blocks for cleaning.
In case of observed partial addressing, the data is copied completely either into the U-block or D-block. The block with invalid pages is then erased. Since, cleaning is applied occasionally; the overhead of erasing before writing is minimized.
Drawbacks: Usually, mapping information at page level is maintained in every page's spare area. Thus decrease in the page space in the page for accommodation of other important bits is observed. Error correction code is usually maintained in the spare area of the page. When the mapping information is added to the spare space available in a page, the space for error correction code is decremented thus diminishing the overall meaning of possessing error correction code.
3.4 Fully associative translation layer (FAST):
Fully associative translation layer is another enhanced FTL that has provided impressive performance in real world applications. It uses simple mapping techniques as in associative mapping and decreases the problems considerably, due to the erase before write feature of the flash memory.
Write request handling: The main advantage of FAST is that a log block consists of data from any logical block. Unlike many other techniques where in one log block is assigned to one data block, log blocks can have data from any logical block to be written.
But to maintain the performance, two sets of different log blocks are maintained. One type supports Sequential Write (SW) if the data is to the same data block. Other one supports Random Write (RW), where in data corresponding to several data blocks is written to one block. Block level mapping is usually used to maintain the mapping information. On receiving a write request, based on the data block, data is written to either the SW block or the RW block to minimize the merging of blocks overhead.
Merging operation: This is one of the efficient FTL's that handle the merging operation efficiently. The number of merging operations is optimized as the data associated with several data blocks can be written to a common log block. Merge operation need to be done for both the SW and RW log blocks.
SW log blocks usually contain data corresponding to a single data block. When the SW block is full, merging operation need to be performed to provide room for further write operation. Swap merging is done, the SW log block is declared to be the new data block and the data block can be erased.
RW log blocks contain data related to many data blocks. Merging a RW block require many merging operations. RW block to be merged is selected in round robin manner. Partial merging is observed; when the RW block is full, the blocks of data in the RW block are merged with the respective data blocks. The number of merging operations depends on the number of data blocks associated with the data in the RW block.
Garbage collection: Garbage collection strategy employed is simple and obvious. Whenever a SW block is full and is merged with the data block, the old data block is erased. And in case of RW block, merging is done with several data blocks. Once the data in the RW block is merged, the block would contain only invalid pages and hence can be erased.
Drawbacks: Similar to AFTL, RW blocks are chosen in round robin fashion which is not an effective methodology for choosing blocks to erase. Blocks are erased randomly hence causing thrashing of blocks problem.
4. PROPOSED HYBRID FTL MODEL:
An enhanced FTL is proposed which can effectively be of use with best performance. This proposed hybrid model utilizes the advantages that are present in the current existing models. Hybrid FTL's block management involves the same three main functionalities, namely handling write requests, efficient merging operation and cleaning operation over blocks of data present in the flash memory. Hybrid address mapping techniques are used for storing, mapping information. Let us consider each of these functionalities:
Handling write request:
Similar to models LAST, AFTL, data is written initially to free blocks and when the block is full data is redirected to other free blocks. Generally, data blocks information is maintained using the Block level mapping and the log blocks information is maintained using Page level mapping.
Block level mapping minimizes the space requirements and page level mapping helps in maintaining information about the pages in log blocks. Unlike LAST, where in for performing write operation on sequential data a separate log block is maintained, a novel mechanism is employed for writing sequential data. On receiving a write request:
Initially, the data block to which the data is intended is checked to see if any free pages are available. If free pages are present, then the data is written to the free pages directly.
If the data block is full, then the incoming data is redirected and is written to a free block and would be the log blocks corresponding to that data block. Log block is maintained for a data block to minimize the cost of reclaiming as number of merging is minimized.
For sequential data, different mechanism is used. Initially, the data that need to be overwritten is analyzed to see if the data is in sequential manner that can fit into a block. If a flash memory has blocks of size 30 pages each, and a write request for 63 pages arrive, the data is analyzed to know the number of blocks. The request needs 2 blocks and 3 pages to perform the write operation. For such request:
If the data is identified as sequential, data is written completely to blocks so that swap merging can be possible.
If not sequential, data is written as pages to any available log blocks of data blocks.
This type of writing improves space handling and decreases the cost of merging and cleaning.
Fig 5: On a request for writing [1, 2, 3, 5, 7], data is identified to be sequential [1, 2, 3] and hence written to single log block [LX], later is declared as the data block. For data [5, 7], pages are invalidated in data block [DB, DC] and are written to a new log block [DA].
Merging operation need to be effectively done to reduce the overhead of cleaning. When the log block available is full, merging should be done between the log block and data block to accommodate further write operations.
Normal Merging: Firstly, when one of the log blocks is full, a free block is identified and the active pages in the log block and the data block are written to it. In other words, complete merging is observed. Thus for minimal number of merging operations more blocks are vacated.
Utilize dead blocks: Secondly, when a log block is observed to be full, dead blocks are identified. Dead blocks are blocks with pages that already exist in another log block and the block is ready for erasure. If any of these dead blocks have free pages to accommodate the current write operation, the writing of data is done instead of merging the block. Hence, these processes help in utilization of dead blocks and decrement the cost of merging.
Cleaning process at timed invokes the merging operation as it identifies the blocks that need to be merged before erasure. Merging operation cost can be decreased if the copying of data is less. The above merging methodologies are applied after a block is selected to be erased.
Erasing functionality in flash memory forms the key for efficiency. Cost of erasing has to be minimized as much as possible to enable quicker access and utilization of space properly. Proposed cleaning policy is not dependent on a single factor instead is based on several factors.
Garbage collection operation in flash memory is applied to blocks. Hence, blocks need to be identified effectively for deletion. Blocks are identified on several factors like:
Cost for merging: Depends on the number of active pages present in the data block and log block that need to be copied or merged completely into a new free block.
Age of block: Time consumed from the previous erasure of the block.
Identifying blocks for erasure:
Blocks are identified using the above factors. A set of strategies are followed before the block can be chosen for cleaning. When the garbage collection operation is invoked:
Initial check for availability of dead blocks is done. As dead blocks contain invalid pages, they are chosen to be erased primarily.
If there are no dead blocks, the merging cost of the blocks available are evaluated. The block with the lowest merging cost is chosen, followed by merging of the data block and log block. After the merge operation, garbage collector works on both the log block and data block.
Density of pages in a block is also considered before merging. Density depends on the active pages present in both the log block and the data block that need to be copied into a new block. If the density is high, more cost for copying is incurred. Hence, blocks with minimum number of active pages is chosen.
Another criterion of importance is the age of the block. Blocks that have been recently updated are not chosen for cleaning. Application of temporal locality assumes that blocks that are just written may tend to be written sooner thus invalidating the pages in the block. Blocks with many invalidate pages can be erased easily as they minimize the cost for copying the pages of the blocks.
All these mechanisms are implemented over the FTL for garbage collection operation. Once a block is erased, its space is set free and hence new data can be written. When choosing a new block, the block that has encountered minimum erasures is chosen to make sure that all the blocks are optimally chosen. Employing these cleaning principles would result in optimizing cost effectively in comparison to current models.
5. CONCLUSION AND FUTURE WORK:
A new enhanced FTL has been proposed that has efficient mechanisms for writing data, erasing data in flash memory. Methodology that considers merging cost for selection of blocks for cleaning is assumed to minimize the overhead of erasing data before writing. Proposed merging technique supposedly helps in enhanced utilization of the available space as for one merge operation it provides two blocks for deletion.
The immediate future work would be to simulate this FTL in flash memory and observe the resultant performance. Merging completely might provide little overhead as several pages need to be copied. Efforts can be put in the direction to minimize that overhead. Further enhancements to this proposed model would be an interesting field of further research.