BLOCK STORAGE BY DECOUPLING ORDERING FROM DURABILITY

• US 20150220439A1
• Filed: 03/28/2014
• Published: 08/06/2015
• Est. Priority Date: 02/04/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: MICKENS, James W., PHANISHAYEE, Amar, VELAYUDHAN PILLAI, Vijaychidambaram
• Granted Patent: US 9,798,631 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

This document relates to data storage techniques. One example can buffer write commands and cause the write commands to be committed to storage in flush epoch order. Another example can maintain a persistent log of write commands that are arranged in the persistent log in flush epoch order. Both examples may provide a prefix consistent state in the event of a crash.

Claims

1. A method performed by a computing device, the method comprising:

receiving multiple logical write commands comprising write data for writing to one or more physical storage devices;

receiving a flush command to flush the write data to the one or more physical storage devices, the multiple write commands being within a flush epoch defined by the flush command;

acknowledging the flush command; and

issuing corresponding device write commands to send the write data to the one or more physical storage devices, wherein at least some of the corresponding device write commands are issued after the flush command is acknowledged.

2. The method of claim 1, wherein the write data is committed to the one or more physical storage devices in a different order than the multiple logical write commands are received.

3. The method of claim 1, further comprising:

ensuring that the write data for each of the multiple logical write commands has been committed to the one or more physical storage devices prior to issuing any subsequent device write commands for a subsequent flush epoch.

4. The method of claim 3, further comprising:

upon determining that the write data for each of the corresponding device write commands has successfully committed, issuing the subsequent device write commands for the subsequent flush epoch.

5. The method of claim 1, further comprising:

issuing at least some of the corresponding device write commands in a different temporal order than the logical write commands are received.

6. The method of claim 1, wherein the one or more physical storage devices comprise multiple different physical storage devices.

7. The method of claim 6, further comprising:

maintaining a write buffer of the write data as the write data is issued to the multiple different physical storage devices via the corresponding device write commands; and

removing the write data from the write buffer as the multiple different physical storage devices confirm that the write data has been successfully persisted.

8. A system comprising:

one or more physical storage devices;

one or more hardware processing resources; and

computer-readable instructions that, when executed by the hardware processing resources, cause the hardware processing resources to;

receive multiple logical write commands having corresponding write data;

receive multiple flush commands, the flush commands defining corresponding flush epochs; and

issue the write data to a persistent log on the one or more physical storage devices via corresponding device write commands, wherein the write data is arranged on the persistent log in flush epoch order.

9. The system of claim 8, wherein the computer-readable instructions cause the one or more hardware processing resources to:

issue the write data to the one or more physical storage devices as expanded blocks of data having recovery information included therein.

10. The system of claim 9, wherein the computer-readable instructions cause the one or more hardware processing resources to:

periodically write checkpoint data to the one or more physical storage devices and use the checkpoint data and the recovery information of the expanded blocks to recover to a consistent prefix.

11. The system of claim 9, wherein the recovery information of the expanded blocks includes virtual block identifiers, epoch numbers, and error correction codes.

12. The system of claim 8, wherein the computer-readable instructions cause the one or more hardware processing resources to:

return from an individual flush command defining an individual flush epoch before at least some write data of the individual flush epoch is acknowledged as having been persisted by the one or more physical storage devices.

13. The system of claim 8, wherein the corresponding device write commands issue the write data to consecutive locations of the persistent log or to permuted locations of the persistent log.

14. The system of claim 13, wherein two consecutive locations of the persistent log are located on different physical storage devices.

15. A method performed by a computing device, the method comprising:

upon restarting after a crash, accessing a persistent log of write data, wherein the write data is arranged in the persistent log in flush epoch order; and

rolling forward through the persistent log while inspecting consistency data in the persistent log until the consistency data indicates that at least one consistency criteria cannot be met.

16. The method of claim 15, wherein the at least one consistency criteria provides for prefix consistency of the persistent log.

17. The method of claim 15, wherein the consistency data identifies flush epochs.

18. The method of claim 15, further comprising:

identifying a stopping condition indicating that the consistency criteria cannot be met; and

responsive to identifying the stopping condition, ceasing the rolling forward.

19. The method of claim 18, further comprising:

prior to identifying the stopping condition, recovering at least some of the write data in the persistent log by updating one or more data structures that map virtual block identifiers to corresponding locations of the at least some write data that is recovered.

20. The method of claim 19, further comprising:

retrieving checkpoint data identifying a checkpoint block where the rolling forward begins and a corresponding checkpoint epoch; and

rolling forward through a subsequent flush epoch after the checkpoint epoch and recovering all writes from the subsequent flush epoch.