50 years later, is two-phase locking the best we can do? • Hacker News Board

Re: 50 years later, is two-phase locking the best we can do?

#31

Post by djha-skin » Sat, Sep 30, 2023, 2:51 AM UTC

We are so arrogant sometimes. The passage of time has nothing to do with reality. People seem to think that given enough time and energy and ingenuity we can do anything we want. This is not how the real world works.

Sometimes, we find a good solution, and it's the best possible one and we found it early on. We think we can do better, but we can't. A classic example of this is Euclid's fifth axiom. It wasn't proven until the 19th century that this axiom was necessary but everyone from Euclid to Gauss tried to get rid of it. Foolish.

Re: 50 years later, is two-phase locking the best we can do?

#32

Post by mjb » Sat, Sep 30, 2023, 2:55 AM UTC

thoughtlede wrote: post #8

roncesvalles wrote: post #7

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?

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.

Re: 50 years later, is two-phase locking the best we can do?

#33

Post by bigstrat2003 » Sat, Sep 30, 2023, 2:57 AM UTC

djha-skin wrote: post #31

We are so arrogant sometimes. The passage of time has nothing to do with reality. People seem to think that given enough time and energy and ingenuity we can do anything we want. This is not how the real world works. Sometimes, we find a good solution, and it's the best possible one and we found it early on. We think we can do better, but we can't. A classic example of this is Euclid's fifth axiom. It wasn't proven u…

It seems to me that while it's foolish to assume we can always improve on something, it's not at all foolish to try to do better (even if the attempts don't succeed). Asking "can we do better than this?" and trying to find a better way is a prerequisite for progress, after all.

Re: 50 years later, is two-phase locking the best we can do?

#34

Post by westurner » Sat, Sep 30, 2023, 3:11 AM UTC

roncesvalles wrote: post #7

thoughtlede wrote: post #6

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…

Concurrency control > Concurrency control in databases > 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)#Disadv...

Two-phase locking (2PL) https://en.wikipedia.org/wiki/Two-phase_locking

Two-phase commit protocol (2PC) https://en.wikipedia.org/wiki/Two-phase_commit_protocol

Paxos: https://en.wikipedia.org/wiki/Paxos_(computer_science)

Raft: https://en.wikipedia.org/wiki/Raft_(algorithm)

Consensus (computer science) https://en.wikipedia.org/wiki/Consensus_(computer_science)

Spanner: https://en.wikipedia.org/wiki/Spanner_(database)

Non-blocking algorithm; "lock-free concurrency", "wait-free" 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

"100-Gbit/s Integrated Quantum Random Number Generator Based on Vacuum Fluctuations" https://link.aps.org/doi/10.1103/PRXQuantum.4.010330

Re: tests of randomness: 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/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

Re: 50 years later, is two-phase locking the best we can do?

#35

Post by samsquire » Sat, Sep 30, 2023, 3:30 AM UTC

I'm a beginner in this topic and I find this topic interesting. I really want there to be an easy-to-deploy consistency solution.

If I have a distributed microservice architecture and I want to keep multiple datastores in synchronization or "consistent" what's the industry best practice?

A few days ago I was trying to solve the inconsistency problem with "settled timestamps" which is a kind of multiversioning idea except that timestamps elapsed with the absence of reported error represent a valid save/commit. Kind of like two phase commit with the second phase being time. The idea is that we watch the clocks of other servers and if they don't update then we know we cannot trust their settled timestamps. (My intent was to allow scaling consistency across many servers, because we don't need to wait for response for every update, we only need to wait for the next timestamp interval)

Here's my Multithreaded multiprocessing Python code to test indeterminancy. 10 threads all send eachother random updates. They also broadcast their own timestamp and the timestamps of their own perspective of the timestamps every other server.

https://replit.com/@Chronological/InconsistencySimulation#ma... (click Run and watch the output, you'll have to wait 10 seconds)

A read in this simulation is the MIN of all timestamps of all servers reported timestamps.

10 seconds into the simulation, we ask every thread for its own perspective of what the counter value is. Sometimes they will all report the same value, a lot of the time they shall be split brained.

I am aware that wall clock timestamps are not suitable for ordering in a distributed system and that logical or vector clocks should be used for ordering.

If you can get the simulation to all report the same number at any point in time, then that would be great :-)

