#📝 Note: Sliding Window Aggregation
#Overview
A sliding window maintains an aggregate (count, sum, top-K) over a moving time interval — e.g., "tweets in the last 60 minutes." As time advances, old events age out and new events are included, giving a continuously updated view of recent activity.
#Core Idea
#Fixed (Tumbling) Window
- Divides time into non-overlapping, fixed-size buckets (e.g., minute 0–60, 60–120).
- Simple but produces jarring jumps at window boundaries.
- Used when bucket-level granularity is acceptable.
#Sliding Window
- A window that moves continuously. At any moment, includes all events in
[now - W, now]. - Challenge: Efficient expiry of old events without reprocessing everything.
#Bucketed Sliding Window (Approximate)
- Divide window
WintoNequal sub-buckets (e.g., 60-min window → 60 × 1-min buckets). - Keep a circular buffer of bucket counts; drop the oldest bucket when time advances.
- Error bounded by 1/N of the window size.
- This is the standard production approach (used by Twitter, Kafka Streams, Flink).
Window W = 60 min, Bucket B = 1 min, N = 60 buckets
Timeline: [bucket_0][bucket_1]...[bucket_59] ← circular buffer
↑ current
On new minute: drop bucket_0, add bucket_60, recompute total
Aggregation: sum(all active buckets) → O(N) but amortized O(1) per event#Comparison
| Type | Memory | Freshness | Complexity | Use Case |
|---|---|---|---|---|
| Tumbling window | Low | Low (resets at boundary) | O(1) | Billing, batch reports |
| Sliding (exact) | High (store all events) | Perfect | O(events in W) | Low-volume, exact metrics |
| Bucketed sliding | Low (N buckets) | ~1 bucket lag | O(1) amortized | Trending, rate limiting |
| Count-Min + sliding | Very low | ~1 bucket lag | O(d×w) | High-cardinality streams |
#When to Use
- Trending detection: "top hashtags in last 60 min" — bucketed sliding window per geohash or globally.
- Rate limiting: "requests in last 1 second" — sliding window counter per user.
- Anomaly detection: "error rate in last 5 min" — sliding window for rolling error counts.
- Real-time dashboards: Any metric that needs a "recent N minutes" view.
#When NOT to Use
- When absolute precision at exact timestamps is required (use event-log replay instead).
- When the window is very large (days/weeks) and data volume is high — use pre-aggregated batch jobs instead.
#Trade-offs
- Pros: Low memory with bucketed approach; O(1) amortized updates; naturally handles bursty traffic by smoothing counts.
- Cons: Bucketed approach introduces up to 1 bucket of lag; exact sliding windows require storing all events; synchronizing across distributed nodes requires care (event-time vs processing-time).
#Used In This Repo
- Twitter Trends (#27) — 1-min buckets × 60 = 1-hr sliding window for hashtag frequency aggregation
- Rate Limiter (#2) — Sliding window counter for per-user request rate enforcement