Memory system managing address translation table and method of controlling thereof

A forward lookup address translation table and a reverse lookup address translation table stored in a nonvolatile second storing unit are transferred as a master table to a volatile first storing unit at a time of start-up. When an event occurs so that the master table needs to be updated, difference information before and after update of any one of the forward lookup address translation table and the reverse lookup address translation table is recorded in the first storing unit as a log, thereby reducing an amount of the log.

CROSS-REFERENCE TO RELATED APPLICATIONS

This application is based upon and claims the benefit of priority from the prior Japanese Patent Application No. 2008-335567, filed on Dec. 27, 2008; the entire contents of which are incorporated herein by reference.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a memory system that includes a nonvolatile semiconductor memory and a control method thereof.

2. Description of the Related Art

Some personal computers (PC) employ a hard disk device as a secondary storage device. In such PCs, a technology is known for backing up data that has been stored in the hard disk device to prevent the data from becoming invalid because of some failure. For example, when act of changing data in the hard disk device is detected, a snapshot as a backup copy of the data before the change is taken and a log of changes made to the data is generated. Then, processing for taking a new snapshot, invalidating a log taken in the past before the new snapshot was taken, and generating a new log is repeated at every specific time, which is disclosed, for example, in US Patent Application Publication No. 2006/0224636. In case data becomes invalid due to some reason, the data can be restored by referring to the snapshot and the log.

BRIEF SUMMARY OF THE INVENTION

A memory system according to an embodiment of the present invention comprises: a memory system comprising: a volatile first storing unit; a nonvolatile second storing unit; and a controller that performs data transfer between a host apparatus and the second storing unit via the first storing unit, wherein the second storing unit is capable of storing therein a first address translation table for managing forward lookup information that correlates a logical address specified from the host apparatus with a storing position in the second storing unit, and a second address translation table for managing reverse lookup information that correlates the storing position in the second storing unit with the logical address, and the controller includes a table transferring unit that transfers the first address translation table and the second address translation table stored in the second storing unit to the first storing unit as a master table, a log control unit that, when an event occurs so that the master table needs to be updated, stores therein difference information before and after update of any one of the first address translation table and the second address translation table as a log in the first storing unit, a log reflecting unit that, when a specific first condition is satisfied, stores the log stored in the first storing unit in the second storing unit and reflects the log stored in the first storing unit in the master table stored in the first storing unit, and a read/write control unit that controls the data transfer by using the master table and the log stored in the first storing unit.

DETAILED DESCRIPTION OF THE INVENTION

In recent years, a capacity of a NAND-type flash memory as a nonvolatile semiconductor storage device has been increased dramatically. As a result, a Solid State Drive (SSD) as a memory system mounted with a NAND-type flash memory attracts attention. The flash memory has advantages such as high speed and lightweight compared with a magnetic disk device. However, the technology disclosed in US Patent Application Publication No. 2006/0224636 cannot be applied to backup of data stored in such PC having the NAND-type flash memory as the secondary storage device as in the case of backup of data stored in the PC having the hard disk device as the secondary storage device. This is because a multi-value memory technology (multi-level cell (MLC)) that can store a plurality of pieces of data (multi-value data) equal to or larger than 2 bits in one memory cell is employed to increase the capacity of the NAND-type flash memory, which is disclosed, for example, in Japanese Patent Application Laid-open No. 2004-192789.

A memory cell configuring a multi-value memory has a field effect transistor structure having a stacked gate structure in which a gate insulating film, a floating gate electrode, an inter-gate insulating film, and a control gate electrode are stacked in order on a channel region and a plurality of threshold voltages can be set according to the number of electrons accumulated in the floating gate electrode. In order to make it possible to perform multi-value storage based on the plurality of threshold voltages, the distribution of a threshold voltage corresponding to one piece of data needs to be made extremely narrow.

The data recorded by the host apparatus such as the PC has both temporal locality and spatial locality. Therefore, when data is recorded, if the data is directly recorded in an address designated from the outside, rewriting, i.e., erasing processing temporally concentrates in a specific area and a bias in the number of times of erasing increases. Therefore, in the NAND-type flash memory, processing called wear leveling for equally distributing data update sections is performed. In the wear leveling processing, for example, a logical address designated by the host apparatus is translated into a physical address of the nonvolatile semiconductor memory so that the data update sections are equally distributed.

In such address translation, a storing position of data is often managed by using a management table such as an address translation table representing a correspondence relationship between a logical address (LBA) supplied from outside and a physical address (NAND address) indicating a position at which data is stored on a NAND-type flash memory. The management table is loaded from a nonvolatile NAND-type flash memory onto a memory such as a dynamic random access memory (DRAM) at the time of start-up, which is updated every time data is written. The correspondence relationship in the address translation table needs to be backed up, for example, by using a backup technology such as the snapshot and the log for using the correspondence relationship over a power-turn-off.

However, writing speed of a NAND-type flash memory that uses the multi-value memory technology is slow. Therefore, if a parallel writing in a NAND-type flash memory or the like is to be performed for improving performance (speed up) of an SSD on which the NAND-type flash memory is mounted, a data amount to be written in the NAND-type flash memory in certain process units increases, and thus an amount of updates of the address translation table increases by the increased data amount to be written in the NAND-type flash memory, which results in increase in log. Thus, the number of times of writing in the NAND-type flash memory increases due to the increase in the amount of log, and the performance of a memory system degrades.

Exemplary embodiments of a memory system and a method of controlling memory system according to the present invention are described in detail below with reference to the accompanying drawings.

Embodiments of the present invention are explained below with reference to the drawings. In the following explanation, components having the same functions and configurations are denoted by the same reference numerals and signs. Redundant explanation of the components is performed only when necessary.

First, terms used in the specification are defined.

Physical page: A unit that can be collectively written and read out in a NAND-type flash memory.

Logical page: A writing and readout unit set in an SSD. The logical page is associated with one or more physical pages.

Physical block: A minimum unit that can be independently erased in the NAND-type flash memory. The physical block includes a plurality of physical pages.

Logical block: An erasing unit set in the SSD. The logical block is associated with one or more physical blocks. The logical block includes a plurality of logical pages.

Sector: A minimum access unit from a host. A sector size is, for example, 512 bytes (B).

Cluster: A management unit for managing “small data (fine grained data)” in the SSD. A cluster size is equal to or larger than the sector size and is set to be equal to a data management unit of a file system that an operating system (OS) of a host employs or a logical page size. For example, the cluster size can be set such that a size twice or larger natural number times as large as the cluster size is the logical page size.

Track: A management unit for managing “large data (coarse grained data)” in the SSD. A track size is set such that a size twice or larger natural number times as large as the cluster size is the track size. For example, the track size can be set equal to the logical block size.

Free block (FB): A logical block which does not include valid data therein and for which a use is not allocated. The free block includes the following two types, i.e., a complete free block (CFB) and a fragment free block (FFB).

Complete free block (CFB): A free block on which an erasing operation needs to be performed for reuse. After performing the erasing operation, writing can be performed from a logical page positioned at the top of a logical block.

