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 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}