How to do distributed locking (2016)

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

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.

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

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.

Sure, that's why I said you might introduce "locks" (reservations is a much better term) for other reasons.

Efficiency is one, as you say.

The other main one that comes to mind is to implement other "business rules" (hate that term, but that's what people use), like for a online shopping app, the stock to fulfill an order might be reserved for a time when the user starts the checkout process.

> and a reliable one for correctness

To be clear, my point is don't use distributed locking for correctness. There are much better options.

Now, the atomicity I mention implies some kind of internal synchronization mechanism for multiple requests, which could be based on locks, but those would be real, non-distributed ones.

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. Meanwhile process 2 commits to node 2 with token "abc". Node 2 accepts the change because it has not received the message from node 1 and your system is now in an inconsistent state.

Note that this cannot happen in a scenario where we have monotonically increasing fencing tokens because that requirement forces the nodes to agree on a total order of operations before they can supply the fencing token.

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 example is when nodes use an ID they were assigned beforehand as part of the token generation, guaranteeing that the leasing tokens they mint will not conflict with other nodes' as long as node IDs are not reused.

You’re describing compare and swap which is a good solution. You’re pushing complexity down to the database, and remember this is distributed locking. When you have a single database it’s simple until the database crashes leaving you in state of not knowing which of your CAS writes took effect. In major systems that demand high availability and multi datacenter backups this becomings pretty complicated with scenarios that break this as well around node failure. Usually some form of paxos transaction log is used. Never assume there is an easy solution in distributed systems… it just always sucks

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

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

> This overcomplicates things...

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

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.

I normally see it as a version column in a database where it being with the data makes it non-distributed.

I'm not even sure how it could be used for exclusive update to a resource elsewhere--all clients will think they 'have' the lock and change the resource, then find out they didn't when they update the lock. Or if they bump the lock first, another client could immediately 'have' the lock too.

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

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

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.

Got it, thank you for clarifying this.

`--force-unsafe`

That would be the saner name, yes.