Effective Caching for Demand-based Flash Translation Layers in Large-Scale Flash Memory Storage Systems

摘要

This invention discloses methods for implementing a flash translation layer in a computer subsystem comprising a flash memory and a random access memory (RAM). According to one disclosed method, the flash memory comprises data blocks for storing real data and translation blocks for storing address-mapping information. The RAM includes a cache space allocation table and a translation page mapping table. The cache space allocation table may be partitioned into a first cache space and a second cache space. Upon receiving an address-translating request, the cache space allocation table is searched to identify if an address-mapping data structure that matches the request is present. If not, the translation blocks are searched for the matched address-mapping data structure, where the physical page addresses for accessing the translation blocks are provided by the translation page mapping table. The matched address-translating data structure is also used to update the cache space allocation table.

主权项

1. A method for implementing a flash translation layer in a computer subsystem that comprises a flash memory and a random access memory (RAM), the flash memory being arranged in blocks each of which comprises a number of pages and is addressable according to a physical block address, each of the pages in any one of the blocks being addressable by a physical page address, the method comprising:
allocating a first number of the blocks as data blocks for storing real data; allocating a second number of the blocks other than the data blocks as translation blocks, a page of any of the translation blocks being regarded as a translation page, wherein an entirety of the translation blocks is configured to store a block-level mapping table comprising first address-mapping data structures each of which includes a logical block address of one of the data blocks and a physical block address that corresponds to the logical block address of the one of the data blocks; allocating a first part of the RAM as a cache space allocation table configured to comprise second address-mapping data structures each of which either is marked as available, or includes a logical block address of a selected one of the data blocks and a physical block address that corresponds to the logical block address of the selected one of the data blocks; allocating a second part of the RAM as a translation page mapping table configured to comprise third address-mapping data structures each of which includes a logical block address of a selected one of the data blocks, and a physical page address of a translation page that stores the physical block address corresponding to the logical block address of the selected one of the data blocks; and when an address-translating request is received, translating a requested virtual data block address to a physical block address corresponding thereto by an address-translating process;wherein the address-translating process comprises:
searching the cache space allocation table for identifying, if any, a first-identified data structure selected from among the second address-mapping data structures where the logical block address in the first-identified data structure matches the requested virtual data block address; if the first-identified data structure is identified, assigning the physical block address in the first-identified data structure as the physical block address corresponding to the requested virtual data block address; if the first-identified data structure is not identified, searching the translation blocks for identifying a second-identified data structure selected from among the first address-mapping data structures where the logical block address in the second-identified data structure matches the requested virtual data block address, wherein the translation page mapping table provides the physical page addresses stored therein for accessing the translation blocks; when the second-identified data structure is identified, assigning the physical block address in the second-identified data structure as the physical block address corresponding to the requested virtual data block address; and when the second-identified data structure is identified, updating the cache space allocation table with the second-identified data structure by a cache-updating process, wherein the cache-updating process includes copying the second-identified data structure onto a targeted second address-mapping data structure selected from among the second address-mapping data structures.