Ordering in distributed systems is significant, as the eventual consistency of the simulation means that some values can arrive late but affect the value, meaning it is not linearizable. Bloomlang tries to solve this.

I'm specifically interested in scaling WITH consistency but I think this is quite difficult.

Re: 50 years later, is two-phase locking the best we can do?

#36

Post by rawgabbit » Sat, Sep 30, 2023, 3:48 AM UTC

samsquire wrote: post #35

I'm a beginner in this topic and I find this topic interesting. I really want there to be an easy-to-deploy consistency solution. If I have a distributed microservice architecture and I want to keep multiple datastores in synchronization or "consistent" what's the industry best practice? A few days ago I was trying to solve the inconsistency problem with "settled timestamps" which is a kind of multiversioning idea ex…

For distributed systems, the main idea is a centralized write ordering journal that is replayed by individual nodes.

Multiple systems write sequentially to the central journal. The journal is simply taking requests like a key value store. The journal is replicated to all the nodes. The nodes read from the journal and performs the complex logic requested.

Re: 50 years later, is two-phase locking the best we can do?

#37

Post by zaphirplane » Sat, Sep 30, 2023, 4:31 AM UTC

rawgabbit wrote: post #25

klabb3 wrote: post #21

One thing I didn’t quite catch was: I thought most write transactions needs consistent reads on many (contended) “objects”, but the actual writes are often just one or two objects. Is 2PL addressing this or does a write transaction take write locks on all objects?

You can take locks on all objects before you write. Most systems don’t do that. Usually there are multiple writes to complete a business process. In each step stale data is read to create a write request similar to how you place your order with the wait staff at the restaurant. The wait staff will orchestrate your request. First the chef prepares your meal according to the order ticket. Second the wait staff delivers…

IIUC, That’s a micro service way, missing cancellations and rollback and timeouts

What happens if the chef can’t fulfill the meal, the customer leaves cause the order is taking long … etc Most real life will not charge the customer is the chef can’t make the meal and cancel the cooking if the customer leaves

The analogy maybe going far ;)

Re: 50 years later, is two-phase locking the best we can do?

#38

Post by acuozzo » Sat, Sep 30, 2023, 4:40 AM UTC

samsquire wrote: post #35

I'm a beginner in this topic and I find this topic interesting. I really want there to be an easy-to-deploy consistency solution. If I have a distributed microservice architecture and I want to keep multiple datastores in synchronization or "consistent" what's the industry best practice? A few days ago I was trying to solve the inconsistency problem with "settled timestamps" which is a kind of multiversioning idea ex…

Is your inter-machine messaging asynchronous and is it possible for one of your machines to crash?

Re: 50 years later, is two-phase locking the best we can do?

#39

Post by telez » Sat, Sep 30, 2023, 4:49 AM UTC

I do not quite understand the last figure for the relaxed avl tree. For the 100 % lookup (rightmost) the TL2 algo should scale linearly with the number of threads. For read-only transactions, TL2 needs to sample the global version, then for all reads make sure the local version is less than or equal to the sampled version. given this, it is difficult to understand why the graph is sub linear and that TL2 is not as fast as the other STM implementations.

Re: 50 years later, is two-phase locking the best we can do?

#40

Post by nine_k » Sat, Sep 30, 2023, 5:16 AM UTC

rawgabbit wrote: post #36

samsquire wrote: post #35

I'm a beginner in this topic and I find this topic interesting. I really want there to be an easy-to-deploy consistency solution. If I have a distributed microservice architecture and I want to keep multiple datastores in synchronization or "consistent" what's the industry best practice? A few days ago I was trying to solve the inconsistency problem with "settled timestamps" which is a kind of multiversioning idea ex…

For distributed systems, the main idea is a centralized write ordering journal that is replayed by individual nodes. Multiple systems write sequentially to the central journal. The journal is simply taking requests like a key value store. The journal is replicated to all the nodes. The nodes read from the journal and performs the complex logic requested.

If business software practices is not enough of a proof, look at any massive online games. They all use one central server as a source of truth about the game world, and broadcast that state to the clients. Anything a client reports that diverges from the central server view is either corrected, rejected, or becomes a reason to disconnect the client for cheating attempts.

If you need strict order, that order should happen in strictly one place. (The universe itself does not support strict order at a distance, as Special Relativity shows.)