Per-user rate limiter

Design a simple per-user API rate limiter for a small backend, say, allow each user 100 requests per minute, returning HTTP 429 when they exceed it. The backend runs as a couple of app instances behind a load balancer, so a user's requests can land on different instances. Cover the algorithm, where the counters live, and what happens when the limit is hit.