Use of application data and garbage-collected data to improve write efficiency of a data storage device

• US 9,436,595 B1
• Filed: 03/15/2013
• Issued: 09/06/2016
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Benitez, Manuel Enrique, Shah, Monish
• Primary Examiner(s): Rojas, Midys
• Assistant Examiner(s): Wei, Jane
• Application Number:
  US13/840,838
• Time in Patent Office: 1,271 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control

Abstract

A data storage device includes a plurality of flash memory devices. A memory controller is configured to receive a request from a host computing device to write a first logical block of application data to the data storage device, write the first logical block to a data buffer, wherein a size of the data buffer is larger than the logical block and may store multiple logical blocks, write one or more logical blocks of garbage-collected data to the data buffer, and write the logical blocks in the data buffer to the data storage device when the data buffer becomes full. The data buffer written to the data storage device includes at least one logical block of application data and at least one logical block of garbage-collected data. In an alternative implementation, garbage-collected data may be written to the data buffer upon expiration of a timer.

Claims

1. A method comprising:

receiving, by a memory controller, a request from a host computing device to write a first logical block of application data to a data storage device;

writing, by the memory controller, the first logical block to a data buffer, wherein a size of the data buffer is a same size as a page that can be written to the data storage device and is larger than the logical block;

starting a timer in response to writing the first logical block to the data buffer;

receiving, by the memory controller, one or more additional requests from the host computing device to write one or more additional logical blocks of application data to the data storage device;

prior to an expiration of the timer, determining that the data buffer is not full;

detecting the expiration of the timer;

writing, by the memory controller, in response to detecting the expiration of the timer and determining that the data buffer is not full, one or more logical blocks of garbage-collected data to the data buffer to fill the data buffer, wherein the garbage-collected data comprises at least one valid logical block of an erase unit of the data storage device that has been selected for garbage collection; and

writing the full data buffer to the data storage device.

2. The method of claim 1 wherein the data buffer includes a plurality of logical blocks and wherein the full data buffer includes at least one logical block of the application data and at least one logical block of garbage-collected data.

3. The method of claim 1 and further comprising:

tracking, by a garbage collection control engine, a number of valid and invalid logical blocks in each of a plurality of erase units of the data storage device; and

selecting one of the erase units for garbage collection based on a number of valid logical blocks and a number of invalid logical blocks within the selected erase unit.

4. The method of claim 1 and further comprising:

determining a number of free erase units within the data storage device;

determining that the number of free erase units is less than a threshold; and

increasing a portion of the data buffer that is reserved for the garbage-collected data based on the determining that the number of free erase units is less than a threshold.

5. The method of claim 1 and further comprising:

determining a number of free erase units within the data storage device;

determining that the number of free erase units is greater than a threshold; and

decreasing a portion of the data buffer that is reserved for the garbage-collected data based on the determining that the number of free erase units is greater than a threshold.

6. The method of claim 1 and further comprising:

determining a number of write requests for application data;

determining that the number of write requests is greater than a threshold; and

decreasing a portion of the data buffer that is reserved for the garbage-collected data based on the determining that the number of write requests is greater than a threshold.

7. The method of claim 1 wherein the receiving comprises receiving, by a memory controller, a request from an application running on a host computing device to write a first logical block of application data to a data storage device;

wherein the timer is associated with the application;

wherein the starting comprises starting the timer associated with the application in response to the writing, by the memory controller, the first logical block of data from the application to a data buffer associated with the timer.

8. The method of claim 1 and further comprising:

adjusting an initial value of the timer as write requests for application data from the host computing device change or a number of free erase units change in order to vary a likely amount of garbage-collected data that will be written to the data buffer.

9. A data storage device, comprising:

a plurality of flash memory devices, each of the flash memory devices being arranged into a plurality of erase units having a plurality of logical blocks for storing data; and

a memory controller operationally coupled with the flash memory devices, the memory controller being configured to;

receive a request from a host computing device to write a first logical block of application data to the data storage device;

write the first logical block to a data buffer, wherein a size of the data buffer is a same size as a page that can be written to the data storage device and is larger than the logical block;

start a timer in response to writing the first logical block to the data buffer;

receive one or more additional requests from the host computing device to write one or more additional logical blocks of application data to the data storage device;

prior to an expiration of the timer, determine that the data buffer is not full;

detect the expiration of the timer;

write, in response to detecting the expiration of the timer and determining that the data buffer is not full, one or more logical blocks of garbage-collected data to the data buffer, wherein the garbage-collected data comprises at least one valid logical block of an erase unit of the data storage device that has been selected for garbage collection; and

write the data buffer to the data storage device.

10. The data storage device of claim 9 wherein the data buffer includes a plurality of logical blocks and wherein the data buffer includes at least one logical block of the application data and at least one logical block of garbage-collected data.

11. The data storage device of claim 9 wherein the memory controller is further configured to:

track a number of valid and invalid logical blocks in each of a plurality of erase units of the data storage device; and

select one of the erase units for garbage collection based on a number of valid logical blocks and a number of invalid logical blocks within the selected erase unit.

12. The data storage device of claim 9 wherein the memory controller is further configured to:

determine a number of free erase units within the data storage device;

determine that the number of free erase units is less than a threshold; and

