Hacker News Reader

From Martin post: "However, the storage server remembers that it has already processed a write with a higher token number (34), and so it rejects the request with token 33."

This is not eventual consistency, this is refusing any new write with ID < past_ID, which requires linearizability.

Second, about eventual consistency, the Token ID even when increasing may not be casually related with the work performed while the lock is hold. if you need just a random order when there are concurrent accesses, you can lexically order the random token IDs, for what is worth.

Compare & Swap: could you argument that? If you want to avoid races in a read-modify-write scenario, you can set the token, do your work, and only write if the token is still the same, so that if your write succeed is because the state of the shared resource is still the same to when you started operating on it.

you don't need a token service if you are going to set the token on the locked resource, perform work and then unset the token. your lock is completely superfluous in that scenario

That's my point in the blog post I wrote. Please read it, I would love your feedback. Or better, you could do even with a best-effort lock, given that race conditions from time to time are harmless.

  2. If your data store can always accept the write only if 
  your token is greater than all the past tokens, than it’s a 
  linearizable store. If you have a linearizable store, you 
  can just generate an incremental ID for each Redlock 
  acquired, so this would make Redlock equivalent to 
  another distributed lock system that provides an 
  incremental token ID with every new lock. However in the 
  next point I’ll show how this is not needed.

you confuse which system is the linearizable one in this point. your storage system is just a dumb storage system that simply returns the object version with the highest clock. what makes it linearizable to an outside observer is that the system generating the lock ids is itself linearizable. if every insert is accompanied by an authentic lock id the system is linearizable. if you generate this lock id via the storage system itself then the storage system must also be linearizable

  3. However “2” is not a sensible choice anyway: most of the times the 
  result of working to a shared resource is not writing to a linearizable 
  store, so what to do? Each Redlock is associated with a large random 
  token (which is generated in a way that collisions can be ignored. The 
  Redlock specification assumes textually “20 bytes from /dev/urandom”). 
  What do you do with a unique token? For example you can implement Check 
  and Set. When starting to work with a shared resource, we set its state 
  to “`<token>`”, then we operate the read-modify-write only if the token 
  is still the same when we write.

would you say this sequence of events is correct:

* process A acquires lock

* process B acquires a lock on the same resource after a time out and sets it's lock id on the resource

* process A sets it's lock id on the resource

* process A writes a new version of the resource

* process B attempts and fails to write a new version of the resource

if it's not correct, would you say redlock prevents it? how?

now consider what happens if the resource is only one of a group of resources that need to be transactionally updated

the bottom line is that distributed transactional locking requires linearization and redlock is plainly not linearizable. please reconsider it's continued development and steer users towards something safer like zookeeper

> your storage system is just a dumb storage system that simply returns the object version with the highest clock. what makes it linearizable to an outside observer is that the system generating the lock ids is itself linearizable.

I don't think you understand Martin motivations. He says that the system has to reject the write with a lower ID, in order to protect from concurrent accesses, and to do so in a way that the client attempting a stale write is notified.

If you mount an eventually consistent system returning the object with higher version, there is nothing of linearizable about it. If the shared resource is a list of names, one client will try to add "Hellen" with version 8, one will try to add "Josh" with version 9. Only one name will end in the list in your schema, and the client adding "Josh" will not even know that the write failed.

So the goal is, when race conditions happen, to avoid them in some way. While I believe that when you use a distributed lock the problem is very often that you don't have other controls over the shared resource, if you really need to do that, a random token is equivalent: using CAS you can reject one of the writes if two clients are writing at the same time.

Note also that when it happens that, because of delays, the clients are accessing concurrently, the lock ID has little to do with the order in which the operations were indented to happen. Back to "add name to a list" problem:

T0: Client A receives new name to add from web.

T0: Client B is idle

T1: Client A is experiencing pauses.

T1: Client B receives new name to add from web.

T2: Client A is experiencing pauses.

T2: Client B receives a lock with ID 1

T3: Client A receives a lock with ID 2

...

So the client that received the name before, can do the operation after, or you can have delays in any other part of the system.

i disagree that i don't understand martin kleppmann's method and also that his method is 'eventually consistent'.

using a random token is not equivalent to using a linearizable lock, see: https://medium.com/@talentdeficit/redlock-unsafe-at-any-time...

