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

How to do distributed locking (2016)

martin.kleppmann.com

Post reply on HN
Print view View original

51–60 of 99 posts

Re: How to do distributed locking (2016)

#51

Post by bootsmann »

computerfan494 wrote: post #19
bootsmann wrote: post #14

Earlier quoted context omitted.

Won't this lead to inconsistent states if you don't do monotonically increasing tokens? I.e. your storage system has two nodes and there are two read-modify-write processes running. Process 1 acquires the first token "abc" and process two also acquires the token "abc". Now process 1 commits, the token is changed to "cde" and the change streamed to node 2. Due to network delay, the change to node 2 is delayed. Meanwhi…

In the above description of optimistic locking, it is assumed that it is impossible to issue the same token to multiple clients. Nodes can agree that a given token has also never been issued before just like a monotonically increasing value. The nice property about non-monitonically-increasing tokens is that nodes may generate them without coordinating if you can make other assumptions about that system. A good examp…

I have a hard time wrapping my head around what you are proposing here. Say client A requests data, they get the token a-abc. Then client B requests data, they get the token b-cde. Client A commits their write, does the storage reject it because they already issued another token (the one from client B) or does it accept it?

Re: How to do distributed locking (2016)

#52

Post by computerfan494 »

bootsmann wrote: post #51
computerfan494 wrote: post #19

Earlier quoted context omitted.

In the above description of optimistic locking, it is assumed that it is impossible to issue the same token to multiple clients. Nodes can agree that a given token has also never been issued before just like a monotonically increasing value. The nice property about non-monitonically-increasing tokens is that nodes may generate them without coordinating if you can make other assumptions about that system. A good examp…

I have a hard time wrapping my head around what you are proposing here. Say client A requests data, they get the token a-abc. Then client B requests data, they get the token b-cde. Client A commits their write, does the storage reject it because they already issued another token (the one from client B) or does it accept it?

My understanding of what the OP was discussing is an optimistic locking system where the nodes only accept commits if the last issued token matches the token included in the commit. While agreeing on the last token requested requires coordination, unlike monotonically increasing tokens you could have well-behaved clients generate token content themselves without coordination. That may or may not be useful as a property.

Re: How to do distributed locking (2016)

#53

Post by etcd »

jroseattle wrote: post #27

We reviewed Redis back in 2018 as a potential solution for our use case. In the end, we opted for a less sexy solution (not Redis) that never failed us, no joke. Our use case: handing out a ticket (something with an identifier) from a finite set of tickets from a campaign. It's something akin to Ticketmaster allocating seats in a venue for a concert. Our operation was as you might expect: provide a ticket to a reques…

I guess this is embarassingly parralelizable in that you can shard by concert to different instances. Might even be a job for that newfangled cloudflare sqlite thing.

Re: How to do distributed locking (2016)

#54

Post by dataflow »

> The lock has a timeout (i.e. it is a lease), which is always a good idea (otherwise a crashed client could end up holding a lock forever and never releasing it). However, if the GC pause lasts longer than the lease expiry period, and the client doesn’t realise that it has expired, it may go ahead and make some unsafe change.

Hold on, this sounds absurd to me:

First, if your client crashes, then you don't need a timed lease on the lock to detect this in the first place. The lock would get released by the OS or supervisor, whether there are any timeouts or not. If both of those crash too, then the connection would eventually break, and the network system should then detect that (via network resets or timeouts, lack of heartbeats, etc.) and then invalidate all your connections before releasing any locks.

Second, if the problem becomes that your client is buggy and thus holds the lock too long without crashing, then shouldn't some kind of supervisor detect that and then kill the client (e.g., by the OS terminating the process) before releasing the lock for everybody else?

Third, if you are going to have locks with timeouts to deal with corner cases you can't handle like the above, shouldn't they notify the actual program somehow (e.g., by throwing an exception, raising a signal, terminating it, etc.) instead of letting it happily continue execution? And shouldn't those cases wait for some kind of verification that the program was notified before releasing the lock?

