educative.io

Educative

How to implement Sliding Window with Counters in Redis

I have checked the Redis that they do have a hash data structure. e.g. key:value -> string(name):HashMap<timestamp, count>.

But redis does not support key auto expiration for the key, i.e. timestamp, in the nested HashMap<timestamp, count>. It only support key exipration for the top level key, that is name here.

Am I understand it correctly? @Design_Gurus

So at best I think we can use a list and passive remove the expired leftmost records to check whether they have live more than 1h. And also compare to the rightmost one to check whether we have excess the quota for 1 min or need to start a new minute.

In order to maintain a total count for an hour, we need another key:value pair in Redis to maintain the count.

While we do the update for a new incoming request, we obsolete the expired records in the left end and subtract the all the expired min_count from the hour_count.

And the we check whether we have excess the hour_count limit.
    if yes, reject.
    if no, continue
        check whether we pass 1 minute by compare with the rightmost record.
            if yes, create a new record and update the new min_count and hour_count
            if no,  check whether we excess the min_count limit 
               if no, update the old min_count in rightmost and hour_count
               if yes, reject