How to do distributed locking (2016)

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.

This is the best way, and actually the only sensible way to approach the problem. I first read about it here https://code.flickr.net/2010/02/08/ticket-servers-distribute...

You are right that anything that needs up to 50000 atomic, short-lived transactions per second can just use Postgres.

Your UPDATE transaction lasts just a few microseconds, so you can just centralise the problem and that's good because it's simpler, faster and safer.

But this is not a _distributed_ problem, as the article explains:

> remember that a lock in a distributed system is not like a mutex in a multi-threaded application. It’s a more complicated beast, due to the problem that different nodes and the network can all fail independently in various ways

You need distributed locking if the transactions can take seconds or hours, and the machines involved can fail while they hold the lock.

> only sensible way

That's a bit strong. Like most of engineering, it depends. Postgres is a good solution if you only have maybe 100k QPS, the locks are logically (if not necessarily fully physically) partially independent, and they aren't held for long. Break any of those constraints, or add anything weird (inefficient postgres clients, high DB load, ...), and you start having to explore either removing those seeming constraints or using other solutions.

Ok fair; I'm not really talking about postgres (the link i shared uses mysql). I'm saying that creating a ticket server that just issues and persists unique tokens, is a way to provide coordination between loosely coupled applications.

I think this illustrates something important, which is that: You don't need locking. You need <some high-level business constraint that might or might not require some form of locking>.

In your case, the constraint is "don't sell more than N tickets". For most realistic traffic volumes for that kind of problem, you can solve it with traditional rdbms transactional behavior and let it manage whatever locking it uses internally.

I wish developers were a lot slower to reach for "I'll build distributed locks". There's almost always a better answer, but it's specific to each application.

Yeah that's cookies. They are great.

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

Classic tech interview question

I guess this is embarassingly parralelizable in that you can shard by concert to different instances. Might even be a job for that newfangled cloudflare sqlite thing.

Interesting. We went through a similar process and ended up with Yugabyte to deal with the locks (cluster).

It’s based on Postgres but performance was not good enough.

We’re now moving to RDMA.

Heh, in my local developer community I have a bit of a reputation for being “the guy” to talk to about distributed systems. I’d done a bunch of work in the early days of the horizontal-scaling movement (vs just buying bigger servers) and did an M.Sc focused on distributed systems performance.

Whenever anyone would come and ask for help with a planned distributed system the first question I would always ask is: does this system actually need to be distributed?! In my 15 years of consulting I think the answer was only actually “yes” 2 or 3 times. Much more often than was helping them solve the performance problems in their single server system; without doing that they would usually just have ended up with a slow complex distributed system.

Edit: lol this paper was not popular in the Distributed Systems Group at my school: https://www.usenix.org/system/files/conference/hotos15/hotos...

“You can have a second computer once you’ve shown you know how to use the first one.”

You could just have multiple clients attempt to update a row that defines the lock. Postgres transactions have no limit and will unwind on client failure. Since connections are persistent, there’s no need to play a game to determine the state of a client.

Your scenario still uses a centralised single postgres server. Failure of that server takes down the whole locking functionality. That's not what people usually mean by "distributed".

"the machines involved can fail" must also include the postgres machines.

To get that, you need to coordinate multiple postgres servers, e.g. using ... distributed locking. Postgres does not provide that out of the box -- neither multi-master setups, nor master-standby synchronous replication with automatic failover. Wrapper software that provides that, such as Stolon and Patroni, use distributed KV stores / lock managers such as etcd and Consul to provide it.

I wanted to post the same paper. With Adrian Colyer’s explanations: https://blog.acolyer.org/2015/06/05/scalability-but-at-what-...

> up to 50000 atomic, short-lived transactions per second

50000?

> You need distributed locking if the transactions can take seconds or hours, and the machines involved can fail while they hold the lock. From my experience, locks are needed to ensure synchronized access to resources. Distributed locks are a form of that isolation being held across computing processes, as opposed to the mutex example provided.

And while our implementation definitively did not use a distributed lock, we could still see those machines fail.

I fail to understand why a distributed lock is needed for anything due to it's duration.

This is exactly how we arrived at our solution. We needed to satisfy the constraint; locking was one means of addressing the constraint.

Maybe we were lucky in our implementation, but a key factor for our decision was understanding how to manage the systems in our environment. We would have skilled up with Redis, but we felt our Postgres solution would be a good first step. We just haven't had a need to go to a second step yet.

Mostly guessing but -> duration is usually inversely correlated with throughput.

If you require high throughput and have a high duration then partitioning/distribution are the normal solution.