Sliding Window Algorithm in Sentinel: Theory, Implementation, and Code Walkthrough

The sliding‑window algorithm is one of the mainstream rate‑limiting methods alongside leaky‑bucket and token‑bucket, and Sentinel adopts it for its lightweight configurability and ability to handle traffic bursts in scenarios like e‑commerce flash sales.

A typical sliding‑window interview problem is given an integer array and a window size n, find the maximum sum of n consecutive elements. The following Java code demonstrates a straightforward solution that maintains a moving sum while sliding the window:

public class WindowDemo {
    public static void solution(int n) {
        // Simulate window data
        int WindowData = 0;
        if (n <= 0) {
            n = 2;
        }
        int a[] = {-1, 2, 3, 7, -10, 6};
        // Initialize window with first n elements
        for (int i = 0; i < n; i++) {
            WindowData = WindowData + a[i];
        }
        System.out.println("窗内数据为：" + WindowData);
        int max = WindowData;
        // Slide the window forward
        for (int i = n; i < a.length; i++) {
            WindowData = WindowData + a[i] - a[i - n];
            System.out.println("窗内数据为：" + WindowData);
            if (max < WindowData) {
                max = WindowData;
            }
        }
        System.out.println("最大值为" + max);
    }
    public static void main(String[] args) {
        solution(2);
    }
}

In Sentinel, a sliding window is represented by a series of WindowWrap objects. Each WindowWrap stores the window length, start timestamp, and a generic value (e.g., a MetricBucket) that holds the actual statistics.

public class WindowWrap {
    private final long windowLengthInMs;
    private long windowStart;
    private T value;
    public WindowWrap(long windowLengthInMs, long windowStart, T value) {
        this.windowLengthInMs = windowLengthInMs;
        this.windowStart = windowStart;
        this.value = value;
    }
    public long windowLength() { return windowLengthInMs; }
    public long windowStart() { return windowStart; }
    public T value() { return value; }
    public void setValue(T value) { this.value = value; }
    public WindowWrap resetTo(long startTime) {
        this.windowStart = startTime;
        return this;
    }
    public boolean isTimeInWindow(long timeMillis) {
        return windowStart <= timeMillis && timeMillis < windowStart + windowLengthInMs;
    }
    @Override
    public String toString() {
        return "WindowWrap{" +
               "windowLengthInMs=" + windowLengthInMs +
               ", windowStart=" + windowStart +
               ", value=" + value +
               '}';
    }
}

The collection of sample windows is managed by LeapArray. It keeps an AtomicReferenceArray<WindowWrap> of fixed size ( sampleCount) and provides methods to locate the current window based on the current timestamp.

public WindowWrap currentWindow() {
    return currentWindow(TimeUtil.currentTimeMillis());
}

public WindowWrap currentWindow(long timeMillis) {
    if (timeMillis < 0) return null;
    int idx = calculateTimeIdx(timeMillis);
    long windowStart = calculateWindowStart(timeMillis);
    while (true) {
        WindowWrap old = array.get(idx);
        if (old == null) {
            WindowWrap window = new WindowWrap(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
            if (array.compareAndSet(idx, null, window)) {
                return window;
            } else {
                Thread.yield();
            }
        } else if (windowStart == old.windowStart()) {
            return old;
        } else if (windowStart > old.windowStart()) {
            if (updateLock.tryLock()) {
                try {
                    return resetWindowTo(old, windowStart);
                } finally {
                    updateLock.unlock();
                }
            } else {
                Thread.yield();
            }
        } else { // windowStart < old.windowStart()
            return new WindowWrap(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
        }
    }
}

private int calculateTimeIdx(long timeMillis) {
    long timeId = timeMillis / windowLengthInMs;
    return (int) (timeId % array.length());
}

protected long calculateWindowStart(long timeMillis) {
    return timeMillis - timeMillis % windowLengthInMs;
}

The actual statistical data stored in each window is encapsulated by MetricBucket. It uses an array of LongAdder counters for different metric events (e.g., PASS, BLOCK). Adding a successful request simply increments the PASS counter.

public class MetricBucket {
    private final LongAdder[] counters;
    private volatile long minRt;
    public MetricBucket() {
        MetricEvent[] events = MetricEvent.values();
        counters = new LongAdder[events.length];
        for (MetricEvent event : events) {
            counters[event.ordinal()] = new LongAdder();
        }
        initMinRt();
    }
    public long get(MetricEvent event) {
        return counters[event.ordinal()].sum();
    }
    public MetricBucket add(MetricEvent event, long n) {
        counters[event.ordinal()].add(n);
        return this;
    }
    public long pass() { return get(MetricEvent.PASS); }
    public void addPass(int n) { add(MetricEvent.PASS, n); }
}

When a request passes all downstream slots, StatisticSlot invokes node.addPassRequest(count). The node delegates to an ArrayMetric which retrieves the current WindowWrap from its LeapArray and calls MetricBucket.addPass(count), thereby updating the PASS counter of the appropriate time slice.

private final LeapArray data;
@Override
public void addPass(int count) {
    WindowWrap wrap = data.currentWindow();
    wrap.value().addPass(count);
}

The window‑sliding logic handles three cases: (1) the target slot is empty and a new WindowWrap is created; (2) the slot already represents the current time slice and is reused; (3) the slot is outdated, so it is reset to the new start time under a lock, effectively sliding the window forward.

Overall, the article demonstrates how Sentinel implements a sliding‑window rate limiter by decomposing a time range into fixed‑size sample windows, storing per‑window metrics in MetricBucket, and continuously updating the appropriate window as requests arrive.