SDS Sliding Window Design: How the 10-Second Window and 1-Second Step Work

The SDS (Service-Based Degrade System) sliding window uses a ring buffer of 1-second buckets to aggregate metrics over a moving 10-second window, enabling real-time downgrade decisions with minimal memory overhead.

The didi/sds repository implements a high-performance sliding window algorithm to track service metrics like visit counts, exceptions, and concurrency. This design balances accuracy and efficiency by using fixed-time buckets and a circular array structure. The 10-second window provides sufficient historical context for downgrade decisions, while the 1-second step ensures granular, real-time responsiveness.

Core Architecture: Buckets and Cycles

At the heart of SDS’s sliding window are three constants defined in BizConstant.java that determine the time granularity and window size.

Bucket Configuration Constants

The system divides time into discrete buckets, each representing exactly one second of metric data:

public static final int BUCKET_TIME = 1;               // 每个桶的时间宽度，单位秒
public static final int CYCLE_BUCKET_NUM = 10;        // 每个周期的桶数量（10 s）
public static final int CYCLE_NUM = 3;                // 保存的完整周期数量（3 × 10 s = 30 s）

• BUCKET_TIME = 1: Defines the 1-second step, the atomic time unit for each bucket.
• CYCLE_BUCKET_NUM = 10: Creates the 10-second window by grouping 10 consecutive buckets into a logical cycle.
• CYCLE_NUM = 3: Maintains three complete cycles (30 seconds total) in memory to support both current decision-making and historical data uploads.

Ring Buffer Implementation

SDS stores metric data in an AtomicLongArray acting as a circular buffer. The array length equals CYCLE_NUM * CYCLE_BUCKET_NUM (30 buckets), providing 30 seconds of retention while enabling O(1) access times.

Index Calculation and Wrap-Around

The SlidingWindowData.java file contains the core logic for mapping timestamps to array indices:

// Calculate bucket index from UTC timestamp (milliseconds)
private int getBucketIndexByTime(long time) {
    return (int) ((DateUtils.getSecond(time) / bucketTimeSecond) % bucketSize);
}

// Handle array wrap-around for negative or overflow indices
private int switchIndex(int index) {
    if (index >= 0 && index < bucketSize) {
        return index;
    } else if (index < 0) {
        return bucketSize + index;            // negative → tail of array
    } else {
        return index - bucketSize;            // overflow → head of array
    }
}

The 1-second step manifests as the progression of time by one second, which advances the bucket index by exactly one position in the ring buffer.

The 10-Second Sliding Window Logic

When a protected method invokes metric recording, incrementAndGet in SlidingWindowData.java updates the current bucket and computes the sliding window aggregate.

Real-Time Metric Aggregation

@Override
public VisitWrapperValue incrementAndGet(long time) {
    int bucketIndex = getBucketIndexByTime(time);

    // Current 1-second bucket value
    long curSecondValue = bucketArray.incrementAndGet(bucketIndex);

    // Sliding 10-second window value (last CYCLE_BUCKET_NUM seconds)
    long slidingCycleValue = curSecondValue;
    for (int i = bucketIndex - cycleBucketNum + 1; i < bucketIndex; i++) {
        slidingCycleValue += bucketArray.get(switchIndex(i));
    }

    return new VisitWrapperValue(curSecondValue, slidingCycleValue);
}

This method returns a VisitWrapperValue containing:

• curSecondValue: The count for the current 1-second step (instantaneous load).
• slidingCycleValue: The sum of the last 10 seconds (10-second window), used for downgrade decisions to smooth out spikes.

Whole-Cycle Aggregation for Uploads

For server-side persistence, SDS computes stable metrics over complete 10-second cycles. The getLastWholeCycleBucketTotalValue method in SlidingWindowData.java sums an entire previous cycle, excluding the incomplete current second:

