227. Design Rate Limit Circuit Breaker

Design Rate Limit Circuit Breaker

Design a circuit breaker that protects a service when too many requests arrive in a short time. This circuit breaker opens based on the number of requests, not the number of failed requests.

The breaker has three states: CLOSED, OPEN, and HALF_OPEN. Requests are accepted only when the current state allows them.

Method Signatures

Constructor

CircuitBreaker(int requestLimit, int windowSeconds, int openSeconds)

Initializes the circuit breaker in CLOSED state.
requestLimit is the maximum number of accepted requests allowed inside one sliding time window.
windowSeconds is the sliding window size in seconds.
openSeconds is the number of seconds the breaker stays OPEN before becoming HALF_OPEN.

Handle Request

String handleRequest(int timestampSeconds)

Processes one incoming request at timestampSeconds.
Returns "ALLOWED,state" if the request is accepted.
Returns "REJECTED,state" if the request is rejected.
The returned state is the effective state before processing the request.

Get State

String getState(int timestampSeconds)

Returns the current effective state at timestampSeconds.
This method does not record a request.

State Rules

CLOSED

Only accepted requests are counted.
At timestamp t, the active sliding window contains accepted request timestamps x such that t - windowSeconds < x ≤ t.
For each request, remove accepted request timestamps outside the active sliding window.
If fewer than requestLimit accepted requests remain in the window, accept the new request and keep the breaker CLOSED.
If accepting the new request would exceed requestLimit, reject it and move the breaker to OPEN.
Multiple accepted requests with the same timestamp are counted as separate accepted requests.
Rejected requests are not added to the sliding window.

OPEN

All requests are rejected while the breaker is OPEN.
After openSeconds seconds have passed since the breaker opened, the effective state becomes HALF_OPEN.

HALF_OPEN

The first request in HALF_OPEN is accepted as a probe request.
After accepting this probe request, the breaker moves to CLOSED and starts a new request window containing only this probe request.

Deterministic Behavior

Requests are processed in the order method calls are received.
If multiple calls have the same timestamp, their call order decides the result.
The output must always be deterministic.
Before processing any public method call, the breaker first computes the effective state for the given timestamp.

Constraints

1 ≤ requestLimit ≤ 1,000,000
1 ≤ windowSeconds ≤ 1,000,000,000
1 ≤ openSeconds ≤ 1,000,000,000
0 ≤ timestampSeconds ≤ 1,000,000,000
Calls to handleRequest and getState use non-decreasing timestamps.
No parameter value will be null.

Examples

Example 1

CircuitBreaker(requestLimit = 3, windowSeconds = 10, openSeconds = 5)

handleRequest(timestampSeconds = 1) returns "ALLOWED,CLOSED"

handleRequest(timestampSeconds = 2) returns "ALLOWED,CLOSED"

handleRequest(timestampSeconds = 4) returns "ALLOWED,CLOSED"

handleRequest(timestampSeconds = 5) returns "REJECTED,CLOSED"

getState(timestampSeconds = 7) returns "OPEN"

getState(timestampSeconds = 10) returns "HALF_OPEN"

handleRequest(timestampSeconds = 10) returns "ALLOWED,HALF_OPEN"

getState(timestampSeconds = 10) returns "CLOSED"

The fourth request at time 5 is checked while the effective state is CLOSED. It would exceed the request limit inside the sliding window, so it is rejected and the breaker opens. At time 10, the open duration has passed, so the effective state is HALF_OPEN and one probe request is allowed.

Example 2

CircuitBreaker(requestLimit = 2, windowSeconds = 5, openSeconds = 3)

handleRequest(timestampSeconds = 1) returns "ALLOWED,CLOSED"

handleRequest(timestampSeconds = 3) returns "ALLOWED,CLOSED"

handleRequest(timestampSeconds = 6) returns "ALLOWED,CLOSED"

handleRequest(timestampSeconds = 7) returns "REJECTED,CLOSED"

At time 6, the active sliding window is (1, 6], so the request at time 1 is outside the active window. Therefore, the request at time 6 is accepted. At time 7, the active sliding window contains the accepted requests at times 3 and 6. Accepting another request would exceed the limit, so the request is rejected and the breaker opens.

Example 3

CircuitBreaker(requestLimit = 2, windowSeconds = 10, openSeconds = 4)

handleRequest(timestampSeconds = 100) returns "ALLOWED,CLOSED"

handleRequest(timestampSeconds = 100) returns "REJECTED,CLOSED"

Calls with the same timestamp are processed in method call order. The third request is checked while the effective state is CLOSED, but accepting it would exceed the limit, so it is rejected and the breaker opens.