Memory system

A memory system that is connectable to a host, the memory system comprising:

• a non-volatile memory including a plurality of blocks;
• a volatile memory;
• and
• a controller configured to manage a correspondence relationship between each of logical addresses included in a logical address space of the memory system and each of physical addresses of the non-volatile memory using a logical-to-physical address translation table stored in the volatile memory,
• wherein the logical-to-physical address translation table includes at least a first table area that stores N pieces of address translation information respectively corresponding to N logical address ranges, where N is an integer equal to or greater than 2, and the controller is configured to:
• write the N pieces of address translation information, including first to (N)th pieces, repeatedly in a first block of the non-volatile memory according to a first order, so that the first, second, . . . , (N)th pieces are written in this order repeatedly in the first block;
• write an update log in the first block each time one of the N pieces is written in the first block, wherein the update log contains all updates to the N pieces of address translation information since the last time the update log was written in the first block, wherein the update log includes logs that are of a first type or a second type, the first type log including a logical address corresponding to data written into the non-volatile memory in response to a write command and a physical address indicating a storage location in the non-volatile memory in which the data is written, and the second type log including a logical address corresponding to data copied during a garbage collection, a new physical address indicating a storage location in the non-volatile memory in which the copied data is written, and an old physical address indicating a storage location in the non-volatile memory from which the copied data is read;
• in response to power to the memory system being restored after the memory system is shutdown, read from the first block, N pieces of address translation information last written into the first block and N update logs last written into the first block, and reconstruct the first table area of the logical-to-physical address translation table in the volatile memory from the N pieces of address translation information read from the first block and the N update logs read from the first block;
• and
• when reconstructing the first table area,
• determine whether the second type log is included in the N update logs, and
• acquire a physical address corresponding to a logical address included in the second type log from the first table area of the logical-to-physical address translation table in the volatile memory when the second type log is included in the N update logs, to reflect content of the second type log in the first table area of the logical-to-physical address translation table in the volatile memory such that the new physical address included in the second type log is associated with the logical address included in the second type log when the old physical address included in the second type log matches the acquired physical address, and to not reflect the content of the second type log in the first table area of the logical-to-physical address translation table in the volatile memory when the old physical address included in the second type log does not match the acquired physical address.