Adaptive, scalable I/O request handling architecture in virtualized computer systems and networks

A system and method for processing input/output (I/O) requests in a virtualized computer system. I/O requests are received from a virtual machine. A set of virtual I/O channels that may be interfaced with a host I/O stack and/or a virtual machine I/O stack adaptively queues requested data using a variety of I/O queue management modules. In one embodiment, the virtual I/O channels include an entropy detection module and a queue storage. The entropy detection module determines an entropy value of specified I/O request data and encodes the specified I/O request data with the entropy value within the queue storage.

BACKGROUND OF THE INVENTION

1. Technical Field

The present invention relates generally to managing I/O resources in a virtualized computer system, and in particular to an I/O request processing architecture implemented in a virtualized computing environment.

2. Description of the Related Art

Logical partitioning of computer resources allows the establishment of multiple system images on a single physical machine or processor complex. Virtualization is a term designating system imaging in which each system image, known also as a virtual machine (VM), operates in a logically independent manner from the other VMs using logically partitioned resources of the physical computer system. In this manner, each logical partition corresponding to a VM can be independently reset, loaded with an operating system that may be different for each VM, and operate with different software programs using different input/output (I/O) devices. Platform virtualization, or simply “virtualization,” is a process or technique that presents a hardware platform to a VM.

Advances in computer system technology relating to high-capacity storage and access applications has resulted in increased platform specialization and performance. Such advances have also lead to a proliferation of specialized systems in high-capacity server implementations such as utilized for data centers. The physical system resources required to support high-capacity data centers are costly in terms of power consumption and other environmental loading, IT management issues such as storage management and physical server management complications. Virtualization addresses these issues by allowing physical platforms to be shared by multiple, disparate, discrete applications. Virtualization of the physical server platform, CPU, memory, and I/O sub-systems has therefore become standard in high-capacity data processing systems.

Sharing of physical system resources often results in over-subscription by the multiple virtualized entities which may contribute to an underutilization of the underlying physical system resources. In particular, virtualization often causes an over-subscription of the I/O sub-systems by the supported VMs, resulting in degraded per-VM and system-wide throughput performance as well as decreased scale-out capability of the host platform in spite of increased host platform physical resource capacity. Symptoms of I/O over-subscription include lower processor utilization by applications with sluggish response time and high latencies. These symptoms are attributable to increased I/O request processing path length which compounds the I/O bottleneck resulting from the shared I/O access architecture of the host system.

In prior systems, I/O over-subscription has been managed through increased concurrency by adding additional physical storage devices and increasing shared accessibility thereto through the use of multi-channel controllers. Additional I/O access improvement measures such as may be employed by Storage-Array-Networking (SAN) systems include increases in storage density, increases in rotational speed of storage devices, and/or increases in I/O channel bandwidth and multiple channels with caching. While these techniques have marginally kept pace with the growing demand for improved VM application performance on physical platforms, platform virtualization introduces several design and performance issues that are presently inadequately addressed by conventional I/O architectures.

It can therefore be appreciated that a need exists for I/O request handling systems and methods that address the issues presented by platform virtualization. The present invention addresses this and other needs unresolved by the prior art.

SUMMARY OF THE INVENTION

A system and method for processing input/output (I/O) requests in a virtualized computer system are disclosed herein. I/O requests are received from a virtual machine. A set of virtual I/O channels that may be interfaced with a host I/O stack and/or a virtual machine I/O stack adaptively queues requested data using a variety of I/O queue management modules. In one embodiment, the virtual I/O channels include an entropy detection module and a queue storage. The entropy detection module determines an entropy value of specified I/O request data and encodes the specified I/O request data with the entropy value within the queue storage.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENT(S)

The systems and methods disclosed herein enable more efficient input/output (I/O) resource allocation within or on behalf of a virtualized computing environment. In one aspect, a set of virtual I/O channels (VIOCs) map views of one or more virtual hard drives (VHDs) into memory. The virtual I/O channels access active portions of VHDs which are mapped into memory using static entitlement allocation policies and/or dynamically adaptive rules disclosed herein. In another aspect, the data comprising the currently in-use mapped view is encoded in a manner enabling bloat-free, lossless compression to further improve physical memory utilization.

In another aspect, the establishment and size of I/O queues within the VIOCs are based on policies designed to minimize I/O access latency. The I/O queues can be sorted by the logically consecutive disk block address of the VHDs, and may be as large as the size of the disk/volume or partition that a VHD resides on. The I/O queues are managed by a sparse global hash table that maps a view of all the logically addressable disk blocks included by the VHD without requiring that all of these blocks reside in main memory. As each block is addressed, a corresponding I/O queue is populated with entropy encoded data blocks that may or may not be compressed.

With reference now to the figures, wherein like reference numerals refer to like and corresponding parts throughout, one embodiment of a virtualized computing environment that may be adapted to implement the virtual I/O management features of the present invention is depicted inFIG. 1A. A virtualized host computer system101is illustrated featuring platform virtualization in the form of multiple virtual machines (VMs)111a-111c. VMs111a-111coperate as logically discrete units, sometimes referred to as “guests” or “guest domains,” that are provided substantially identical execution environments on host system101. Within their respective domains, VMs111a-111cinclude their own guest operating systems113a-113cwhich in some respects define and differentiate the guest domains. The guest domains of VMs111a-111cfurther include respective guest applications117a-117cand guest drivers115a-115cthat are handled and managed privately by each of the respective guest OSs113a-113c.

The logical isolation between VMs111a-111cis provided by a virtualization layer109, which is a part of the host software. Virtualization layer109includes a virtual switching mechanism having isolation and load balancing functions. As depicted and explained in further detail below, the virtual switching mechanism implemented by virtualization layer109may be embodied as a virtual machine monitor (VMM) and host OS, or alternately may be a hypervisor. Examples of virtualization types include VMware ESX server, VMware server, Microsoft Virtual Server, and Xen. Regardless of the particular platform implementation, virtualization architectures such as that depicted inFIG. 1Aprovide execution environments having qualitatively greater isolation between processes than may be achieved when coordinating multiple processes on the same instance of an OS.

The virtualization of host computer system101enables each of multiple users (i.e., VMs) to access a complete and private computer system from a shared set of host drivers107and physical system resources103. Such sharing of host resources has many advantages including increased flexibility in physical resource allocation resulting in greater net physical resource utilization. Another advantage is that VMs111a-111ccan be brought online (e.g. booted or otherwise restarted) much faster and with less system resource utilization than on a dedicated physical machine platform in which many more hardware and software initialization tasks are required for startup.

FIG. 1Bis a block diagram of an exemplary I/O request processing architecture of a virtualized computer system. The depicted I/O request processing architecture includes a host side comprising a host I/O stack151and physical system resources103. A virtual machine monitor (VMM)201and a host OS155provide the virtualization or abstraction layer illustrated as virtualization layer109inFIG. 1between host I/O stack151and a VM131. VMM201can be an application of host OS155, which together with host OS155forms a software abstraction layer between the host system and VM131. Host OS155may be any of a variety of known operating systems suitable for performing a host OS function, such as AIX® or Windows 2003®.