i am not sure what your point about delays and concurrent clients is, of course a system can't infer order from events that happen outside of it's visibility. the lock system can only provide synchronization at the point the lock is acquired

Martin made no mention of strong vs. eventual consistency.

If you write to a store like cassandra using a monotonic token, the result will converge correctly. If you require to never read "stale" data, you can read / write w/ quorum. There is no linearization in the storage layer in this case.

In this case the lock is not superfluous and you have safety.

Regarding CAS, I said that your argument (in support of redlock) was wrong. I would be happy to respond to a proposed algorithm, but as someone else mentioned, either the storage layer can provide a CAS operation, in which case your lock is not required and the workers read, mutate, CAS, OR if the storage layer has any weaker semantics then it is not possible to ensure safety with a token.

>the storage layer can provide a CAS operation, in which case your lock is not required and the workers read, mutate, CAS

Yeah, so Optimistic Concurrency Control. Possibly a Redlock-like lease scheme could be used to improve performance in the high-contention case.

> Secondly, Antirez's argument that you can use a compare & swap in a transactional storage layer is also wrong. This is not possible to write safely.

Could you elaborate on this? I'm not sure I'm as pessimistic as you on this one point.

In short, either the storage layer provides enough guarantees to ensure safety without redlock OR it is not possible to ensure safety.

I believe that antirez's proposal is the former, but if he has a safe algorithm that does not require a linearizable CAS operation in the storage layer and is safe w/ redlock, I would love to hear it.

I also provided an example of how to use Cassandra which is eventually consistent safely with a locking service that provides monotonic tokens.

Compare and swap has a consensus number of 2. A consensus number is the maximum number of processes for which the object can solve a simple consensus problem. It is impossible to construct a wait-free implementation of an object with consensus number n from an object with a lower consensus number. In other words, test-and-set is weaker than transactions or Paxos for >2 concurrent clients.

http://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf

