Adaptive, Scalable I/O Request Handling Architecture in Virtualized Computer Systems and Networks

• US 20080104589A1
• Filed: 04/24/2007
• Published: 05/01/2008
• Est. Priority Date: 11/01/2006
• Status: Abandoned Application

• Current Assignee: Hyper9, Inc. (SolarWinds Corp.)
• Original Assignee: Hyper9, Inc. (SolarWinds Corp.)
• Inventors: Kellar, John Edward, McCrory, Dave Dennis
• Application Number:
  US11/739,426
• Publication Number:
  US 20080104589A1
• Time in Patent Office: Days
• US Class Current: 718/1
• CPC Class Codes: G06F 2009/45579 I/O management, e.g. providing access to device drivers or storage
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects

Abstract

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.

Claims

1. A method for processing input/output (I/O) requests in a computer system employing system virtualization in which each of multiple virtual machines operates in a logically independent manner using logically partitioned physical resources of the computer system, said method comprising:

receiving an I/O request from a virtual machine, wherein said I/O request is directed to a virtual hard drive (VHD) associated with said virtual machine; and

queuing data specified by said I/O request into an I/O data queue responsive to said I/O request, wherein said queuing comprises;

determining an entropy value of said specified I/O request data; and

encoding said specified I/O request data with said entropy value within said I/O data queue.

2. The method of claim 1, further comprising determining an absolute information redundancy value and a relative information redundancy value of said specified I/O request data.

3. The method of claim 2, further comprising utilizing said determined entropy, absolute information redundancy, and relative information redundancy to generate an identity function signature.

4. The method of claim 3, wherein said I/O data queue is one of multiple member I/O data queues within a set of virtual I/O channels, said method further comprising comparing said identity function signature of said specified I/O request data with identity function signatures of data stored in other of said multiple I/O data queues for performing delta compression within said VIOCs.

5. The method of claim 1, wherein the specified I/O request data comprises a data block having multiple data tokens, said determining an entropy value further comprising:

determining a relative entropy value of said data block in accordance with the frequency of occurrences of the data tokens; and

determining the redundancy of the data block from said relative entropy value.

6. The method of claim 5, further comprising responsive to the redundancy of the data block being greater than a specified threshold, compressing said data block.

7. The method of claim 6, wherein said compressing said data block further includes adaptively selecting a compression algorithm from among multiple different compression algorithms, said selecting among multiple compression algorithms comprising selecting a compression algorithm to compress said data block in accordance with processor cycles availability.

8. The method of claim 1, further comprising:

generating a sparse table of queue entries for said VHD upon initialization of said virtual machine, wherein each queue entry of said sparse table corresponds to a logical block address; and

populating each queue entry using said queuing step.

9. The method of claim 8, wherein said populating step comprises:

generating a linked list of variable size data blocks; and

utilizing a coherency protocol to maintain coherency across between linked lists, wherein said coherency protocol includes a committed and valid state and a committed and invalid state.

10. The method of claim 8, farther comprising adaptively adjusting memory space allocated to each queue entry in accordance with a rate of data flow into said queue entry, an average dwell time, a hit ratio for data in said queue entry, and an average compression ratio for data stored in said queue entry.

11. The method of claim 10, wherein said size of said queue entry is determined in accordance with the relation:

$\mathrm{AVGQ}=\frac{\mathrm{AVGIO}·<br><br>\mathrm{AVGTIQ}·<br><br>\mathrm{QCR}}{\mathrm{QHR}}$

wherein;

AVGQ is said size of said queue entry;

AVGIO is said rate of data flow into said queue entry;

AVGTIO is said average dwell time data;

QCR is said average compression ratio; and

,

QHR is said hit ratio.

12. The method of claim 1, further comprising, responsive to said I/O request resulting in a read miss, pre-fetching data into said I/O data queue.

13. The method of claim 12, wherein said pre-fetching comprises fetching a data block having an entropy value similar to the entropy value of said requested data.

14. The method of claim 13, wherein pre-fetching comprises fetching a data block based on a gap prediction.

15. A system for processing input/output (I/O) requests in a computer system employing system virtualization in which each of multiple virtual machines operates in a logically independent manner using logically partitioned physical resources of the computer system, said system comprising:

an interface that receives an I/O request from a virtual machine, wherein said I/O request is directed to a virtual hard drive (VHD) associated with said virtual machine; and

virtual I/O channels (VIOCs) that queue data specified by said I/O request into an I/O data queue responsive to said I/O request, wherein said VIOCs comprise an entropy encoding module that determines an entropy value of said specified I/O request data and encodes said specified I/O request data with said entropy value within said I/O data queue.

16. The system of claim 15, wherein said entropy encoding module determines a relative redundancy value and an absolute redundancy value of said specified I/O request data.

17. The system of claim 16, wherein said VIOCs further comprise an identity function module that utilizes said determined entropy, relative redundancy, and absolute redundancy to generate an identity function signature.

18. The system of claim 17, wherein said I/O data queue is one of multiple member I/O data queues within said VIOCs, said method further comprising comparing said identity function signature of said specified I/O request data with identity function signatures of data stored in other of said multiple I/O data queues for performing delta compression within said VIOCs.

19. The system of claim 15, wherein the specified I/O request data comprises a data block having multiple data tokens, wherein said entropy encoding module:

determines a relative entropy value of said data block in accordance with the frequency of occurrences of the data tokens; and

determines the redundancy of the data block from said relative entropy value.

20. The system of claim 19, further comprising a compression module that compresses said data block responsive to the redundancy of the data block being greater than a specified threshold.