Patent Description:
Machine Creation Services ("MCSs") is a component of a virtual desktop platform that can be used to design and deliver virtual desktop images. Using Application Programming Interfaces ("APIs") from an underlying hypervisor, MCSs configure, start, stop and delete Virtual Machines ("VMs"). The MCSs use copies of a master VM to provision virtual desktops. The clones include an differencing hard disk, an identity hard disk and a personal virtual disk. The MCSs have an I/O optimization feature that uses disk caching to offload temporary write operations to shared storage for VMs.

A disk cache is a mechanism for improving the time it takes to read from and write to a hard disk. The disk cache can be part of the hard disk or a portion of a Random Access Memory ("RAM") that is reserved for use by the hard disk. During operation, a program running on a computing device may need access to new data. In this case, an Operating System ("OS") first checks to see if the new data is stored in the disk cache. If so, the new data is retrieved from the disk cache. If not, the OS performs operations to read the new data from the hard disk. Disk caching improves the computing device's overall performance since data can be accessed much faster from the disk cache as opposed to the hard disk.

A TRIM command ("TRIM") allows the OS to inform a Solid State Drive ("SSD") which blocks of data are no longer considered in use and can be erased. TRIM processing improves performance of the SSD. The SSD may organize data into pages which are grouped together in blocks. Data can be read and written at the page level but can only be erased at the block level. For a deletion operation, the OS sends a TRIM command to the SSD for marking given pages for deletion. Notably, the pages are not actually erased from memory at this time. For a write operation, the pages marked for deletion are grouped into a block and erased to make room for the new data to be written to the SSD. <CIT> provides apparatuses, systems, methods, and computer program products for interrupting storage operations. <CIT> describes memory access requests in hybrid memory system. <CIT> provides a memory scheduling method and method of operating a memory system. <CIT> describes memory systems having improved out-of-order execution of commands and methods for operating the same.

The present disclosure concerns implementing systems and methods for handling operation requests in a computing device. The methods comprise: queuing at least one first I/O operation (e.g., a read operation or a write operation) and a first TRIM operation for a plurality of block portions of a disk cache in a first list of operations to be performed by the computing device; analyzing the first TRIM operation to determine a size thereof; estimating a first amount of time to complete the first TRIM operation; and comparing the first amount of time to a first threshold value. If the first amount of time is less than the first threshold value, then the first I/O operation is performed followed by the first TRIM operation. In contrast, if the first amount of time is greater than the first threshold value, then the first TRIM operation is selectively divided into at least a second TRIM operation for first block portions contained in the plurality of block portions of the disk cache and at least a third TRIM operation for second block portions contained in the plurality of block portions of the disc cache. Thereafter, the first I/O operation is performed followed by the second TRIM operation, and the third TRIM operation is queued in a second list of operations to be performed by the computing device. Notably, an estimated amount of time to complete the second TRIM operation is less than the first threshold value.

In some scenarios, the methods further comprise: queuing at least one second I/O operation in the first list; 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 third TRIM operation; and determining if the third amount of time is less than the second threshold value. If the third amount of time is less than the second threshold value, the second I/O operation is performed followed by the third TRIM operation.

If the second I/O operation comprises a write operation for writing data to the first block portions, then the data is written to other block portions of the disc cache that are not contained in the first and second block portions. If the second I/O operation comprises a read operation for reading data in the second block portion, then an empty data set is returned. If the second I/O operation comprises a read operation for reading data in the second block portion, then the data is read (a) from the disk 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 disk cache to the hard disk.

The present solution will be described with reference to the following drawing figures, in which like numerals represent like items throughout the figures.

The present solution may be embodied in other specific forms. The described embodiments are to be considered in all respects only as illustrative. The scope of the present solution is indicated by the appended claims rather than by this detailed description.

Furthermore, the described features, advantages and characteristics of the present solution may be combined in any suitable manner in one or more embodiments. One skilled in the relevant art will recognize, in light of the description herein, that the present solution can be practiced without one or more of the specific features or advantages of a particular embodiment. In other instances, additional features and advantages may be recognized in certain embodiments that may not be present in all embodiments of the present solution.

Reference throughout this specification to "one embodiment", "an embodiment", or similar language means that a particular feature, structure, or characteristic described in connection with the indicated embodiment is included in at least one embodiment of the present solution.

The present solution generally concerns implementing systems and methods for dynamic TRIM processing with disk caching to provide a consistent system I/O response. The word "TRIM" is used here in relation to the present solution in a general sense. A TRIM operation includes, but is not limited to, ATA TRIM operations, SCSI UNMAP operations and/or other similar operations. TRIM processing on Solid State Drives ("SSDs") can be queued to improve performance. However, the Data Set Range ("DSR") can be quite large which reduces overall system responsiveness. Dynamically adjusting the TRIM processing with disk caching provides a consistent system I/O response. This dynamic adjustment of TRIM processing distinguishes from existing solutions by not only queuing TRIM commands but also breaking the TRIM commands into chunks to maintain a system I/O response. Also, disk caching using system memory handles new read and write operations to dynamically trimmed blocks. The system I/O response is measured to help manage the amount of outstanding dynamically trimmed blocks.

