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

21–30 of 99 posts

Re: How to do distributed locking (2016)

#21

Post by jmull »

bootsmann wrote: post #14
jmull wrote: post #4

This overcomplicates things... * If you have something like what the article calls a fencing token, you don't need any locks. * The token doesn't need to be monotonically increasing, just a passive unique value that both the client and storage have. Let's call it a version token. It could be monotonically increasing, but a generated UUID, which is typically easier, would work too. (Technically, it could even be a has…

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…

"node1", "node2", and "storage" are three separate things in the distributed environment. Only storage accepts changes, and it's what verifies the incoming token matches the current token.

So node2 doesn't get to accept changes. It can only send changes to storage, which may or may not be accepted by it.

Re: How to do distributed locking (2016)

#22

Post by eru »

jmull wrote: post #4

This overcomplicates things... * If you have something like what the article calls a fencing token, you don't need any locks. * The token doesn't need to be monotonically increasing, just a passive unique value that both the client and storage have. Let's call it a version token. It could be monotonically increasing, but a generated UUID, which is typically easier, would work too. (Technically, it could even be a has…

Git push's `--force-with-lease` option does essentially this.

(Honestly, they should rename `--force-with-lease` to just `--force`, and rename the old `--force` behaviour to `--force-with-extreme-prejudice` or something like that. Basically make the new behaviour the default `--force` behaviour.)

Re: How to do distributed locking (2016)

#23

Post by zeroxfe »

jmull wrote: post #4

This overcomplicates things... * If you have something like what the article calls a fencing token, you don't need any locks. * The token doesn't need to be monotonically increasing, just a passive unique value that both the client and storage have. Let's call it a version token. It could be monotonically increasing, but a generated UUID, which is typically easier, would work too. (Technically, it could even be a has…

> This overcomplicates things...

You're misinterpreting the problem described, and proposing a solution for a different problem.

Re: How to do distributed locking (2016)

#24

Post by antirez »

computerfan494 wrote: post #15
antirez wrote: post #7

I suggest reading the comment I left back then in this blog post comments section, and the reply I wrote in my blog. Btw, things to note in random order: 1. Check my comment under this blog post. The author had missed a fundamental point in how the algorithm works. Then he based the refusal of the algorithm on the remaining weaker points. 2. It is not true that you can't wait an approximately correct amount of time,…

To be honest I've long been puzzled by your response blog post. Maybe the following question can help achieve common ground: Would you use RedLock in a situation where the timeout is fairly short (1-2 seconds maybe), the work done usually takes ~90% of that timeout, and the work you do while holding a RedLock lock MUST NOT be done concurrently with another lock holder? I think the correct answer here is always "No" b…

The timeout must be much larger than the time required to do the work. The point is that distributed locks without a release mechanism are in practical terms very problematic.

Btw, things to note in random order:

1. Check my comment under this blog post. The author had missed a fundamental point in how the algorithm works. Then he based the refusal of the algorithm on the remaining weaker points.

2. It is not true that you can't wait an approximately correct amount of time, with modern computers an APIs. GC pauses are bound and monotonic clocks work. These are acceptable assumptions.

3. To critique the auto release mechanism in-se, because you don't want to expose yourself to the fact that there is a potential race, is one thing. To critique the algorithm in front of its goals and its system model is another thing.

4. Over the years Redlock was used in a huge amount of use cases with success, because if you pick a timeout which is much larger than: A) the time to complete the task. B) the random pauses you can have in normal operating systems. Race conditions are very hard to trigger, and the other failures in the article were, AFAIK, never been observed. Of course if you have a super small timeout to auto release the lock, and the task may easily take this amount of time, you just committed a deisgn error, but that's not about Redlock.

Re: How to do distributed locking (2016)

#25

Post by eknkc »

I tend to use postgresql for distributed locking. As in, even if the job is not db related, I start a transaction and obtain an advisory lock which stays locked until the transaction is released. Either by the app itself or due to a crash or something.

Felt pretty safe about it so far but I just realised I never check if the db connection is still ok. If this is a db related job and I need to touch the db, fine. Some query will fail on the connection and my job will fail anyway. Otherwise I might have already lost the lock and not aware of it.

Without fencing tokens, atomic ops and such, I guess one needs a two stage commit on everything for absolute correctness?

Re: How to do distributed locking (2016)

#26

Post by noprocrasted »

galeaspablo wrote: post #2

Many engineers don’t truly care about the correctness issue, until it’s too late. Similar to security. Or they care but don’t bother checking whether what they’re doing is correct. For example, in my field, where microservices/actors/processes pass messages between each other over a network, I dare say >95% of implementations I see have edge cases where messages might be lost or processed out of order. But there isn’…

> there isn’t an alignment of incentives that fixes this problem

