CN110389904B

CN110389904B - Memory device with compressed FTL table

Info

Publication number: CN110389904B
Application number: CN201810360299.XA
Authority: CN
Inventors: 鲁海波
Original assignee: Beijing Memblaze Technology Co Ltd
Current assignee: Beijing Memblaze Technology Co Ltd
Priority date: 2018-04-20
Filing date: 2018-04-20
Publication date: 2024-10-01
Anticipated expiration: 2038-04-20
Also published as: CN110389904A

Abstract

The application relates to solid-state storage equipment, in particular to a compressed FTL table used in the solid-state storage equipment, and the application achieves the purpose of storing the FTL entries in a form that the boundaries of the FTL entries are not always aligned with the boundaries of the storage units by aligning the boundaries of the storage units according to the boundaries of the access units by moving the access units containing the FTL entries from an external memory to a cache and moving the storage units containing the FTL entries from the access units in the cache so as to utilize the FTL entries, thereby achieving the effect of saving the space of the storage equipment occupied by the FTL table.

Description

Memory device with compressed FTL table

Technical Field

The present application relates to solid state storage devices, and in particular to using compressed FTL tables in solid state storage devices.

Background

FIG. 1 illustrates a block diagram of a prior art solid state storage device. The solid state storage device 102 is coupled to a host for providing storage capability for the host. The host and solid state storage device 102 may be coupled by a variety of means including, but not limited to, connecting the host to the solid state storage device 102 via, for example, SATA (SERIAL ADVANCED Technology Attachment ), SCSI (Small Computer system interface), SAS (SERIAL ATTACHED SCSI ), IDE (INTEGRATED DRIVE Electronics, integrated drive Electronics), USB (Universal Serial Bus ), PCIE (PERIPHERAL COMPONENT INTERCONNECT EXPRESS, PCIE, peripheral component interconnect), NVMe (NVM Express, high speed nonvolatile storage), ethernet, fibre channel, wireless communication network, etc. The host may be an information processing device capable of communicating with the storage device in the manner described above, such as a personal computer, tablet, server, portable computer, network switch, router, cellular telephone, personal digital assistant, or the like. The memory device 102 includes an interface 103, a control unit 104, one or more NVM chips 105, and a DRAM (Dynamic Random Access Memory ) 110.

NAND flash memory, phase change memory, feRAM (Ferroelectric RAM, ferroelectric memory), MRAM (Magnetic Random Access Memory, magnetoresistive memory), RRAM (RESISTIVE RANDOM ACCESS MEMORY, resistive memory), etc. are common NVM.

The interface 103 may be adapted to exchange data with a host by means of, for example SATA, IDE, USB, PCIE, NVMe, SAS, ethernet, fibre channel, etc.

The control unit 104 is used to control data transfer among the interface 103, NVM chip 105, and DRAM 110, and also for memory management, host logical address to flash physical address mapping, erase balancing, bad block management, etc. The control component 104 can be implemented in a variety of ways, such as software, hardware, firmware, or a combination thereof, for example, the control component 104 can be in the form of an FPGA (Field-programmable gate array), an ASIC (Application SPECIFIC INTEGRATED Circuit), or a combination thereof. The control component 104 may also include a processor or controller in which software is executed to manipulate the hardware of the control component 104 to process IO (Input/Output) commands. Control unit 104 may also be coupled to DRAM 110 and may access data of DRAM 110. FTL tables and/or cached data of IO commands may be stored in the DRAM.

The control section 104 includes a flash interface controller (or referred to as a media interface controller, a flash channel controller) that is coupled to the NVM chip 105 and issues commands to the NVM chip 105 in a manner conforming to an interface protocol of the NVM chip 105 to operate the NVM chip 105 and receive a command execution result output from the NVM chip 105. Known NVM chip interface protocols include "Toggle", "ONFI", and the like.

In a solid state storage device, FTL (Flash Translation Layer ) is utilized to maintain mapping information from logical addresses to physical addresses. The logical addresses constitute the storage space of the solid state storage device as perceived by upper level software such as the operating system. The physical address is an address for accessing a physical storage unit of the solid state storage device. Address mapping may also be implemented in the related art using an intermediate address modality. For example, logical addresses are mapped to intermediate addresses, which in turn are further mapped to physical addresses.

The table structure storing mapping information from logical addresses to physical addresses is called FTL table. FTL tables are important metadata in solid state storage devices. Typically, the data items of the FTL table record address mapping relationships in units of data pages in the solid-state storage device.

FTL tables include a plurality of FTL entries (or entries). In one case, a correspondence of one logical page address to one physical page is recorded in each FTL entry. In another case, correspondence between consecutive logical page addresses and consecutive physical pages is recorded in each FTL entry. In yet another case, a correspondence of logical block addresses to physical block addresses is recorded in each FTL entry. In still another case, a mapping relationship between a logical block address and a physical block address, and/or a mapping relationship between a logical page address and a physical page address is recorded in the FTL entry.

An improved FTL algorithm and manner in which it is applied in solid state storage devices is disclosed at "DFTL:A Flash Translation Layer Employing Demand-based Selective Caching of Page-level Address Mappings", which is available in its entirety from http:// www.cse.psu.edu/-buu 1/papers/ps/dftl-aspris09. Pdf. Chinese patent application number 2017113473632 (entitled "method and apparatus for address translation for mass solid state storage devices") provides FTL tables suitable for mass solid state storage devices and methods of use thereof.

Disclosure of Invention

With the increase in solid state storage device capacity, such as solid state storage devices having a 4TB capacity, the FTL table includes 10≡9 entries, resulting in a significant amount of memory space being consumed to store the FTL in the solid state storage device. To ensure access to FTL tables, FTL tables are typically stored in DRAM memory, e.g., DDR interface. Providing DRAM memory in the solid state storage device sufficient to store FTL tables also increases the cost of the solid state storage device. There is a need to save memory space occupied by FTL tables.

According to a first aspect of the present application there is provided a first storage device according to the first aspect of the present application comprising: the front-end processing unit of the control part moves the access unit containing the FTL entry corresponding to the accessed logical address from the external memory to the FTL cache of the control part, and moves the storage unit containing the FTL entry corresponding to the accessed logical address in the access unit moved to the FTL cache to the front-end processing unit so as to use the FTL entry; wherein the memory cells are aligned by the boundaries of the memory cells, and the boundaries of FTL entries are not always aligned to the boundaries of the memory cells.

According to the first storage device of the first aspect of the present application, the access unit is a minimum unit for transmitting data between the external memory and the control unit.

According to the first or second storage device of the first aspect of the present application, the memory access unit is a memory row.

According to one of the first to third storage devices of the first aspect of the present application, the storage unit is a minimum unit for data transmission between the front-end processing unit and FTL cache.

According to one of the first to fourth storage devices of the first aspect of the present application, the front-end processing unit calculates a storage address of an access unit containing FTL entries corresponding to the accessed logical addresses relative to the FTL table start address, and moves the access unit from the external memory to the FTL cache according to the storage address.

According to the fifth storage device of the first aspect of the present application, the front-end processing unit calculates m×se/sl to obtain an integer part dl of a quotient, and obtains a storage address of an access unit containing FTL entries corresponding to the accessed logical address with respect to an FTL table start address through the integer part dl of the quotient, where m is the number of FTL entries stored before FTL entries corresponding to the accessed logical address in the FTL table, se is the size of FTL entries in bits, and sl is the size of the access unit in bits.

According to the sixth storage device of the first aspect of the present application, for a memory unit with a size of 64 bytes, the front-end processing unit discards or right-shifts the lower 9 bits of m×se to obtain a calculation result of m×se/sl.

According to the sixth or seventh storage device of the first aspect of the present application, the front-end processing unit calculates mase/sl to obtain an integer part rl of a remainder, and obtains, through the integer part rl of the remainder, a distance between a start address of an FTL entry corresponding to the accessed logical address in the FTL cache and the start address of the memory unit.

According to the eighth storage device of the first aspect of the present application, for a memory unit with a size of 64 bytes, the front-end processing unit uses the lower 9 bits of m×se as the integer part rl of the remainder of m×se/sl.

