[Feature Request] WAIT until a change is made

[GoogleCodeExporter]

I would like a blocking command which waits on one or more keys until a 
change is made to its value. For example I could wait on a list, set, 
sorted set, or simple string values. I see there was already some 
discussion [1] on a similar topic, which turned into the block pop 
commands. However, this feature request is for a more general form so I 
figured I would start a new feature request.

The use case I have for this is that I'm storing a set of messages in a 
sorted set, and I would like my client notified when this sorted set 
changes. I realise I could use a list, BRPOP on it, and use it as a 
notification system, however my setup is a little more complex because of 
how my slaves are configured.

I have 1 master, and multiple slaves connected to this master. Each time 
the master makes a change to the sorted set I need all slaves to receive a 
notification and do something with the set. I could create a notification 
list, which the slaves BLPOP on and the master RPUSH onto. As there is no 
replication back from the slave, this ensures each slave is able to POP off 
every notification at its own rate. The only problem is that the master is 
unable to pop of the notifications because that action would be replicated 
to the slaves. Meaning a huge list of every notification would be stored on 
the master.

Instead a WAIT command would allow my slave/clients to WAIT on the set 
until a change is made. Once the change is made it can then act on it.

WAIT key1 key2 ... keyN timeout

This command returns the list of keys which were changes, or nil if the 
timeout occurred. When multiple clients are WAITing on the keys, then all 
clients get woken up. This is different to how BLPOP does it, as it only 
wakes one client per push. The rational here is that in a list, there are 
only a finite number of items in the list that can be popped. However here 
what the client does is left up to the client.

If the developers agree that this is useful I am willing to code it.

[1] http://code.google.com/p/redis/issues/detail?id=65

Original issue reported on code.google.com by brampton on 26 Mar 2010 at 1:08

[GoogleCodeExporter]

I like this idea.  It would allow me to do better implement a system I have 
today that 
relies on polling instead of a blocking network call.

Original comment by jzaw...@gmail.com on 26 Mar 2010 at 2:46

[GoogleCodeExporter]

One question: after we get a list of "changed keys", do I need to re-issue the 
WAIT command?

If yes, then this could cause lost notifications, if a modification is made 
between the time you get the changed 
keys and the time you re-send the WAIT command, you will not get that.

If we don't need to re-issue the WAIT command after every notification, then 
this needs more protocol work, 
for unsolicited notifications. At any point in time, the server might send you 
a notification from a command 
previously executed.

In this case, you should probably design this as a "watch list" that can be 
activated on each connection, and 
create commands to manipulate it (add keys, remove keys, on/off).

Either way, it seems to me that what you want is some sort of pubsub system, 
and there are plenty of those 
already.

Bye,

Original comment by mel...@gmail.com on 26 Mar 2010 at 3:33

[GoogleCodeExporter]

Sorry if my message sounded too negative, not my intention.

I would like very much to see a system as simple as you describe, just not sure 
it should be Redis.

Bye

Original comment by mel...@gmail.com on 26 Mar 2010 at 3:35

[GoogleCodeExporter]

melopt your feedback is welcome and pointed out a very obvious problem with my 
idea. 
Thanks. I will have to go back to the drawing board to figure out how I can do 
what I 
want.

Maybe instead of WAIT on any data type, a different Semaphore style system. 
BLOCK_AND_DECR which blocks until a integer is positive and then decrements it 
straight away. However, I will go away and think more on this.

BTW I am trying to build a publish subscribe system in Redis. I have looked at 
others 
pubsub out there, but based on my requirements and the fact that I would find 
Redis 
useful for other reasons, I thought it be best to build onto of Redis (even if 
it did 
mean writing some patches).

Original comment by brampton on 26 Mar 2010 at 5:52

[GoogleCodeExporter]

I still can't dig this proposal, it was discussed several time, but in my 
opinion it's not 
a good idea. I can see how BLPOP is limited to one client notified at a time, 
but 
WAITing on keys state change is:

1) It is complex semantic, but still is not able to model some problem in a 
clean way 
(for instance a real time chat with many people).
2) there are many ways a key can change state, as we have different types. This 
I bet 
will lead to a number of different feature requests over the first "WAIT" 
implementation. For instance requests so that WAIT can return the kind of 
change 
performed on the key (delete, push, string value reset, and so forth). And 
also: can I 
just watch for a specific event? Can I wait for more keys at once?
3) It is not possible to perform an operation on the key without WAIT to be 
awakened. Sometimes when a key is changed we want to awake the clients waiting 
for it, sometimes in the real world it is needed to hack on the key to fix 
something 
and we don't want clients to react at all.

