Policy-based checkpointing fault tolerance across remote virtual machines

Embodiments include a checkpointing fault tolerance network architecture enables a first computer system to be remotely located from a second computer system. An intermediary computer system is situated between the first computer system and the second computer system to manage the transmission of checkpoint information from the first computer system to the second computer system in an efficient manner. The intermediary computer system responds to requests from the second computer system for updated data corresponding to memory pages selected by the second computer system, or memory pages identified through application of policy information defined by the second computer system.

BACKGROUND

As large-scale enterprises continue to adopt virtualization platforms as the foundation of their data centers, virtual machine (VM) fault tolerance has become an increasingly important feature to be provided by virtualization platform providers. Because a single host server in a virtualized data center can support multiple VMs, failure of that host server can bring down a multitude of services that were provided by the different VMs running on the failed host server. As such, virtualization platforms need to provide a mechanism to quickly resurrect a failed VM on a different host server so that the enterprise can maintain the quality of its service.

Currently, providing fault tolerance for a primary VM is typically achieved by providing a backup VM that runs on a server residing in a different “fault domain” from the server of the primary virtual machine. A fault domain can generally be described as a set of host servers in a data center (or data centers) that share a number of specified attributes and/or characteristics that results in a higher probability of failure of host servers in the fault domain upon a failure of one of the host servers in the fault domain. The attributes and/or characteristics utilized by an enterprise to define its data center fault domains depend upon the type of disasters and the level of recovery that the enterprises desire to achieve. For example, an enterprise may choose to define its fault domains based upon the physical proximity of host servers (storage rack location, geographic locations, etc.), the dependency of such servers on shared hardware (networked storage, power sources, physical connections, etc.) or software technologies (shared file systems, etc.), and the like. A well-constructed fault domain minimizes the correlation of a failure of a VM in one fault domain with the failure of another VM in a different fault domain.

VM fault tolerance may be provided using deterministic replay, checkpointing, or a hybrid of the two, which is disclosed in U.S. patent application Ser. No. 12/259,762, filed on Aug. 28, 2008, the entire contents of which are incorporated by reference herein. With replay techniques, essential portions of a primary VM's instruction stream (e.g., non-deterministic events within the primary VM's instruction stream) are captured in real-time (e.g., by a hypervisor layer or virtual machine monitor component of the primary VM) and transmitted to a backup VM (e.g., presumably located in a different fault domain) to “replay” the primary VM's execution in a synchronized fashion. If the primary VM fails, the backup VM can then take over without discernible loss of time. While replay techniques provide a robust fault tolerance solution with fast recovery times, they are less viable, for example, when non-deterministic events become more frequent or more difficult to identify within instruction streams, as is the case with virtual machines that support SMP (symmetric multiprocessing) architectures with multiple virtual CPUs.

In contrast to replay techniques, checkpointing based fault tolerance techniques are more flexible in their capabilities to support a variety of virtual architectures, including SMP-based virtual machines. Techniques for generating and using checkpoints in a virtual computer system are disclosed in U.S. Pat. No. 7,529,897, the entire contents of which are incorporated by reference herein. With checkpointing, the primary VM is periodically stunned (i.e., execution is temporarily halted) during the course of execution (each such stun period referred to as a “checkpoint”) to determine any modifications made to the state of the primary VM since a prior checkpoint. Once such modifications are determined, they are transmitted to the backup VM which is then able to merge the modifications into its current state, thereby reflecting an accurate state of the primary VM at the time of the checkpoint. Only upon notification of a failure of the primary VM does the backup VM begin running, by loading the stored state of the primary VM into its own execution state. However, due to the potentially large size of checkpoint information (e.g., multiple gigabytes) in a transmitted state and the need to stun the primary VM at periodic checkpoints to transmit such state to the backup VM, the backup VM must be networked to the primary VM with sufficiently high bandwidth such that the stun period is not prolonged by network bandwidth limitations. This constraint currently restricts the ability to locate backup VMs in locations that are geographically distant from the primary VM or otherwise in a manner in which backup VMs are connected to primary VMs using network connections having insufficient bandwidth capacity to effectively transmit checkpoint information.

SUMMARY

One or more embodiments of the present invention enable a backup VM that receives checkpointing information to be remotely located from a primary VM. Such embodiments situate an intermediary computer system between the primary VM and the backup VM to manage the transmission of checkpoint information to the backup VM in an efficient manner. In some embodiments, the intermediary computer system is networked to the primary VM through a high bandwidth connection but is networked to the backup VM through a lower bandwidth connection. During each checkpoint, the intermediary computer system receives and stores updated data from the primary VM that corresponds to memory pages in the state of the primary VM that have been modified since a previous checkpoint.

One or more embodiments described herein transmit an updated state of a first computer system to a second computer system through an intermediary computer system. The intermediary computer system receives checkpoint information packets from the first computer system. Each checkpoint information packet includes updated data corresponding to one or more memory pages of the first computer system that have been modified since a previously received checkpoint information packet. The intermediary computer system provides the second computer system with data describing the memory pages and receives, from the second computer system, a request for a copy of at least one of the memory pages. The intermediary computer system transmits the requested copy of the memory pages to the second computing device.

Alternatively or in addition, the second computer system defines policy information describing one or more of the memory pages to select. The intermediary computing system applies the defined policy information to select the memory pages and transmits to the second computing system the selected memory pages.

This summary introduces a selection of concepts that are described in more detail below. This summary is not intended to identify essential features, nor to limit in any way the scope of the claimed subject matter.