According to the eighth or ninth storage device of the first aspect of the present application, the front-end processing unit calculates (sl-rl), and if the result of (sl-rl) is smaller than se, the front-end processing unit moves the access unit containing the FTL entry starting address corresponding to the accessed logical address and the access unit subsequent to the access unit to the FTL cache.

According to a fifth storage device of the first aspect of the present application, the front-end processing unit calculates m_se/sm/sml to obtain an integer part dl of a quotient, and obtains the memory address of an access unit containing FTL entries corresponding to the accessed logical address relative to the FTL table start address through the integer part dl of the quotient, where m is the number of FTL entries stored before FTL entries corresponding to the accessed logical address in the FTL table, se is the size of FTL entries in bits, sm is the size of memory units in bits, and sml is the size of access units in memory units.

According to one of the fifth to eleventh storage devices of the first aspect of the present application, the front-end processing unit calculates a memory unit containing an FTL entry end address corresponding to the accessed logical address, and if the memory unit containing the end address is the same as the memory unit containing the memory address, the memory unit containing the memory address can completely contain the FTL entry.

According to the twelfth storage device of the first aspect of the present application, the front-end processing unit calculates mχse+se-1 to obtain an end address of FTL entries corresponding to the accessed logical address in the FTL table, where m is the number of FTL entries stored before FTL entries corresponding to the accessed logical address in the FTL table, and se is the size of FTL entries in bits.

According to the first storage device of the first aspect of the present application, the front-end processing unit calculates a storage address of a storage unit, which is moved to the FTL cache and accommodates FTL entries corresponding to the accessed logical addresses, in the access unit relative to an FTL table start address, and moves the storage unit from the access unit in the FTL cache to the front-end processing unit according to the storage address.

According to the fourteenth storage device of the first aspect of the present application, the front-end processing unit calculates m×se/sm to obtain an integer part dm of a quotient, and obtains the storage address through the integer part dm of the quotient, where m is the number of FTL entries stored before FTL entries corresponding to the accessed logical address in the FTL table, se is the size of FTL entries in bits, and sm is the size of a storage unit in bits.

A fifteenth memory device according to the first aspect of the present application, wherein, for a memory cell having a size of 32-bit doublewords, the front-end processing unit discards or right-shifts m×se lower 5 bits to obtain a calculation result of m×se/sm.

According to the fourteenth or fifteenth storage device of the first aspect of the present application, the front-end processing unit calculates an integer part rm of a remainder obtained by m se/sm, and obtains a distance between a start address of an FTL entry corresponding to the accessed logical address in a storage unit and a start address of the storage unit through the integer part rm of the remainder.

A seventeenth storage device according to the first aspect of the present application, wherein, for a storage unit having a size of 32-bit doublewords, the front-end processing unit takes the lower 5 bits of m_se as an integer part rm of m_se/sm remainder.

According to a seventeenth or eighteenth storage device of the first aspect of the present application, wherein the front-end processing unit calculates (sm-rm), and if the result of (sm-rm) is smaller than se, the front-end processing unit moves a storage unit accommodating the FTL entry start address corresponding to the accessed logical address and a storage unit subsequent to the storage unit to the front-end processing unit.

According to one of the fourteenth to nineteenth storage devices of the first aspect of the present application, the front-end processing unit calculates a storage unit that accommodates an end address of the FTL entry corresponding to the accessed logical address, and if the storage unit that accommodates the end address is identical to the storage unit that accommodates the storage address, the storage unit that accommodates the storage address can accommodate the FTL entry completely.

According to the twentieth storage device of the first aspect of the present application, the front-end processing unit calculates mχse+se-1 to obtain an end address of the FTL entry corresponding to the accessed logical address in the FTL table.

According to the twenty-first storage device of the first aspect of the present application, the front-end processing unit obtains the storage unit and the access unit accommodating FTL entries m to FTL entries m+n according to the start address and the end address of FTL entries corresponding to the accessed n consecutive logical addresses.

According to a twenty-second storage device of the first aspect of the present application, wherein a start address of the FTL entry in terms of bits in the FTL table is m×se, and an end address of the FTL entry m+n in terms of bits in the FTL table is (m+n) ×se+se-1.

According to one of the first to twenty-third storage devices of the first aspect of the present application, in response to the access unit loading into the FTL cache, the front-end processing unit records a logical address of the FTL entry accommodated by the access unit loaded into the FTL cache.

According to a twenty-fourth storage device of the first aspect of the present application, the front-end processing unit compares a logical address to be accessed with a logical address of an FTL entry accommodated by a recorded access unit moved to the FTL cache, and if the logical address to be accessed is within a range of the logical address of the FTL entry accommodated by the recorded cached access unit, acquires the FTL entry corresponding to the logical address to be accessed from the FTL cache.

According to the twenty-fourth storage device of the first aspect of the present application, the front-end processing unit calculates a first logical address corresponding to the first FTL entry at a start address of the access unit loaded into the FTL cache, and determines whether the access unit completely accommodates the first FTL entry; the front-end processing unit calculates a second logical address corresponding to a second FTL entry at the end address of the access unit and judges whether the access unit completely accommodates the second FTL entry; the front-end processing unit records FTL entries that the access unit completely accommodates.

According to the twenty-sixth storage device of the first aspect of the present application, the front-end processing unit calculates l1 sl/se, where the integer part de of the quotient indicates a first logical address corresponding to the first FTL entry at the start address of the access unit, l1 is the number of access units stored before the access unit l1 in the plurality of access units storing the FTL table, sl is the size of the access unit in bits, and se is the size of the FTL entry in bits.

According to a twenty-seventh storage device of the first aspect of the present application, the front-end processing unit calculates l1 sl/se to obtain an integer portion re of the remainder of the quotient, and if re is 0, the access unit completely accommodates the first FTL entry.

According to the twenty-sixth storage device of the first aspect of the present application, the front-end processing unit calculates (l1×sl+sl-1)/se, and the integer part of the obtained quotient indicates a second logical address corresponding to a second FTL entry located at an end address of the access unit, where l1 is a number of access units stored before the access unit l1 in a plurality of access units storing the FTL table, sl is a size of the access unit in bits, and se is a size of the FTL entry in bits.

According to the twenty-ninth storage device of the first aspect of the present application, the front-end processing unit calculates an integer part ree of a remainder obtained by (l1+sl-1)/se, and if ree is se-1, the memory access unit l1 completely accommodates the second FTL entry.

The twenty-seventh or twenty-eighth storage device according to the first aspect of the present application, wherein the front-end processing unit transforms the I1 sl/se computation into a (I1 sl 2^j/se)/(2^j) computation, where j is a larger integer for ease of computation.

According to the twenty-seventh or twenty-eighth storage device of the first aspect of the present application, the front-end processing unit converts division calculation in l1 s/se into multiplication and subtraction by calculating re=l1 s-de.

According to a twenty-fifth storage device of the first aspect of the present application, wherein the front-end processing unit calculates a difference d in bits from a start address of an FTL entry corresponding to the accessed logical address to a start address of the access unit, and the integer part of the d/se quotient indicates the number of FTL entries in the access unit that are completely accommodated before the FTL entry; the front-end processing unit calculates the difference a between the end address of the FTL entry corresponding to the accessed logical address and the end address of the access unit in terms of bits, and the integer part of the a/se quotient indicates the number of the FTL entries which are completely accommodated in the access unit after the FTL entries; recording logical addresses from FTL entries completely accommodated before the FTL entries to FTL entries completely accommodated after the FTL entries in a memory access unit; where se is the size of the FTL entry in bits.

The first storage device according to the first aspect of the present application further includes: and a host interface coupled to the front-end processing unit, the host interface for exchanging commands and data with a host.

The first storage device according to the first aspect of the present application further includes: and a media interface for accessing the NVM chip.

The first storage device according to the first aspect of the present application, wherein the FTL entry size is different from an integer multiple of the storage unit size.

The first storage device according to the first aspect of the present application, wherein the FTL is cached as a memory inside the control part.

