001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.juneau.rest.server.guard;
018
019import static org.apache.juneau.commons.utils.Shorts.*;
020
021import java.time.*;
022import java.util.*;
023import java.util.function.*;
024
025import org.apache.juneau.http.response.*;
026import org.apache.juneau.rest.server.*;
027
028/**
029 * Token-bucket {@link RestGuard} that throttles requests on a configurable per-request key.
030 *
031 * <p>
032 * On each request the guard atomically attempts to acquire one token from a per-key bucket.  When tokens are
033 * available the request proceeds and three advisory response headers are populated
034 * ({@code X-RateLimit-Limit}, {@code X-RateLimit-Remaining}, {@code X-RateLimit-Reset}).  When the bucket is
035 * empty a {@link TooManyRequests} exception is thrown with a {@code Retry-After} header set to the integer
036 * number of seconds until the next token will be available.
037 *
038 * <h2 class='topic'>Example usage</h2>
039 *
040 * <p class='bjava'>
041 *    <ja>@Rest</ja>(path=<js>"/api"</js>)
042 *    <jk>public class</jk> ApiResource <jk>extends</jk> BasicRestServlet {
043 *
044 *       <jc>// Per-IP rate limit, 100 req/min, 200-burst.</jc>
045 *       <ja>@Bean</ja>(name=<js>"guards"</js>)
046 *       <jk>public</jk> RestGuardList rateLimits(BeanStore <jv>bs</jv>) {
047 *          <jk>return</jk> RestGuardList.<jsm>create</jsm>(<jv>bs</jv>)
048 *             .append(RateLimitGuard.<jsm>create</jsm>()
049 *                .permitsPerMinute(100)
050 *                .burst(200)
051 *                .build())
052 *             .build();
053 *       }
054 *    }
055 * </p>
056 *
057 * <h2 class='topic'>Keying</h2>
058 *
059 * <p>
060 * The default key is the request's {@linkplain RestRequest#getRemoteAddr() remote address}.  Set
061 * {@link Builder#xForwardedForAware(boolean) xForwardedForAware(true)} to honor the first hop of the
062 * {@code X-Forwarded-For} header — required when running behind a trusted reverse proxy.
063 *
064 * <p>
065 * <b>Trusted-proxy assumption.</b>  When {@code xForwardedForAware} is enabled without a trusted proxy in front
066 * of the application, attackers can spoof the {@code X-Forwarded-For} header and defeat the IP-based key.  Only
067 * opt in when the request edge enforces the header.
068 *
069 * <h2 class='topic'>Storage</h2>
070 *
071 * <p>
072 * Bucket state is held by a pluggable {@link Storage} SPI.  The default {@link Storage#inMemory()} implementation
073 * uses an access-ordered map with LRU eviction policy (capped at 100 000 keys by default), suitable
074 * for single-pod deployments.  Distributed deployments should provide a substrate-backed implementation
075 * (e.g. Redis) so per-pod buckets do not split the shared rate envelope.
076 *
077 * <h2 class='topic'>Probe paths</h2>
078 *
079 * <p>
080 * Built-in probe paths ({@code /healthz}, {@code /readyz}, {@code /livez}) are exempted from throttling by
081 * default so a misconfigured limit cannot mask a healthy pod from the orchestrator.  Override via
082 * {@link Builder#exemptPaths(String...)}.
083 *
084 * <h2 class='topic'>Time source</h2>
085 *
086 * <p>
087 * Refill math uses {@link System#nanoTime()}.  This is monotonic and safe across wall-clock jumps but does not
088 * map to a calendar instant, which slightly complicates debugging when the bucket is in an unexpected state.  The
089 * nanosecond source is pluggable on {@link InMemoryStorage} (package-private constructor overload) so tests can
090 * pin the refill window with a deterministic clock instead of racing real wall-clock time; production code always
091 * goes through the single-arg constructor, which defaults to {@code System::nanoTime}.  The wall-clock
092 * {@link BucketState#lastRequest()} instant reported by {@link Storage#snapshot()} is read from a separate
093 * {@link Clock} (default {@link Clock#systemUTC()}), likewise overridable through a package-private constructor.
094 *
095 * <h2 class='section'>See Also:</h2><ul>
096 *    <li class='link'><a class="doclink" href="https://juneau.apache.org/docs/topics/RestServerRateLimitAndRequestId">Rate-Limiting and Request-Id Propagation</a>
097 * </ul>
098 *
099 * @since 10.0.0
100 */
101@SuppressWarnings({
102   "java:S1192", // Duplicate string literals are HTTP header names and rate-limit response field names; intentional
103   "java:S3516" // guard() and isRequestAllowed() always return true by contract; denial is signalled by throwing tooManyRequests
104})
105public class RateLimitGuard extends RestGuard {
106
107   /** Response header name for the advisory ceiling (tokens per refill window). */
108   public static final String HEADER_LIMIT = "X-RateLimit-Limit";
109
110   /** Response header name for the advisory tokens remaining after this call. */
111   public static final String HEADER_REMAINING = "X-RateLimit-Remaining";
112
113   /** Response header name for the advisory seconds until the bucket is fully refilled. */
114   public static final String HEADER_RESET = "X-RateLimit-Reset";
115
116   /** Standard HTTP {@code Retry-After} header name. */
117   public static final String HEADER_RETRY_AFTER = "Retry-After";
118
119   private final int capacity;
120   private final double permitsPerSecond;
121   private final Function<RestRequest,String> keyResolver;
122   private final boolean xForwardedForAware;
123   private final Set<String> exemptPaths;
124   private final BiConsumer<RestRequest,RateLimitInfo> onLimitExceeded;
125   private final Storage storage;
126
127   /**
128    * Constructor.
129    *
130    * @param b The builder configuring this guard.  Must not be <jk>null</jk>.
131    */
132   protected RateLimitGuard(Builder b) {
133      reqnn("builder", b);
134      if (b.permitsPerSecond <= 0.0)
135         throw new IllegalArgumentException("Argument 'permitsPerSecond' must be > 0.");
136      if (b.burst <= 0)
137         throw new IllegalArgumentException("Argument 'burst' must be > 0.");
138      this.capacity = b.burst;
139      this.permitsPerSecond = b.permitsPerSecond;
140      this.keyResolver = b.keyResolver != null ? b.keyResolver : RestRequest::getRemoteAddr;
141      this.xForwardedForAware = b.xForwardedForAware;
142      this.exemptPaths = Set.copyOf(b.exemptPaths);
143      this.onLimitExceeded = b.onLimitExceeded;
144      this.storage = b.storage != null ? b.storage : Storage.inMemory();
145   }
146
147   /**
148    * Creates a new builder.
149    *
150    * @return A new builder.
151    */
152   public static Builder create() {
153      return new Builder();
154   }
155
156   @Override /* Overridden from RestGuard */
157   public boolean guard(RestRequest req, RestResponse res) {
158      if (isExempt(req))
159         return true;
160      var key = resolveKey(req);
161      var result = storage.tryAcquire(key, capacity, permitsPerSecond);
162      var info = new RateLimitInfo(key, capacity, result.remaining(), result.secondsUntilReset(), result.allowed());
163      if (! result.allowed()) {
164         setAdvisoryHeaders(res, info);
165         var retry = Math.max(1L, info.secondsUntilReset());
166         res.setHeader(HEADER_RETRY_AFTER, Long.toString(retry));
167         if (onLimitExceeded != null)
168            onLimitExceeded.accept(req, info);
169         throw tooManyRequests(info);
170      }
171      setAdvisoryHeaders(res, info);
172      return true;
173   }
174
175   @Override /* Overridden from RestGuard */
176   public boolean isRequestAllowed(RestRequest req) {
177      return true;
178   }
179
180   private boolean isExempt(RestRequest req) {
181      if (exemptPaths.isEmpty())
182         return false;
183      var pi = Objects.toString(req.getPathInfo(), "");
184      var sp = Objects.toString(req.getServletPath(), "");
185      return exemptPaths.contains(pi) || exemptPaths.contains(sp);
186   }
187
188   private String resolveKey(RestRequest req) {
189      if (xForwardedForAware) {
190         var xff = req.getHeader("X-Forwarded-For");
191         if (inb(xff)) {
192            var comma = xff.indexOf(',');
193            return (comma < 0 ? xff : xff.substring(0, comma)).trim();
194         }
195      }
196      var k = keyResolver.apply(req);
197      return or(k, "");
198   }
199
200   private static TooManyRequests tooManyRequests(RateLimitInfo info) {
201      var retry = Math.max(1L, info.secondsUntilReset());
202      var ex = new TooManyRequests("Rate limit exceeded for key '%s'. Retry after %ss.", info.key(), retry);
203      ex.setHeader(HEADER_LIMIT, Integer.toString(info.limit()));
204      ex.setHeader(HEADER_REMAINING, "0");
205      ex.setHeader(HEADER_RESET, Long.toString(info.secondsUntilReset()));
206      ex.setHeader(HEADER_RETRY_AFTER, Long.toString(retry));
207      return ex;
208   }
209
210   private static void setAdvisoryHeaders(RestResponse res, RateLimitInfo info) {
211      res.setHeader(HEADER_LIMIT, Integer.toString(info.limit()));
212      res.setHeader(HEADER_REMAINING, Integer.toString(info.remaining()));
213      res.setHeader(HEADER_RESET, Long.toString(info.secondsUntilReset()));
214   }
215
216   /**
217    * Builder for {@link RateLimitGuard}.
218    */
219   public static class Builder {
220
221      private static final Set<String> DEFAULT_EXEMPT_PATHS = Set.of("/healthz", "/readyz", "/livez");
222
223      double permitsPerSecond = 10.0;
224      int burst = 10;
225      Function<RestRequest,String> keyResolver;
226      boolean xForwardedForAware;
227      Set<String> exemptPaths = new LinkedHashSet<>(DEFAULT_EXEMPT_PATHS);
228      BiConsumer<RestRequest,RateLimitInfo> onLimitExceeded;
229      Storage storage;
230
231      /**
232       * Constructor.
233       */
234      protected Builder() {}
235
236      /**
237       * Sets the steady-state refill rate in permits per second.
238       *
239       * @param value Permits per second.  Must be {@code > 0}.
240       * @return This object.
241       */
242      public Builder permitsPerSecond(int value) {
243         permitsPerSecond = value;
244         return this;
245      }
246
247      /**
248       * Sets the steady-state refill rate in permits per minute.
249       *
250       * <p>
251       * Equivalent to {@code permitsPerSecond(value / 60.0)}.
252       *
253       * @param value Permits per minute.  Must be {@code > 0}.
254       * @return This object.
255       */
256      public Builder permitsPerMinute(int value) {
257         permitsPerSecond = value / 60.0;
258         return this;
259      }
260
261      /**
262       * Sets the steady-state refill rate in permits per hour.
263       *
264       * <p>
265       * Equivalent to {@code permitsPerSecond(value / 3600.0)}.
266       *
267       * @param value Permits per hour.  Must be {@code > 0}.
268       * @return This object.
269       */
270      public Builder permitsPerHour(int value) {
271         permitsPerSecond = value / 3600.0;
272         return this;
273      }
274
275      /**
276       * Sets the burst capacity (maximum tokens a bucket can hold).
277       *
278       * @param value Burst capacity.  Must be {@code > 0}.
279       * @return This object.
280       */
281      public Builder burst(int value) {
282         burst = value;
283         return this;
284      }
285
286      /**
287       * Sets the per-request key resolver.
288       *
289       * <p>
290       * Default is {@link RestRequest#getRemoteAddr()}.  Common alternatives include the user-principal name,
291       * an API-key header, or a tenant id.  When the resolver returns <jk>null</jk> the empty string is used.
292       *
293       * @param value Resolver function.  Must not be <jk>null</jk>.
294       * @return This object.
295       */
296      public Builder keyBy(Function<RestRequest,String> value) {
297         reqnn("value", value);
298         keyResolver = value;
299         return this;
300      }
301
302      /**
303       * Enables {@code X-Forwarded-For}-aware key resolution.
304       *
305       * <p>
306       * When enabled, the first comma-separated hop of the {@code X-Forwarded-For} header takes precedence over
307       * the configured {@link #keyBy(Function)} resolver.  Only opt in when a trusted reverse proxy strips and
308       * rewrites the header; otherwise clients can spoof it to defeat IP-based throttling.
309       *
310       * @param value <jk>true</jk> to honor {@code X-Forwarded-For}.
311       * @return This object.
312       */
313      public Builder xForwardedForAware(boolean value) {
314         xForwardedForAware = value;
315         return this;
316      }
317
318      /**
319       * Sets the set of request paths that bypass throttling.
320       *
321       * <p>
322       * Matched against {@link RestRequest#getPathInfo()} and {@link RestRequest#getServletPath()} (exact
323       * match).  Defaults to {@code /healthz}, {@code /readyz}, {@code /livez} — the built-in probe paths.
324       * Pass an empty array to clear the defaults.
325       *
326       * @param values Exempt paths.  Must not be <jk>null</jk>.
327       * @return This object.
328       */
329      public Builder exemptPaths(String...values) {
330         reqnn("values", values);
331         exemptPaths = new LinkedHashSet<>(Arrays.asList(values));
332         return this;
333      }
334
335      /**
336       * Sets a callback invoked when a request is rejected due to an empty bucket.
337       *
338       * <p>
339       * Useful for structured logging or metrics emission.  The callback runs before {@link TooManyRequests} is
340       * thrown and must not block.  Exceptions raised inside the callback propagate to the caller.
341       *
342       * @param value Callback.  Must not be <jk>null</jk>.
343       * @return This object.
344       */
345      public Builder whenLimitExceeded(BiConsumer<RestRequest,RateLimitInfo> value) {
346         reqnn("value", value);
347         onLimitExceeded = value;
348         return this;
349      }
350
351      /**
352       * Sets the bucket-state storage backend.
353       *
354       * <p>
355       * Default is {@link Storage#inMemory()}.  Substitute a distributed backend (Redis, DynamoDB, etc.) when
356       * running multiple pods that share a single rate envelope.
357       *
358       * @param value Storage backend.  Must not be <jk>null</jk>.
359       * @return This object.
360       */
361      public Builder storage(Storage value) {
362         reqnn("value", value);
363         storage = value;
364         return this;
365      }
366
367      /**
368       * Builds the guard.
369       *
370       * @return A new {@link RateLimitGuard}.
371       */
372      public RateLimitGuard build() {
373         return new RateLimitGuard(this);
374      }
375   }
376
377   /**
378    * Snapshot of rate-limit state passed to the {@link Builder#whenLimitExceeded(BiConsumer) onLimitExceeded}
379    * callback and used to populate advisory response headers.
380    *
381    * @param key The per-request key (e.g. remote address, principal name).
382    * @param limit The bucket capacity (also reported as {@code X-RateLimit-Limit}).
383    * @param remaining Tokens remaining after this acquisition attempt.  Zero when the request was rejected.
384    * @param secondsUntilReset Seconds until the bucket is full again (also reported as {@code X-RateLimit-Reset}).
385    * @param allowed <jk>true</jk> if the request was admitted; <jk>false</jk> if the bucket was empty.
386    */
387   public record RateLimitInfo(String key, int limit, int remaining, long secondsUntilReset, boolean allowed) {}
388
389   /**
390    * Point-in-time view of a single token bucket as exposed by {@link Storage#snapshot()}.
391    *
392    * <p>
393    * Used by operator-facing tooling (e.g. {@code AdminMixin}'s {@code /admin/ratelimit} endpoint) to
394    * surface live per-key bucket state alongside the static configuration.  Token-bucket vocabulary
395    * intentionally — there is no discrete refill window because the bucket refills continuously at
396    * {@code permitsPerSecond}, so this record reports the current fill level ({@link #tokens()}), the integer
397    * tokens currently available ({@link #remaining()}), a convenience throttled flag, and the wall-clock instant
398    * of the bucket's last activity.
399    *
400    * @param key The per-request key (e.g. remote address, principal name).
401    * @param tokens The current fractional token count in the bucket.  Continuously refilled at the
402    *    configured {@code permitsPerSecond} rate up to the configured capacity.
403    * @param remaining The integer number of tokens currently available — {@code floor(tokens)}.
404    *    Mirrors the {@code X-RateLimit-Remaining} advisory header.
405    * @param throttled <jk>true</jk> when the bucket is empty enough that the next request would be rejected
406    *    ({@code tokens < 1.0}).  Convenience flag for at-a-glance operator dashboards.
407    * @param lastRequest The wall-clock {@link Instant} at which the bucket was last touched.
408    *
409    * @since 10.0.0
410    */
411   public record BucketState(String key, double tokens, int remaining, boolean throttled, Instant lastRequest) {}
412
413   /**
414    * Returns the bucket capacity (the maximum number of tokens a bucket can hold).
415    *
416    * @return The bucket capacity.
417    * @since 10.0.0
418    */
419   public int getCapacity() {
420      return capacity;
421   }
422
423   /**
424    * Returns the steady-state refill rate in permits per second.
425    *
426    * @return The refill rate.
427    * @since 10.0.0
428    */
429   public double getPermitsPerSecond() {
430      return permitsPerSecond;
431   }
432
433   /**
434    * Returns whether {@code X-Forwarded-For}-aware key resolution is enabled.
435    *
436    * @return <jk>true</jk> if {@code X-Forwarded-For} resolution is enabled.
437    * @since 10.0.0
438    */
439   public boolean isXForwardedForAware() {
440      return xForwardedForAware;
441   }
442
443   /**
444    * Returns the set of request paths that bypass throttling.
445    *
446    * @return The exempt paths.  Never <jk>null</jk>.
447    * @since 10.0.0
448    */
449   public Set<String> getExemptPaths() {
450      return exemptPaths;
451   }
452
453   /**
454    * Returns the bucket-state storage backend in use by this guard.
455    *
456    * @return The storage backend.  Never <jk>null</jk>.
457    * @since 10.0.0
458    */
459   public Storage getStorage() {
460      return storage;
461   }
462
463   /**
464    * Convenience accessor for {@link Storage#snapshot()} on the underlying storage backend.
465    *
466    * <p>
467    * Returns an empty map when the configured {@link Storage} does not override
468    * {@link Storage#snapshot()} (the default behavior for storages — e.g. Redis-backed — that can't cheaply
469    * enumerate every bucket).
470    *
471    * @return A point-in-time map of per-key bucket state.  Never <jk>null</jk>.
472    * @since 10.0.0
473    */
474   public Map<String,BucketState> snapshot() {
475      return storage.snapshot();
476   }
477
478   /**
479    * SPI for storing per-key token-bucket state.
480    *
481    * <p>
482    * Implementations must be thread-safe.  The default {@link #inMemory()} implementation is suitable for
483    * single-pod deployments.  Multi-pod deployments that share a single rate envelope should substitute a
484    * distributed backend.
485    *
486    * @since 10.0.0
487    */
488   public interface Storage {
489
490      /**
491       * Attempts to acquire one token from the bucket associated with the given key.
492       *
493       * @param key The bucket key.  Never <jk>null</jk>.
494       * @param capacity The maximum tokens the bucket can hold.
495       * @param permitsPerSecond The steady-state refill rate.
496       * @return The outcome of the attempt.  Never <jk>null</jk>.
497       */
498      AcquireResult tryAcquire(String key, int capacity, double permitsPerSecond);
499
500      /**
501       * Evicts buckets idle for longer than the given TTL.
502       *
503       * <p>
504       * The default {@link #inMemory()} implementation evicts opportunistically when its size cap is exceeded;
505       * call this method to force an eager sweep (typically from a scheduled task).
506       *
507       * @param ttl The idle threshold.  Buckets last touched longer than {@code ttl} ago are removed.
508       */
509      void evict(Duration ttl);
510
511      /**
512       * Returns a point-in-time view of every per-key bucket currently held by this storage backend.
513       *
514       * <p>
515       * Optional operation for operational visibility.  The default implementation returns an empty map so
516       * that external storage backends (Redis, DynamoDB, etc.) that can't cheaply enumerate every bucket
517       * stay backwards-compatible without code changes.  In-memory implementations <b>SHOULD</b> override
518       * this to expose live bucket state — see the bundled {@link #inMemory()} implementation, which walks
519       * its internal map and returns one {@link BucketState} per entry.
520       *
521       * <p>
522       * The returned map is a snapshot, not a live view — concurrent modifications to the underlying
523       * storage after this method returns are not reflected.  Per-bucket reads are individually consistent
524       * (the in-memory implementation reads each bucket under its own monitor), but the snapshot as a whole
525       * is not a global point-in-time consistent view.
526       *
527       * <p>
528       * <b>Cardinality warning:</b> on storages that hold many buckets (the bundled in-memory storage caps
529       * at 100&nbsp;000 keys by default) the returned map can be large.  Operator-facing callers should
530       * either filter client-side or use a paginated alternative if one is offered by the backend.
531       *
532       * @return A point-in-time map of per-key bucket state, keyed by per-request key.  Never <jk>null</jk>.
533       * @since 10.0.0
534       */
535      default Map<String,BucketState> snapshot() {
536         return Map.of();
537      }
538
539      /**
540       * Creates a new in-memory storage backend with the default size cap (100 000 keys).
541       *
542       * @return A new in-memory storage backend.
543       */
544      static Storage inMemory() {
545         return new InMemoryStorage(100_000);
546      }
547
548      /**
549       * Creates a new in-memory storage backend with a custom size cap.
550       *
551       * @param maxKeys The maximum number of keys held before LRU-style eviction kicks in.  Must be {@code > 0}.
552       * @return A new in-memory storage backend.
553       */
554      static Storage inMemory(int maxKeys) {
555         return new InMemoryStorage(maxKeys);
556      }
557
558      /**
559       * Outcome of a {@link #tryAcquire(String, int, double) tryAcquire} attempt.
560       *
561       * @param allowed <jk>true</jk> if the request was admitted.
562       * @param remaining Tokens left in the bucket after the attempt.
563       * @param secondsUntilReset Seconds until the bucket is full again.
564       */
565      record AcquireResult(boolean allowed, int remaining, long secondsUntilReset) {}
566   }
567
568   /**
569    * Default in-memory {@link Storage} implementation.
570    *
571    * <p>
572    * Backed by an access-ordered {@link LinkedHashMap} keyed by the per-request key.  Each bucket tracks token count
573    * and last touch time.  When the map exceeds {@code maxKeys} entries the least-recently-used bucket is removed
574    * in constant time.
575    */
576   static final class InMemoryStorage implements Storage {
577
578      private final LinkedHashMap<String,Bucket> buckets;
579      private final int maxKeys;
580      private final LongSupplier nanoClock;
581      private final Clock clock;
582
583      InMemoryStorage(int maxKeys) {
584         this(maxKeys, System::nanoTime);
585      }
586
587      /**
588       * Constructor allowing the nanosecond time source to be overridden.
589       *
590       * <p>
591       * Test-only seam.  Production code should always use {@link #InMemoryStorage(int)}, which defaults to
592       * real {@link System#nanoTime()}.  Tests that need to pin the token-bucket refill window regardless of
593       * machine speed can supply a deterministic {@link LongSupplier} here instead of racing {@link Thread#sleep}
594       * against real time.
595       *
596       * @param maxKeys The maximum number of keys held before LRU-style eviction kicks in.  Must be {@code > 0}.
597       * @param nanoClock Supplies the current time in nanoseconds for refill math and idle-eviction bookkeeping.  Must not be <jk>null</jk>.
598       */
599      InMemoryStorage(int maxKeys, LongSupplier nanoClock) {
600         this(maxKeys, nanoClock, Clock.systemUTC());
601      }
602
603      /**
604       * Constructor allowing both the nanosecond and the wall-clock time sources to be overridden.
605       *
606       * <p>
607       * Test-only seam, like {@link #InMemoryStorage(int, LongSupplier)}.  The {@link Clock} only stamps the
608       * {@link BucketState#lastRequest()} instant reported by {@link #snapshot()}; refill and eviction math stay on
609       * {@code nanoClock}.
610       *
611       * @param maxKeys The maximum number of keys held before LRU-style eviction kicks in.  Must be {@code > 0}.
612       * @param nanoClock Supplies the current time in nanoseconds for refill math and idle-eviction bookkeeping.  Must not be <jk>null</jk>.
613       * @param clock Supplies the wall-clock time recorded as each bucket's last-request instant.  Must not be <jk>null</jk>.
614       */
615      InMemoryStorage(int maxKeys, LongSupplier nanoClock, Clock clock) {
616         reqnn("nanoClock", nanoClock, "clock", clock);
617         if (maxKeys <= 0)
618            throw new IllegalArgumentException("Argument 'maxKeys' must be > 0.");
619         this.maxKeys = maxKeys;
620         this.buckets = new LinkedHashMap<>(16, 0.75f, true) {
621            private static final long serialVersionUID = 1L;
622            @Override /* Overridden from LinkedHashMap */
623            protected boolean removeEldestEntry(Map.Entry<String,Bucket> eldest) {
624               return size() > InMemoryStorage.this.maxKeys;
625            }
626         };
627         this.nanoClock = nanoClock;
628         this.clock = clock;
629      }
630
631      @Override
632      public AcquireResult tryAcquire(String key, int capacity, double permitsPerSecond) {
633         Bucket bucket;
634         synchronized (buckets) {
635            bucket = buckets.computeIfAbsent(key, k -> new Bucket(capacity, nanoClock, clock));
636         }
637         return bucket.tryAcquire(capacity, permitsPerSecond);
638      }
639
640      @Override
641      public void evict(Duration ttl) {
642         var threshold = nanoClock.getAsLong() - ttl.toNanos();
643         synchronized (buckets) {
644            buckets.entrySet().removeIf(e -> e.getValue().lastTouchedNanos() < threshold);
645         }
646      }
647
648      @Override
649      public Map<String,BucketState> snapshot() {
650         var out = new LinkedHashMap<String,BucketState>();
651         Map<String,Bucket> copy;
652         synchronized (buckets) {
653            copy = new LinkedHashMap<>(buckets);
654         }
655         for (var e : copy.entrySet()) {
656            var b = e.getValue();
657            var tokens = b.tokens();
658            out.put(e.getKey(), new BucketState(
659               e.getKey(),
660               tokens,
661               (int) Math.floor(tokens),
662               tokens < 1.0,
663               Instant.ofEpochMilli(b.lastWallMillis())
664            ));
665         }
666         return Map.copyOf(out);
667      }
668
669      int size() {
670         synchronized (buckets) {
671            return buckets.size();
672         }
673      }
674   }
675
676   /**
677    * Per-key token-bucket state.
678    *
679    * <p>
680    * Holds a fractional token count and the {@link System#nanoTime()} value of the last touch.  The
681    * {@code synchronized} block keeps the read-refill-write sequence atomic without the overhead of a lock-free
682    * CAS loop on this hot path.
683    */
684   static final class Bucket {
685
686      private double tokens;
687      private long lastNanos;
688      private long lastWallMillis;
689      private final LongSupplier nanoClock;
690      private final Clock clock;
691
692      Bucket(int capacity) {
693         this(capacity, System::nanoTime, Clock.systemUTC());
694      }
695
696      /**
697       * Constructor allowing the time sources to be overridden.
698       *
699       * <p>
700       * Test-only seam — see {@link InMemoryStorage#InMemoryStorage(int, LongSupplier, Clock)}.
701       *
702       * @param capacity The initial (full) token count.
703       * @param nanoClock Supplies the current time in nanoseconds for refill math.  Must not be <jk>null</jk>.
704       * @param clock Supplies the wall-clock time recorded as the last-request instant.  Must not be <jk>null</jk>.
705       */
706      Bucket(int capacity, LongSupplier nanoClock, Clock clock) {
707         this.nanoClock = nanoClock;
708         this.clock = clock;
709         this.tokens = capacity;
710         this.lastNanos = nanoClock.getAsLong();
711         this.lastWallMillis = clock.millis();
712      }
713
714      synchronized Storage.AcquireResult tryAcquire(int capacity, double permitsPerSecond) {
715         var now = nanoClock.getAsLong();
716         var elapsedSeconds = (now - lastNanos) / 1_000_000_000.0;
717         tokens = Math.min(capacity, tokens + elapsedSeconds * permitsPerSecond);
718         lastNanos = now;
719         lastWallMillis = clock.millis();
720         if (tokens >= 1.0) {
721            tokens -= 1.0;
722            return new Storage.AcquireResult(true, (int) Math.floor(tokens), secondsUntilFull(capacity, permitsPerSecond));
723         }
724         return new Storage.AcquireResult(false, 0, secondsUntilFull(capacity, permitsPerSecond));
725      }
726
727      synchronized long lastTouchedNanos() {
728         return lastNanos;
729      }
730
731      synchronized double tokens() {
732         return tokens;
733      }
734
735      synchronized long lastWallMillis() {
736         return lastWallMillis;
737      }
738
739      private long secondsUntilFull(int capacity, double permitsPerSecond) {
740         var needed = Math.max(0.0, capacity - tokens);
741         return (long) Math.ceil(needed / permitsPerSecond);
742      }
743   }
744}