Host I/O stack151processes I/O requests received from VMM201using a specified layered protocol defined by the layers depicted within the stack. The stack layered I/O request processing enables the request to ultimately be handled by hardware within physical system resources103. Host I/O stack151includes host OS155interfacing transport and filesystem filter drivers163, which interface user mode drivers165. Within transport and filesystem filter drivers163, filesystem filter drivers generally maintain the on-disk structures utilized by various filesystems, while transport filter drivers implement specific network protocols required for processing network I/O traffic. The filter drivers163intercept I/O requests passed from host OS155. By intercepting the request before it reaches its intended target, filter drivers163can extend or replace functionality provided by the original target of a given request or otherwise modify the request.

User mode drivers165interface a host kernel167which provides mechanisms for interrupt and exception handling, thread scheduling and synchronization, multiprocessor synchronization, and timekeeping. Kernel167interfaces with a set of kernel mode drivers169, which in turn interface with hardware filter drivers171. Hardware filter drivers171are lower-level device filter drivers that monitor and/or modify I/O requests in accordance with a particular class of physical devices (e.g., hard disk storage) within physical system resources103. These filters are typically utilized to redefine hardware behavior to match expected specifications. Host kernel mode drivers169in conjunction with hardware filter drivers171provide the interface to the hardware within physical system resources103.

Physical system resources103comprise host hardware and associated resources including a central processing unit (CPU)203, memory205, disk drives207, and network interface cards209. CPU203may be a multiprocessor or any other suitable processor design or configuration. Memory205represents data storage generally characterized in the art as “main memory” and associated levels of cache memory, and is typically implemented as a form of random access memory (RAM). Network cards209may incorporate one or more communication interfaces as further described below.

Disk drives207include any suitable type of substantially permanent data storage media such as disks arrays used in large scale storage applications. In virtualized systems as illustrated inFIGS. 1A and 1B, data storage media such as disk drives207provide the persistent storage to maintain the logical and data definitions of each of the resident VMs as file data structures referred to herein as virtual hard drives (VHDs). It should be noted that as represented herein, disk drives207may be representative of various storage embodiments for persistent storing the VHD data from which VMs are generated. Such embodiments include, without particular limitation, direct attached storage such as Small Computer System Interface (SCSI) arrays as well as storage area networks (SANs), which use host bus adapters. Disk drives207may further be representative of network attached storage (NAS) interfaced over a network connection as well as solid state disks or solid state memory systems, Universal Serial Bus (USB) memory sticks or flash drives, or DVD/CD read/write devices.

VMM201is installed as an application of host OS155, and effectively forms a software abstraction layer between the physical host system resources and VM131. VM131comprises a layered I/O processing stack of functions similar to that host I/O stack151. In particular, VM131includes a guest OS133interfacing VM filter drivers135, which interface a VM kernel139, which further interfaces VM kernel mode drivers141. VM kernel mode drivers141further interface virtual hardware143at the bottom of the VM I/O stack.

In a conventional configuration, a file or data I/O request (e.g., read/write/modify) generated by the VM guest OS133is passed to VM filter drivers135, which pass the request to VM kernel mode drivers141via VM kernel139. VM kernel mode drivers141pass the I/O request to the virtual hardware143.

Having been processed through the VM I/O stack, the I/O request is passed down to host I/O stack151via the virtual switching function of VMM201. Host OS155passes the I/O request to transport and filesystem filter drivers163, which pass the request to user mode drivers165and finally to host kernel mode drivers169via host kernel167. Host kernel mode drivers169in conjunction with hardware filter drivers171interface the logically partitioned physical system resources103to service the request. A response to the request, such as the data requested in a read I/O request, is then passed all the way back up, layer by layer, to the originator of the request, such as VM guest OS133. For a data read, for example, data may be read from memory205or disk drives207and returned to host kernel drivers169. The data is passed all the way back up host I/O stack151, layer by layer, to VMM201. VMM201forwards the data to the virtual hardware143, which passes the data through the layers of the VM I/O stack back to guest OS133.

The dual stack request and response path illustrated inFIG. 1Bresults in a significant throughput bottleneck and corresponding performance degradation in conventional virtualized systems. The bottleneck is caused in part by the dual I/O stack processing paradigm of the virtualized system in which CPU203handles interrupt requests at each level of both stacks and also by the additional path length of the object code required to process an I/O request. The bottleneck scales with the number of VMs implemented and active on the host system.

FIG. 2illustrates a virtualized computer system250including components and features for accelerating access to I/O data and otherwise addressing the I/O request bottleneck depicted and explained with reference toFIG. 1B. As shown inFIG. 2, system250comprises VMM201, which in conjunction with a host OS235, forms the virtualization layer between the host system components and a set of VMs131a-131c. The depicted host-side components include a host I/O stack211and physical system resources103described with reference toFIG. 1B. As shown inFIG. 2host I/O stack211includes host OS235, which in turn comprises transport and filesystem filter drivers213, user mode drivers215, a kernel217, kernel mode drivers219, and hardware filter drivers221performing similar interfacing functions as those of the stack layers described with reference toFIG. 1B.

In accordance with conventional I/O processing, an I/O request (e.g., read/write/modify) generated by a VM131is passed to VMM201through a VM I/O processing stack implemented by a guest OS and guest drivers such as in the manner shown inFIG. 1B. Following the VM I/O stack processing of the I/O request, the VM stack encapsulated request is passed from VMM201to host I/O stack211where it is processed by the aforementioned driver and kernel layers and is ultimately serviced by appropriate physical system resources103. Depending on the I/O request, a response may be required which is then passed all the way back up, layer by layer, to the originator of the request, such as any one of VMs131a-131c.

To improve I/O throughput and overall system performance, virtualized computer system250further comprises an adaptive I/O data handling mechanism embodied inFIG. 2as host-level virtual I/O channels (VIOCs)223and a host-level VIOC agent225. As explained in further detail below, VIOCs223includes physical memory resources as well as logic and program modules, instructions, and other data structures for performing I/O request processing management in a manner accelerating access to VM I/O data and generally improving per-VM and system-wide I/O data throughput. In the depicted embodiment, VIOCs223interface with transport and filesystem filter drivers213and hardware filter drivers221while VIOC agent225interfaces with VIOCs223as well as host OS235.

FIG. 4is a more detailed block diagram illustrating an embodiment of the interfacing of VIOCs223and VIOC agent225with host I/O stack211. As shown inFIG. 4, VIOCs223generally comprise a queue storage413that provides physical storage for data collected and managed using the techniques described herein. VIOCs223further comprise management components and modules for implementing the collection and management of the stored queue data. In the depicted embodiment, queue storage413comprises a sub-portion of available physical memory205. The queue management components of VIOCs223generally comprise a queue driver409, a queue service405, a filesystem filter driver407incorporated within filter drivers213, and a storage filter driver412within hardware filter drivers221.

Queue service405is included within a service layer403, which is a sub-function of host OS235in the upper portion of host I/O stack211. Queue driver409logically interfaces queue service405, filesystem filter driver407, and storage filter driver412. Queue driver409manages data structures within queue storage413in accordance with information received from the filter drivers and other modules.

As shown inFIG. 4, queue storage413contains one or more VHD image files415,417,419each comprising one or more block addressable I/O queues which are depicted and explained in further detail below with reference toFIGS. 5A and 5B. The queues making up image files415,417, and419are adaptively managed by queue driver409using a variety of metrics, statistics, and other data relating to I/O channeling. In one embodiment, queue driver409generates VHD image files415,417, and419in a manner establishing multiple virtual I/O channels that may be dedicated or shared for data access by local or networked VMs delivering VM I/O requests to host I/O stack211.

