How to do distributed locking

Thanks to Martin for analyzing Redlock, I looked forward to an analysis. I don't agree with the two main arguments of the analysis. TLDR: I think the unique random token of Redlock is enough for Check & Set when the lock holder work materializes into a database write (also note that it requires a linearizable database, to check token_A_ID > token_B_ID in the Martin proposed solution), and I think the system model is very real world (AFAIK the algorithm is not dependent on bounded network delays, I think there is an issue in the analysis, details in my blog post so other people can evaluate), and that the fact different processes can count relative time, without any absolute clock, with a bound error (like, 10%) is absolutely credible. However, I'm analyzing the analysis in depth right now and writing a blog post with the details to be posted tomorrow. Also note that usually when you need a distributed lock, it's because you have no sane way to handle race conditions, otherwise you can do with some weaker and/or optimistic locking form to start with.

It&#x27;s a long read, but the gist of this article is &quot;use the right tool for the job&quot;. Redis is really good for some things, but in its current implementation, distributed locking is not one of them.<p>Along with the author of this blog post, I would recommend the usage of Zookeeper if you have a need for obtaining a lock in a distributed environment. You can read an analysis of how Zookeeper performs under a (intentionally) partitioned network here:<p><a href="https:&#x2F;&#x2F;aphyr.com&#x2F;posts&#x2F;291-jepsen-zookeeper" rel="nofollow">https:&#x2F;&#x2F;aphyr.com&#x2F;posts&#x2F;291-jepsen-zookeeper</a>

If you want to have a truly parallel system, you cannot share resources between processes. If you need a lock, then that implies sharing of resources... Which implies limited scalability according to Amdahl&#x27;s law.<p>To achieve unlimited scalability, you need to make sure that no single data store is shared between all processes and that the amount of interprocess communication (on a per-process basis) doesn&#x27;t increase as you add more processes.<p>The more sharing you have, the less you can scale your system.

&quot;If you still don’t believe me about process pauses, then consider instead that the file-writing request may get delayed in the network before reaching the storage service. Packet networks such as Ethernet and IP may delay packets arbitrarily, and they do [7]: in a famous incident at GitHub, packets were delayed in the network for approximately 90 seconds [8]. This means that an application process may send a write request, and it may reach the storage server a minute later when the lease has already expired.&quot;<p>This statement confused me. It seems to say that the packets were delayed in the network for 90 seconds before being delivered. From reading the original sources it actually sounds like packets were discarded by the switches, so the original requests discarded, and the nodes were partitioned for 90 seconds. When the partition was removed both nodes thought they were the leader and simultaneously requested the other to shutdown. Can anyone confirm? Keeping packets delayed in a network for 90 seconds would seem quite difficult (though not impossible assuming certain bugs).<p>Edit: On re-reading I think this is just talking about the network stack in general - not the network. A temporary partition may delay delivery of your request until max TCP retries is exceeded on your host, if its recovered before then your request may arrive later than you intended.

Why not just use the database to handle the &quot;locking&quot; for you? For example, to ensure that an email with ID=123 gets sent only once, just check if &quot;email 123 sent&quot; is in the database, otherwise commit it to the database, wait for the transaction to be committed, and send the email.<p>Edit: Why is this downvoted? It is a serious question.