Referring now to <FIG>, there is provided an illustration of an exemplary computing device <NUM>. Computing device <NUM> may include more or less components than those shown in <FIG>. However, the components shown are sufficient to disclose an illustrative embodiment implementing the present solution. The hardware architecture of <FIG> represents one illustration of a representative computing device implementing a dynamic TRIM processing with disk caching to provide a consistent system I/O response. As such, the computing device <NUM> of <FIG> implements at least a portion of each method described herein.

Some or all components of the computing device <NUM> can be implemented as hardware, software and/or a combination of hardware and software. The hardware includes, but is not limited to, one or more electronic circuits. The electronic circuits can include, but are not limited to, passive components (e.g., resistors and capacitors) and/or active components (e.g., amplifiers and/or microprocessors). The passive and/or active components can be adapted to, arranged to and/or programmed to perform one or more of the methodologies, procedures, or functions described herein.

As shown in <FIG>, the computing device <NUM> comprises a user interface <NUM>, a CPU <NUM>, a system bus <NUM>, a memory <NUM> connected to and accessible by other portions of computing device <NUM> through system bus <NUM>, and hardware entities <NUM> connected to system bus <NUM>. The user interface can include input devices and output devices, which facilitate user-software interactions for controlling operations of the computing device <NUM>. The input devices include, but are not limited, a physical and/or touch keyboard <NUM>. The output devices include, but are not limited to, a speaker <NUM>, a display <NUM>, and/or light emitting diodes <NUM>.

At least some of the hardware entities <NUM> perform actions involving access to and use of memory <NUM>. Memory <NUM> includes, but is not limited to, a RAM <NUM>, a hard disk <NUM>, a disk cache <NUM>, and/or a Compact Disc Read Only Memory ("CD-ROM") (not shown in <FIG>).

Hardware entities <NUM> can include a disk drive unit <NUM> comprising a computer-readable storage medium <NUM> on which is stored one or more sets of instructions <NUM> (e.g., software code) configured to implement one or more of the methodologies, procedures, or functions described herein. The instructions <NUM> can also reside, completely or at least partially, within the memory <NUM> and/or within the CPU <NUM> during execution thereof by the computing device <NUM>. The memory <NUM> and the CPU <NUM> also can constitute machine-readable media. The term "machine-readable media", as used here, refers to a single medium or multiple media (e.g., a centralized or distributed database, and/or associated caches and servers) that store the one or more sets of instructions <NUM>. The term "machine-readable media", as used here, also refers to any medium that is capable of storing, encoding or carrying a set of instructions <NUM> for execution by the computing device <NUM> and that cause the computing device <NUM> to perform any one or more of the methodologies of the present disclosure.

In some scenarios, the hardware entities <NUM> include an electronic circuit (e.g., a processor) programmed for facilitating TRIM processing. In this regard, it should be understood that the electronic circuit can access and run software applications <NUM> installed on the computing device <NUM>. One software application <NUM> is generally operative to facilitate the provision of dynamic TRIM processing with disk caching. The functions of the software application <NUM> will become apparent as the discussion progresses.

Notably, the disk cache <NUM> is used to queue read operations, write operations, and TRIM operations. The TRIM operations may take longer to process as compared to the read and write operations. Depending on the DSRs and estimated times to process the TRIM operations, the ranges are dynamically trimmed where some blocks from the ranges are trimmed (i.e., erased to make room for new data to be stored in memory) while others are left pending for additional processing.

Referring now to <FIG>, illustrations are provided which are useful for understanding a conventional operation queuing process. As operation requests are received by a CPU, they are queued in a list <NUM> within a disc cache <NUM>. The operations are performed in the order specified by the list <NUM>. For example, a first write operation <NUM><NUM> is first performed to write data to block portions <NUM>,. , N of the disk cache <NUM>. Next, a first read operation <NUM><NUM> is performed to read the data stored in block portions <NUM>,. , N from the disk cache <NUM>. Then, a second write operation <NUM><NUM> is performed to write data to block portions N+<NUM>,. , M of the disk cache <NUM>, followed by a second read operation <NUM><NUM>. Subsequently, a third write operation <NUM><NUM> is performed to write data to block portions M+<NUM>,. , Y of the disk cache <NUM>, followed by a third read operation <NUM><NUM>. Upon completing the third read operation <NUM><NUM>, a TRIM operation <NUM> is performed in which block portions <NUM>,. , Y of the disk cache <NUM> are marked for deletion, as shown by <FIG>.