Filesystem filter driver407logically interfaces queue service405, storage filter driver412as well as queue driver409. Filesystem filter driver407communicates with queue service405using variations of standard process calls utilized in the service-to-driver interface. I/O request data (e.g. read or write data) may be transferred directly between queue driver409and a volume/disk driver411as controlled by I/O request processing by filesystem filter driver407.

In operation, a VM stack encapsulated I/O request received by service layer403, such as from VMs131or as a network I/O request packet (IRP) from virtualization layer109, is initially detected within host I/O stack211by queue service405. Queue service405forwards the request to filesystem filter driver407which queries queue driver409to determine whether VIOCs223contain the requested data. To this end, filesystem filter driver407examines the I/O request and queries queue driver409to determine whether the requested data is contained in or otherwise logically accessible from queue storage413. If VIOCs223are not able to service the request, a queue miss results and filesystem filter driver407forwards the request to a volume/disk driver411. If, for example, the queue miss is a read miss, volume/disk driver411retrieves the data from disk drives and returns the data to filesystem filter driver407which forwards the retrieved data to queue service405. Queue service405forwards the retrieved data to the requesting entity such as via virtualization layer109. Depending on the configuration, volume/disk driver411or filesystem filter driver407also provides the retrieved data to queue driver409, which stores the retrieved data within queue storage413in accordance with queue management policy explained in further detail below.

If, as determined by filesystem filter driver407and queue driver409, VIOCs223are able to service the request, queue driver409handles the request using address and data information stored within queue storage413as depicted and explained in further detail below.

FIG. 4depicts VIOC agent225as an agent service incorporated within host OS service layer403. While depicted inFIG. 4as a distinct logical module for illustrative purposes, VIOC agent225may be incorporated in part or entirely within queue driver409. VIOC agent225detects and tracks processor utilization and memory utilization via the usage of VIOCs223in association with VMs. To this end, VIOC agent225interfaces queue driver409via queue service405as well as interfacing kernel mode driver219to obtain system metrics relating to processor and memory utilization, available physical resource bandwidth and other metrics relating to I/O processing. Such metrics and statistics preferably include compression ratios within queue storage413, size and rate of change of consumed memory space within queue storage413, number and ratio of I/O queue hits and misses, as well as processor/logical partition utilization metrics that may be obtained from virtualization layer109or hardware drivers and controllers. Such metrics further include physical volume/disk storage configuration including the number of spindles, redundant array of independent disks (RAID) type, bus type (e.g., USB, PCI, PCI-X), physical storage controller configuration (e.g., SCSI device, controller cache capacity, READ/WRITE caching allocation, etc.). VIOC agent225uses the statistics and utilization data to make decisions regarding the status and operation of VIOCs223. For example, the size of all or specified portions of queue storage413may be dynamically scaled in accordance with absolute and/or relative memory and processor utilization and I/O latency and throughput as determined and tracked by VIOC agent225.

VIOC agents, such as VIOC agent225, can manage VIOCs such as VIOCs223in different ways either individually or in cooperation with other VIOC agents. For example, an agent may manage one or more I/O queues within VIOC queue storage using a series of pre-specified priority parameters that establish relative prioritization among queues within or across VIOCs. Alternately, VIOCs can be controlled in an automated fashion by enabling VIOC agents to determine demands placed on a VM or on a specific VHD and thereby determine how much memory to assign to that particular queue at a given point in time. VIOC agent225may also determine virtual CPU load due to disk I/O bottlenecks and host CPU load to determine if throttling or additional VIOC storage space would benefit the VM.

VIOC agent225can also monitor the state of each VM and, upon a change in state, manage the corresponding I/O queues within VIOCs223accordingly. For example, upon a hard or soft reboot, VIOC agent225may commit all writes to disk and clear data within VIOCs223(i.e. image files415,417,419). During a power down sequence, VIOC agent225may eliminate one or more I/O queues from the list of active queues and copy the queue states to disk for retrieval upon restart. When a VM is suspended, a VIOC agent225may enable the VM's corresponding queue(s) to persist in memory and commit writes. The agent may also commit writes and store to disk for retrieval when the VM is resumed.

FIGS. 5A and 5Bare more detailed block diagrams of an embodiment of VIOCs223depicting features and components for processing I/O requests in a virtualized environment. Queue service405provides a logical interface with performance counters (not depicted) and controls configuration of the drivers including files, directories, filesystems, and volumes that are monitored and/or queued. Filesystem filter driver407intercepts I/O requests which may be encapsulated within I/O request packets, and routes the requests and IRP flag data extracted from the encapsulated requests to queue driver409. Queue driver409processes the I/O request data from filesystem filter driver using a hashing table503that performs a hashing function to determine whether queue storage413contains the read/write address (assuming a read/write/modify request) corresponding to requested read/write data.

Queue storage413generally comprises hash table indexed sets of data maintained in logically associated I/O queues562a-562neach associated with block addresses depicted inFIG. 5Bas LBAs. The data stored in queue storage413(i.e., within I/O queues562a-562n) can include both non-compressed data505as well as compressed data507. Data requested by a read I/O request that is in non-compressed data505is retrieved and sent by queue driver409back to the VM client requester. If requested read data is contained within compressed data507and not in uncompressed form, the data is decompressed and provided as non-compressed data505prior to being sent by queue driver409to the requesting client.

Queue driver409comprises a compression module512for compressing data to be stored as compressed data507. Compression module512preferably includes multiple different compression engines, each employing a different compression algorithm to compress data in accordance with entropy signature characteristics as explained below. In a preferred embodiment compression module512includes a Lempel-Ziv Markov type compression engine that compresses data to be stored as compressed data507in accordance with a Lempel-Ziv Markov chain algorithm.

If data requested by an I/O read request is not located in queue storage413(i.e., queue read miss), the request is sent to a read queue509from which it is forwarded to volume/disk driver411which retrieves the requested data from disk drives207. A read request handled by volume/disk driver411is sent to disk drives207as a request to read a logical block address (LBA). Data returned from volume/disk driver411may include the requested data as well as read-ahead data which are copied into the applicable I/O queues562a-562nand in concert with the requested data being delivered to the requesting VM client. As depicted and explained in further detail with reference toFIGS. 5B,13, and15, an entropy encoding mechanism is utilized to provide smart pre-fetch in association with a read miss.

For a write I/O request, the object data block having a specified LBA is written to queue storage413and simultaneously or subsequently copied back to secondary storage such as disk drives207. The write data is tagged by a tagging mechanism513and sent to queue storage413as well as to a write queue515which temporarily stores the write data until volume/disk driver411and a write optimizer517indicate that disk drives207are available to receive the data. In one embodiment, tagging mechanism513follows a multi-state state machine algorithm that allows dispatching of writes during idle processor and disk cycles to avoid blocking. Write optimizer517tracks storage availability on disk drives207so that the data is written to physically proximate locations to minimize file/data fragmentation.

Queue driver409includes logic modules and instructions that enable optimized handling of each discretely handled datum (e.g., block or page) maintained in queue storage413. Included among such performance optimization functionality is an entropy encoding module504that is utilized by queue driver409to encode data blocks to be queued within queue storage413using any combination of entropy, redundancy, and efficiency values. As utilized herein, entropy generally refers to entropy as applied in the field of information theory. Examples of information theory entropy include Shannon Entropy or simply “information entropy” such as described by Claude E. Shannon in the technical paper “A Mathematical Theory of Communication” (1948), the content of which is incorporated herein by reference. Redundancy in information theory is the number of bits used to transmit a message minus the number of information bits in the message and may be derived from entropy values computed by entropy encoding module504.