DETAILED DESCRIPTION

Embodiments described herein provide updated state of a first computer system802to a second computer system806via an intermediary computer system115to provide fault tolerance for first computer system802. In some embodiments, the updated state corresponds to checkpoint information packets including data describing memory pages of a plurality of virtual machines (VMs) executing on first computer system802.

In some aspects, intermediary computer system115pushes the memory pages to second computer system806. In other aspects, second computer system806pulls the memory pages from intermediary computer system115by selectively requesting particular memory pages. For example, as described below with reference toFIG. 6andFIG. 6, intermediary computer system115responds to requests from second computer system806for updated data relating to particular memory pages. Second computer system806may also develop and send policy information to intermediary computer system115that describes the memory pages of interest to the second computing device. The pull embodiments enable, for example, scalability to a plurality of second computer systems806as well as better efficiency.

Still other aspects contemplate both push and pull environments. For example, in a push and pull hybrid environment, intermediary computer system115pushes some memory pages to second computer system806as described with reference toFIG. 2andFIG. 3while second computer system806also pulls some memory pages from intermediary computer system115as described with reference toFIG. 6andFIG. 7.

FIG. 1Adepicts a block diagram of an embodiment of a network architecture for a primary and backup virtual machine using intermediary computer system115. A primary VM100resides on a primary server105in a fault domain110of a data center. One example of a primary server105that supports virtual machines is a server that runs VMware's ESX™ hypervisor product, which is commercially available from VMware, Inc. of Palo Alto, Calif. (although it should be recognized that any virtualization technologies may be used consistent with the teachings herein, including Xen®, Microsoft Hyper-V and the like). An intermediary computer system115(hereinafter, “intermediary”) is situated in close enough proximity to server105such that a high bandwidth connection120can be placed between server105and intermediary115. High bandwidth connection120, as described further below, provides sufficient bandwidth capacity to support the transmission of checkpoint information between primary VM100and intermediary115during primary VM's100execution. For example, in one embodiment, high bandwidth connection120provides sufficient bandwidth capacity for intermediary115to efficiently receive checkpoint information from the primary VM100at a rate of 50 to 100 times per second, with each set of checkpoint information potentially comprising multiple gigabytes of data. Although intermediary115is located at a sufficient physical proximity to primary VM100to enable high bandwidth connection120, intermediary115is also located in a different fault domain125than fault domain110of primary VM100, such that a failure of primary VM100(or server105) is not correlated to (or otherwise does not have a significant correlation to) a failure of intermediary115. As further depicted inFIG. 1A, a backup VM130resides on a backup server135that shares fault domain125with intermediary115. A lower bandwidth connection140between intermediary115and backup VM130provides flexibility to situate backup VM130in a location geographically remote from intermediary115and/or primary VM100.

In some embodiments, primary server105and backup server135are referred to as first computer system802(or first computing system) and second computer system806(or second computing system), respectively.

FIG. 1Bdepicts a block diagram of a second embodiment of a network architecture for a primary and backup virtual machine using intermediary computer system115. As depicted inFIG. 1B, intermediary115and backup VM130on backup server135reside in different fault domains125and145, respectively. For example, in one embodiment, primary VM100resides on blade primary server105which also comprises fault domain110. Intermediary115is a second blade server utilizing the same chassis as blade primary server105but comprises a different fault domain125. Intermediary115may be placed on top of the chassis, for example, to protect against flood damage that may affect blade primary server105which is placed on the bottom of the chassis (e.g., such that blade primary server105and the intermediary115exhibit different failure characteristics resulting in different fault domains110and125, respectively). High bandwidth connection120, in such an embodiment, may be facilitated by the PCI-e backplane of the chassis. Backup VM130on backup server135may be located in geographically remote location in this embodiment. For example, if primary VM100and intermediary115are located in a data center in Palo Alto, Calif., backup VM130may be located in a different data center in Boston, Mass. In another embodiment, intermediary115may be located at the edge of a subnet, for example, as a modified NIC or a router or other edge device, for consolidation in management. Alternatively, the functionality of intermediary115may be implemented within primary server105itself, for example, set in a relatively more reliable part of the processor or motherboard of primary server105.

FIG. 2depicts a flow diagram for transmitting an updated state of a primary virtual machine to a backup virtual machine using intermediary computer system115. In one embodiment, primary server105, which hosts primary VM100, includes a checkpointing module (or other checkpointing functionality) in its hypervisor. As further detailed below, such a checkpointing module transmits checkpoint information packets over high bandwidth connection120to intermediary115at each checkpoint. Each checkpoint information packet includes information reflecting changes in the state of primary VM's100memory (and emulated devices, in certain embodiments) from the previously transmitted checkpoint information packet. In one embodiment, transmission of checkpoint information packets by the hypervisor of primary server105occurs, for example, approximately at a rate of 50 to 100 times per second.

In step200, the hypervisor of primary server105instantiates primary VM100. In step202, the hypervisor of primary server105takes an initial snapshot of the state of primary VM100and transmits the snapshot to intermediary115. The initial snapshot comprises a plurality of memory pages that make up the state of memory (and, in certain embodiments, the state of emulated devices) of primary VM100. For example, in one embodiment, each memory page has a size of 4 KB such that a primary VM100configured with a virtual RAM of 4 GB would have an initial snapshot size of approximately 1 million memory pages. In an embodiment utilizing VMware's ESX™ virtualization platform, VMware's VMotion technology can be used to create and transmit such an initial snapshot. In step204, intermediary115receives and stores the initial snapshot. In step206, the hypervisor of primary VM100initiates a timer to periodically trigger the initiation of checkpoints to generate checkpoint information packets (e.g., 50 to 100 times a second, etc.). Prior to the expiration of the timer, in step208, the hypervisor delays and queues any and all outbound network packets generated by primary VM100.