At some later time, a fourth read operation <NUM><NUM> is performed to read data that was previously stored in block portions <NUM>,. , N of the disc cache <NUM>. Since this data is marked for deletion, the data is read from the hard disk if it was flushed thereto rather than from the disc cache <NUM> during the fourth read operation <NUM><NUM>. Next, a fourth write operation <NUM><NUM> is performed in which (a) data block portions N+<NUM>,. , N are erased and (b) new data is written to block portions N+<NUM>,. , N of the disk cache <NUM>, as shown by <FIG>.

Despite the advantages of the above operation queuing process, it suffers from certain drawbacks. For example, the TRIM operation <NUM> takes a relatively long amount of time to complete, and therefore adversely affects overall system responsiveness to I/O operation requests. Therefore, an improved operation queuing process is needed in which the overall system responsiveness to I/O operation requests is improved. The present solution provides such an improved operation queuing process.

Referring now to <FIG>, there is provided a flow diagram of an illustrative method <NUM> for handling operation requests in accordance with the present solution. Method <NUM> begins with <NUM> and continues with <NUM> where requests for first I/O operations are received at a processing unit (e.g., CPU <NUM> of <FIG>). The first I/O operations include, but are not limited, to read operations and/or write operations. The first I/O operations are queued in a first list contained in a data cache (e.g., disc cache <NUM> of <FIG>).

An illustration of an illustrative first list <NUM> of queued operations is provided in <FIG>. The queued operations include write operations <NUM><NUM>, <NUM><NUM>, <NUM><NUM> and read operations <NUM><NUM>, <NUM><NUM>, <NUM><NUM>. In <FIG>, the write and read operations are shown in an alternating order (i.e., each write operation is followed by a read operation). The present solution is not limited in this regard. The read operations and/or write operations can be in any order. Also, the number of read operations can be the same as or different than the number of write operations.

In <NUM>, the processing unit receives a request for a first TRIM operation for a plurality of block portions in the disc cache. The first TRIM operation is queued in the first list following the first I/O operations. For example, as shown in <FIG>, the first TRIM operation <NUM> is queued in list <NUM> after the read operation <NUM><NUM>.

In <NUM>, the first I/O operations are performed. For example, as shown in <FIG>, data is written to block portions <NUM>,. , N of the data cache <NUM> in accordance with write operation <NUM><NUM>. This data is then read from the data cache <NUM> in accordance with the read operation <NUM><NUM>. Similarly, data is written to block portions N+<NUM>,. , M of the data cache <NUM> in accordance with write operation <NUM><NUM>. This data is then read from the data cache <NUM> in accordance with the read operation <NUM><NUM>. Likewise, data is written to block portions M+<NUM>,. , Y of the data cache <NUM> in accordance with write operation <NUM><NUM>. This data is then read from the data cache <NUM> in accordance with the read operation <NUM><NUM>.

Once <NUM> is completed, the processing unit performs trimming related tasks in <NUM>-<NUM>. The trimming related tasks involve: analyzing a first TRIM operation (e.g., TRIM operation <NUM> of <FIG>) to determine a size thereof; estimating a first amount of time to complete the first TRIM operation; and determining if the estimated first amount of time is less than a first threshold value. The first threshold value can be a pre-defined value. If the estimated first amount of time is less than the first threshold value [<NUM>:YES], the first TRIM operation is performed as shown by <NUM>. Upon completing the first TRIM operation, method <NUM> returns to <NUM>.

In contrast, if the estimated first amount of time is greater than the first threshold value [<NUM>:NO], then <NUM> is performed where the first TRIM operation is divided into at least a second TRIM operation for first block portions contained in the plurality of block portions and a third TRIM operation for second block portions contained in the plurality of block portions. First and second block portions are of the same or different size, and contain different ones of the block portions comprising the plurality. Notably, an estimated amount of time to complete at least the second TRIM operation is less than the first threshold value. Accordingly, the second TRIM operation is performed in <NUM> since there will not be a significant impact on the system's responsiveness to I/O requests. For example, as shown in <FIG>, only the data in block portions <NUM>,. , N are marked for deletion in accordance with a second TRIM operation <NUM>. The data in block portions N+<NUM>,. , Y are not marked for deletion at this time as such operation would cause an undesirable effect on the system's responsiveness to I/O requests. Accordingly, <NUM> also involves queueing the third TRIM operation in a second list of queued operations. An illustration of an illustrative second list <NUM> is provided in <FIG>. As shown in <FIG>, a third TRIM operation <NUM> is queued in the list <NUM>. After completing <NUM>, method <NUM> continues with <NUM> of <FIG>.