I think that there is a fundamental problem about this, that is, what people 
really 
want when proposing WAIT or other systems to monitor for state changes, is 
instead 
a more general (and simpler) notification mechanism. I designed one and 
proposed it 
in the Google Group, so this is my proposal: Redis Channels.

A client can open one or more channels with:

CHANNEL OPEN channel1 channel2 foo bar

Multiple clients can open the same channel. All the clients that opened a 
channel will 
receive a bulk reply when some other client will write on the channel with:

CHANNEL WRITE channel1 <data>

Basically all the clients with channel1 opened will receive "data", in the 
following 
form:

*2
$8
channel1
$8
somedata

that is, as a two elements array, one is the channel name, one the data, so 
when the 
client is listening to multiple chans it is still possible to distinguish the 
originating 
chan.

A client can close all the opened channels with:

CHANNEL CLOSE

this will produce a NULL bulk reply, so the client can continue reading all the 
notifications until the NULL bulk is reached, and the connection can continue 
with 
any other Redis command.

This is:

1) Trivial to implement, it's a matter of 50 lines of code. If we agree it's a 
good 
system I can implement this in 2.0 monday.
2) Fully general. Many-to-many, you can send any bulk load. You can model WAIT 
using it, or an IRC-alike web based system, or what you want, in a trivial way.
3) Event-driven friendly. Imagine a node.js program using this stuff. The 
node.js 
Redis client will just bind a function to a channel, and every time there is 
something 
new the function gets called with two args (the channel name and the payload).

I really like this idea, just I want to be sure I'm not the only one :)

Cheers,
Salvatore

Original comment by anti...@gmail.com on 27 Mar 2010 at 7:52

[GoogleCodeExporter]

Antirez,

Channel is a great idea and should be the focus versus a wait feature. I've 
been playing 
with the concept in node.js the last few weeks and it has play in many areas 
including 
redis.

Thanks, Alexander

Original comment by sicul...@gmail.com on 27 Mar 2010 at 8:33

[GoogleCodeExporter]

Hi,

Channels is a great tool. Its a classic pubsub setup, where your topics (in 
classic pubsub lingo) are called channels :).

Its true that you can model WAIT over Channels. You only need one thing: you 
need a Channel per key, and you need 
that Redis writes to that Channel every time the key changes.

Having this functionality inside Redis is nice. I say this because over the 
past months I lurked in the mailing list I saw 
Salvatore come up with simple solutions that work very very well, and we got to 
trust him more and more, and we 
want to use his code.

But on a general note, you could probably use a "real" pubsub system, like 
OpenAMQ, and proxy the Redis replication 
feed into it. As a fake Redis slave you'll get a notification for each changed 
key, just rewrite that into a AMQP 
notification over a particular exchange.

But simplicity wins most of the time, so a basic pubsub system, with Channels, 
will probably be enough for most of 
people's needs.

Thinking a bit ahead, if I were to deploy this (and I really like per key 
notifications), I would probably dedicate a Redis 
slave as my pubsub system: master does what Redis does best, works as a 
DB/Cache, and we setup a dedicated slave 
as the pubsub hub, that gets all of his changes from the master and checks open 
channels and sends out 
notifications.

On that setup, this slave could even be configured as a null-store: it gets the 
sync feed but doesn't actually stores 
nothing, just notifies. I bet we can get a pretty low memory usage service with 
this setup.

Bye,

Original comment by mel...@gmail.com on 27 Mar 2010 at 9:02

[GoogleCodeExporter]

So that I understand the CHANNEL proposal. Once I CHANNEL OPEN, can I issue 
other 
commands? Or am I blocked? The fact I can CHANNEL CLOSE would seem to imply I 
can issue 
other commands. So my question is, how do I destiguse channel multi bulk 
replies, from 
the replies of other commands? I could see a condition where I'm sending 
multiple 
commands in a pipelined fashion, but the channel data just appears in the 
middle of 
this. Would my client not get confused?