Fragment free block (FFB): A free block in which a logical page with no data written therein remains and which can be reused without performing the erasing operation. Writing can be performed in the remaining logical page with no data written therein.

Bad block (BB): A physical block on the NAND-type flash memory that cannot be used as a storage area because of a large number of errors. For example, a physical block for which the erasing operation is not normally finished is registered as the bad block BB.

Writing efficiency: A statistical value of an erasing amount of the logical block with respect to a data amount written from the host in a specific period. As the writing efficiency is smaller, a wear degree of the NAND-type flash memory is smaller.

Valid cluster: A cluster that stores latest data (cluster-sized data) corresponding to a logical address.

Invalid cluster: A cluster that stores non-latest data (cluster-sized data) not to be referred as a result that data having an identical logical address is written in a different location.

Valid track: A track that stores latest data (track-sized data) corresponding to a logical address.

Invalid track: A track that stores non-latest data (track-sized data) not to be referred as a result that data having an identical logical address is written in a different location.

Multi level cell (MLC) mode: Mode in which writing is normally performed using an upper page and a lower page in a NAND-type flash memory capable of multi-valued storage. A logical block of the MLC mode is associated with one or more physical blocks used in the MLC mode.

Pseudo single level cell (SLC) mode: Mode in which writing is performed using only a lower page in a NAND-type flash memory capable of multi-valued storage. A logical block of the pseudo SLC mode is associated with one or more physical blocks used in the pseudo SLC mode. Even a physical block used once in the pseudo SLC mode can be used in the MLC mode after the erasing operation.

FIG. 1is a block diagram of a configuration example of an SSD100according to a first embodiment of the present invention. The SSD100is connected to a host apparatus1(hereinafter, host1) such as a PC or a central processing unit (CPU) core via a memory connection interface such as an advanced technology attachment interface (ATA I/F)2and functions as an external storage of the host1. The SSD100can transmit data to and receive data from an apparatus for debugging and manufacture inspection200via a communication interface3such as an RS232C I/F. The SSD100includes a NAND-type flash memory (hereinafter, NAND memory)10as a nonvolatile semiconductor memory, a drive control circuit4as a controller, a DRAM20as a volatile semiconductor memory, a power supply circuit5, a light-emitting diode (LED) for state display6, a temperature sensor7that detects a temperature in a drive, and a fuse8.

The power supply circuit5generates a plurality of different internal direct current (DC) power supply voltages from external DC power supplied from a power supply circuit on the host1side and supplies these internal DC power supply voltages to respective circuits in the SSD100. The power supply circuit5detects a rising edge of an external power supply, generates a power-on reset signal, and supplies the power-on reset signal to the drive control circuit4. The fuse8is provided between the power supply circuit on the host1side and the power supply circuit5in the SSD100. When an overcurrent is supplied from an external power supply circuit, the fuse8is disconnected to prevent malfunction of the internal circuits.

In this case, the NAND memory10includes four parallel operation elements10ato10dthat perform four parallel operations. The parallel operation elements10ato10dare connected to the drive control circuit4by four channels (ch0to ch3). Each of the parallel operation elements10ato10dincludes a plurality of banks (in this case, four banks (Bank0to Bank3)) capable of performing bank interleave. Each bank includes a plurality of NAND memory chips (in this case, two memory chips (Chip0and Chip1)). Each memory chip is divided into, for example, two districts of a plane0and a plane1each of which includes a plurality of physical blocks. The plane0and the plane1include peripheral circuits independent from each other (e.g., a row decoder, a column decoder, a page buffer, and a data cache) and can simultaneously perform erasing, writing, and readout by using a double speed mode. In this manner, each NAND memory chip of the NAND memory10can perform the parallel operation by a plurality of channels, the bank interleave operation by a plurality of banks, and the parallel operation by the double speed mode using a plurality of planes. Each memory chip can be divided into four planes or be configured without being divided.

The DRAM20functions as a cache for data transfer between the host1and the NAND memory10and a memory for a work area. In the memory for the work area of the DRAM20, a master table (snapshot) that is obtained by loading various management tables stored in the NAND memory10at the time of start-up or the like, log information that is a change difference of a management table, and the like are stored. A ferroelectric random access memory (FeRAM), a magnetoresistive random access memory (MRAM), a phase change random access memory (PRAM), or the like can be used instead of the DRAM20. The drive control circuit4performs data transfer control between the host1and the NAND memory10via the DRAM20and controls the respective components in the SSD100. The drive control circuit4supplies a signal for status display to the LED for state display6. The drive control circuit4also has a function of receiving a power-on reset signal from the power supply circuit5and supplying a reset signal and a clock signal to respective units in the own circuit and the SSD100.

Each of memory cell transistors MT includes a metal oxide semiconductor field effect transistor (MOSFET) including the stacked gate structure formed on a semiconductor substrate. The stacked gate structure includes a charge storage layer (a floating gate electrode) formed on the semiconductor substrate via a gate insulating film and a control gate electrode formed on the charge storage layer via an inter-gate insulating film. In the memory cell transistors MT, a threshold voltage changes according to the number of electrons accumulated in the floating gate electrode. The memory cell transistor MT stores data according to a difference in the threshold voltage. The memory cell transistor MT can be configured to store one bit or can be configured to store multiple values (data equal to or larger than two bits).

The memory cell transistor MT is not limited to the structure having the floating gate electrode and can be the structure such as a metal-oxide-nitride-oxide-silicon (MONOS) type that can adjust a threshold by causing a nitride film interface as a charge storage layer to trap electrons. Similarly, the memory cell transistor MT of the MONOS structure can be configured to store one bit or can be configured to store multiple values (data equal to or larger than two bits).

In each of the NAND strings, (q+1) memory cell transistors MT are arranged between a source of a selection transistor ST1and a drain of a selection transistor ST2such that current paths thereof are connected in series. In other words, the memory cell transistors MT are connected in series in a Y direction such that adjacent ones of the memory cell transistors MT share a diffusion region (a source region or a drain region).

Control gate electrodes of the memory cell transistors MT are connected to word lines WL0to WLq, respectively, in order from the memory cell transistor MT located on the most drain side. Therefore, a drain of the memory cell transistor MT connected to the word line WL0is connected to the source of the selection transistor ST1. A source of the memory cell transistor MT connected to the word line WLq is connected to the drain of the selection transistor ST2.

The word lines WL0to WLq connect the control gate electrodes of the memory cell transistors MT in common among the NAND strings in the physical block. In other words, the control gates of the memory cell transistors MT present in an identical row in the block are connected to an identical word line WL. (p+1) memory cell transistors MT connected to the identical word line WL are treated as one page (physical page). Data writing and data readout are performed by each physical page.

The bit lines BL0to BLp connect drains of selection transistors ST1in common among the blocks. In other words, the NAND strings present in an identical column in a plurality of blocks are connected to an identical bit line BL.

