KVM Fault Tolerance: Kemari for KVM

Hi all,

It has been a while coming, but we have finally started work on Kemari's port to KVM. For those not familiar with it, Kemari provides the basic building block to create a virtualization-based fault tolerant machine: a virtual machine synchronization mechanism.

Traditional high availability solutions can be classified in two
groups: fault tolerant servers, and software clustering.

Broadly speaking, fault tolerant servers protect us against hardware failures and, generally, rely on redundant hardware (often proprietary), and hardware failure detection to trigger fail-over.

On the other hand, software clustering, as its name indicates, takes care of software failures and usually requires a standby server whose software configuration for the part we are trying to make fault tolerant must be identical to that of the active server.

Both solutions may be applied to virtualized environments. Indeed, the current incarnation of Kemari (Xen-based) brings fault tolerant server-like capabilities to virtual machines and integration with existing HA stacks (Heartbeat, RHCS, etc) is under consideration.

After some time in the drawing board we completed the basic design of Kemari for KVM, so we are sending an RFC at this point to get early feedback and, hopefully, get things right from the start. Those already familiar with Kemari and/or fault tolerance may want to skip the "Background" and go directly to the design and implementation bits.

This is a pretty long write-up, but please bear with me.

== Background ==

We started to play around with continuous virtual synchronization technology about 3 years ago. As development progressed and, most importantly, we got the first Xen-based working prototypes it became clear that we needed a proper name for our toy: Kemari.

The goal of Kemari is to provide a fault tolerant platform for virtualization environments, so that in the event of a hardware failure the virtual machine fails over from compromised to properly operating hardware (a physical machine) in a way that is completely transparent to the guest operating system.

Although hardware based fault tolerant servers and HA servers (software clustering) have been around for a (long) while, they typically require specifically designed hardware and/or modifications to applications. In contrast, by abstracting hardware using virtualization, Kemari can be used on off-the-shelf hardware and no application modifications are needed.

After a period of in-house development the first version of Kemari for Xen was released in Nov 2008 as open source. However, by then it was already pretty clear that a KVM port would have several advantages. First, KVM is integrated into the Linux kernel, which means one gets support for a wide variety of hardware for free. Second, and in the same vein, KVM can also benefit from Linux' low latency networking capabilities including RDMA, which is of paramount importance for a extremely latency-sensitive functionality like Kemari. Last, but not the least, KVM and its community is growing rapidly, and there is increasing demand for Kemari-like functionality for KVM.

Although the basic design principles will remain the same, our plan is to write Kemari for KVM from scratch, since there does not seem to be much opportunity for sharing between Xen and KVM.

== Design outline ==

The basic premise of fault tolerant servers is that when things go awry with the hardware the running system should transparently continue execution on an alternate physical host. For this to be possible the state of the fallback host has to be identical to that of the primary.

Kemari runs paired virtual machines in an active-passive configuration and achieves whole-system replication by continuously copying the state of the system (dirty pages and the state of the virtual devices) from the active node to the passive node. An interesting implication of this is that during normal operation only the active node is actually executing code.

Another possible approach is to run a pair of systems in lock-step (à la VMware FT). Since both the primary and fallback virtual machines are active keeping them synchronized is a complex task, which usually involves carefully injecting external events into both virtual machines so that they result in identical states.

The latter approach is extremely architecture specific and not SMP friendly. This spurred us to try the design that became Kemari, which we believe lends itself to further optimizations.

== Implementation ==

The first step is to encapsulate the machine to be protected within a virtual machine. Then the live migration functionality is leveraged to keep the virtual machines synchronized.

Whereas during live migration dirty pages can be sent asynchronously from the primary to the fallback server until the ratio of dirty pages is low enough to guarantee very short downtimes, when it comes to fault tolerance solutions whenever a synchronization point is reached changes to the virtual machine since the previous one have to be sent synchronously.

Since the virtual machine has to be stopped until the data reaches and is acknowledged by the fallback server, the synchronization model is of critical importance for performance (both in terms of raw throughput and latencies). The model chosen for Kemari along with other implementation details is described below.

* Synchronization model

The synchronization points were carefully chosen to minimize the amount of traffic that goes over the wire while still maintaining the FT pair consistent at all times. To be precise, Kemari uses events that modify externally visible state as synchronizations points. This means that all outgoing I/O needs to be trapped and sent to the fallback host before the primary is resumed, so that it can be replayed in the face of hardware failure.

The basic assumption here is that outgoing I/O operations are idempotent, which is usually true for disk I/O and reliable network protocols such as TCP (Kemari may trigger hidden bugs on applications that use UDP or other unreliable protocols, so those may need minor changes to ensure they work properly after failover).

The synchronization process can be broken down as follows:

- Event tapping: On KVM all I/O generates a VMEXIT that is synchronously handled by the Linux kernel monitor i.e. KVM (it is worth noting that this applies to virtio devices too, because they use MMIO and PIO just like a regular PCI device).

- VCPU/Guest freezing: This is automatic in the UP case. On SMP environments we may need to send a IPI to stop the other VCPUs.

- Notification to qemu: Taking a page from live migration's playbook, the synchronization process is user-space driven, which means that qemu needs to be woken up at each synchronization point. That is already the case for qemu-emulated devices, but we also have in-kernel emulators. To compound the problem, even for user-space emulated devices accesses to coalesced MMIO areas can not be detected. As a consequence we need a mechanism to communicate KVM-handled events to qemu.

The channel for KVM-qemu communication can be easily build upon the existing infrastructure. We just need to add a new a page to the kvm_run shared memory area that can be mmapped from user space and set the exit reason appropriately.

Regarding in-kernel device emulators, we only need to care about writes. Specifically, making kvm_io_bus_write() fail when Kemari is activated and invoking the emulator again after re-entrance from user space should suffice (this is somewhat similar to what we do in kvm_arch_vcpu_ioctl_run() for MMIO reads).

