Aggregation of Write Traffic to a Data Store

• US 20120102265A1
• Filed: 01/05/2012
• Published: 04/26/2012
• Est. Priority Date: 09/19/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cong, Shi, Brender, Scott, Mehra, Karan, Moss, Darren G., Tipton, William R., Verma, Surendra
• Granted Patent: US 9,448,890 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• 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 machine-implemented method for sequentially aggregating a data set in a write log in a flash-based storage, the machine-implemented method comprising:

determining whether the data set is suitable for the sequential aggregating in the write log in the flash-based storage;

sequentially writing the data set to the write log in the flash-based storage, instead of writing to an intended destination of a random access medium, when the data set is determined to be suitable for the sequential aggregating, the random access medium being the flash-based storage, a second flash-based storage, or a disk;

maintaining a remapping tree for mapping entries in the write log to logical block addresses in a volume of the random access medium;

draining entries of the write log to respective intended destinations of the random access medium upon detection of any one of a plurality of conditions, the plurality of conditions including;

a disabling of the write log;

an absence of input/output activity with respect to the random access medium and the write log being more than a first predetermined amount full;

the write log being at least a second predetermined amount full regardless of the input/output activity with respect to the random access medium, the second predetermined amount being larger than the first predetermined amount; and

the remapping tree being larger than a third predetermined size.

2. The machine-implemented method of claim 1, wherein the determining of whether the data set is suitable for the sequential aggregating in the write log further comprises:

determining whether the data set is less than a predetermined size, and

determining that the data set is suitable for the sequential aggregating in the write log when the data set is determined to be less than the predetermined size.

3. The machine-implemented method of claim 1, further comprising:

writing a respective full checkpoint or a respective incremental checkpoint to the write log at certain times, each of the respective full checkpoints or each of the respective incremental checkpoints including information describing contents of the write log.

4. The machine-implemented method of claim 1, further comprising:

recovering the write log after a dirty shutdown, the recovering further comprising;

determining whether at least one checkpoint is included in the write log, each of the at least one checkpoint including information describing contents of the write log,

finding a last checkpoint in the write log when the at least one checkpoint is determined to be included in the write log,

rebuilding the remapping tree based, at least partly, on the last checkpoint,

reading from an entry of the write log, corresponding to a first entry of the write log not having corresponding information included in any checkpoint, until no additional valid entries of the write log are found,

updating the remapping tree when a valid entry of the write log is found, and

setting an end log sequence number of the write log based on a last found valid entry of the write log.

5. The machine-implemented method of claim 4, wherein when the determining of whether at least one checkpoint is included in the write log determines that no checkpoint is included in the write log, the recovering of the write log further comprises:

reading the write log, beginning from a start of the write log, until no additional valid entries of the write log are found, and

updating the remapping tree based on found valid entries of the write log.

6. The machine-implemented method of claim 1, further comprising:

writing an invalidation record to at least one entry of the write log indicating that the at least one entry of the write log is invalid, wherein

invalidated entries of the write log are not drained to respective intended destinations on the random access medium.

7. The machine-implemented method of claim 1, wherein the random access medium is the flash-based storage.

8. A system for sequentially aggregating a data set in a write log residing on a flash-based storage, the system comprising:

at least one processor; and

a memory connected to the at least one processor and including instructions for the at least one processor, when the at least one processor executes the instructions the at least one processor performs a method comprising;

determining whether a data set is suitable for sequentially writing to the write log in the flash-based storage when a size of the data set is less than a predetermined size,

sequentially writing the data set to the write log, instead of writing to an intended destination on a random access medium, when the data set is determined to be suitable for the sequential writing, the random access medium being the flash-based storage, a second flash-based storage, or a disk;

maintaining a remapping tree for mapping between entries in the write log and logical block addresses in the random access medium, and

draining entries of the write log to respective intended destinations on the random access medium when an absence of input/output activity with respect to the random access medium is detected and the write log is at least a predetermined amount full.

9. The system of claim 8, wherein the method further comprises:

writing an invalidation record to the write log indicating that logical block addresses of the flash-based storage are invalid for one or more entries of the write log.

10. The system of claim 9, wherein the method further comprises:

draining only non-invalidated ones of the entries of the write log to the respective intended destinations on the random access medium.

11. The system of claim 8, wherein the remapping tree is an avl tree.

12. The system of claim 8, wherein the method further comprises:

writing a respective full checkpoint or a respective incremental checkpoint to the write log at time intervals, each one of respective full checkpoints or the respective incremental checkpoints including information describing contents of the write log at a time the one of the respective full checkpoints or the respective incremental checkpoints was written.

13. The system of claim 8, wherein the method further comprises:

determining, after a dirty shutdown, whether at least one checkpoint is included in the write log,

finding a last checkpoint in the write log when at least one checkpoint is determined to be included in the write log,

rebuilding the remapping tree based, at least partly, on the last checkpoint,

reading from an entry of the write log, corresponding to a first entry of the write log not having information included in any checkpoint, until no additional valid entries of the write log are found, and

updating the remapping tree after a valid entry of the write log is found.

14. A machine-readable storage medium having instructions recorded thereon for at least one processor, the instructions comprising:

instructions for determining whether data intended to be written to a random access medium is suitable for being sequentially written to a write log included within a volume of a flash-based storage device, the random access medium being the flash-based storage device, a second flash-based storage device, or a disk;

instructions for sequentially writing the data to the write log when the data is determined to be suitable for being sequentially written to the write log;

instructions for maintaining a remapping tree for mapping between entries in the write log and logical block addresses of the random access medium; and

instructions for draining entries of the write log to respective intended destinations on the random access medium upon detection of at least one of a plurality of conditions, the plurality of conditions comprising, as one of the plurality of conditions, the remapping tree being larger than a predetermined size.

15. The machine-readable storage medium of claim 14, wherein the plurality of conditions further comprise:

a disabling of the write log,

an absence of input/output activity with respect to the random access medium and the write log being more than a second predetermined amount full, and

the write log being at least a third predetermined amount full regardless of the input/output activity with respect to the random access medium, the third predetermined amount being larger than the second predetermined amount.

16. The machine-readable storage medium of claim 14, wherein the instructions further comprise:

instructions for writing a checkpoint to the write log, contents of the checkpoint describing contents of the write log.

17. The machine-readable storage medium of claim 16, wherein the instructions further comprise:

instructions for recovering the remapping tree, after a shutdown, based, at least partially, on the checkpoint.

18. The machine-readable storage medium of claim 17, wherein the instructions for recovering the remapping tree further comprise:

instructions for reading the write log, starting from an entry of the write log corresponding to a first entry of the write log not having corresponding information included in the checkpoint, for a next valid entry of the write log, and

instructions for updating the remapping tree based on the next valid entry of the write log.

19. The machine-readable storage medium of claim 14, wherein the instructions further comprise:

instructions for writing an invalidation record to the write log indicating that logical block addresses of the flash-based storage device, corresponding to at least one entry of the write log, are invalid, and

instructions for not draining, to intended destinations on the random access medium, invalidated entries of the write log.

20. The machine-readable storage medium of claim 14, further comprising:

instructions for determining whether the data intended to be written to the random access medium is included in a stream; and

instructions for determining that the data is not suitable to be written to the write log when the data is determined to be in the stream.