The systems and methods disclosed herein synergistically leverage the relations between information entropy, and absolute and relative redundancy to derive an identity checking function implemented by an identity function module519that may be usefully applied to achieve delta compression within queue storage413. The identity checking function implemented by module519relies on the assumption that data blocks having equal values of information entropy, and absolute and relative redundancy are substantially identical. The identity checking function is used by queue driver409to achieve a delta compression that minimizes population of queue data block locations with blocks having identical data but different physical, logical, or network addresses. In this manner, the identity of a data block as determined by its information entropy and corresponding absolute and relative redundancy may be used as a unique identifier of that data block, regardless of its addressable position within a VHD, network packet, or physical disk location.

Entropy encoding module504includes logic, instructions, and program modules that determine/estimate the entropy of a data block in the following manner. The absolute entropy H of a block of a data set of n tokens (1, 2, . . . , n) occurring with respective probabilities or frequencies p1, . . . , pnis defined by the equation:

H=-∑i=1n⁢pi⁢log⁢⁢pi(1)
For example, in a block of data comprising a bare string of English language words, the set of tokens comprises the letters a-z. The probability or frequency of occurrence of the letter a (pa) is equal to the number of occurrences of a in the block divided by the total number of letters in the block. H=0 if and only if all the pibut one are zero. In other words, if all the tokens in a block of data are the same, the entropy of that block is zero. For a given number of tokens, n, H is a maximum and equal to log n when all the piare equal (i.e., 1/n).

The ratio of the absolute entropy of a set of tokens to the maximum value it could have is the set's relative entropy, HREL, determined in accordance with the relation:

HREL=-∑i=1n⁢pi⁢log⁢⁢pilog⁢⁢n(2)
Encoding module504further includes logic and/or program modules and instructions for determining the absolute and relative redundancy values for the data blocks. Namely, the absolute redundancy, D, at a specified token position within a block may be characterized by the relation:
D=R−r,
where R is the cumulative redundancy of the data string for the previous r−1 bits in the data string, and r is the redundancy of the rthtoken. The relative redundancy may be expressed as the ratio D/R.

In one embodiment, the entropy estimate may be made by entropy encoding module504using a frequency table for the data representation used. Frequency tables are used for predicting the probability frequency of presumed alphabetic token occurrences in a data stream and the use of such tables is well known in cryptographic arts. For example, for English language ASCII data, a 256-entry relative frequency table may be used. For the disclosed embodiments, the token stream may comprise ASCII-encoded tokens, but is not restricted to this.

In one aspect of the systems and methods disclosed herein, the entropy and redundancy values are utilized by queue management modules such as queue driver409to determine whether data is to be stored within queue storage413in a compressed format or as non-compressed data. Compression of data within queue storage413allows for relatively large amounts of data to be stored in VIOCs223with minimum consumption of physical memory. Multiple compression algorithms can be implemented concurrently by multiple compression engines for compressing across multiple data structures within queue storage413simultaneously.

FIG. 5Bis a high-level block diagram depicting queue storage413such as may be implemented by the VIOCs shown inFIG. 5A. Specifically,FIG. 5Billustrates hash table503as generally comprising a VHD queue storage management module522that generates multiple queue entries that may correspond to one or more VHDs. In the depicted embodiment, the multiple queue entries correspond to logical block addresses (LBAs) 0 through 1000. Each of LBAs 0-1000 specifies the location (i.e., address) of blocks of data stored on disk drives207or other persistent data storage systems. The logical blocks addressed by LBAs 0-1000 are typically 512 or 1024 bytes each but may be larger or smaller depending on the storage media type.

Upon system initialization, such as during system restart or during initialization of a VM, VHD queue storage management module522generates a sparse table of hash entries for each of the LBAs. The hash entries logically describe the physical storage space of one or more VHDs. The entries for the LBAs are initially empty and remain empty unless and until processing of I/O requests results in data blocks being stored in compressed or non-compressed form into the VHD image managed by VHD queue storage management module522. In the depicted embodiment, for example, LBAs 0 and 2 address I/O queues562aand562c, respectively, which comprise blocks524and526.

The LBA 1, 100, and 1000 entries are shown as containing variable size data blocks contained within I/O queues562b,562d, and562n, respectively, which preferably form a self-referential pointer space such as that implemented within linked lists. I/O queue562bcontains variable size data blocks528,532, and534as well as a block530containing a pointer to invalid, in-flight data. I/O queue562dcontains a variable sized data block540and an in-flight block pointer536referencing a variable size data block546within I/O queue562n. I/O queue562dfurther includes link pointers to copy-on-write (CoW) blocks, represented as blocks538and542, which point to corresponding CoW marked variable sized data blocks548and552within I/O queue562n. In contrast to random access organization such as provided by standard CPU cache memory, the data blocks and pointers contained in each of I/O queues562a-562ncomprise double linked lists enabling the internal cross-referencing depicted inFIG. 5B. As known in the art, a double linked list is a linked list containing a sequence of fields or nodes, each containing a data field and two link references, one pointing to a next node or data field and the other pointing to a previous node or field. Data tracking and coherency across the I/O queues is preferably performed in accordance with the modified MSI protocol depicted and explained with reference toFIG. 18. Furthermore, and as depicted and explained in further detail with reference toFIGS. 14 and 15, the data blocks contained in I/O queues562a-562nare preferably entropy-encoded to minimize redundancy in the resultant VIOCs maintained by VHD queue storage management module522.

Furthermore, queued data within queues562can be prioritized in a variety of ways such as prioritization based on any combination of hit recency (e.g. LRU), hit frequency (MFU), and queue dwell time. In a further aspect of the present invention, replacement policy prioritization may additionally or alternately utilized entropy signature correlations among queued blocks.

In the embodiments thus far described and illustrated, the VIOCs have been host-configured and managed. In an alternate embodiment of the systems and methods disclosed herein, VIOCs may be configured and managed on the virtual machine level. In such an embodiment, and as illustrated inFIG. 3, the VIOCs may be implemented at both the host level and the virtual machine level, or exclusively at the virtual machine level.

FIG. 3illustrates a system300in which VM-level VIOCs are implemented and managed at both the host level and the virtual machine level. VMM201, host OS stack211and its components, hardware103and its components, VIOCs223and VIOC agent225are substantially the same as those described with reference toFIG. 2. Analogously to host I/O stack211, a VM I/O stack301comprises multiple instruction and logic layers for implementing an I/O request processing protocol. Namely, VM I/O stack301generally comprises an OS303, a set of transport and filesystem drivers305, a set of user mode drivers307, a kernel309, a set of kernel mode drivers311, and a set of hardware filter drivers313. Interfaced with VM I/O stack301are a set of VM-level VIOCs317and a VM-level VIOC agent315. VM I/O stack301, VIOCs315, and VIOC agent317operate in substantially the same way as described above with respect to a host implementation of the VIOCs and VIOC agent.

