Coalescing metadata and data writes via write serialization with device-level address remapping

• US 10,289,340 B2
• Filed: 02/08/2017
• Issued: 05/14/2019
• Est. Priority Date: 02/23/2016
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: O'Krafka, Brian W., George, Johann, Bolkhovitin, Vladislav, Krishnan, Manavalan, Firsov, Evgeniy
• Primary Examiner(s): Warren, Tracy A
• Application Number:
  US15/428,086
• Publication Number:
  US 20170242626A1
• Time in Patent Office: 825 Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/466 Metadata, control data
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
• CPC Class Codes: G06F 2212/7208 Multiple device management, e.g. distributing data over multiple flash devices
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

Systems, methods and/or devices are used to coalesce metadata and data writes via write serialization with device-level address remapping. In one aspect, a method of managing a storage system having one or more storage devices includes a serialized write operation to the storage system, in which a serialization segment accumulates data objects and mapping information until the segment is full, at which time the serialization segment is written to the storage system in a single contiguous write. As a result, the number of I/O operations is decreased from a minimum of two (one to write data and one to write updated mapping information) to a single write operation. Further, if the serialization segment contains existing valid data prior to accumulating data objects and mapping information, the valid data is moved to the beginning of the serialization segment using either a remap or xcopy operation.

Claims

1. A method of managing a storage system having a plurality of storage devices, the method comprising:

detecting a request to perform a write operation for a data object to the storage system, wherein the write operation includes a first write of updated mapping information to a tiered data structure, the tiered data structure used to translate a key associated with the data object to a physical location of the data object in the storage system, and a second write of data to be written for the data object;

creating a serialization segment in a memory, distinct from the plurality of storage devices, wherein creating the serialization segment includes;

coalescing valid data in the serialization segment, including;

for each contiguous sequence of valid logical addresses in the serialization segment, sending instructions from a host system to one or more storage devices of the plurality of storage devices to move data corresponding to the respective contiguous sequence of valid logical addresses; and

repacking valid logical addresses in the serialization segment to a beginning of the serialization segment;

accumulating, in the serialization segment, the first write of updated mapping information to the tiered data structure and the second write of the data to be written; and

writing, in a single contiguous write, contents of the serialization segment, other than the coalesced valid data, to one or more storage devices of the plurality of storage devices of the storage system.

2. The method of claim 1, wherein the instructions to move data comprise remap instructions that change logical addresses in the serialization segment associated with memory portions in the plurality of storage devices from initial logical addresses to new logical addresses in the serialization segment, without causing physical movement of data.

3. The method of claim 1, wherein the instructions to move data comprise copy instructions that copy data corresponding to valid logical addresses in the serialization segment from initial memory portions in the plurality of storage devices to different memory portions in the plurality of storage devices corresponding to new logical addresses in the serialization segment.

4. The method of claim 1, further comprising identifying the serialization segment, from among a plurality of serialization segments, in accordance with one or more predefined characteristics of the data to be written.

5. The method of claim 4, wherein:

the serialization segment corresponds to a selected stripe of a plurality of stripes of logical address space; and

identifying the serialization segment includes identifying the serialization segment in accordance with selection criteria.

6. The method of claim 5, wherein each stripe of the plurality of stripes of logical address space corresponds to one or more erase blocks in the plurality of storage devices.

7. The method of claim 5, wherein each stripe of the plurality of stripes of logical address space corresponds to a RAID stripe.

8. The method of claim 1, wherein the coalescing valid data is performed during garbage collection.

9. The method of claim 1, wherein the first write and the second write are accumulated in the serialization segment after the coalesced valid data.

10. The method of claim 1, wherein the memory is a non-volatile random-access memory (NVRAM).

11. The method of claim 1, wherein writing the contents of the serialization segment to one or more storage devices of the plurality of storage devices of the storage system is performed in accordance with a determination that the serialization segment is full.

12. The method of claim 1, wherein:

writing the contents of the serialization segment to one or more storage devices of the plurality of storage devices of the storage system is performed in accordance with a batch commit algorithm; and

one or more writes accumulated in the serialization segment within a predefined time period are written in the single contiguous write.

13. The method of claim 1, wherein the method is controlled by the host system that includes a client on behalf of which data is stored in the storage system.

14. A host system, comprising:

an interface for operatively coupling to a storage system having a plurality of storage devices;