According to a second aspect of the present application there is provided a method of accessing FTL table entries according to the second aspect of the present application, comprising the steps of: acquiring a logic address accessed by an IO command; calculating an access unit containing an FTL (flash translation) item corresponding to the accessed logical address in an external memory according to the logical address accessed by the IO command, and loading the access unit into a cache; calculating the address of a storage unit which accommodates the FTL entry corresponding to the accessed logical address in the access storage unit according to the logical address accessed by the IO command; and acquiring the storage unit from a cache according to the address of the storage unit in the access unit so as to use the FTL entry.

According to the first method for accessing FTL table entries in the second aspect of the present application, a memory address of an access unit for accommodating FTL entries corresponding to accessed logical addresses is calculated with respect to an FTL table start address, and the access unit is moved from an external memory to a cache according to the memory address.

According to a second method for accessing FTL table entries in a second aspect of the present application, m is calculated to obtain an integer part dl of a quotient, and the memory address of an access unit for accommodating FTL entries corresponding to the accessed logical address relative to the FTL table start address is obtained through the integer part dl of the quotient, where m is the number of FTL entries stored before FTL entries corresponding to the accessed logical address in the FTL table, se is the size of FTL entries in bits, and sl is the size of an access unit in bits.

According to the third method for accessing FTL table entry of the second aspect of the present application, for the access unit with the size of 64 bytes, the lower 9 bits of the m×se are discarded or shifted to the right to obtain the calculation result of the m×se/sl.

According to the second or third method for accessing FTL table entries in the second aspect of the present application, m_se/sl is calculated to obtain an integer part rl of a remainder, and a distance between a start address of FTL entry corresponding to an accessed logical address in the FTL cache and a start address of the memory unit is obtained through the integer part rl of the remainder.

A fifth method for accessing FTL table entries according to the second aspect of the present application, wherein for a memory location of size 64 bytes, the lower 9 bits of m se are taken as the integer part rl of the remainder of m se/sl.

According to the fifth or sixth method for accessing FTL table entry according to the second aspect of the present application, wherein (sl-rl) is calculated, and if the result of (sl-rl) is smaller than se, the memory cell containing the starting address of FTL entry corresponding to the accessed logical address and the memory cell following the memory cell are moved to the cache.

According to the first method for accessing FTL table entries of the second aspect of the present application, m is calculated, se/sm/sml is calculated to obtain an integer part dl of a quotient, the integer part dl of the quotient is used to obtain the memory address of the access unit for accommodating FTL entries corresponding to the accessed logical address relative to the FTL table start address, m is the number of FTL entries stored before FTL entries corresponding to the accessed logical address in the FTL table, se is the size of FTL entries in bits, sm is the size of memory units in bits, and sml is the size of access units in memory units.

According to one of the first to eighth methods of accessing FTL table entries according to the second aspect of the present application, the memory unit containing the ending address of the FTL entry corresponding to the accessed logical address is calculated, and if the memory unit containing the ending address is the same as the memory unit containing the memory address, the memory unit containing the memory address can completely contain the FTL entry.

A ninth method of accessing FTL table entries according to the second aspect of the present application, wherein calculating mse+se-1 results in accommodating the end address of FTL entry corresponding to the logical address being accessed.

According to the first method for accessing FTL table entries in the second aspect of the present application, a first memory address of a memory location of the FTL table entry corresponding to the accessed logical address in the access unit moved to the cache is calculated relative to the FTL table start address, and the memory location is obtained from the cache according to the first memory address so as to use FTL entries.

According to an eleventh method for accessing FTL table entries in the second aspect of the present application, m is calculated to obtain an integer part dm of a quotient, and the storage address is obtained through the integer part dm of the quotient, where m is the number of FTL entries stored before FTL entries corresponding to the accessed logical address in the FTL table, se is the size of FTL entries in bits, and sm is the size of a storage unit in bits.

A twelfth method for accessing FTL table entries according to the second aspect of the present application, wherein for a memory cell of size 32-bit doubleword, discarding or right-shifting the lower 5 bits of mse results in computation results of mse/sm.

According to a method for accessing FTL table entries according to the eleventh or twelfth aspect of the present application, an integer part rm of a remainder obtained by m se/sm is calculated, and a distance between a start address of FTL entry corresponding to an accessed logical address in a memory cell and a start address of the memory cell is obtained through the integer part rm of the remainder.

A fourteenth method of accessing FTL table entries according to the second aspect of the present application, wherein for a memory location of size 32-bit doubleword, the lower 5 bits of m se are taken as the integer portion rm of the m se/sm remainder.

According to a fourteenth or fifteenth method of accessing FTL table entries of the second aspect of the present application, wherein (sm-rm) is calculated, and if the result of (sm-rm) is less than se, a memory location containing a start address of FTL entry corresponding to the accessed logical address and a memory location subsequent to the memory location are retrieved from the cache to use FTL entry.

According to one of the methods of accessing FTL table entries according to the eleventh to sixteenth aspects of the present application, wherein the storage unit accommodating the end address of the FTL entry corresponding to the accessed logical address is calculated, and if the storage unit accommodating the end address is identical to the storage unit accommodating the storage address, the storage unit accommodating the storage address can accommodate the FTL entry completely.

A seventeenth method of accessing FTL table entries according to the second aspect of the present application, wherein calculating mse+se-1 results in accommodating FTL entry end addresses corresponding to the accessed logical addresses.

According to an eighteenth method of accessing FTL table entries of the second aspect of the present application, the memory locations and the memory locations accommodating FTL entries m to FTL entries m+n are obtained from the start address and the end address of FTL entries corresponding to the n consecutive logical addresses to be accessed.

According to a nineteenth method of accessing FTL table entries according to the second aspect of the present application, wherein the FTL entries have a start address m×se in bits in the FTL table, and FTL entries m+n have an end address (m+n) ×se+se-1 in bits in the FTL table.

According to the first method for accessing the FTL table entry of the second aspect of the present application, after the access unit is loaded into the cache, the logical address of the FTL entry accommodated by the cached access unit is recorded; the method further comprises the steps of: and comparing the logic address to be accessed by the IO command with the logic address of the FTL entry accommodated by the recorded cached access unit, and if the logic address to be accessed by the IO command is in the range of the logic address of the FTL entry accommodated by the recorded cached access unit, acquiring the FTL entry corresponding to the logic address to be accessed by the IO command from the cache.

According to a twenty-first method of accessing FTL table entries of the second aspect of the present application, wherein in response to loading the access unit into the cache, a first logical address corresponding to the first FTL entry at a start address of the access unit is calculated; judging whether the access unit completely accommodates the first FTL entry; calculating a second logical address corresponding to a second FTL entry at an end address of the access unit; judging whether the access unit completely accommodates the second FTL entry; the FTL entry that the access unit completely accommodates is recorded.

According to a twenty-second method for accessing FTL table entries in the second aspect of the present application, l1 is calculated, i 1 is si/se, the integer part de of the quotient indicates a first logical address corresponding to the first FTL entry at the start address of the access unit, l1 is the number of access units stored before the access unit l1 in the plurality of access units storing FTL table, si is the size of the access unit in bits, and se is the size of FTL entry in bits.

According to a twenty-second or twenty-third method for accessing FTL table entries in the second aspect of the present application, l1 is calculated to obtain an integer part re of a remainder of a quotient, if re is 0, the access unit l1 completely accommodates the first FTL entry, where l1 is the number of access units stored before the access unit l1 in a plurality of access units storing FTL table, sl is the size of the access unit in bits, and se is the size of the FTL entry in bits.

According to a twenty-second method of accessing FTL table entries in a second aspect of the present application, wherein (l1×sl+sl-1)/se is calculated, the integer part of the obtained quotient indicates a second logical address corresponding to a second FTL entry located at an end address of the access unit l1, where l1 is a number of access units stored before the access unit l1 among a plurality of access units storing FTL table, sl is a size of the access unit in bits, and se is a size of FTL entry in bits.