The whole notion that timeouts should somehow permit the program execution to continue ordinary control flow sounds like the root cause of the problem, and nobody is even batting an eye at it? Is there an obvious reason why this makes sense? I feel I must be missing something here... what am I missing?

Re: How to do distributed locking (2016)

#55

Post by OnlyMortal »

jroseattle wrote: post #27

We reviewed Redis back in 2018 as a potential solution for our use case. In the end, we opted for a less sexy solution (not Redis) that never failed us, no joke. Our use case: handing out a ticket (something with an identifier) from a finite set of tickets from a campaign. It's something akin to Ticketmaster allocating seats in a venue for a concert. Our operation was as you might expect: provide a ticket to a reques…

Interesting. We went through a similar process and ended up with Yugabyte to deal with the locks (cluster).

It’s based on Postgres but performance was not good enough.

We’re now moving to RDMA.

Re: How to do distributed locking (2016)

#56

Post by neonbrain »

dataflow wrote: post #54

> The lock has a timeout (i.e. it is a lease), which is always a good idea (otherwise a crashed client could end up holding a lock forever and never releasing it). However, if the GC pause lasts longer than the lease expiry period, and the client doesn’t realise that it has expired, it may go ahead and make some unsafe change. Hold on, this sounds absurd to me: First, if your client crashes , then you don't need a ti…

The assumption that your server will always receive RST or FIN from your client is incorrect. There are some cases when these packets are being dropped, and your server will stay with an open connection while the client on the remote machine is already dead. P.S. BTW, it's not me who downvoted you

Re: How to do distributed locking (2016)

#57

Post by winwang »

dataflow wrote: post #54

> The lock has a timeout (i.e. it is a lease), which is always a good idea (otherwise a crashed client could end up holding a lock forever and never releasing it). However, if the GC pause lasts longer than the lease expiry period, and the client doesn’t realise that it has expired, it may go ahead and make some unsafe change. Hold on, this sounds absurd to me: First, if your client crashes , then you don't need a ti…

This isn't a mutex, but the distributed equivalent of one. The storage service is the one who invalidates the lock on their side. The client won't detect its own issues without additional guarantees not given (supposedly) by Redlock.

Re: How to do distributed locking (2016)

#58

Post by neonbrain »

winwang wrote: post #57
dataflow wrote: post #54

> The lock has a timeout (i.e. it is a lease), which is always a good idea (otherwise a crashed client could end up holding a lock forever and never releasing it). However, if the GC pause lasts longer than the lease expiry period, and the client doesn’t realise that it has expired, it may go ahead and make some unsafe change. Hold on, this sounds absurd to me: First, if your client crashes , then you don't need a ti…

This isn't a mutex, but the distributed equivalent of one. The storage service is the one who invalidates the lock on their side. The client won't detect its own issues without additional guarantees not given (supposedly) by Redlock.

My understanding is that the dataflow user was talking about a notification which the server is supposed to receive from the OS in the case of a broken client connection. This notification is usually received, but cannot be guaranteed in a distributed environment.

Re: How to do distributed locking (2016)

#59

Post by dataflow »

neonbrain wrote: post #56
dataflow wrote: post #54

> The lock has a timeout (i.e. it is a lease), which is always a good idea (otherwise a crashed client could end up holding a lock forever and never releasing it). However, if the GC pause lasts longer than the lease expiry period, and the client doesn’t realise that it has expired, it may go ahead and make some unsafe change. Hold on, this sounds absurd to me: First, if your client crashes , then you don't need a ti…

The assumption that your server will always receive RST or FIN from your client is incorrect. There are some cases when these packets are being dropped, and your server will stay with an open connection while the client on the remote machine is already dead. P.S. BTW, it's not me who downvoted you

I made no such assumption this will always happen though? That's why the comment was so much longer than just "isn't TCP RST enough?"... I listed a ton of ways to deal with this that didn't involve letting the program continue happily on its path.
Post reply on HN