FIG. 2Bis a schematic diagram of a threshold distribution, for example, in a quaternary data storage mode for storing two bits in one memory cell transistor MT. In the quaternary data storage mode, any one of quaternary data “xy” defined by upper page data “x” and lower page data “y” can be stored in the memory cell transistor MT.

As the quaternary data “xy”, for example, “11”, “01”, “00”, and “10” are allocated in order of threshold voltages of the memory cell transistor MT. The data “11” is an erased state in which the threshold voltage of the memory cell transistor MT is negative. The rule of allocation of data is not limited thereto. The configuration can be such that three or more bits are stored in one memory cell transistor MT.

In a lower page writing operation, the data “10” is selectively written in the memory cell transistor MT having the data “11” (in the erased state) according to the writing of the lower bit data “y”. A threshold distribution of the data “10” before upper page writing is located about in the middle of threshold distributions of the data “01” and the data “00” after the upper page writing and can be broader than a threshold distribution after the upper page writing. In an upper page writing operation, writing of upper bit data “x” is selectively applied to a memory cell of the data “11” and a memory cell of the data “10”. The data “01” and the data “00” are written in the memory cells. In the pseudo SLC mode, writing is performed using only the lower page. The lower page writing is faster than the upper page writing.

FIG. 3is a block diagram of a hardware internal configuration example of the drive control circuit4. The drive control circuit4includes a data access bus101, a first circuit control bus102, and a second circuit control bus103. A processor104that controls the entire drive control circuit4is connected to the first circuit control bus102. A boot ROM105, in which a boot program for booting respective management programs (FW: firmware) stored in the NAND memory10is stored, is connected to the first circuit control bus102via a ROM controller106. A clock controller107that receives the power-on rest signal from the power supply circuit5shown inFIG. 1and supplies a reset signal and a clock signal to the respective units is connected to the first circuit control bus102.

The second circuit control bus103is connected to the first circuit control bus102. An I2C circuit108for receiving data from the temperature sensor7shown inFIG. 1, a parallel IO (PIO) circuit109that supplies a signal for status display to the LED for state display6, and a serial IO (SIO) circuit110that controls the RS232C I/F 3 are connected to the second circuit control bus103.

An ATA interface controller (ATA controller)111, a first error checking and correction (ECC) circuit112, a NAND controller113, and a DRAM controller114are connected to both the data access bus101and the first circuit control bus102. The ATA controller111transmits data to and receives data from the host1via the ATA interface2. A static random access memory (SRAM)115used as a data work area and a firmware expansion area is connected to the data access bus101via an SRAM controller116. When the firmware stored in the NAND memory10is started, the firmware is transferred to the SRAM115by the boot program stored in the boot ROM105.

The NAND controller113includes a NAND I/F117that performs interface processing for interface with the NAND memory10, a second ECC circuit118, and a direct memory access (DMA) controller for DMA transfer control119that performs access control between the NAND memory10and the DRAM20. The second ECC circuit118performs encode of a second correction code and performs encode and decode of a first error correction code. The first ECC circuit112performs decode of a second error correction code. The first error correction code and the second error correction code are, for example, a Hamming code, a Bose Chaudhuri Hocquenghem (BCH) code, a Reed Solomon (RS) code, or a low density parity check (LDPC) code. Correction ability of the second error correction code is higher than correction ability of the first error correction code. A technology related to such error correction is disclosed, for example, in International Patent Application PCT/JP2008/063344 or International Patent Application PCT/JP2008/063345 by the same applicant, and the whole content thereof is incorporated in the present application.

As shown inFIG. 1, in the NAND memory10, the four parallel operation elements10ato10dare connected in parallel to the NAND controller113in the drive control circuit4via four channels (4ch) each for a plurality of bits, so that the four parallel operation elements10ato10dcan be actuated in parallel. The NAND memory10of each channel is divided into four banks capable of the bank interleave, and can access to the plane0and the plane1of each memory chip simultaneously. Therefore, processing such as writing can be performed almost simultaneously on eight physical blocks (4 banks×2 planes) at the maximum for each channel.

FIG. 4is a block diagram of a functional configuration example of a firmware realized by the processor104. Functions of the firmware realized by the processor104are roughly classified into a data managing unit120, an ATA-command processing unit121, a security managing unit122, a boot loader123, an initialization managing unit124, and a debug supporting unit125.

The data managing unit120controls data transfer between the NAND memory10and the DRAM20and various functions concerning the NAND memory10via the NAND controller113and the first ECC circuit112. The ATA-command processing unit121performs data transfer processing between the DRAM20and the host1in cooperation with the data managing unit120via the ATA controller111and the DRAM controller114. The security managing unit122manages various kinds of security information in cooperation with the data managing unit120and the ATA-command processing unit121.

The boot loader123loads, when a power supply is turned on, the management programs (firmware) from the NAND memory10onto the SRAM115. The initialization managing unit124performs initialization of respective controllers and circuits in the drive control circuit4. The debug supporting unit125processes data for debug supplied from the outside via the RS232C interface. The data managing unit120, the ATA-command processing unit121, and the security managing unit122are mainly functional units realized by the processor104executing the management programs stored in the SRAM115.

In the present embodiment, functions realized by the data managing unit120are mainly explained. The data managing unit120performs, for example, provision of functions that the ATA-command processing unit121requests the NAND memory10and the DRAM20as storage devices (in response to various commands such as a Write request, a Cache Flush request, and a Read request from the host), management of a correspondence relation between a logical address given from the host1and a physical address of the NAND memory10, protection of management information by a snapshot and a log, provision of fast and highly efficient data readout and writing functions using the DRAM20and the NAND memory10, and ensuring of reliability of the NAND memory10.

FIG. 5is a schematic diagram of functional blocks formed in the NAND memory10and the DRAM20. A write cache (WC)21and a read cache (RC)22configured on the DRAM20are interposed between the host1and the NAND memory10. The WC21temporarily stores therein Write data from the host1. The RC22temporarily stores therein Read data from the NAND memory10. The blocks in the NAND memory10are allocated to respective management areas of a pre-stage storage area (FS: Front Storage)12, an intermediate stage storage area (IS: Intermediate Storage)13, and a main storage area (MS: Main Storage)11by the data managing unit120in order to reduce an amount of erasing for the NAND memory10during writing. The FS12manages data from the WC21in cluster units, i.e., “small units” and stores small data for a short period. The IS13manages data overflowing from the FS12in cluster units (first management units), i.e., “small units” and stores small data for a long period. The MS11manages data from the WC21, the FS12, and the IS13in track units (second management units), i.e., “large units”. A technology for managing blocks in the NAND memory10by allocating them in each management area in this manner is disclosed, for example, in International Patent Application PCT/JP2008/073950 or International Patent Application PCT/JP2008/067600 by the same applicant, and the whole content thereof is incorporated in the present application.

