4 ms·

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 o

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.

roncesvalles 3y ago
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.
- thoughtlede 3y ago
  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?
  - foota 3y ago
    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.
    - reubenbond 3y ago
      Which systems use Calvin-like protocols?
      - foota 3y ago
        FaunaDB is the most popular, I believe.
  - mjb 3y ago
    2PC (or atomic commitment more generally) is needed for sharded/partitioned systems with different data on each node. In these systems, each node gets a vote on whether a transaction should be allowed to commit. Replication, making multiple copies of the same data, doesn't need 2PC. Instead, algorithms like Paxos, Raft, or chain replication are used.
- User23 3y ago
  I find it interesting that “distributed” and “concurrent” end up falling under the mathematical concept of nondeterminism with respect to correctness. Of course a practically efficient implementation has additional concerns.
- westurner 3y ago
  Concurrency control > Concurrency control in databases > Why is concurrency control needed?: https://en.m.wikipedia.org/wiki/Concurrency_control#Why_is_concurrency_control_needed https://en.m.wikipedia.org/wiki/Concurrency_control#Why_is_c...? Locks (computer science) > Disadvantages: https://en.wikipedia.org/wiki/Lock_(computer_science)#Disadvantages https://en.wikipedia.org/wiki/Lock_(computer_science)#Disadv... Two-phase locking (2PL) https://en.wikipedia.org/wiki/Two-phase_locking https://en.wikipedia.org/wiki/Two-phase_locking Two-phase commit protocol (2PC) https://en.wikipedia.org/wiki/Two-phase_commit_protocol https://en.wikipedia.org/wiki/Two-phase_commit_protocol Paxos: https://en.wikipedia.org/wiki/Paxos_(computer_science) https://en.wikipedia.org/wiki/Paxos_(computer_science) Raft: https://en.wikipedia.org/wiki/Raft_(algorithm) https://en.wikipedia.org/wiki/Raft_(algorithm) Consensus (computer science) https://en.wikipedia.org/wiki/Consensus_(computer_science) https://en.wikipedia.org/wiki/Consensus_(computer_science) Spanner: https://en.wikipedia.org/wiki/Spanner_(database) https://en.wikipedia.org/wiki/Spanner_(database) Non-blocking algorithm; "lock-free concurrency", "wait-free" https://en.wikipedia.org/wiki/Non-blocking_algorithm https://en.wikipedia.org/wiki/Non-blocking_algorithm "Ask HN: Why don't PCs have better entropy sources?" [for generating txids/uuids] https://news.ycombinator.com/item?id=30877296 https://news.ycombinator.com/item?id=30877296 "100-Gbit/s Integrated Quantum Random Number Generator Based on Vacuum Fluctuations" https://link.aps.org/doi/10.1103/PRXQuantum.4.010330 https://link.aps.org/doi/10.1103/PRXQuantum.4.010330 Re: tests of randomness: https://mail.python.org/archives/list/python-ideas@python.org/message/T3CM5FIVVUZRDP7RQ2QRNQTPWUR4WAR7/ https://mail.python.org/archives/list/python-ideas@python.or... TIL there's a regular heartbeat in the quantum foam; there's a regular monotonic heartbeat in the quantum Rydberg wave packet interference; and that should be useful for distributed applications with and without vector clocks and an initial time synchronization service (WhiteRabbit > PTP > NTP Network Time Protocol) https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.4.043041 https://journals.aps.org/prresearch/abstract/10.1103/PhysRev... : > The [quantum time-keeping application of this research] relies on the unique fingerprint that is created by the time-dependent photoionization of these complex wave packets. These fingerprints determine how much time has passed since the wave packet was formed and provide an assurance that the measured time is correct. Unlike any other clock, this quantum watch does not utilize a counter and is fully quantum mechanical in its nature. The quantum watch has the potential to become an invaluable tool in pump-probe spectroscopy due to its simplicity, assurance of accuracy, and ability to provide an absolute timestamp, i.e., there is no need to find time zero. IIUC a Rydberg antenna can read and/or write such noise? "Patterns of Distributed Systems (2022)" https://news.ycombinator.com/item?id=36504073 https://news.ycombinator.com/item?id=36504073

