Skip to contentSkip to conversation

COLO HA Project proposal

RFC Hongyang Yang 5 participants 11 messages Jun 24, 2014 – Jul 8, 2014 KVM

lore
Share & tools
lore
#0 lore raw

Background:
COLO HA project is a high availability solution. Both primary
VM (PVM) and secondary VM (SVM) run in parallel. They receive the same request from client, and generate response in parallel too. If the response packets from PVM and SVM are identical, they are released immediately. Otherwise, a VM checkpoint (on demand) is conducted. The idea is presented in Xen summit 2012, and 2013, and academia paper in SOCC 2013. It's also presented in KVM forum 2013:
http://www.linux-kvm.org/wiki/images/1/1d/Kvm-forum-2013-COLO.pdf
Please refer to above document for detailed information.

The attached was the architecture of kvm-COLO we proposed.
- COLO Manager: Requires modifications of qemu
- COLO Controller
COLO Controller includes modifications of save/restore
flow just like MC(macrocheckpoint), a memory cache on secondary VM which cache the dirty pages of primary VM and a failover module which provides APIs to communicate with external heartbead module.
- COLO Disk Manager
When pvm writes data into image, the colo disk manger
captures this data and send it to the colo disk manger which makes sure the context of svm's image is consentient with the context of pvm's image.

- COLO Agent("Proxy module" in the arch picture) We need an agent to compare the packets returned by Primary VM and Secondary VM, and decide whether to start a checkpoint according to some rules. It is a linux kernel module for host.

- Other minor modifications
We may need other modifications for better performance.

Signature · 2 lines
Thanks,
Yang.
#1 lore raw

* Hongyang Yang ([email protected]) wrote:

Hi Yang,

Quoted 11 lines

Background:
COLO HA project is a high availability solution. Both primary
VM (PVM) and secondary VM (SVM) run in parallel. They receive the same request from client, and generate response in parallel too. If the response packets from PVM and SVM are identical, they are released immediately. Otherwise, a VM checkpoint (on demand) is conducted. The idea is presented in Xen summit 2012, and 2013, and academia paper in SOCC 2013. It's also presented in KVM forum 2013:
http://www.linux-kvm.org/wiki/images/1/1d/Kvm-forum-2013-COLO.pdf
Please refer to above document for detailed information.

Yes, I remember that talk - very interesting.

I didn't quite understand a couple of things though, perhaps you can explain:
1) If we ignore the TCP sequence number problem, in an SMP machine
don't we get other randomnesses - e.g. which core completes something first, or who wins a lock contention, so the output stream might not be identical - so do those normal bits of randomness cause the machines to flag as out-of-sync?

2) If the PVM has decided that the SVM is out of sync (due to 1) and
the PVM fails at about the same point - can we switch over to the SVM?

I'm worried that due to (1) there are periods where the system is out-of-sync and a failure of the PVM is not protected. Does that happen? If so how often?

Quoted 5 lines

The attached was the architecture of kvm-COLO we proposed.
- COLO Manager: Requires modifications of qemu
- COLO Controller
COLO Controller includes modifications of save/restore
flow just like MC(macrocheckpoint), a memory cache on

Quoted 8 lines

secondary VM which cache the dirty pages of primary VM and a failover module which provides APIs to communicate with external heartbead module.
- COLO Disk Manager
When pvm writes data into image, the colo disk manger
captures this data and send it to the colo disk manger which makes sure the context of svm's image is consentient with the context of pvm's image.

I wonder if there is anyway to coordinate this between COLO, Michael Hines microcheckpointing and the two separate reverse-execution projects that also need to do some similar things.
Are there any standard APIs for the heartbeet thing we can already tie into?

Quoted 5 lines

- COLO Agent("Proxy module" in the arch picture) We need an agent to compare the packets returned by Primary VM and Secondary VM, and decide whether to start a checkpoint according to some rules. It is a linux kernel module for host.

Why is that a kernel module, and how does it communicate the state to the QEMU instance?

Quoted 2 lines

- Other minor modifications
We may need other modifications for better performance.

Dave
P.S. I'm starting to look at fault-tolerance stuff, but haven't got very far yet, so starting to try and understand the details of COLO, microcheckpointing, etc

Quoted 3 lines
Signature · 2 lines
Thanks,
Yang.

--
Dr. David Alan Gilbert / [email protected] / Manchester, UK

#2 lore raw

Hi David,

Quoted 18 lines · Dr. David Alan Gilbert

* Hongyang Yang ([email protected]) wrote:

Hi Yang,

Quoted 11 lines

