How SDS Implements Sliding‑Window Rate Limiting Using AtomicLongArray

SDS (Service Degradation System) implements thread‑safe sliding‑window rate limiting by storing per‑second counters in a ring buffer backed by java.util.concurrent.atomic.AtomicLongArray, enabling lock‑free atomic increments and seamless time‑based bucket rotation.

The SDS (Service Degradation System) open‑source project provides high‑performance rate limiting and degradation policies for distributed microservices. At the heart of its time‑window algorithms lies the SlidingWindowData class, which leverages AtomicLongArray to maintain a circular buffer of counters that atomically track request volumes across configurable sliding windows.

Ring Buffer Architecture

The sliding‑window implementation treats AtomicLongArray as a circular ring buffer where each array element represents one second of traffic volume.

Bucket Layout and Capacity

In sds-client/src/main/java/com/didiglobal/sds/client/counter/SlidingWindowData.java, the constructor initializes the array size as cycleNum * cycleBucketNum, defaulting to 10 cycles × 10 seconds = 100 buckets. Each index holds the cumulative count for a specific UTC second, allowing the system to retain granular per‑second data while covering a total window span determined by the cycle configuration.

Circular Index Mapping with switchIndex

To handle seamless wrap‑around when the write cursor reaches the array boundary, the class provides the switchIndex(int logicalIndex) method. This method maps any logical index—including negative values generated during backward window traversal—back into the valid physical range of the underlying AtomicLongArray. The ring buffer design eliminates the need for array resizing or expensive copy operations as time progresses.

Time‑Based Bucket Indexing

The getBucketIndexByTime(long time) method converts a millisecond timestamp into the appropriate bucket position using the formula:

(timestamp‑seconds / bucketTimeSecond) % bucketSize

This calculation relies on the current UTC second, ensuring the index advances exactly once per real‑time second regardless of call frequency. By deriving the bucket from the absolute time rather than a relative cursor, SDS guarantees that concurrent threads always target the same array index for a given second, which is essential for accurate aggregation.

Lock‑Free Atomic Updates

Concurrent safety is achieved through AtomicLongArray's native atomic primitives. The incrementAndGet(long time) method first resolves the bucket index for the provided timestamp, then executes:

bucketArray.incrementAndGet(bucketIndex)

Because AtomicLongArray provides hardware‑level compare‑and‑swap operations, multiple threads can safely increment the same per‑second counter without blocking, mutex acquisition, or contention penalties. This lock‑free approach delivers consistent latency even under extreme concurrency.

Computing the Sliding‑Window Total

After atomically incrementing the current bucket, the implementation calculates the total volume across the entire sliding window. The method walks backward over the previous cycleBucketNum‑1 buckets, invoking switchIndex(i) to resolve each physical array position while handling wrap‑around, and sums their values.

The aggregated result is encapsulated in a VisitWrapperValue object that exposes both the current‑second count (getBucketValue()) and the sliding‑window total (getSlidingCycleValue()). This dual‑value return allows rate‑limiting rules to evaluate both instantaneous spikes and sustained traffic patterns over the configured window (e.g., the last 10 seconds).

Cycle Management and Background Cleanup

To prevent stale counters from previous windows from contaminating future calculations, SDS implements a proactive cleanup strategy. The clearNextCycleValue(long time) method zeros out the bucket set belonging to the next statistical cycle before it becomes active.

This maintenance operation is scheduled periodically via CycleDataService.CycleClearAndUploadTask, which runs inside sds-client/src/main/java/com/didiglobal/sds/client/service/CycleDataService.java. By clearing buckets in advance, the system ensures that when the ring buffer cursor wraps around to a previously used index, the counter starts fresh rather than accumulating historical data.

Integration with Higher‑Level Rate Limiters

While SlidingWindowData can be used directly, SDS typically embeds it within higher‑level abstractions such as token buckets. The TokenBucketData class delegates its counting logic to an internal SlidingWindowData instance, allowing QPS‑based throttling to leverage the same accurate, sliding‑window metrics.

Direct Sliding‑Window Usage

// Create a default 100‑bucket sliding window (10 cycles × 10 seconds)
SlidingWindowData window = new SlidingWindowData();

// Record an event at the current time
long now = System.currentTimeMillis();
VisitWrapperValue value = window.incrementAndGet(now);

System.out.println("Current second: " + value.getBucketValue());
System.out.println("Sliding total: " + value.getSlidingCycleValue());

Token Bucket Integration

// Initialize a token bucket: 100 tokens per second, max capacity 200
TokenBucketData tokenBucket = new TokenBucketData(100, 200);

// Attempt to acquire a token
long remaining = tokenBucket.takeOneToken(System.currentTimeMillis());
if (remaining < 0) {
    // Rate limit exceeded—reject or degrade the request
}

Service Bootstrap

// Register with the background service for automatic cycle cleanup
TokenBucketData rateLimiter = CycleDataService.createTokenBucketCycleData();
// CycleDataService automatically schedules clearNextCycleValue calls
// and uploads aggregated statistics to the SDS admin server.

Summary

• Ring Buffer Design: SDS stores per‑second counters in a circular AtomicLongArray sized to cycleNum * cycleBucketNum (default 100 buckets), treating the array as a ring via the switchIndex mapping function.
• Atomic Updates: The incrementAndGet method leverages AtomicLongArray.incrementAndGet for lock‑free, thread‑safe counter increments regardless of concurrency levels.
• Time‑Based Indexing: Bucket positions are calculated from absolute UTC seconds using (timestamp / bucketTimeSecond) % bucketSize, ensuring deterministic index assignment.
• Sliding Aggregation: After each increment, the system sums the previous cycleBucketNum‑1 buckets to produce the rolling window total returned in VisitWrapperValue.
• Proactive Cleanup: clearNextCycleValue periodically zeroes upcoming buckets via CycleDataService.CycleClearAndUploadTask to prevent stale data from affecting future windows.
• Modular Integration: Higher‑level components like TokenBucketData delegate counting to SlidingWindowData, enabling consistent sliding‑window semantics across QPS limiting, token buckets, and degradation policies.

Frequently Asked Questions

How does SDS handle index wrap‑around in the circular buffer?

The switchIndex(int logicalIndex) method in SlidingWindowData.java maps any logical index—including negative values used when walking backward through the window—into the valid physical range of the AtomicLongArray. This ensures the ring buffer seamlessly cycles from the final index back to the first without array resizing or memory reallocation.

What is the default sliding‑window size and bucket granularity?

By default, SDS configures the sliding window with 10 cycles of 10 seconds each, resulting in a 100‑bucket AtomicLongArray where every bucket represents exactly one second of traffic. This yields a default look‑back window of 10 seconds for rate‑limiting calculations, though both the cycle count and bucket duration are configurable.

How does the system prevent stale counter values from affecting new time windows?

SDS employs the clearNextCycleValue(long time) method, invoked periodically by CycleDataService.CycleClearAndUploadTask, to zero out the bucket set belonging to the next statistical cycle before it becomes active. This proactive clearing ensures that when the ring buffer cursor wraps around to reuse a bucket index, the counter starts from zero rather than retaining historical counts.

Can applications use the sliding‑window counter outside of the token‑bucket implementation?

Yes. Developers can instantiate SlidingWindowData directly to obtain raw per‑second and sliding‑window totals via incrementAndGet(time), which returns a VisitWrapperValue containing both the current bucket count and the aggregated window sum. This enables custom rate‑limiting logic, metrics collection, or degradation policies that require precise sliding‑window statistics.

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