According to a twenty-fifth method for accessing FTL table entries in the second aspect of the present application, wherein an integer part ree of a remainder obtained by (l 1 ×sl+sl-1)/se is calculated, and if ree is se-1, the memory unit l1 completely accommodates a second FTL entry, where l1 is the number of memory units stored before the memory unit l1 in a plurality of memory units storing FTL table, sl is the size of the memory unit in bits, and se is the size of FTL entry in bits.

A thirteenth or twenty-fourth method of accessing FTL table entries according to the second aspect of the present application, wherein l1 sl/se is transformed into (l 1 sl 2^j/se)/(2^j), wherein j is a larger integer for ease of calculation.

According to a twenty-fifth or twenty-sixth method of accessing FTL table entries according to the second aspect of the present application, the division calculation in l1 is converted into a multiplication and subtraction operation by re=l1.

According to a twenty-first method of accessing FTL table entries of the second aspect of the present application, wherein, in response to loading the access unit into the cache, calculating a difference d in bits from the starting address of the FTL entry corresponding to the accessed logical address to the starting address of the access unit, the integer part of the d/se quotient indicating the number of FTL entries in the access unit that were completely accommodated before said FTL entry; calculating the difference a between the end address of the FTL entry corresponding to the accessed logical address and the end address of the access unit in terms of bits, wherein the integer part of the a/se quotient indicates the number of the FTL entries which are completely accommodated in the access unit after the FTL entries; recording logical addresses from FTL entries completely accommodated before the FTL entries to FTL entries completely accommodated after the FTL entries in a memory access unit; where se is the size of the FTL entry in bits.

According to a third aspect of the present application there is provided a program according to the third aspect of the present application comprising program code which, when loaded into and executed on a host, causes a processor of the host to perform the method of accessing FTL table entries of any of the above.

According to the application, the access unit containing the FTL entry is moved from the external memory to the cache, and the memory unit containing the FTL entry is moved from the access unit in the cache to utilize the FTL entry, so that the purpose of storing the FTL entry in a compressed mode that the boundary of the FTL entry is not always aligned with the boundary of the memory unit according to the boundary alignment of the memory unit is realized, and the effect of saving the space of the memory device occupied by the FTL table is achieved.

Drawings

In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the drawings used in the embodiments or the description of the prior art will be briefly described below, and it is obvious that the drawings in the following description are only some embodiments described in the present invention, and other drawings may be obtained according to these drawings for a person having ordinary skill in the art.

FIG. 1 illustrates a block diagram of a prior art solid state storage device;

FIG. 2 illustrates a block diagram of a solid state storage device, according to an embodiment of the application;

FIG. 3 illustrates a schematic diagram of storing FTL entries in compressed form in an external memory according to an embodiment of the present application;

FIG. 4 illustrates a flow chart of accessing FTL entries stored in compressed form in external memory according to an embodiment of the present application;

Fig. 5 illustrates a schematic diagram of FTL entries in FTL cache locations according to an embodiment of the present application.

Detailed Description

The following description of the embodiments of the present invention will be made clearly and fully with reference to the accompanying drawings, in which it is evident that the embodiments described are some, but not all embodiments of the invention. All other embodiments, which can be made by those skilled in the art based on the embodiments of the invention without making any inventive effort, are intended to be within the scope of the invention.

FIG. 2 illustrates a block diagram of a solid state storage device according to an embodiment of the application. The control component 104 of the solid state storage device includes a host interface 210, a front-end processing unit 260, a back-end processing unit 270, and a media interface 220 for accessing the NVM chip 105.

The host interface 210 is used to exchange commands and data with a host. In one example, the host communicates with the storage device via an NVMe/PCIe protocol, the host interface 210 processes PCIe protocol packets, extracts NVMe protocol commands, and returns the processing results of the NVMe protocol commands to the host.

The front-end processing unit 260 is coupled to the host interface 210 for receiving IO commands sent by the host to the storage device. For a read IO command, front-end processing unit 260 queries the FTL table according to the logical address accessed by the IO command to obtain a physical address corresponding to the logical address, and instructs back-end processing unit 270 to read data from NVM chip 105 through media interface 220 according to the physical address. For write IO commands, front-end processing unit 260 assigns a physical address to the IO command, instructs back-end processing unit 270 to write the data to be written by the write IO command to the assigned physical address of NVM chip 105 through the media interface, and front-end processing unit 260 also updates the FTL table with the assigned physical address.

The control component 104 is also coupled to an external memory (e.g., DRAM with DDR interface) 110. A portion of the space of the external memory 110 is used to store FTLs. In fig. 2, a plurality of entries of the FTL table (FTL entry 0, FTL entry 1, FTL entry 2, FTL entry 3 … … FTL entry m, FTL entry m+1, FTL entry m+2, FTL entry m+3, etc.) are shown stored in the external memory 110. FTL entries have a specified size, e.g., 30 bits, for describing the physical addresses of 10-9 or 2-30 physical memory locations on the NVM chip.

The external memory 110 has a large access latency. To improve FTL table access performance, the control means further comprises FTL cache 262.FTL cache 262 is memory internal to the control unit with low access latency. The front-end processing unit 260 caches FTL entries retrieved from the external memory 110 in the FTL cache 262 and uses FTL entries in the FTL cache 262 in processing IO commands.

For FTL entries with a size of e.g. 30 bits, a storage unit of 4 bytes is used in the prior art to store FTL entries in an external memory. Typically 4 bytes form a Double Word (DWORD), accessing external memory in a 4 byte size is well supported by the prior art.

However, storing FTL entries (30 bits) with double word size (32 bit) memory cells wastes 2 bits in the memory cells. When FTL entries have, for example, 10-9 or 2-30 FTL entries, the total wasted memory is over 100MB.

With continued reference to FIG. 2, data transfer between the external memory 110 to the control unit occurs in memory rows. By way of example, the memory line size is 64 bytes, as determined by the data width of the bus and/or memory controller that the control unit accesses the external memory. The memory line is the minimum data size for transferring data between the external memory 110 and the control unit.

It will be appreciated that FTL entries may have other sizes, e.g., 29 bits, 31 bits, 32bits, 34 bits, or even larger or smaller.

Fig. 3 illustrates a schematic diagram of storing FTL entries in compressed form in an external memory according to an embodiment of the present application.

The memory cell is the smallest unit, e.g. a memory row, of data transferred between the external memory and the control unit. The access unit includes a plurality of memory units, having a size of, for example, a doubleword, which is the smallest unit for data transfer between the front-end processing unit 260 (see also fig. 2) of the control unit and the FTL cache. The memory cells are aligned along the boundaries of the memory cells such that the starting address of a memory cell is always the starting address of a memory cell and the ending address of a memory cell is always the ending address of a memory cell, there being no memory cell spanning two memory cells.

According to the embodiment of fig. 3, FTL entries are smaller in size than the memory cells, for example 30 bits. The FTL entries of the FTL table are closely arranged (also referred to as being stored in compressed form) in a memory unit, the end of one FTL entry (e.g. FTL entry 0) is immediately adjacent to the beginning of the next FTL entry (e.g. FTL entry 1), there is no unoccupied memory space between the two FTL entries. Since the size of FTL entries is smaller than the size of memory cells, the boundaries of FTL entries and memory cells are not always aligned and, correspondingly, the boundaries of FTL entries and access cells are not always aligned. For example, the starting address of FTL entry 0 is aligned with the starting address of the memory cell, while the starting address of FTL entry 1 is located at 30 bits from the starting address of the memory cell 0 (2 bits from the starting address of the memory cell 1), and the starting address of FTL entry 2 is located at 28 bits from the starting address of the memory cell 1.

For example, in fig. 3, point C is the boundary between the access unit L0 and the access unit L1, and is also the boundary between the memory units. Point a is the boundary of the memory location, but not the boundary of the memory location, nor the boundary of the FTL entry. Point B is the boundary of the FTL entry, not the boundary of the memory location, nor the boundary of the memory location.

The solid state storage device indicates the logical address to access from the IO command of the host interface. The logical address corresponds to the FTL entry, for example, a physical address for the NVM memory chip corresponding to the logical address is recorded in the FTL entry uniquely determined by the value of the logical address.

