atomically add user to a clan
Andrés M. Quijano
I'm evaluating redis and considering of using it to replace MySQL in
an web based multiplayer game (similar to Travian)
I'm concerned about atomicity, probably this has came up thousands of
times but I couldn't find anything on the discussion group
For example, one specific scenario is this one:
A clan is a group of users, and a user can be part of one clan (or
none)
That can be designed easily having clan:id:members as a set of user
ids and user:id:clan a string with an id of the clan it belongs t
But how would you add a user to a clan, meaning adding it to the set
of the clan and adding the clan id to the user, atomically, so that no
inconsistencies arise?
Thanks in advance
Andrés
Birukoff
way. Maybe later Salvatore will implement MULTI/EXEC command (that
will accept several commands that will be executed as single operation
after 'EXEC' part); he promised to think about it later. It is not in
todo list yet but I hope it will.
Salvatore Sanfilippo
> But how would you add a user to a clan, meaning adding it to the set
> of the clan and adding the clan id to the user, atomically, so that no
> inconsistencies arise?
Hello Andrés,
I was replying that you can try to design the application so that it's
tolerant about having the user ID in the clan set and not the contrary
(and possibly fix the issue in the fly when the inconsistency is
detected), or that pipelining could solve the problem in most
real-world scenarios, even if it's not a guarantee, but I was not
happy with my reply.
Sometimes to write a reply is the best way to think about the problem,
and simply the MULTI/EXEC solution I and other people proposed in the
bast was the way to go. So after an hour of hacking I'm happy to
announce this is now implemented in Redis :)
This is not a real-world solution since currently there is to consider
the code as an unstable thing, but probably in a few weeks it will be
'beta quality' code, and in a few months will be inside Redis-stable,
so at least there is a trivial upgrade path, starting dealing with the
inconsistency (that in the real world is very unlikely to happen),
maybe adding some application logic to deal with the problem, and
later upgrade to MULTI/EXEC.
It was not trivial to design in order to play well with currently
implemented client libs, but I think that my solution is solid.
This is how it works:
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
MULTI
+OK
SET mykey 4
ciao
+QUEUED
GET mykey
+QUEUED
EXEC
*2
+OK
$4
ciao
Do you like it? Because every queued command will reply with a +QUEUED
status code, guess what? You can already use existing client libs (if
well designed) to work with the new command. Not only, to detect
errors will not require some special path in client libs or in the
Redis code, since this is what happens if you try to queue bad stuff:
MULTI
+OK
PING
+QUEUED
NOT A GOOD COMMAND
-ERR unknown command 'NOT'
PING WRONG NUMBER OF ARGS
-ERR wrong number of arguments for 'ping' command
EXEC
*1
+PONG
Also note how "EXEC" works. It replies with a multi-bulk reply where
every element is the reply of a single command. So the effect is that
EXEC returns an "array" of replies. Again this should work out of the
box with good client libs.
Redis-rb is a good client lib:
>> require 'redis'
=> true
>> r = Redis.new
=> #<Redis:0x100152b78 @port=6379, @thread_safe=nil, @password=nil,
@db=0, @host="127.0.0.1", @logger=nil, @timeout=5>
>> r.multi
=> "OK"
>> r.ping
=> "QUEUED"
>> r.ping
=> "QUEUED"
>> r.exec
=> ["PONG", "PONG"]
Cool if you ask me :)
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
Adam Michaels
Another idea is to add an argument to it which would force a write to
disk immediately on COMMIT. What do you propose would happen if one of
the commands failed? A ROLLBACK or silent fail? There is also some
questions on how this would work with redis-cluster and if the keys
inside the "transaction" are on different servers and if doing two
phase commits is required.
This is a major feature and we should give it some more time to iron
it out. Redis on ACID, never thought the project would be here a year
ago.
On Dec 27, 1:00 pm, Salvatore Sanfilippo <anti...@gmail.com> wrote:
> 2009/12/27 Andrés M. Quijano <tulsi...@gmail.com>:
> Salvatore 'antirez' Sanfilippohttp://invece.org
Birukoff
There is already MSET that could potentially involve keys from several
physical servers, and a number of other commands.
Dan Bravender
I just started following Redis and implementing new features in my
fork at GitHub. Redis is a great project and it's good to see that it
is getting atomicity!
I do see a potential problem with the current implementation:
If you execute INCR or INCRBY inside of a MULTI you don't know what
the value of the key will be until the EXEC is run. This means that if
you want to get a unique user ID and make use of that value you can't.
The same is true for all read and write commands, they all return
'+QUEUED'.
Proposed solution is to have all the commands behave the same inside
and outside of the MULTI by implementing a COW hash (Copy On Write):
- MULTI -> redis creates a new empty transaction COW dictionary
- INCR, INCRBY -> These are already atomic and their side-effects
should go directly into the real dictionary (not the transaction
dictionary) because other transactions need to have the latest values
here (I believe this is how AUTO INCREMENT fields work in transactions
in SQL databases)
- Read command -> Check if the value is in the cache dictionary. If
it is, return the cached transaction value
- Write command
- Updating an existing value (e.g. list, set manipulation, etc.) ->
Copy the value from the real dictionary into the cache dictionary then
perform the update in the cache dictionary
- Setting a new key or clobbering an existing key -> Set it in the
cache dictionary
- EXEC
- Atomic phase - Increment the refcount on all the values in the
cache key store. Update the pointers in the real dictionary so that
the keys point to the objects in the cache dictionary in an atomic
update and return "+OK"
- Free the cache dictionary and decrement the refcount to all the
keys that were overwritten in the real dictionary
- If a timeout or error occurs before EXEC then the cache dictionary
is freed and we get "-ERR Aborted MULTI"
Optional MULTISAFE command idea:
For the certain operations you don't want to perform them if you'd
clobber fresh changes. It might be a lot of overhead (since it
requires adding timestamps to all key modifications), but an even
stronger transaction could be made by checking during the atomic
commit phase that all of the keys affected by the updates have
modification times less than the values that they had when the MULTI
was started.
After the proposed changes, everything looks the same as it used to so
we can receive values from all queries:
MULTI
+OK
DEL useridcounter
:0
INCR useridcounter
:1 # <- We need this to perform the next command... if we get +QUEUED
here we cannot know which userid is next
SET user:1:name 4
Fred
+OK
EXEC
+OK
An implementation of this idea will be facilitated by placing a new
layer for setting and reading keys that checks whether or not the
current connection is in MULTI mode or not and performs the action on
the appropriate dictionary.
Does anyone see any potential problems with this? Please let me know
what you think!
Cheers,
Dan
On Dec 27, 4:00 pm, Salvatore Sanfilippo <anti...@gmail.com> wrote:
> 2009/12/27 Andrés M. Quijano <tulsi...@gmail.com>:
>
> Salvatore 'antirez' Sanfilippohttp://invece.org
Stephen Farrell
On Dec 27, 2009, at 10:53 PM, Dan Bravender <dan.br...@gmail.com>
wrote:
> --
>
> 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
> .
>
>
Adam Michaels
version counter instead of using a timestamp. That could give you
basic optimistic locking of the keys inside the transaction without
the overhead of storing a timestamp on every key. The keys not
involved in transactions would never get a version, saving memory.
Salvatore Sanfilippo
> You could call it BEGIN/COMMIT like they do for SQL transactions.
Hello Adam, yes, I explicitly avoided the name in order to avoid an
implicit claim that this is equivalent to SQL transactions. Still I
think it's pretty fair to call them "Redis transactions" as they are
ACID as far as I can tell, once I add something like "EXEC FSYNC"
(that you also proposed! this will give use the "D" of ACID)
> Another idea is to add an argument to it which would force a write to
> disk immediately on COMMIT. What do you propose would happen if one of
Exactly, yesterday I added an "AOFSYNC" command to force an append
only file sync so that it was possible to do:
MULTI + ... commnads + AOFSYNC + EXEC
So that the transaction is also durable regardless of the AOF fsync
policy specified in the config file.
But then I didn't liked the idea and removed it in order to implement
an optional argument for "EXEC" to perform the fsync. So I can't agree
more about your proposal ;)
> the commands failed? A ROLLBACK or silent fail? There is also some
This is a bit too fare IMHO, at least for now. We'll see in the future btw.
> questions on how this would work with redis-cluster and if the keys
> inside the "transaction" are on different servers and if doing two
> phase commits is required.
Basically redis-cluster will never support everything a single node is
supporting. But on the other hand node-specific features may provide
some per-node feature to allow for a simpler implementation of
redis-cluster and other features.
On the other side I think that most multi-keys commands should work in
redis-cluster if the user explicitly force the keys to hash all the
same, using key-tags. So for instance if partitioning is done per-user
the application can still use Redis transactions or SMOVE, or
SINTERSTORE or other complex operations against user-data.
> This is a major feature and we should give it some more time to iron
> it out. Redis on ACID, never thought the project would be here a year
> ago.
Indeed, AOF opened a whole new level of durability, and transactions
turned out to be trivial to implement. The whole implementation took
an hour. This, blocking LPOP, Hashes and Virtual Memory should really
open Redis to many new applications.
Salvatore Sanfilippo
> MULTI/EXEC doesn't complicate cluster work any more then it is now.
> There is already MSET that could potentially involve keys from several
> physical servers, and a number of other commands.
Indeed, we are forced to start thinking about node-commands and
cluster-commands. They can hardly be the same, it's already hard to
implement basic single-key atomic operations on Redis-cluster, go
figure how hard it is to implement multi node operations. Currently
most of the other key-value stores implementing a cluster have only
support for basic GET/SET/DEL operations.
I'll follow the roadmap implementing redis-cluster after VM, but I'm
every day more convinced that a good way to implement distributed
fault tolerant applications with Redis is application level sharding
where every node is replicated one or more times for redundancy. All
this will become more clear when I'll start working to redis-cluster
but my guess is that I could like if redis-cluster also will provide
"tools" to help working with application level sharding, like ways to
move keys matching patterns from one node to another and so forth.
Cheers,
Salvatore
> On 28 дек, 07:03, Adam Michaels <ilov...@gmail.com> wrote:
> There is also some
>> questions on how this would work with redis-cluster and if the keys
>> inside the "transaction" are on different servers and if doing two
>> phase commits is required.
>
> --
>
> 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 'antirez' Sanfilippo
Salvatore Sanfilippo
> Hello everyone!
>
> I just started following Redis and implementing new features in my
> fork at GitHub. Redis is a great project and it's good to see that it
> is getting atomicity!
>
> I do see a potential problem with the current implementation:
>
> If you execute INCR or INCRBY inside of a MULTI you don't know what
> the value of the key will be until the EXEC is run. This means that if
> you want to get a unique user ID and make use of that value you can't.
> The same is true for all read and write commands, they all return
> '+QUEUED'.
Hello Dan,
I see what you mean, basically Redis transactions are now limited to
the fact you can't use what you read, so there is no way to use INCR
or even more interestingly *conditionals* like "do this if this list
is at least 10 elements long".
I think this is a good tradeoff as the current semantic is *much*
simpler to implement and understand.
Other Redis atomic commands help you to work with this limits. For
instance in your example:
id = r.incr('my.next.id')
r.multi
r.sadd('my.ids',id)
r.rpush('foobar,id)
r.exec
ID is outside the transaction but still the transaction can fail
without to create any problem.
There are examples where with current MULTI/EXEC it's not possible to
find a good solution, but it's a tradeoff, and I think an acceptable
one.
Salvatore Sanfilippo
<ant...@gmail.com> wrote:
> There are examples where with current MULTI/EXEC it's not possible to
> find a good solution, but it's a tradeoff, and I think an acceptable
> one.
Forgot to mention one thing. That there is also another solutions to
many problems, that is to use the locking provided by SETNX (check the
SETNX documentation, there is an algorithm for optimistic locking)
*and* our transactions. This allows to perform much more complex
operations when required.
Dan Bravender
Thank you for clearing up how to use INCR with the new MULTI and EXEC
commands and thank you for Redis. I'm glad that I posted the question
before implementing my overly complex idea :-D.
Since commands have a different response in MULTI mode I would like to
recommend that client libraries return a Queued object when Redis
responds with "+QUEUED". When passed as an argument to another command
an exception should be raised.
Python example:
>>> r.multi()
>>> id = r.incr('my.next.id')
>>> id
... <Queued object at ...>
>>> r.sadd('my.ids',id)
... Exception: Queued response cannot be used as a parameter. Read
values before calling MULTI. Please see the MULTI documentation for
more information.
This will help find errors before the user inserts 'QUEUED' as values
everywhere. I will implement this in the Python library.
Cheers,
Dan
On Dec 28, 6:03 am, Salvatore Sanfilippo <anti...@gmail.com> wrote:
> On Mon, Dec 28, 2009 at 12:01 PM, Salvatore Sanfilippo
>
> <anti...@gmail.com> wrote:
> > There are examples where with current MULTI/EXEC it's not possible to
> > find a good solution, but it's a tradeoff, and I think an acceptable
> > one.
>
> Forgot to mention one thing. That there is also another solutions to
> many problems, that is to use the locking provided by SETNX (check the
> SETNX documentation, there is an algorithm for optimistic locking)
> *and* our transactions. This allows to perform much more complex
> operations when required.
>
> Cheers,
> Salvatore
>
> --
> Salvatore 'antirez' Sanfilippohttp://invece.org
Joubin Houshyar
Just curious: wouldn't an embedded script engine (Lua seems to be a
very good fit) address all these issues? I understand it would be a
pain to do all the bindings, but once done it seems it would fit quite
nicely in the single threaded model of the server and the transaction
and lexical scope of the script would cover a pretty wide range of use
cases.
Alternatively, a server side (named) lock would appear (?) to provide
the same exact functionality as the MULTI, with the added bonus that
intermediate values are usable, and allow interleaving of other
clients' commands to proceed while the 'transaction' is in progress.
A MULTI does block all other clients, correct? [I think this was
discussed but don't remember just now what conclusions were reached]
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
LOCK my-transaction
+OK
SET mykey 4
ciao
+OK
GET mykey
$4
ciao
UNLOCK my-transaction
+OK
/Regards
On Dec 28, 6:01 am, Salvatore Sanfilippo <anti...@gmail.com> wrote:
> Salvatore 'antirez' Sanfilippohttp://invece.org
Steve Farrell
Alternatively, a server side (named) lock would appear (?) to provide
the same exact functionality as the MULTI,
Sergey Shepelev
> Hi,
>
> Just curious: wouldn't an embedded script engine (Lua seems to be a
> very good fit) address all these issues? I understand it would be a
> pain to do all the bindings, but once done it seems it would fit quite
> nicely in the single threaded model of the server and the transaction
> and lexical scope of the script would cover a pretty wide range of use
> cases.
>
Yeah, scripting would be awesome.
Dan Bravender
>> discussed but don't remember just now what conclusions were reached]
MULTI does *not* block other clients. Once EXEC is run then all the
queued commands are run atomically on the server.
Salvatore Sanfilippo
I think you both are saying the same thing :)
MULTI/EXEC, when EXEC is run, will execute sequentially all the
commands queued without to run other stuff in the context of other
clients, then will immediately pass to other clients.
Actually there *is* a minor violation of this rule now. Even when
executed in the context of a MULTI/EXEC, an LPUSH/RPUSH against a list
that is empty and having clients blocking with an BLPOP/BRPOP for this
key, will run a bit of code in the context of the other client. So for
example:
DEL mylist
(another client waits with "BLPOP mylist 0")
MULTI
LPUSH mylist somevalue
LLEN mylist
EXEC
Will return ["+OK",0]
That is, mylist length is not 1 as the LPUSH behavior if there is a
blocking client for this key is to pass the value to it.
This message passing strategy is just too simple to implement, too
fast, and too interesting from the point of view of the durability
(there is no need to write the LPUSH operation into the append only
file because we just forwarded the value to another client without to
modify the list). So I think this inconsistency is absolutely
acceptable.
And actually, if you see it from the right point of view, it's not an
inconsistency, it's just that the BLPOP behavior is more like "tell
LPUSH and RPUSH to pass my the object ASAP" than "block until there is
something to get from the list". At least form the implementation
point of view. Of course in the documentation I'll simply write that
BLPOP is a blocking LPOP that waits for more data in the list and get
this data ASAP :)
Cheers,
Salvatore
> --
>
> 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 'antirez' Sanfilippo