&quot;When used as a failure detector, timeouts are just a guess that something is wrong. (If they could, distributed algorithms would do without clocks entirely, but then consensus becomes impossible [10].&quot;<p>Having just re-read Lynch&#x27;s paper, can you explain what you mean here? I didn&#x27;t see anything explicitly relying on time. It could be there is some implicit usage I didnt see. Additionally, the paper&#x27;s impossibility result is about &quot;perfectly correct consensus&quot; which applies with and without clocks and then has a positive result for &quot;partially correct consensus&quot; (i.e. not deciding a value is a correct result). Im not sure which you mean when you say &quot;consensus becomes impossible&quot; as it is either already impossible (the perfectly correct protocol) with one faulty process or (to my understanding) not dependent on time (the partially correct protocol).<p>p.s. great article!

For those interested in distributed locking with Redis and C#, check out this blog post we did which also links to a github project. We use this very heavily. Hope it helps someone.<p><a href="http:&#x2F;&#x2F;stackify.com&#x2F;distributed-method-mutexing&#x2F;" rel="nofollow">http:&#x2F;&#x2F;stackify.com&#x2F;distributed-method-mutexing&#x2F;</a>

&gt; In a reasonably well-behaved datacenter environment, the timing assumptions will be satisfied most of the time – this is known as a partially synchronous system [12]. But is that good enough?<p>Please consider this answer [0] (which I personally understood as - YES, real systems are always partial sync): &quot;Asynchronous systems have no fixed upper bounds. In practice, systems tend to exhibit partial synchrony, which is described as one of two models by Dwork and Lynch in Consensus in the Presence of Partial Synchrony. [1]&quot;<p>[0] <a href="http:&#x2F;&#x2F;bravenewgeek.com&#x2F;category&#x2F;distributed-systems-2&#x2F;" rel="nofollow">http:&#x2F;&#x2F;bravenewgeek.com&#x2F;category&#x2F;distributed-systems-2&#x2F;</a><p>[1] <a href="http:&#x2F;&#x2F;groups.csail.mit.edu&#x2F;tds&#x2F;papers&#x2F;Lynch&#x2F;jacm88.pdf" rel="nofollow">http:&#x2F;&#x2F;groups.csail.mit.edu&#x2F;tds&#x2F;papers&#x2F;Lynch&#x2F;jacm88.pdf</a>

Interesting document a colleague of mine wrote: <a href="https:&#x2F;&#x2F;specs.openstack.org&#x2F;openstack&#x2F;openstack-specs&#x2F;specs&#x2F;chronicles-of-a-dlm.html" rel="nofollow">https:&#x2F;&#x2F;specs.openstack.org&#x2F;openstack&#x2F;openstack-specs&#x2F;specs&#x2F;...</a>

Not directly related, but in a sublink within that piece I found an interesting read about 2 phase commits in Postgres.<p><a href="https:&#x2F;&#x2F;aphyr.com&#x2F;posts&#x2F;282-call-me-maybe-postgres" rel="nofollow">https:&#x2F;&#x2F;aphyr.com&#x2F;posts&#x2F;282-call-me-maybe-postgres</a>

Interesting stuff. In all my distributed systems work so far, I&#x27;ve assumed that a distributed lock is a thing to avoid. I really should take another look at them, just as a tool to have at my disposal.

Why would you ever want to do distributed locking when you can do MVCC via eg vector clocks, possibly with cryptographic signatures?<p>If you want to acquire some shared resource, then elect an owner for that resource.

Instead of the fencing token, could the scenario in the blog post be prevented using a good hashing function?<p>When you perform a write, instead of the token, send a hash of the object previously read. The storage can then compare this against a hash of the resource&#x27;s current state. If it doesn&#x27;t match the lock expired and the write is not accepted.<p>This would reduce the state to keep track off to the resources themselves.

Has anyone used both Zookeeper and etcd in production for management of distributed state?<p>Generally when I think of this problem I reach for etcd, not Zookeeper first, in the hopes of it being lighter (with a relatively vague definition of &quot;light&quot;), and easier to use.

&gt; If they could, distributed algorithms would do without clocks entirely, but then consensus becomes impossible<p>Consensus can be achieved without clocks using blockchains: Instead of timelocking the resource, client can broadcast his altered version after making changes to the network. The next client than then start working on top of this changed resource, but since multiple versions might be floating around (due to timing issues in the first place) the longest tree wins. So if a client submits work done on a shorter tree then it is rejected by the network.<p>This has other issues like it takes longer time &amp; reorganization risks but it does away with clocks altogether by providing a different method of timestamping.<p>This is similar to proof-of-work timestamp server that bitcoin uses but we can do away with proof-of-work because the resource and membership in the network is centralised.