To avoid missing synchronization points one should be careful with coalesced MMIO-like optimizations. In the particular case of coalesced MMIO, the I/O operation that caused the exit to user space should act as a write barrier when it was due to an access to a non-coalesced MMIO area. This means that before proceeding to handle the exit in kvm_run() we have to make sure that all the coalesced MMIO has reached the fallback host.

- Virtual machine synchronization: All the dirty pages since the last synchronization point and the state of the virtual devices is sent to the fallback node from the user-space qemu process. For this the existing savevm infrastructure and KVM's dirty page tracking

capabilities can be reused. Regarding in-kernel devices, with the likely advent of in-kernel virtio backends we need a generic way to access their state from user-space, for which, again, the kvm_run share memory area could be used.

- Virtual machine run: Execution of the virtual machine is resumed as soon as synchronization finishes.

* Clock

Even though we do not need to worry about the clock that provides the tick (the counter resides in memory, which we keep synchronized), the same does not apply to counters such as the TSC (we certainly want to avoid a situation where counters jump back in time right after fail-over, breaking guarantees such as monotonicity).

To avoid big hiccups after migration the value of the TSC should be sent to the fallback node frequently. An access from the guest (through RDTSC, RDTSCP, RDMSR, or WRMSR) seems like the right moment to do this. Fortunately, both vmx and SVM provide controls to intercept accesses to the TSC, so it is just a matter of setting those appropriately ("RDTSC exiting" VM-execution control, and RDTSC, RDTSCP, RDMSR, WRMSR instruction intercepts, respectively). However, since synchronizing the virtual machines every time the TSC is accessed would be prohibitive, the transmission of the TSC will be done lazily, which means delaying it until there is a non-TSC synchronization point arrives.

* Failover

Failover process kicks in whenever a failure in the primary node is detected. At the time of writing we just ping the virtual machine periodically to determine whether it is still alive, but in the long term we have plans to integrate Kemari with the major HA stacks (Hearbeat, RHCS, etc).

Ideally, we would like to leverage the hardware failure detection capabilities of newish x86 hardware to trigger failover, the idea being that transferring control to the fallback node proactively when a problem is detected is much faster than relying on the polling mechanisms used by most HA software.

Finally, to restore the virtual machine in the fallback host the loadvm infrastructure used for live-migration is leveraged.

* Further information

Please visit the link below for additional information, including documentation and, most importantly, source code (for Xen only at the moment).

http://www.osrg.net/kemari
==

Any comments and suggestions would be greatly appreciated.

If this is the right forum and people on the KVM mailing list do not mind, we would like to use the CC'ed mailing lists for Kemari development. Having more expert eyes looking at one's code always helps.

Thanks,

Fernando
--
To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Quoted 167 lines · Fernando Luis Vázquez Cao

Hi all,

It has been a while coming, but we have finally started work on Kemari's port to KVM. For those not familiar with it, Kemari provides the basic building block to create a virtualization-based fault tolerant machine: a virtual machine synchronization mechanism.

Traditional high availability solutions can be classified in two
groups: fault tolerant servers, and software clustering.

Broadly speaking, fault tolerant servers protect us against hardware failures and, generally, rely on redundant hardware (often proprietary), and hardware failure detection to trigger fail-over.

On the other hand, software clustering, as its name indicates, takes care of software failures and usually requires a standby server whose software configuration for the part we are trying to make fault tolerant must be identical to that of the active server.

Both solutions may be applied to virtualized environments. Indeed, the current incarnation of Kemari (Xen-based) brings fault tolerant server-like capabilities to virtual machines and integration with existing HA stacks (Heartbeat, RHCS, etc) is under consideration.

After some time in the drawing board we completed the basic design of Kemari for KVM, so we are sending an RFC at this point to get early feedback and, hopefully, get things right from the start. Those already familiar with Kemari and/or fault tolerance may want to skip the "Background" and go directly to the design and implementation bits.

This is a pretty long write-up, but please bear with me.

== Background ==

We started to play around with continuous virtual synchronization technology about 3 years ago. As development progressed and, most importantly, we got the first Xen-based working prototypes it became clear that we needed a proper name for our toy: Kemari.

The goal of Kemari is to provide a fault tolerant platform for virtualization environments, so that in the event of a hardware failure the virtual machine fails over from compromised to properly operating hardware (a physical machine) in a way that is completely transparent to the guest operating system.

Although hardware based fault tolerant servers and HA servers (software clustering) have been around for a (long) while, they typically require specifically designed hardware and/or modifications to applications. In contrast, by abstracting hardware using virtualization, Kemari can be used on off-the-shelf hardware and no application modifications are needed.

After a period of in-house development the first version of Kemari for Xen was released in Nov 2008 as open source. However, by then it was already pretty clear that a KVM port would have several advantages. First, KVM is integrated into the Linux kernel, which means one gets support for a wide variety of hardware for free. Second, and in the same vein, KVM can also benefit from Linux' low latency networking capabilities including RDMA, which is of paramount importance for a extremely latency-sensitive functionality like Kemari. Last, but not the least, KVM and its community is growing rapidly, and there is increasing demand for Kemari-like functionality for KVM.

Although the basic design principles will remain the same, our plan is to write Kemari for KVM from scratch, since there does not seem to be much opportunity for sharing between Xen and KVM.

== Design outline ==

The basic premise of fault tolerant servers is that when things go awry with the hardware the running system should transparently continue execution on an alternate physical host. For this to be possible the state of the fallback host has to be identical to that of the primary.

Kemari runs paired virtual machines in an active-passive configuration and achieves whole-system replication by continuously copying the state of the system (dirty pages and the state of the virtual devices) from the active node to the passive node. An interesting implication of this is that during normal operation only the active node is actually executing code.