Background:
COLO HA project is a high availability solution. Both primary
VM (PVM) and secondary VM (SVM) run in parallel. They receive the same request from client, and generate response in parallel too. If the response packets from PVM and SVM are identical, they are released immediately. Otherwise, a VM checkpoint (on demand) is conducted. The idea is presented in Xen summit 2012, and 2013, and academia paper in SOCC 2013. It's also presented in KVM forum 2013:
http://www.linux-kvm.org/wiki/images/1/1d/Kvm-forum-2013-COLO.pdf
Please refer to above document for detailed information.

Yes, I remember that talk - very interesting.

Quoted 7 lines

I didn't quite understand a couple of things though, perhaps you can explain:
1) If we ignore the TCP sequence number problem, in an SMP machine
don't we get other randomnesses - e.g. which core completes something first, or who wins a lock contention, so the output stream might not be identical - so do those normal bits of randomness cause the machines to flag as out-of-sync?

It's about COLO agent, CCing Congyang, he can give the detailed explanation.

Quoted 3 lines

2) If the PVM has decided that the SVM is out of sync (due to 1) and
the PVM fails at about the same point - can we switch over to the SVM?

Yes, we can switch over, we have some mechanisms to ensure the SVM's state is consentient:
- memory cache.
The memory cache was initially the same as PVM's memory. At
checkpoint, we cache the dirty memory of PVM while transporting the memory, write cached memory to SVM when we received all PVM memory (we only need to write memory that was both dirty on PVM and SVM from last checkpoint). This solves problem 2) you've mentioned above:
If PVM fails while checkpointing, SVM will discard the cached memory and continue to run and to provide service just as it is.

- COLO Disk manager
Like memory cache, COLO Disk manager caches the Disk modifications
of PVM, and write it to SVM Disk when checkpointing. If PVM fails while checkpointing, SVM will discard the cached Disk modifications.

Quoted 19 lines

I'm worried that due to (1) there are periods where the system is out-of-sync and a failure of the PVM is not protected. Does that happen? If so how often?

Quoted 5 lines

The attached was the architecture of kvm-COLO we proposed.
- COLO Manager: Requires modifications of qemu
- COLO Controller
COLO Controller includes modifications of save/restore
flow just like MC(macrocheckpoint), a memory cache on

Quoted 8 lines

secondary VM which cache the dirty pages of primary VM and a failover module which provides APIs to communicate with external heartbead module.
- COLO Disk Manager
When pvm writes data into image, the colo disk manger
captures this data and send it to the colo disk manger which makes sure the context of svm's image is consentient with the context of pvm's image.

Quoted 5 lines

I wonder if there is anyway to coordinate this between COLO, Michael Hines microcheckpointing and the two separate reverse-execution projects that also need to do some similar things.
Are there any standard APIs for the heartbeet thing we can already tie into?

Sadly we have checked MC, it does not have heartbeat support for now.

Quoted 9 lines
Quoted 6 lines

- COLO Agent("Proxy module" in the arch picture) We need an agent to compare the packets returned by Primary VM and Secondary VM, and decide whether to start a checkpoint according to some rules. It is a linux kernel module for host.

Why is that a kernel module, and how does it communicate the state to the QEMU instance?

The reason we made this a kernel module is to gain better performance. We can easily hook the packets in a kernel module.
QEMU instance uses ioctl() to communicate with the COLO Agent.

Quoted 18 lines
Quoted 3 lines

- Other minor modifications
We may need other modifications for better performance.

Dave
P.S. I'm starting to look at fault-tolerance stuff, but haven't got very far yet, so starting to try and understand the details of COLO, microcheckpointing, etc

Quoted 3 lines

--
Thanks,
Yang.

--
Dr. David Alan Gilbert / [email protected] / Manchester, UK .

Signature · 2 lines
Thanks,
Yang.
#3 lore raw
Quoted 9 lines
Quoted 8 lines

I didn't quite understand a couple of things though, perhaps you can explain:
1) If we ignore the TCP sequence number problem, in an SMP machine
don't we get other randomnesses - e.g. which core completes something first, or who wins a lock contention, so the output stream might not be identical - so do those normal bits of randomness cause the machines to flag as out-of-sync?

Quoted 3 lines

It's about COLO agent, CCing Congyang, he can give the detailed explanation.

Let me clarify on this issue. COLO didn't ignore the TCP sequence number, but uses a new implementation to make the sequence number to be best effort identical between the primary VM (PVM) and secondary VM (SVM). Likely, VMM has to synchronize the emulation of randomization number generation mechanism between the PVM and SVM, like the lock-stepping mechanism does.

Further mnore, for long TCP connection, we can rely on the (on-demand) VM checkpoint to get the identical Sequence number both in PVM and SVM.

Thanks, Eddie

#4 lore raw
Quoted 13 lines · * Dong, Eddie ([email protected]) wrote:
Quoted 9 lines
Quoted 8 lines