Once the timer expires in step210, the hypervisor initiates a checkpoint by stunning primary VM100(i.e., freezes its execution state) in step212and generates a checkpoint information packet reflecting the current state of stunned primary VM100and transmits the checkpoint information packet to intermediary115in step214. In one embodiment, the checkpoint information packet comprises a subset of the memory pages (or portions thereof) of the initial snapshot that have been updated during execution of primary VM100since a previously transmitted checkpoint information packet (or since the initial snapshot for a first checkpoint information packet). It should be recognized that a variety of techniques may be utilized to identify updated memory pages in primary VM100including, for example, leveraging hardware that may be available on primary server105for detecting such modified pages through hardware controlled dirty bits of page tables and page directories used for memory virtualization. In step216, intermediary115successfully receives the transmitted checkpoint information packet and in step218transmits an acknowledgement of successful receipt back to primary server105. Once the hypervisor of primary server105receives the transmitted acknowledgement in step220, the hypervisor resumes execution of primary VM100in step222and releases all the queued up network packets (from step208) in step224before returning back to step208. Delaying and queuing the outbound network packets in step208and releasing them only after receiving acknowledgement from intermediary115of receipt of a checkpoint information packet in step220ensures that restoration of primary VM100by backup server135upon a failure of primary VM100is based on a state of primary VM100that can properly resume network communications with external entities (i.e., re-transmit outbound network packets since the recovered state without confusing recipients, re-receive inbound network packets that it is expecting, etc.).

Meanwhile, in step226, intermediary115updates its stored snapshot of the state of primary VM100with the updated memory pages (or portions thereof) in the checkpoint information packet received in step216. Simultaneously with its continuous receipt of checkpoint information packets and updates to its stored snapshot of the state of primary VM100in steps216and226, intermediary115also continuously (e.g., via a separate running process or thread, etc.) determines and transmits those received memory pages that have been modified less or least recently by primary VM100to backup server135in step228(such less or least recently modified memory pages referred to herein as “cold” memory pages). In step230, the hypervisor of backup server135receives these cold memory pages and, in step232, incorporates the cold memory pages into its reconstructed state of primary VM100for backup VM130. It should be recognized that the reconstructed state of primary VM100maintained by backup VM130may not necessarily reflect a completed state of any particular past “checkpointed” state of primary VM100since intermediary115, in step228, only transmits “cold” memory pages to backup server135. That is, memory pages that are considered “hotter” by intermediary115(i.e., modified more recently), even if needed to provide backup server135a complete set of memory pages reflecting the state of primary VM100at a particular checkpoint, are held back and not transmitted to backup server135. Holding back such hotter memory pages conserves the limited bandwidth capacity of lower bandwidth connection140between intermediary115and backup server135, based upon a presumption that the hotter memory pages will be again modified before backup VM130needs to take any action due to a failure of primary VM100.

If, in step234, intermediary115detects a failure of primary VM100(or is otherwise notified thereof), then in step236, intermediary115notifies backup server135of the failure of primary VM100and transmits any unsent memory pages of its stored snapshot of primary VM100to backup server135. In step238, backup server135receives notification of the failure of primary VM100and the memory pages and, in step240, incorporates the received memory pages into its reconstructed state for primary VM100and resumes execution of primary VM100as backup VM130.

FIG. 3depicts a data structure for transmitting cold memory pages at intermediary computer system115. In one embodiment, intermediary115, in contrast to primary server105and backup server135which run virtualization platforms, is a non-virtualized computer system running one or more processes (e.g., or threads, etc.) that receives checkpoint information packets from primary server105and transmits memory pages to backup server135as based upon information maintained in a data structure300(although it should be recognized that intermediary115may also be implemented in a virtual machine in alternative embodiments). As depicted inFIG. 3, data structure300is an array of entries that each correspond to one of memory pages0to N−1 that comprise the initial snapshot of primary VM100(see, e.g., step202ofFIG. 2). Each such entry comprises a reference field302(e.g., address pointer) to a location in intermediary's115memory that stores a copy of the memory page received from primary server105and a checkpoint number field304indicating the checkpoint (represented as an epoch or chronological number) in which intermediary115received its current copy of the memory page.

A thread, referred to as receive thread306, manages the receipt of memory pages of primary VM100from primary server105(e.g., from the initial snapshot in step202as well as from each subsequent checkpoint information packet in step214). In step308, for each memory page received from primary server105via high bandwidth connection120, receive thread306stores the memory page in the memory of intermediary115. In step310, receive thread306inserts the storage address of the stored memory page into the reference field302of the entry in data structure300corresponding to the received memory page. In step312, receive thread306updates the checkpoint number field304of the entry with the current checkpoint number.

