Aggregation of write traffic to a data store

• US 9,448,890 B2
• Filed: 01/05/2012
• Issued: 09/20/2016
• Est. Priority Date: 09/19/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Cong, Shi, Brender, Scott, Mehra, Karan, Moss, Darren G., Tipton, William R., Verma, Surendra
• Primary Examiner(s): Wong, Leslie
• Application Number:
  US13/343,985
• Publication Number:
  US 20120102265A1
• Time in Patent Office: 1,720 Days
• Field of Search: 707/823, 707/824, 707/999.107, 707/999.205, 711/104, 711/112
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 12/0638 Combination of memories, e.g. ROM and RAM such as to permit replacement or supplementing of words in one module by words in another module address formation of the next microinstruction G06F9/26; masking faults in memories by using spares or by reconfiguring G11C29/70
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 2212/205 Hybrid memory, e.g. using both volatile and non-volatile memory
• CPC Class Codes: G06F 2212/221 Static RAM
• CPC Class Codes: G06F 2212/2228 Battery-backed RAM
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G11C 7/1006 Data managing, e.g. manipulating data before writing or reading out, data bus switches or control circuits therefor

Abstract

A method and a processing device are provided for sequentially aggregating data to a write log included in a volume of a random-access medium. When data of a received write request is determined to be suitable for sequentially aggregating to a write log, the data may be written to the write log and a remapping tree, for mapping originally intended destinations on the random-access medium to one or more corresponding entries in the write log, may be maintained and updated. At time periods, a checkpoint may be written to the write log. The checkpoint may include information describing entries of the write log. One or more of the checkpoints may be used to recover the write log, at least partially, after a dirty shutdown. Entries of the write log may be drained to respective originally intended destinations upon an occurrence of one of a number of conditions.

Claims

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

receiving, by the computing device, a request to write data to an intended destination on a random access storage device;

determining, by the computing device based on monitoring storage device offsets of read and write requests comprising the request to write the data, whether or not patterns of the read and write requests are sequential;

writing, by the computing device in response to the patterns of the read and write requests being sequential or in response to a write log status indicating invalidation only, the data to at least one intended destination in the random access storage device, where the write log status indicating invalidation only indicates that only invalidation records can be written to the write log;

redirecting, by the computing device in response to the patterns of the read and write requests not being sequential and in response to the write log status not indicating invalidation only, the data to the write log; and

mapping, by the computing device in response to the redirecting, the redirected data to the at least one intended destination.

2. The method of claim 1, where the patterns of the read and write requests being determined to not be sequential indicate that the data is suitable for being redirected to the write log.

3. The method of claim 1, where the patterns of the read and write requests being determined to be sequential indicate that the data is part of a stream.

4. The method of claim 1, where the data is redirected to the write log further in response to the data being less than a predetermined size.

5. The method of claim 1, where the data is written to the at least one intended destination in the random access storage device further in response to the data being greater than a predetermined size.

6. The method of claim 1, where the data is redirected instead of being written to the at least one intended destination.

7. The method of claim 1, where the random access storage device comprises flash-based storage or a disk.

8. A system comprising:

a computing device that includes at least one processor and memory storing instructions; and

the instructions that, based on execution by the at least one processor, configure the computing device to;

receive a request to write data to an intended destination on a random access storage device;

determine, based on monitoring storage device offsets of read and write requests comprising the request to write the data, whether or not patterns of the read and write requests are sequential;

write, in response to the patterns of the read and write requests being sequential or in response to a write log status indicating invalidation only, the data to at least one intended destination in the random access storage device, where the write log status indicating invalidation only indicates that only invalidation records can be written to the write log;

redirect, in response to the patterns of the read and write requests not being sequential and in response to the write log status not indicating invalidation only, the data to the write log; and

map, in response to the redirecting, the redirected data to the at least one intended destination.

9. The system of claim 8, where the patterns of the read and write requests being determined to not be sequential indicate that the data is suitable for being redirected to the write log.

10. The system of claim 8, where the patterns of the read and write requests being determined to be sequential indicate that the data is part of a stream.

11. The system of claim 8, where the data is redirected to the write log further in response to the data being less than a predetermined size.

12. The system of claim 8, where the data is written to the at least one intended destination in the random access storage device further in response to the data being greater than a predetermined size.

13. The system of claim 8, where the data is redirected instead of being written to the at least one intended destination.

14. A machine-readable storage medium comprising:

memory that comprises instructions that, based on execution by at least one processor of a computing device, configure the computing device to perform actions comprising;

receiving a request to write data to an intended destination on a random access storage device;

determining, based on monitoring storage device offsets of read and write requests comprising the request to write the data, whether or not patterns of the read and write requests are sequential with respect to the intended destination;

writing, in response to the patterns of the read and write requests being sequential or in response to a write log status indicating invalidation only, the data to at least one intended destination in the random access storage device, where the write log status indicating invalidation only indicates that only invalidation records can be written to the write log;

redirecting, in response to the patterns of the read and write requests not being sequential and in response to the write log status not indicating invalidation only, the data to the write log, where an invalidation-only status of the write log indicates that only invalidation records can be written to the write log; and

mapping, in response to the redirecting, the redirected data to the at least one intended destination.

15. The machine-readable storage medium of claim 14, where the patterns of the read and write requests being determined to not be sequential indicate that the data is suitable for being redirected to the write log.

16. The machine-readable storage medium of claim 14, where the patterns of the read and write requests being determined to be sequential indicate that the data is part of a stream.

17. The machine-readable storage medium of claim 14, where the data is redirected to the write log further in response to that the data being less than a predetermined size.

18. The machine-readable storage medium of claim 14, where the data is written to the at least one intended destination in the random access storage device further in response to the data being greater than a predetermined size.

19. The machine-readable storage medium of claim 14, where the data is redirected instead of being written to the at least one intended destination.

20. The machine-readable storage medium of claim 14, where the random access storage device comprises flash-based storage or a disk.