Specific functional configurations of the respective components shown inFIG. 5are explained in detail. When the host1performs Read or Write for the SSD100, the host1inputs logical block addressing (LBA) as a logical address via the ATA I/F2. As shown inFIG. 6, the LBA is a logical address in which serial numbers from zero are attached to sectors (size: 512 B). In the present embodiment, as management units for the WC21, the RC22, the FS12, the IS13, and the MS11, which are the components shown inFIG. 5, a logical cluster address formed of a bit string equal to or higher in order than a low-order (s+1)th bit of the LBA and a logical track address formed of a bit string equal to or higher in order than a low-order (s+t+1)th bit of the LBA are defined. In the present embodiment, the size of a track and a logical block is the same. A logical block is a virtual block associated with a plurality of physical blocks on a chip of the NAND memory10. In the present embodiment, a logical block is associated with physical blocks for the number of parallel channels (in this case, four channels as shown inFIG. 1). In the similar manner, a logical page is associated with physical pages for four channels. A logical block is selected from physical blocks belonging to the same bank for efficiently using the bank interleave.

The RC22is an area for temporarily storing, in response to a Read request from the host1, Read data from the NAND memory10(the FS12, the IS13, and the MS11). Data transfer to the host1is basically performed from the RC22. When data writing is performed from the WC21to the NAND memory10, data on the RC22of the same logical address is invalidated.

The WC21is an area for temporarily storing, in response to a Write request from the host1, Write data from the host1. Data on the WC21is managed in cluster units, and writing and management of valid data are performed in sector units. When a resource of the WC21becomes insufficient, data stored on the WC21is flushed to the NAND memory10. When writing is performed to the logical address same as that of data on the RC22from the host1, the latest data is stored on the WC21. Therefore, when there is data corresponding to the same logical address on the WC21, the RC22, and the NAND memory10, the data is new in the order of the WC21, the RC22, and the NAND memory10, so that the data on the WC21is prioritized to be returned to the host1.

The MS11performs data management in track units, and most user data is stored in the MS11. A track (high-density track) that has many valid clusters on the WC21is directly written from the WC21to the MS11. Moreover, data that cannot be managed by the FS12and the IS13is input to the MS11. A track of which LBA is the same as a track input to the MS11is invalidated in a logical block, and this logical block is released. A cluster that belongs to the track of which LBA is the same as the track input to the MS11is invalidated in a logical block, and a logical block in which all clusters are invalidated is released. The MS11consists of a plurality of logical blocks of the MLC mode. In the present embodiment, the size of a track and a logical block is the same, so that additional recording processing performed in the FS12or the IS13and compaction (processing for collecting only valid clusters to generate a new logical block and releasing an invalid cluster part) performed in the IS13are unnecessary in the MS11. If the track size is smaller than the logical block size, the additional recording processing performed in the FS12and the IS13and the compaction performed in the IS13can be applied to the MS11.

The FS12is a buffer that adapts a first-in first-out (FIFO) structure in which data is managed in cluster units, and input is performed in units of logical page in which a plurality of clusters is collected. A track (low-density track) with smaller number of valid clusters on the WC21is first written on the FS12. The FS12has the FIFO structure in which logical blocks are arranged in the order of data writing. When a cluster of which LBA is the same as a cluster present in the FS12is input to the FS12, it is sufficient to invalidate the cluster in the FS12, and rewriting is not performed. The cluster of which LBA is the same as the cluster input to the FS12is invalidated in a logical block, and a logical block in which all clusters in the logical block are invalidated is released. A cluster stored in a logical block that reaches the end of the FIFO structure of the FS12is regarded as a cluster with low possibility of rewriting from the host1and the logical block as a whole is moved to the IS13under the management of the IS13. In the present embodiment, the FS12consists of a plurality of logical blocks of the pseudo SLC mode to speed up writing. The FS12can consist of a plurality of logical blocks of the MLC mode. Data with a high update frequency is invalidated when passing through the FS12and only data with low update frequency overflows from the FS12, so that the FS12can separate data with low update frequency from data with high update frequency. Consequently, it is possible to lower the possibility that the compaction occurs frequently in the IS13of a subsequent stage.

The IS13is a buffer for storing a cluster with low possibility of rewriting, and management of data is performed in cluster units in the same manner as the FS12. When a cluster of which LBA is the same as a cluster present in the IS13is input to the FS12and the IS13, it is sufficient to invalidate the cluster in the IS13, and rewriting is not performed. In the similar manner to the FS12, the IS13has a list structure in which logical blocks are arranged in order from a logical block on which data is written first (from a logical block that is moved from the FS12first); however the IS13performs the compaction, which is different from the FS12. When the capacity of the IS13is saturated or management tables for the FS12and the IS13are saturated, the compaction (collecting valid clusters from the IS13and rewriting it to the IS13) or a defragmentation (integrating clusters of the FS12and the IS13into a track and flushing it to the MS11) is performed. In the present embodiment, the IS13consists of a mixture of logical blocks of the MLC mode and the pseudo SLC mode. In other words, a block moved from the FS12to the IS13is a logical block of the pseudo SLC mode; however, the block is rewritten to a logical block of the MLC mode when performing the compaction in the IS13. When the FS12consists of logical blocks of the MLC mode, the IS13also consists of only logical blocks of the MLC mode.

FIG. 7is a schematic diagram of management tables for the data managing unit120to control and manage the respective components shown inFIG. 5. The table for managing the DRAM20includes a RC management table23, a WC track table24, a WC track information table25, a WC high-density track information table26, and a WC low-density track information table27. The table for managing the NAND memory10includes a track table30, a cluster directory table31, a cluster table32, a cluster block information table33, and a logical-to-physical translation table40. The table for managing the NAND memory10is classified into a table referred to in a forward lookup address translation and a table referred to in a reverse lookup address translation. The forward lookup address translation is to obtain (logical block address+cluster position) at which data is actually stored from LBA of the data. The reverse lookup address translation is to obtain LBA of data from (logical block address+cluster position).

The RC management table23is for managing data transferred from the NAND memory10to the RC22.

The WC track table24is a hash table to look up WC track information concerning data stored on the WC21from LBA, and includes a plurality of entries (tags) for each index that is a few bits of least significant bits (LSB) of a track address of the LBA. Each tag stores an LBA track address and a pointer to the WC track information corresponding to the track address.

The WC track information table25includes a WC track least recently used (LRU) information table25afor managing the time ordering of accessed WC track information by a double-linked list using LRU and a WC track free information table25bthat manages a free WC track information number. When data is flushed from the WC21to the NAND memory10, the oldest accessed track is taken by using the WC track LRU information table25a.

WC track information corresponds to one of a plurality of tracks present in the WC21.

WC track information includes (1) a track address present in the WC21, the number of valid clusters on the WC21in a track, information indicating whether each cluster is valid, and cluster position information indicating a position of each cluster in the WC21, (2) information (sector bitmap) indicating a sector that stores valid data among a plurality of sectors included in one cluster, and (3) track status information (e.g., valid, invalid, during data transfer from ATA, and during writing in the NAND memory). In the WC track information, LSB (t) bits of a cluster address present in the own track are managed at a storage position at which a valid cluster is present; however, the method of managing a cluster address is arbitrary. For example, the LSB (t) bits themselves of the cluster address present in the own track can be managed (seeFIG. 6).

