How the Token Bucket Algorithm Is Implemented and Configured in SDS

The SDS token bucket algorithm uses a sliding-window counter to generate tokens each second, evaluates requests against configured generation rates and bucket capacity in TokenBucketStrategyExecutor, and exposes tunable parameters through the SdsStrategy configuration model.

SDS (Service Degrade System) implements a token bucket algorithm to enforce precise rate limits and protect downstream services from traffic spikes. According to the didi/sds source code, the implementation combines a sliding-window token generator, a strategy executor for admission control, and a centralized configuration system managed through the SDS admin console or REST API.

Core Architecture and Components

The token bucket implementation consists of three primary components that handle generation, execution, and configuration.

TokenBucketData – Token Generation and Storage

The TokenBucketData class in sds-client/src/main/java/com/didiglobal/sds/client/counter/TokenBucketData.java serves as the data holder that generates tokens using a sliding-window approach. It creates a SlidingWindowData instance to track token distribution across time buckets:

private AbstractCycleData cycleTokenBucketData = new SlidingWindowData(
        BizConstant.CYCLE_NUM, BizConstant.CYCLE_BUCKET_NUM, BizConstant.BUCKET_TIME);

Each second, the algorithm generates a fixed number of tokens defined by the configuration. The takeOneToken(long time) method increments the counter for the current time bucket and returns the total tokens consumed in that second:

VisitWrapperValue visitWrapperValue = cycleTokenBucketData.incrementAndGet(time);
return visitWrapperValue.getBucketValue();

TokenBucketStrategyExecutor – Admission Control Logic

The TokenBucketStrategyExecutor class in sds-client/src/main/java/com/didiglobal/sds/client/strategy/executor/TokenBucketStrategyExecutor.java implements the core decision logic. Its strategyCheck method evaluates whether a request should proceed or be downgraded based on the current bucket state and historic token availability.

SdsStrategy and Admin API – Runtime Configuration

The SdsStrategy bean in sds-client/src/main/java/com/didiglobal/sds/client/bean/SdsStrategy.java exposes two critical parameters: tokenBucketGeneratedTokensInSecond (the generation rate) and tokenBucketSize (the bucket capacity). The admin controller in sds-admin/src/main/java/com/didiglobal/sds/admin/controller/PointStrategyController.java validates and persists these values, defaulting missing fields to -1 (disabled).

How the Token Bucket Algorithm Works in SDS

The algorithm follows a precise execution flow that balances immediate token availability with historic bucket reserves.

1. Token Generation

The system creates tokens discretely each second using the sliding-window counter. The generatedTokensInSecond parameter defines the refill rate, while bucketSize caps the maximum accumulable tokens. When bucketSize is -1 or equal to the generation rate, the bucket effectively operates without burst capacity beyond the per-second limit.

2. Token Consumption

When a request enters the system, the client calls TokenBucketData.takeOneToken(now), which stores the current second's token count in CheckData.takeTokenBucketNum. This value represents how many tokens have been consumed in the present second.

3. Admission Decision

The TokenBucketStrategyExecutor applies the following logic in strategyCheck:

• Invalid Configuration: If generatedTokensInSecond is null or negative, the strategy is bypassed (return true).
• Within Current Limit: If the current second's token count is less than or equal to generatedTokensInSecond, the request passes immediately.
• Bucket Overflow Handling: If bucketSize is less than or equal to generatedTokensInSecond, excess requests beyond the generation rate are rejected.
• Capacity Check: If the request's token count exceeds bucketSize, the request is rejected.
• Historic Bucket Fallback: When the current second is exhausted, the executor checks previous seconds for spare tokens using the formula:

return CYCLE_BUCKET_NUM * BUCKET_TIME * generatedTokensInSecond
       - takeTokenBucketNum + downgradeCount > 0;

If this calculation yields a positive value, the request proceeds using accumulated tokens from earlier windows; otherwise, SDS triggers a downgrade.

4. Lifecycle Management

CycleDataService.createTokenBucketCycleData() instantiates fresh TokenBucketData objects for each statistics cycle. The CycleClearAndUploadTask clears next-cycle counters at half-cycle intervals to maintain accurate sliding windows and prevent memory leaks.

Configuring Token Bucket Parameters

Administrators configure the token bucket through the SDS admin console or REST API endpoints. The configuration pipeline persists values in the database and distributes them to client agents via periodic heartbeats.

Configuration Parameters

