You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@pekko.apache.org by "hanishi (via GitHub)" <gi...@apache.org> on 2025/08/23 01:45:14 UTC
[D] Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation) [pekko]
GitHub user hanishi created a discussion: Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation)
I’ve been thinking of building a cluster-wide, approximate rate limiter using Pekko Distributed Data (PNCounterMap).
**Basic idea**
1. Time-bucketed windows: derive windowId = now / windowMs.
2. Sharding: hash the key (e.g. "ip:1.2.3.4" or "imp|pub|slot") into N buckets → multiple PNCounterMapKeys per window.
2.1 Operation:
- On Allow(key): read counter for this (windowId, bucket).
- If count(key) < capacity → increment and return true.
- Otherwise → return false.
3. Consistency: use ReadLocal / WriteLocal for speed; accept small overshoot under race because state converges via gossip.
4. Rotation / expiration: only keep now and now-1 windows live; stop touching older windows so they naturally expire from gossip (avoid mass per-entry remove() and tombstone buildup).
**Why**
- Designed for things like impression/click throttling in an ad network.
- Goal is best-effort flood control, not strict global counters.
- Avoids external systems (Redis/Kafka). Runs cluster-wide with only DData.
**Questions for the community**
- Has anyone else used this shard + rotate pattern to manage high-cardinality keys with DData?
- Any pitfalls around tombstones or gossip overhead when rotating many CRDT keys per minute/hour?
- Roughly how many concurrent CRDT instances (PNCounterMapKeys) are considered safe in production practice?
GitHub link: https://github.com/apache/pekko/discussions/2053
----
This is an automatically sent email for notifications@pekko.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@pekko.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [D] Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation) [pekko]
Posted by "hanishi (via GitHub)" <gi...@apache.org>.
GitHub user hanishi added a comment to the discussion: Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation)
I’m experimenting with a dedicated project that uses JMH to see how it goes. I will share it when I am done, if anyone is interested.
GitHub link: https://github.com/apache/pekko/discussions/2053#discussioncomment-14199670
----
This is an automatically sent email for notifications@pekko.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@pekko.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [D] Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation) [pekko]
Posted by "He-Pin (via GitHub)" <gi...@apache.org>.
GitHub user He-Pin added a comment to the discussion: Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation)
At $Work, we are using redis/tair to do this. DData may not be suitable for this, because of the latency.
GitHub link: https://github.com/apache/pekko/discussions/2053#discussioncomment-14195943
----
This is an automatically sent email for notifications@pekko.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@pekko.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [D] Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation) [pekko]
Posted by "hanishi (via GitHub)" <gi...@apache.org>.
GitHub user hanishi added a comment to the discussion: Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation)
Thanks for the feedback. Just to clarify — when you'd go with Redis, is it mainly from the perspective of:
• avoiding gossip overhead in DData (lots of deltas flying around), and
• avoiding tombstone/GC buildup when keys churn?
I totally get those concerns. My use case is a bit different (best-effort flood control, approximate limits are fine, and I want to keep the stack self-contained without external Redis), which is why I’m exploring DData. But I want to make sure I understand what you would pick Redis.
GitHub link: https://github.com/apache/pekko/discussions/2053#discussioncomment-14195594
----
This is an automatically sent email for notifications@pekko.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@pekko.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [D] Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation) [pekko]
Posted by "hanishi (via GitHub)" <gi...@apache.org>.
GitHub user hanishi added a comment to the discussion: Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation)
It’s just a simulation harness to see how a DData-based rate limiter could work in practice.
The goal is to observe denial patterns and cleanup behavior.
https://github.com/hanishi/ddata-limiter-simulation
GitHub link: https://github.com/apache/pekko/discussions/2053#discussioncomment-14207377
----
This is an automatically sent email for notifications@pekko.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@pekko.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [D] Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation) [pekko]
Posted by "hanishi (via GitHub)" <gi...@apache.org>.
GitHub user hanishi edited a comment on the discussion: Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation)
[WIP]
https://github.com/hanishi/ddata-limiter-simulation/blob/main/modules/limiter-core/src/main/scala/com/example/bloom/WindowedBloomReplayGuard.scala
You can test it with this!
https://github.com/hanishi/ddata-limiter-simulation/blob/main/modules/limiter-simulation/src/main/scala/com/example/bloom/WindowedBloomReplayGuardDriver.scala
GitHub link: https://github.com/apache/pekko/discussions/2053#discussioncomment-14466937
----
This is an automatically sent email for notifications@pekko.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@pekko.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [D] Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation) [pekko]
Posted by "hanishi (via GitHub)" <gi...@apache.org>.
GitHub user hanishi added a comment to the discussion: Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation)
On second thought, I may not even need cluster-wide rate limiting. Each serve URL is already HMAC-signed and contains a valid-until timestamp. That means: expired URLs are automatically rejected, and replays outside the window can’t pass. So I could just accept impressions/clicks within that short validity window, tolerate duplicates there and rely on probabilistic aggregation downstream for analytics like HLL. This would keep the system much simpler and avoid gossip/tombstone overhead altogether.
Still, it seems interesting to experiment with adding a DData-based limiter on top, just to see how far the shard+rotate pattern can go. Even if it’s not essential, it could be a good case study of DData feasibility under high-churn keys.
GitHub link: https://github.com/apache/pekko/discussions/2053#discussioncomment-14196063
----
This is an automatically sent email for notifications@pekko.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@pekko.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [D] Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation) [pekko]
Posted by "hanishi (via GitHub)" <gi...@apache.org>.
GitHub user hanishi added a comment to the discussion: Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation)
What about Bloom filter based rate limiter? The idea is to implement a distributed rate-limiter and replay-guard without keeping explicit counters, but instead by windowing with Bloom filters: each shard entity manages a current and previous time window, recording whether a given nonce has been seen; if it appears again in the same window it is denied, and anything older than the previous window is automatically rejected. This approach makes grants/denials a function of time-bucketed membership rather than precise counting, and it scales cleanly across a cluster. To survive shard passivation or rebalancing, each entity periodically publishes a compact Bloom snapshot into Pekko DData, so that a new incarnation can immediately warm-start with the recent windows instead of forgetting its history. The result is a fast, memory-efficient limiter that tolerates rebalances and skew while providing strong deduplication semantics.
GitHub link: https://github.com/apache/pekko/discussions/2053#discussioncomment-14345631
----
This is an automatically sent email for notifications@pekko.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@pekko.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [D] Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation) [pekko]
Posted by "hanishi (via GitHub)" <gi...@apache.org>.
GitHub user hanishi edited a comment on the discussion: Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation)
What about Bloom filter based rate limiter? The idea is to implement a distributed rate-limiter and replay-guard without keeping explicit counters, but instead by windowing with Bloom filters: each shard entity manages a current and previous time window, recording whether a given nonce has been seen; if it appears again in the same window it is denied, and anything older than the previous window is automatically rejected. This approach makes grants/denials a function of time-bucketed membership rather than precise counting, and it scales cleanly across a cluster. To survive shard passivation or rebalancing, each entity periodically publishes a compact Bloom snapshot into Pekko DData, so that a new incarnation can immediately warm-start with the recent windows instead of forgetting its history. The result is a fast, memory-efficient limiter that tolerates rebalances and skew while providing strong deduplication semantics. Each shard manages a disjoint partition of the input key-space
(e.g., part = crc32(key) % parts) and therefore holds the dedup state only for its slice.
GitHub link: https://github.com/apache/pekko/discussions/2053#discussioncomment-14345631
----
This is an automatically sent email for notifications@pekko.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@pekko.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [D] Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation) [pekko]
Posted by "He-Pin (via GitHub)" <gi...@apache.org>.
GitHub user He-Pin added a comment to the discussion: Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation)
I think better go with redis
GitHub link: https://github.com/apache/pekko/discussions/2053#discussioncomment-14195138
----
This is an automatically sent email for notifications@pekko.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@pekko.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [D] Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation) [pekko]
Posted by "hanishi (via GitHub)" <gi...@apache.org>.
GitHub user hanishi edited a comment on the discussion: Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation)
Thanks for the feedback. Just to clarify — when you'd go with Redis, is it mainly from the perspective of:
• avoiding gossip overhead in DData (lots of deltas flying around), and
• avoiding tombstone/GC buildup when keys churn?
I totally get those concerns. My use case is a bit different (best-effort flood control, approximate limits are fine, and I want to keep the stack self-contained without external Redis), which is why I’m exploring DData. But I want to make sure I understand why you would pick Redis.
GitHub link: https://github.com/apache/pekko/discussions/2053#discussioncomment-14195594
----
This is an automatically sent email for notifications@pekko.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@pekko.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org
Re: [D] Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation) [pekko]
Posted by "hanishi (via GitHub)" <gi...@apache.org>.
GitHub user hanishi added a comment to the discussion: Rate Limiter Pattern on DData (PNCounterMap with Sharding + Rotation)
[WIP]
https://github.com/hanishi/ddata-limiter-simulation/blob/main/modules/limiter-core/src/main/scala/com/example/bloom/WindowedBloomReplayGuard.scala
GitHub link: https://github.com/apache/pekko/discussions/2053#discussioncomment-14466937
----
This is an automatically sent email for notifications@pekko.apache.org.
To unsubscribe, please send an email to: notifications-unsubscribe@pekko.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: notifications-unsubscribe@pekko.apache.org
For additional commands, e-mail: notifications-help@pekko.apache.org