The WC high-density track information table26is for managing high-density (the number of valid clusters in a track is equal to or more than a specific percentage) track information to be written on the MS11and manages WC track information concerning a high-density track and the number thereof.

The WC low-density track information table27is for managing low-density (the number of valid clusters in a track is less than a specific percentage) track information to be written in the FS12and manages the total number of clusters of a low-density track.

The track table30is a table for obtaining track information from a track address of LBA. Track information includes (1) a logical block address (information indicating a logical block in which data of a track is stored), (2) a cluster directory number (information that becomes valid when at least part of data in a track is stored in the FS12or the IS13and that indicates a table number of a cluster directory table that is present for each track when data in a track is stored in the FS12or the IS13), and (3) the number of FS/IS clusters (information that indicates the number of clusters in a track stored in the FS12or the IS13and is used for determining whether to perform the defragmentation).

The cluster directory table31is an intermediate table for tracing to a logical block when data in a track is stored in the FS12or the IS13. The cluster directory table31is provided for each track. Cluster directory information registered in each cluster directory table31consists of an array of information (cluster table number information) indicating a table number of the cluster table32. One piece of information is selected from among a plurality of pieces of the cluster table number information arrayed in one cluster directory table31by upper few bits in LSB (t) bits of a cluster address of LBA.

The cluster directory table31includes a cluster directory LRU table31afor managing the time ordering of cluster directory information (array of cluster table number information) together with a corresponding track address with a writing time as a reference by a double-linked list using LRU and a cluster directory free information table31bthat manages a free cluster directory together with a corresponding track address by a double-linked list.

The cluster table32is a table that relates to the cluster directory table31and manages a cluster position in a logical block at which data is stored when the data in a track is stored in the FS12or the IS13. The cluster table32is referred to from the track table30indirectly via the cluster directory table31. The cluster table32is actually an array of (logical block address+cluster position) for a plurality of clusters. One piece of information is selected from among a plurality of pieces of (logical block address+cluster position) arrayed in one cluster table32by lower few bits in LSB (t) bits of a cluster address of LBA. The cluster table32also includes a cluster block information number and information about a cluster position therein as an array.

The cluster block is a block that stores data in cluster units among logical blocks. Cluster block information is information for managing logical blocks of the FS12and the IS13and indicates a type of a cluster present in the logical blocks. A plurality of the cluster block information is coupled in the order of FIFO in the FS12and the IS13as a double-linked list.

Cluster block information includes (1) a logical block address, (2) the number of valid clusters, and (3) LBA of a cluster included in a logical block.

The cluster block information table33includes a cluster block information table33afor managing free information, a cluster block information table33bfor the FS12, and a cluster block information table33cfor the IS13. The cluster block information table33amanages unused cluster block information, the cluster block information table33bmanages cluster block information included in the FS12, and the cluster block information table33cmanages cluster block information included in the IS13. Each of the cluster block information tables33ato33cis managed as a double-linked list. The principal use of the reverse lookup address translation is the compaction of the IS13. The reverse lookup address translation is used to check a type of a cluster stored in a logical block as a compaction target and rewrite data to a different location. Therefore, in the present embodiment, the reverse lookup address translation targets only the FS12and the IS13that store data in cluster units.

The logical-to-physical translation table40is a table for managing information concerning translation between a logical block address and a physical block address and the life. The logical-to-physical translation table40includes information indicating a plurality of physical block addresses belonging to a logical block, information indicating the number of times of erasing of a logical block address, and information about a cluster block information number, for each logical block address. For rewriting data of a certain LBA to a different location, the LBA in an original cluster block needs to be invalidated, so that it is needed to trace to a cluster block from the LBA. Therefore, an identifier of cluster block information is stored in management information of a logical block managed by the logical-to-physical translation table40.

With the management information managed by each management table, LBA used in the host1, a logical NAND address (logical block address+offset) used in the SSD100, and a physical NAND address (physical block address+offset) used in the NAND memory10can be associated with each other, so that data exchange between the host1and the NAND memory10can be performed.

The tables for NAND memory management, such as the track table30, the cluster directory table31, the cluster table32, the cluster block information table33, and the logical-to-physical translation table40shown inFIG. 7, among the above management tables are stored in a specific area of the nonvolatile NAND memory10. At the time of start-up, each management table stored in the NAND memory10is loaded onto a work area of the volatile DRAM20, which is used by the data managing unit120, so that each management table is updated. Each management table loaded on the DRAM20is called a master table. Even when the power is turned off, the master table needs to be restored to a state before the power is turned off, so that a system of storing the master table in the nonvolatile NAND memory10is needed. A snapshot indicates a whole nonvolatile management table on the NAND memory10. An operation of storing the master table loaded on the DRAM20directly in the NAND memory10is expressed also as “take a snapshot”. A log indicates a change difference of a management table. If a snapshot is taken for every update of a master table, a processing speed becomes slow and the number of times of writing in the NAND memory10increases, so that only a log as a change difference is normally recorded in the NAND memory10. An operation of reflecting a log in a master table and storing it in the NAND memory10is expressed also as “commit”.

FIG. 8is a schematic diagram illustrating an updating state of a snapshot and a log at the time of data update. When the data managing unit120updates data, changes made to a master table are accumulated in a log (hereinafter, “DRAM log”) on the DRAM20. Depending on the type of a management table, a master table is directly updated and an updated content is accumulated in a DRAM log, or an updated content is recorded in a change area secured on the DRAM log without directly changing a master table. When performing data readout or data writing, the accumulated DRAM log is also referred to in addition to a master table.

After data update becomes stable, a log is committed. In the commit processing, a content of a DRAM log is reflected in a master table as necessary and is further stored in the NAND memory10to make it nonvolatile. A snapshot is stored in the NAND memory10on occasions such as in a normal power-off sequence and when a storage area for a log on the DRAM20becomes insufficient. At the time when writing of a log or a snapshot in the NAND memory10is finished, the processing of making the management table nonvolatile is completed. A technology for making the management information nonvolatile in this manner is disclosed, for example, in International Patent Application PCT/JP2009/052597 by the same applicant, and the whole content thereof is incorporated in the present application.

Read processing is briefly explained. When a Read command and LBA as a readout address are input from the ATA-command processing unit121, the data managing unit120searches through the RC management table23and the WC track table24to check whether data corresponding to the LBA is present in the WC21or the RC22. In the case of a cache hit, the data managing unit120reads out data of the WC21or the RC22corresponding to the LBA and sends the data to the ATA-command processing unit121.

If there is no hit in the RC22or the WC21, the data managing unit120searches in which part of the NAND memory10data as a search target is stored. If the data is stored on the MS11, the data managing unit120traces the LBA→the track table30→the logical-to-physical translation table40to obtain the data on the MS11. On the other hands, if the data is stored on the FS12or the IS13, the data managing unit120traces the LBA→the track table30→the cluster directory table31→the cluster table32→the logical-to-physical translation table40to obtain the data on the FS12or the IS13.