I didn't quite understand a couple of things though, perhaps you can explain:
1) If we ignore the TCP sequence number problem, in an SMP machine
don't we get other randomnesses - e.g. which core completes something first, or who wins a lock contention, so the output stream might not be identical - so do those normal bits of randomness cause the machines to flag as out-of-sync?

Quoted 3 lines

It's about COLO agent, CCing Congyang, he can give the detailed explanation.

Quoted 8 lines

Let me clarify on this issue. COLO didn't ignore the TCP sequence number, but uses a new implementation to make the sequence number to be best effort identical between the primary VM (PVM) and secondary VM (SVM). Likely, VMM has to synchronize the emulation of randomization number generation mechanism between the PVM and SVM, like the lock-stepping mechanism does.

Further mnore, for long TCP connection, we can rely on the (on-demand) VM checkpoint to get the identical Sequence number both in PVM and SVM.

That wasn't really my question; I was worrying about other forms of randomness, such as winners of lock contention, and other SMP non-determinisms, and I'm also worried by what proportion of time the system can't recover from a failure due to being unable to distinguish an SVM failure from a randomness issue.

Dave

Quoted 3 lines

Thanks, Eddie

--
Dr. David Alan Gilbert / [email protected] / Manchester, UK

#5 lore raw
Quoted 10 lines
Quoted 6 lines

Let me clarify on this issue. COLO didn't ignore the TCP sequence number, but uses a new implementation to make the sequence number to be best effort identical between the primary VM (PVM) and secondary VM (SVM). Likely, VMM has to synchronize the emulation of randomization number generation mechanism between the PVM and SVM, like the

lock-stepping mechanism does.

Quoted 3 lines

Further mnore, for long TCP connection, we can rely on the (on-demand) VM checkpoint to get the identical Sequence number both in PVM and

Quoted 8 lines

SVM.

That wasn't really my question; I was worrying about other forms of randomness, such as winners of lock contention, and other SMP non-determinisms, and I'm also worried by what proportion of time the system can't recover from a failure due to being unable to distinguish an SVM failure from a randomness issue.

Thanks Dave:
Whether the randomness value/branch/code path the PVM and SVM may have,
It is only a performance issue. COLO never assumes the PVM and SVM has same internal Machine state. From correctness p.o.v, as if the PVM and SVM generate Identical response, we can view the SVM is a valid replica of PVM, and the SVM can take over When the PVM suffers from hardware failure. We can view the client is all the way talking with the SVM, without the notion of PVM. Of course, if the SVM dies, we can regenerate a copy of PVM with a new checkpoint too.
The SOCC paper has the detail recovery model :)

Thanks, Eddie

#6 lore raw
Quoted 18 lines · * Dong, Eddie ([email protected]) wrote:
Quoted 10 lines
Quoted 6 lines

Let me clarify on this issue. COLO didn't ignore the TCP sequence number, but uses a new implementation to make the sequence number to be best effort identical between the primary VM (PVM) and secondary VM (SVM). Likely, VMM has to synchronize the emulation of randomization number generation mechanism between the PVM and SVM, like the

lock-stepping mechanism does.

Quoted 3 lines

Further mnore, for long TCP connection, we can rely on the (on-demand) VM checkpoint to get the identical Sequence number both in PVM and

Quoted 8 lines

SVM.

That wasn't really my question; I was worrying about other forms of randomness, such as winners of lock contention, and other SMP non-determinisms, and I'm also worried by what proportion of time the system can't recover from a failure due to being unable to distinguish an SVM failure from a randomness issue.

Quoted 9 lines

Thanks Dave:
Whether the randomness value/branch/code path the PVM and SVM may have,
It is only a performance issue. COLO never assumes the PVM and SVM has same internal Machine state. From correctness p.o.v, as if the PVM and SVM generate Identical response, we can view the SVM is a valid replica of PVM, and the SVM can take over When the PVM suffers from hardware failure. We can view the client is all the way talking with the SVM, without the notion of PVM. Of course, if the SVM dies, we can regenerate a copy of PVM with a new checkpoint too.
The SOCC paper has the detail recovery model :)

I've had a read; I think the bit I was asking about was what you labelled 'D' in that papers fig.4 - so I think that does explain it for me.
But I also have some more questions:

1) 5.3.3 Web server
a) In fig 11 it shows Remus's performance dropping off with the number of threads - why is that? Is it just an increase in the amount of memory changes in each snapshot?
b) Is fig 11/12 measured with all of the TCP optimisations shown in fig 13 on?

2) Did you manage to overcome the issue shown in 5.6 with newer guest kernels degredation - could you just fall back to micro checkpointing if the guests diverge too quickly?

3) Was the link between the two servers for synchronisation a low-latency dedicated connection?

4) Did you try an ftp PUT benchmark using external storage - i.e. that wouldn't have the local disc synchronisation overhead?

Dave

Quoted 5 lines

Thanks, Eddie