• tokenBucketGeneratedTokensInSecond: Defines how many tokens the bucket generates each second. Set to -1 to disable the strategy.
• tokenBucketSize: Sets the maximum token capacity. When set to -1, the capacity defaults to the generation rate (no burst allowed).

Admin API Validation

In PointStrategyController, the system guarantees non-null values by defaulting missing fields:

if (pointStrategyRequest.getTokenBucketGeneratedTokensInSecond() == null) {
    pointStrategyRequest.setTokenBucketGeneratedTokensInSecond(-1);
}
if (pointStrategyRequest.getTokenBucketSize() == null) {
    pointStrategyRequest.setTokenBucketSize(-1);
}

These values are stored in the PointStrategy database table (token_bucket_generated_tokens_in_second, token_bucket_size) and pushed to clients through SdsHeartBeatService.updatePointStrategyFromWebServer().

Practical Implementation Examples

Defining a Token Bucket Strategy in Java

import com.didiglobal.sds.client.bean.SdsStrategy;

SdsStrategy strategy = new SdsStrategy();
strategy.setPoint("orderService.process");
strategy.setTokenBucketGeneratedTokensInSecond(100); // 100 QPS limit
strategy.setTokenBucketSize(200);                  // Allow burst up to 200
// Other thresholds can be set to -1 to disable them

Configuring via REST API

Send a POST request to /sds/api/pointStrategy with the following JSON payload:

{
  "point": "orderService.process",
  "visitThreshold": -1,
  "concurrentThreshold": -1,
  "exceptionThreshold": -1,
  "timeoutThreshold": -1,
  "tokenBucketGeneratedTokensInSecond": 100,
  "tokenBucketSize": 200,
  "downgradeRate": 100,
  "delayTime": -1,
  "retryInterval": -1
}

The controller stores these values and distributes them to client agents during the next heartbeat cycle.

Client-Side Integration

Business code interacts with the token bucket transparently through the SDS client:

// Entry registers the request and starts counting
SdsClient.enter("orderService.process");

try {
    // ... business logic ...
    processOrder();
} finally {
    // Exit triggers the token bucket check in TokenBucketStrategyExecutor
    SdsClient.exit("orderService.process");
}

During exit(), the client invokes TokenBucketData.takeOneToken() to record consumption and executes the strategy chain. If tokens are exhausted, SdsClient returns a fallback value or throws SdsException based on the downgradeRate configuration.

Summary

• Token Generation: TokenBucketData uses a SlidingWindowData counter to generate tokens discretely each second according to tokenBucketGeneratedTokensInSecond.
• Admission Control: TokenBucketStrategyExecutor.strategyCheck() evaluates requests against current and historic bucket states, allowing bursts only when tokenBucketSize permits and previous windows contain spare capacity.
• Configuration: Parameters are managed through SdsStrategy, persisted via PointStrategyController, and distributed to clients through the heartbeat mechanism.
• Default Behavior: Setting either parameter to -1 disables the token bucket strategy for that point, causing the executor to return true and allow all traffic.

Frequently Asked Questions

How does SDS handle token bucket bursts?

When tokenBucketSize exceeds tokenBucketGeneratedTokensInSecond, the algorithm permits bursts up to the configured capacity. If the current second's tokens are exhausted, the executor checks previous seconds' unused capacity using the formula CYCLE_BUCKET_NUM * BUCKET_TIME * generatedTokensInSecond - takeTokenBucketNum + downgradeCount. If the result is positive, the request proceeds; otherwise, it is downgraded.

What happens if I set tokenBucketSize to -1?

Setting tokenBucketSize to -1 (the default) configures the bucket with no burst capacity beyond the immediate generation rate. Effectively, the bucket size equals tokenBucketGeneratedTokensInSecond, meaning only tokens generated in the current second are available, and no accumulation occurs across time windows.

Where does the token bucket check occur in the request lifecycle?

The check occurs during SdsClient.exit(). When the business method completes, the client calls TokenBucketData.takeOneToken() to record the request in the current second's counter, then passes this data to TokenBucketStrategyExecutor for evaluation. This placement ensures the system accounts for every executed request while allowing the business logic to run before applying rate limits.

How are configuration changes propagated to clients?

The SDS admin service persists token bucket parameters in the PointStrategy database table via PointStrategyController. Client agents poll the admin server through SdsHeartBeatService.updatePointStrategyFromWebServer(), downloading the latest SdsStrategy configurations during each heartbeat interval. Changes take effect immediately after the next successful poll.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}