The depicted VM stack and host stack VIOC interfacing of system300provides a VM I/O queuing domain and a host I/O queuing domain enabling improved I/O request processing. As shown inFIG. 3, an I/O request, I/O REQ, originating from a VM application is processed through the depicted VM I/O processing stack. As I/O REQ is processed, it is encapsulated within a VM I/O request packet, VM IRP. The application and virtual hardware specific context contained in request flags and other context data may be read and unmasked by file system filter drivers305and VM hardware filter drivers313such that VIOCs317may construct and manage corresponding VHD images in accordance with VM stack processing data.

The reading and unmasking of application and virtual hardware specific context performed by the filter drivers is used to supply hints to a corresponding queue driver or other manager of VIOCs317on how to handle the corresponding I/O data blocks. These hints are encapsulated in the IRP flags used in either the VM itself (the guest OS) or from the VMM to the host OS. An example of these flags could be a set of flags indicating that the I/O is expected to be synchronous in nature, with sequential reading or writing characteristics and that the initiating application does not want any intermediate buffering to take place due to consistency constraints. These hints are used by the queue driver to shorten the I/O data path or reduce I/O latency by pre-selecting allocation strategies for the queue driver or determining expected seek characteristics (direction of head movement on a physical disk platter, if the underlying device is a physical disk) of the underlying storage device. An example of this is Rotational Positioning Sensing (RPS) where the underlying physical device begins head movement before initiation of follow on I/O.

The VM I/O request packet, VM IRP, is then passed to host stack211via VMM201where it is processed layer-by-layer until it is encapsulated within a host I/O request packet, HOST IRP. Host-level file system filter drivers213and hardware filter drivers221may read and unmask I/O request context contained in flags and other context data within HOST IRP such that VIOCs223may construct and manage corresponding VHD images in accordance with VM stack and host stack processing data.

As further depicted inFIG. 3, VIOC services are shared between the VM and host systems. A communication link319is provided between VM-level VIOC agent315and host-level VIOC agent225. VIOC agent225monitors queue statistics and utilization for optimizing the performance of VIOCs223. In a similar manner, VM-level VIOC agent315monitors queue statistics and utilization of the VIOCs317for optimizing the performance of VIOCs317.

Communication link319enables the agents to communicate with each other to optimize performance of the overall VIOC system. While depicted inFIG. 3as an external connection, communication link319can also be implemented in shared memory space, as a serial or parallel pass-through interface, or as a global variable pass-through. Communication link319may also be implemented as an infiniband link, or as a disk storage interface. If communication link319is implemented as part of a disk storage interface, the data collected and used by VM VIOC agent315may be written into an area inside of a virtual hard disk while VIOC agent225mounts a read-only copy of the virtual machine's disk (i.e., VHD) and reads the statistics accordingly such as via an interprocess call/remote procedure call (IPC/RPC).

FIG. 6is a simplified block diagram illustrating exemplary communications between different VIOC systems of different computer systems, including the same or different types of computer systems (e.g., physical versus virtualized). Two computers, shown as computer1601and computer2611, are each configured as either a VM or a physical host system. In this manner, communications are illustrated for VM-to-VM or host-to-VM communications in which such communications are similar regardless of the configuration of the particular computer system. The computer1601includes a VIOC system604having a VIOC agent603and corresponding VIOCs605. For a physical host system, VIOC agent603and VIOCs605are configured similar to the host-level VIOC agent225and host-level VIOCs223previously described. For a VM (e.g., VM131), VIOC agent603and VIOCs605are configured similar to the VM-level VIOC agent317and VM-level VIOCs315previously described.

A network stack607interfaces with VIOC agent603for communications and data transfers; data transfers, however, may also be made directly between VIOCs605and network stack607. Network stack607is configured as any standard or custom implementation including, but not limited to, Transmission Control Protocol/Internet Protocol (TCP/IP), User Datagram Protocol (UDP), Hypertext Transfer Protocol (HTTP), and/or custom protocols including wirespeed protocols and the like. Network stack607interfaces a hardware interface (I/F)609, which represents either a hardware I/F within host physical system resources103or a virtual hardware I/F within virtual hardware resources143(FIG. 1B). The hardware I/F609may include any one or more of several types of hardware interface types, such as Infiniband®, Ethernet, Token Ring, SCSI, direct memory access (DMA), remote direct memory access (RDMA), or any other networking or disk channel technology.

Computer2611includes a VIOC system614configured in substantially the same manner as VIOC system604and includes a VIOC agent613and VIOCs615similar to VIOC agent603and VIOCs605. VIOC system614communicates with a network stack617, which is configured in similar manner as the network stack607and which interfaces a hardware I/f619configured in similar manner as the hardware I/F609. VIOC system604is able to communicate with external entities via the hardware I/F609and VIOC system614is likewise able to communicate with external entities via the hardware I/F619.

A communication link610is shown provided between the hardware I/Fs609and619, enabling communication between VIOC systems604and614. Such communication is enabled between multiple VMs, host systems, VM to host, host to VM, etc. The hardware I/Fs609and619may be different or otherwise incompatible in which case communication link610provides the appropriate translation between the hardware interfaces. Communication link610is a more specific embodiment of the communication link319implemented between the host and VM queue agents225and315shown inFIG. 3. The communication methods may also be according to alternative methods as known to those skilled in the art, such as memory searches, pointers, VMM directions, redirections, etc. It should be noted that the system implemented as shown inFIG. 6is not limited to two hosts but may include any number of networked or otherwise connect host systems.

FIG. 7is a block diagram of a host system700with a host VIOC system701and a number “N” of VM VIOC systems703, individually shown as VM1VIOC system, VM2VIOC system, . . . VMN VIOC system, illustrating communication between VIOC systems. Each VIOC system, including the host VIOC system701and each VM VIOC system703, includes VIOCs and a VIOC agent configured in a similar manner as previously described. Communication links705illustrate that host VIOC system701is able to communicate with each of VM VIOC systems703and that VM VIOC systems703are able to communicate with each other. Each communication link705may be configured in a similar manner as the communication link610enabling interfaces between corresponding hardware interfaces. In one embodiment, communication is conducted on a peer-to-peer basis and queue management functions are centralized or distributed among one or more of the VIOC systems.

In an alternate embodiment, a centralized VIOC manager709is provided for managing VIOC functions of the host VIOC system701and the VM VIOC systems703. VIOC manager709is shown with dashed lines indicating an optional configuration. VIOC manager709performs queue management functions which may or may not be performed its own local VIOCs/I/O queues. In one embodiment, communication links705are extended to VIOC manager709to enable communications between VIOC manager709and the host VIOC system701and each of the VM VIOC systems703. In this case, host VIOC system701and VM VIOC systems703are able to communicate with each other while management functions are centralized at VIOC manager709. In an alternate embodiment, host VIOC system701and each of VM VIOC systems703communicate solely with VIOC manager709.

FIG. 8is a simplified block diagram of a network VIOC system800illustrating communication between host VIOC systems803and805(individually labeled host1VIOC system803and host2VIOC system805) via a network801. Again, each host VIOC system803and805includes local VIOCs and a local VIOC agent configured in a similar manner as previously described. Each host VIOC system803and805may be interfaced with any number of VM VIOC managers in a similar manner as shown inFIG. 7. For example, host1VIOC system803is linked to any number of VM VIOC systems804and host2VIOC system805is linked to any number of VM VIOC systems806. Each VIOC system communicates via a corresponding hardware interface in a similar manner as shown inFIG. 6in which the communication link610contemplates the network801. In this manner, any number of VIOC systems communicate across network801for purpose of VIOC/queue control and management. The VIOC systems, including the host VIOC systems803and805and the VM VIOC systems804and806, may communicate on a peer-to-peer basis. Also management is either centralized at any one VIOC system or distributed among multiple VIOC systems in the network VIOC system800.

