Bugnik
← All problems

11API Gateway Rate Limiter

C++EasyBug fixSuggested time: 60 min

API gateway rate limiter (token buckets, request log CSV)

Sign in to start

Before you start

You'll get more out of this problem if you're comfortable with:

Language

  • Values vs references in C++ (auto x = ... vs auto& x = ...)
  • const member functions and matching declarations in .h and .cpp

Libraries and frameworks

  • std::map lookups with find, emplace and iterators

Build and test tools

  • Reading g++ errors such as "no declaration matches"
  • Running the tests and filtering them by name

Reasoning

  • Converting between milliseconds and seconds
  • The token-bucket rate-limiting algorithm (capacity, refill rate, cost per request)

Background

The Partner Platform team at a large online retailer runs the gateway that sits in front of the public seller APIs. Every partner client is on a plan that limits how fast it may call the APIs, enforced with token buckets. After a refactor of the limiter, partners on the cheapest plan are flooding the order service, and the support dashboard shows them as never being throttled.

How the system works

Configuration

One entry per line, written as key=value words separated by spaces or tabs. Keys are case-insensitive, unknown keys are ignored, and blank lines and lines starting with # are skipped.

plan=starter capacity=3 refill=1
plan=pro capacity=10 refill=5
client=acme-shop plan=pro
  • A line with a client key defines a client: client (the client id) and plan are required. Client ids are case-sensitive.
  • Any other line with a plan key defines a plan: plan (its name), capacity and refill are required. Plan names are case-insensitive and are stored in lower case. capacity and refill are whole numbers from 1 to 1,000,000.
  • A client may name a plan defined further down the file.
  • A word without =, a line that is neither a plan nor a client, a duplicate plan name (in any case), a duplicate client id, or a client on an unknown plan is a ParseError.

Request log

The edge proxy records requests as CSV: timestampMs,clientId,method,path.

timestampMs,clientId,method,path
1000,acme-shop,GET,/v1/items
1250,tiny-store,POST,/v1/orders
  • An optional header row (the first non-blank, non-# line, if it starts with timestamp in any case) is skipped. Blank lines and # lines are skipped. Fields are trimmed.
  • Exactly 4 fields. timestampMs is a whole number of milliseconds (0 or more, at most 15 digits). clientId must not be empty. method is GET, HEAD, POST, PUT or DELETE in any case. path must start with /.
  • Anything else is a ParseError. Rows don't have to be in time order.

Cost: reads (GET, HEAD) cost 1 token; writes (POST, PUT, DELETE) cost 2 tokens.

Token bucket

Each client has one bucket, sized by its plan.

  • A bucket holds at most capacity tokens and refills continuously at refill tokens per second, so 250 ms at refill=2 adds half a token. Partial tokens are kept (the bucket stores thousandths of a token) and add up over later requests.
  • Refilling never takes the bucket above capacity.
  • If the clock goes backwards (a request with an earlier timestamp than the bucket's last update), nothing is added and the bucket's clock stays where it was.
  • A request is allowed when the bucket holds at least its cost (exactly enough is allowed); the cost is then taken out. A denied request takes nothing.
  • tokensAt(t) reports the whole tokens (rounded down) the bucket would hold at time t, without changing it.

The gateway

Gateway::handle(request):

  1. A client id that isn't in the configuration → denied, reason UNKNOWN_CLIENT, remaining 0. Unknown clients get no bucket and no stats.
  2. A client's bucket is created full at the timestamp of its first request.
  3. The bucket refills to the request's timestamp and tries to take the request's cost: allowed with reason OK, or denied with reason RATE_LIMITED.
  4. remaining is the bucket's whole tokens after the request.
  5. Each known client's stats count its allowed and denied requests. A client with no requests has zero counts.

Gateway::replay(log) handles each request in order (state carries over from one request to the next) and returns the number allowed, rate-limited and from unknown clients. When given a vector, it also appends every decision to it in order.

Example (starter: capacity 3, refill 1/s): a POST at 0 ms is allowed (1 token left); a POST at 100 ms is rate-limited (1.1 tokens); a PUT at 1100 ms is allowed (2.1 tokens before, 0.1 after).

Project structure

include/
  util.h          ParseError, trim / toLower / split / splitWords, number parsing
  config.h        Plan, Config (plans and clients), configuration parser
  request_log.h   Method, Request, request cost, request log CSV parser
  token_bucket.h  TokenBucket (refill, consume, tokensAt)
  gateway.h       Decision, ClientStats, ReplaySummary, Gateway
src/              implementations of the above
tests/            unit tests (testlib.h is the test framework, runner.cpp the entry point, fixtures.h shared data)

Your task

Partners and the support team have reported problems since the limiter refactor:

  • The project no longer builds.
  • A client that has used up its whole bucket is allowed again a few milliseconds later instead of waiting for tokens to refill.
  • Partners can send bursts far bigger than their plan's capacity, and their throttled-request counter on the dashboard stays at 0.

Find and fix the defects so that all tests pass.

  • Do not modify files in tests/.
  • Keep your changes minimal. Fix the defects; don't rewrite modules.
  • Additional hidden tests check the behaviour described in this README.