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