Write reordering in a hybrid disk drive

Patent metadata

Field	Value
Publication number	US-9747043-B2
Application number	US-201514956280-A
Country	US
Kind code	B2
Filing date	Dec 1, 2015
Priority date	Mar 16, 2012
Publication date	Aug 29, 2017
Grant date	Aug 29, 2017

Abstract

A hybrid drive and associated methods increase the rate at which data are transferred to a nonvolatile storage medium in the hybrid drive. By using a large nonvolatile solid state memory device as cache memory for a magnetic disk drive, a very large number of write commands can be cached and subsequently reordered and executed in an efficient manner. In addition, strategic selection and reordering of only a portion of the write commands stored in the nonvolatile solid state memory device increases efficiency of the reordering process.

First claim

We claim:

1. A data storage device comprising:
a nonvolatile solid state memory device;
a magnetic storage disk; and
a control unit configured to order data blocks to be written to the magnetic storage disk by:
writing the data blocks to the nonvolatile solid state memory device;
selecting N data blocks out of M data blocks stored in the nonvolatile solid state memory device to create a first ordering of data blocks, where N is less than M;
reordering the selected data blocks to create a second ordering having a first data block different than the first data block of the first ordering prior to writing the selected data blocks to the magnetic storage disk; and
writing the first data block of the second ordered data blocks to the magnetic storage disk,
wherein selecting N data blocks comprises selecting the N least-recently-used data blocks from a least-recently-used list of data blocks that are stored in the nonvolatile solid state memory device and have not been written to the magnetic storage disk.

2. The data storage device of claim 1 , wherein the least-recently used list of data blocks comprises a recency list of data blocks written to the nonvolatile solid state memory device, a frequency list of data blocks written to the nonvolatile solid state memory device, or a combination of both.

3. The data storage device of claim 2 , wherein at least one of the recency list and the frequency list comprises a linked list of data blocks in which a data structure is associated with each data block included in the linked list and includes a pointer referencing the next less-recently-used data block in the linked list and a pointer referencing the next more-recently-used data block in the linked list.

4. The data storage device of claim 2 , wherein at least one of the recency list and the frequency list comprises a linked list of data block groups in which a data structure is associated with each data block group included in the linked list and includes a pointer referencing a next less-recently-used data block group in the linked list and a pointer referencing a next more-recently-used data block group in the linked list.

5. The data storage device of claim 4 , wherein a data block group in the linked list consists of a plurality of data blocks in which a least-recently-used data block of the plurality of data blocks has been used more recently than any data block in the next less-recently-used data block group and a most-recently-used data block of the plurality of data blocks has been used less recently than any data block in the next more-recently-used data block group.

6. The data storage device of claim 1 , wherein the control unit is configured to order data blocks to be written to the magnetic storage disk by further performing the steps of:
selecting a second group of N data blocks out of the M data blocks stored in the nonvolatile solid state memory device to create a first ordering of the second group of N data blocks;
reordering the selected second group of N data blocks to create a second ordering of the second group of N data blocks having a first data block different than the first data block of the first ordering of the second group of N data blocks, prior to writing the selected data blocks to the magnetic storage disk; and
writing the first data block of the second ordering of the second group of N data blocks to the magnetic storage disk.

7. The data storage device of claim 1 , wherein the control unit is configured to order data blocks to be written to the magnetic storage disk by further performing the step of: writing the second data block of the second ordered data blocks to the magnetic storage disk.

8. The data storage device of claim 1 , wherein N is substantially less than M or at least an order of magnitude less than M.

9. The data storage device of claim 1 , wherein the control unit is configured to order data blocks to be written to the magnetic storage disk by further performing the step of: periodically writing the least-recently-used data block from the least-recently-used list of data blocks.

10. The data storage device of claim 1 , wherein reordering the selected data blocks further comprises: calculating an access time for each write command associated with a portion of the selected data blocks, wherein the reordering of the selected data blocks is based on the calculated access times.

11. A data storage device comprising:
a nonvolatile solid state memory device;
a magnetic storage disk; and a control unit configured to order data blocks to be written to the magnetic storage disk by:
writing the data blocks to the nonvolatile solid state memory device;
selecting N data blocks out of M data blocks stored in the nonvolatile solid state memory device to create a first ordering of data blocks, where N is less than M;
reordering the selected data blocks to create a second ordering having a first data block different than the first data block of the first ordering prior to writing the selected data blocks to the magnetic storage disk;
writing the first data block of the second ordered data blocks to the magnetic storage disk; and
periodically writing the least-recently-used data block stored in the nonvolatile solid state memory device from a least-recently-used list of data blocks that are stored in the nonvolatile solid state memory device and have not been written to the magnetic storage disk,
wherein selecting N data blocks comprises selecting N data blocks whose logical block addresses are closest to the logical block address of the write command currently being executed.

12. The data storage device of claim 11 , wherein the least-recently used list of data blocks comprises a recency list of data blocks written to the nonvolatile solid state memory device, a frequency list of data blocks written to the nonvolatile solid state memory device, or a combination of both.

13. The data storage device of claim 11 , wherein the control unit is configured to order data blocks to be written to the magnetic storage disk by further performing the steps of:
selecting a second group of N data blocks out of the M data blocks stored in the nonvolatile solid state memory device to create a first ordering of the second group of N data blocks;
reordering the selected second group of N data blocks to create a second ordering of the second group of N data blocks having a first data block different than the first data block of the first ordering of the second group of N data blocks prior to writing the selected data blocks to the magnetic storage disk; and
writing the first data block of the second ordering of the second group of N data blocks to the magnetic storage disk.

14. The data storage device of claim 11 , wherein the control unit is configured to order data blocks to be written to the magnetic storage disk by further performing the step of: writing the second data block of the second ordered data blocks to the magnetic storage disk.

15. The data storage device of claim 11 , wherein N is substantially less than M or at least an order of magnitude less than M.

16. The data storage device of claim 11 , wherein reordering the selected data blocks further comprises: calculating an access time for each write command associated with a portion of the selected data blocks, wherein the reordering of the selected data blocks is based on the calculated access times.

17. A data storage device comprising:
a nonvolatile solid state memory device;
a magnetic storage disk; and a control unit configured to order data blocks to be written to the magnetic storage

Assignees

• Toshiba Kk

Inventors

• Zayas Fernando Anibal
• Ehrlich Richard M
• Dunn Eric R

Classifications

• G11B2020/1294

  Increase of the access speed · CPC title

• G11B20/12

  Formatting, e.g. arrangement of data block or words on the record carriers {(within interface between computers and data recorders G06F3/06)} · CPC title

• G06F2212/1024

  Latency reduction · CPC title

• G06F2212/69

  Physics · mapped topic

• G06F12/0804

  with main memory updating (G06F12/0806 takes precedence) · CPC title