A check-and-set version of MULTI/EXEC
Salvatore Sanfilippo
yesterday I proposed a CAS-ing (check and set) MULTI/EXEC version that
can be used as a base to implement atomic commands without requiring
scripting.
Today I evolved the idea into a much more cleaner API and behavior. I
want to present the new idea in a clear form in this post.
The addition of two commands is needed: CAS and UNCAS. Let's start with CAS.
CAS key1 key2 key3
MULTI
... some command ...
EXEC
Basically in the above example EXEC will succeed only if key1, key2,
key3 were not modified after CAS was called against this keys.
So for instance, how to implement INCR on top of this?
CAS key
GET key => 10
10+1 = 11
MULTI
SET key 11
EXEC
If when EXEC is called, key was not modified, then EXEC can be
executed and will set the new (incremented) value.
Otherwise if some other client modified the value of "key" in the
meanwhile, EXEC will return "-ERR CAS check failed on EXEC".
This is a form of optimistic locking like memcached CAS, but much more
powerful as it allows to execute groups of commands, does not require
additional fields in the Redis object, works with our complex data
types, and so forth.
UNCAS is needed as I may want to optimistically lock a key, if what we
read inside is not what we expected we may want to abort the operation
at all, UNCASsing it.
As you can see, CAS is a "state" in the connection. It's like if I
tell Redis "start watching this keys, and in the next call of EXEC
performed against this connection, abort the EXEC at all if at least
one of this keys changed".
This can solve all the atomicity issues where scripting could be
required, but with a much simpler semantics.
There is also to think at this from the point of view of clustering.
I wanted to formalize this idea a bit and post it into the group in
order to have a reference in the future about this possibility.
As usually feedbacks will be very welcomed.
Cheers,
Salvatore
--
Salvatore 'antirez' Sanfilippo
http://invece.org
"Once you have something that grows faster than education grows,
you’re always going to get a pop culture.", Alan Kay
Sergey Shepelev
State idea is great, but i think CAS is not a best name because it
doesn't set anything.
How about WATCH? SUPERVISE? BEHOLD?
BEGIN? START STATE?
GUARD? PROTECT? KEEP?
> Cheers,
> Salvatore
>
> --
> Salvatore 'antirez' Sanfilippo
> http://invece.org
>
> "Once you have something that grows faster than education grows,
> you’re always going to get a pop culture.", Alan Kay
>
> --
> 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.
>
>
Salvatore Sanfilippo
> State idea is great, but i think CAS is not a best name because it
> doesn't set anything.
> How about WATCH? SUPERVISE? BEHOLD?
> BEGIN? START STATE?
> GUARD? PROTECT? KEEP?
Indeed, CAS is not a good name, but I think your "PROTECT" is pretty cool.
Demis Bellot
GET key => 10
10+1 = 11
MULTI
SET key 11
EXEC
Salvatore Sanfilippo
> Hey Salvatore,
> This is exactly the kind of thing I'm looking for to enrich Redis's atomic
> transaction support, allowing a richer set of constructs.
> I think we need a little more info about the behaviour:
> It looks as though CAS/PROTECT is tied to future MULTI/EXEC operation?
Exactly. Only the next multi/exec operation on *that* connection is effected.
> If I understand It correctly, it looks a little unbalanced though as EXEC
> seems to mean 'EXEC and UNCAS'?
Yes actually EXEC has the effect of UNPROECT-ing everything is
currently PROTECTed.
> I know it's an extra operation but what are your thoughts on being explicit
> - so the scope becomes clearer i.e.
> CAS key
> GET key => 10
> 10+1 = 11
> MULTI
> SET key 11
> EXEC
> UNCAS
On top of my head I can't find any scenario where it is desirable to
not UNCAS everything on EXEC implicitly...
> Is it based on the 'value' or the last time it was changed? e.g. what if
> another operation in mid-transaction changes the value back to 10? so the
EXEC will fail anyway even if the original value is restored.
> value is the same but it has still been changed by someone else.
> In this case what would the behaviour be if the key was a LIST/SET/HASH?
> Would the check be based if the list remains exactly the same or that if any
> write operation on the LIST/SET/HASH was performed? I guess the latter would
> be the easiest to implement.
Indeed, as in practical terms it's mostly the same, I think the right
semantic is to abort the EXEC in any kind of write operation against
the key, without any kind of difference about types and so forth. This
of course also includes DELete operations, EXPIREs sets, and so forth.
Matt Todd
API would look like in a library like redis-rb.
redis.multi(:protect => ['key1', 'key2', 'key3']) do
v = redis.get 'key1'
redis.set 'key2', v + 1
redis.incr 'key3'
end
Possibly? Does that seem semantically aligned with what we're doing?
Matt
> --
> 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.
>
>
--
Matt Todd
Highgroove Studios
www.highgroove.com
cell: 404-314-2612
blog: maraby.org
Scout - Web Monitoring and Reporting Software
www.scoutapp.com
Vinuth Madinur
Mike Shaver
> Should the operations be restricted only to the keys protected?
No, I think explicitly not. For example, I may want to incr a
statistics key only if my transaction succeeds, but I don't care what
its specific values are.
(I don't really like the name PROTECT, since I don't think the
semantics are that it prevents racing updates, but rather than it
fails/retries if such an update happened. So to me it's more like a
DEPEND.)
Mike
Sergey Shepelev
I like DEPEND.
> Mike
Vinuth Madinur
On Wed, Apr 7, 2010 at 1:43 PM, Vinuth Madinur <vinuth....@gmail.com> wrote:No, I think explicitly not. For example, I may want to incr a
> Should the operations be restricted only to the keys protected?
statistics key only if my transaction succeeds, but I don't care what
its specific values are.
Mike Shaver
> The EXEC command's result could tell whether the transaction succeeded or
> not?
True, though I think that it's cleaner to keep it all in one spot --
too many times I've had my stats get wonky because I changed how I
computed the ID of something I was modifying, but didn't change the
code that logged updates by ID to match.
Mike
amix
distributed lock built on top of memcached:
http://amix.dk/blog/post/19386
Maybe instead of calling it CAS/UNCAS you could call it LOCK/UNLOCK.
Regards,
amix
> Salvatore 'antirez' Sanfilippohttp://invece.org
Mason Jones
appropriate -- it's more like WATCH, where it will simply fail/abort
if the keys have been affected. It doesn't prevent the keys from
changing, so it's really not a lock.
PROTECT isn't bad, but it's also not quite right. Tricky.
Of the suggestions so far, I guess I like the look of WATCH or DEPEND.
Konstantin Merenkov
I don't know whether it's good, though.
(want to say that I don't like DEPEND).
--
Best Regards,
Konstantin Merenkov
Ezra Zygmuntowicz
Can you remind me and the group about why things must return queued inside of the multiple/exec block? Is it to avoid network hops during the atomic multiple/exec block?
Thanks
Ezra
Sent from my iPad
Marcus
not.
Would you consider a STOREIN command for the atomic operations that
could be benefited by something simple like that?
Salvatore Sanfilippo
> This is really very interesting... trying to think through what the
> API would look like in a library like redis-rb.
>
> redis.multi(:protect => ['key1', 'key2', 'key3']) do
> v = redis.get 'key1'
> redis.set 'key2', v + 1
> redis.incr 'key3'
> end
>
> Possibly? Does that seem semantically aligned with what we're doing?
Yes this sounds like a good API to me, perfectly mappable to
MULTI/EXEC/PROTECT (or whatever it will be called)
Salvatore Sanfilippo
> Is there really no way to allow the use of return values inside of a multiple/exec block? If we could use return values inside of our multiple/exec the need for scripting would be basically nil. Combined with this PROTECT mechanism would allow us to build almost any true atomic command without scripting.
Hello Ezra,
basically with the PROTECT stuff there is no longer *need* to get
return values from MULTI/EXEC, as you can read the value before, since
it's protected and the transaction will abort if it changed in some
way.
The reason why inside MULTI/EXEC commands return QUEUED is because
they are not called at all, but just put into a queue for later
execution when EXEC is called, this is the only (simple) way to
implement isolation / atomicity.
So now with PROTECT (or any other name we'll use at the end, maybe
WATCH) this will look like this, in the general schema:
WATCH vars you want to read
GET vars...
LRANGE vars ...
in general, read operations are here, and are against the same vars
that we WATCH usually
MULTI
write operations go here... in order to update the final state of the dataset
EXEC => will fail if our WATCHed stuff changed
So with this general schema it is possible to implement any kind of primitive.
I could like to show a few more examples, is there some user in the
list with an example of an atomic operation he *really* needs so that
I can provide an example of implementation with MULTI/EXEC/PROTECT?
Andy McCurdy
I could like to show a few more examples, is there some user in thelist with an example of an atomic operation he *really* needs so that
I can provide an example of implementation with MULTI/EXEC/PROTECT?
Salvatore Sanfilippo
> The one several people wanted at the SF Redis meetup was atomic ZPOP/ZREVPOP
> where you pop and return the item with the lowest or highest score on a
> ZSET.
Indeed! Great idea:
Function ZPOP(myzset)
BEGIN
PROTECT myzset
val = ZRANGE myzset 0 0
MULTI
ZREM myzset $val
EXEC
END
If EXEC fails (as another client popped an element in the meantime),
just reiterate.
It's worth to note that if there are a lot of clients ZPOPping
aggressively from the *same* list, there are good chances that from
time to time the PROTECT thing fails. LOCK/UNLOCK would be able to
deliver better performances in this scenario, as clients performing
the operation while the value is "busy" will be queued.
This is a problem in general with Check And Set: if many clients are
CASsing against the same value, once the probability of collisions
become high, the performance starts to drop.
Demis Bellot
--
Salvatore Sanfilippo
> Hey if this feature is going to force having a timestamp against every key
> then I vote for being able to get KEYS * in last modified order, or KEYS *
> modified after the provided timestamp.
> This will allow background tasks to maintain a Search Index of data held in
> Redis more easily.
> Thoughts?
What's nice about MULTI/EXEC/PROTECT is that it does not require *any*
additional space or field in the keyspace.
When a client does a PROTECT it's just registered in a key->client
hash table until there is the EXEC. In this window of time, if a
change happens in the key, a function is called that checks all the
clients waiting for changes in that key, and a simple flag in the
client structure is set.
So this feature is trivial to code and with zero memory overhead. Two
good points.
What I don't like is the behavior with many concurrent clients trying
to protect the same key. Lots of failing EXECs...
Cheers,
Salvatore
Sergey Shepelev
> On Thu, Apr 8, 2010 at 12:25 AM, Demis Bellot <demis....@gmail.com> wrote:
>> Hey if this feature is going to force having a timestamp against every key
>> then I vote for being able to get KEYS * in last modified order, or KEYS *
>> modified after the provided timestamp.
>> This will allow background tasks to maintain a Search Index of data held in
>> Redis more easily.
>> Thoughts?
>
> What's nice about MULTI/EXEC/PROTECT is that it does not require *any*
> additional space or field in the keyspace.
> When a client does a PROTECT it's just registered in a key->client
> hash table until there is the EXEC. In this window of time, if a
> change happens in the key, a function is called that checks all the
> clients waiting for changes in that key, and a simple flag in the
> client structure is set.
>
> So this feature is trivial to code and with zero memory overhead. Two
> good points.
>
> What I don't like is the behavior with many concurrent clients trying
> to protect the same key. Lots of failing EXECs...
http://en.wikipedia.org/wiki/Thundering_herd_problem
Seems unevitable by design of CAS-like operations.
There could be more intelligent approach taken in Haskell software
transactional memory implementation: a retry function, which repeats
transaction again, if someone modified data in the meantime.
But i can't imagine a use case where repeat could serve a useful role
without server-side scripting.