(Processing in the WC21)

Next, write processing is briefly explained. When a Write command and LBA as a write address are input from the ATA-command processing unit121, data specified by the LBA is written on the WC21. If the WC21has no free area, data is flushed from the WC21to be written in the NAND memory10by referring to each management table for DRAM management thereby generating a free area. A low-density track in which the number of valid clusters in a track is less than a specific percentage is flushed to the FS12as cluster size data. When the flush destination is the FS12, a valid cluster in the track is written in logical page units.

A high-density track in which the number of valid clusters in a track is equal to or more than the specific percentage is flushed to the MS11as track size data. When the flush destination is the MS11, data of a track size is directly written in the whole logical block. When there is a plurality of logical blocks as a writing target, the transfer efficiency is improved by using the double-speed mode or the bank interleave. Each management table for DRAM management is updated in accordance with data written in the WC21or flush of data to the NAND memory10.

(Writing in the MS11)

Writing in the MS11is performed in the following procedures as shown inFIG. 9.

1. A data image of a track is generated on the DRAM20(padding processing). Specifically, a cluster that is not present in the WC21and a cluster that holds not all the sectors in the WC21are read out from the NAND memory10to be integrated with data of the WC21.

2. A logical block (track block) is secured from a CFB for the MS11. The track block is a block that stores therein data in track units among logical blocks.

3. The generated data image of the track is written in the secured logical block.

4. Track information is checked from LBA of the track, which is correlated with a logical block address corresponding to the written logical block to be registered in a required table for NAND memory management.

5. Old data in the WC21and the NAND memory10is invalidated.

(Writing in the FS12)

Writing in the FS12is performed by generating a data image of a cluster on the DRAM20(padding processing) and performing writing on a newly-secured logical block (cluster block) in logical page units by using the pseudo SLC mode. As the logical block to be secured, an FFB having a logical page capable of writing a data image equal to or more than a data image to be written is prioritized. If an FFB is not present, a CFB is used. The writing in the FS12is performed in the procedures as shown inFIG. 10.

A logical block (cluster block) for writing data of a low-density track from the WC21to the FS12is called an FS input buffer (FSIB).

1. When a total data amount in the low-density track input from the WC21is small, i.e., when the number of valid clusters is smaller than a specific threshold, an FFB in which the data can be written is secured to be an FSIB.

2. When the total data amount in the low-density track input from the WC21is large, i.e., when the number of valid clusters is equal to or larger than the specific threshold, a CFB is secured to be an FSIB. At this time, a plurality of logical blocks capable of writing data in parallel is secured to be an FSIB.

3. A data image of a cluster to be written is generated on the DRAM20. Specifically, regarding a cluster that holds not all the sectors in the WC21, data of a sector that is not present on the WC21is read out from the NAND memory10to be integrated with data of a sector on the WC21.

4. The cluster on the WC21and the cluster image generated on the work area are written in the FSIB.

5. The FSIB is added to a list of the FS12.

6. The written track is reinserted into the end of the cluster directory LRU table31a.

(Movement from the FS12to the IS13)

When the number of logical blocks under the management of the FS12exceeds the maximum number of logical blocks, as shown inFIG. 11, a logical block that is overflowed from the FS12is moved directly to the IS13. The number of logical blocks to be moved in one process is determined by the following rule in accordance with the number of valid clusters in the overflowed logical block.

A logical block that is moved is added from the oldest logical block of the FS12so that the number of clusters in the overflowed logical block becomes close to the border of one logical block of the MLC mode. The number of clusters is caused to be close to the border of one logical block of the MLC mode to accommodate valid clusters as many as possible in a logical block after the compaction.

When the number of clusters exceeds the number of clusters that can be subjected to the compaction simultaneously in the IS13, the number of blocks is set so that the number of clusters is equal to or smaller than the number of clusters that can be subjected to the compaction simultaneously in the IS13.

The upper limit value is set to the number of blocks to be moved.

(Compaction and Defragmentation in the IS13)

In the IS13, when the number of logical blocks under the management of the IS13exceeds the maximum number of logical blocks, the IS13suppresses the number of logical blocks to be equal to or less than the maximum number of blocks by data movement (defragmentation processing) to the MS11and the compaction. When a data erasing unit (logical block) and a data management unit (cluster) are different, according to the progress of rewriting of the NAND memory10, logical blocks are made porous by invalid data. When the logical blocks in such a porous state increase, substantially usable logical blocks decrease and a storage area of the NAND memory10cannot be effectively used. Therefore, processing called compaction for collecting valid clusters and rewriting it in a different logical block is performed. The defragmentation processing is processing of integrating clusters of the FS12and the IS13into a track and flushing it to the MS11.

Subsequently, the essential part of this embodiment is explained more in detail. First, the forward lookup address translation using the forward lookup management table and the reverse lookup address translation using the reverse lookup management table are explained.

FIG. 12is a schematic diagram illustrating the forward lookup address translation. The forward lookup address translation is to obtain a logical cluster address (logical block address and offset) in which data is actually recorded from LBA. The forward lookup address translation is mainly performed to read out data from the NAND memory10to the DRAM20, more specifically, to read out data required from the ATA-command processing unit121and to read out padding data when writing data in the NAND memory10and organizing data in the NAND memory10. In the forward lookup address translation, a logical NAND address is obtained by tracing tables of two stages from the track table30, i.e., the LBA→the track table30→the cluster directory table31→the cluster table32→the logical NAND address.

FIG. 13is a flowchart of the forward lookup address translation processing performed by the data managing unit120.

Specifically, the data managing unit120translates LBA into a track address higher in order than a (s+t+1)th bit (Step S100), obtains track information from the track table30with the translated track address as an index (Step S110), and obtains a cluster directory number in the track information. The data managing unit120determines whether the cluster directory number is an invalid value or a valid value (Step S120). If the cluster directory number is an invalid value (Yes at Step S120), it is determined that data is stored in the MS11and a logical block address is obtained from the track information (Step S130). The data managing unit120translates the obtained logical block address into a physical block address by the logical-to-physical translation table40(Step S140), and further calculates offset from the calculated physical block address from LSB (t) bits of a cluster address of the LBA (Step S150), thereby obtaining cluster data in the physical block (Step S210).

On the other hands, if the cluster directory number is a valid value (No at Step S120), the data managing unit120obtains a cluster directory corresponding to the cluster directory number (Step S160), obtains an identifier (cluster table number) of a cluster table from the cluster directory with upper few bits of LSB (t) bits of the cluster address as an index (cluster directory index) with respect to the obtained cluster directory (Step S170), and obtains the cluster table corresponding to the identifier (Step S180). The data managing unit120obtains a logical cluster address (logical block address and offset) from the cluster table with lower few hits of the LSB (t) bits of the cluster address of the LBA as an index (cluster table index) (Step S190). The data managing unit120translates the obtained logical block address into a physical block address by the logical-to-physical translation table40(Step S200) and obtains cluster data (Step S210).

