Moving window (Rolling counters) in Redis, LUA and NodeJS
This tutorial explains how to implement simple moving window (rolling counter) in NodeJS and Redis. We will use sorted sets to count every request and then will show another approach.
We will count number of hits made in 24 hours. You can easily modify it to show weekly and monthly statistics.
At first install Redis and Redis-scripto modules as described in previous article.
Create demo.js. It runs simple-counter.lua and prints result which adds one hit to zset and returns number of hits made in last 24 hours as of running.
It just adds one timestamp to the stat:hits sorted set, removes old timestamps and returns total count.
You can notice that score and value are both a timestamp
That leads to incorrect results in case of two requests made simultaneously. Indeed, timestamps will be the same and only one result will be stored in sorted set. To fix it, we need to use some unique value.
For simplicity, we can use some Redis key as a counter and just increment it with every request. Modify simple-counter.lua:
Here we used stat:counter as a unique value.
What if we don’t need stats per second and are only interested in minutes? We can save some memory by doing this
Or if we need hours:
Modify simple-counter.lua accordingly.
If your site has millions of hits, removing and counting sorted sets might become an expensive operation. If you don’t need each individual hit information (you may want to store user’s request url, ip address and other information), you can use just several integer keys and let Redis expire and remove old ones.
Since there are only 24 hours, we can create 24 keys and store hits for each hour of the day accordingly. But then we can’t make it moving, as we need all 24 keys to get stats and we can’t delete ‘old’ ones.
To fix it, let’s pretend that there are 25 hours a day (timestamp in hours modulo 25). We will write hits to each one (of 25) continuously, but use only 24 last ones to get total. With each write we ask Redis to expire current hour key in 86400 seconds (24h).
Since we have 25 hours and each key expires in 24 hours, the least written one (that was 25 hours ago) will be removed by Redis. We will start counting from zero when we get to it again.
Thus we have the moving window (rolling counter).
Actually my spouse proposed another way of doing the same thing which might be more intuitive. We can use 24 keys and a flag (another key) indicating current hour we are writing to. When current hour changes, set corresponding hour stat to zero. Redis is single threaded and we won’t get any race conditions, like setting a flag multiple times.
Since we don’t need to expire anything, we can use Redis hashes.