11–20 of 87 posts
MVCC is what most databases do.
2500 years later and the best hypotenuse algorithm is still Pythagoras’.
Earlier quoted context omitted.
A little summary: 2PC: An algorithm used in the context of distributed transactions where each machine handles a different part of the transaction. This means that nothing is redundant - the success of each and every participant is required for the transaction to be committed. Paxos/Raft/consensus: An algorithm usually used in the context of distributed replication. Since every participant is doing the same thing, it…
In a multi-replica system, where, say, we cannot tolerate any failures or lags, is 2PC used in practice to achieve consensus? Or are there other methods for achieving such strict consensus?
MVCC is what most databases do.
While it’s not mentioned, I suppose you want to prioritize older transactions in order to prevent long-running transactions from being starved by shorter-running transactions. (If one long transaction conflicts with an average of, say, three short transactions, and on each conflict it’s effectively random who wins, then each long transaction has only a 1/8 chance of winning all three conflicts and being able to commit.)
But preventing starvation only requires older transactions to be prioritized most of the time, not every single time, especially not if the transaction is only slightly older. So some kind of timestamp / cycle counter should work fine, even if there’s skew between threads or other sources of inaccuracy. Ties could be broken by thread ID, or again by having both sides abort.
Earlier quoted context omitted.
In a multi-replica system, where, say, we cannot tolerate any failures or lags, is 2PC used in practice to achieve consensus? Or are there other methods for achieving such strict consensus?
There are other means, the most common being Calvin like protocols where every replica deterministically processes some log, and so only one round of distributed calls is necessary.
Earlier quoted context omitted.
Two-phase locking is different from two-phase commit, in spite of an overlap in their naming. Two-phase commit is relevant to be compared against Paxos - both of which fall under the category of consensus protocols. Two-phase locking is a concurrency control mechanism.
A little summary: 2PC: An algorithm used in the context of distributed transactions where each machine handles a different part of the transaction. This means that nothing is redundant - the success of each and every participant is required for the transaction to be committed. Paxos/Raft/consensus: An algorithm usually used in the context of distributed replication. Since every participant is doing the same thing, it…
2500 years later and the best hypotenuse algorithm is still Pythagoras’.
[1] https://www.cs.utexas.edu/~EWD/transcriptions/EWD09xx/EWD975...
For Wait-Or-Die, do you really need to fetch_and_add to get a transaction ID? Do you need a transaction ID at all? It sounds like the goal is just to have an arbitrary-but-consistent ordering of active transactions so that different transactions can agree on who should wait and who should die in the event of a conflict. So why not just use the thread ID? Or even a random number might work (if ties are treated as “die…
They (and others) are great for this kind of case - and many others.
For Wait-Or-Die, do you really need to fetch_and_add to get a transaction ID? Do you need a transaction ID at all? It sounds like the goal is just to have an arbitrary-but-consistent ordering of active transactions so that different transactions can agree on who should wait and who should die in the event of a conflict. So why not just use the thread ID? Or even a random number might work (if ties are treated as “die…
I would use a ULID rather than thread ID. https://github.com/ulid/spec They (and others) are great for this kind of case - and many others.
There is also a draft to make a new uuid variant – uuid v7 – that will be very similar to how ulid works.
https://www.ietf.org/archive/id/draft-peabody-dispatch-new-u...