Class WindowLimiter
java.lang.Object
org.frontcache.guard.ratelimit.WindowLimiter
Fixed-window request counter: how many requests one key sent inside the current measurement slot.
The window is a slot on a fixed grid - slot
w covers
[w * windowMillis, (w+1) * windowMillis) - so a key's count resets when the slot rolls
over. There is no per-key timer, no sweeper and no expiry list: a slot id that no longer matches
IS the reset, which is what keeps per-key state down to two numbers.
Storage
The key space is attacker-chosen and unbounded, so a map keyed by client address is a memory-exhaustion primitive that then needs a cap, an eviction policy and a sweeper thread. This is instead one fixedAtomicLongArray, allocated once, with each key's state packed into a
single long:
value = (tag << 44) | (windowId << 20) | count
20 bits 24 bits 20 bits
so an update is a single CAS and tag, window and count can never be torn apart. windowId
is compared for equality only, never ordered, so its wrap after 2^24 windows (5.3 years at a 10s
window) is harmless. count saturates rather than overflowing into windowId - a
key at a million requests in one window is long since limited.
Collisions
Two keys landing in the same array slot with different tags: the arriving one takes the slot over and starts a fresh count. This is the failure direction that matters - a takeover never lets a visitor inherit a foreign, exhausted count, so no attacker can get a chosen victim limited by brute-forcing keys that collide with them. The cost of undersizing is therefore under-counting, visible as a rising takeover rate, and never a false rejection. Never throws, and fails open: CAS contention beyond a couple of retries returns "allowed".-
Field Summary
FieldsModifier and TypeFieldDescriptionstatic final longSet incheckAndCountFlagged(long, long)'s answer on the request that took a key over the limit - the first refused one of its window.static final inthighest limit the packed count can still distinguish from saturation -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionlongcheckAndCount(long keyHash, long nowMillis) Counts one request forkeyHashand says whether it is over the limit.longcheckAndCountFlagged(long keyHash, long nowMillis) checkAndCount(long, long), withFIRST_OVER_LIMITset on the one request per key and window that crossed the limit - what makes "a client went over" an event that happens once, not once per refused request.intgetLimit()longClients that went over the limit since this limiter was created, each counted once per window.intlonglongstatic long64-bit mix of bucket name and key.static longtoString()
-
Field Details
-
MAX_LIMIT
public static final int MAX_LIMIThighest limit the packed count can still distinguish from saturation- See Also:
-
FIRST_OVER_LIMIT
public static final long FIRST_OVER_LIMITSet incheckAndCountFlagged(long, long)'s answer on the request that took a key over the limit - the first refused one of its window. Far above any window's millis, so masking it off leaves the Retry-After.- See Also:
-
-
Constructor Details
-
WindowLimiter
- Parameters:
slotCount- number of array slots; rounded up to a power of two by the caller
-
-
Method Details
-
nowMillis
public static long nowMillis() -
checkAndCount
public long checkAndCount(long keyHash, long nowMillis) Counts one request forkeyHashand says whether it is over the limit.- Parameters:
keyHash- 64-bit mix of bucket name and key (seehash(String, String))nowMillis- monotonic millis, fromnowMillis()- Returns:
- 0 when the request is within the limit, otherwise the millis remaining until the current window rolls over (i.e. the Retry-After the client should be told)
-
checkAndCountFlagged
public long checkAndCountFlagged(long keyHash, long nowMillis) checkAndCount(long, long), withFIRST_OVER_LIMITset on the one request per key and window that crossed the limit - what makes "a client went over" an event that happens once, not once per refused request. -
hash
64-bit mix of bucket name and key. FNV-1a for the bytes, then a murmur3 finalizer so that the array index (low bits) and the collision tag (high bits) are independent of each other - a tag taken from bits that also drive the index would add no discrimination at all. -
getBucket
-
getLimit
public int getLimit() -
getWindowMillis
public long getWindowMillis() -
getSlotCount
public int getSlotCount() -
getTakeovers
public long getTakeovers()- Returns:
- how often an arriving key has taken a slot from a different key. Climbing steadily means the slot array is undersized for the traffic.
-
getOverLimitCount
public long getOverLimitCount()Clients that went over the limit since this limiter was created, each counted once per window. -
toString
-