A simultaneously running thread, referred to as transmit thread314, manages the transmission of “cold” memory pages (e.g., least recently modified) to backup server135as described in step228ofFIG. 2(via low bandwidth connection140). Transmit thread314maintains a checkpoint variable316indicating a checkpoint number that transmit thread314is currently operating upon as well as a current array index318that indicates the current entry in data structure300upon which transmission thread314is operating during its execution. Checkpoint variable316is initialized to zero (e.g., the value of checkpoint number field304in each entry of data structure300when such entry corresponds to the memory page received from the initial snapshot received in step204ofFIG. 2) and current array index318is initialized to the index of the first entry of data structure300(e.g., index of zero). Transmit thread314begins with the first entry of data structure300(e.g., entry for memory page0) and if such entry's checkpoint number field304matches checkpoint variable316in step320, then in step322, transmit thread314begins transmitting the memory page (i.e., such memory page being a “cold” memory page) referenced in the entry's reference field302to backup server135through lower bandwidth connection140. In step324, upon receiving an acknowledgment from backup server135of successful receipt of the memory page, transmit thread314determines whether current array index318represents the index of the last entry of data structure300. If transmit thread314determines that current array index318represents the index of the last entry in data structure300, then in step326, transmit thread314increments checkpoint variable316, resets current array index318to the index of the first entry of data structure300(e.g., index of zero), and returns to the beginning of data structure300. Otherwise, transmit thread314increments current array index318and moves to the next entry in data structure300in step328.

If, in step330, transmit thread314receives notification of a failure of primary VM100, then in step332, transmit thread314traverses through data structure300, transmitting memory pages referenced in each entry (a) whose checkpoint number304is greater than checkpoint variable316, or (b) whose checkpoint number304equals checkpoint variable316and whose index is greater than or equal to current array index318(i.e., indicating that the memory page has not yet been transmitted to backup server135). In one embodiment, upon receiving notification of a failure of primary VM100in step330, transmit thread314begins to transmit the “hotter” memory pages first, by transmitting those memory pages having the highest values in their checkpoint number fields304, in an effort to enable backup VM130to start execution prior to receiving all unsent memory pages in the snapshot, under a presumption, for example, that the hotter memory pages are more likely to be accessed during subsequent execution of backup VM130than colder memory pages.

It should be recognized that transmit thread314may traverse data structure300and transmit cold memory pages to backup server135at a significantly slower rate due to lower bandwidth connection140than the rate that receive thread308receives and updates memory pages at each checkpoint through high bandwidth connection120. As such, the value of checkpoint variable316remains lower than the actual current checkpoint number of checkpoint information packets received by receive thread306. By holding back hotter memory pages and transmitting cold memory pages, intermediary115thus reduces the possibility that the bandwidth capacity of lower bandwidth connection140will be wasted on transmission of memory pages that would likely be overwritten with updated data in the near future (i.e., fewer memory pages are transmitted by intermediary115than are received).

It should be recognized that data structure300and techniques described inFIG. 3are merely exemplary and that a variety of alternative data structures and techniques that may be utilized to determine whether memory pages are “cold” (i.e., with a different conception of how “cold” may be defined or assessed). For example, in an alternative embodiment ofFIG. 3may include a transmission bit in each entry of data structure300which would indicate whether the memory page corresponding to the entry has already been transmitted to backup VM130. Another alternative embodiment utilizes an array of entries indexed by memory pages of the primary VM's snapshot (similar to data structure300), where each entry in the array comprises a reference to the stored memory page (similar to reference field302) and a counter value. In such an embodiment, a receive thread increments the counter value for an entry each time a received checkpoint information packet includes a corresponding updated memory page. Simultaneously, a transmit thread continually cycles through the array and transmits memory pages corresponding to entries that have a pre-specified low counter value. Such an embodiment utilizes the concept of least frequently modified memory pages to define “cold” rather than least recently modified. Yet another alternative embodiment utilizes a data structure that maintains a list of checkpoint numbers for each memory page corresponding to the checkpoints in which such memory page was updated. Such a data structure provides flexibility to specify or define “cold” memory pages in a variety of ways, such as, for example, memory pages with the smallest list of checkpoint numbers or memory pages that have remained unchanged for a consecutive number of checkpoints (e.g., least frequently modified or least recently modified, etc.).

An exemplary host computing device for implementing embodiments disclosed herein is next described.

FIG. 4is a block diagram of an exemplary host computing device400. The functionality of each of first computer system802, intermediary computer system115, and second computer system806may be implemented by a computing device such as host computing device400.

Host computing device400represents any computing device that includes a processor402for executing instructions. For example, host computing device400may represent a group of processing units or other computing devices such as in a cloud computing configuration. Processor402includes any quantity of processing units, and is programmed to execute computer-executable instructions for implementing aspects of the disclosure. The instructions may be performed by processor402or by multiple processors executing within host computing device400, or performed by a processor or by multiple processors external to host computing device400. In some embodiments, executable instructions are stored in a memory404. Memory404is any device allowing information, such as executable instructions and/or other data, to be stored and retrieved. Memory404includes any quantity of computer-readable media associated with or accessible by host computing device400. Memory404, or portions thereof, may be internal to host computing device400, external to host computing device400, or both. For example, memory404may include one or more random access memory (RAM) modules, flash memory modules, hard disks, solid state disks, and/or optical disks.

