Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to do distributed locking

martin.kleppmann.com

Post reply on HN
Print view View original

21–30 of 73 posts

Re: How to do distributed locking

#21

Post by dvirsky »

teraflop wrote: post #20
dvirsky wrote: post #16

Earlier quoted context omitted.

The author dedicates a good chunk of code to describing a potential problem that might happen in long GC pauses or similar situations. That problem is not unique to redis. Is there any way to avoid it in ZK?

Yep, and the author even (briefly) describes it. But you can't do it without moving some of the logic into the storage service, to check fencing tokens. Zookeeper exposes various kinds of IDs that can be used to do fencing; apparently (I haven't read the details) Redlock doesn't. Interestingly, even though HBase uses Zookeeper for coordination, it does not use it for fencing. Instead, fencing is handled by atomic "lo…

The solution of fencing tokens on the storage layer that's proposed there, just pushes the problem one layer down - you'll still need the storage layer to be consistent for this to work. Also it means it should be aware of those semantics, which complicates thigns. Redlock has non incremental tokens, so I guess it can be used as well. Read @antirez's reply above.

Re: How to do distributed locking

#22

Post by teraflop »

bkeroack wrote: post #12
hardwaresofton wrote: post #10

Has anyone used both Zookeeper and etcd in production for management of distributed state? 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 "light"), and easier to use.

etcd would be a fine choice, but Consul provides a lock feature[1] out of the box. 1. https://www.consul.io/docs/guides/leader-election.html

As the article explains at length, using Zookeeper or etcd as a "locking service" in this way is not safe, even if the service is perfect and failure-free. There is a fundamental race condition between finding out that you've obtained a lock, and doing some other operation that assumes mutual exclusion.

Re: How to do distributed locking

#23

Post by ploxiln »

antirez wrote: post #15

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…

The quality of your C code running on a single node is by all accounts really good. But you sometimes speak about distributed systems in a way that is not correct to people who have really spent a lot of time making these things work at scale.

I've done distributed systems, and in fact I usually don't implement systems that are 100% correct under maximally-adverse conditions, for performance and convenience reasons. But it's important to know and acknowledge where and how the system is less than 100% bullet-proof, so that you can understand and recover from failures. When you have 1000 servers, some virtual in the cloud, some in a colocation facility, and maybe 10 or 20 subtle variants in hardware, you will get failures that should not happen but they do. For example, I've had an AWS host where the system time jumped backwards and forwards by 5 minutes every 30 seconds. And I've seen a tcp load-balancer appliance managed by a colo facility do amazingly wrong things.

The point is, you need to understand where the consistency scheme in a distributed system is "fudged", "mostly reliable", "as long as conditions aren't insane", and where they are really guaranteed (which is almost nowhere). Then you can appropriately arrange for "virtually impossible" errors/failures to be detected and contained. This ad-hoc logic you bring to the problem of distributed systems doesn't really help.

Not to "dogpile", but elucidate for others who may not know some of the history here: https://aphyr.com/posts/287-asynchronous-replication-with-fa... and the also interesting reply: http://antirez.com/news/56

Re: How to do distributed locking

#24

Post by u320 »

antirez wrote: post #15

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…

> I think the unique random token of Redlock is enough for Check & Set when the lock holder work materializes into a database write

But that's optimistic concurrency control! In that case the locking service is a pure optimization and doesn't affect correctness. So why use this complex multi-node locking thing then, instead of a single redis node?

Re: How to do distributed locking

#25

Post by mring33621 »

tyre wrote: post #19
praneshp wrote: post #7

Interesting document a colleague of mine wrote: https://specs.openstack.org/openstack/openstack-specs/specs/...

Off-topic but that URL is remarkably repetitive. Is that some kind of SEO play?

Yo, Dawg, I heard you like some openstack in your openstack...

Re: How to do distributed locking

#26

Post by praneshp »

tyre wrote: post #19
praneshp wrote: post #7

Interesting document a colleague of mine wrote: https://specs.openstack.org/openstack/openstack-specs/specs/...

Off-topic but that URL is remarkably repetitive. Is that some kind of SEO play?

No, its an effect of autobuilding from a git repo, I think.

The specs are submitted for review at https://github.com/openstack/openstack-specs

Re: How to do distributed locking

#27

Post by takeda »

bkeroack wrote: post #12
hardwaresofton wrote: post #10

Has anyone used both Zookeeper and etcd in production for management of distributed state? 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 "light"), and easier to use.

etcd would be a fine choice, but Consul provides a lock feature[1] out of the box. 1. https://www.consul.io/docs/guides/leader-election.html

Doesn't it have the same issue that redis does?

Re: How to do distributed locking

#28

Post by sdab »

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

Having just re-read Lynch's paper, can you explain what you mean here? I didn't see anything explicitly relying on time. It could be there is some implicit usage I didnt see. Additionally, the paper's impossibility result is about "perfectly correct consensus" which applies with and without clocks and then has a positive result for "partially correct consensus" (i.e. not deciding a value is a correct result). Im not sure which you mean when you say "consensus becomes impossible" 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.s. great article!

Re: How to do distributed locking

#29

Post by robinhouston »

sdab wrote: post #28

"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]." Having just re-read Lynch's paper, can you explain what you mean here? I didn't see anything explicitly relying on time. It could be there is some implicit usage I didnt see. Additionally, the paper's impossibility re…

I'm having trouble relating this comment to the referenced paper [1], which seems to be explicit that its impossiblity result does not apply when synchronised clocks are available.

For example, on page 375: “Crucial to our proof is that processing is completely asynchronous; that is, we make no assumptions about the relative speeds of processes or about the delay time in delivering a message. We also assume that processes do not have access to synchronized clocks, so algorithms based on time-outs, for example, cannot be used.”

1. http://www.cs.princeton.edu/courses/archive/fall07/cos518/pa...

Re: How to do distributed locking

#30

Post by sdab »

robinhouston wrote: post #29
sdab wrote: post #28

"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]." Having just re-read Lynch's paper, can you explain what you mean here? I didn't see anything explicitly relying on time. It could be there is some implicit usage I didnt see. Additionally, the paper's impossibility re…

I'm having trouble relating this comment to the referenced paper [1], which seems to be explicit that its impossiblity result does not apply when synchronised clocks are available. For example, on page 375: “Crucial to our proof is that processing is completely asynchronous; that is, we make no assumptions about the relative speeds of processes or about the delay time in delivering a message. We also assume that proc…

You mean the OP's comment or mine? I agree with you if you mean the OP's comment. Though your quote refers to synchronized clocks. I dont think OP is referring to synchronized clocks, though your point that Lynch et al does not rely on timeouts is what Im getting at.
Post reply on HN