FIG. 14is a schematic diagram illustrating the reverse lookup address translation.FIG. 15is a flowchart of the reverse lookup address translation processing performed by the data managing unit120. The reverse lookup address translation is to obtain LBA of data from a logical cluster address (logical block address and offset) in which the data is actually recorded. The reverse lookup address translation is mainly performed for the compaction of the IS13. Data (track or cluster) of the LBA stored in a logical block as a compaction target is checked to be used for rewriting the data to a different logical block. When writing data in the NAND memory10or organizing data in the NAND memory10, reverse lookup management information is updated.

In the present embodiment, the reverse lookup address translation is used only with respect to data in the FS12and the IS13in which data is recorded in cluster units, and is not used for data in the MS11that records data in track units. Reverse lookup information of data in cluster units is stored in the cluster block information table33. In performing the reverse lookup address translation, first, the data managing unit120specifies a certain cluster block. The following procedures are performed to determine LBA of a cluster stored in the specified cluster block by the data managing unit120. The reverse lookup address translation for a cluster block belonging to the IS13is explained.

1. The data managing unit120searches a list of the cluster block information table33belonging to the IS13. In the compaction of the TS13, a cluster block is selected from among cluster blocks belonging to the IS13in accordance with a certain rule (Step S300). The cluster blocks belonging to the IS13are managed in a double link structure in the cluster block information table33, so that it is possible to reach the cluster block information by tracing the link.

2. As described above, the cluster table32also has an array of cluster block information numbers and information (offset) about cluster positions therein. The data managing unit120obtains a cluster address in the cluster block information with information (offset) about a cluster position obtained from the cluster table32as an index (Step S310).

The track table30, the cluster directory table31, and the cluster table32, for the forward lookup, and the cluster block information table33for the reverse lookup basically share information. If a failure occurs in one of the forward lookup management table and the reverse lookup management table, the reverse lookup management table can be restored from the forward lookup management table, or vice versa. In the present embodiment, a reverse lookup address translation table in track units for the MS11is not provided, and LBA is obtained by scanning the track table30that manages tack information as the forward lookup information.

FIG. 16is a functional block diagram illustrating a relevant portion according to the present embodiment of the present invention. As described above, the NAND memory10stores a user-data storing unit201, such as the MS11, the FS12, and the IS13, which stores therein user data, a NAND management table202for NAND memory management that is stored in a specific storage area on the NAND memory10as a snapshot, and a log (hereinafter, “NAND log”)203that is stored in a specific storage area on the NAND memory10in the similar manner to the NAND management table202as change difference information of the NAND management table202. The NAND management table202includes tables shown inFIG. 7, such as the track table30, the cluster directory table31, the cluster table32, the cluster block information table33, and the logical-to-physical translation table40, except for tables for DRAM management.

In the DRAM20, the WC21, the RC22, a master table204that is the NAND management table202loaded on the DRAM20, and a DRAM log205as a log on the DRAM20that accumulates and stores changes made to the master table204are stored. As described above, the master table204includes a forward lookup table204afor performing the forward lookup address translation and a reverse lookup table204bfor performing the reverse lookup address translation.

A controller120as the data managing unit includes a table transferring unit209, a read/write control unit210, a log control unit211, and a log reflecting unit212.

The table transferring unit209performs various processing, such as processing of transferring various NAND management tables (snapshot)202stored in the NAND memory10to the DRAM20as the master table204at the time of start-up and processing of storing the master table204on the DRAM20in the NAND memory10as a snapshot when a specific condition is satisfied such as when a normal power-off sequence occurs or a storage area for a log becomes insufficient.

The read/write control unit210performs the above-described read/write control based on the master table204and the DRAM log205.

The log control unit211performs processing of accumulating and storing only difference information of the reverse lookup table204bof the master table204, which manages the reverse lookup information, before and after update when an event occurs so that the master table204needs to be updated.

When a specific condition is satisfied, such as when an amount of log reaches a certain value or at the time when data update becomes stable so that management tables are consistent with each other after accumulated log is reflected in each management table of the master table204, the log reflecting unit212stores the DRAM log205on the DRAM20in the NAND memory10as the NAND log203and performs the commit processing of reflecting the DRAM log205in both of the forward lookup table204aand the reverse lookup table204b. After a snapshot is taken or the commit processing is performed, the DRAM log205accumulated on the DRAM20is invalidated.

Next, accumulation of log, the commit processing, a restoring operation, and the like are explained with reference toFIGS. 17 to 20.FIG. 17is a schematic diagram for explaining the accumulation of log, the commit processing, the restoring operation, and the like.FIG. 18is a flowchart of the log accumulation processing.FIG. 19is a flowchart of the commit processing of log.FIG. 20is a flowchart of the table restoring processing.

In an initial state, the read/write control unit210performs the above-described read/write control based on only the master table204that the table transferring unit209transfers on the DRAM20. When an event occurs so that the master table204needs to be updated, such as writing on the NAND memory10or organizing data in the NAND memory10(defragmentation or compaction) (Step S400), the log control unit211secures a copy of only a changed portion of the master table204to the DRAM log205without directly updating the master table204and records a change difference to the copy for update.

When generating the DRAM log205, the log control unit211updates only the reverse lookup table204bthat manages the reverse lookup information, and does not update the forward lookup table204athat manages the forward lookup information, which is only referred to (Step S410). The cluster block information table33belongs to a reverse lookup table among the NAND management tables shown in FIG.7. The cluster block information is information indicating a cluster address (LBA) of data stored in a logical block belonging to the FS12and the IS13, and each cluster block information, for example, is managed by dividing a logical block in a certain size (cluster page) such as in logical page units for reducing a recording size to a log. Therefore, one to a plurality of updates that occurs in a cluster page that is divided in a certain size is accumulated and recorded in order in the same entry of the DRAM log205.

As described above, although a reverse lookup address translation table for the MS11(logical table→LBA track address) in track units is not provided, because only a log of a reverse lookup table is taken in the present embodiment, the log control unit211records a log of temporary reverse lookup information of a track called track block information in the DRAM log205for updating the track table30(Step S420). In the track block information, a logical block address in which a track is written and a track address are stored.

When an entry of the same management table is referred to or updated many times, the read/write control unit210and the log control unit211take a copy on the DRAM log205as a target for reference or update as the latest management information. As a method of searching for a copy on the DRAM log205, a pointer to the copy on the DRAM log205is embedded in the master table204(Step S410). For the reference or the update, an address of the copy is brought to be a target for the reference or the update. Consequently, when the read/write control unit210refers to a table, whether the table is the master table204or the copy on the DRAM log205can be transparently handled.