In an alternate embodiment, a VIOC manager807is also shown linked to the network801via communication link810. VIOC manager807is shown with dashed lines indicating an optional configuration. In centralized configuration, VIOC manager807communicates with each of the host VIOC systems803and805for purposes of VIOC/queue management and may further communicate with each of the VM VIOC systems804and806. In one embodiment, for example, each VM VIOC system804and806may be linked to the network801in addition or in the alterative to be linked to its local host VIOC system. In this manner, VIOC manager807is individually interfaced with each of the host VIOC systems803and805and each of the VM VIOC systems804and806.

A centralized queue manager, such as VIOC managers709and/or807, may be executed as an application on any host system or on any VM of any given host system. Each VIOC system being centrally managed includes a local VIOC agent which monitors the queue statistics and processor/memory utilization of its corresponding queue and reports the information to the central queue manager. The VIOC manager instructs each VIOC system, such as using a predetermined command protocol or the like, to adjust its queue and queue operations to optimize queue functions in the system.

FIG. 9is a simplified block diagram illustrating replication of a VIOC system architecture according to an exemplary embodiment. A first VIOC system architecture906, including a host VIOC system HCS1and N VM VIOC systems VCS11, VCS12, . . . VCS1N, is coupled to a network910in a similar manner as previously described. It is desired to replicate VIOC system architecture906into another, similar VIOC system architecture, shown as a second VIOC system architecture908, through the network910. A communication and queue management architecture according to an exemplary embodiment facilitates the replication procedure. As illustrated, the first host VIOC system HCS1is replicated to a second host VIOC system HCS1across the network910. Likewise, the VM VIOC systems VCS11, VCS12, . . . , VCS1N are replicated to a second set of VM VIOC systems VCS21, VCS22, . . . , VCS2N, respectively, of the second VIOC system architecture908. Communication links are established between VIOC systems of the second VIOC system architecture908to mimic that of the first VIOC system architecture906.

FIG. 10is a block diagram illustrating an alternate embodiment of host and VM queue memories. As illustrated, a host queue memory901and a VM queue memory903are both stored in the memory205. The host queue memory previously described is a dynamic memory in which stored data is constantly changing in response to I/O requests. In contrast, host queue memory901is a static memory with predetermined pre-stored data that does not change over time. The static host queue memory901is interfaced with a dynamic host Copy On Write (CoW) queue memory902, which stores data from subsequent read or write operations. In particular, new data is written to host CoW queue memory902so that the data of host queue memory901remains unmodified. When new data is written to a data block that is addressed by multiple VMs, this data block is then copied to the block previously occupied only by a pointer if and only if the data block does not have identical LBAs but matches only at the entropy/redundancy level, since the VM that previously referenced this block did not modify this memory. If the LBA of the CoW block is the same between both VMs then the block is not copied but instead both VMs have modifications to this block to complete. Data is read from either host queue memory901or host CoW queue memory902depending upon where the data is located. A similar static VM queue memory903interfaced with a dynamic VM CoW queue memory904is included in memory205and operates in the same manner. In an alternate embodiment, a CoW can be used specifically when an UNDO disk is used. In this manner, writes are never committed to the disk when an UNDO disk is discarded at the end of a session, resulting in reduced reset time. Alternatively, the writes could be committed on-demand following a sequence in accordance with the previously described embodiment.

FIG. 11is a block diagram illustrating a mixed mode system according to another embodiment. In this case, a host system1101includes a host VIOC system1102(such as, for example, including VIOCs223and VIOC agent225). Host system1101supports several VMs, including, for example, a first VM11103, a second VM21105, a third VM31107and a fourth VM41109. The VM11103includes a VM1VIOC system1104and the VM21105includes a VM2VIOC system1106. In one embodiment, the VM11103and the VM21105leverage only their respective VM VIOCs1104and1106, respectively, rather than the host VIOC system1102. Alternatively, the VM11103and the VM21105leverage their own VM VIOCs and host VIOC system1102. In contrast, the VM31107and the VM41109do not include corresponding VM VIOC systems. The VM31107and the VM41109generally leverage the host VIOC system1102.

FIG. 12is a block diagram of a hybrid VIOC system1200according to another embodiment. The VM filter drivers1203are shown including the VM queue filter driver1212interfacing the VM queue driver1213in a similar manner as previously described for host VIOCs223. Also shown is memory205including a VM queue storage1217interfacing VM queue driver1213in a similar manner as previously described. In this embodiment, however, the VM volume/disk driver411is replaced with a request mapping module1201. VM queue filter driver1212and VM queue driver1213both interface the request mapping module1201, which directly interfaces the host volume/disk driver411of the host kernel mode drivers219. In this manner, the VM VIOCs more directly interface the host hardware via the host volume/disk driver411thereby bypassing significant portions of the VM stack and the host stack. The host VIOC system, such as including VIOCs223and VIOC agent225is optional and may be eliminated with the exception of host volume/disk driver411.

In the previous configurations, I/O queuing occurs on the host or the VM or both. The hybrid VIOC system1200is a combined solution that splits the I/O queuing mechanism between the host and VM. By splitting the I/O queuing mechanisms between the host and the VM systems, a greater efficiency is achieved through bypassing the additional overhead of unnecessary filter drivers and redundant I/O queues. VM queue filter driver1212operates as part of the VM and communicates with the VM-based I/O queue. A read I/O request, for example, is passed from a VM application through VM queue filter driver1212and then either to a VM I/O queue (if it is a queue hit) or down through the VM kernel layers to the VMM201and then onto the stack of the physical host system. Under the host OS stack is the kernel mode filter driver that catches the I/O request (a logical block) or (logical block number) and requests the data from the disk drives207. It then passes the response back up the stack and populates the VM queue with the requested block.

In the event of a queue hit, request remapping module1201remaps a virtual I/O request to a physical I/O request in most cases. A virtual I/O request may be directly mapped to a physical I/O. In one embodiment, the translation occurs through a block map that stores the location of the physical block in perspective to the matching logical block. In this manner, the VM user mode filter driver and the physical host kernel driver communicate with one another as though they were directly linked. This allows for the VM queue to function very efficiently inside of the VM. It is noted that is possible to locate the queue outside of the VM as well, such as a host-level queue. The translation may occur inside of the VMM201, on the host OS235, or even within the memory205. In another embodiment, the I/O queue can reside on the host system.

FIG. 13is a high-level flow diagram illustrating steps performed during processing of a read request as implemented by virtualized I/O request processing architectures such as shown inFIGS. 2,3,4,5A, and5B. The process begins as shown at step1302with host I/O stack211receiving a read-type I/O request from VMM201. The read request received by host stack211has been generated by a VM application client and processed by the VM I/O stack. In addition to the read directive, the read request is encapsulated with VM-specific context data.

The VM I/O stack encapsulated read request is received by a filter device at or near the top of host I/O stack211. In one embodiment, the receiving filter device(s) may comprise file system filter driver407, which processes the VM I/O stack encapsulated read request as shown at step1304. Specifically, file system filter driver407parses the request command/argument directive (in this case a read of specified data) at step1306, and further determines the request context as conveyed by the VM stack encapsulation/encoding (step1308). Assuming the read request is received as a VM encapsulated I/O request packet (IRP), the context data is typically encoded as IRP flags. The directive and request context determined by filesystem filter driver407is received by queue driver409which processes this information to handle the request using VIOCs223.