roncesvalles 3y ago

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.

thoughtlede 3y ago
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?
- foota 3y ago
  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.
  - reubenbond 3y ago
    Which systems use Calvin-like protocols?
    - foota 3y ago
      FaunaDB is the most popular, I believe.
- mjb 3y ago
  2PC (or atomic commitment more generally) is needed for sharded/partitioned systems with different data on each node. In these systems, each node gets a vote on whether a transaction should be allowed to commit. Replication, making multiple copies of the same data, doesn't need 2PC. Instead, algorithms like Paxos, Raft, or chain replication are used.
User23 3y ago
I find it interesting that “distributed” and “concurrent” end up falling under the mathematical concept of nondeterminism with respect to correctness. Of course a practically efficient implementation has additional concerns.
westurner 3y ago
Concurrency control > Concurrency control in databases > Why is concurrency control needed?: https://en.m.wikipedia.org/wiki/Concurrency_control#Why_is_concurrency_control_needed https://en.m.wikipedia.org/wiki/Concurrency_control#Why_is_c...? Locks (computer science) > Disadvantages: https://en.wikipedia.org/wiki/Lock_(computer_science)#Disadvantages https://en.wikipedia.org/wiki/Lock_(computer_science)#Disadv... Two-phase locking (2PL) https://en.wikipedia.org/wiki/Two-phase_locking https://en.wikipedia.org/wiki/Two-phase_locking Two-phase commit protocol (2PC) https://en.wikipedia.org/wiki/Two-phase_commit_protocol https://en.wikipedia.org/wiki/Two-phase_commit_protocol Paxos: https://en.wikipedia.org/wiki/Paxos_(computer_science) https://en.wikipedia.org/wiki/Paxos_(computer_science) Raft: https://en.wikipedia.org/wiki/Raft_(algorithm) https://en.wikipedia.org/wiki/Raft_(algorithm) Consensus (computer science) https://en.wikipedia.org/wiki/Consensus_(computer_science) https://en.wikipedia.org/wiki/Consensus_(computer_science) Spanner: https://en.wikipedia.org/wiki/Spanner_(database) https://en.wikipedia.org/wiki/Spanner_(database) Non-blocking algorithm; "lock-free concurrency", "wait-free" https://en.wikipedia.org/wiki/Non-blocking_algorithm https://en.wikipedia.org/wiki/Non-blocking_algorithm "Ask HN: Why don't PCs have better entropy sources?" [for generating txids/uuids] https://news.ycombinator.com/item?id=30877296 https://news.ycombinator.com/item?id=30877296 "100-Gbit/s Integrated Quantum Random Number Generator Based on Vacuum Fluctuations" https://link.aps.org/doi/10.1103/PRXQuantum.4.010330 https://link.aps.org/doi/10.1103/PRXQuantum.4.010330 Re: tests of randomness: https://mail.python.org/archives/list/python-ideas@python.org/message/T3CM5FIVVUZRDP7RQ2QRNQTPWUR4WAR7/ https://mail.python.org/archives/list/python-ideas@python.or... TIL there's a regular heartbeat in the quantum foam; there's a regular monotonic heartbeat in the quantum Rydberg wave packet interference; and that should be useful for distributed applications with and without vector clocks and an initial time synchronization service (WhiteRabbit > PTP > NTP Network Time Protocol) https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.4.043041 https://journals.aps.org/prresearch/abstract/10.1103/PhysRev... : > The [quantum time-keeping application of this research] relies on the unique fingerprint that is created by the time-dependent photoionization of these complex wave packets. These fingerprints determine how much time has passed since the wave packet was formed and provide an assurance that the measured time is correct. Unlike any other clock, this quantum watch does not utilize a counter and is fully quantum mechanical in its nature. The quantum watch has the potential to become an invaluable tool in pump-probe spectroscopy due to its simplicity, assurance of accuracy, and ability to provide an absolute timestamp, i.e., there is no need to find time zero. IIUC a Rydberg antenna can read and/or write such noise? "Patterns of Distributed Systems (2022)" https://news.ycombinator.com/item?id=36504073 https://news.ycombinator.com/item?id=36504073