This tweet got remind me on the wonderful Redis sorted/ordered set

Ordered sets in redis#

Everyone prbably here knows that redis is a key value in memory datastore, used for faster accessing our data. ordered sets in redis are nothing different than a key value pair, where the value is a collection of member and a score, below is how u can imagine a typical redis sorted set will be stored.

Key: rate_limit:1.2.3.4#

member | score#

req-1 | 100 req-2 | 103 …

The members are ordered primarily with their score in asc order, if multiple members have the same score, then they are ordered lexicographically by the member value.

Internally redis uses skip list while adding/removing members to maintain the order, refer this video for skip list.

Commands#

Below are some of the useful/important commands that used in real time.

  • ZADD - use to add a member and score to the key. EG: ZADD req_info 9:00:00 req-1 [ZADD KEY SCORE MEMBER]
  • ZRANGE - use to list all the members in ascending order. EG: ZRANGE req_info 0 -1 [ZRANGE KEY START_INDEX END_INDEX] here 0 -1 means from 0th element to last.
  • ZRANK - use to get the rank of the passing member. EG: ZADD req_info 9:00:00 req-1 [ZADD KEY SCORE MEMBER] ZADD req_info 9:00:02 req-2 [ZADD KEY SCORE MEMBER] ZRANK req_info “req-2”[ZRANK KEY MEMBER] => outputs 2

Rate limit usecase#

When i was in 4th year of my career, i had used this magical stuff for one of my organization to rate limit our external API’s Don’t ask me why u did rate limiting all by urself instead of third party libraries or cloud solution, i dont know :(, nevertheless its good for me our original ratelimit architecture was way more complex involving many things, but at the core redis ordered set was the one powering all these.

Here is a simpler version of the same in go. btw my original implementation was on node, since am fond of go recently, example follows the same below is a simple psuedo code version in go, which almost does the job.

package ratelimiter

type RateLimiter struct {
	rdb   *redis.Client
	limit int
	window time.Duration
}

func (rl *RateLimiter) IsAllowed(user string) bool {
    // here our score would be the timestamp and member would be the unique id
    // key would be rate_limit:$USER_IP

	now := time.Now().UnixMilli()
	windowStart := now - rl.window.Milliseconds()

	KEY := fmt.Sprintf("rate_limit:%s", user)

    // removes all members in the set within the min and max keyframe
	REDIS_CLIENT.ZREMRANGEBYSCORE(KEY, "0", fmt.Sprintf("%d", windowStart))

    // add new score with member
    REDIS_CLIENT.ZADD(KEY, {
        Score: now,
        Member: uuid()
    })

    // fetch total member
	totalMemberWithinLimit := ZCARD(KEY)

    EXPIRE(KEY, rl.window+1*time.Minute)

	return totalMemberWithinLimit <= int64(rl.limit)
}

Explanation: consider we have to rate limit our application by 3req per ip per minute, in this case our RateLimiter struct would become

rl := RateLimiter {
    limit: 3
    window: 1*time.Minute
}
// now consider we are getting 5requests with t1(100) t2(103) t3(106) t4(109) t5(1011), consider our window is 100
// req-1 t1(100) ip 1
// our redis will have
// remove: now - window (100 - 100) => remove 0, 0 => nothing satisfied
// KEY: rate_limit:1 members: [[UNIQ_1, 0]]
// returns totalMemberWithinLimit <= rl.limit -> 1 <= 3 -> true
// req-2 t2(103) ip 1
// remove: now - window (103 - 100) => remove 0, 3 => nothing satisfied
// KEY: rate_limit:1 members: [[UNIQ_1, 100], [UNIQ_2, 103]]
// returns totalMemberWithinLimit <= rl.limit -> 2 <= 3 -> true
// req-3 t3(106) ip 1
// remove: now - window (106 - 100) => remove 0, 6 => nothing satisfied
// KEY: rate_limit:1 members: [[UNIQ_1, 100], [UNIQ_2, 103], [UNIQ_3, 106]]
// returns totalMemberWithinLimit <= rl.limit -> 3 <= 3 -> true
// req-4 t4(109) ip 1
// remove: now - window (109 - 100) => remove 0, 9 => nothing satisfied
// KEY: rate_limit:1 members: [[UNIQ_1, 100], [UNIQ_2, 103], [UNIQ_3, 106], [UNIQ_4, 109]]
// returns totalMemberWithinLimit <= rl.limit -> 4 <= 3 -> false -> request blocked
// same req-4 trying after sometime t5(205) ip 1
// remove: now - window (205 - 100) => remove 0, 105 => satisfied UNIQ_1, UNIQ_2 are deleted now
// KEY: rate_limit:1 members: [[UNIQ_3, 106], [UNIQ_4, 205]]
// returns totalMemberWithinLimit <= rl.limit -> 2 <= 3 -> true

// this is how rate limiting can be implemented without any application state involved using ordered set in redis

NOTE: Still this pseudo code is not a production grade one, lot of things i didn’t considered here like race condition( what if two request arrive at the exactly same time for the same ip), expiration for the key, its not atomic if u carefully look at the code etc.

This code just provides u a high level understanding of how powerful redis ordered sets are with a practical use-case of rate limiter, there are lot more use-cases as well like leaderboard, even u can build your own hackernews kinda site with ranking algorithm which could be implemented using this.