As shown in <FIG>, <NUM> involves receiving requests for second and third I/O operations, and queueing the same in the first list contained in the data cache. <FIG> shows the first list <NUM> having second I/O operations <NUM><NUM>, <NUM><NUM>, <NUM> and third I/O operations <NUM><NUM>, <NUM><NUM> queued therein. In <NUM>, an estimate is determined for a second amount of time to complete each second I/O operation. A value of a second threshold is set in <NUM> based on the estimated second amount of time(s). For example, the second threshold value is set to be equal to the estimated second amount of time or is set to be equal to the smallest or largest estimated second amount of time. Next in <NUM>, an estimate is determined for a third amount of time to complete the third TRIM operation (e.g., third TRIM operation <NUM> of <FIG>). If the estimated third amount of time is less than the second threshold value [<NUM>:YES], then method <NUM> continues with <NUM> where the second I/O operations are performed followed by the third TRIM operation. After completing the third TRIM operations, method <NUM> returns to <NUM>.

In contrast if the estimated third amount of time is greater than the second threshold value [<NUM>:NO], then method <NUM> continues with <NUM> where the second I/O operations are performed. If the second I/O operation is a read operation (e.g., read operation <NUM><NUM> of <FIG>) for the first block portion (i.e., data in block portions of the disk cache that are marked for deletion), then the data is read (a) from the disk cache if it has not yet been erased therefrom or (b) from a memory or the hard disk depending on whether it has been flushed out of the disk cache to the hard disk. If the second I/O operation is a write operation for the first block portions (write operation <NUM><NUM> of <FIG>), then it is redirected to other available block portions of the disc cache (e.g., block portions Y+<NUM>,. , X of <FIG>). If the second I/O operation is a read operation e.g., read operation <NUM> of <FIG>) from the second block portion (i.e., a block portion which has yet to be trimmed in accordance with the third TRIM operation), then an empty data set is returned.

Upon completing the second I/O operations, <NUM> is performed where an estimate is determined for a third amount of time to complete each of the third I/O operations (e.g., third I/O operations <NUM><NUM>, <NUM><NUM> of <FIG>). A value of a third threshold is set based on the estimated third amount of times(s). If the estimated third amount of time is less than the third threshold value [<NUM>:YES], then the third I/O operations are performed followed by the third TRIM operation, as shown by <NUM>. Upon completing the third TRIM operations, method <NUM> returns to <NUM>. <FIG> comprise illustrations useful for understanding operations of <NUM>. In contrast, if the estimated third amount of time is greater than the third threshold value [<NUM>:NO], then <NUM> is performed where method <NUM> ends or other processing is performed (e.g., return to <NUM>).

As should be understood, the present solution is not limited to the particulars of method <NUM>. For example, some of the operations of <NUM>-<NUM> can be performed concurrently and/or in a different order than that shown in <FIG>. Accordingly, method <NUM> can be modified in accordance with a particular application.

The present solution can be employed in various applications, in addition to those discussed above. For example, the dynamic TRIM processing of the present solution can be applied to non-temporary data systems where the writes are written to the system disk. However, in this case, as the cache fills up, writes are more frequently to the system disk as compared to the temporary cache disk case, leaving more space to smooth out any large TRIM operations. The trimmed blocks and any non-committed write blocks will eventually have to be passed through to the system disk to maintain integrity. So, there may be a slower system shutdown. However, deferring the larger operations helps maintain system responsiveness while users are actively using the system. Also, in this case, one must be careful with write to areas that have overlapping trimmed areas. SSDs cannot simply overwrite existing data, so any valid data in that area that need to be overwritten needs to be copied before the old blocks can be erased. In those cases, the overlapping trimmed areas are sent to the system disk to prevent old invalid data from being copied around.

Claim 1:
A method for handling operation requests in a computing device (<NUM>), comprising:
queuing at least one first Input/Output, I/O, operation and a first TRIM operation in a first list of operations (<NUM>) to be performed by the computing device (<NUM>);
analyzing the first TRIM operation (<NUM>) for a plurality of block portions to determine a size thereof;
estimating a first amount of time to complete the first TRIM operation (<NUM>);
comparing the first amount of time to a first threshold value;
selectively dividing the first TRIM operation (<NUM>) into at least a second TRIM operation (<NUM>) for first block portions contained in the plurality of block portions of a disk cache (<NUM>) and at least a third TRIM operation (<NUM>) for second block portions contained in the plurality of block portions of the disk cache (<NUM>), if the first amount of time is greater than the first threshold value;
performing the at least one first I/O operation followed by the second TRIM operation;
queuing the third TRIM operation in a second list of operations (<NUM>) to be performed by the computing device (<NUM>);
queuing at least one second I/O operation in the first list (<NUM>);
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 third TRIM operation (<NUM>);
determining if the third amount of time is less than the second threshold value; and
performing the second I/O operation followed by the third TRIM operation (<NUM>) if the third amount of time is less than the second threshold value.