Memory system and method for controlling nonvolatile memory
According to one embodiment, a memory system manages a plurality of management tables corresponding to a plurality of first blocks in a nonvolatile memory. Each management table includes a plurality of reference counts corresponding to a plurality of data in a corresponding first block. The memory system copies a set of data included in a copy-source block for garbage collection and corresponding respectively to reference counts belonging to a first reference count range to a first copy-destination block, and copies a set of data included in the copy-source block and corresponding respectively to reference counts belonging to a second reference count range having a lower limit higher than an upper limit of the first reference count range to a second copy-destination block.
1. A method of controlling a nonvolatile memory, the nonvolatile memory including a plurality of blocks, said method comprising:
managing, per physical address of a location in the nonvolatile memory in which data have been stored, the number of logical addresses associated with the physical address; and
performing garbage collection by:
copying first data from a first physical address in a copy-source block to a first block and not copying second data from a second physical address in the copy-source block to the first block; and
copying the second data from the second physical address in the copy-source block to a second block and not copying the first data from the first physical address in the copy-source block to the second block, wherein
the number of logical addresses associated with the first physical address belongs to a first range, and
the number of logical addresses associated with the second physical address belongs to a second range different from the first range.
2. The method of claim 1 , wherein,
when the first data is data having a lifetime longer than a lifetime of the second data, the first range is greater than the second range.
3. The method of claim 1 , further comprising:
when writing update data of third data already stored in the nonvolatile memory, decrementing the number of logical addresses associated with a physical address of a location in which the third data is stored by one.
4. The method of claim 1 , further comprising:
when writing third data to the nonvolatile memory, the third data not matching with any data stored in the nonvolatile memory,
writing the third data to the nonvolatile memory;
updating a first translation table managing a corresponding relationship between logical addresses and intermediate addresses to associate a first intermediate address with a logical address of the third data;
updating a second translation table managing a corresponding relationship between the intermediate addresses and physical addresses of locations in the nonvolatile memory to associate a third physical address with the first intermediate address, the third physical address indicating a location in the nonvolatile memory in which the third data is written; and
setting the number of logical addresses associated with the third physical address to one.
5. The method of claim 1 , further comprising:
in a case where third data matches with fourth data already stored in the nonvolatile memory, without writing the third data to the nonvolatile memory,
updating a first translation table managing a corresponding relationship between logical addresses and intermediate addresses to associate a first intermediate address with a logical address of the third data, the first intermediate address having been associated with a logical address of the fourth data;
maintaining a second translation table managing a corresponding relationship between the intermediate addresses and physical addresses of locations in the nonvolatile memory such that a third physical address is associated with the first intermediate address, the third physical address indicating a location in the nonvolatile memory in which the fourth data is stored; and
incrementing the number of logical addresses associated with the third physical address by one.
6. The method of claim 1 , further comprising:
in the garbage collection, not copying third data from a third physical address in the copy-source block to any block, wherein
the number of logical addresses associated with the third physical address is zero.
7. The method of claim 1 , further comprising:
selecting, as the copy-source block, a third block in preference to a fourth block, wherein
a maximum of the numbers of logical addresses respectively associated with physical addresses of locations in the third block is greater than a maximum of the numbers of logical addresses respectively associated with physical addresses of locations in the fourth block.
8. The method of claim 7 , further comprising:
selecting the third block as the copy-source block in a case where an amount of invalid data in the third block is larger than a first threshold; and
selecting the fourth block as the copy-source block in a case where an amount of invalid data in the third block is larger than a second threshold, wherein
the first threshold is smaller than the second threshold.
9. A method of controlling a nonvolatile memory, the nonvolatile memory including a plurality of blocks, said method comprising:
managing, per physical address of a location in the nonvolatile memory in which data have been stored, the number of logical addresses associated with the physical address; and
performing garbage collection by selecting first data in preference to second data as copy target data for the garbage collection, wherein
the first data is stored at a first physical address,
the number of logical addresses associated with the first physical address belongs to a first range,
the second data is stored at a second physical address,
the number of logical addresses associated with the second physical address belongs to a second range, and
the first range is greater than the second range.
10. The method of claim 9 , wherein
the first data is data having a lifetime longer than a lifetime of the second data.
11. The method of claim 9 , further comprising:
when writing update data of third data already stored in the nonvolatile memory, decrementing the number of logical addresses associated with a physical address of a location in which the third data is stored by one.
12. The method of claim 9 , further comprising:
when writing third data to the nonvolatile memory, the third data not matching with any data stored in the nonvolatile memory,
writing the third data to the nonvolatile memory;
updating a first translation table managing a corresponding relationship between logical addresses and intermediate addresses to associate a first intermediate address with a logical address of the third data;
updating a second translation table managing a corresponding relationship between the intermediate addresses and physical addresses of locations in the nonvolatile memory to associate a third physical address with the first intermediate address, the third physical address indicating a location in the nonvolatile memory in which the third data is written; and
setting the number of logical addresses associated with the third physical address to one.
13. The method of claim 9 , further comprising:
in a case where third data matches with fourth data already stored in the nonvolatile memory, without writing the third data to the nonvolatile memory,
updating a first translation table managing a corresponding relationship between logical addresses and intermediate addresses to associate a first intermediate address with a logical address of the third data, the first intermediate address having been associated with a logical address of the fourth data;
maintaining a second translation table managing a corresponding relationship between the intermediate addresses and physical addresses of locations in the nonvolatile memory such that a third physical address is associated with the first intermediate address, the third physical address indicating a location in the nonvolatile memory in which the fourth data is stored; and
incrementing the number of logical addresses associated with the third physical address by one.
14. The method of claim 9 , further comprising:
in the garbage collection, not copying third data from a third physical address in the copy-source block to any block, wherein
the number of logical addresses associated with the third physical address is zero.
15. A method of controlling a nonvolatile memory, the nonvolatile memory including a plurality of blocks, said method comprising:
managing, per physical address of a location in the nonvolatile memory in which data have been stored, the number of logical addresses associated with the physical address; and
when executing garbage collection, copying data from a copy-source physical address to a copy-destination physical address, and associating the number of logical addresses that has been associated with the copy-source physical address with the copy-destination physical address.
16. The method of claim 15 , further comprising:
when writing update data of first data already stored in the nonvolatile memory, decrementing the number of logical addresses associated with a physical address of a location in which the first data is stored by one.
17. The method of claim 15 , further comprising:
when writing first data to the nonvolatile memory, the first data not matching with any data stored in the nonvolatile memory,
writing the first data to the nonvolatile memory;
updating a first translation table managing a corresponding relationship between logical addresses and intermediate addresses to associate a first intermediate address with a logical address of the first data;
updating a second translation table managing a corresponding relationship between the intermediate addresses and physical addresses of locations in the nonvolatile memory to associate a first physical address with the first intermediate address, the first physical address indicating a location in the nonvolatile memory in which the first data is written; and
setting the number of logical addresses associated with the first physical address to one.
18. The method of claim 15 , further comprising:
in a case where first data matches with second data already stored in the nonvolatile memory, without writing the first data to the nonvolatile memory,
updating a first translation table managing a corresponding relationship between logical addresses and intermediate addresses to associate a first intermediate address with a logical address of the first data, the first intermediate address having been associated with a logical address of the second data;
maintaining a second translation table managing a corresponding relationship between the intermediate addresses and physical addresses of locations in the nonvolatile memory such that a first physical address is associated with the first intermediate address, the first physical address indicating a location in the nonvolatile memory in which the second data is stored; and
incrementing the number of logical addresses associated with the first physical address by one.
19. The method of claim 15 , further comprising:
in the garbage collection, not copying first data from a first physical address to any location in the nonvolatile memory, wherein
the number of logical addresses associated with the first physical address is zero.
20. The method of claim 15 , further comprising:
selecting, as a copy-source block for the garbage collection, a first block in preference to a second block, wherein
a maximum of the numbers of logical addresses respectively associated with physical addresses of locations in the first block is greater than a maximum of the numbers of logical addresses respectively associated with physical addresses of locations in the second block.