Another possible approach is to run a pair of systems in lock-step (à la VMware FT). Since both the primary and fallback virtual machines are active keeping them synchronized is a complex task, which usually involves carefully injecting external events into both virtual machines so that they result in identical states.

The latter approach is extremely architecture specific and not SMP friendly. This spurred us to try the design that became Kemari, which we believe lends itself to further optimizations.

== Implementation ==

The first step is to encapsulate the machine to be protected within a virtual machine. Then the live migration functionality is leveraged to keep the virtual machines synchronized.

Whereas during live migration dirty pages can be sent asynchronously from the primary to the fallback server until the ratio of dirty pages is low enough to guarantee very short downtimes, when it comes to fault tolerance solutions whenever a synchronization point is reached changes to the virtual machine since the previous one have to be sent synchronously.

Since the virtual machine has to be stopped until the data reaches and is acknowledged by the fallback server, the synchronization model is of critical importance for performance (both in terms of raw throughput and latencies). The model chosen for Kemari along with other implementation details is described below.

* Synchronization model

The synchronization points were carefully chosen to minimize the amount of traffic that goes over the wire while still maintaining the FT pair consistent at all times. To be precise, Kemari uses events that modify externally visible state as synchronizations points. This means that all outgoing I/O needs to be trapped and sent to the fallback host before the primary is resumed, so that it can be replayed in the face of hardware failure.

The basic assumption here is that outgoing I/O operations are idempotent, which is usually true for disk I/O and reliable network protocols such as TCP (Kemari may trigger hidden bugs on applications that use UDP or other unreliable protocols, so those may need minor changes to ensure they work properly after failover).

The synchronization process can be broken down as follows:

- Event tapping: On KVM all I/O generates a VMEXIT that is synchronously handled by the Linux kernel monitor i.e. KVM (it is worth noting that this applies to virtio devices too, because they use MMIO and PIO just like a regular PCI device).

- VCPU/Guest freezing: This is automatic in the UP case. On SMP environments we may need to send a IPI to stop the other VCPUs.

- Notification to qemu: Taking a page from live migration's playbook, the synchronization process is user-space driven, which means that qemu needs to be woken up at each synchronization point. That is already the case for qemu-emulated devices, but we also have in-kernel emulators. To compound the problem, even for user-space emulated devices accesses to coalesced MMIO areas can not be detected. As a consequence we need a mechanism to communicate KVM-handled events to qemu.

The channel for KVM-qemu communication can be easily build upon the existing infrastructure. We just need to add a new a page to the kvm_run shared memory area that can be mmapped from user space and set the exit reason appropriately.

Regarding in-kernel device emulators, we only need to care about writes. Specifically, making kvm_io_bus_write() fail when Kemari is activated and invoking the emulator again after re-entrance from user space should suffice (this is somewhat similar to what we do in kvm_arch_vcpu_ioctl_run() for MMIO reads).

To avoid missing synchronization points one should be careful with coalesced MMIO-like optimizations. In the particular case of coalesced MMIO, the I/O operation that caused the exit to user space should act as a write barrier when it was due to an access to a non-coalesced MMIO area. This means that before proceeding to handle the exit in kvm_run() we have to make sure that all the coalesced MMIO has reached the fallback host.

Quoted 4 lines

- Virtual machine synchronization: All the dirty pages since the last synchronization point and the state of the virtual devices is sent to the fallback node from the user-space qemu process. For this the existing savevm infrastructure and KVM's dirty page tracking

I failed to understand whether you take the lock step approach and sync every vmexit + make sure the shadow host will inject irq on the original guest's instruction boundary or alternatively use continuous live snapshots.

If you use live snapshots, why do you need to track mmio, etc? Is it in order to save the device sync stage in live migration? In order to do it you fully lock step qemu execution (or send the entire vmstate to the slave). Isn't the device part is << dirt pages part?

Thanks,
Dor

Quoted 69 lines

capabilities can be reused. Regarding in-kernel devices, with the likely advent of in-kernel virtio backends we need a generic way to access their state from user-space, for which, again, the kvm_run share memory area could be used.

- Virtual machine run: Execution of the virtual machine is resumed as soon as synchronization finishes.

* Clock

Even though we do not need to worry about the clock that provides the tick (the counter resides in memory, which we keep synchronized), the same does not apply to counters such as the TSC (we certainly want to avoid a situation where counters jump back in time right after fail-over, breaking guarantees such as monotonicity).

To avoid big hiccups after migration the value of the TSC should be sent to the fallback node frequently. An access from the guest (through RDTSC, RDTSCP, RDMSR, or WRMSR) seems like the right moment to do this. Fortunately, both vmx and SVM provide controls to intercept accesses to the TSC, so it is just a matter of setting those appropriately ("RDTSC exiting" VM-execution control, and RDTSC, RDTSCP, RDMSR, WRMSR instruction intercepts, respectively). However, since synchronizing the virtual machines every time the TSC is accessed would be prohibitive, the transmission of the TSC will be done lazily, which means delaying it until there is a non-TSC synchronization point arrives.

* Failover

Failover process kicks in whenever a failure in the primary node is detected. At the time of writing we just ping the virtual machine periodically to determine whether it is still alive, but in the long term we have plans to integrate Kemari with the major HA stacks (Hearbeat, RHCS, etc).

Ideally, we would like to leverage the hardware failure detection capabilities of newish x86 hardware to trigger failover, the idea being that transferring control to the fallback node proactively when a problem is detected is much faster than relying on the polling mechanisms used by most HA software.

Finally, to restore the virtual machine in the fallback host the loadvm infrastructure used for live-migration is leveraged.

* Further information

Please visit the link below for additional information, including documentation and, most importantly, source code (for Xen only at the moment).

http://www.osrg.net/kemari
==

Any comments and suggestions would be greatly appreciated.

If this is the right forum and people on the KVM mailing list do not mind, we would like to use the CC'ed mailing lists for Kemari development. Having more expert eyes looking at one's code always helps.