private long getLastWholeCycleBucketTotalValue(int bucketIndex) {
    long total = 0;
    int cycleNum = switchIndex(bucketIndex - cycleBucketNum) / cycleBucketNum;
    int startBucketIndex = cycleNum * cycleBucketNum;
    int endBucketIndex   = startBucketIndex + cycleBucketNum;

    for (int i = startBucketIndex; i < endBucketIndex; i++) {
        total += bucketArray.get(i);
    }
    return total;
}

CycleDataService.java invokes this method every 5 seconds to upload the previous whole-cycle data, ensuring the server receives consistent, non-overlapping 10-second metrics.

Cycle Maintenance and Cleanup

To prevent stale data from polluting new cycles, SDS proactively clears buckets before they are reused. The cleanBucketArrayValue method zeros out the buckets belonging to the next logical cycle:

private void cleanBucketArrayValue(long time) {
    int curBucketIndex = getBucketIndexByTime(time);
    int cycleNum = switchIndex(curBucketIndex + cycleBucketNum) / cycleBucketNum;
    int startBucketIndex = cycleNum * cycleBucketNum;
    int endBucketIndex   = startBucketIndex + cycleBucketNum;

    for (int i = startBucketIndex; i < endBucketIndex; i++) {
        bucketArray.set(i, 0);
    }
}

This cleanup ensures that when the sliding window advances, it never sums data from 30 seconds ago with current metrics.

Practical Usage Example

The following pattern demonstrates how SDS strategies use the 10-second window for downgrade logic:

long now = System.currentTimeMillis();

// Record visit and retrieve both current and windowed values
VisitWrapperValue v = slidingWindowData.incrementAndGet(now);

long currentSecondVisits = v.getBucketValue();        // 1-second step value
long last10SecVisits = v.getSlidingCycleValue();      // 10-second window aggregate

// Downgrade trigger based on 10-second trend (smoothing spikes)
if (last10SecVisits > VISIT_THRESHOLD) {
    // Trigger service downgrade
}

As implemented in didi/sds, this approach allows strategies to distinguish between temporary spikes (1-second) and sustained load (10-second) when making degradation decisions.

Summary

• 1-Second Step: Each bucket in SlidingWindowData.java represents exactly one second (BUCKET_TIME = 1), providing granular metric tracking.
• 10-Second Window: The sliding aggregation sums the last CYCLE_BUCKET_NUM (10) buckets, offering a stable view of recent service load.
• 30-Second Buffer: The underlying ring buffer stores 30 seconds of data (CYCLE_NUM = 3), supporting both real-time decisions and periodic uploads of complete 10-second cycles.
• Atomic Operations: The use of AtomicLongArray ensures thread-safe increments without blocking, critical for high-throughput services.

Frequently Asked Questions

Why does SDS use 1-second buckets instead of millisecond precision?

1-second buckets strike a balance between timeliness and memory efficiency. According to the didi/sds source code, millisecond-level buckets would require thousands of array slots for a 10-second window, increasing memory pressure and CPU overhead during aggregation without providing meaningful benefits for service degradation decisions, which typically respond to second-level trends.

How does the ring buffer handle time wrap-around?

The switchIndex method in SlidingWindowData.java handles index calculations modulo the buffer size (30). When indices exceed the array bounds or become negative during sliding window calculations, switchIndex wraps them to the corresponding position in the circular buffer, ensuring the 10-second window always references valid, recent data.

What is the difference between the sliding window and whole-cycle window?

The sliding window (10-second) is a moving aggregate used for real-time downgrade decisions, updated every time a metric is recorded. The whole-cycle window is a fixed 10-second block (e.g., seconds 0-9, 10-19) used for server uploads via CycleDataService.java. The sliding window provides immediate responsiveness, while the whole-cycle window provides stable, non-overlapping metrics for historical analysis.

How often does SDS upload metrics to the server?

CycleDataService.java uploads data every 5 seconds (half a cycle). It calls getLastWholeCycleValue to retrieve the completed previous 10-second cycle’s totals, ensuring the server receives regular updates without the overhead of per-second uploads.

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