Host computing device400may include a user interface device410for receiving data from a user408and/or for presenting data to user408. User408may interact indirectly with host computing device400via another computing device such as VMware's vCenter Server or other management device. User interface device410may include, for example, a keyboard, a pointing device, a mouse, a stylus, a touch sensitive panel (e.g., a touch pad or a touch screen), a gyroscope, an accelerometer, a position detector, and/or an audio input device. In some embodiments, user interface device410operates to receive data from user408, while another device (e.g., a presentation device) operates to present data to user408. In other embodiments, user interface device410has a single component, such as a touch screen, that functions to both output data to user408and receive data from user408. In such embodiments, user interface device410operates as a presentation device for presenting information to user408. In such embodiments, user interface device410represents any component capable of conveying information to user408. For example, user interface device410may include, without limitation, a display device (e.g., a liquid crystal display (LCD), organic light emitting diode (OLED) display, or “electronic ink” display) and/or an audio output device (e.g., a speaker or headphones). In some embodiments, user interface device410includes an output adapter, such as a video adapter and/or an audio adapter. An output adapter is operatively coupled to processor402and configured to be operatively coupled to an output device, such as a display device or an audio output device.

Host computing device400also includes a network communication interface412, which enables host computing device400to communicate with a remote device (e.g., another computing device) via a communication medium, such as a wired or wireless packet network. For example, host computing device400may transmit and/or receive data via network communication interface412. User interface device410and/or network communication interface412may be referred to collectively as an input interface and may be configured to receive information from user408.

Host computing device400further includes a storage interface416that enables host computing device400to communicate with one or more of datastores316, which store virtual disk images, software applications, and/or any other data suitable for use with the methods described herein. In exemplary embodiments, storage interface416couples host computing device400to a storage area network (SAN) (e.g., a Fibre Channel network) and/or to a network-attached storage (NAS) system (e.g., via a packet network). The storage interface416may be integrated with network communication interface412.

FIG. 5depicts a block diagram of virtual machines5351,5352. . .535Nthat are instantiated on host computing device400, which may be referred to as a host computing device or simply host314. Host computing device400includes a hardware platform205, such as an x86 architecture platform. Hardware platform205may include processor402, memory404, network communication interface412, user interface device410, and other input/output (I/O) devices, such as a presentation device106(shown inFIG. 4). A virtualization software layer, also referred to hereinafter as a hypervisor510, is installed on top of hardware platform205.

The virtualization software layer supports a virtual machine execution space530within which multiple virtual machines (VMs5351-535N) may be concurrently instantiated and executed. Hypervisor510includes a device driver layer515, and maps physical resources of hardware platform205(e.g., processor402, memory404, network communication interface412, and/or user interface device410) to “virtual” resources of each of VMs5351-535Nsuch that each of VMs5351-535Nhas its own virtual hardware platform (e.g., a corresponding one of virtual hardware platforms5401-540N), each virtual hardware platform having its own emulated hardware (such as a processor545, a memory550, a network communication interface555, a user interface device560and other emulated I/O devices in VM5351). Hypervisor510may manage (e.g., monitor, initiate, and/or terminate) execution of VMs5351-535Naccording to policies associated with hypervisor510, such as a policy specifying that VMs5351-535Nare to be automatically restarted upon unexpected termination and/or upon initialization of hypervisor510. In addition, or alternatively, hypervisor510may manage execution VMs5351-535Nbased on requests received from a device other than host computing device400. For example, hypervisor510may receive an execution instruction specifying the initiation of execution of first VM5351from a management device via network communication interface412and execute the execution instruction to initiate execution of first VM5351.

In some embodiments, memory550in first virtual hardware platform5401includes a virtual disk that is associated with or “mapped to” one or more virtual disk images stored on a disk (e.g., a hard disk or solid state disk) of host computing device400. The virtual disk image represents a file system (e.g., a hierarchy of directories and files) used by first VM5351in a single file or in a plurality of files, each of which includes a portion of the file system. In addition, or alternatively, virtual disk images may be stored on one or more remote computing devices, such as in a storage area network (SAN) configuration. In such embodiments, any quantity of virtual disk images may be stored by the remote computing devices.

Device driver layer515includes, for example, a communication interface driver520that interacts with network communication interface412to receive and transmit data from, for example, a local area network (LAN) connected to host computing device400. Communication interface driver520also includes a virtual bridge525that simulates the broadcasting of data packets in a physical network received from one communication interface (e.g., network communication interface412) to other communication interfaces (e.g., the virtual communication interfaces of VMs5351-535N). Each virtual communication interface for each VM5351-535N, such as network communication interface555for first VM5351, may be assigned a unique virtual Media Access Control (MAC) address that enables virtual bridge525to simulate the forwarding of incoming data packets from network communication interface412. In an embodiment, network communication interface412is an Ethernet adapter that is configured in “promiscuous mode” such that all Ethernet packets that it receives (rather than just Ethernet packets addressed to its own physical MAC address) are passed to virtual bridge525, which, in turn, is able to further forward the Ethernet packets to VMs5351-535N. This configuration enables an Ethernet packet that has a virtual MAC address as its destination address to properly reach the VM in host computing device400with a virtual communication interface that corresponds to such virtual MAC address.

Virtual hardware platform5401may function as an equivalent of a standard x86 hardware architecture such that any x86-compatible desktop operating system (e.g., Microsoft WINDOWS brand operating system, LINUX brand operating system, SOLARIS brand operating system, NETWARE, or FREEBSD) may be installed as guest operating system (OS)565in order to execute applications570for an instantiated VM, such as first VM5351. Virtual hardware platforms5401-540Nmay be considered to be part of virtual machine monitors (VMM)5751-575Nthat implement virtual system support to coordinate operations between hypervisor510and corresponding VMs5351-535N. Those with ordinary skill in the art will recognize that the various terms, layers, and categorizations used to describe the virtualization components inFIG. 5may be referred to differently without departing from their functionality or the spirit or scope of the disclosure. For example, virtual hardware platforms5401-540Nmay also be considered to be separate from VMMs5751-575N, and VMMs5751-575Nmay be considered to be separate from hypervisor510. One example of hypervisor510that may be used in an embodiment of the disclosure is included as a component in VMware's ESX brand software, which is commercially available from VMware, Inc.