Next, when a specific condition (first condition) is satisfied, such as when an amount of log reaches a certain value or when updated management tables are consistent with each other (Step S500), the commit processing is performed. In the commit processing, the log reflecting unit212reflects the DRAM log205that accumulates only the reverse lookup information in the reverse lookup table204b(Step S510), restores the forward lookup table204aby using the DRAM log205that accumulates only the reverse lookup information (Step S520), and further stores the DRAM log205that accumulates only the reverse lookup information in the NAND memory10as the NAND log203to make it nonvolatile (Step S530). In the commit processing, when the DRAM log205is reflected in the master table204, interrupt read from the host is prohibited.

When the cluster block information as the reverse lookup information is committed, the following processing is performed for each cluster block information.

(1) The log reflecting unit212compares cluster addresses in a logical block of the master table204that correspond to cluster block information on the DRAM log205, and reflects a cluster address that becomes a valid state from an invalid state in the forward lookup address translation table such as the track table30, the cluster directory table31, and the cluster table32.

If the cluster directory table31and the cluster table32are not allocated to track information, an entry is secured.

A logical block address and a cluster position corresponding to the cluster block information are set to the cluster table32.

(2) The log reflecting unit212copies the cluster block information on the DRAM log205to the corresponding master table204.

When track block information as the reverse lookup information is committed, the following processing is performed for each track block information.

(1) The log reflecting unit212releases the cluster directory table31and the cluster table32in track information corresponding to a track address in track block information on the DRAM log205.

(2) The log reflecting unit212sets a logical block address in the track block information to corresponding track information.

The forward lookup management table is updated to the latest state by the commit processing. That is, the read/write control unit210can perform the above-described read/write control by referring to the latest forward lookup management table after the commit processing.

When a specific condition (second condition) is satisfied, such as when a normal power-off sequence occurs or when a storage area for a log becomes insufficient, the table transferring unit209stores the master table204on the DRAM20as a snapshot in the NAND memory10as the NAND management table202.

When, for example, incorrect power-off occurs without a normal power-off sequence being performed, the NAND management table202in the NAND memory10is not the latest condition and the NAND log203is the latest condition.

For example, when the log reflecting unit212detects such condition by comparing timestamps of the NAND log203and the NAND management table202at the time of start-up of the SSD100(Step S600), the table transferring unit209transfers the NAND management table (snapshot)202stored in the NAND memory10to the DRAM20as the master table204(Step S610). Furthermore, the log control unit211transfers the NAND log (only the reverse lookup information)203to the DRAM20to generate the DRAM log205(only the reverse lookup information) (Step S620). Thereafter, the log reflecting unit212reflects the generated DRAM log205in the reverse lookup table204b(Step S630) and restores the forward lookup table204aby using the DRAM log205(Step S640).

The forward lookup information is not included in a log, so that the log can be reduced. Moreover, if a forward lookup master table is not updated in an update operation in which the status of the master table and the log is unstable, the forward lookup master table is always in a stable condition except when the DRAM log205is reflected in the forward lookup master table, so that the forward lookup address translation can be performed always by the master table in response to interrupt read from a host.

In the write processing of data on the FS12or the IS13, while considering logical block units, a free page of a block is searched for, and data is additionally written in the free page. A reverse lookup table indicates the type of data held in a free area of a block or in a block, and write processing mainly uses the reverse lookup table. In such write processing, the forward lookup table is used only for padding, invalidation of overwritten data, and the like. Therefore, designing becomes easy and the cost for designing can be reduced by storing reverse lookup information as a log rather than forward lookup information.

According to the first embodiment, only changes of a reverse lookup table are recorded in a log, and a forward lookup table is constructed based on the log of the reverse lookup table at the time of the commit processing, so that the amount of the log that needs to be stored in a DRAM or a NAND memory can be reduced.

In the present embodiment, only reverse lookup information is recorded as a log; however, it is possible to reduce a log by recording only forward lookup information. Moreover, a reverse lookup address translation table in track units for the MS11is not provided and only a reverse lookup address translation table in cluster units for the FS12and the IS13is provided; however, when the compaction processing is needed also in the MS11because a track size is set to be smaller than a logical block size, a reverse lookup address translation table in track units can be provided to speed up the searching processing.

FIG. 21is a perspective view of an example of a PC1200on which the SSD100is mounted. The PC1200includes a main body1201and a display unit1202. The display unit1202includes a display housing1203and a display device1204accommodated in the display housing1203.

The main body1201includes a chassis1205, a keyboard1206, and a touch pad1207as a pointing device. The chassis1205includes a main circuit board, an optical disk device (ODD) unit, a card slot, and the SSD100.

The card slot is provided so as to be adjacent to the peripheral wall of the chassis1205. The peripheral wall has an opening1208facing the card slot. A user can insert and remove an additional device into and from the card slot from outside the chassis1205through the opening1208.

The SSD100can be used instead of a conventional hard disk drive (HDD) in the state of being mounted on the PC1200or can be used as an additional device in the state of being inserted into the card slot.

FIG. 22is a schematic diagram of a system configuration example of the PC1200on which the SSD100is mounted. The PC1200includes a CPU1301, a north bridge1302, a main memory1303, a video controller1304, an audio controller1305, a south bridge1309, a basic input/output system read-only memory (BIOS-ROM)1310, the SSD100, an ODD unit1311, an embedded controller/keyboard controller IC (EC/KBC)1312, and a network controller1313.

The CPU1301is a processor for controlling an operation of the PC1200, and executes an operating system (OS) loaded from the SSD100onto the main memory1303. Furthermore, when the ODD unit1311is capable of executing at least one of read processing and write processing on a mounted optical disk, the CPU1301executes the processing.

Moreover, the CPU1301executes a system BIOS stored in the BIOS-ROM1310. The system BIOS is a computer program for controlling a hardware of the PC1200.

The north bridge1302is a bridge device that connects a local bus of the CPU1301to the south bridge1309. The north bridge1302has a memory controller for controlling an access to the main memory1303.

Moreover, the north bridge1302has a function of executing a communication with the video controller1304and a communication with the audio controller1305through an accelerated graphics port (AGP) bus and the like.

The main memory1303temporarily stores therein a computer program and data, and functions as a work area of the CPU1301. The main memory1303, for example, consists of a DRAM.

The video controller1304is a video reproduction controller for controlling the display unit1202used as a display monitor of the PC1200.

The audio controller1305is an audio reproduction controller for controlling a speaker1306of the PC1200.

The south bridge1309controls each device on a low pin count (LPC) bus1314and each device on a peripheral component interconnect (PCI) bus1315. Moreover, the south bridge1309controls the SSD100that is a memory device storing various types of software and data through the ATA interface.

The PC1200accesses the SSD100in sector units. A write command, a read command, a flush command, and the like are input to the SSD100through the ATA interface.

The south bridge1309has a function of controlling an access to the BIOS-ROM1310and the ODD unit1311.

The EC/KBC1312is a one-chip microcomputer in which an embedded controller for power management and a keyboard controller for controlling the keyboard1206and the touch pad1207are integrated.

The EC/KBC1312has a function of turning on/off the PC1200based on an operation of a power button by a user. The network controller1313is, for example, a communication device that executes communication with an external network such as the Internet.