17

I have a redis list I have created, I am using it as a queue at the moment that reverses once in a while. My problem is that I would like to be able to get the index of an item on that queue/list by value.

Example

If I have a list with the following values:

{"dan","eduardo","pedro"}

The indexes would be:

0 : "dan"
1 : "eduardo"
2 : "pedro"

I want to be able by passing in the value to get the index of that value on my list.

Like "eduardo" and get back '1'.

Is that possible if so how would you do it?

Also something I should say is that I am performing queue commands to my list, removing items from the top and adding them at the bottom.

I am currently using node.js 0.6.6 and the latest redis module with the latest redis version 2.4.4.

I am happy for a solution just in redis-cli.

Also there is no constraint other then it must be possible to do it with redis alone, no external process etc however if you want to use the EVAL command with lua go for it.

Edit

Also I think my answer might be on sorted sets not queues.

1
  • 1
    Redis has evolved and as of Redis 6.0.6 there is now a solution to do exactly this. Can you please change your accepted answer and select the answer that shows the solution? Thanks!
    – seinecle
    Dec 1, 2021 at 12:20

6 Answers 6

12

Use sorted sets to implement a queue.

Add members and use timestamp as score.

> ZADD queue 1326990501 foo 1326990502 bar 1326990503 baz 1326990504 qux
(integer) 4

You can return members in FIFO and LIFO order by the use of ZRANGE and ZREVRANGE respectively.

FIFO:

> ZRANGE queue 0 0
"foo"

LIFO:

> ZREVRANGE queue 0 0
"qux"

To find the index of a member use ZRANK. ZRANK op is O(log(N))

> ZRANK queue bar
(integer) 1
3
  • if i move items on the set, to the scores update themselves? i.e. if all score are 1 to 100, if i change the first item on the set to 101 the score for the other wont change will they?
    – dmportella
    Jan 19, 2012 at 16:41
  • I'm not sure I understand the question. If you change the score of a member in the sorted set, its rank(index) might change as well. The rank of any given member depends on the score of all other members in the sorted set. Hence, why the ZRANK is O(log(N)). I'm not sure if this answers your question, but you can just play around with sorted sets in redis-cli and you'll probably find the answers you are looking for.
    – Simon Klee
    Jan 19, 2012 at 20:40
  • overhaul I think you have most of it sorted however managing the scores on a sorted set, that acts like a queue that items get moved from the top to the bottom and might reverse e.g. items from the bottom moving to the top would be a lot of overhead since items are moving every 250 milliseconds. Don't get me wrong your answer is good but I can't take the score management overhead.
    – dmportella
    Jan 24, 2012 at 23:22
10

I don't know the nodejs client details for this, but the following is an implementation of a very simple indexOf command in lua.

In a my file indexof.lua i have the following code:

local key = KEYS[1]
local obj = ARGV[1]
local items = redis.call('lrange', key, 0, -1)
for i=1,#items do
    if items[i] == obj then
        return i - 1
    end
end 
return -1

Lets push a few values to a mylist.

> rpush mylist foo bar baz qux
(integer) 4

We can use the lua script to find the index of any value within the list. The command is O(N).

$ redis-cli --eval indexof.lua mylist , bar
(integer) 1

index of bar was 1

> lindex mylist 1
"bar"

index of nil is -1

$ redis-cli --eval indexof.lua mylist , nil
(integer) -1

Look at the http://redis.io/commands/eval further documentation on EVAL command.

3
  • 3
    This is an interesting example of Lua usage. However, the cost is a full copy of the list, plus a linear search in Lua. It can only be applied on small lists. For large lists, it will freeze Redis loop for several seconds and consume too much memory. Jan 19, 2012 at 12:31
  • 1
    It depends on the application if the solution given in this answer is a good choice. Given by the description of the question there are no indications to how big or small the queue is. To have a lower memory overhead we need to use a different search algorithm, and to do that the list must be ordered by value. Also, I think using zrank and sorted sets sounds like a better solution if this is an operation done on a large list of items.
    – Simon Klee
    Jan 19, 2012 at 15:20
  • The queue can be up to 10000 items long. and it changes i.e. items get dequeued and enqueued every 200 milliseconds.
    – dmportella
    Jan 19, 2012 at 16:44
