Memory system and method for controlling nonvolatile memory

1. A memory system connectable to a host, comprising:

a nonvolatile memory; and

a controller electrically connected to the nonvolatile memory and configured to store a part of contents of a logical-to-physical address translation table stored in the nonvolatile memory in a random access memory as a first cache, and store compressed address translation data obtained by compressing the contents of the logical-to-physical address translation table in the random access memory as a second cache,

wherein the controller is configured to:

execute, when first address translation data including a first physical address indicating a physical storage location of the nonvolatile memory where data corresponding to a first logical address specified by the host is stored does not exist in the first cache and first compressed address translation data corresponding to the first address translation data exists in the second cache, an operation for storing uncompressed address translation data obtained by decompressing the first compressed address translation data in the second cache in the first cache and an operation for acquiring the first physical address from the uncompressed address translation data; and

execute, when the first address translation data does not exist in the first cache and the first compressed address translation data does not exist in the second cache, an operation for reading the first address translation data from the logical-to-physical address translation table, an operation for storing the read first address translation data in the first cache, an operation for acquiring the first physical address from the read first address translation data, and an operation for storing compressed address translation data obtained by compressing the read first address translation data in the second cache.

2. The memory system according to claim 1 , wherein the second cache has a size capable of holding compressed address translation data for logical-to-physical address translation for all logical addresses of the memory system.

3. The memory system according to claim 1 , wherein the controller is configured to secure a first region for the second cache on the random access memory, such that the second cache has a first size capable of holding compressed address translation data for logical-to-physical address translation for all logical addresses of the memory system, and use the remaining second region of the random access memory as the first cache.

4. The memory system according to claim 3 , wherein the controller is configured to change a size of the second cache from an initial size to the first size, such that the size of the second cache increases as an amount of compressed address translation data cached in the second cache increases, and use both an unused region in the first region and the second region as the first cache until the size of the second cache increases to the first size.

5. The memory system according to claim 4 , wherein the controller is configured to dispose the first cache and the second cache on the random access memory, such that a region used as the second cache increases in a direction from an end of the first region toward a boundary between the first region and the second region and a region used as the first cache increases in a direction from an end of the second region toward the boundary.

6. The memory system according to claim 1 , wherein

the controller comprises a decoder circuit that decompresses compressed data and an encoder circuit that compresses data, and

the controller is configured to

when the first address translation data does not exist in the first cache and the first compressed address translation data corresponding to the first address translation data exists in the second cache, decompress the first compressed address translation data by the decoder circuit, and

when the first address translation data does not exist in the first cache and the first compressed address translation data does not exist in the second cache, compress the read first address translation data by the encoder circuit.

7. The memory system according to claim 1 , wherein

the first cache comprises a plurality of cache entries and each cache entry of the first cache stores address translation data including a plurality of physical addresses corresponding to a plurality of consecutive logical addresses, and

the second cache comprises a plurality of cache entries and each cache entry of the second cache stores compressed address translation data obtained by compressing the address translation data including the physical addresses.

8. A method of controlling a nonvolatile memory in a memory system, the method comprising:

storing a part of contents of a logical-to-physical address translation table stored in the nonvolatile memory in a random access memory as a first cache and storing compressed address translation data obtained by compressing the contents of the logical-to-physical address translation table in the random access memory as a second cache;

executing, when first address translation data including a first physical address indicating a physical storage location of the nonvolatile memory where data corresponding to a first logical address specified by a host is stored does not exist in the first cache and first compressed address translation data corresponding to the first address translation data exists in the second cache, an operation for storing uncompressed address translation data obtained by decompressing the first compressed address translation data in the second cache in the first cache and an operation for acquiring the first physical address from the uncompressed address translation data; and

executing, when the first address translation data does not exist in the first cache and the first compressed address translation data does not exist in the second cache, an operation for reading the first address translation data from the logical-to-physical address translation table, an operation for storing the read first address translation data in the first cache, an operation for acquiring the first physical address from the read first address translation data, and an operation for storing compressed address translation data obtained by compressing the read first address translation data in the second cache.

9. The method according to claim 8 , wherein the second cache has a size capable of holding compressed address translation data for logical-to-physical address translation for all logical addresses of the memory system.

10. The method according to claim 8 , further comprising:

securing a first region for the second cache on the random access memory, such that the second cache has a first size capable of holding compressed address translation data for logical-to-physical address translation for all logical addresses of the memory system; and

using the remaining second region of the random access memory as the first cache.

11. The method according to claim 10 , further comprising:

changing a size of the second cache from an initial size to the first size, such that the size of the second cache increases as an amount of the compressed address translation data cached in the second cache increases; and

using both an unused region in the first region and the second region as the first cache until the size of the second cache increases to the first size.