For the operations illustrated and described with reference toFIG. 6andFIG. 7, first computer system802may correspond to a first server hosting a primary virtual machine and second computer system806may correspond to a second server hosting a backup virtual machine. In such an example, the first server may reside in a first fault domain while the second server resides in a second fault domain. Further, second computer system806may be networked to intermediary computer system115through a bandwidth connection (e.g., a low bandwidth connection) that does not support timely transmission of modified states of first computer system802received by intermediary computer system115at checkpoints.

FIG. 6is a flowchart of an exemplary method600performed by intermediary computer system115to transmit an updated state of first computer system802to second computer system806in response to a request from second computer system806. While method600is described with reference to execution by intermediary computer system115, it is contemplated that method600may be performed by any computing device. Further, one or more of the operations may be performed by different threads on intermediary computer system115.

Further, the operations illustrated inFIG. 6may be implemented as computer-executable instructions stored on one or more computer-readable storage media. The instructions, when executed by a processor of intermediary computer system115, cause the processor to transmit an updated state of first computer system802to second computer system806. In some embodiments, second computer system806is networked to intermediary computer system115through a low bandwidth connection that does not support timely transmission of modified states of first computer system802received by intermediary computer system115at checkpoints.

At602, intermediary computer system115receives checkpoint information packets from first computer system802. Each checkpoint information packet has updated data corresponding to one or more memory pages of first computer system802that have been modified since a previously received checkpoint information packet. In some embodiments, intermediary computer system115receives the checkpoint information packets periodically through a high bandwidth connection with first computer system802.

In some embodiments, intermediary computer system115maintains an array of entries corresponding to each memory page received from first computer system802. Each entry of the array includes a reference to a copy of the corresponding memory page stored in intermediary computer system115, and a checkpoint number identifying a checkpoint at which the copy was received by intermediary computer system115.

At604, intermediary computer system115provides second computer system806with data describing the memory pages stored at intermediary computer system115. In some embodiments, intermediary computer system115publishes the data for access by second computer system806. For example, intermediary computer system115publishes information about dirty memory pages (e.g., modified or changed memory pages) and the coldness of each memory page. The coldness may be based on how long ago the memory page was modified or how frequently the page is being modified. In general, publishing the data includes, for example, publishing one or more of the following for each of the memory pages: a memory page identifier, a time-based age of the memory page, a frequency of modification for the memory page, and a recency of modification to the memory page. Intermediary computer system115may also provide an application programming interface (API) to enable second computer system806to request one or more of the memory pages from intermediary computer system115. For example, the API may include a call in which the memory page identifier is an argument.

Second computer system806analyzes or otherwise processes the data to identify memory pages of interest to second computer system806. Second computer system806may then request particular memory pages from intermediary computer system115. For example, if intermediary computer system115receives from second computer system806a request for a copy of at least one of the memory pages at606, intermediary computer system115transmits the requested copy of the memory page to the second computing device at608.

Alternatively or in addition, second computer system806may define policy information describing the type or kind of memory pages of interest to second computer system806. The policy information includes factors or criteria for use in identifying the memory pages of interest. The factors or criteria include, for example, quantities of one or more of the following: memory pages per epoch, dirty pages (e.g., changed pages), guest pages, user pages, supervisor pages, large pages (e.g., more than four kilobytes), and the like. Second computer system806provides the policy information to intermediary computer system115. Intermediary computer system115receives and applies the policy information to select, track, and/or monitor memory pages matching the criteria specified in the policy information. Intermediary computer system115collects data describing the selected, tracked, and/or monitored memory pages.

Alternatively or in addition to transmitting the updated state of first computer system802to second computer system806on demand as requested by second computer system806as illustrated inFIG. 6, intermediary computer system115may automatically transmit the updated state (e.g., without a request from second computer system806). For example, intermediary computer system115may periodically determine whether the one or more memory pages stored at intermediary computer system115have been updated by first computer system802and have not been transmitted to second computer system806. If so, intermediary computer system115transmits to second computer system806, without a request from second computer system806, the updated data corresponding to a memory page determined to be a least recently updated memory page. Determining whether any of the memory pages have been least recently updated includes, for example, traversing entries in an array storing received memory pages to compare a current checkpoint variable with the checkpoint number of each entry of the array. If the checkpoint number of the entry equals the current checkpoint variable, intermediary computer system115identifies the memory page corresponding to that entry as a least recently updated memory page. After analyzing a last entry in the array, intermediary computer system115increments the current checkpoint variable and immediately or subsequently proceeds to re-traverse the array. In some embodiments, the identified memory pages are then transmitted to second computer system806. If updated data corresponding to a plurality of unsent memory pages is to be sent to second computer system806, intermediary computer system115sends the memory pages that have been least recently modified first.

Similarly, intermediary computer system115may periodically determine whether the one or more memory pages stored at intermediary computer system115have been updated by first computer system802and have not been transmitted to second computer system806. If so, intermediary computer system115transmits to second computer system806, without a request from second computer system806, the updated data corresponding to a memory page determined to be a least frequently updated memory page.

FIG. 7is a flowchart of an exemplary method700performed by second computer system806to request an updated state of first computer system802from intermediary computer system115based on the policy information. While method700is described with reference to execution by second computer system806, it is contemplated that method700may be performed by any computing device. Further, one or more of the operations may be performed by different threads on second computer system806.