Thanks,

Fernando

Signature · 3 lines

To unsubscribe from this list: send the line "unsubscribe kvm" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Hi,

Thanks for your comments!

Quoted 173 lines · Dor Laor

Quoted 167 lines · Fernando Luis Vázquez Cao

Hi all,

It has been a while coming, but we have finally started work on Kemari's port to KVM. For those not familiar with it, Kemari provides the basic building block to create a virtualization-based fault tolerant machine: a virtual machine synchronization mechanism.

Traditional high availability solutions can be classified in two
groups: fault tolerant servers, and software clustering.

Broadly speaking, fault tolerant servers protect us against hardware failures and, generally, rely on redundant hardware (often proprietary), and hardware failure detection to trigger fail-over.

On the other hand, software clustering, as its name indicates, takes care of software failures and usually requires a standby server whose software configuration for the part we are trying to make fault tolerant must be identical to that of the active server.

Both solutions may be applied to virtualized environments. Indeed, the current incarnation of Kemari (Xen-based) brings fault tolerant server-like capabilities to virtual machines and integration with existing HA stacks (Heartbeat, RHCS, etc) is under consideration.

After some time in the drawing board we completed the basic design of Kemari for KVM, so we are sending an RFC at this point to get early feedback and, hopefully, get things right from the start. Those already familiar with Kemari and/or fault tolerance may want to skip the "Background" and go directly to the design and implementation bits.

This is a pretty long write-up, but please bear with me.

== Background ==

We started to play around with continuous virtual synchronization technology about 3 years ago. As development progressed and, most importantly, we got the first Xen-based working prototypes it became clear that we needed a proper name for our toy: Kemari.

The goal of Kemari is to provide a fault tolerant platform for virtualization environments, so that in the event of a hardware failure the virtual machine fails over from compromised to properly operating hardware (a physical machine) in a way that is completely transparent to the guest operating system.

Although hardware based fault tolerant servers and HA servers (software clustering) have been around for a (long) while, they typically require specifically designed hardware and/or modifications to applications. In contrast, by abstracting hardware using virtualization, Kemari can be used on off-the-shelf hardware and no application modifications are needed.

After a period of in-house development the first version of Kemari for Xen was released in Nov 2008 as open source. However, by then it was already pretty clear that a KVM port would have several advantages. First, KVM is integrated into the Linux kernel, which means one gets support for a wide variety of hardware for free. Second, and in the same vein, KVM can also benefit from Linux' low latency networking capabilities including RDMA, which is of paramount importance for a extremely latency-sensitive functionality like Kemari. Last, but not the least, KVM and its community is growing rapidly, and there is increasing demand for Kemari-like functionality for KVM.

Although the basic design principles will remain the same, our plan is to write Kemari for KVM from scratch, since there does not seem to be much opportunity for sharing between Xen and KVM.

== Design outline ==

The basic premise of fault tolerant servers is that when things go awry with the hardware the running system should transparently continue execution on an alternate physical host. For this to be possible the state of the fallback host has to be identical to that of the primary.

Kemari runs paired virtual machines in an active-passive configuration and achieves whole-system replication by continuously copying the state of the system (dirty pages and the state of the virtual devices) from the active node to the passive node. An interesting implication of this is that during normal operation only the active node is actually executing code.

Another possible approach is to run a pair of systems in lock-step (à la VMware FT). Since both the primary and fallback virtual machines are active keeping them synchronized is a complex task, which usually involves carefully injecting external events into both virtual machines so that they result in identical states.

The latter approach is extremely architecture specific and not SMP friendly. This spurred us to try the design that became Kemari, which we believe lends itself to further optimizations.

== Implementation ==

The first step is to encapsulate the machine to be protected within a virtual machine. Then the live migration functionality is leveraged to keep the virtual machines synchronized.

Whereas during live migration dirty pages can be sent asynchronously from the primary to the fallback server until the ratio of dirty pages is low enough to guarantee very short downtimes, when it comes to fault tolerance solutions whenever a synchronization point is reached changes to the virtual machine since the previous one have to be sent synchronously.

Since the virtual machine has to be stopped until the data reaches and is acknowledged by the fallback server, the synchronization model is of critical importance for performance (both in terms of raw throughput and latencies). The model chosen for Kemari along with other implementation details is described below.

* Synchronization model

The synchronization points were carefully chosen to minimize the amount of traffic that goes over the wire while still maintaining the FT pair consistent at all times. To be precise, Kemari uses events that modify externally visible state as synchronizations points. This means that all outgoing I/O needs to be trapped and sent to the fallback host before the primary is resumed, so that it can be replayed in the face of hardware failure.

The basic assumption here is that outgoing I/O operations are idempotent, which is usually true for disk I/O and reliable network protocols such as TCP (Kemari may trigger hidden bugs on applications that use UDP or other unreliable protocols, so those may need minor changes to ensure they work properly after failover).

The synchronization process can be broken down as follows:

- Event tapping: On KVM all I/O generates a VMEXIT that is synchronously handled by the Linux kernel monitor i.e. KVM (it is worth noting that this applies to virtio devices too, because they use MMIO and PIO just like a regular PCI device).

- VCPU/Guest freezing: This is automatic in the UP case. On SMP environments we may need to send a IPI to stop the other VCPUs.

- Notification to qemu: Taking a page from live migration's playbook, the synchronization process is user-space driven, which means that qemu needs to be woken up at each synchronization point. That is already the case for qemu-emulated devices, but we also have in-kernel emulators. To compound the problem, even for user-space emulated devices accesses to coalesced MMIO areas can not be detected. As a consequence we need a mechanism to communicate KVM-handled events to qemu.

The channel for KVM-qemu communication can be easily build upon the existing infrastructure. We just need to add a new a page to the kvm_run shared memory area that can be mmapped from user space and set the exit reason appropriately.