In addition to the request information extracted by the filter device, queue driver409receives VHD settings data from a storage filter driver412as shown at step1310. The VHD data preferably includes file system characteristics such as may be obtained from meta data511stored in association with the underlying VHD. The determination and retrieval of such VHD data by queue driver409from storage filter driver412may be asynchronous to any given I/O request.

As explained above with reference toFIG. 3, queue driver409assesses the read request context data extracted by filesystem filter driver407with host volume/disk driver meta data from storage filter driver412to make VIOC access decisions with respect to the read request. For example, the IRP flags may indicate that the read request is part of a series of synchronous requests having sequential reading/writing characteristics. Queue driver409uses such “hints” in conjunction with storage side/VHD meta data to pre-selected queuing allocation (e.g. read-ahead, pre-fetch) to be performed with respect to the presently received read request.

The read request processing continues as illustrated at step1312with queue driver409determining whether the requested data is queued locally within VIOCs223. Queue driver409determines whether the data is queued by accessing hash table503which indexes queue entries562a-562ncorresponding to the LBAs of underlying VHDs. Referring to the depiction of hash table503inFIG. 5B, for example, the requested data may be determined at step1316to be locally queued at the requested address within one of the depicted variable sized blocks stored within queues562b,562d, or562n. Alternatively, queue driver409may determine at steps1312and1316that the requested data is queued within VIOCs223at a different address using the pointer swizzling illustrated and explained with reference toFIGS. 5A and 5B. If so, the matching data is located using a corresponding swizzled pointer as shown at step1318.

Upon locating the directly or referentially stored requested data, and if the queued data is entropy encoded, the requested data block is decoded prior to being sent to the requesting VM client (steps1322,1324, and1326). If the requested data is compressed within its respective queue within queue storage413, the decoding illustrated at step1324further includes decompressing the data either as part of or in addition to the entropy signature decoding process.

Returning to step1312, responsive to queue driver409determining that the requested data is not accessible from VIOCs223(i.e., a queue miss), the read request is sent down host I/O stack211for processing (steps1312and1314). As part of the queue miss processing, a read-ahead or pre-fetch is performed with the data fetch as shown at step1320.

As part of retrieving the data from one of the queues within VIOCs223or copying to/updating the queue in case of data copy from volume/disk driver, the queue replacement policy tag (e.g., LRU) is updated as shown at step1328and the process ends.

Referring now toFIG. 14, there is illustrated a modify-write portion of a read/write/modify processing sequence as processed by VIOCs223. The process begins as shown at step1402with a modified block of data received by queue driver409to be written to queue storage413. Entropy encoding module504encodes the received block by first estimating one or more entropy and/or redundancy values for data block, as illustrated at step1404. In one embodiment, the entropy and redundancy values determined by module504include the absolute entropy as well as the absolute and relative redundancy of the data block.

Entropy encoding block504utilizes the computed entropy/redundancy values to encode the received data block as shown at step1406. The entropy encoding may be performed as a data transform of the block data such as by compression or encryption. The entropy encoding may also comprise associating one or more entropy/redundancy values as a token or header with the data block within VIOCs223. For example, if a 64-bit entropy value is estimated for the data block, the 64-bit value may be stored as a meta data tag for the block within the block's metadata511. The entropy encoding serves multiple purposes including block compression and delta compression as well as for optimizing ensuing pre-fetch or read-ahead operations performed when the data block is removed from the queues and subsequently fetched back into queue storage413.

Queue driver409determines whether, in accordance with the estimated entropy value, the data has exceeded a specified redundancy threshold (step1408). If not, queue driver409stores the received data as non-compressed data505within queue storage413, as shown at step1416. If a write miss occurs (step1412), a block replacement cycle is commenced (step1414) in association with writing the non-compressed data to queue storage413. The block replacement depicted at step1414is performed in accordance with a specified queue replacement policy. The replacement policy may be based on any combination of hit recency (e.g. LRU), hit frequency (MFU), and/or queue dwell time. In one embodiment, the replacement policy includes correlating the entropy signatures of queue blocks in combination with hit recency or frequency to account for similarity between blocks and relative activity as criteria for replacement.

If, as determined at decision step1408, the received data has a redundancy value greater than the specified threshold level, compression module512compresses the data as indicated at block1410prior to the data being written to queue storage413. Following or in conjunction with the compressed or non-compressed data being queued within queue storage413, the data is written back to disk or other backing storage (step1418) and the entropy encoding for the data block is stored in the block's meta data511(step1420).

Referring now toFIG. 15, there is illustrated an embodiment of a read-ahead or pre-fetch cycle such as may be implemented as part of a queue miss read depicted at step1320inFIG. 13. Queue driver409determines, at decision step1501, whether the entropy/redundancy signature of a data block to be fetched into queue storage413has been recorded. If so, the read-ahead selection includes checking for stored blocks having entropy signatures, also previously recorded, that are similar to the entropy signature of the target block being fetched (step1503). In one embodiment, a data block is determined to be similar to another data block if their respective entropy values are within 6% of each other (i.e., entropy values are similar to at least a value of 94%).

If, as determined at decision block1503, there are blocks with similar entropy within a specified physical address distance from the target fetched block, the closest block(s) in terms of LBA are also fetched as shown at step1505. In the depicted embodiment, the blocks may reside any logical distance from the requested block, and the queue driver will pre-fetch and pre-load up to 4096 (4k) blocks. If any of the re-requested pre-fetch blocks reside in any queue, including queues not handling the current I/O request, the pre-fetch will consist of only a pointer update and the block will not actually be fetched or inserted into the queue handling the request. The queue consistency protocol (described below as a modified MSI with reference toFIGS. 16-17) will only copy the block into the requester queue if the block becomes modified or invalid in another queue.

Returning to step1501, if the entropy of the target fetch block is not recorded or if no stored blocks proximate the fetch block are found to have similar entropy, queue driver409determines if gap prediction data has been recorded for previous read cycles (step1507). Gap prediction is performed by tracking the distance or “gap” between successive reads in which data is fetched from a particular file stored on a VHD. If usable gap prediction data is available, one or more blocks are pre-fetched based on such data as illustrated at step1509. If queue driver409does not employ gap prediction or if usable prediction data is not available for the fetch block in question at step1507, queue driver409fetches the next sequential block(s) of data, as indicated at block1511.

After fetching/pre-fetching one or more data blocks in the manner shown at steps1505,1509, or1511, entropy encoding module504estimates the entropy of the fetched block(s) and encodes the block(s) with the resultant entropy/redundancy signatures, as shown at block1513. For blocks having previously recorded entropy/redundancy signatures, such as blocks considered at steps1503and1505, the entropy/redundancy may not have to be computed but may be retrieved as part of the blocks' meta data.

Next, as depicted at step1515, identity function module519cross compares entropy and redundancy values of the fetched data blocks with the entropy and redundancy values of presently queued data blocks to check for data matches using an identity function signature. Specifically, identity function module519compares the entropy, the absolute redundancy, and the relative redundancy values of the fetched blocks to entropy and redundancy values of presently queued blocks and if a match is found, the fetched blocks are not copied into queue storage413. Instead, pointers to the extant matching blocks are stored and translated from the LBAs of the fetched blocks in a pointer swizzling process shown at step1517.

