# Sliding window rate limits in distributed systems

[Grab](https://yomu.fyi/company/grab) · Naveen Kumar Jakuva Premkumar · Dec 14, 2023

**Type:** Problem & solution

## Summary

Marketing communications across Grab's user base risked causing notification overload and consent revocations. To enforce personalized daily and weekly frequency caps across more than 270 million users, the team addressed segment membership storage and communication rate limiting. They adopted roaring bitmaps instead of Bloom filters to compactly store user segment data without hash collisions or costly rebuilds upon deletion. For frequency capping, they chose Amazon ElastiCache for Redis over DynamoDB, executing a sliding log rate limiting algorithm directly on the cluster using Lua scripts and sorted sets. Timestamps are stored as sorted set scores, and historical data is cleaned up via eviction ranges to prevent unbounded memory growth.

## Context

High volumes of marketing communications risked causing notification fatigue and consent revocations among Grab's user base of over 270 million users.

## Approach / What changed

Grab paired roaring bitmaps for memory-efficient user segmentation storage with a Redis-backed sliding log rate limiter using Lua scripts and sorted sets to enforce daily and weekly frequency caps.

## Takeaways

- Roaring bitmaps avoided the hash collisions and lack of deletion support found in Bloom filters while dynamically compressing user segment sets across sparse and dense distributions.
- A sliding log rate limiter was chosen over a fixed sliding window to prioritize rate limiting accuracy, using Redis sorted sets with timestamp scores to count communications in O(log n) time.
- Because Redis sorted sets do not natively support per-entry TTLs, historical records are pruned by passing an eviction timestamp into the Lua script using the zremrangebyscore command.

**Tags:** [Architecture](https://yomu.fyi/topic/architecture), [Caching](https://yomu.fyi/topic/caching), [Performance](https://yomu.fyi/topic/performance), [Redis](https://yomu.fyi/topic/redis), [Scalability](https://yomu.fyi/topic/scalability)

[Read original post](https://engineering.grab.com/frequency-capping)