At702, second computer system806receives or otherwise accesses data defining the memory pages available at the intermediary computing device. The data includes, for example, the published data described above with reference toFIG. 6. At704, second computer system806defines policy information. As described herein, the policy information includes factors or criteria for use in identifying the memory pages of interest.

At706, second computer system806sends the defined policy information to intermediary computer system115. Intermediary computer system115applies the policy information to select, track, or monitor particular memory pages. Intermediary computer system115sends updated data corresponding to the selected memory pages stored at intermediary computer system115to second computer system806. At708, second computer system806receives the updated data from intermediary computer system115.

In some embodiments, second computer system806may specify in the policy information, or request explicitly, copies of the same memory page corresponding to different times or time intervals. For example, second computer system806may request a copy of a particular memory page before application of a root toolkit and a copy of the same particular memory page after application of the root toolkit. Upon receipt of the two (or more) copies of the same particular memory page, second computer system806compares the received copies to identify differences in the copies. This enables second computer system806to analyze the effects of applying the root toolkit.

FIG. 8is a block diagram of intermediary computer system115transmitting pages to a plurality of second computer systems806. In some embodiments, intermediary computer system115receives pages from first computer system802and transmits the pages to a plurality of second computer systems806over time, as described herein. Intermediary computer system115is independent of each of the different types of second computer systems806(e.g., heterogeneous), in some embodiments.

Intermediary computer system115maintains information describing the pages stored by intermediary computer system115. Similarly, each of second computer systems806maintains information describing the pages stored by that second computer system806. The information may be stored in any format and in any data structure. In the example ofFIG. 8, the information is stored in tables. An exemplary table correlates each page number to a checkpoint identifier (ID), version number, epoch number, transfer time, or other means for identifying the version of the page represented by the page number.

The table maintained by intermediary computer system115correlates page numbers associated with a plurality of the pages stored by intermediary computer system115with checkpoint IDs. In some embodiments, intermediary computer system115updates the table as the pages are received from first computer system802and stored by intermediary computer system115.

The tables maintained by second computer systems806correlate page numbers associated with a plurality of the pages stored by second computer systems806with checkpoint IDs. In some embodiments, each table is initially empty, and then populated over time by second computer system806maintaining the table as pages are received from intermediary computer system115. For example, second computer system806may request pages from intermediary computer system115on a page-by-page basis and thus update the table on a page-by-page basis.

Alternatively or in addition, second computer system806may receive a snapshot of the table stored by intermediary computer system115. From the table, second computer system806selects one or more pages to request from intermediary computer system115based on the recency of modification of the pages, frequency of modification of the pages, and/or other policy. Second computer system806requests the selected pages from intermediary computer system115.

Intermediary computer system115transmits the requested pages to intermediary computer system115individually or as a batch of pages. For example, depending on a cost of the link between intermediary computer system115and second computer system806, transmission of the pages from intermediary computer system115to second computer system806can be throttled. The cost of the link may be defined as available bandwidth, financially, in terms of latency, or any other measure.

As an example and as shown inFIG. 8, the table or map obtained by second computer system806indicates that Page X is at Checkpoint ID5. Second computer system806requests Page X from intermediary computer system115, but receives Page X with Checkpoint ID10from intermediary computer system115because Checkpoint ID10is the latest version of Page X. For example, the table or map maintained by second computer system806became out-of-date because of a delay between the snapshot request and the request for Page X. Second computer system806stores the received Page X and updates the table to reflect that the stored version or generation of Page X is Checkpoint ID10. Page X stored by second computer system806is thus a coherent copy of Page X stored by intermediary computer system115with respect to page number and checkpoint ID.

Similarly, the table or map obtained by second computer system806indicates that Page Z is at Checkpoint ID1. Second computer system806requests Page Z from intermediary computer system115, but receives Page Z with Checkpoint ID2from intermediary computer system115because Checkpoint ID2is the latest version of Page Z. Second computer system806stores the received Page Z and updates the table to reflect that the stored version of Page Z is Checkpoint ID2.

After receiving the initial snapshot of the table maintained by intermediary computer system115and receiving the selected pages and updating the table, second computer system806may subsequently request another snapshot of the table stored by intermediary computer system115. Second computer system806compares this later snapshot with the table currently maintained by second computer system806to identify those pages that have changed (e.g., with different checkpoint IDs). Second computer system806then requests updated versions of those changed pages from intermediary computer system115. In this manner, second computer system806only updates those pages that have changed (e.g., dirty pages) since the last iteration.

The table maintained by intermediary computer system115may include other columns not shown or described herein, but only transmit selected columns based on the request from second computer system806. As such, intermediary computer system115may dynamically create maps, tables, or snapshots on the fly.

Alternatively or in addition, intermediary computer system115may provide additional information from its table that has not been requested by second computer system806. For example, intermediary computer system115may proactively send to second computer system806copies of pages that have been recently requested by other second computer systems806. In this manner, intermediary computer system115optimizes page transmission based on the likelihood of relevancy of the pages to second computer system806. Page transmission may also be optimized based on the cost of the link between intermediary computer system115and second computer system806(e.g., transmit additional pages if the added cost is minimal or reasonable).

Additional Examples

The following scenarios are merely exemplary and not intended to be limiting in any way.