one or more processors; and

controller memory storing one or more programs, which when executed by the one or more processors cause the host system to perform operations comprising;

detecting a request to perform a write operation for a data object to the storage system, wherein the write operation includes a first write of updated mapping information to a tiered data structure, the tiered data structure used to translate a key associated with the data object to a physical location of the data object in the storage system, and a second write of data to be written for the data object;

creating a serialization segment in a memory, distinct from the plurality of storage devices, wherein creating the serialization segment includes;

coalescing valid data in the serialization segment, including;

for each contiguous sequence of valid logical addresses in the serialization segment, sending instructions from the host system to one or more storage devices of the plurality of storage devices to move data corresponding to the respective contiguous sequence of valid logical addresses; and

repacking valid logical addresses in the serialization segment to a beginning of the serialization segment;

accumulating, in the serialization segment, the first write of updated mapping information to the tiered data structure and the second write of the data to be written; and

writing, in a single contiguous write, contents of the serialization segment, other than the coalesced valid data, to one or more storage devices of the plurality of storage devices of the storage system.

15. The host system of claim 14, wherein the one or more programs include:

a coalescing module configured to coalesce valid data in the serialization segment, including sending instructions to the one or more storage devices of the plurality of storage devices to move valid data, and repacking valid logical addresses in the serialization segment; and

a serialization module configured to serialize data and updated mapping information in the serialization segment.

16. A storage system, comprising:

a plurality of storage devices;

one or more subsystems having one or more processors,

the one or more processors including;

means for detecting a request to perform a write operation for a data object to the storage system, wherein the write operation includes a first write of updated mapping information to a tiered data structure, the tiered data structure used to translate a key associated with the data object to a physical location of the data object in the storage system, and a second write of data to be written for the data object;

means for creating a serialization segment in a memory, distinct from the plurality of storage devices, wherein the means for creating the serialization segment includes;

means for coalescing valid data in the serialization segment, including;

for each contiguous sequence of valid logical addresses in the serialization segment, means for sending instructions from a host system to one or more storage devices of the plurality of storage devices to move data corresponding to the respective contiguous sequence of valid logical addresses; and

means for repacking valid logical addresses in the serialization segment to a beginning of the serialization segment;

means for accumulating, in the serialization segment, the first write of updated mapping information to the tiered data structure and the second write of the data to be written; and

means for writing, in a single contiguous write, contents of the serialization segment, other than the coalesced valid data, to one or more storage devices of the plurality of storage devices of the storage system.

17. The storage system of claim 16, wherein the instructions to move data comprise remap instructions that change logical addresses in the serialization segment associated with memory portions in the plurality of storage devices from initial logical addresses to new logical addresses in the serialization segment, without causing physical movement of data.

18. The storage system of claim 16, wherein the instructions to move data comprise copy instructions that copy data corresponding to valid logical addresses in the serialization segment from initial memory portions in the plurality of storage devices to different memory portions in the plurality of storage devices corresponding to new logical addresses in the serialization segment.

19. The storage system of claim 16, wherein:

the serialization segment corresponds to a selected stripe of a plurality of stripes of logical address space; and

the one or more programs include instructions for identifying the serialization segment in accordance with one or more predefined characteristics of the data to be written.

20. A non-transitory computer readable storage medium, storing one or more programs configured for execution by one or more processors of a storage system, the one or more programs including instructions that when executed by the one or more processors cause the storage system to perform a set of operations comprising:

detecting a request to perform a write operation for a data object to the storage system, wherein the write operation includes a first write of updated mapping information to a tiered data structure, the tiered data structure used to translate a key associated with the data object to a physical location of the data object in the storage system, and a second write of data to be written for the data object;

creating a serialization segment in a memory, distinct from the plurality of storage devices, wherein creating the serialization segment includes;

coalescing valid data in the serialization segment, including;

for each contiguous sequence of valid logical addresses in the serialization segment, sending instructions from the host system to one or more storage devices of the plurality of storage devices to move data corresponding to the respective contiguous sequence of valid logical addresses; and

repacking valid logical addresses in the serialization segment to a beginning of the serialization segment;

accumulating, in the serialization segment, the first write of updated mapping information to the tiered data structure and the second write of the data to be written; and

writing, in a single contiguous write, contents of the serialization segment, other than the coalesced valid data, to one or more storage devices of the plurality of storage devices of the storage system.