This CHANNELs idea would certainly do what I need.

Original comment by brampton on 27 Mar 2010 at 12:58

[GoogleCodeExporter]

Redis channels looks good.  +1 here.  I can see some uses for this in our 
environment, 
particularly with implementing message bus based systems.

Sounds very much like IRC at a lower level :)

Original comment by chrisjsmithzz@gmail.com on 27 Mar 2010 at 2:37

[GoogleCodeExporter]

I assume there would be a CHANNEL POLL command, which each client would poll 
with after issuing any number 
of CHANNEL OPEN commands?  CHANNEL POLL would return nil if no messages came 
through any channels that 
client was listening on, or the (<channel name>, <data>) pair(s) that antirez 
described above is there are new 
messages.

Original comment by sed...@gmail.com on 27 Mar 2010 at 9:34

[GoogleCodeExporter]

I'm curious to whether or not this would block as well. If it doesn't block, 
but allows the 
execution of other commands, this would be amazing.

Also, would creating channels be as cheap as creating keys?

Original comment by tristanz...@gmail.com on 27 Mar 2010 at 10:55

[GoogleCodeExporter]

I know I'm coming in late, but I would vote against the channel command, 
because while it sounds somewhat useful it doesn't 
solve the original problem of waiting until a key changes.

I would suggest the addition of a few more discrete purpose blocking commands, 
and optionally a wrapper to allow you to wait 
on multiple blocking commands at once.

== BMULTI - Multiple Blocking Command Wrapper  ==
First the wrapper, keeping with the MULTI/EXEC/DISCARD pattern.  It basically 
tells the server you wish to perform a blocking 
wait for something to happen. 

BMULTI
+all further bcommands will be queued until bexec or bdiscard is issued
BLPOP key1 key2 key3
+blocking queued
BRPOP key3 key4 key5
+blocking queued
BEXEC timeout
 1. blpop worker:queue:3
 2. dothiscommand

 individual timeouts overriden by wrapper timeout
 waits until first blocking command occurs or timeout
 adds command + key to normal output of blocking command that fired
 removes waits for blocking commands that didn't happen

== Additional Blocking Commands ==

2) there are many ways a key can change state, as we have different types. This 
I bet 
will lead to a number of different feature requests over the first "WAIT" 
implementation. For instance requests so that WAIT can return the kind of 
change 
performed on the key (delete, push, string value reset, and so forth). And 
also: can I 
just watch for a specific event? Can I wait for more keys at once?

=== Generic Command Key Idea ===
Make a command that lets you wait for specific command on a specific key like 
this:

   BWaitForCommand command Key1 key2 key3 key4

It monitors the replication stream much like monitor does.  When a command / 
key pair - much like a key value pair - matches, 
the blocking event continues.  It would return the command key args.

Not really useful to me, but would allow people to wait for very specific 
events.

=== Specific Blocking Events ===
Avoid the confusion of generic "WAIT" by making very specific commands.  I 
think the majority blocking key changes waits would 
be waiting for items added or removed to a list or set.  I prefer something 
like the following commands, which seem more 
"redis-like" in my head. 

BLMEMBERADDED Key1 Key2 Key3 Timeout
BSMEMBERADDED Key1 Key2 Key3 Timeout
BZMEMBERADDED Key1 Key2 Key3 Timeout
BZMEMBERREMOVED Key1 Key2 Key3 Timeout

I like these because they are discrete well defined operations could be used by 
themselves and customized per data type, and 
with the BMULTI wrapper you could combine them as needed.

== Stay Focused - "WAIT until a change is made" ==
The notification system sounds interesting, but this reads like Zawinski's Law 
in action.  For me at least notifications and 
channels are not what is needed.  I just want to wait until a new item is added 
to a list or not, without changing the list 
like BLPOP/BRPOP does.  

Channel notifications might as well be irc because while notifications sound 
nice, they still are not triggered automatically 
by changes. I still have to go lookup the key and figure out what has changed. 
At the very least I would move CHANNEL idea to 
it's own issue and keep discussing how wait for key changes should be 
implemented in this issue. 

Original comment by russr...@gmail.com on 28 Mar 2010 at 3:22

[GoogleCodeExporter]

thanks for your input russryba. Maybe I missed it, but your solution doesn't 
solve the 
problem pointed out by melopt, where you could lose updates between the 
blocking calls.

