CODEWITHSUNDEEP
pythonalgorithmredisleaderboard
user1629366
user1629366

Reputation: 2011

Redis getting sets of user around a given score

I am using redis to implement the leaderboard. The problem statement I am addressing is - given a user, get five users above him, and five users below him in the leaderboard.

Following is the approach, that I have taken, please let me know, if it is optimal, or something better can be done:

1. lower_key = zrank('set_name', 'member_name') // get the position of the user in the set
2. higer_key = zcard('set_name') // the total no. of elements in the leaderboard
3. low = max(0, lkey-5) // edge-case if user rank is less than 5.
4. high = min(key+5, higher_key) // edge-case if user rank lies is top-5
5. zrange('set_name', low, high) // get the range between the intervals. 

zrank is O(log(N))
zcard is O(1)
zrange step is O(log(N)+M)

Is there a better way to perform this operation?

EIDT : One of the answer mentioned about too much of back and forth switching, hence I added a pipeline, please have a look at the implementation - 

pipeline = self.redis_connection.pipeline()
lkey = pipeline.zrank(leaderboard_name, member)
hkey = pipeline.zcard(leaderboard_name)
inter = int(self.DEFAULT_PAGE_SIZE)/2
low = max(0, key-inter)
high = min(key+inter, hkey)
pipeline.zrange(leaderboard_name, low, high)
return pipeline.execute()

Please let me know your thoughts.

Upvotes: 2

Views: 1129

Answers (1)

Eli
Eli

Reputation: 38949

So, your current approach is fine and works (aside from the typos in the variable names), but requires a lot of back and forth between your client and your redis server, and that's usually where Redis' bottleneck ends up. The back and forth in your case is unnecessary, as you can actually do everything in a single LUA script that you then run as a Redis command from your client. Everything is done on the Redis server then, and there's only one back and forth instead of the 3 in your case.

Here's how I would do it in LUA (untested):

local key_idx = redis.call("ZRANK", KEYS[1], ARGV[1])
local card_idx = redis.call("ZCARD", KEYS[1])
local low_idx = math.max(0, key_idx-5)
local high_idx = math.min(key_idx+5, card_idx)
local return_arr = redis.call("ZRANGE", KEYS[1], low_idx, high_idx)
return return_arr

You'd then call this from redis as:

redis-cli eval "$(cat ./myscript.lua)" 1 sorted_set_name, member_name

Upvotes: 1

Related Questions