Wait, compare and swap has a consensus number of infinite (from Herlihy's paper).

Oops, you're right. I was thinking of test-and-set.

> I'm not even going to touch his argument that using system clocks in a distributed locking algorithm is safe...

Please do

I don't need to, Martin did an excellent job touching on this in his original post, including real world references.

Antirez responded to that and disagreed to this point in his new post. What do you make of his response?

Clock drift is a real thing in distributed systems.

If I have a 5 second lock that expires at 12:01:00 and my clock is off by 1 second I could write at 12:01:01 potentially after someone else has a lock, or worse, after someone else has written.

but the expiration time is relative to the redis server's time, and the time measurement on the client side is done relative to the client's time. Other clients don't care about your clock and you don't care about redis' clock AFAIK. From TFM:

> The client computes how much time elapsed in order to acquire the lock, by subtracting from the current time the timestamp obtained in step 1. If and only if the client was able to acquire the lock in the majority of the instances (at least 3), and the total time elapsed to acquire the lock is less than lock validity time, the lock is considered to be acquired.

What is the effect on the client of a VM live migration "pause"?

or daylight savings change?

or ntp updates which change the time?

Since the system clock can change relative to itself at any time, what effect does that have on the algorithm?

I don't disagree, I'm just saying that time drift between nodes is not an issue with this algorithm. Also, using monotonic clock as antirez says he intends to in the post, will take care of most of these scenarios besides VM migration pauses.

Distributed time is tricky, but it depends on what the intended use is. Under normal operation it will only move forward, for example.

> VM live migration "pause"?

System clock will take a larger step than usual. It won't go backwards.

> daylight savings change?

None. System clock is UTC for a reason.

> ntp updates which change the time?

NTP only drifts the clock (under normal operation).

Not that I think it effects your point, but just off the top of my head:

System clock will take a larger step than usual. It won't go backwards.

Assumes that checkpoint and restore to a previous time won't happen.

NTP only drifts the clock (under normal operation).

Unless it's a system like this. Note that this was pulled at about 1pm EST.

  Waiting for clock tick...
  ...got clock tick
  Time read from Hardware Clock: 2016/02/09 22:36:50
  Hw clock time : 2016/02/09 22:36:50 = 1455057410 seconds since 1969
  Tue 09 Feb 2016 02:36:50 PM PST  -1.038948 seconds

Under normal operation it will only move forward

'Under normal operation' is not really a high bar for distributed systems. After all, the network is reliable 'under normal operation' too.

> Assumes that checkpoint and restore to a previous time won't happen.

Or migration to a host whose clock is behind the original host's clock.

Use CLOCK_MONOTONIC. Or you could make your client abort when the clock goes backwards.

If someone forks a VM from a running snapshot, you're screwed whether they mess with the clock or not.

> NTP only drifts the clock (under normal operation).

That shouldn't be an assumption. NTP may jump the clock if the difference is too high, I've had it once that a system was connected to two different NTP servers and they each had a different clock and the system would jump the clock every now and then based on what NTP server it though was more correct.

What about requiring PTP sync or shutting down the node? I have no idea about the practical implications, just something I thought of. You can get a CDMA time server on ebay for a few hundred bucks that support PTP.

Off hand you either need multiple time servers or you might as well have a central lock (since you are bottlenecked in either case) which just punts the issue, now the various time servers need to be in sync or the issue comes up.

Replying here since I can't reply to your deeper comment.

A client can never know with certainty that it has successfully acquired the lock because, for example, the process could freeze between reading the current time from hardware and the steady_time function returning.

You can not rely on time, for safety. Only for advice.

yes, that goes back to the first issue in Martin's article, and he mentioned the tokens thing for this. But time drift between the machines is not an issue, is my point.

> I'm not even going to touch his argument that using system clocks in a distributed locking algorithm is safe...

He's using it relatively, ie. if (stop time - start time <= $got_lock_fast_enough) { continue... } Is this not legit?

In a virtualized environment, system time and wall clock time can vary widely. Imagine a VM that's paused and restored.

I would assume that introducing a VM that has "time-travelled" (especially the restore-from-previous-state case someone mentioned above) into a distributed system would inherently break that distributed system, no matter what it's doing. It's a really crazy thing to do, much crazier than a regular network partition.

Personally, though, I don't see why it's so hard to just say "this distributed lock system requires that soft real-time guarantees can be made of the host platform. If the platform misses the algorithm's scheduling deadline, the system breaks. If the platform has no way of providing for a soft real-time deadline (because e.g. it's running in a VM that can be paused), the software will detect this and fail to start."

Because you don't want the system to break.

But it wouldn't, because the surrounding infrastructure would be guaranteeing that. My point is that distributed systems engineers are assuming too few things about the hardware and OS. A much wider space of distributed algorithms become useful if you have full control over your stack.

Do you think NASA quibbles about how to make a perfect consensus bit-coding algorithm between the fault-tolerant processors of a mars probe? No; they just use hardware+firmware that provides a hard real-time platform, allowing the algorithm itself to be simple.

It doesn't require a VM pause to cause a system freeze, an SMI interrupt can do that as well.

It doesn't take a lot to have backwards time travel, NTP can do that for you as well in some bad configurations.

It's very hard to rely on time in a distributed system. If you want a simple algorithm just don't rely on time at all, use it for logs so a human can correlate things when debugging an issue but don't assume time will flow at the same rate for all systems. Do use a monotonic clock always for internal timers, time does move backwards in systems.

I have seen SMI pauses for almost 5 seconds!

What if the system freezes between reading the current time from the hardware and the stead_time function returning?

In short, you CANNOT rely on time in any way shape or form for safety. You can only use it as advice & to get liveliness.

Martin's point is that Redlock pays the cost of other safe locking algorithms w/o the benefit of safety.

This, usually. It's fair to point out that very specialized clocks, such as Google uses with Spanner, can allow you to achieve some consistency without coordination/locks, but for pretty much anyone else the rule you stated very much applies.

FWIW, I went digging for more recent info about TrueTime and found the following.

http://www.cse.buffalo.edu/~demirbas/publications/augmentedT...

Do you have any references for this?

This discussion is very interesting and I would like to read up a bit more on your argument and why is this so.

I know that distributed systems are hard, but this is a problem that I find interesting to learn more about.

References to what specifically?

Martin provided a number in his original blog post, I also elaborated a bit more on my various points in other comments.

Upon reading a bit more on the subject I realized that I would need a more background before asking for references that will be a very specific in terms of subject depth.

I read a bit on BOOM and it's not a field I'm keeping up with so I figured it would be no point in more references if I didn't understand the more shallower levels of the discussion first.

Sorry about that, I tried to jump a bit too soon, and thanks for answering :)