Pop multiple values from Redis data structure atomically?

Question

Is there a Redis data structure, which would allow atomic operation of popping (get+remove) multiple elements, which it contains?

There are well known SPOP or RPOP, but they always return a single value. Therefore, when I need first N values from set/list, I need to call the command N-times, which is expensive. Let's say the set/list contains millions of items. Is there anything like SPOPM "setName" 1000, which would return and remove 1000 random items from set or RPOPM "listName" 1000, which would return 1000 right-most items from list?

I know there are commands like SRANDMEMBER and LRANGE, but they do not remove the items from the data structure. They can be deleted separately. However, if there are more clients reading from the same data structure, some items can be read more than once and some can be deleted without reading! Therefore, atomicity is what my question is about.

Also, I am fine if the time complexity for such operation is more expensive. I doubt it will be more expensive than issuing N (let's say 1000, N from the previous example) separate requests to Redis server.

I also know about separate transaction support. However, this sentence from Redis docs discourages me from using it for parallel processes modifying the set (destructively reading from it):
When using WATCH, EXEC will execute commands only if the watched keys were not modified, allowing for a check-and-set mechanism.

Solution 1

Starting from Redis 3.2, the command SPOP has a [count] argument to retrieve multiple elements from a set.

See http://redis.io/commands/spop#count-argument-extension

Solution 2

Use LRANGE with LTRIM in a pipeline. The pipeline will be run as one atomic transaction. Your worry above about WATCH, EXEC will not be applicable here because you are running the LRANGE and LTRIM as one transaction without the ability for any other transactions from any other clients to come between them. Try it out.

Solution 3

To expand on Eli's response with a complete example for list collections, using lrange and ltrim builtins instead of Lua:

127.0.0.1:6379> lpush a 0 1 2 3 4 5 6 7 8 9
(integer) 10
127.0.0.1:6379> lrange a 0 3        # read 4 items off the top of the stack
1) "9"
2) "8"
3) "7"
4) "6"
127.0.0.1:6379> ltrim a 4 -1        # remove those 4 items
OK
127.0.0.1:6379> lrange a 0 999      # remaining items
1) "5"
2) "4"
3) "3"
4) "2"
5) "1"
6) "0"

If you wanted to make the operation atomic, you would wrap the lrange and ltrim in multi and exec commands.

Also as noted elsewhere, you should probably ltrim the number of returned items not the number of items you asked for. e.g. if you did lrange a 0 99 but got 50 items you would ltrim a 50 -1 not ltrim a 100 -1.

To implement queue semantics instead of a stack, replace lpush with rpush.

Solution 4

Here is a python snippet that can achieve this using redis-py and pipeline:

from redis import StrictRedis

client = StrictRedis()

def get_messages(q_name, prefetch_count=100):
    pipe = client.pipeline()
    pipe.lrange(q_name, 0, prefetch_count - 1)  # Get msgs (w/o pop)
    pipe.ltrim(q_name, prefetch_count, -1)  # Trim (pop) list to new value
    messages, trim_success = pipe.execute()
    return messages

I was thinking that I could just do a a for loop of pop but that would not be efficient, even with pipeline especially if the list queue is smaller than prefetch_count. I have a full RedisQueue class implemented here if you want to look. Hope it helps!

Solution 5

if you want a lua script, this should be fast and easy.

local result = redis.call('lrange',KEYS[1],0,ARGV[1]-1)
redis.call('ltrim',KEYS[1],ARGV[1],-1)
return result

then you don't have to loop.

update: I tried to do this with srandmember (in 2.6) with the following script:

local members = redis.call('srandmember', KEYS[1], ARGV[1])
redis.call('srem', KEYS[1], table.concat(table, ' '))
return members

but I get an error:

error: -ERR Error running script (call to f_6188a714abd44c1c65513b9f7531e5312b72ec9b): 
Write commands not allowed after non deterministic commands

I don't know if future version allow this but I assume not. I think it would be problem with replication.

View more solutions

Comments

[plmw]

Does a redis pipeline guarantee atomicism? I think what you mean is a redis transaction.

[Eli]

pipelining itself without MULTI and EXEC is not, but every Redis library I've ever used has these on by default, and I didn't want to complicate the issue. So, yes, if you're using some odd Redis library where pipelines do not have MULTI and EXEC on by default, you should turn them on.

[Eli]

Why the extra hassle of Lua when you can just do this in a single transaction/pipeline using built-in Redis functions?

[zenbeni]

@Eli because it can be some kind of pessimistic locking, so it is way different to MULTI.

[zenbeni]

Also: you can't use in a multi of many redis requests, the return of one redis query to build the next one. You can easily with LUA.

[Eli]

you're not using the return of one query to build the next. You just LRANGE and then LTRIM on a list. You don't need the results from LRANGE to LTRIM.

[Eli]

And in his case he doesn't need to use WATCH, just EXEC and MULTI, which doesn't need to lock anything, but executes as an atomic operation where it's guaranteed that nothing can possibly happen between LRANGE and LTRIM. redis.io/topics/transactions

[BHSPitMonkey]

This answer ignores the entire basis of the question: "Therefore, when I need first N values from set/list, I need to call the command N-times, which is expensive. Let's say the set/list contains millions of items."

[Philippe T.]

Really, maybe a misunderstanding , but the goal is to get N item from List/set in a command? "Is there a Redis data structure, which would allow atomic operation of popping (get+remove) multiple elements, which it contains?" ... "which would return and remove 1000 random items from set or RPOPM "listName" 1000"... = redis-cli eval "$(cat script.lua)" 1 "listName" 1000

[Justin]

or in "normal" redis, which is perfectly OK for this situation: MULTI; LRANGE key 0 N-1; LTRIM N -1; EXEC;

[Yehosef]

The OP seems to not be interested in using transactions - see the end of the question. But in any event you should add your suggestion as an answer instead of a comment to my answer.

[Emil]

I'm concerned about the following: suppose the list has fewer than 100 members, and you do lrange 0 99 followed by ltrim 100 -1 - the first command will fail, and the second will truncate the list to nothing.

[Eli]

@Emil the first command will not fail. It will return up to 100 members, even if that number is less. See docs here: redis.io/commands/LRANGE#out-of-range-indexes

[Hrishikesh Mishra]

Can you try this redis.call('srem', KEYS[1], unpack(members))

[thom_nic]

Since OP asked for set or list and SPOP only works for set, I added a complete example of how to do this for a list: stackoverflow.com/a/43130793/213983

[Geert-Jan]

You might want to consider changing "pop 4 items off the top of the stack" -> "read 4 items from the head of the stack". 'pop' has the overall meaning to read + delete at once, most of the time from the rear of the structure.

[cppcoder]

You cannot use lrange and ltrim in multi and exec since redis does not support intra-transaction dependency

[Archmede]

Will this block any push operations? Is this a recommended approach while using a Reactive Framework?

[Mickey Hovel]

I hope I can still get an answer... Is there an option to "spop count" from redis list in an atomic way? And in a way that make sure the data is returned from the oldest to the newest. Spop returns random values which might make the oldest data to be handled in a very late stage.

[Gravy]

Im confused about how LTRIM works when there is only 1 member in the list. I can't get LTRIM working when only 1 element is remaining. I think that this answer might be bugged / incomplete. @Eli