Re: Issue 65 in redis: [Feature Request] Blocking LPOP
re...@googlecode.com
Comment #4 on issue 65 by mrevelle: [Feature Request] Blocking LPOP
http://code.google.com/p/redis/issues/detail?id=65
I really like the idea of having a "SUBSCRIBE" command that would allow a
client to subscribe to receive a
notification of either the next or all changes for a particular key. That
seems general enough and since a
common use case of Redis is as a holder of system state it makes sense that
system components (aka, clients)
shouldn't have to poll the server.
If this is acceptable to the developers, I'm more than willing to do the
work and provide a patch.
--
You received this message because you are listed in the owner
or CC fields of this issue, or because you starred this issue.
You may adjust your issue notification preferences at:
http://code.google.com/hosting/settings
re...@googlecode.com
Comment #5 on issue 65 by antirez: [Feature Request] Blocking LPOP
http://code.google.com/p/redis/issues/detail?id=65
Hello mrevelle,
I'm currently considering how to implement this. The feature can't be added
in 1.1 as
we already have too fresh meat and I really want 1.1 to be as stable as 1.0
was so
there is a lot to test already. But I could like to implement this feature
in a
cooperative and more general way. Something like this:
A client can issue the following command:
SLEEP foobar
(foobar does not have to be a key, can be any kind of string without spaces
and
newlines)
this client will block until some other client will issue the following:
AWAKE foobar
Multiple clients can sleep for the same token, and AWAKE will aware all the
clients in
a single operation. A client can sleep only for a single token.
This way the implementation will be much simpler, Redis will be faster, and
the user
will have full control, that is, sometimes it is needed to change the keys
without for
the "workers" to start processing items, because for instance there is a
script to
sanitize the DB running.
It seems like the best of all the worlds, please if you think my design is
flawed don't
esitate to prove me wrong.
Cheers,
Salvatore
re...@googlecode.com
Comment #6 on issue 65 by temotor: [Feature Request] Blocking LPOP
http://code.google.com/p/redis/issues/detail?id=65
Salvatore, you always come up with approaches i've never seen before. :)
Which is
good.
Obviously, there a race condition with multiple clients doing:
AWAKE foobar
RPOP list-key
What's your opinion on this?
I believe it looks like http://en.wikipedia.org/wiki/Thundering_herd_problem
re...@googlecode.com
Comment #7 on issue 65 by antirez: [Feature Request] Blocking LPOP
http://code.google.com/p/redis/issues/detail?id=65
Hello temotor,
yeah I was thinking about this issue when writing this proposal. Basically
in order to
be general this implementation is no longer atomic, *even* when a single
client
waits. This is the "flow of time" when implementing blocking LPOP using
SLEEP and
AWAKE.
t1) client 1 SLEEPs for foo_token
t2) client 2 PUSHes something in foo and AWAKE foo_token
t3) client 1 gets the +OK from the server
t4) client 1 LPOPs from foo
between t3 and t4 another client may PUSH something inside the foo list, so
there is
no guarantee that the latest item pushed by client 2 will be what client 1
will read, as
opposed to BLPOP (blocking lpop) that is able to guarantee this.
But the good news is that in most of the algorithms I can think of based on
blocking
by the consumer what really is important is to avoid polling. Once there is
something
new in the list this is going to be processed ASAP. Even if new stuff is in
the list as
far as the consumer is getting the top-most it should be ok.
But... unfortunately it's not this simple :)
Again, single client blocking, we'll try to generalize the idea later.
t1) client 1 SLEEPs for foo_token
t2) client 2 PUSHes something in foo and AWAKE foo_token
t3) client 1 gets the +OK from the server
t4) client 1 LPOPs from foo
t5) client 1 is still LPOPping, but client 3 PUSHes something into foo and
AWAKE
foo_token, that does not exist. No operation is permed by AWAKE.
t6) client 1 SLEEPs again for foo_token. Even if there are elements inside
the list it
will not get unblocked.
/\/\/\/\~~~~ NOT COOL ~~~~/\/\/\/\/ :)
How to fix this? Adding an internal counter, probably.
AWAKE increments a counter associated to the token
SLEEP waits if the counter is zero, otherwise decrements the counter and
returns.
With the new implementations of AWAKE and SLEEP now it's possible to mount a
blocking LPOP that actually is able to avoid deadlocks.
Still there is a problem even with just one client. What about the consumer
crashing
just after SLEEP returns with +OK but before the LPOP? There will be an
element
inside the list but no-one will LPOP it.
There are two fixes:
a) In some protocol it does not matter a lot, just it will get popped the
next time
something is pushed. After SLEEP the client may start with an LLEN to check
if there is
something new.
b) better: anyway a client before to SLEEP will start checking if the are
the conditions
to start working instead to wait. That is, perform an LLEN and if it's 0
start SLEEPing.
Multiple clients:
I think that when multiple clients are sleeping for the same key all should
be
awakened and the counter decremented of just one. This is almost never a
bad thing,
at max just one will get new data and all the rest will get a 'nil' in the
List example,
in basically they have a way to check if there is no data in all the
protocols.
After all the user is permitting N clients to sleep for the same key, she
should know
what she is doing.
On the other side SLEEP/AWAKE allow for a lot of new interesting protocols
to be
mounted, for instance you can have a randomized message passing data
structure,
that is a Redis Set with an SRANDPOP in the consumer side, or a centralized
way to
perform timing on background jobs in large structures with a lot of
background
processes, in order to make all this adaptive to the load, and so forth.
Cheers,
Salvatore
re...@googlecode.com
Comment #8 on issue 65 by temotor: [Feature Request] Blocking LPOP
http://code.google.com/p/redis/issues/detail?id=65
How about this?
SLEEP foo_key timeout
It returns +OK (meaning "you are awaken") or +TIMEOUT.
This is basically select(2) for single "key descriptor" :)
re...@googlecode.com
Comment #9 on issue 65 by antirez: [Feature Request] Blocking LPOP
http://code.google.com/p/redis/issues/detail?id=65
Yep temotor, a timeout may make systems based on SLEEP/AWAKE a lot more
robust. It
may be very similar to the final solution... at some point of the 1.x Redis
saga it may
get implemented, not sure when this will happen, if there are chances for
1.2 or 1.3
given the huge list in the TODO :)
Cheers,
Salvatore
re...@googlecode.com
Comment #11 on issue 65 by nick.telford: [Feature Request] Blocking LPOP
http://code.google.com/p/redis/issues/detail?id=65
Hi guys,
I thought I'd weigh in, since I'm looking at building a highly scalable
streaming
server using Redis "queues".
I agree with everyone that we need a mechanism to block connections until
the target
list becomes non-empty and I think I have a pretty high-performance
solution.
Essentially, it's the solution that Severin suggested - but using epoll.
Looking at
trunk, I notice that the event loop now has support for epoll and kqueue,
which gives
Redis a high performance async event loop.
Proposal: BLPOP/BRPOP that blocks the current connection until an item in
the target
list becomes available. When one (or more) is available, the item is
removed from the
left/right of the list.
Blocking is done using epoll/kqueue to subscribe to the LPUSH/RPUSH events
(with a
callback) and then blocks the connection. When the event is triggered, the
callback
is called and the first connection subscribed to it is given the element
from the
left/right of the list as requested.
To summarise:
- 1 connects to Redis
- 2 connects to Redis
- 1 issues a BLPOP command for key "test"
- 1 is blocked because "test" is an empty list
- 2 issues an RPUSH command with a value
- the PUSH event for "test" is fired, sending the value back to 1 and
unblocking it
Note: events are queued and only a single connection is ever unblocked to
handle an
event, this prevents any race-conditions as each blocked connection will
wait in line
for an element to become available to it.
For lists that already have items:
- 1 connects to Redis
- 1 issues a BLPOP command for key "test"
- because "test" has at least one item, 1 doesn't subscribe to any epoll
events and
simply does an LPOP command
// psuedo-code
if (llen(key) > 0) { return popGenericCommand(c, where); } }
This shouldn't be too much additional work as far as I can tell and should
be very
high-performance. The only bottleneck i can think of is the having a lot of
connections blocking could mean you run out of file-descriptors.
That said, its the application's responsibility to ensure it doesn't open
up too many
connections and the DBAs responsibility to ensure the database doesn't run
out of
connections.
Regards,
Nick Telford
re...@googlecode.com
Comment #12 on issue 65 by ezmobius: [Feature Request] Blocking LPOP
http://code.google.com/p/redis/issues/detail?id=65
I'd love to see this implemented as Nick outlines. Having a blocking pop
would make queueing with redis much
more compelling.
re...@googlecode.com
Comment #13 on issue 65 by antirez: [Feature Request] Blocking LPOP
http://code.google.com/p/redis/issues/detail?id=65
@Nick thanks for the proposal.
@ezmobius I was thinking about this stuff the whole day... Basically Nick
proposed
more or less the Severin Hacker solution, but with a more well specified
semantics.
What I didn't liked about this solution was the not-enough general
approach: it's
interesting in general if Redis can be awakened by general events, not just
L/R
pushes against a list. But the general solution has a race condition,
fixable with
counters, but is still a not so trivial semantics to tell the user.
Then I finally realized that actually the blocking LPOP can be used as well
as a
general notification tool, it's just that it is more promptly tuned to do
the obvious
thing, blocking on lists.
In short: finally I'll implement this stuff in the 1.3-unstable at the
start of the
next year. The implementation will not be exactly what Nick suggested but
this is
just a matter of internals, the semantics will be the same.
re...@googlecode.com
Comment #14 on issue 65 by nick.telford: [Feature Request] Blocking LPOP
http://code.google.com/p/redis/issues/detail?id=65
Fantastic! :D Was good discussing this with you today Salvatore.
re...@googlecode.com
Comment #15 on issue 65 by temotor: [Feature Request] Blocking LPOP
http://code.google.com/p/redis/issues/detail?id=65
Will it have a timeout?
re...@googlecode.com
Comment #16 on issue 65 by gwebmast...@yahoo.com: [Feature Request]
Blocking LPOP
http://code.google.com/p/redis/issues/detail?id=65
How are slaves considered in these scenarios?
re...@googlecode.com
Comment #17 on issue 65 by antirez: [Feature Request] Blocking LPOP
http://code.google.com/p/redis/issues/detail?id=65
slaves are an issue indeed. Not sure for the timeout, possibly will not
have one in the
first implementation but will be added later. I've still to fix my ideas
about the
implementation.
Btw this is my current idea on the implementation:
When a client issues a BLPOP, if the list is not empty, we just forward the
call to
LPOP. It's a non brainer from all the point of views, no timeout concerns,
no
replication concerns as LPOP will increment server->dirty so the command
will be
forwarded to all the slaves (and to the append only file, of course).
When a client issues a BLPOP *and the list is empty* what happens is that
this client
is put into a different hash table, where the key is the blocking key, and
the value is a
list of all the clients blocking for this client. Clients will be appended
on tail. Server-
> dirty is NOT incremented, so the operation does not exists form the point
> of view
of the slaves or the append only file. Also the read handler of the event
loop will be
unregistered for this client.
So when a PUSH is performed against a key, a function named something like
awakeBlockingClients() is called. This function checks if there is some
client waiting
for the key, takes the first (the head of the list) so that the first that
blocked will be
the first to be served. If there is one the object just pushed by the
client will be
returned to the blocked client, and its read handler re-registered.
And here there is a trick: how this works with replication and AOF file?
Think at it, if
we are BLPOP-ing and another client LPUSHed the list will be the same! We
are just
forwarding a string from a client to another one :) And the list was empty
previously,
so there is no difference between LPUSH and RPUSH. There is no dirty flag
to set, no
command to forward to slaves, no command to write in the append log file.
Ok now I've a much better idea about how to implement this ;)
re...@googlecode.com
Status: Fixed
Comment #18 on issue 65 by antirez: [Feature Request] Blocking LPOP
http://code.google.com/p/redis/issues/detail?id=65
this was implemented time ago, closing the issue...
re...@googlecode.com
Comment #19 on issue 65 by severin.hacker: [Feature Request] Blocking LPOP
http://code.google.com/p/redis/issues/detail?id=65
thanks!