4 ms·

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 li

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

antirez 11y ago
> 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.
- querulous 11y ago
  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-40ceac109dbb#.j9ekopmcm 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

antirez 11y ago

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

querulous 11y ago
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-40ceac109dbb#.j9ekopmcm 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