Original comment by brampton on 28 Mar 2010 at 3:32

[GoogleCodeExporter]

Ok I'll provide some more detail as I see my initial post didn't fully 
specified the 
semantics of the channel command. Note that currently I use CHANNEL open / 
close 
/ write but the command names may change in the future to respect better the 
official names of this messaging pattern.

A client can listen for a channel issuing the command:

CHANNEL OPEN channel1 channel2 ... channelN

Once a client opened a channel, the protocol is a "push style" one, that is, 
every time 
Redis receives new data for that channel, all the listening clients will 
receive a two-
elements multi bulk reply, where the first element is the channel name (where 
the 
message was send) and the second element is the data itself.

So the client does NOT need to use additional commands in order to receive 
messages. This means that the API will be different if the client is a blocking 
one (For 
instance the ruby client redis-rb is a blocking one) or if the client is non 
blocking 
(like the Node.js redis client or the Python Twisted client).

Blocking clients will pass an anonymous function, a method name, or a block, 
and 
this block will be called every time there is a new function. Example with the 
interface I think it's best for the Ruby client:

r = Redis.new
r = Redis.channel("open","foo","bar") {|chan,msg|
    puts "Received message #{msg} from #{chan}"
    return true
}

If the block returns true, it continues to get new messages (that is, the 
redis-rb 
implementation will just wait for the next reply and will call "yield" when a 
new 
message is received.

if the block returns false, the client sends "CHANNEL CLOSE", reads 
(discarding) all 
the further replies (if there was something already in queue) until a nul multi 
bulk 
reply is read (that is "*-1" in the wire protocol), and finally the r.channel() 
call 
returns.

Can the client issue commands after a CHANNEL OPEN command?
I think it can only be able to issue other CHANNE OPEN commands in order to 
open 
more channels if needed (as a result of messages it gets), or can call CHANNEL 
CLOSE channel1 channel2 ... channelN to close some channel).

Only of a client closes *all* the channels the server will reply with the nul 
multi-bulk 
reply. It is probably a good idea to also provide a CHANNEL CLOSEALL commands 
or 
alike in order to just close all the commands without the need for the client 
to 
remember what was opened and what was not.

Non blocking clients instead will just bind a function to a channel and return. 
Every 
time there is a new message the function will be called asynchronously, while 
the 
rest of the node.js / eventmachine /twisted / what-you-want application 
continues 
to run.

How to send messages to a channel?

CHANNEL SEND <channel name> <data>

the above command has nothing of special, and will just return the number of 
clients 
that received the message (that can be zero if no one is listening for that 
channel).

Time complexity:

Opening a channel is O(1)
Closing a channel is O(1)
Writing to a channel is O(N) where N is the number of clients listening to this 
channel, 
but the constant times are really small as it's a zero-copy operation.

How WAIT can be implemented by channels?

There are many ways but the most trivial way is to write to the channel having 
the 
same name of the key when a key is modified. For instance:

MULTI
SET x ciao
CHANNEL SEND x set
DEL y
CHANNEL SEND y del
EXEC

as you can see CHANNEL is more powerful than WAIT itself as it is also trivial 
to 
specify *how* the key was modified.

If you ask me, this feature rocks.

Original comment by anti...@gmail.com on 28 Mar 2010 at 5:02

[GoogleCodeExporter]

I think this and a lot of other external features are a bad idea to be built 
into the core of Redis.

A better and easier to maintain model would be to introduce an extension system 
- similar to nginx or Tokyo 
Tyrant. This extension could be done via C (like with nginx) or Lua (like Tokyo 
Tyrant).

This extension system would make it possible to extend Redis with all kinds of 
things without polluting the 
core code.

Original comment by ami...@gmail.com on 28 Mar 2010 at 11:33

[GoogleCodeExporter]

Channels (Pub/Sub) is now part of Redis, what we may do in the future is to use 
Pub/Sub to notify about events affecting specific keys, or to notify about keys 
expiring. This is not a priority currently as with Pub/Sub this can be 
implemented in the application layer and is probably the way to go, so for now 
I'm closing the issue, we have other priorities! ;)

Cheers,
Salvatore

Original comment by anti...@gmail.com on 27 Aug 2010 at 11:19

• Changed state: WontFix