Regarding in-kernel device emulators, we only need to care about writes. Specifically, making kvm_io_bus_write() fail when Kemari is activated and invoking the emulator again after re-entrance from user space should suffice (this is somewhat similar to what we do in kvm_arch_vcpu_ioctl_run() for MMIO reads).

To avoid missing synchronization points one should be careful with coalesced MMIO-like optimizations. In the particular case of coalesced MMIO, the I/O operation that caused the exit to user space should act as a write barrier when it was due to an access to a non-coalesced MMIO area. This means that before proceeding to handle the exit in kvm_run() we have to make sure that all the coalesced MMIO has reached the fallback host.

Quoted 4 lines

- Virtual machine synchronization: All the dirty pages since the last synchronization point and the state of the virtual devices is sent to the fallback node from the user-space qemu process. For this the existing savevm infrastructure and KVM's dirty page tracking

Quoted 4 lines

I failed to understand whether you take the lock step approach and sync every vmexit + make sure the shadow host will inject irq on the original guest's instruction boundary or alternatively use continuous live snapshots.

We'll take the live snapshots approach for now.

Quoted 4 lines

If you use live snapshots, why do you need to track mmio, etc? Is it in order to save the device sync stage in live migration? In order to do it you fully lock step qemu execution (or send the entire vmstate to the slave). Isn't the device part is << dirt pages part?

We're thinking to capture mmio operations that effect the state of devices as synchronization points. The purpose is to lock step qemu execution as you mentioned.

Thanks,

Yoshi

Quoted 78 lines

Thanks,
Dor

Quoted 69 lines

capabilities can be reused. Regarding in-kernel devices, with the likely advent of in-kernel virtio backends we need a generic way to access their state from user-space, for which, again, the kvm_run share memory area could be used.

- Virtual machine run: Execution of the virtual machine is resumed as soon as synchronization finishes.

* Clock

Even though we do not need to worry about the clock that provides the tick (the counter resides in memory, which we keep synchronized), the same does not apply to counters such as the TSC (we certainly want to avoid a situation where counters jump back in time right after fail-over, breaking guarantees such as monotonicity).

To avoid big hiccups after migration the value of the TSC should be sent to the fallback node frequently. An access from the guest (through RDTSC, RDTSCP, RDMSR, or WRMSR) seems like the right moment to do this. Fortunately, both vmx and SVM provide controls to intercept accesses to the TSC, so it is just a matter of setting those appropriately ("RDTSC exiting" VM-execution control, and RDTSC, RDTSCP, RDMSR, WRMSR instruction intercepts, respectively). However, since synchronizing the virtual machines every time the TSC is accessed would be prohibitive, the transmission of the TSC will be done lazily, which means delaying it until there is a non-TSC synchronization point arrives.

* Failover

Failover process kicks in whenever a failure in the primary node is detected. At the time of writing we just ping the virtual machine periodically to determine whether it is still alive, but in the long term we have plans to integrate Kemari with the major HA stacks (Hearbeat, RHCS, etc).

Ideally, we would like to leverage the hardware failure detection capabilities of newish x86 hardware to trigger failover, the idea being that transferring control to the fallback node proactively when a problem is detected is much faster than relying on the polling mechanisms used by most HA software.

Finally, to restore the virtual machine in the fallback host the loadvm infrastructure used for live-migration is leveraged.

* Further information

Please visit the link below for additional information, including documentation and, most importantly, source code (for Xen only at the moment).

http://www.osrg.net/kemari
==

Any comments and suggestions would be greatly appreciated.

If this is the right forum and people on the KVM mailing list do not mind, we would like to use the CC'ed mailing lists for Kemari development. Having more expert eyes looking at one's code always helps.

Thanks,

Fernando
--
To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

--
To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Kemari runs paired virtual machines in an active-passive configuration and achieves whole-system replication by continuously copying the state of the system (dirty pages and the state of the virtual devices) from the active node to the passive node. An interesting implication of this is that during normal operation only the active node is actually executing code.

The synchronization process can be broken down as follows:

- Event tapping: On KVM all I/O generates a VMEXIT that is synchronously handled by the Linux kernel monitor i.e. KVM (it is worth noting that this applies to virtio devices too, because they use MMIO and PIO just like a regular PCI device).

- Notification to qemu: Taking a page from live migration's playbook, the synchronization process is user-space driven, which means that qemu needs to be woken up at each synchronization point. That is already the case for qemu-emulated devices, but we also have in-kernel emulators. To compound the problem, even for user-space emulated devices accesses to coalesced MMIO areas can not be detected. As a consequence we need a mechanism to communicate KVM-handled events to qemu.

- Virtual machine synchronization: All the dirty pages since the last synchronization point and the state of the virtual devices is sent to the fallback node from the user-space qemu process. For this the existing savevm infrastructure and KVM's dirty page tracking capabilities can be reused. Regarding in-kernel devices, with the likely advent of in-kernel virtio backends we need a generic way to access their state from user-space, for which, again, the kvm_run share memory area could be used.

Quoted 8 lines · Fernando Luis Vázquez Cao

Kemari runs paired virtual machines in an active-passive configuration and achieves whole-system replication by continuously copying the state of the system (dirty pages and the state of the virtual devices) from the active node to the passive node. An interesting implication of this is that during normal operation only the active node is actually executing code.

Can you characterize the performance impact for various workloads? I assume you are running continuously in log-dirty mode. Doesn't this make memory intensive workloads suffer?

Quoted 6 lines

The synchronization process can be broken down as follows:

- Event tapping: On KVM all I/O generates a VMEXIT that is synchronously handled by the Linux kernel monitor i.e. KVM (it is worth noting that this applies to virtio devices too, because they use MMIO and PIO just like a regular PCI device).

Some I/O (virtio-based) is asynchronous, but you still have well-known tap points within qemu.

Quoted 8 lines