9

Getting the index of an element in a redis list is possible with LPOS command (available since version 6.0.6)

From the documentation,

  • Command - LPOS key element [FIRST rank] [COUNT num-matches] [MAXLEN len]
  • The command returns the index of matching elements inside a Redis list.
  • By default, when no options are given, it will scan the list from head to tail, looking for the first match of "element". If the element is found, its index (the zero-based position in the list) is returned. Otherwise, if no match is found, NULL is returned.

So in you case, for the list {"dan","eduardo","pedro"} with key users

LPOS users eduardo

Must return 1. I personally haven't tried using it in a lua script hence not providing the script but should be straight forward I believe.

2
  • This is now (as of version 6.0.6) the correct answer. It needs upvotes. Sep 1, 2020 at 3:38
  • updated to be the accepted answer ty for letting us know
    – dmportella
    Jul 29, 2022 at 20:01
8

As you may tell by now, Redis don't support such operation (sad face).

Although someone made some pretty good remarks on why such operation would make sense, looks like Salvatore won't implemented it any time soon.

There are basically two workarounds (as pointed out by the other answers):

  • Use a custom lua script to find the index in the list;
  • Use a sorted set (instead of a list) with a timestamp as score and ZRANK for the index.

Since the first is O(N) and the latter just O(log(N)) you can probably tell which one outperforms the other.

Anyway I decided to put to the test*:

╔════════════════╦═══════════════════════╦══════════════════════╗
║                ║ Sorted Set with ZRANK ║ List with lua script ║
╠════════════════╬═══════════════════════╬══════════════════════╣
║  1000 elements ║   0.0638264 seconds   ║   0.2723238 seconds  ║
╠════════════════╬═══════════════════════╬══════════════════════╣
║ 10000 elements ║   00.4484714 seconds  ║  41.0661683 seconds  ║
╚════════════════╩═══════════════════════╩══════════════════════╝

Yup, that's staggering 41 seconds for just ten thousand elements.

* On Windows 7, Redis 2.8 (MSOpenTech port), .NET 4 with compiler optimizations turned on and StackExchange.Redis 1.0.488.

0
5

As per ticket 140 on the list of issues of redis.io

Feature Request: lRank

"Hi, this command will likely not be implemented as it is both an O(N) command and one that usually is felt as needed only when there is some error in the data layout design." by Salvatore Sanfilippo on https://github.com/antirez/redis/issues/140.

I am not quite sure why and how wanting to find out the index of an item by value could be an error in the data design. However he makes clear that you can use lua code and/or sorted sets.

So the up shot of it is that there is no way to find out the index of an item in a list other then using a lua script.

However depending on the implementation i.e. data design it may be better to consider sorted sets instead of lists.

1

Using sorted sets (ZADD, etc) you can use ZRANK.

Edit: My old answer below doesn't work, because your list changes, although it does, with a list that only grows using RPUSH.

You could store the index with the value (or its hash) as a key:

set listvalue listindex

In order to keep your redis organised, you could prefix those keys with the listname:

set listname:listvalue listindex
5
  • I am not sure what you mean could you provide an example?
    – dmportella
    Jan 18, 2012 at 11:47
  • I think using sorted sets would work but i would need to update the index.score for everyone on every change to the table if I wanted to keep the numbers right.
    – dmportella
    Jan 18, 2012 at 12:50
  • ZRANK returns the rank (ie index) of the key in the sorted set.
    – mtsr
    Jan 18, 2012 at 12:56
  • Which is fine, I understand that however I think I would still need to update the score so to change the order of the items to mimic the queue behaviour.
    – dmportella
    Jan 18, 2012 at 13:09
  • 1
    Ahhh, yes. That's the idea of the sorted set. If you ZADD the same member again, its score is updated to the new score. Alternatively you can ZINCRBY to increment/decrement a score without doing a lookup first. But this is mainly for priority queues, not so much for LIFO or FIFO.
    – mtsr
    Jan 18, 2012 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.