50 years later, is two-phase locking the best we can do?
concurrencyfreaks.blogspot.com
50 years later, is two-phase locking the best we can do?
1–10 of 87 posts
Re: 50 years later, is two-phase locking the best we can do?
#2[flagged]
Re: 50 years later, is two-phase locking the best we can do?
#3this is a great paper that provides a framework for comparing 2 phase and paxos.
https://lamport.azurewebsites.net/video/consensus-on-transac...
Re: 50 years later, is two-phase locking the best we can do?
#4MVCC is what most databases do.
Re: 50 years later, is two-phase locking the best we can do?
#52500 years later and the best hypotenuse algorithm is still Pythagoras’.
Re: 50 years later, is two-phase locking the best we can do?
#6this is a great paper that provides a framework for comparing 2 phase and paxos. https://lamport.azurewebsites.net/video/consensus-on-transac...
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.
Re: 50 years later, is two-phase locking the best we can do?
#7this is a great paper that provides a framework for comparing 2 phase and paxos. https://lamport.azurewebsites.net/video/consensus-on-transac...
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's tolerable if a few fail or give outputs that diverge from the majority.
2PL: A method of acquiring multiple locks such that first you acquire all the required locks (first phase), then you do what you need to do, and then you release all the locks (second phase). This is in contrast to a locking scheme where lock acquisitions and releases are interspersed. This isn't strictly limited to distributed systems, although it's common to see 2PC with 2PL.
If this piques your interest, read the Spanner paper! Spanner uses all three - 2PC with 2PL for distributed read-write transactions, and Paxos for replication.
PS: "Distributed" just means there's more than one machine involved, any of which may fail independently, and communication among these machines happens over unreliable wire.
Re: 50 years later, is two-phase locking the best we can do?
#8Earlier 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…
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?
Re: 50 years later, is two-phase locking the best we can do?
#92500 years later and the best hypotenuse algorithm is still Pythagoras’.
You jest but this is a computationally slow algorithm that only works for right angle triangles in a Cartesian space. There’s very reasonable and fast trigonometric approximations. The general form would be the cosine law which applies to any triangle. We can derive this from more abstract metrics over an inner product space.. a sort of vector space of any dimension.
Re: 50 years later, is two-phase locking the best we can do?
#102500 years later and the best hypotenuse algorithm is still Pythagoras’.
You jest but this is a computationally slow algorithm that only works for right angle triangles in a Cartesian space. There’s very reasonable and fast trigonometric approximations. The general form would be the cosine law which applies to any triangle. We can derive this from more abstract metrics over an inner product space.. a sort of vector space of any dimension.
First thing I thought of is https://en.wikipedia.org/wiki/Fast_inverse_square_root