How to do distributed locking (2016)
martin.kleppmann.com
How to do distributed locking (2016)
1–10 of 99 posts
Re: How to do distributed locking (2016)
#2Many 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’t an alignment of incentives that fixes this problem. Ie the payment structures for executives and engineers aren’t aligned with the best outcome for customers and shareholders.
Re: How to do distributed locking (2016)
#3Many 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’…
I think there's a bit of an alignment of incentives: the edge cases are tricky enough that your programmers probably need to handle a lot of support tickets, which isn't good for anyone.
But I don't see anyway to convince yesterday's managers to give us time to build it right.
Re: How to do distributed locking (2016)
#4This 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 hash of all the data in the store, though that's probably not practical.) The logic becomes:
(1) client retrieves the current version token from storage, along with any data it may want to modify. There's no external lock, though the storage needs to retrieve the data and version token atomically, ensuring the token is specifically for the version of the data retrieved.
(2) client sends the version token back along with any changes.
(3) Storage accepts the changes if the current token matches the one passed with the changes and creates a new version token (atomically, but still no external locks).
Now, you can introduce locks for other reasons (hopefully goods ones... they seem to be misused a lot). Just pointing out they are/should be independent of storage integrity in a distributed system.
(I don't even like the term lock, because they are temporary/unguaranteed. Lease or reservation might be a term that better conveys the meaning.)
Re: How to do distributed locking (2016)
#5Many 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’…
The path to fixing this requires first measuring and monitoring it, then establishing service level objectives that represent customer experience. Product and engineering teams have to agree on them. If the SLOs become violated, focus shifts towards system stability.
Getting everyone onboard is hard and that is why good leadership is needed. When customers start to churn because bugs pop up and new features are slow or non existent, then the case is very easy to make quality part of the process. Mature leaders get ahead of that as early as possible.
Re: How to do distributed locking (2016)
#6Many 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’…
The path to fixing this requires first measuring and monitoring it, then establishing service level objectives that represent customer experience. Product and engineering teams have to agree on them. If the SLOs become violated, focus shifts towards system stability. Getting everyone onboard is hard and that is why good leadership is needed. When customers start to churn because bugs pop up and new features are slow…
Good leadership is spot on! Agreed. The cynic part of me sees incentives that discourage mature leadership styles.
Leaders tend to be impatient and think of this quarter’s OKRs as opposed to the business’ long term financial health. In other word the leaders of leaders use standard MBA prescribed incentive structures.
Re: How to do distributed locking (2016)
#7I 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, 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)
#8This 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 neglects the first reason listed in the article for why you would use a lock.
> Efficiency: Taking a lock saves you from unnecessarily doing the same work twice (e.g. some expensive computation). If the lock fails and two nodes end up doing the same piece of work, the result is a minor increase in cost (you end up paying 5 cents more to AWS than you otherwise would have) or a minor inconvenience (e.g. a user ends up getting the same email notification twice).
I think multiple nodes doing the same work is actually much worse than what’s listed, as it would inhibit you from having any kind of scalable distributed processing.
Re: How to do distributed locking (2016)
#9This 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.
Re: How to do distributed locking (2016)
#10This 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 neglects the first reason listed in the article for why you would use a lock. > Efficiency: Taking a lock saves you from unnecessarily doing the same work twice (e.g. some expensive computation). If the lock fails and two nodes end up doing the same piece of work, the result is a minor increase in cost (you end up paying 5 cents more to AWS than you otherwise would have) or a minor inconvenience (e.g. a user end…
As mentioned in the article, a non-100%-correct lock can be used for efficiency purposes. So basically use an imperfect locking mechanism for efficiency and a reliable one for correctness.