Service Limitierung mit Bucket4J

REST Services können nur eine gewisse Anzahl von Anfragen innerhalb eines Zeit Fensters verarbeiten. Werden zu viele Anfragen gestellt, dann gerät der Service unter Last und reagiert sehr langsam oder gar nicht mehr. Zusätzliche Anfragen, die ein vorgegebenes Limit übersteigen, sollten daher vom Service abgelehnt werden.

Ein sehr effizienter Mechanismus um die Zahl der Zugriffe zu begrenzen ist der Einsatz eines Token-Buckets. Die Idee dahinter ist recht einfach. Für einen Request wird aus einem Token-Buckets eine gewisse Zahl von Tokens entnommen. Sind nicht mehr genügend Tokens vorhanden, dann wird der Request abgelehnt. Damit der Token-Buckets nicht dauerhaft geleert wird, werden in einem konstanten Strom neue Tokens eingefügt.

Als Beispiel dazu eine Anekdote aus meiner Jugend.

In den 80er Jahren besuchte unsere Schulklasse West-Berlin und wie damals üblich, gehörte ein Besuch in Ost-Berlin dazu. Im Centrum Kaufhaus am Alexanderplatz beobachteten wir eine eigenartige Prozession. Vor der Schuhabteilung stand eine lange Schlange von Neugierigen. Die Schlange entstand, weil sich jeder einen Einkaufkorb nahm, bevor er in die Abteilung verschwanden. Waren alle Einkaufskörbe fort, dann warteten die Menschen. Nach ein paar Minuten kam ein Mitarbeiter und brachte neue Einkaufskörbe, die er vom Ausgang der Schuhabteilung holte. Für uns Schüler aus dem Westen war es damals irritierend, dass niemand ohne Einkaufskorb in die Abteilung ging und außerdem keine Schuhe gekauft wurden.

In dieser Geschichte stand der Stapel Einkaufskörbe für den Token-Bucket und die Kunden für die zu verarbeitenden Request. Der Mitarbeiter sorgte dafür, dass in regelmäßigen Abständen der Token-Bucket wieder gefüllt wurde.

Eine weitere wichtige Eigenschaft des Token-Buckets zeigt sich auch in dem obigen Beispiel. Die Kapazität des Token-Buckets ist begrenzt. Sobald der Token-Bucket gefüllt ist, werden keine neuen Tokens mehr hinzugefügt. Auch im Kaufhaus stellt der Mitarbeiter nur eine maximale Anzahl von Einkaufskörbe vor den Eingang. Genau so viele Einkaufskörbe, wie Kunden gleichzeitig in der Schuhabteilung sein dürfen.

Um einen eigenen REST Service zu limitieren, kann die Bibliothek Bucket4J eingebunden werden.

<dependency>
  <groupId>com.github.vladimir-bukhtoyarov</groupId>
  <artifactId>bucket4j-core</artifactId>
  <version>4.10.0</version>
</dependency>

Ein REST Service kann mit Bucket4J recht einfach limitiert werden, Dazu wird nur ein Filter benötigt, der für jeden Request prüft, ob der Token-Bucket noch genügend Tokens enthält. Reichen die Token nicht mehr, dann liefert der Filter den HTTP Status Code 412 (To Many Requests) zurück. Die hier dargestellte Klasse BucketFilter beinhalten den gesamten notwendigen Code.

public class BucketFilter implements Filter {

  private static final Logger logger = LoggerFactory.getLogger(BucketFilter.class);
  private static final String REMAINING = "X-Rate-Limit-Remaining";
  private static final String RETRY_AFTER_SECONDS = "X-Rate-Limit-Retry-After-Seconds";

  private final Bucket bucket;
  private final ObjectMapper objectMapper;

  public BucketFilter(@Value("${bucket.capacity:20}") int capacity, ObjectMapper objectMapper) {
    this.objectMapper = objectMapper;
    Refill refill = Refill.greedy(capacity, Duration.ofMinutes(1));
    Bandwidth limit = Bandwidth.classic(capacity, refill);
    bucket = Bucket4j.builder().addLimit(limit).build();
  }

  @Override
  public void doFilter(ServletRequest request, ServletResponse response, FilterChain chain)
      throws IOException, ServletException {
    logger.info("bucket filter");
    ConsumptionProbe probe = bucket.tryConsumeAndReturnRemaining(1);
    HttpServletResponse httpResponse = (HttpServletResponse) response;
    if (probe.isConsumed()) {
      httpResponse.setHeader(REMAINING, String.valueOf(probe.getRemainingTokens()));
      chain.doFilter(request, response);
      return;
    }
    String seconds = String.valueOf(NANOSECONDS.toSeconds(probe.getNanosToWaitForRefill()));
    httpResponse.setHeader(RETRY_AFTER_SECONDS, seconds);
    httpResponse.setContentType(MediaType.APPLICATION_JSON_VALUE);
    httpResponse.setStatus(TOO_MANY_REQUESTS.value());
    CustomErrorResponse body = new CustomErrorResponse(TOO_MANY_REQUESTS,
        "Too many requests, retry after " + seconds + "s!");
    httpResponse.getWriter().append(objectMapper.writeValueAsString(body));
  }
}