increase a portion of the data buffer that is reserved for the garbage-collected data based on the determining that the number of free erase units is less than a threshold.

13. The data storage device of claim 9 wherein the memory controller is further configured to:

determine a number of free erase units within the data storage device;

determine that the number of free erase units is greater than a threshold; and

decrease a portion of the data buffer that is reserved for the garbage-collected data based on the determining that the number of free erase units is greater than a threshold.

14. The data storage device of claim 9 wherein the memory controller is further configured to:

determine a number of write requests for application data;

determine that the number of write requests is greater than a threshold; and

decrease a portion of the data buffer that is reserved for the garbage-collected data based on the determining that the number of write requests is greater than a threshold.

15. The data storage device of claim 9 wherein the memory controller being configured to receive comprises the memory controller being configured to receive a request from an application running on a host computing device to write a first logical block of application data to a data storage device;

wherein the memory controller being configured to start comprises the memory controller being configured to start the timer associated with the application in response to the writing the first logical block of data from the application to the data buffer associated with the timer.

16. The data storage device of claim 9 wherein the data buffer that is written to the data storage device comprises a full data buffer that includes at least one logical block of application data and at least one logical block of garbage-collected data.

17. A non-transitory computer-readable storage medium storing instructions that when executed cause a processor to perform a process, the process comprising:

receiving a request from a host computing device to write a first logical block of application data to a data storage device;

writing the first logical block to a data buffer, wherein a size of the data buffer is a same size as a page that can be written to the data storage device and is larger than the logical block;

starting a timer in response to writing the first logical block to the data buffer;

receiving one or more additional requests from the host computing device to write one or more additional logical blocks of application data to the data storage device;

prior to an expiration of the timer, determining that the data buffer is not full;

detecting the expiration of the;

writing, in response to detecting the expiration of the timer and determining that the data buffer is not full, one or more logical blocks of garbage-collected data to the data buffer, wherein the garbage-collected data comprises at least one valid logical block of an erase unit of the data storage device that has been selected for garbage collection; and

writing the data buffer to the data storage device.

18. The computer-readable storage medium of claim 17 wherein the data buffer that is written to the data storage device comprises a full data buffer that includes at least one logical block of application data and at least one logical block of garbage-collected data.

19. The computer-readable storage medium of claim 17 wherein the data buffer includes a plurality of logical blocks and wherein the data buffer that is written to the data storage device is full and includes at least one logical block of the application data and at least one logical block of garbage-collected data.

20. The computer-readable storage medium of claim 17 wherein the process further comprises:

tracking a number of valid and invalid logical blocks in each of a plurality of erase units of the data storage device; and

selecting one of the erase units for garbage collection based on a number of valid logical blocks and a number of invalid logical blocks within the selected erase unit.

21. The computer-readable storage medium of claim 17 wherein the process further comprises:

determining a number of free erase units within the data storage device;

determining that the number of free erase units is less than a threshold; and

increasing a portion of the data buffer that is reserved for the garbage-collected data based on the determining that the number of free erase units is less than a threshold.

22. A data storage device, comprising:

a plurality of flash memory devices, each of the flash memory devices being arranged into a plurality of erase units having a plurality of logical blocks for storing data; and

a memory controller operationally coupled with the flash memory devices, the memory controller being configured to;

receive a request from a host computing device to write a first logical block of application data to the data storage device;

write the first logical block to a data buffer, wherein a size of the data buffer is larger than the logical block and may store multiple logical blocks;

start a timer when the first logical block is written to the data buffer;

write one or more logical blocks of garbage-collected data to the data buffer, wherein the garbage-collected data comprises at least one valid logical block of an erase unit of the data storage device that has been selected for garbage collection;

prior to an expiration of the timer, determine that the data buffer is not full;

detect the expiration of the timer;

in response to detecting the expiration of the timer and determining that the data buffer is not full, write one or more additional logical blocks of garbage-collected data to the data buffer to fill the data buffer; and

write the full data buffer to the data storage device.

23. The data storage device of claim 22, wherein at least a portion of the data buffer is reserved for garbage-collected data.

24. The data storage device of claim 23 wherein the portion of the data buffer that is reserved for garbage collection is variable based on a number of free erase units in the data storage device.

25. The data storage device of claim 22, wherein at least a portion of the data buffer is reserved for application or host data.

26. The data storage device of claim 22, wherein:

at least a first portion of the data buffer is reserved for garbage-collected data;

at least a second portion of the data buffer is reserved for application data; and

wherein the sizes of the first portion and the second portion are adjusted based on a number of free erase units in the data storage device.

27. A method comprising:

receiving a request by a memory controller from a host computing device to write a first logical block of application data to the data storage device;

writing the first logical block to a data buffer, wherein a size of the data buffer is larger than the logical block and may store multiple logical blocks;

starting a timer when the first logical block is written to the data buffer;

writing one or more logical blocks of garbage-collected data to the data buffer, wherein the garbage-collected data comprises at least one valid logical block of an erase unit of the data storage device that has been selected for garbage collection;

prior to an expiration of the timer, detecting that the data buffer is not full;

detecting the expiration of the timer;

in response to detecting the expiration of the timer and detecting that the data buffer is not full, writing one or more additional logical blocks of garbage-collected data to the data buffer to fill the data buffer; and

writing the full data buffer to the data storage device.