# How SDS Implements Sliding‑Window Rate Limiting Using AtomicLongArray

> Discover how SDS implements thread-safe sliding window rate limiting using AtomicLongArray for lock-free atomic increments and seamless time-based bucket rotation in this technical deep dive.

- Repository: [DiDi/sds](https://github.com/didi/sds)
- Tags: internals
- Published: 2026-02-28

---

**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`](https://github.com/didi/sds/blob/main/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:

```java
(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:

```java
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`](https://github.com/didi/sds/blob/main/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

```java
// 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

```java
// 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

```java
// 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`](https://github.com/didi/sds/blob/main/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.