Pattern for expiring set members

28126 views
Skip to first unread message

tom

unread,
Jun 4, 2010, 5:34:30 AM6/4/10
to Redis DB
Hi,

I am just trying to wrap my head around the expire command. Any way to
expire members of a set instead of the 'whole' key?

Tom

Salvatore Sanfilippo

unread,
Jun 4, 2010, 5:55:43 AM6/4/10
to redi...@googlegroups.com

Hello Tom!

the short answer is that it is not possible, but actually there are
patterns to make this possible.
This patterns have different tradeoffs. There are mainly three
patterns to do this:

1) Store the set element together with a timestamp. For instance if
your set is element is "foo", instead store "foo:<unix timestamp>",
where the unix timestamp is the time at which the element should no
longer be considered valid. So you handle this at application level.
The obvious problem is that if you don't access set elements this will
stay forever.

2) Use a sorted set (a single, global one for all the sets you have)
where the score is the unix time at which an expire will happen, and
the value is the encoded key-name+set-element, so that in a worker you
can get this data every second from the sorted set, and purge the old
entries.

3) mix 1+2 and just store in the sorted set an entry for every whole
set where you know you have at least one expire: use always the
nearest expire of the sorted set as key. In a worker check all the
elements of the set and purge only what's needed, then update the
score in the sorted set to the next-to-expire element in the set. This
is viable only if the sets are small.

Possibly there are other methods, but here the bottom line is: you
have to mount such a mechanism at application level using what Redis
provides.

One thing that we may do in future, is to provide timers. Ways to tell Redis:

AFTER 10
SREM myset foo
EXEC

That is, execute this command(s) in 10 seconds starting from now. Just
an idea... but may be an interesting experiment.

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

tom

unread,
Jun 4, 2010, 6:06:17 AM6/4/10
to Redis DB
Hello Salvatore,

thanks a bunch for your immediate response! Because I am dealing with
perishable locations of vehicles I even consider this pattern, even if
you dare us not to use KEYS :-)
I am dealing with approx. 500.000 vehicle, half of them change every
60 secs. Currently I am considering moving from a two-index solution
in Postgres to a geohashed solution in redis.
Redis would bring two main advantages to the table: SETs are cheap and
I would'n need to take 'manual' care of the expired locations. Also
retrieval with the geohashes is (hopefully) extremely efficient, as I
can select the scope of retrieval by only considering keys with a
certain geohash-length, for example:

vehicle:asdk332hka => "set with 5 vehicles"
vehicle:asdk => "set with 120 vehicles"

So I thought about using KEYS to find, well, the keys according to my
scope needs and then I would simply use strings to store the vehicle
id's or even the the complete vehicle data to save one lookup.
And then the keys could simply expire.

Any thoughts on using KEYS here? I am well below 1 mio keys here (as
in your example) and even waiting 40ms wouldn't be a problem
(customers are currently waiting up to one sec !! ).



On Jun 4, 11:55 am, Salvatore Sanfilippo <anti...@gmail.com> wrote:
> Salvatore 'antirez' Sanfilippohttp://invece.org

Salvatore Sanfilippo

unread,
Jun 4, 2010, 6:13:30 AM6/4/10
to redi...@googlegroups.com
On Fri, Jun 4, 2010 at 12:06 PM, tom <list...@googlemail.com> wrote:

> So I thought about using KEYS to find, well, the keys according to my
> scope needs and then I would simply use strings to store the vehicle
> id's or even the the complete vehicle data to save one lookup.
> And then the keys could simply expire.

Well everything can be abused as long as it solves a problem, but
maybe you should look at sorted sets and the ZRANGEBYSCORE command.

Now maybe I'm understanding the expire problem better. What do you
want is dropping the vehicle form the set when you don't get fresh
information for N seconds? If this is what you are trying to do, I
think there is a good solution using a sorted set, that is simply to
remember in a sorted set the last time (use the unix time as score)
you got an updated location of a given vehicle, and in which key it is
located. So you can have the worker purging old info every second.

Salvatore


--
Salvatore 'antirez' Sanfilippo

tom

unread,
Jun 4, 2010, 7:50:24 AM6/4/10
to Redis DB
We continued the discussion on IRC #redis. But here are the main
points that Salvatore brought up:

- In my special case, KEYS is not too bad. BUT due to it's long-
locking nature it really limits the number of queries that may be run
per server in parallel.
- To remedy this, maybe set-up a handful of servers OR go the
ZRANGEBYSCORE route

So basically, if +/- 40ms per query is no problem because there are
max a few queries per sec -> KEYS, else ZRANGEBYSCORE

Thanks for the quick help.

On Jun 4, 12:13 pm, Salvatore Sanfilippo <anti...@gmail.com> wrote:
> On Fri, Jun 4, 2010 at 12:06 PM, tom <listo....@googlemail.com> wrote:
> > So I thought about using KEYS to find, well, the keys according to my
> > scope needs and then I would simply use strings to store the vehicle
> > id's or even the the complete vehicle data to save one lookup.
> > And then the keys could simply expire.
>
> Well everything can be abused as long as it solves a problem, but
> maybe you should look at sorted sets and the ZRANGEBYSCORE command.
>
> Now maybe I'm understanding the expire problem better. What do you
> want is dropping the vehicle form the set when you don't get fresh
> information for N seconds? If this is what you are trying to do, I
> think there is a good solution using a sorted set, that is simply to
> remember in a sorted set the last time (use the unix time as score)
> you got an updated location of a given vehicle, and in which key it is
> located. So you can have the worker purging old info every second.
>
> Salvatore
>
> --
> Salvatore 'antirez' Sanfilippohttp://invece.org
Reply all
Reply to author
Forward
0 new messages