Class WindowLimiter

java.lang.Object
org.frontcache.guard.ratelimit.WindowLimiter
public class WindowLimiter extends Object
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 fixed AtomicLongArray, 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 Details

    • MAX_LIMIT

      public static final int MAX_LIMIT
      highest limit the packed count can still distinguish from saturation
      See Also:

  • Constructor Details

    • WindowLimiter

      public WindowLimiter(String bucket, int limit, long windowMillis, int slotCount)
      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 for keyHash and says whether it is over the limit.
      Parameters:
      keyHash - 64-bit mix of bucket name and key (see hash(String, String))
      nowMillis - monotonic millis, from nowMillis()
      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)

    • hash

      public static long hash(String bucket, String key)
      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

      public String 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.

    • toString

      public String toString()
      Overrides:
      toString in class Object