Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

concurrencyfreaks.blogspot.com

Post reply on HN
Print view View original

41–50 of 87 posts

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

#41

Post by colanderman »

telez wrote: post #39

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 fa…

I don't see such a graph for TL2? I do see one for TLRW though which does use reader locks, hence the scalability cap.

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

#42

Post by telez »

colanderman wrote: post #41
telez wrote: post #39

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 fa…

I don't see such a graph for TL2? I do see one for TLRW though which does use reader locks, hence the scalability cap.

the chart doesn't seem visible on ios safari but i can see it on firefox desktop however, the figure seems to be the same as from the linked paper: https://zenodo.org/record/7886718

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

#43

Post by layer8 »

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…

I’d suggest to re-evaluate if you really, really need (a) distributed data stores and (b) synchronous consistency. Things become much simpler if you can forego one of them.

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

#44

Post by foota »

reubenbond wrote: post #16
foota wrote: post #13

Earlier quoted context omitted.

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.

Which systems use Calvin-like protocols?

FaunaDB is the most popular, I believe.

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

#45

Post by infogulch »

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…

I suspect TigerBeetle DB will be the industry benchmark for consistent, high throughput, fault tolerant, distributed databases in 5 years.

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

#46

Post by masklinn »

techdragon wrote: post #23
codetrotter wrote: post #20

Earlier quoted context omitted.

ulid is great, I use it a lot. 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...

I use ULID a lot too and It’s frustrating how close the new spec UUIDs are to it without actually being the same… so I’ve got a bunch of code to modify once Postgres supports generation of the new UUIDs server side without extensions or stored procedures. Relatively painless work, but frustrating since it could have been avoided.

> frustrating since it could have been avoided.

How? UUID is a structured format so the only options I can see is ulid creating their own unregistered uuid variant (probably a terrible idea) or adding ulid support to postgres (nothing to do with uuid).

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

#48

Post by techdragon »

masklinn wrote: post #46
techdragon wrote: post #23

Earlier quoted context omitted.

I use ULID a lot too and It’s frustrating how close the new spec UUIDs are to it without actually being the same… so I’ve got a bunch of code to modify once Postgres supports generation of the new UUIDs server side without extensions or stored procedures. Relatively painless work, but frustrating since it could have been avoided.

> frustrating since it could have been avoided. How? UUID is a structured format so the only options I can see is ulid creating their own unregistered uuid variant (probably a terrible idea) or adding ulid support to postgres (nothing to do with uuid).

I'd love for Postgres to adopt ULID as a first class variant of the same basic 128bit wide binary optimized column type they use for UUIDs, but I don't expect they will, while its "popular" its not likely popular enough to have support for them to maintain it in the long run... Also the smart money ahead of time would have been for the ULID spec to sacrifice a few data bits to leave the version specifying sections of the bit field layout unused in the ULID binary spec (https://github.com/ulid/spec#binary-layout-and-byte-order) for the sake of future compatibility with "proper" UUIDs... Performing one quick bitfield modification on every row in PostgreSQL would have been less painful as in set bit, vs load parse, repack in order to re-computing the appropriate UUIDv7s (or UUIDv8s for some reason) since the primary key update transaction should be roughly the same speed either way.

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

#49

Post by colanderman »

telez wrote: post #42
colanderman wrote: post #41

Earlier quoted context omitted.

I don't see such a graph for TL2? I do see one for TLRW though which does use reader locks, hence the scalability cap.

the chart doesn't seem visible on ios safari but i can see it on firefox desktop however, the figure seems to be the same as from the linked paper: https://zenodo.org/record/7886718

Ah ok I found it there, I see what you mean now. My only guess would be cache effects? With that large AVL tree (1 M entries, so likely dozens of MiB), you are escaping L2 cache and hitting shared L3 or main memory for a large portion of lookups, and are bandwidth-constrained at the die level, thus adding that knee (which I think is visible with some of the other algorithms as well).

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

#50

Post by bawolff »

nine_k wrote: post #40
rawgabbit wrote: post #36

Earlier quoted context omitted.

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 h…

Bitcoin: Am I joke to you?

Everyone: yes.

Post reply on HN