To access FTL entry corresponding to a certain logical address m (e.g., FTL entry m, m is 0 or a positive integer), the front-end processing unit 260 (see also fig. 2) moves the access unit L1 containing FTL entry m in the external memory 110 to the FTL cache 262. The front-end processing unit also identifies which of the memory locations L1 of the access locations L1 moved to FTL cache 262 holds FTL entries to be accessed.

According to an embodiment of the present application, a memory location (L1) is determined to accommodate a specified FTL entry m in external memory 110 to move memory location L1 from external memory 110 to FTL cache 262. And also determines the memory location k (and possibly memory location k + 1) in which to house the designated FTL entry m in memory location L1 to move FTL entry m from FTL cache 262 to front-end processing unit 260.

By way of example, the IO command indicates that logical address m is to be accessed, FTL entry m records a physical address corresponding to logical address m. M FTL entries (FTL entry 0 to FTL entry m-1) are stored before FTL entry m in the FTL table, so that the starting address of FTL entry m in bits in the FTL table is m×se with respect to the starting address of the stored FTL table, where se represents the size (number of bits) of FTL entry (e.g., 30). The size of the memory cell in bits is denoted sm (e.g., 32-bit doubleword). The size of the memory cell in bits is noted as sl (e.g., 64 bytes (512 bits)).

Calculating mse/sm, the resulting integer part of the quotient (denoted dm) indicates the memory address of memory location k (see fig. 3) relative to the FTL table start address. Alternatively, for a memory cell of size 32-bit doubleword, discarding the lower 5 bits of mse (e.g., reserving the upper bits except the lower 5 bits, or shifting the lower 5 bits to the right) results in an mse/sm calculation. Replacing the division operation with a bit operation will significantly increase the computation speed.

Calculating m se/sm, the integer portion of the resulting remainder (denoted rm) indicates the distance in memory location k (see fig. 3) of the starting address of FTL entry m relative to the starting address of memory location k. Alternatively, for a memory cell of size 32-bit doubleword, the lower 5 bits of m se are taken as rm.

Further, if (sm-rm) is less than se, it means that the memory cell k cannot fully accommodate FTL entry m, and thus a portion of FTL entry m is stored by memory cell k+1.

The integer part of the quotient calculated as mse/sl (denoted as dl) indicates the memory address of the memory cell l (see fig. 3) relative to the FTL table start address. Alternatively, for a memory cell of size 64 bytes, discarding the lower 9 bits of mse (e.g., reserving the upper bits except the lower 9 bits, or shifting 9 bits right) results in a computation of mse/sl.

Alternatively, the size of the memory cells in memory cells is noted sml (e.g., 16 memory cells are accommodated per memory cell). The integer part of the quotient calculated mse/sm/sml (denoted as dl) indicates the memory address of the memory location l1 (see fig. 3) relative to the FTL table start address.

Calculating mse/sl, the integer portion of the resulting remainder (denoted as rl) indicates the distance of the starting address of FTL entry m in access unit l1 (see fig. 3) relative to the starting address of access unit l 1. Alternatively, for a memory cell of size 64 bytes, the lower 9 bits of m se are taken as rl.

Further, if (sl-rl) is smaller than se, this means that the access unit l1 cannot fully accommodate FTL entry m, and thus part of FTL entry m is stored by the access unit l 2.

In an alternative embodiment, mse is the start address in bits of FTL entry m in FTL table, and the end address in bits of FTL entry m in FTL table is obtained by (mse+se-1). In a similar manner, a memory location and a memory access location are obtained that accommodate the end address (m+se-1) of FTL entry m in bits in the FTL table. By identifying whether the memory cell/access unit is identical to memory cell k/access unit l1, it is identified whether memory cell k can fully accommodate FTL entry m and whether access unit l1 can fully accommodate FTL entry m.

In still another embodiment, the IO command accesses a plurality of consecutive logical addresses, the beginning logical address being m and the ending logical address being m+n. m+se is the start address in bits of FTL entry m in FTL table, and the end address in bits of FTL entry m+n in FTL table is obtained by ((m+n) +se-1). Thereby yielding a memory location and memory access location that accommodates FTL entry m through FTL entry m + n.

Fig. 4 illustrates a flow chart of accessing FTL entries stored in compressed form in external memory according to an embodiment of the present application.

In step S410, the front-end processing unit (see also fig. 2, front-end processing unit 260) receives the IO command and obtains the logical address accessed by the IO command. The logical address of the IO command access may be one or more. For clarity purposes, the embodiment illustrated in FIG. 4 is described with the IO command accessing a logical address as an example.

In step S420, the memory unit l1 (and possibly the memory unit l 2) of the external memory 110 containing FTL entry corresponding to the accessed logical address m is calculated according to the logical address accessed by the IO command. In step S430, the access unit l1 (and possibly the access unit l 2) is read out from the external memory 110 to load the access unit l1 (and possibly the access unit l 2) into the FTL cache 262. In step S440, the front-end processing unit 260 further calculates the address of the memory cell (memory cell mm and possible memory cell mm+1) of FTL entry m corresponding to the accessed logical address, which is accommodated in the access cell l1 (and possible access cell l 2), according to the logical address accessed by the IO command.

In step S450, the front-end processing unit obtains the memory location mm (and possibly the memory location mm+1) from the FTL cache 262 to use the FTL entry m according to the address of the memory location mm (and possibly the memory location mm+1) in the memory location l1 (and possibly the memory location l 2).

Fig. 5 illustrates FTL cache filled with access units comprising FTL entries as a result of performing the method of fig. 4. For clarity purposes FTL entry m is accommodated by a single memory unit and access unit.

With FTL entry m transferred to FTL cache 262, a plurality of other FTL entries (FTL entry m-1, FTL entry m+1, and portions of FTL entry m-2 and FTL entry m+2) adjacent to FTL entry m and accommodated by the same access unit l1 are transferred to FTL cache 262.

In fig. 5, portions of FTL entry m-2 and FTL entry m+2 are located outside of access unit l1 and these portions are not loaded into FTL cache 262 by the method illustrated in fig. 4.

In addition to FTL entry m being loaded according to logical address m of the IO command, other FTL entries are stored in FTL cache 262. These other FTL entries may be fully utilized. If the next IO command received by the front-end processing unit 260 accesses FTL entries (FTL entry m-1 to FTL entry m+1) existing in the FTL cache 262, the FTL entry is accessed directly from the FTL cache 262 without reading the FTL entry again from the external memory 110, thereby accelerating the processing of the IO command by shortening the fetch time of the FTL entry.

In order to use these other FTL entries in FTL cache 262, the logical addresses to which these other FTL entries correspond need to be known. That is, with respect to the starting address of the FTL table, the starting address of the memory unit l1 in the FTL cache 262 is l1×sl, where l1 is the number (starting from 0) of the memory unit l1 in the plurality of memory units storing the FTL table.

Calculating l1 sl/se, the integer part of the resulting quotient (denoted as de) indicates the logical address (m-2) corresponding to FTL entry m-2 (see fig. 5) located at the starting address of the access unit l 1. Calculating l1 sl/se, the integer portion of the resulting remainder (denoted as re) indicates the distance (in bits) of the starting address of memory location l1 from the starting address of FTL entry m-2. If re is 0, it means that the access unit l1 completely accommodates FTL entry m-2, and if re is greater than 0, it means that the access unit l1 does not completely accommodate FTL entry m-2.

Similarly, (l1+sl-1)/se is calculated, the integer portion of the resulting quotient indicating the logical address (m+2) corresponding to FTL entry m+2 (see fig. 5) located at the end address of the access unit l 1. The integer portion of the remainder (noted ree) obtained by calculating (l1+sl-1)/se indicates the distance (in bits) of the end address of memory location l1 from the start address of FTL entry m+2. If ree is se-1, this means that the access unit l1 completely accommodates FTL entry m+2, and if ree is smaller than se-1, this means that the access unit l1 does not completely accommodate FTL entry m+2.

