compare-exchange
Marc Gravell
Regards,
Marc Gravell
Josiah Carlson
> SETNX has a specific scenario raised - of locking and deadlock avoidance
> (http://redis.io/commands/setnx); however, even in the final sample given
> there are a few issues - for example, C4 and C5 could end up artificially
> extending the locked time even though they are *failing* to acquire the lock
> (which could perhaps lead to both thinking the lock is active elsewhere,
> delaying lock acquisition), and relies on accurate clocks between clients.
Your description of the problems with the SETNX lock description are
correct. I've got an article on locking in Redis that I've been
meaning to publish, which points out many of the problems with the
different locks built for Redis. Case in point: I've not found a
single lock implementation for Redis available online that isn't
broken in one way or another.
As of right now, the features are sufficient to build a lock, but to
do it correctly is difficult.
> I wonder, though, if there isn't a much easier solution here;
>
> Two random ramblings are discussed below - just snowballing, but I'm
> wondering if they could be helpful here:
>
> --------------------------------------
>
> Random thought 1: conditional getset
>
> The current GETSET is comparable to an interlocked-exchange; the values are
> swapped atomically, with the new value being stored and the old value being
> returned.
>
> However, in locking another common operation is the interlocked conditional
> (compare) exchange, where-by a comparand and a new value are supplied, and
> the exchange only happens if the old value matches the comparand.
>
> I wonder whether redis would benefit from this; it fits well with the atomic
> model, and would allow pretty simple lock usage:
>
> - call: setnx <key> <new timestamp>
> - if returns 1, we got the lock; exit
> - call: get <key> and check for expired; if not expired, sleep etc and redo
> from start (as per existing SETNX notes)
> - (so here we believe the lock has expired due to a crashed client)
> - call: getsetc <key> <new timestamp> <the expired timestamp> --------
> EMPH: THIS COMMAND DOES NOT EXIST
> - if we get back 1, the value hadn't changed - it was still expired so we
> won the lock; hoorah!
> - if we got back 0, the value had already changed to a new timestamp -
> someone else won; redo from start
This would solve the problem with locks, and perhaps a couple others
related problems related to race conditions on data.
> ---------------------------------------
>
> Random thought 2: using volatility
>
> I looked at options involving volatility; but there's a problem: if you
> don't run in a transaction, you are liable to race conditions, and it all
> goes crazy. Obviously we can't do a GET inside a MULTI (to check the value),
> since it will be deferred until the EXEC. It is *tempting* (but wrong) to do
> a:
That's what WATCH is for. You WATCH a key, get information about it,
decide what you want to do, then set up a MULTI/EXEC that only
completes if the data hasn't changed. At present, if you are not using
scripting, the only technically correct way of implementing a lock
involves the use of WATCH/MULTI/EXEC in at least expiration.
> multi
> setnx <key> <dummy value>
> expire <key> <duration>
> exec
>
> but this is very wrong because the expire happens even if we don't win the
> key, which means you can easily stop the key ever expiring if you query
> within the timeout. A simple workaround would be a setnx that accepted
> expiry as part of the atomic operation "if the key doesn't exist, create it
> with expiry; if it exists, leave it alone and do not change the expiry"
>
> setnxex <key> <dummy value> <timeout> -------- EMPH: THIS COMMAND DOES
> NOT EXIST
>
> and... that's actually all of it; if it returns 1, we won the key (job
> done); if it returns 0, you need to wait
That would be sufficient to have simple and correct locks in Redis.
> ---------------------------------------
>
> Random thought 3: using lua
>
> it looks like this is something where we could do the "call setnx, checking
> whether it returned 1; if it returned 1 call expire" at the server,
> essentially writing "setnxex" as a lua script
There is potential for this to fail if the data was swapped to disk,
the command was delayed by the OS, and Redis checked for timeout and
killed the command mid-process. There are a lot of problems that are
brought up here where I would generally agree "this is complicated to
explain, would be annoying to implement... they should just use
scripting". But for operations that are fundamental (and I believe
locking is fundamental), having commands to do them easily and
correctly makes sense.
> ------------------------------------
>
> I *suspect* the likely suggestion here is "use lua", but both the options
> mentioned above feel like core string methods that could be useful to a lot
> of callers, rather than being implemented lots of times as lua (and the
> necessity, then, of either sending the script lots of times, or using
> evalsha and handling the script-missing case).
>
>
> Anyway - I've rambled. Just some ideas thrown out there. To do with as you
> please, or to say "dude, you're missing <really obvious and simpler fix>".
> The main thing I'm trying to avoid is accidentally extending the lock
> lifetime when FAILING to obtain the lock.
You are right, locks in Redis are a PITA. I would vote for adding an
optional expiration time to SETNX. It implements locking with timeouts
sufficiently and minimally, and requires relatively minor changes to
client libraries.
Regards,
- Josiah
Marc Gravell
Interesting.
Marc
> --
> You received this message because you are subscribed to the Google Groups "Redis DB" group.
> To post to this group, send email to redi...@googlegroups.com.
> To unsubscribe from this group, send email to redis-db+u...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/redis-db?hl=en.
>
Marc Gravell
Marc
On 5 Jan 2012, at 18:05, Josiah Carlson <josiah....@gmail.com> wrote:
Salvatore Sanfilippo
> Yes, a WATCH, GET (pre-check here), MULTI, GETSET, EXEC (check success) should spoof a conditional exchange, but... Unnecessarily painful (ESP when multiplexed)
>
> Marc
Marc, Josiah, very interesting discussion.
Please can you explain what would be the formal behavior of the lock you need?
I'm not sure about what multiplexing means in this context.
I think we should start defining the kind of lock we want, like: with
timeout, released when the client disconnects, with or without an
explicit queue to acquire it, with support for write/read locks so
that multiple reads are allowed, and so forth.
If this is useful I think we should go forward and implement a new
command that impleemnts a good distributed lock with Redis.
Cheers,
Salvatore
--
Salvatore 'antirez' Sanfilippo
open source developer - VMware
http://invece.org
"We are what we repeatedly do. Excellence, therefore, is not an act,
but a habit." -- Aristotele
Josiah Carlson
> On Thu, Jan 5, 2012 at 7:38 PM, Marc Gravell <marc.g...@gmail.com> wrote:
>> Yes, a WATCH, GET (pre-check here), MULTI, GETSET, EXEC (check success) should spoof a conditional exchange, but... Unnecessarily painful (ESP when multiplexed)
>>
>> Marc
>
> Marc, Josiah, very interesting discussion.
>
> Please can you explain what would be the formal behavior of the lock you need?
> I'm not sure about what multiplexing means in this context.
>
> I think we should start defining the kind of lock we want, like: with
> timeout, released when the client disconnects, with or without an
> explicit queue to acquire it, with support for write/read locks so
> that multiple reads are allowed, and so forth.
>
> If this is useful I think we should go forward and implement a new
> command that impleemnts a good distributed lock with Redis.
I'm of the opinion that "simpler is better", and that one should go
for the simplest solution that solves the vast majority of the
problems.
There are 3 major classes of locks (as I see it):
1. basic lock, no timeout
2. lock with timeout
3. lock with timeout and a queue for first-come, first-served
Using SETNX bare gets you #1, and addresses maybe 10-15% of lock usage
in the real world (people want timeouts). Giving SETNX an optional
timeout gets you #2, and addresses probably 85-90% of lock usage.
Adding a queue, a special command, and the release of the lock on
disconnect may get you another 5% of potential users, with an overall
reduction in latency, but I think that there is a better solution in
the general case if this kind of functionality is desired. But, if you
release a lock when a client is disconnected, it's probably going to
cause problems*.
Having used locks, looked at lock implementations, implemented a few
different kinds of locks, and having written about locks, my
suggestion:
1. Add an optional timeout to SETNX. It addresses 85-90% of the
standard use-cases for getting and setting a lock with a timeout
atomically.
2. To deal with releasing a lock, add DELC <key> <oldvalue>; if the
<oldvalue> matches the value at the key, delete the key, otherwise
leave it alone (if the key is already deleted, return a different
response).
With those two commands, it is trivial to acquire the lock with a
timeout, and release the lock when you are done.
What about the "fair" queue, reducing round-trips, etc.? This gets
more complicated, but I believe a more generic solution is preferable
to a lock-specific solution...
There have been many requests for the ability to "subscribe" to events
against given keys. Things like "tell me when key X expires" or "tell
me when key Y has changed". Maybe it's time to seriously consider it?
For example, let's imagine that you could subscribe to one of 3
different events on keys, causing a command to be executed. Something
like:
KEYSUB lock:access-token DELETE RPUSH queue:access-token *
Where you would be subscribing to DELETE (and EXPIRE) on the
'lock:access-token' key, causing the key to be pushed to the
queue:access-token list. To implement a "fair" queue with locking, you
would perform...
def acquire()
locked = 0
while not locked:
token = generate_unique_token()
locked = conn.setnx('lock:access-token', token, timeout)
if not locked:
conn.keysub('lock:access-token', 'DELETE', 'RPUSH queue:access-token *')
conn.blpop('queue:access-token', 1)
return token
def release(token):
conn.delc('lock:access-token', token)
If you could do this, then fair locking is solved** (you have to bail
out on the blocking pop because of the race condition between the
setnx and the keysub call).
Semantically (for locks):
1. You can subscribe to ADD, UPDATE, and DELETE on keys (mirroring DB
triggers for insert/update/delete).
2. Once a KEYSUB has been executed, it is discarded.
3. Discard duplicate KEYSUB calls (same key, same condition, same
exact command).
Open question:
If there is a KEYSUB, should there be a way of creating a permanent KEYSUB?
Regards,
- Josiah
* In the case of network instability, if the lock is released on
disconnect, the client with the lock will reconnect, will expect to
have the lock, but won't. Also, in some cases with pooled connections,
a connection won't necessarily be used for a single set of operations
(especially in the case where the lock is meant to synchronize access
to some remote resource; we used locks to ensure that only one of our
task workers was hitting Twitter's Streaming API at a time).
** If you don't care about fair locking, and just want to get a lock
or retry, the acquire call with the updated setnx looks like:
def acquire()
locked = 0
while not locked:
token = generate_unique_token()
locked = conn.setnx('lock:access-token', token, timeout)
if not locked:
time.sleep(.001)
return token
Marc Gravell
In many ways volatile keys are pretty ideal for a lock with eventual timeout (allowing centralised time), and it would probably be possible to do via:
watch <key>
exists <key>
(check result; if 1 sleep and redo from start)
multi
setex <key> <timeout> <dummy value>
exec
(check for success)
Which would probably work equally (and will probably be my stopgap, assuming it works). The difficulty with this (and the meaning of multiplexing here) is that on a busy web site, to minimise resources we interleave commands from unrelated requests on the same connection (in most cases that don't involve a transaction, this is very effective as all the commands are unrelated). However, the moment I add a watch/multi/exec I need to stop interleaving until complete.
My point, though, was that an operation like "setnx with expiry if successful" seems like a handy primitive, so I was just throwing it out there. It would certainly seem to solve robust locking at a stroke, at least for the non-queued case. The conditional getset also seems useful, but leaves a lot more remaining to do robust locking. Of course, if the *only* case it really solves is locking, it might not be so ideal, and maybe an actual locking command is nice; tbh, I hadn't even thought of going so far as adding an entire construct - I was just using existing string methods.
The idea of queued locking (similar to the blocking pops) isn't one I had considered. I don't have specific requirements for such, and if I was working with current tech I'd be half tempted to use a pub/sub channel to advertise the lock being released (to interrupt sleep for retry)... But I'm just making stuff up now.
Josiah mentioned robust release of the lock; I'm not sure that is necessary, because one key scenario where you have a problem is if a client with the lock takes too long and the lock is stolen. In that case, all bets are already off, as there's **already** a good chance you're incorrectly running two things in parallel. However, your mention of a theoretical lock that lasts no longer than the connection is intriguing. Still not perfect, but in the bastard-scenarios where it breaks there's enough chaos on the network that it is hard to see alternatives.
I worry about over complicating things, though. My original thought was just to do something simple and pragmatic that solves a tricky case with the minimum of fuss and bugs :p
(ends random thoughts, part the second)
Marc
ivan babrou
Josiah Carlson
> We have a RedisLock class written in php for locks with setnx, getset, and
> salt in the key value. I may post algorithm later if anyone interested.
> There is still collision 1/10000000 (salt) and it depends on system time
> accuracy, but you may improve it if you like.
Ivan,
If you want to post your lock, please do so. If you aren't using WATCH
in at least the lock release process, I suspect that there are other
issues that you don't know about with your lock.
More to the point, I got an okay to post this excerpt from the book
I'm writing, which discusses locking in Redis as is currently
available. http://dr-josiah.blogspot.com/2012/01/creating-lock-with-redis.html
Regards,
- Josiah