Dynamic delete command partitioning with disk caching

• US 10,635,595 B2
• Filed: 08/27/2018
• Issued: 04/28/2020
• Est. Priority Date: 07/28/2017
• Status: Active Grant

• Current Assignee: Citrix Systems, Inc. (Cloud Software Group)
• Original Assignee: Citrix Systems, Inc. (Cloud Software Group)
• Inventors: Taylor, Alton
• Primary Examiner(s): Cygiel, Gary W.
• Application Number:
  US16/112,849
• Publication Number:
  US 20190034343A1
• Time in Patent Office: 610 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 2212/7204 Capacity control, e.g. partitioning, end-of-life degradation
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control

Abstract

Systems and methods for handling operation requests in a computing device. The methods comprise: queuing a first I/O operation and first TRIM operation in a first list of operations; analyzing the first TRIM operation for a plurality of block portions of a disk cache to determine a size thereof; estimating a first amount of time to complete the first TRIM operation; comparing the first amount of time to a first threshold value; selectively dividing the first TRIM operation into at least a second TRIM operation for first block portions contained in the plurality of block portions and at least a third TRIM operation for second block portions contained in the plurality of block portions, if the first amount of time is greater than the first threshold value; performing the first I/O operation followed by the second TRIM operation; and queuing the third TRIM operation in a second list of operations.

Claims

1. A method for operating a storage device, comprising:

receiving, by a controller in communication with the storage device, requests for a plurality of Input/Output (“

I/O”

) operations and a request for a deletion operation by which one or more blocks of data stored in the storage device are to be marked for erasure;

estimating, by the controller, a first amount of time to complete the deletion operation;

when the first amount of time reaches a first threshold value, performing the following operations;

dividing the deletion operation into a first sub-deletion operation and at least one second sub-deletion operation, each of the first and second sub-deletion operations being associated with a respective subset of the one or more blocks of data stored in the storage device;

performing at least one first I/O operation of the plurality of I/O operations and the first sub-deletion operation;

caching the at least one second sub-deletion operation; and

performing the cached at least one second sub-deletion operation during an otherwise idle time of the storage device.

2. The method according to claim 1, wherein the deletion operation comprising an SCSI UNMAP command.

3. The method according to claim 1, wherein the deletion operation comprises an ATA TRIM command.

4. The method according to claim 1, wherein the deletion operation is generated based upon the requests for a plurality of I/O operations.

5. The method according to claim 1, further comprising queuing at least one second I/O operation.

6. The method according to claim 5, further comprising:

estimating a second amount of time to complete the at least one second I/O operation;

setting a value of a second threshold value based on the second amount of time;

estimating a third amount of time to complete the at least one second sub-deletion operation; and

determining if the third amount of time is less than the second threshold value.

7. The method according to claim 6, further comprising performing the at least one second I/O operation immediately followed by the at least one second sub-deletion operation if the third amount of time is less than the second threshold value.

8. The method according to claim 6, further comprising performing the at least one second I/O operation comprising a write operation for writing data to a first block portion of a cache, where the data is written to other second block portions of the cache that are not contained in the first block portion.

9. The method according to claim 6, further comprising performing the at least one second I/O operation comprising a read operation for reading data in a block portion of a cache, and returning an empty data set.

10. The method according to claim 6, further comprising performing the at least one second I/O operation comprising a read operation for reading data in a block portion of a cache, where the data is read (a) from the cache if it has not yet been erased therefrom or (b) from a memory or hard disk depending on whether the data has been flushed out of the cache to the hard disk.

11. A system, comprising:

a processor; and

a non-transitory computer-readable storage medium comprising programming instructions that are configured to cause the processor to implement a method for operating a storage device, wherein the programming instructions comprise instructions to;

receive requests for a plurality of Input/Output (“

I/O”

) operations and a request for a deletion operation by which one or more blocks of data stored in the storage device are to be marked for erasure;

estimate a first amount of time to complete the deletion operation;

when the first amount of time reaches a first threshold value, performing the following operations;

divide the deletion operation into a first sub-deletion operation and at least one second sub-deletion operation, each of the first and second sub-deletion operations being associated with a respective subset of the one or more blocks of data stored in the storage device;

perform at least one first I/O operation of the plurality of I/O operations and the first sub-deletion operation;

cache the at least one second sub-deletion operation; and

perform the cached at least one second sub-deletion operation during an otherwise idle time of the storage device.

12. The system according to claim 11, wherein the deletion operation comprising an SCSI UNMAP command.

13. The system according to claim 11, wherein the deletion operation comprises an ATA TRIM command.

14. The system according to claim 11, wherein the deletion operation is generated based upon the requests for a plurality of I/O operations.

15. The system according to claim 11, wherein the programming instructions further comprise instructions to queue at least one second I/O operation.

16. The system according to claim 15, wherein the programming instructions further comprise instructions to:

estimate a second amount of time to complete the at least one second I/O operation;

set a value of a second threshold value based on the second amount of time;

estimate a third amount of time to complete the at least one second sub-deletion operation; and

determine if the third amount of time is less than the second threshold value.

17. The system according to claim 16, wherein the programming instructions further comprise instructions to perform the at least one second I/O operation immediately followed by the at least one second sub-deletion operation if the third amount of time is less than the second threshold value.

18. The system according to claim 16, wherein the programming instructions further comprise instructions to perform the at least one second I/O operation comprising a write operation for writing data to a first block portion of a cache, where the data is written to other second block portions of the cache that are not contained in the first block portion.

19. The system according to claim 16, wherein the programming instructions further comprise instructions to perform the at least one second I/O operation comprising a read operation for reading data in a block portion of a cache, and returning an empty data set.

20. The system according to claim 16, wherein the programming instructions further comprise instructions to perform the at least one second I/O operation comprising a read operation for reading data in a block portion of a cache, where the data is read (a) from the cache if it has not yet been erased therefrom or (b) from a memory or hard disk depending on whether the data has been flushed out of the cache to the hard disk.