- Notification to qemu: Taking a page from live migration's playbook, the synchronization process is user-space driven, which means that qemu needs to be woken up at each synchronization point. That is already the case for qemu-emulated devices, but we also have in-kernel emulators. To compound the problem, even for user-space emulated devices accesses to coalesced MMIO areas can not be detected. As a consequence we need a mechanism to communicate KVM-handled events to qemu.

Do you mean the ioapic, pic, and lapic?

Perhaps its best to start with those in userspace (-no-kvm-irqchip).

Why is access to those chips considered a synchronization point?

Quoted 8 lines

- Virtual machine synchronization: All the dirty pages since the last synchronization point and the state of the virtual devices is sent to the fallback node from the user-space qemu process. For this the existing savevm infrastructure and KVM's dirty page tracking capabilities can be reused. Regarding in-kernel devices, with the likely advent of in-kernel virtio backends we need a generic way to access their state from user-space, for which, again, the kvm_run share memory area could be used.

I wonder if you can pipeline dirty memory synchronization. That is, write-protect those pages that are dirty, start copying them to the other side, and continue execution, copying memory if the guest faults it again.

How many pages do you copy per synchronization point for reasonably difficult workloads?

Quoted 11 lines · Avi Kivity

Quoted 8 lines · Fernando Luis Vázquez Cao

Kemari runs paired virtual machines in an active-passive configuration and achieves whole-system replication by continuously copying the state of the system (dirty pages and the state of the virtual devices) from the active node to the passive node. An interesting implication of this is that during normal operation only the active node is actually executing code.

Can you characterize the performance impact for various workloads? I assume you are running continuously in log-dirty mode. Doesn't this make memory intensive workloads suffer?

Yes, we're running continuously in log-dirty mode.

We still do not have numbers to show for KVM, but the snippets below from several runs of lmbench using Xen+Kemari will give you an idea of what you can expect in terms of overhead. All the tests were run using a fully virtualized Debian guest with hardware nested paging enabled.

fork exec sh P/F C/S [us]
------------------------------------------------------

Base                  114  349 1197 1.2845  8.2
Kemari(10GbE) + FC    141  403 1280 1.2835 11.6
Kemari(10GbE) + DRBD  161  415 1388 1.3145 11.6
Kemari(1GbE) + FC     151  410 1335 1.3370 11.5
Kemari(1GbE) + DRBD   162  413 1318 1.3239 11.6

* P/F=page fault, C/S=context switch

The benchmarks above are memory intensive and, as you can see, the overhead varies widely from 7% to 40%. We also measured CPU bound operations, but, as expected, Kemari incurred almost no overhead.

Quoted 9 lines

Quoted 8 lines

- Notification to qemu: Taking a page from live migration's playbook, the synchronization process is user-space driven, which means that qemu needs to be woken up at each synchronization point. That is already the case for qemu-emulated devices, but we also have in-kernel emulators. To compound the problem, even for user-space emulated devices accesses to coalesced MMIO areas can not be detected. As a consequence we need a mechanism to communicate KVM-handled events to qemu.

Quoted 1 line

Do you mean the ioapic, pic, and lapic?

Well, I was more worried about the in-kernel backends currently in the works. To save the state of those devices we could leverage qemu's vmstate infrastructure and even reuse struct VMStateDescription's pre_save() callback, but we would like to pass the device state through the kvm_run area to avoid a ioctl call right after returning to user space.

Quoted 1 line

Why is access to those chips considered a synchronization point?

The main problem with those is that to get the chip state we use an ioctl when we could have copied it to qemu's memory before going back to user space. Not all accesses to those chips need to be treated as synchronization points.

Quoted 1 line

I wonder if you can pipeline dirty memory synchronization. That is, write-protect those pages that are dirty, start copying them to the other side, and continue execution, copying memory if the guest faults it again.

Asynchronous transmission of dirty pages would be really helpful to eliminate the performance hiccups that tend to occur at synchronization points. What we can do is to copy dirty pages asynchronously until we reach a synchronization point, where we need to stop the guest and send the remaining dirty pages and the state of devices to the other side.

However, we can not delay the transmission of a dirty page across a synchronization point, because if the primary node crashed before the page reached the fallback node the I/O operation that caused the synchronization point cannot be replayed reliably.

Quoted 1 line

How many pages do you copy per synchronization point for reasonably difficult workloads?

That is very workload-dependent, but if you take a look at the examples below you can get a feeling of how Kemari behaves.

IOzone Kemari sync interval[ms] dirtied pages
---------------------------------------------------------
buffered + fsync 400 3000
O_SYNC 10 80

In summary, if the guest executes few I/O operations, the interval between Kemari synchronizations points will increase and the number of dirtied pages will grow accordingly.

Quoted 29 lines · Fernando Luis Vázquez Cao

Quoted 11 lines · Avi Kivity

Quoted 8 lines · Fernando Luis Vázquez Cao

Kemari runs paired virtual machines in an active-passive configuration and achieves whole-system replication by continuously copying the state of the system (dirty pages and the state of the virtual devices) from the active node to the passive node. An interesting implication of this is that during normal operation only the active node is actually executing code.

Can you characterize the performance impact for various workloads? I assume you are running continuously in log-dirty mode. Doesn't this make memory intensive workloads suffer?

Yes, we're running continuously in log-dirty mode.

We still do not have numbers to show for KVM, but the snippets below from several runs of lmbench using Xen+Kemari will give you an idea of what you can expect in terms of overhead. All the tests were run using a fully virtualized Debian guest with hardware nested paging enabled.

fork exec sh P/F C/S [us]
------------------------------------------------------

Base                  114  349 1197 1.2845  8.2
Kemari(10GbE) + FC    141  403 1280 1.2835 11.6
Kemari(10GbE) + DRBD  161  415 1388 1.3145 11.6
Kemari(1GbE) + FC     151  410 1335 1.3370 11.5
Kemari(1GbE) + DRBD   162  413 1318 1.3239 11.6

