Advanced Redis Use Cases

Active users of a web application

Here we need to clarify what is an “active user” first: an active user is a logged-in user which has interactions with a web application recently. Web applications using http(s) protocal are stateless, so here “recently” has to be estimated and inaccurate: e.g., if we reckon a user is not active in our website until the last request he sent was 30 seconds ago, “recently” can be defined as a const variable of 30. The following solution needs zadd() and zcount() support:

Trigger zadd() for each logged-in user’s request:

zadd("active_users", <CURRENT_TIMESTAMP>, <USER_ID>)

Invoke zcount() to calculate active users with the estimated parameter <RECENTLY>:

zcount("active_users", <CURRENT_TIMESTAMP> - <RECENTLY>, <CURRENT_TIMESTAMP>)

Pros:
– The time complexity of zadd() and zcount() is O(log(N)) in sorted set.
– Additionally, we can also get the last active time of a logged-in user by invoking zrank() of which time complexity is O(log(N)).

Cons:
– Relatively large cost of memory.
– The expired records need to be removed by cron tasks or asynchronous jobs.

Consecutive check-in users for the last 3 days

Invoke setbit in our check-in API, here N in key check_in_day_N is the date(with any format) user checked-in:

setbit("check_in_day_N", <USER_ID>, 1)

Invoke bitop and with keys of the last 3 days, the total number of “1”s in return value is the total number of consecutive check-in users for the last 3 days:

bitop("and", "check_in_day_1", "check_in_day_2", "check_in_day_3")

Additionally, invoke bitop or with the 3 keys above, we can also get the total number of how many user checked-in for the last 3 days:

bitop("or", "check_in_day_1", "check_in_day_2", "check_in_day_3")

A lightweight rate limiter

This rate limiter contains two parts: a fixed window policy and a sliding window policy.

The fixed window policy maintains a key-value pair represents how many requests we received within a fixed period of time. e.g., the fixed window policy of 10 seconds can be easily described as <CURRENT_TIMESTAMP> / 10 => <COUNTER>.

The sliding window policy is a bit more complicated: we need to sum up recent N fixed window’s value and compare the result with our sliding window policy.

The following picture shows a rate limiter with a fixed window policy of 100 requests / 10 seconds and a sliding window policy of 600 requests / 50 seconds:

Here we use hashes to implement a sliding window, when a request is received, we increase the fixed window:

HINCRBY <USER_ID> <FIXED_WINDOW> 1

And fetch current fixed window size:

HGET <USER_ID> <FIXED_WINDOW>

If fixed window size is larger than the fixed window policy allows, current request would fail. Otherwise, we move to sliding window policy:

HMGET <USER_ID> <FIXED_WINDOW_1> <FIXED_WINDOW_2> ... <FIXED_WINDOW_N>

Similarly, if the sliding window size is larger than the sliding window policy allows, current request would fail.

Priority Queue

A Simple Priority Queue can be implemented by Sorted Sets.

  • Add some hackers:
127.0.0.1:6379[<span data-mce-type="bookmark" style="display: inline-block; width: 0px; overflow: hidden; line-height: 0;" class="mce_SELRES_start"></span>10]> zadd hackers 1940 "Alan Kay"
(integer) 1
127.0.0.1:6379[10]> zadd hackers 1957 "Sophie Wilson"
(integer) 1
127.0.0.1:6379[10]> zadd hackers 1953 "Richard Stallman"
(integer) 1
127.0.0.1:6379[10]> zadd hackers 1949 "Anita Borg"
(integer) 1
127.0.0.1:6379[10]> zadd hackers 1965 "Yukihiro Matsumoto"
(integer) 1
127.0.0.1:6379[10]> zadd hackers 1914 "Hedy Lamarr"
(integer) 1
127.0.0.1:6379[10]> zadd hackers 1916 "Claude Shannon"
(integer) 1
127.0.0.1:6379[10]> zadd hackers 1969 "Linus Torvalds"
(integer) 1
127.0.0.1:6379[10]> zadd hackers 1912 "Alan Turing"
(integer) 1
  • Get the list of hackers ordered by their age:
127.0.0.1:6379[10]> zrange hackers 0 -1
1) "Alan Turing"
2) "Hedy Lamarr"
3) "Claude Shannon"
4) "Alan Kay"
5) "Anita Borg"
6) "Richard Stallman"
7) "Sophie Wilson"
8) "Yukihiro Matsumoto"
9) "Linus Torvalds"
  • Remove the youngest hacker:
127.0.0.1:6379[10]> ZREVRANGE hackers 0 0
1) "Linus Torvalds"
127.0.0.1:6379[10]> ZREM hackers "Linus Torvalds"
(integer) 1
  • Re-check the list:
127.0.0.1:6379[10]> zrange hackers 0 -1
1) "Alan Turing"
2) "Hedy Lamarr"
3) "Claude Shannon"
4) "Alan Kay"
5) "Anita Borg"
6) "Richard Stallman"
7) "Sophie Wilson"
8) "Yukihiro Matsumoto"

Leave a Reply

Your email address will not be published. Required fields are marked *

*