Re: Quorum commit for multiple synchronous replication.

Hello, context switch was complete that time, sorry.

There's multiple "target LET"s. So we need kth-largest LTEs.

At Wed, 7 Dec 2016 19:04:23 +0900, Michael Paquier <michael(dot)paquier(at)gmail(dot)com> wrote in <CAB7nPqR10OnEL5XxW1DVYvAXmtpEVNCMi=V-6Jb_9owFuY8aSg(at)mail(dot)gmail(dot)com>
> On Wed, Dec 7, 2016 at 5:17 PM, Masahiko Sawada <sawada(dot)mshk(at)gmail(dot)com> wrote:
> > Sorry, I could not understand this algorithm. Could you elaborate
> > this? It takes only O(n) times?
>
> Nah, please forget that, that was a random useless thought. There is
> no way to be able to select the k-th element without knowing the
> hierarchy induced by the others, which is what the partial sort would
> help with here.

So, let's consider for some cases,

- needing 3-quorum among 5 standbys.

There's no problem whatever make kth-largest we choose.
Of course qsorts are fine.

- needing 10 quorums among 100 standbys.

I'm not sure if there's any difference with 3/5.

- needing 10 quorums among 1000 standbys.
Obviously qsorts are doing too much. Any kind of kth-largest
algorithm should be involved. For instance quickselect with O(n
long n) - O(n) seems better in comparison to O(n log n) - O(n^2)
of qsort.

- needing 700 quorums among 1000 standbys.

I don't think this case is worth consider but kth-largest is
better even for this case.

If we don't 700/1000 is out of at least the current scope, I also
recommend to use kth-largest selection.

If not, the quorum calculation is triggered by every standby
reply message and the frequency of the calculation seems near to
the frequency of WAL-insertion for the worst case. (Right?) Even
the kth-largest takes too long time to have 1000 standys.

Maintining kth-largest in shared memory needs less CPU but leads
to more bad contention on the shared memory.

Inversely, we already have waiting LSNs of backends in procarray.
If we have another array in the order of waiting LSNs and having
a condition varialble on the number of comforming
walsenders. Every walsender can individually looking up it and
count it up. It might performs better but I'm not sure.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center