Mapping table for improving write operation efficiency
View Patent ↗A non-volatile storage system is disclosed which provides a mapping table which includes a granularity which does not correspond to the page size of a non-volatile storage array. A reduced mapping table granularity enables more than one mapping entry to exist in a single page on the solid-state array. A write command which does not exceed a mapping table entry can invalidate only a portion of the written page, and can be combined with a second write command to write a new page of the solid-state array.
1. A method for reducing write amplification in a data storage system, the method comprising:
maintaining a mapping table for a non-volatile solid-state storage array comprising a plurality of memory pages, the mapping table comprising a plurality of entries, each entry in the mapping table providing a one-to-one mapping between one of a plurality of logical addresses and one of a plurality of physical addresses corresponding to one of a plurality of partial memory pages of the plurality of memory pages;
receiving a first write command from a host system, the first write command designating a first logical address of the plurality of logical addresses and first write data;
when a size of the first write data is smaller than a memory page size of the plurality of memory pages, waiting for a period of time to receive a second write command from the host system, the second write command designating a second logical address of the plurality of logical addresses and second write data;
when the second write command is received from the host system within the period of time and the combined size of the first write data and the second write data is smaller than or equal to the memory page size, issuing a write command to a destination memory page of the plurality of memory pages for the first and the second write commands, the destination memory page comprising a first partial memory page of the plurality of partial memory pages and a second partial memory page of the plurality of partial memory pages;
updating entries of the mapping table to reflect writing of the first and second write data by:
updating a first mapping entry for the first logical address with a first physical address of the plurality of physical addresses corresponding to the first partial memory page thereby invalidating data stored in a third partial memory page of the plurality of partial memory pages, and
updating a second mapping entry for the second logical address with a second physical address of the plurality of physical addresses corresponding to the second partial memory page thereby invalidating data stored in a fourth partial memory page of the plurality of partial memory pages; and
executing the issued write command on the storage array;
wherein the method is performed under control of a controller of the data storage system, and
wherein updating the entries of the mapping table is performed so that at least some memory pages of the plurality of memory pages each store partially-valid data and partially-invalid data.
2. The method for reducing write amplification of claim 1 , wherein the combined size of the first write data and the second write data is equal to the memory page size.
3. The method for reducing write amplification of claim 1 , wherein the first write data comprises 4 kilobytes (KB) of write data.
4. The method for reducing write amplification of claim 1 , wherein the memory page size is 8 KB.
5. The method for reducing write amplification of claim 1 , wherein the size of each of the first and second partial memory pages matches a logical chunk size of 4 KB.
6. The method for reducing write amplification of claim 1 , wherein the size of each of the first and second partial memory pages matches a write data size used by the host system.
7. A data storage system, comprising:
a non-volatile solid-state storage array comprising a plurality of memory pages; and
a controller configured to:
maintain a mapping table for the storage array, the mapping table comprising a plurality of entries, each entry in the mapping table providing a one-to-one mapping between one of a plurality of logical addresses and one of a plurality of physical addresses corresponding to one of a plurality of partial memory pages of the plurality of memory pages,
receive a first write command from a host system, the first write command designating a first logical address of the plurality of logical addresses and first write data,
when a size of the first write data is smaller than a memory page size of the plurality of memory pages, waiting for a period of time to receive a second write command from the host system, the second write command designating a second logical address of the plurality of logical addresses and second write data,
when the second write command is received from the host system within the period of time and the combined size of the first write data and the second write data is smaller than or equal to the memory page size, issue a write command to a destination memory page of the plurality of memory pages for the first and the second write commands, the destination memory page comprising a first partial memory page of the plurality of partial memory pages and a second partial memory page of the plurality of partial memory pages,
update entries of the mapping table to reflect writing of the first and second write data by:
updating a first mapping entry for the first logical address with a first physical address of the plurality of physical addresses corresponding to the first partial memory page thereby invalidating data stored in a third partial memory page of the plurality of partial memory pages, and
updating a second mapping entry for the second logical address with a second physical address of the plurality of physical addresses corresponding to the second partial memory page thereby invalidating data stored in a fourth partial memory page of the plurality of partial memory pages, and
execute the issued write command on the storage array,
wherein the controller is further configured to update the entries of the mapping table so that at least some memory pages of the plurality of memory pages each store partially-valid data and partially-invalid data.
8. The data storage system of claim 7 , wherein the first write data comprises 4 KB of write data.
9. The data storage system of claim 7 , wherein each memory page of the at least some memory pages comprises a portion storing the partially-valid data which corresponds to one logical address of the plurality of logical addresses and a portion storing the partially-invalid data which does not correspond to one logical address of the plurality of logical addresses.
10. The data storage system of claim 7 , wherein the controller is further configured to perform garbage collection operations which combine partially-valid data from different memory pages of the plurality of memory pages into a single memory page of the plurality of memory pages.
11. The method for reducing write amplification of claim 1 , wherein the third partial memory page stores a prior version of data corresponding to the first logical address, and the fourth partial memory page stores a prior version of data corresponding to the second logical address.
12. The data storage system of claim 7 , wherein the third partial memory page stores a prior version of data corresponding to the first logical address, and the fourth partial memory page stores a prior version of data corresponding to the second logical address.
13. The method for reducing write amplification of claim 1 , wherein said updating the entries of the mapping table further comprises updating the entries of the mapping table to reflect writing of the first and second write data so that another partial memory page of the same memory page of the plurality of memory pages as the third partial memory page continues to store valid data which corresponds to one logical address of the plurality of logical addresses.
14. The method for reducing write amplification of claim 1 , wherein when the second write command is not received from the host system within the period of time, issuing the write command to the destination memory page for the first write command and not the second write command.
15. The data storage system of claim 7 , wherein the controller is further configured to update the entries of the mapping table to reflect writing of the first and second write data so that another partial memory page of the same memory page of the plurality of memory pages as the third partial memory page continues to store valid data which corresponds to one logical address of the plurality of logical addresses.
16. The data storage system of claim 7 , wherein when the second write command is not received from the host system within the period of time, the controller is further configured to issue the write command to the destination memory page for the first write command and not the second write command.