In one scenario, first computer system802fails at some point in time. Upon detection of the failure by intermediary computer system115or notification to intermediary computer system115, intermediary computer system115transmits to second computer system806the updated data corresponding to each unsent memory page stored at intermediary computer system115. In this manner, second computer system806is then able to move from acting as a backup or secondary system to acting as first computer system802. For example, upon failure of first computer system802, intermediary computer system115sends an evacuate signal to second computer system806. Second computer system806requests copies of each of the memory pages stored by intermediary computer system115that have not yet been transmitted to second computer system806. Upon the receipt of such a request, intermediary computer system115transmits the requested copies of the memory pages to second computer system806.

In another example, intermediary computer system115responds to requests from a plurality of second computer systems806. In such an example, intermediary computer system115may identify request patterns among the plurality of second computer systems806. Exemplary request patterns include, but are not limited to, page-based patterns (e.g., second computer systems806requesting similar sets of memory pages) and time-based patterns (e.g., second computer systems806requesting similar sets of memory pages at approximately the same time). Based on the request patterns, intermediary computer system115proactively shares copies of memory pages requested by one of second computer systems806with other second computer systems806(e.g., in anticipation of receiving similar requests from these other second computer systems806).

Exemplary Operating Environment

It should be recognized that various modifications and changes may be made to the specific embodiments described herein without departing from the broader spirit and scope of the invention as set forth in the appended claims. For example, while the foregoing discussions have focused on embodiments in which primary server105and intermediary115transmitting complete memory pages (if such memory page has been modified), it should be recognized that alternative embodiments may apply difference techniques or other compression techniques on memory pages at either or both of primary server105and intermediary115prior to their transmission. Such alternative embodiments may thus transmit only updated data corresponding to the memory pages rather than the complete memory pages themselves. Similarly, it should be recognized that although the foregoing embodiments have discussed a single intermediary115, embodiments may incorporate multiple intermediaries, possible in different fault domains, such that probability of failure of all intermediaries is negligible. Additionally, while the foregoing embodiments have been generally described using primary and backup VMs, other primary and backup computer systems, including non-virtualized systems, may be used consistent with the teachings herein.

The operations described herein may be performed by a computer or computing device. The computing devices communicate with each other through an exchange of messages and/or stored data. Communication may occur using any protocol or mechanism over any wired or wireless connection. A computing device may transmit a message as a broadcast message (e.g., to an entire network and/or data bus), a multicast message (e.g., addressed to a plurality of other computing devices), and/or as a plurality of unicast messages, each of which is addressed to an individual computing device. Further, in some embodiments, messages are transmitted using a network protocol that does not guarantee delivery, such as User Datagram Protocol (UDP). Accordingly, when transmitting a message, a computing device may transmit multiple copies of the message, enabling the computing device to reduce the risk of non-delivery.

Aspects of the disclosure transform a general-purpose computer into a special-purpose computing device when programmed to execute the instructions described herein.

One or more embodiments of the present disclosure may be implemented as one or more computer programs, computer-executable instructions, or as one or more computer program modules embodied in one or more computer-readable media. In some embodiments, the term computer-readable medium refers to any data storage device that stores data that can thereafter be input to a computer system. Computer-readable media may be based on any existing or subsequently developed technology for embodying computer programs in a manner that enables them to be read by a computer. Exemplary computer readable media include memory such as hard drives, network attached storage (NAS), read-only memory, random-access memory, flash memory drives, digital versatile discs (DVDs), compact discs (CDs), floppy disks, magnetic tape, and other optical and non-optical data storage devices. By way of example and not limitation, computer readable media comprise computer storage media and communication media. Computer storage media include volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Computer storage media are tangible, exclude propagated data signals, and are mutually exclusive to communication media. In some embodiments, computer storage media are implemented in hardware. Exemplary computer storage media include hard disks, flash drives, and other solid-state memory. In contrast, communication media typically embody computer readable instructions, data structures, program modules, or other data in a modulated data signal such as a carrier wave or other transport mechanism and include any information delivery media.

The computer readable medium can also be distributed over a network coupled computer system so that the computer readable code is stored and executed in a distributed fashion.

The various embodiments described herein may employ various computer-implemented operations involving data stored in computer systems. For example, these operations may require physical manipulation of physical quantities usually, though not necessarily, these quantities may take the form of electrical or magnetic signals where they, or representations of them, are capable of being stored, transferred, combined, compared, or otherwise manipulated. Further, such manipulations are often referred to in terms, such as producing, identifying, determining, or comparing.

Although described in connection with an exemplary computing system environment, embodiments of the disclosure are operative with numerous other general purpose or special purpose computing system environments or configurations. Examples of well-known computing systems, environments, and/or configurations that may be suitable for use with aspects of the disclosure include, but are not limited to, mobile computing devices, personal computers, server computers, hand-held or laptop devices, multiprocessor systems, gaming consoles, microprocessor-based systems, set top boxes, programmable consumer electronics, mobile telephones, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.

Plural instances may be provided for components, operations or structures described herein as a single instance. Further, at least a portion of the functionality of the various elements illustrated in the figures may be performed by other elements in the figures, or an entity (e.g., processor, web service, server, application program, computing device, etc.) not shown in the figures. For example, while boundaries between various components, operations and data stores are illustrated in the context of specific illustrative configurations, other allocations of functionality are envisioned that fall within the scope of the invention. In general, structures and functionality presented as separate components in exemplary configurations may be implemented as a combined structure or component. Similarly, structures and functionality presented as a single component may be implemented as separate components. These and other variations, modifications, additions, and improvements may fall within the scope of the appended claims(s).