ZADD scoring on update

[Michael Russo]

All,

I'm looking to build a FIFO queue, with one important/ non-standard property: if an item that already exists in the queue is added again, then the insert should effectively be ignored. (This data structure can be useful for managing certain types of jobs, like warming caches, etc.)

An efficient way to model this structure in Redis would be to use a ZSET, where the score of each item in the set is the unix timestamp of when the item was added.

However, the semantics of ZADD are that if an item already exists in the set, that the score is updated to the score specified in the command. If there were some way to tell ZADD to not update the score if an element already exists, or perhaps to supply a certain score if the element is new and a different score if the element is not new, then this queue-like data structure could be easily (and very efficiently) modelled in Redis.

There are potentially a few other ways to do this, with the obvious approach being to check if an item already exists in the ZSET (using a set intersection) before issuing the ZADD command. However, this isn't bullet-proof, because it doesn't look like we will be able to do this within the context of a MULTI/EXEC.

Does anyone have any other ideas?

Best,
Michael

[Salvatore Sanfilippo]

On Tue, May 25, 2010 at 10:25 PM, Michael Russo <mjr...@gmail.com> wrote:

> There are potentially a few other ways to do this, with the obvious approach being to check if an item already exists in the ZSET (using a set intersection) before issuing the ZADD command.  However, this isn't bullet-proof, because it doesn't look like we will be able to do this within the context of a MULTI/EXEC.

Hello Michael,

this is a very good day to ask about that ;)
Because today Redis got WATCH, that is the Check and Set version of MULTI/EXEC

documentation here: http://code.google.com/p/redis/wiki/MultiExecCommand

With this you can mount your primitive (and many other cool stuff)
without problems and without race conditions.

You can find WATCH support in Redis 2.1.1 (tagged in Redis's git).
2.1.1 is a development version but you can consider it pretty stable
as it's 2.0-RC1 + WATCH and other minor changes.

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

[Michael Russo]

Thanks Salvatore!

Assuming that the queue is in a key called 'queue',  I'm trying to add an item called 'item1' to the queue, and 'tempzset' and 'tempkey' are temporary keys, then:

    WATCH queue

    MULTI

    DEL tempzset tempkey   # erase the temporary keys (needed for the intersection)

    ZADD tempzset 0 item1

    num_elements  = ZINTERSTORE tempkey 2 queue tempzset

    EXEC

    if num_elements == 0:  # if true, then 'item1' is not already in 'queue'

        MULTI

        ZADD queue <current_timestamp> item1

        EXEC

However,  I need the WATCH to persist through two MULTI/EXECs, which won't work because keys are automatically UNWATCHed after every transaction. 

It seems like there must be a much simpler way to express this.   (Alternatively, is it possible to issue the WATCH command inside of the first MULTI/EXEC block, after the ZINTERSTORE?)

Best,

Michael

--
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]

On Tue, May 25, 2010 at 11:31 PM, Michael Russo <mjr...@gmail.com> wrote:
> Thanks Salvatore!
> Assuming that the queue is in a key called 'queue',  I'm trying to add an
> item called 'item1' to the queue, and 'tempzset' and 'tempkey' are temporary
> keys, then:

That's my try.

First semantic: if the element is already there, don't add it at all.
In pseudocode:

FUNCTION ZADDNX(key,score,element):
WATCH key
score = ZSCORE key element
IF score != NIL
MULTI
ZADD key score element
retval = EXEC
IF retval == NIL: ZADDNX(key,score,element) (just try again if our
optimistic lock failed)
END

This time instead, a ZADDNX2 that will use a different score if the
element already exists

FUNCTION ZADDNX2(key,score_new,score_exists,element):
WATCH key
score = ZSCORE key element
IF score == NIL
addscore = score_new
ELSE
addscore = score_exists
END
MULTI
ZADD key addscore element
EXEC ( again.. if exec fails retry)
END

You can implement everything with just one MULTI/EXEC pair

[Michael Russo]

Beautiful, thanks Salvatore.

[Manish]

Wouldn't it still be better to have this in redis itself, since WATCH
optimistically locks the whole set, and if the set is highly write
active, you'll actually get a lot of retries, even if the element
you're touching may not have score updates for a while. Also, it'd be
nice to avoid the ZSCORE round trip since the server needs to do that
anyway for the ZADD regardless.

I actually just added code for ZADDNX, and another command I thought
was useful: ZADDCMP, which encapsulates a ZADD that succeeds only if
the existing score is lower than the new score, as well as the other
way around. Does this sound useful enough to be intergrated into
redis, especially since WATCH seems ill-suited for a high traffic
single set?

-Manish

On May 25, 2:43 pm, Salvatore Sanfilippo <anti...@gmail.com> wrote:

> On Tue, May 25, 2010 at 11:31 PM, Michael Russo <mjru...@gmail.com> wrote:
> > Thanks Salvatore!
> > Assuming that the queue is in a key called 'queue',  I'm trying to add an
> > item called 'item1' to the queue, and 'tempzset' and 'tempkey' are temporary
> > keys, then:
>
> That's my try.
>
> First semantic: if the element is already there, don't add it at all.
> In pseudocode:
>
> FUNCTION ZADDNX(key,score,element):
>   WATCH key
>   score = ZSCORE key element
>   IF score != NIL
>   MULTI

>  ZADDkey score element

>   retval = EXEC
>   IF retval == NIL: ZADDNX(key,score,element) (just try again if our
> optimistic lock failed)
> END
>
> This time instead, a ZADDNX2 that will use a different score if the
> element already exists
>
> FUNCTION ZADDNX2(key,score_new,score_exists,element):
>   WATCH key
>   score = ZSCORE key element
>   IF score == NIL
>     addscore = score_new
>   ELSE
>     addscore = score_exists
>   END
>   MULTI

>  ZADDkey addscore element

>   EXEC ( again.. if exec fails retry)
> END
>
> You can implement everything with just one MULTI/EXEC pair
>
> Cheers,
> Salvatore
>
> --

> Salvatore 'antirez' Sanfilippohttp://invece.org