"Microservices" itself is often a symptom of this problem.

Everyone and their dog wants to introduce a network boundary in between function calls for no good reason just so they can subsequently have endless busywork writing HTTP (or gRPC if you're lucky) servers, clients & JSON (de?)serializers for said function calls and try to reimplement things like distributed transactions across said network boundary and dealing with the inevitable "spooky action at a distance" that this will yield.

Re: How to do distributed locking (2016)

#27

Post by jroseattle »

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 request if one is available, assign some metadata from the request to the allocated ticket, and remove it from consideration for future client requests.

We had failed campaigns in the past (over-allocation, under-allocation, duplicate allocation, etc.) so our concern was accuracy. Clients would connect and request a ticket; we wanted to exclusively distribute only the set of tickets available from the pool. If the number of client requests exceeded the number of tickets, the system should protect for that.

We tried Redis, including the naive implementation of getting the lock, checking the lock, doing our thing, releasing the lock. It was ok, but administrative overhead was a lot for us at the time. I'm glad we didn't go that route, though.

We ultimately settled on...Postgres. Our "distributed lock" was just a composite UPDATE statement using some Postgres-specific features. We effectively turned requests into a SET operation, where the database would return either a record that indicated the request was successful, or something that indicated it failed. ACID transactions for the win!

With accuracy solved, we next looked at scale/performance. We didn't need to support millions of requests/sec, but we did have some spikiness thresholds. We were able to optimize read/write db instances within our cluster, and strategically load larger/higher-demand campaigns to allocated systems. We continued to improve on optimization over two years, but not once did we ever have a campaign with ticket distribution failures.

Note: I am not an expert of any kind in distributed-lock technology. I'm just someone who did their homework, focused on the problem to be solved, and found a solution after trying a few things.

Re: How to do distributed locking (2016)

#28

Post by computerfan494 »

antirez wrote: post #24
computerfan494 wrote: post #15

Earlier quoted context omitted.

To be honest I've long been puzzled by your response blog post. Maybe the following question can help achieve common ground: Would you use RedLock in a situation where the timeout is fairly short (1-2 seconds maybe), the work done usually takes ~90% of that timeout, and the work you do while holding a RedLock lock MUST NOT be done concurrently with another lock holder? I think the correct answer here is always "No" b…

The timeout must be much larger than the time required to do the work. The point is that distributed locks without a release mechanism are in practical terms very problematic. Btw, things to note in random order: 1. Check my comment under this blog post. The author had missed a fundamental point in how the algorithm works. Then he based the refusal of the algorithm on the remaining weaker points. 2. It is not true th…

Locking without a timeout is indeed in the majority of use-cases a non-starter, we are agreed there.

The critical point that users must understand is that it is impossible to guarantee that the RedLock client never holds its lease longer than the timeout. Compounding this problem is that the longer you make your timeout to minimize the likelihood of this from accidentally happening, the less responsive your system becomes during genuine client misbehaviour.

Re: How to do distributed locking (2016)

#29

Post by noprocrasted »

secondcoming wrote: post #16
galeaspablo wrote: post #2

Many engineers don’t truly care about the correctness issue, until it’s too late. Similar to security. Or they care but don’t bother checking whether what they’re doing is correct. For example, in my field, where microservices/actors/processes pass messages between each other over a network, I dare say >95% of implementations I see have edge cases where messages might be lost or processed out of order. But there isn’…

> 95% of implementations I see have edge cases where messages might be lost or processed out of order. Eek. This sort of thing can end up with innocent people in jail, or dead. [0] https://en.wikipedia.org/wiki/British_Post_Office_scandal

The problem (or the solution, depending on which side you're on) is that innocent people are in jail or dead. The people that knowingly allowed this to happen are still free and wealthy.

So I'm not particularly sure this is a good example - if anything, it sets the opposite incentives, that even jailing people or driving them to suicide won't actually have any consequences for you.

Re: How to do distributed locking (2016)

#30

Post by jameshart »

karmakaze wrote: post #9
jmull wrote: post #4

This overcomplicates things... * If you have something like what the article calls a fencing token, you don't need any locks. * The token doesn't need to be monotonically increasing, just a passive unique value that both the client and storage have. Let's call it a version token. It could be monotonically increasing, but a generated UUID, which is typically easier, would work too. (Technically, it could even be a has…

This is known as 'optimistic locking'. But I wouldn't call it a distributed locking mechanism.

Optimistic locks are absolutely a distributed locking mechanism, in that they are for coordinating activity among distributed nodes - but they do require the storage node to have strong guarantees about serialization and atomicity of writes. That means it isn’t a distributed storage solution, but it is something you can build over the top of a distributed storage solution that has strong read after write guarantees.
Post reply on HN