--
Dr. David Alan Gilbert / [email protected] / Manchester, UK

#7 lore raw
Quoted 9 lines
Quoted 2 lines

Thanks Dave:
Whether the randomness value/branch/code path the PVM and SVM

may

Quoted 6 lines

have, It is only a performance issue. COLO never assumes the PVM and SVM has same internal Machine state. From correctness p.o.v, as if the PVM and SVM generate Identical response, we can view the SVM is a valid replica of PVM, and the SVM can take over When the PVM suffers from hardware failure. We can view the client is all the way talking with the SVM, without the notion of PVM. Of course, if the SVM dies, we

Quoted 5 lines

can regenerate a copy of PVM with a new checkpoint too.

Quoted 1 line

The SOCC paper has the detail recovery model :)

I've had a read; I think the bit I was asking about was what you labelled 'D' in that papers fig.4 - so I think that does explain it for me.

Very good :)

Quoted 7 lines

But I also have some more questions:

1) 5.3.3 Web server
a) In fig 11 it shows Remus's performance dropping off with the number
of threads - why is that? Is it
just an increase in the amount of memory changes in each
snapshot?

I didn't dig into details of them, but document the throughput we observed. I felt a bit stranger too, memory dirty page set may be larger than small connection Case, but I am not sure and that is the data we saw :(

Quoted 2 lines

b) Is fig 11/12 measured with all of the TCP optimisations shown in fig
13 on?

Yes.

Quoted 4 lines

2) Did you manage to overcome the issue shown in 5.6 with newer guest
kernels degredation - could you just fall
back to micro checkpointing if the guests diverge too quickly?

In general, I would say the COLO performance for these 2 workloads is pretty good, and I actually didn't list the subsection 5.6 initially. It is the conference sepherd who ask me to add this paragraph to make the paper to be balanced :)

In summary, COLO can have very good MP-guest performance comparing with Remus, with the payment of potential optimization/modification effort to guest TCP/IP stack. One solution may Not work for all workloads, but it provides a large room for OSVs to provide customized solution for a specific usage -- which I think is very good for open source biz model: make money through consultant. Huawei technology Ltd. announced to support COLO in there cloud OS, Probably for specific usage too.

Quoted 3 lines

3) Was the link between the two servers for synchronisation a low-latency
dedicated connection?

We use 10 Gbps NIC in the paper, and yes it is dedicated link, but the solution itself doesn't require dedicated link.

Quoted 4 lines

4) Did you try an ftp PUT benchmark using external storage - i.e. that
wouldn't have the local disc
synchronisation overhead?

Not yet.
External network shared storage works, but today the performance may be not that good, because our optimization so far is still very limited. It is just an initial effort to make the 2 common workloads happy. We believe there are large room ahead to make the response of TCP/IP stack more predictable. Once the basic COLO stuff is ready for product and accepted by the industry, it is possible we may impact TCP community to have this kind of predictability
in mind for the future protocol development, which will greatly help the performance.

Thx Eddie

#8 lore raw
In reply to Hongyang Yang
Quoted 9 lines · Hongyang Yang
Quoted 6 lines

I wonder if there is anyway to coordinate this between COLO, Michael Hines microcheckpointing and the two separate reverse-execution projects that also need to do some similar things.
Are there any standard APIs for the heartbeet thing we can already tie into?

Sadly we have checked MC, it does not have heartbeat support for now.

Right, MC by itself does not need heartbeats out-of-the box.

Probably the best thing we can coordinate from MC is the part of the data transmission protocol and memory management - because we need to make sure you guys are staying compatible with the QEMUFile abstraction the same way that the TCP and RDMA protocols are staying compatible with that abstraction.

COLO should able to run over any protocol supported by QEMUFile.

I can help with some of that...

- Michael

#9 lore raw

Hi Michael,

Thank you for paying attention on this.

Quoted 8 lines · Michael R. Hines
Quoted 7 lines · Hongyang Yang
Quoted 6 lines

I wonder if there is anyway to coordinate this between COLO, Michael Hines microcheckpointing and the two separate reverse-execution projects that also need to do some similar things.
Are there any standard APIs for the heartbeet thing we can already tie into?

Quoted 7 lines
Quoted 2 lines

Sadly we have checked MC, it does not have heartbeat support for now.

Right, MC by itself does not need heartbeats out-of-the box.

Probably the best thing we can coordinate from MC is the part of the data transmission protocol and memory management - because we need

Yes, that's what we have planned.

Quoted 5 lines

to make sure you guys are staying compatible with the QEMUFile abstraction the same way that the TCP and RDMA protocols are staying compatible with that abstraction.

COLO should able to run over any protocol supported by QEMUFile.

Indeed.

Quoted 7 lines

I can help with some of that...

- Michael

.

Signature · 2 lines
Thanks,
Yang.