diff options
author | Patrick Steinhardt <psteinhardt@gitlab.com> | 2020-07-02 08:48:46 +0300 |
---|---|---|
committer | Patrick Steinhardt <psteinhardt@gitlab.com> | 2020-07-03 08:29:49 +0300 |
commit | abbe26db3f3a84f7498919919e3c5561d39ff800 (patch) | |
tree | 900cf600313c3148a5eb4593ecb58bcdfe842c94 /doc/beginners_guide.md | |
parent | 78873d0bfe8d091d60accb813e17c9c5e8a014ec (diff) |
transactions: Implement weighted voting
In order to make better use of reference transactions, it's essential to
have a voting mechanism that is able to reach a quorum even if a subset
of voters failed to show up or disagreed with the result. This is most
helpful e.g. in our concept of primary/secondaries, where we can
for example establish the policy that only the primary has a voting
right while all the others don't or that at least primary and another
node need to agree on the result. This is now made possible by
introducing weighted voting to the transaction manager.
The mechanism is quite simple: given a set of voters, each voter is
assigned a number of votes in the range `[0,maxInt]`. Only when the
accumulated votes of all voters for a given item exceeds a certain
threshold will the transaction be committed. If the threshold is lower
than the accumulated votes or if any node has no votes, then a certain
subset of nodes may fail in the process and will get an "abort" message,
while the others get a "commit" message.
In order to enable somewhat flexible strategies, the caller is allowed
to choose a threshold. There are two important limitations, though:
- The threshold may not exceed the accumulated votes of all nodes.
If it did, then no matter how the voters vote, the transaction
would always be aborted.
- The threshold always needs to be at least `ceil(votes(nodes)/2)`.
If it's lower than that, then a transaction may reach multiple
quorums and thus commit different results.
Note that the resulting voting code is quite complex, which mostly stems
from the fact that we need to make sure that the channel signaling that
the transaction has reached quorum doesn't get closed twice. We thus
need to ensure two properties:
- The first voter casting a vote that causes it to exceed the
threshold will close the channel. All the other voters will check
whether any vote exists that exceeds the threshold already, in
which case they know not to close the channel.
- In case no quorum is reached, the last node to cast its vote will
close the channel to signal that all participants are done with
the process. As no voter is allowed to cast votes multiple times,
this is safe.
Together, these two conditions suffice to make sure that there's no way
the channel can be closed twice.
Diffstat (limited to 'doc/beginners_guide.md')
0 files changed, 0 insertions, 0 deletions