Division calculations are time consuming. In an alternative embodiment, the division calculation in l1 sl/se is converted into a multiplication and shift operation to speed up the process of obtaining the quotient (de) and remainder (re) of l1 sl/se. For example, l1×sl/se is converted to (l1×sl 2^j/se)/(2^j), where j is a larger integer that the front-end processing unit 260 can conveniently calculate, e.g., 20 to 30. So that l1 sl/se is converted to l1 sl multiplied by (2^j/se) divided by (2^j). Since j is a known specified value (e.g., a value in 20-30), and thus (2^j/se) is also a known value that can be calculated (denoted as a), the integer portion of (2^j/se) is taken as a and the fractional portion is discarded for ease of processing by the front-end processing unit 260. The front-end processing unit calculates l1 sl times a. The divide by (2^j) calculation is converted into a right shift j-bit operation. The front-end processing unit 260 thus multiplies the result by j bits to the right by calculating l1 sl times a to obtain the quotient of l1 sl/se (de). So that the original calculation of the division by se is replaced by one multiplication (multiplication a) and one shift (right shift by j bits).

Further, the remainder re=l1_sl_de_se, and the remainder (re) can be obtained by multiplication and subtraction from the already obtained quotient (de). Further, the positive integer se is decomposed into one or more sums of powers of 2 (e.g., 30=2ζ4+2ζ3+2ζ2+2ζ2A kind of electronic device. Note that se=2Δ1+2Δ2+ … +2Δai (where ai is a positive integer), then de=de (2Δ1+2Δ2+ … +2Δai) =de 2×a1+de 2×a2+ … +de 2×ai. And de x 2 ai is obtained by shifting de left ai times, thereby converting the multiplication operation into a shift left operation and an addition operation. As yet another example, 30= (2^4-1) x 2, whereby de x 30= (de x 2^4-de) x 2, the value of de x 30 is obtained by subtracting de from the result of de left-shifting by 4 bits and then left-shifting the obtained result by 1 bit.

Based on the teachings of the above disclosed solution, one of ordinary skill in the art will recognize a variety of ways to determine all FTL entries in the access unit l1 that are fully accommodated. For example, calculating the difference in bits (noted d) of the starting address of FTL entry m to the starting address of memory location l1, the integer part of the quotient obtained by d/se indicates how many FTL entries are also completely accommodated in memory location l1 before FTL entry m. The sequence numbers of these entries precede and are adjacent to the sequence number of FTL entry m. Similarly, it is determined how many FTL entries are also fully accommodated in the access unit l1 after FTL entry m.

Still alternatively, based on knowing the starting address of the first fully-accommodated FTL entry in the access unit l1, it is also convenient to determine all FTL entries fully accommodated in the access unit l1 according to the size (sl) of the access unit l1 and the size (se) of the FTL entries.

The first FTL entry fully accommodated in the memory cell l1 in FTL cache 262 is denoted as (start_e), and the last FTL entry fully accommodated in the memory cell l1 in FTL cache 262 is denoted as (end_e). All FTL entries between FTL entry (start_e) and FTL entry (end_e) are completely accommodated in FTL cache 262. The front-end processing unit 260 records a logical address range (from start_e to end_e) corresponding to the FTL entry (start_e) and FTL entry (end_e). In turn, front-end processing unit 260, in response to receiving the logical address to be accessed by the IO command, determines whether the required FTL entry is already present in FTL cache 262 by comparing whether the logical address to be accessed by the IO command belongs to a logical address range (from start_e to end_e). For FTL entries already present in FTL cache 262, front-end processing unit 260 retrieves FTL entries from FTL cache 262 without accessing external memory 110.

In one embodiment, for a write IO command, the physical address recorded in the FTL entry corresponding to the logical address of the write command is updated to the new physical address assigned to the write IO command. The front-end processing unit 260 updates FTL entries in the FTL cache 262 and writes memory locations in the FTL cache 262 containing updated FTL entries back to the external memory 110.

The present application also provides a program comprising program code which, when loaded into and executed on a host computer, causes a processor of the host computer to perform one of the methods provided above according to the embodiments of the present application.

It will be understood that each block of the block diagrams and flowchart illustrations, and combinations of blocks in the block diagrams and flowchart illustrations, respectively, can be implemented by various means including computer program instructions. These computer program instructions may be loaded onto a general purpose computer, special purpose computer, or other programmable data control apparatus to produce a machine, such that the instructions which execute on the computer or other programmable data control apparatus create means for implementing the functions specified in the flowchart block or blocks.

These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data control apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including computer-readable instructions for implementing the function specified in the flowchart block or blocks. The computer program instructions may also be loaded onto a computer or other programmable data control apparatus to cause a series of operational operations to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide operations for implementing the functions specified in the flowchart block or blocks.

Accordingly, blocks of the block diagrams and flowchart illustrations support combinations of means for performing the specified functions, combinations of operations for performing the specified functions and program instruction means for performing the specified functions. It will also be understood that each block of the block diagrams and flowchart illustrations, and combinations of blocks in the block diagrams and flowchart illustrations, can be implemented by special purpose hardware-based computer systems that perform the specified functions or operations, or combinations of special purpose hardware and computer instructions.

Although the present application has been described with reference to examples, which are intended for purposes of illustration only and not to be limiting of the application, variations, additions and/or deletions to the embodiments may be made without departing from the scope of the application.

Many modifications and other embodiments of the applications set forth herein will come to mind to one skilled in the art to which these embodiments pertain having the benefit of the teachings presented in the foregoing descriptions and the associated drawings. Therefore, it is to be understood that the applications are not to be limited to the specific embodiments disclosed and that modifications and other embodiments are intended to be included within the scope of the appended claims. Although specific terms are employed herein, they are used in a generic and descriptive sense only and not for purposes of limitation.

Claims

1. A storage device, comprising: the front-end processing unit of the control part moves the access unit containing the FTL entry corresponding to the accessed logical address from the external memory to the FTL cache of the control part, calculates and obtains the memory address of the memory unit containing the FTL entry corresponding to the accessed logical address in the access unit moved to the FTL cache relative to the starting address of the FTL table, and moves the memory unit containing the FTL entry corresponding to the accessed logical address in the access unit moved to the FTL cache from the access unit in the FTL cache to the front-end processing unit according to the memory address so as to use the FTL entry; wherein the memory cells are aligned by the boundaries of the memory cells, and the boundaries of FTL entries are not always aligned to the boundaries of the memory cells.

2. The memory device of claim 1, wherein the access unit is a minimum unit for transferring data between an external memory and a control unit.

3. The memory device of claim 1 or 2, wherein the memory access unit is a memory row.

4. The storage device of claim 1 or 2, wherein the storage unit is a minimal unit of data transfer between the front-end processing unit and FTL cache.

5. The storage device according to claim 1 or 2, wherein the front-end processing unit calculates a memory address of an access unit accommodating FTL entries corresponding to the accessed logical addresses relative to the FTL table start address, and moves the access unit from the external memory to the FTL cache according to the memory address.

6. The storage device of claim 5, wherein the front-end processing unit calculates mse/sl to obtain an integer portion dl of a quotient from which a memory address of an access unit accommodating FTL entries corresponding to the accessed logical address relative to a FTL table start address is obtained, where m is a number of FTL entries stored before FTL entries corresponding to the accessed logical address in the FTL table, se is a size of FTL entries in bits, and sl is a size of an access unit in bits.

7. The storage device of claim 6, wherein for a memory access unit of 64 bytes, the front-end processing unit discards or right-shifts m x se low 9 bits to obtain a computation result of m x se/sl.

8. The storage device of claim 6, wherein the front-end processing unit calculates mase/sl to obtain an integer portion rl of a remainder, and obtains a distance of a starting address of the FTL entry corresponding to the accessed logical address in the FTL cache relative to the starting address of the memory unit in the FTL cache through the integer portion rl of the remainder.

9. The memory device of claim 8, wherein for a memory cell size of 64 bytes, the front-end processing unit takes the lower 9 bits of m se as the integer portion rl of the m se/sl remainder.

10. The storage device of claim 8, wherein the front-end processing unit calculates (sl-rl) and, if the result of (sl-rl) is less than se, the front-end processing unit moves to FTL cache a memory cell containing FTL entry start address corresponding to the accessed logical address and a memory cell subsequent to the memory cell.

11. The memory device of claim 5, wherein the front-end processing unit calculates mse/sm/sml to obtain an integer portion dl of a quotient from which the memory address of the access unit holding the FTL entry corresponding to the accessed logical address relative to the FTL table start address is obtained, where m is the number of FTL entries stored before the FTL entry corresponding to the accessed logical address in the FTL table, se is the size of FTL entry in bits, sm is the size of the memory unit in bits, and sml is the size of the access unit in memory unit.

12. The memory device of claim 5, wherein the front-end processing unit calculates a memory cell that holds an FTL entry end address corresponding to the logical address being accessed, and if the memory cell that holds the end address is the same as the memory cell that holds the memory address, the memory cell that holds the memory address can fully hold the FTL entry.

13. The storage device of claim 12, wherein the front-end processing unit calculates mχse+se-1 to obtain an end address of FTL entries in the FTL table corresponding to the accessed logical address, where m is a number of FTL entries stored before FTL entries in the FTL table corresponding to the accessed logical address, and se is a size of FTL entries in bits.

14. The storage device according to claim 1 or 2, wherein the front-end processing unit calculates m_se/sm to obtain an integer part dm of a quotient, and obtains the storage address through the integer part dm of the quotient, where m is a number of FTL entries stored before FTL entries corresponding to the accessed logical address in the FTL table, se is a size of FTL entries in bits, and sm is a size of a storage unit in bits.

15. The memory device of claim 14, wherein for a memory cell of size 32-bit doubleword, the front-end processing unit discards or right-shifts m x se lower 5 bits to obtain a computation result of m x se/sm.

16. The storage device of claim 14, wherein the front-end processing unit calculates an integer portion rm of a remainder of m se/sm, and obtains a distance in a storage unit of a start address of the FTL entry corresponding to the accessed logical address from the start address of the storage unit through the integer portion rm of the remainder.

17. The memory device of claim 16, wherein for a memory cell of size 32-bit doubleword, the front-end processing unit takes the lower 5 bits of m se as the integer portion rm of the m se/sm remainder.

18. The memory device of claim 16, wherein the front-end processing unit calculates (sm-rm) and, if the result of (sm-rm) is less than se, moves to the front-end processing unit a memory unit containing the FTL entry start address corresponding to the accessed logical address and a memory unit subsequent to the memory unit.

19. The storage device of claim 1 or 2, wherein the front-end processing unit calculates a storage unit that accommodates an end address of the FTL entry corresponding to the accessed logical address, and if the storage unit that accommodates the end address is the same as the storage unit that accommodates the storage address, the storage unit that accommodates the storage address can accommodate the FTL entry completely.

20. The memory device of claim 19, wherein the front-end processing unit computes mχse+se-1 to obtain an end address of FTL entry in FTL table corresponding to the accessed logical address.

21. The memory device of claim 20, wherein the front-end processing unit obtains a memory location and a memory access location that accommodate FTL entry m through FTL entry m+n from a start address and an end address of FTL entry corresponding to n consecutive logical addresses being accessed.

22. The memory device of claim 21, wherein a start address in bits of FTL entry in FTL table is m x se and an end address in bits of FTL entry m+n in FTL table is (m+n) x se+se-1.

23. The storage device of claim 1 or 2, wherein the front-end processing unit records a logical address of FTL entry accommodated by a memory unit loaded into the FTL cache in response to the memory unit being loaded into the FTL cache.

24. The memory device of claim 23, wherein the front-end processing unit compares the logical address to be accessed with the logical address of the FTL entry held by the recorded access unit moved to the FTL cache, and obtains the FTL entry corresponding to the logical address to be accessed from the FTL cache if the logical address to be accessed is within the range of the logical address of the FTL entry held by the recorded cached access unit.

25. The storage device of claim 23, wherein the front-end processing unit calculates a first logical address corresponding to a first FTL entry at a start address of a memory unit loaded into the FTL cache, and determines whether the memory unit completely accommodates the first FTL entry; the front-end processing unit calculates a second logical address corresponding to a second FTL entry at the end address of the access unit and judges whether the access unit completely accommodates the second FTL entry; the front-end processing unit records FTL entries that the access unit completely accommodates.

26. The storage device of claim 25, wherein the front-end processing unit calculates l1 x sl/se, the integer portion de of the quotient indicating a first logical address corresponding to the first FTL entry at a start address of the access unit, wherein l1 is a number of access units stored before the access unit l1 among the plurality of access units storing the FTL table, sl is a size of the access unit in bits, and se is a size of the FTL entry in bits.

27. The memory device of claim 26, wherein the front-end processing unit calculates l1 x sl/se to obtain an integer portion re of the remainder of the quotient, and if re is 0, the access unit fully accommodates the first FTL entry.

28. The storage device of claim 25, wherein the front-end processing unit calculates (i 1 x sl+sl-1)/se, the integer portion of the quotient indicating a second logical address corresponding to a second FTL entry located at an end address of the access unit, wherein i 1 is a number of access units stored before the access unit l1 among a plurality of access units storing the FTL table, sl is a size of the access unit in bits, and se is a size of the FTL entry in bits.

29. The memory device of claim 28, wherein the front-end processing unit calculates an integer portion ree of a remainder of (i 1 x sl+sl-1)/se, and if ree is se-1, the memory access unit i 1 fully accommodates the second FTL entry.

30. The memory device of claim 26, wherein the front-end processing unit transforms the l 1 x sl/se computation to a (l 1 x sl x 2 x j/se)/(2^j) computation, where j is a larger integer that facilitates computation.

31. The memory device of claim 26, wherein the front-end processing unit converts division calculations in l 1 x sl/se into multiplication and subtraction operations by calculating re = l 1 x sl-de.

32. The memory device of claim 24, wherein the front-end processing unit computes a difference in bits d, d/se quotient of a starting address of FTL entry corresponding to the accessed logical address to a starting address of the memory unit, the integer portion of d/se quotient indicating a number of FTL entries in the memory unit that were fully accommodated prior to the FTL entry; the front-end processing unit calculates the difference a between the end address of the FTL entry corresponding to the accessed logical address and the end address of the access unit in terms of bits, and the integer part of the a/se quotient indicates the number of the FTL entries which are completely accommodated in the access unit after the FTL entries; recording logical addresses from FTL entries completely accommodated before the FTL entries to FTL entries completely accommodated after the FTL entries in a memory access unit; where se is the size of the FTL entry in bits.

33. The storage device of claim 1 or 2, further comprising: and a host interface coupled to the front-end processing unit, the host interface for exchanging commands and data with a host.

34. The storage device of claim 1 or 2, further comprising: a media interface for accessing the NVM chip.

35. The storage device of claim 1 or2, wherein the FTL entry is of a size different from an integer multiple of a storage unit size.

36. The storage device of claim 1 or 2, wherein the FTL is cached as a memory internal to the control component.

37. A method of accessing FTL table entries, comprising the steps of:

Acquiring a logic address accessed by an IO command;

calculating an access unit containing an FTL (flash translation) item corresponding to the accessed logical address in an external memory according to the logical address accessed by the IO command, and loading the access unit into a cache;

Calculating a first storage address of a storage unit containing the FTL entry corresponding to the accessed logical address in the access storage unit moved to the cache relative to the FTL table starting address according to the logical address accessed by the IO command;

According to a first memory address of the memory unit in the access unit relative to the starting address of the FTL table, a memory unit which is moved to the access unit in the cache and accommodates FTL entries corresponding to the accessed logical addresses is used for acquiring the memory unit from the access unit in the cache so as to use FTL entries; wherein the memory cells are aligned by the boundaries of the memory cells, and the boundaries of FTL entries are not always aligned to the boundaries of the memory cells.

38. The method of accessing FTL table entries according to claim 37, wherein a memory address of an access unit accommodating FTL entries corresponding to accessed logical addresses is calculated with respect to FTL table start addresses, and the access unit is moved from external memory to cache according to the memory address.

39. The method of accessing FTL table entries according to claim 38, wherein mse/sl is calculated to obtain an integer part dl of a quotient, and the memory address of the access unit accommodating FTL entries corresponding to the accessed logical address relative to the FTL table start address is obtained by the integer part dl of the quotient, where m is the number of FTL entries stored before FTL entries corresponding to the accessed logical address in the FTL table, se is the size of FTL entries in bits, and sl is the size of the access unit in bits.

40. The method of accessing an FTL table entry of claim 39, wherein for a memory location of size 64 bytes, discarding or right shifting the lower 9 bits of m x se results in a calculation of m x se/sl.

41. The method of accessing FTL table entries according to claim 38 or 39, wherein calculating mse/sl results in an integer part rl of a remainder, and a distance of a starting address of FTL entry corresponding to the accessed logical address in the access unit in FTL cache with respect to the starting address of the access unit is obtained through the integer part rl of the remainder.

42. The method of accessing an FTL table entry of claim 41, wherein for a memory location of size 64 bytes, the lower 9 bits of m se are taken as the integer portion rl of the remainder of m se/sl.

43. The method of accessing FTL table entries according to claim 41, wherein (sl-rl) is calculated, and if the result of (sl-rl) is less than se, the memory cell containing the starting address of FTL entry corresponding to the accessed logical address and the memory cell subsequent to the memory cell are moved to the cache.

44. The method of accessing FTL table entries according to claim 37, wherein mse/sm/sml is calculated to obtain an integer part dl of a quotient, from which integer part dl the memory address of the access unit holding FTL entries corresponding to the accessed logical address is obtained with respect to the FTL table start address, where m is the number of FTL entries stored before FTL entries corresponding to the accessed logical address in the FTL table, se is the size of FTL entries in bits, sm is the size of memory units in bits, sml is the size of access units in memory units.

45. The method of accessing FTL table entries according to claim 44, wherein the memory location holding the ending address of FTL entry corresponding to the accessed logical address is calculated, and if the memory location holding the ending address is identical to the memory location holding the memory address, the memory location holding the memory address can completely hold the FTL entry.

46. The method of accessing FTL table entries according to claim 45, wherein calculating mse+se-1 results in accommodating the end address of FTL entry corresponding to the logical address being accessed.

47. The method of accessing FTL table entries according to claim 37, wherein m_se/sm is calculated to obtain an integer part dm of a quotient, and the storage address is obtained by the integer part dm of the quotient, wherein m is the number of FTL entries stored before FTL entries corresponding to the accessed logical address in FTL table, se is the size of FTL entries in bits, and sm is the size of storage unit in bits.

48. The method of accessing FTL table entry of claim 47, wherein for a memory location of size 32-bit doubleword, discarding or right-shifting the lower 5 bits of mse results in computation of mse/sm.

49. The method of accessing FTL table entries according to claim 47, wherein an integer portion rm of a remainder obtained by m se/sm is calculated, and a distance of a start address of FTL entry corresponding to the accessed logical address in a memory location with respect to the start address of the memory location is obtained through the integer portion rm of the remainder.

50. The method of accessing a FTL table entry of claim 49, wherein for a memory location of size 32-bit doubleword, the lower 5 bits of m se are taken as the integer portion rm of the m se/sm remainder.

51. The method of accessing FTL table entry according to claim 49, wherein (sm-rm) is calculated, and if the result of (sm-rm) is less than se, a memory location containing a start address of FTL entry corresponding to the accessed logical address and a memory location subsequent to the memory location are obtained from the cache to use FTL entry.

52. The method of accessing FTL table entry according to claim 47, wherein the storage unit accommodating FTL entry end address corresponding to the accessed logical address is calculated, and if the storage unit accommodating the end address is the same as the storage unit accommodating the storage address, the storage unit accommodating the storage address can accommodate the FTL entry completely.

53. The method of accessing FTL table entries according to claim 52, wherein calculating mse+se-1 results in accommodating FTL entry end addresses corresponding to accessed logical addresses.

54. The method of accessing FTL table entry of claim 53, wherein the memory location and the memory location accommodating FTL entry m to FTL entry m+n are obtained from the start address and the end address of FTL entry corresponding to n consecutive logical addresses to be accessed.

55. The method of accessing a FTL table entry of claim 54, wherein the FTL entry has a start address m x se in bits in the FTL table, and the FTL entry m+n has an end address (m+n) x se+se-1 in bits in the FTL table.

56. The method of accessing FTL table entries according to claim 37, wherein after the access unit is loaded into the cache, recording the logical address of FTL entry accommodated by the cached access unit; the method further comprises the steps of: and comparing the logic address to be accessed by the IO command with the logic address of the FTL entry accommodated by the recorded cached access unit, and if the logic address to be accessed by the IO command is in the range of the logic address of the FTL entry accommodated by the recorded cached access unit, acquiring the FTL entry corresponding to the logic address to be accessed by the IO command from the cache.

57. The method of accessing FTL table entry of claim 56, wherein in response to loading the access unit into the cache, calculating a first logical address corresponding to the first FTL entry at the start address of the access unit;

judging whether the access unit completely accommodates the first FTL entry;

calculating a second logical address corresponding to a second FTL entry at an end address of the access unit;

judging whether the access unit completely accommodates the second FTL entry;

the FTL entry that the access unit completely accommodates is recorded.

58. The method of accessing FTL table entries according to claim 57, wherein l1 is calculated, the integer part de of the quotient indicates a first logical address corresponding to the first FTL entry at a start address of the access unit, wherein l1 is a number of access units stored before the access unit l1 among the plurality of access units storing FTL table, sl is a size of the access unit in bits, and se is a size of the FTL entry in bits.

59. The method of accessing FTL table entries according to claim 57, wherein l1 is calculated to obtain an integer portion re of remainder of quotient, and if re is 0, the memory access unit l1 completely accommodates the first FTL entry, wherein l1 is a number of memory access units stored before the memory access unit l1 among the plurality of memory access units storing FTL table, sl is a size of the memory access unit in bits, and se is a size of FTL entry in bits.

60. The method of accessing a FTL table entry of claim 57, wherein (l 1 x sl+sl-1)/se is calculated, the integer part of the obtained quotient indicating a second logical address corresponding to a second FTL entry located at an end address of the access unit l1, wherein l1 is a number of access units stored before the access unit l1 among a plurality of access units storing the FTL table, sl is a size of the access unit in bits, and se is a size of the FTL entry in bits.

61. The method of accessing FTL table entries according to claim 60, wherein the integer part ree of the remainder obtained by (i 1x sl+sl-1)/se is calculated, and if ree is se-1, the memory unit l1 completely accommodates the second FTL entry, wherein l1 is the number of memory units stored before the memory unit l1 among the plurality of memory units storing FTL table, sl is the size of the memory unit in bits, and se is the size of FTL entry in bits.

62. The method of accessing FTL table entries of claim 58 or 59, wherein l 1 x sl/se is transformed into (l 1 x sl x 2 x j/se)/(2^j), wherein j is a larger integer for ease of calculation.

63. The method of accessing FTL table entry of claim 60, wherein division calculation in l1 is converted into multiplication and subtraction by re = l 1x sl-de x se.

64. The method of accessing FTL table entries according to claim 56 or 57, wherein in response to loading the access unit into the cache, calculating a difference in bits d of the starting address of FTL entry corresponding to the accessed logical address to the starting address of the access unit, d/se resulting integer part of the quotient indicating the number of FTL entries in the access unit that were completely accommodated before said FTL entry;

Calculating the difference a between the end address of the FTL entry corresponding to the accessed logical address and the end address of the access unit in terms of bits, wherein the integer part of the a/se quotient indicates the number of the FTL entries which are completely accommodated in the access unit after the FTL entries;

recording logical addresses from FTL entries completely accommodated before the FTL entries to FTL entries completely accommodated after the FTL entries in a memory access unit;

where se is the size of the FTL entry in bits.