Block storage by decoupling ordering from durability

• US 10,114,709 B2
• Filed: 10/19/2016
• Issued: 10/30/2018
• Est. Priority Date: 02/04/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Mickens, James W., Phanishayee, Amar, Velayudhan Pillai, Vijaychidambaram
• Primary Examiner(s): Bansal, Gurtej
• Application Number:
  US15/298,091
• Publication Number:
  US 20170039114A1
• Time in Patent Office: 741 Days
• 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 comprising:

receiving multiple write commands having corresponding write data;

receiving multiple flush commands, the multiple flush commands defining corresponding flush epochs;

issuing the write data to a persistent log on a physical storage device with consistency data;

acknowledging an individual flush command that defines an individual flush epoch before confirming that at least some write data for the individual flush epoch has committed on the physical storage device; and

after a crash, recovering the write data on the physical storage device to a consistent state using the consistency data.

2. The method of claim 1, the consistent state being a prefix-consistent state.

3. The method of claim 1, the consistency data identifying the flush epochs.

4. The method of claim 1, the persistent log being stored on multiple physical storage devices.

5. The method of claim 1, further comprising:

maintaining mappings of virtual storage locations identified by the write commands to physical storage locations on the physical storage device.

6. The method of claim 5, further comprising:

storing the mappings on the physical storage device and using the mappings to recover a virtual storage device after the crash.

7. A system comprising:

one or more physical storage devices;

one or more hardware processing resources configured via computer-readable instructions which, when executed by the one or more hardware processing resources, cause the one or more hardware processing resources to;

receive multiple write commands having corresponding write data;

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

issue the write data to a persistent log on the one or more physical storage devices with consistency data;

acknowledge an individual flush command that defines an individual flush epoch before receiving confirmation that at least some write data for the individual flush epoch has committed on the one or more physical storage devices; and

after a crash, recover the persistent log to a consistent state using the consistency data.

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

increment a current flush epoch as individual flush commands are received; and

include the current flush epoch in the consistency data issued with the write data to the persistent log.

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

store, in the persistent log, a checkpoint epoch identifying a last-known prefix-consistent flush epoch.

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

store, in the persistent log, a checkpoint block identifying a last-known block in the persistent log for which all previous writes are known to have persisted.

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

store, in the persistent log, validity information indicating whether individual physical blocks of the one or more physical storage devices include valid data.

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

recover the one or more physical storage devices by starting at the checkpoint block and rolling forward through subsequent blocks of the persistent log until a stopping condition is reached.

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

determine that an individual stopping condition occurs in an instance when;

the validity information indicates that a particular block is not valid; and

a current flush epoch from the consistency data of the particular block is less than the checkpoint epoch.

14. The system of claim 13, wherein the computer-readable instructions, when executed by the one or more hardware processing resources, cause the one or more hardware processing resources to:

until at least one stopping condition is reached, recover subsequent blocks from the persistent log.

15. The system of claim 14, wherein the computer-readable instructions, when executed by the one or more hardware processing resources, cause the one or more hardware processing resources to:

as the subsequent blocks are recovered, update the validity information to indicate that the subsequent blocks are valid.

16. A storage resource storing computer-readable instructions which, when executed by one or more hardware processing resources, cause the one or more hardware processing resources to perform acts comprising:

receiving multiple write commands having corresponding write data;

receiving multiple flush commands, the multiple flush commands defining corresponding flush epochs;

issuing the write data to a persistent log on a physical storage device with consistency data;

acknowledging an individual flush command that defines an individual flush epoch before confirming that at least some write data for the individual flush epoch has committed on the physical storage device; and

after a crash, using the write data and the consistency data to recover a virtual storage device to a consistent state.

17. The storage resource of claim 16, the acts further comprising:

issuing respective instances of write data to the persistent log immediately upon receiving respective write commands.

18. The storage resource of claim 16, the consistent state being a prefix-consistent state.

19. The storage resource of claim 16, the acts further comprising:

receiving the individual flush command from client code; and

returning to the client code without blocking after receiving the flush commands.

20. The storage resource of claim 19, the acts further comprising:

responsive to receiving the individual flush command, incrementing a flush epoch counter that identifies a current flush epoch; and

including the flush epoch counter in individual consistency data associated with a plurality of different write commands that are associated with the current flush epoch.