Im Konstruktor der Klasse wird ein Bucket mit einer Kapazität (20 Token) und einer Füllleistung von 20 Token pro Minute erzeugt.

  public BucketFilter(@Value("${bucket.capacity:20}") int capacity, ObjectMapper objectMapper) {
    this.objectMapper = objectMapper;
    Bandwidth limit = Bandwidth.simple(capacity, Duration.ofMinutes(1));
    bucket = Bucket4j.builder().addLimit(limit).build();
  }

In der doFilter Methode wird für den ServletRequest geprüft, ob ein Token vorhanden ist. Im positiven Fall wird die FilterChain weiter bearbeitet und im negativen Fall eine Antwort mit dem Status Code 429 erzeugt. Die Fehlerantwort nutzt das Resultat der Methode tryConsumeAndReturnRemaining um dem Aufrufer mitzuteilen, wann der Token-Bucket wieder genügend Token enthalten könnte. Wer nicht so hilfsbereit sein möchte, kann stattdessen die Methode tryConsume verwenden.

public void doFilter(ServletRequest request, ServletResponse response, FilterChain chain)
    throws IOException, ServletException {
  HttpServletResponse httpResponse = (HttpServletResponse) response;
  ConsumptionProbe probe = bucket.tryConsumeAndReturnRemaining(1);
  if (probe.isConsumed()) {
    httpResponse.setHeader(REMAINING, String.valueOf(probe.getRemainingTokens()));
    chain.doFilter(request, response);
    return;
  }
  String seconds = String.valueOf(NANOSECONDS.toSeconds(probe.getNanosToWaitForRefill()));
  httpResponse.setHeader(RETRY_AFTER_SECONDS, seconds);
  httpResponse.setContentType(MediaType.APPLICATION_JSON_VALUE);
  httpResponse.setStatus(TOO_MANY_REQUESTS.value());
  CustomErrorResponse body = new CustomErrorResponse(TOO_MANY_REQUESTS,
      "Too many requests, retry after " + seconds + "s!");
  httpResponse.getWriter().append(objectMapper.writeValueAsString(body));
}

Diese einfache Implementierung kann durch die Verwendung zusätzlicher Informationen und mehrerer Token-Buckets eine Reihe weiterer Anwendungsfälle unterstützen.

  • Verwenden verschiedene Kunden einen Dienst, dann sollte es allen Kunden gleichmäßig möglich sein den Dienst zu nutzen. Statt eines Buckets mit einer globalen Limitierung, werden mehrere Buckets mit gleicher Limitierung verwendet. Die Kunden können anhand ihrer IP Adresse, einem HTTP-Header, oder ihrer Anmeldeinformationen unterschieden werden und jeder Kunde erhält seinen eigenen Bucket.
  • Premium-Kunden können bevorzugt werden, indem ihnen ein höheres Limit zugewiesen wird als anderen Kunden. So könnten normale Kunden nur 20 Requests pro Minute ausführen, während Premium-Kunden 60 Requests pro Minute ausführen können.
  • Die Gruppe der angemeldete Nutzer kann ein höheres Limit besitzen als die anonymen Nutzer, damit bei vielen Zugriffen, die angemeldeten Nutzer vorrangig behandelt werden.
  • Abfragen (GET) an einen Server sind in der Regel günstiger als Änderung (PUT) oder Neuerstellung (POST). Im dargestellten Filter wurde nur ein Token pro Request aus dem Token-Bucket gezogen. Je nach HTTP Methode und Endpunkten können aber auch unterschiedlich viele Token gezogen werden. Beispielsweise könnte ein GET zwei Token kosten, während ein PUT schon drei Token und ein POST vier Token kostet.
  • Sparsamere Anfragen, die mit If-Match und If-None-Match arbeiten, können bevorzugt werden, in dem Antworten mit einem HTTP Status Code 304 eine günstiger sind. Bei einer GET Anfrage, die zwei Token kostet, könnte am Ende des Filters, mit der Methode Bucket.addToken ein Token wieder gutgeschrieben werden, wenn der Status Code der Antwort 304 ist. So kosten sparsame GET Anfragen nur die Hälfte.

Darüber hinaus bietet Bucket4J noch mehr interessanter Features, wie die dem Cluster-Einsatz durch Caching Lösungen wie JCache oder Hazelcast oder der Einsatz in Client Anwendungen oder als Scheduler.