Quoted 6 lines

* P/F=page fault, C/S=context switch

The benchmarks above are memory intensive and, as you can see, the overhead varies widely from 7% to 40%. We also measured CPU bound operations, but, as expected, Kemari incurred almost no overhead.

Is lmbench fork that memory intensive?

Do you have numbers for benchmarks that use significant anonymous RSS? Say, a parallel kernel build.

Note that scaling vcpus will increase a guest's memory-dirtying power but snapshot rate will not scale in the same way.

Quoted 11 lines

Quoted 10 lines

Quoted 8 lines

- Notification to qemu: Taking a page from live migration's playbook, the synchronization process is user-space driven, which means that qemu needs to be woken up at each synchronization point. That is already the case for qemu-emulated devices, but we also have in-kernel emulators. To compound the problem, even for user-space emulated devices accesses to coalesced MMIO areas can not be detected. As a consequence we need a mechanism to communicate KVM-handled events to qemu.

Do you mean the ioapic, pic, and lapic?

Quoted 5 lines

Well, I was more worried about the in-kernel backends currently in the works. To save the state of those devices we could leverage qemu's vmstate infrastructure and even reuse struct VMStateDescription's pre_save() callback, but we would like to pass the device state through the kvm_run area to avoid a ioctl call right after returning to user space.

Hm, let's defer all that until we have something working so we can estimate the impact of userspace virtio in those circumstances.

Quoted 6 lines

Quoted 1 line

Why is access to those chips considered a synchronization point?

The main problem with those is that to get the chip state we use an ioctl when we could have copied it to qemu's memory before going back to user space. Not all accesses to those chips need to be treated as synchronization points.

Ok. Note that piggybacking on an exit will work for the lapic, but not for the global irqchips (ioapic, pic) since they can still be modified by another vcpu.

Quoted 8 lines

Quoted 1 line

I wonder if you can pipeline dirty memory synchronization. That is, write-protect those pages that are dirty, start copying them to the other side, and continue execution, copying memory if the guest faults it again.

Asynchronous transmission of dirty pages would be really helpful to eliminate the performance hiccups that tend to occur at synchronization points. What we can do is to copy dirty pages asynchronously until we reach a synchronization point, where we need to stop the guest and send the remaining dirty pages and the state of devices to the other side.

Quoted 4 lines

However, we can not delay the transmission of a dirty page across a synchronization point, because if the primary node crashed before the page reached the fallback node the I/O operation that caused the synchronization point cannot be replayed reliably.

What I mean is:

- choose synchronization point A
- start copying memory for synchronization point A
- output is delayed
- choose synchronization point B
- copy memory for A and B
if guest touches memory not yet copied for A, COW it
- once A copying is complete, release A output
- continue copying memory for B
- choose synchronization point B

by keeping two synchronization points active, you don't have any pauses. The cost is maintaining copy-on-write so we can copy dirty pages for A while keeping execution.

Quoted 10 lines

Quoted 1 line

How many pages do you copy per synchronization point for reasonably difficult workloads?

That is very workload-dependent, but if you take a look at the examples below you can get a feeling of how Kemari behaves.

IOzone Kemari sync interval[ms] dirtied pages
---------------------------------------------------------
buffered + fsync 400 3000
O_SYNC 10 80

Quoted 3 lines

In summary, if the guest executes few I/O operations, the interval between Kemari synchronizations points will increase and the number of dirtied pages will grow accordingly.

In the example above, the externally observed latency grows to 400 ms, yes?

Quoted 12 lines

What I mean is:

- choose synchronization point A
- start copying memory for synchronization point A
- output is delayed
- choose synchronization point B
- copy memory for A and B
if guest touches memory not yet copied for A, COW it
- once A copying is complete, release A output
- continue copying memory for B
- choose synchronization point B

Quoted 1 line

by keeping two synchronization points active, you don't have any pauses. The cost is maintaining copy-on-write so we can copy dirty pages for A while keeping execution.

The overall idea seems good, but if I'm understanding correctly, we need a buffer for copying memory locally, and when it gets full, or when we COW the memory for B, we still have to pause the guest to prevent from overwriting. Correct?

To make things simple, we would like to start with the synchronous transmission first, and tackle asynchronous transmission later.

Quoted 11 lines

Quoted 11 lines

Quoted 2 lines

How many pages do you copy per synchronization point for reasonably difficult workloads?

That is very workload-dependent, but if you take a look at the examples below you can get a feeling of how Kemari behaves.

IOzone Kemari sync interval[ms] dirtied pages
---------------------------------------------------------
buffered + fsync 400 3000
O_SYNC 10 80

Quoted 5 lines

Quoted 3 lines

In summary, if the guest executes few I/O operations, the interval between Kemari synchronizations points will increase and the number of dirtied pages will grow accordingly.

In the example above, the externally observed latency grows to 400 ms, yes?

Not exactly. The sync interval refers to the interval of synchronization points captured when the workload is running. In the example above, when the observed sync interval is 400ms, it takes about 150ms to sync VMs with 3000 dirtied pages. Kemari resumes I/O operations immediately once the synchronization is finished, and thus, the externally observed latency is 150ms in this case.

Quoted 18 lines

Quoted 16 lines

What I mean is:

- choose synchronization point A
- start copying memory for synchronization point A
 - output is delayed
- choose synchronization point B
- copy memory for A and B
  if guest touches memory not yet copied for A, COW it
- once A copying is complete, release A output
- continue copying memory for B
- choose synchronization point B

by keeping two synchronization points active, you don't have any pauses. The cost is maintaining copy-on-write so we can copy dirty pages for A while keeping execution.

Quoted 4 lines