In one embodiment the identify function signature for each block is simply the values of the entropy, the absolute redundancy, and the relative redundancy of each respective data block. In an alternate embodiment, an identity function signature, I, for each respective data block is derived in accordance with the relation: I=H(R)/D/d, where H is the value of entropy, R is the absolute redundancy, and D/d is the relative redundancy. The values of the respective identity function signatures are compared and if equal a match between the blocks is determined.

For the fetched blocks having no data match within queue storage413, queue driver409determines whether, in accordance with the estimated entropy value, the data has exceeded a specified redundancy threshold (step1408). If not, queue driver409stores the fetched blocks as non-compressed data505within queue storage413, as shown at step1416. If a write miss occurs (step1412), a block replacement cycle is commenced (step1414) in association with writing the non-compressed data to queue storage413. Similar to the embodiment depicted inFIG. 14, the replacement policy may include correlating the entropy signatures of queue blocks in combination with hit recency or frequency to account for similarity between blocks and relative activity as criteria for replacement.

If, as determined at decision step1408, the fetched data has a redundancy value greater than the specified threshold level, compression module512compresses the data as indicated at block1410prior to the data being written to queue storage413. As depicted at step1420, the entropy encoding for fetched data blocks not previously queued is stored in the block's meta data511.

FIG. 16illustrates a modified MSI protocol for maintaining coherency among the I/O queues maintained within VIOCs according to the systems and methods disclosed herein. Caching differs substantially from queuing according to the systems and methods disclosed herein in that caching utilizes different consistency models while queues having an inherent consistency model due to the structure of the queue itself. The resulting enforced serialization simplifies the consistency and does not introduce additional latency or access speed costs. Data in a queue may be allocated, but the disk I/O may not complete in hundreds if not thousands of microseconds. During this time, additional I/O requests could be made against the same allocated data. Accordingly, the states of “committed and valid” and “committed and invalid” are added to the MSI protocol. The state diagram ofFIG. 17illustrates the state transitions for write-invalidation in accord with the present inventive design principles.

As described herein, the VIOC systems communicate with each other on a peer-to-peer basis or are controlled or managed by a VIOC manager (e.g.,709,807) for purposes of queue utilization optimization. In one embodiment, the size of the queue memory (e.g.,901,903) is dynamically adjusted, such as on a periodic or continuous basis, based on a set of queue optimization relationships. For the host system, the available amount of memory for queue purposes (HAQ) is based on the amount of the physical memory (PMA), the memory usage of host-based applications (HAMU) the memory usage of the host OS (HOSU), the memory usage of the VMM (VMMU), the number N of simultaneously running VMs, the memory usage of the ith VM OS (VMOSUi), and the memory usage of the applications running on the it VM (VMAMUi) according to the following equation:

A⁢⁢V⁢⁢G⁢⁢Q⁢⁢V⁢⁢M=A⁢⁢V⁢⁢G⁢⁢I⁢⁢O⁢⁢V⁢⁢M·A⁢⁢V⁢⁢G⁢⁢T⁢⁢I⁢⁢Q·Q⁢⁢C⁢⁢RQ⁢⁢H⁢⁢R(4)
A VIOC agent according to the systems and methods disclosed herein “learns” over time and the quality of data in a queue improves. Thus, over time, the queue hit ratio QHR approaches one, and the average rate of data I/O transferred into the queue over a given sampling period of each simultaneous VM AVGIOVM approaches zero. Accordingly, the average amount of queue memory space that is efficiently consumed by a VM AVGQVM becomes smaller over time. Although, the average rate of data I/O transferred into the queue over a given sampling period of each simultaneous VM A VGIOVM approaches zero, the size of the queue cannot be allowed to go to zero. The minimum queue usable allocated to a VM (MINQUVM) is based on AVGQVM according to equation (2) and a queue size factor (SF) according to the following equation (5):
MINQUVM=AVGQVM·SF(5)
In one embodiment, SF is approximately 1.25, although SF may be any suitable value depending upon the particular configuration; however, MINQUVM cannot be allowed to be less than a certain predetermined minimum. The maximum amount of memory efficiently consumed by a VM (MAXVMM) is based on VM OS usage (VMOSU), VM application usage (VMAU), and optionally VM queue usage (VMQU) according to the following equation (6):
MAXVMM=VMOSU+VMAU+VMQU(6)

It is noted that if an application normally attempts to store large amounts of data in memory, it may be more efficient in many cases to have the application swap inside of the VM and queue the swap file I/Os as they pass through the VMM to the host queue. It is noted that if the VM queue is not used, then VMQU is zero. If MAXVMM is exceeded, then the queue performance of the host queue is sub-optimal. If AHUQ is less than MINQUVM, then queue performance of the host queue is sub-optimal. In this manner, there exists a “sweet spot” of queue size allocation in which a balance is achieved between the memory allocated to a VM versus the amount of queue usable to perform the necessary queuing of the I/O of the VM.

Queuing at the host level is desirable in many situations as it does not intrude upon the contents of the VM by requiring a VM agent to be installed. This may result, however, in sub-optimal settings being used on the host queue due to lack of insight into the VM. There are alternatives to getting the data through an agent inside the VM. Two alternatives are to look inside of the VM's hard disk(s) and look at what OS is being used and what applications are installed, look at entropy values that are being read/written and comparing them against a known sequence of entropy values, or having someone manually enter the data (or the equivalent of when a VM is provisioned to have the data stored somewhere so that it can be referred to by the queue).

Queuing at the VM level is desirable when there is a need for the host to be free of any additional software installed on it, or if the physical queuing software is not supported on that particular virtualization software or hypervisor configuration. For the VM system, the available amount of memory for queue purposes (VMAQ) is based on the VM memory (VMMEM), memory usage of VM-based applications (VMAU) and the memory usage of the VM OS (VMOSU) according to the following equation (7):
VMAQ=VMMEM−(VMAU+VMOSU)  (7)
The amount of useable queue (VMUQ) for the VM system is based on VMAQ according to equation (7) and the amount of VM queue in use (VMQIU) according to the following equation (8):
VMUQ=VMAQ−VMQIU(8)
The maximum amount of efficiently usable queue (MAXEUQ) is based on the average amount of data I/O transferred over a given sampling period (AIO), the average time in queue (ATIQ) a queue hit ratio (QHR) and a queue compression ratio (QCR) according to the following equation (9):

M⁢⁢A⁢⁢X⁢⁢Q⁢⁢V⁢⁢M=A⁢⁢I⁢⁢O·A⁢⁢T⁢⁢I⁢⁢Q·Q⁢⁢C⁢⁢RQ⁢⁢H⁢⁢R(9)
The minimal queue usable by a VM (VMMINQU) is based on MAXEUQ according to equation (9) and the queue size factor (SF) according to the following equation (10):
VMMINQU=MAXEUQ*SF(10)

If a VM application normally tries to put large amounts of data in memory, it may be more efficient in many cases to have it swap memory to disk and have the queue monitor the swap file I/Os.

Although the systems and methods disclosed herein has been described in considerable detail with reference to certain preferred versions thereof, other versions and variations are possible and contemplated. Those skilled in the art should appreciate that they can readily use the disclosed conception and specific embodiments as a basis for designing or modifying other structures for carrying out the same purposes of the systems and methods disclosed herein without departing from the spirit and scope of the invention as defined by the appended claims.