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

41–50 of 99 posts

Re: How to do distributed locking (2016)

#41

Post by nasretdinov »

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…

So basically your answer (and the correct answer most of the time) was that you don't really need distributed locks even if you think you do :)

Re: How to do distributed locking (2016)

#42

Post by zeroxfe »

jameshart wrote: post #30
karmakaze wrote: post #9

Earlier quoted context omitted.

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.

This is unconventional use of the term "distributed locking". This alternative just punts the hard part of locking to the storage system.

Re: How to do distributed locking (2016)

#43

Post by antirez »

computerfan494 wrote: post #28
antirez wrote: post #24

Earlier quoted context omitted.

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

In most real world scenarios, the tradeoffs are a bit softer than what people in the formal world dictates (and doing so they forced certain systems to become suboptimal for everything but during failures, kicking them out of business...). Few examples:

1. E-commerce system where there are a limited amount of items of the same kind, you don't want to oversell.

2. Hotel booking system where we don't want to reserve the same dates/rooms multiple times.

3. Online medical appointments system.

In all those systems, to re-open the item/date/... after some time it's ok, even after one day. And if the lock hold time is not too big, but a very strict compromise (it's also a reasonable choice in the spectrum), and it could happen that during edge case failures three items are sold and there are two, orders can be cancelled.

So yes, there is a tension between timeout, race condition, recovery time, but in many systems using something like RedLock the development and end-user experience can be both improved with a high rate of success, and the random unhappy event can be handled. Now the algorithm is very old, still used by many implementations, and as we are talking problems are solved in a straightforward way with very good performances. Of course, the developers of the solution should be aware that there are tradeoffs between certain values: but when are distributed systems easy?

P.S. why 10 years of strong usage count, in the face of a blog post telling that you can't trust a system like that? Because even if DS issues emerge randomly and sporadically, in the long run systems that create real-world issues, if they reach mass usage, are known. A big enough user base is a continuous integration test big enough to detect when a solution has real world serious issues. So of course RedLock users picking short timeouts with tasks that take a very hard to predict amount of time, will indeed incur into knonw issues. But the other systemic failure modes described in the blog post are never mentioned by users AFAIK.

Re: How to do distributed locking (2016)

#46

Post by cosmicradiance »

anonzzzies wrote: post #45

I am updating my low level and algo knowledge; what are good books about this (I have the one written by the author). I am looking to build something for fun, but everything is either a toy or very complicated.

System Design Interview I and II - Alex Xu. Take one of the topics and do it practically.

Re: How to do distributed locking (2016)

#47

Post by apwell23 »

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…

Classic tech interview question

Re: How to do distributed locking (2016)

#48

Post by bootsmann »

jmull wrote: post #21
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…

"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.

If the storage is a singular entity then this is not a distributed systems problem at all, no?

Re: How to do distributed locking (2016)

#49

Post by computerfan494 »

antirez wrote: post #43
computerfan494 wrote: post #28

Earlier quoted context omitted.

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

In most real world scenarios, the tradeoffs are a bit softer than what people in the formal world dictates (and doing so they forced certain systems to become suboptimal for everything but during failures, kicking them out of business...). Few examples: 1. E-commerce system where there are a limited amount of items of the same kind, you don't want to oversell. 2. Hotel booking system where we don't want to reserve th…

I feel like you're dancing around admitting the core issue that Martin points out - RedLock is not suitable for systems where correctness is paramount. It can get close, but it is not robust in all cases.

If you want to say "RedLock is correct a very high percentage of the time when lease timeouts are tuned for the workload", I would agree with you actually. I even possibly agree with the statements "most systems can tolerate unlikely correctness failures due to RedLock lease violations. Manual intervention is fine in those cases. RedLock may allow fast iteration times and is worth this cost". I just think it's important to be crystal clear on the guarantees RedLock provides.

I first read Martin's blog post and your response years ago when I worked at a company that was using RedLock despite it not being an appropriate tool. We had an outage caused by overlapping leases because the original implementor of the system didn't understand what Martin has pointed out from the RedLock documentation alone.

I've been a happy Redis user and fan of your work outside of this poor experience with RedLock, by the way. I greatly appreciate the hard work that has gone into making it a fantastic database.

Re: How to do distributed locking (2016)

#50

Post by sethammons »

noprocrasted wrote: post #26
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…

I've worked with microservices at scale and it was fantastic. We couldn't break backwards compatibility with our API without a lot of coordination. Outside of that, you could deploy as frequently as needed and other services could update as needed to make use of new features.

The monoliths I have worked in, very contrastingly, have had issues coordinating changes within the codebases, code crosses boundaries it should not and datastores get shared and coupled to (what should be) different domains leading to slow, inefficient code and ossified options for product changes.

Post reply on HN