The overall idea seems good, but if I'm understanding correctly, we need a buffer for copying memory locally, and when it gets full, or when we COW the memory for B, we still have to pause the guest to prevent from overwriting. Correct?

Yes.  During COW the guest would not be able to access the page, but if other vcpus access other pages, they can still continue.  So generally synchronization would be pauseless.

Quoted 2 lines

To make things simple, we would like to start with the synchronous transmission first, and tackle asynchronous transmission later.

Of course.  I'm just worried that realistic workloads will drive the latency beyond acceptable limits.

Quoted 18 lines

Quoted 11 lines

Quoted 11 lines

Quoted 2 lines

How many pages do you copy per synchronization point for reasonably difficult workloads?

That is very workload-dependent, but if you take a look at the examples below you can get a feeling of how Kemari behaves.

IOzone            Kemari sync interval[ms]  dirtied pages
---------------------------------------------------------
buffered + fsync                       400           3000 O_SYNC                                  10             80

Quoted 6 lines

Quoted 3 lines

In summary, if the guest executes few I/O operations, the interval between Kemari synchronizations points will increase and the number of dirtied pages will grow accordingly.

In the example above, the externally observed latency grows to 400 ms, yes?

Quoted 6 lines

Not exactly.  The sync interval refers to the interval of synchronization points captured when the workload is running.  In the example above, when the observed sync interval is 400ms, it takes about 150ms to sync VMs with 3000 dirtied pages.  Kemari resumes I/O operations immediately once the synchronization is finished, and thus, the externally observed latency is 150ms in this case.

Not sure I understand.

If a packet is output from a guest immediately after a synchronization point, doesn't it need to be delayed until the next synchronization point?

 So it's not just the guest pause time that matters, but also the interval between sync points?

Quoted 44 lines · Avi Kivity

Quoted 35 lines · Fernando Luis Vázquez Cao

Quoted 11 lines · Avi Kivity

Quoted 8 lines · Fernando Luis Vázquez Cao

Kemari runs paired virtual machines in an active-passive configuration and achieves whole-system replication by continuously copying the state of the system (dirty pages and the state of the virtual devices) from the active node to the passive node. An interesting implication of this is that during normal operation only the active node is actually executing code.

Quoted 3 lines

Can you characterize the performance impact for various workloads?  I assume you are running continuously in log-dirty mode.  Doesn't this make memory intensive workloads suffer?

Yes, we're running continuously in log-dirty mode.

We still do not have numbers to show for KVM, but the snippets below from several runs of lmbench using Xen+Kemari will give you an idea of what you can expect in terms of overhead. All the tests were run using a fully virtualized Debian guest with hardware nested paging enabled.

                    fork exec   sh    P/F  C/S   [us]
------------------------------------------------------
Base                  114  349 1197 1.2845  8.2 Kemari(10GbE) + FC    141  403 1280 1.2835 11.6 Kemari(10GbE) + DRBD  161  415 1388 1.3145 11.6 Kemari(1GbE) + FC     151  410 1335 1.3370 11.5 Kemari(1GbE) + DRBD   162  413 1318 1.3239 11.6
* P/F=page fault, C/S=context switch

Quoted 4 lines

The benchmarks above are memory intensive and, as you can see, the overhead varies widely from 7% to 40%. We also measured CPU bound operations, but, as expected, Kemari incurred almost no overhead.

Is lmbench fork that memory intensive?

Quoted 5 lines

Do you have numbers for benchmarks that use significant anonymous RSS? Say, a parallel kernel build.

Note that scaling vcpus will increase a guest's memory-dirtying power but snapshot rate will not scale in the same way.

I don't think lmbench is intensive but it's sensitive to memory latency. We'll measure kernel build time with minimum config, and post it later.

Quoted 4 lines

I don't think lmbench is intensive but it's sensitive to memory latency. We'll measure kernel build time with minimum config, and post it later.

Here are some quick numbers of parallel kernel compile time. The number of vcpu is 1, just for convenience.

time make -j 2 all
-----------------------------------------------------------------------------
Base: real 1m13.950s (user 1m2.742s, sys 0m10.446s)
Kemari: real 1m22.720s (user 1m5.882s, sys 0m10.882s)

time make -j 4 all
-----------------------------------------------------------------------------
Base: real 1m11.234s (user 1m2.582s, sys 0m8.643s)
Kemari: real 1m26.964s (user 1m6.530s, sys 0m12.194s)

The result of Kemari includes everything, meaning dirty pages tracking and synchronization upon I/O operations to the disk.
The compile time using j=4 under Kemari was worse than that of j=2, but I'm not sure this is due to dirty pages tracking or sync interval.

Quoted 16 lines

Quoted 4 lines

I don't think lmbench is intensive but it's sensitive to memory latency. We'll measure kernel build time with minimum config, and post it later.

Here are some quick numbers of parallel kernel compile time. The number of vcpu is 1, just for convenience.

time make -j 2 all

-----------------------------------------------------------------------------
Base:    real 1m13.950s (user 1m2.742s, sys 0m10.446s)
Kemari: real 1m22.720s (user 1m5.882s, sys 0m10.882s)

time make -j 4 all

Quoted 9 lines

-----------------------------------------------------------------------------
Base:    real 1m11.234s (user 1m2.582s, sys 0m8.643s)
Kemari: real 1m26.964s (user 1m6.530s, sys 0m12.194s)

The result of Kemari includes everything, meaning dirty pages tracking and synchronization upon I/O operations to the disk.
The compile time using j=4 under Kemari was worse than that of j=2, but I'm not sure this is due to dirty pages tracking or sync interval.

Do disk writes trigger synchronization?  Otherwise this is a very relaxed test.  I'm surprised the degradation is so low running continuously in log-dirty.

Is this an npt or ept system?  Without npt or ept I'd expect less degradation since the page tables are heavily manipulated anyway.

--
Do not meddle in the internals of kernels, for they are subtle and quick to panic.

--
To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html