文章目录
-
- 先说结论
- LeapArray 数据结构
- 格子定位：时间到索引的映射
- 数据写入：CAS 更新无锁
- 数据统计：累加所有有效格子
- 回答技巧与点评
-
- 加分回答
- 面试官点评
个人网站
前面讲了限流算法，知道 Sentinel 用滑动窗口——但它的滑动窗口和教科书上的不一样。Sentinel 的 LeapArray 是一个高性能、低内存的滑动窗口实现。面试官问这题，他想听的是：你能不能讲清 LeapArray 的数据结构、滑动机制、和指标统计的流程？
先说结论
| 维度 | 说明 || | ——|——|| | 数据结构 | 环形数组（LeapArray）+ 每个格子（WindowWrap）存统计数据 || | 窗口配置 | 默认 1 秒窗口分 2 格，每格 500ms || | 滑动方式 | 根据当前时间计算格子索引，覆盖过期格子 || | 并发安全 | 用 CAS 更新格子起始时间，避免加锁 || | 统计指标 | 通过 QPS、异常数、RT 等 || | 内存优化 | 固定大小数组，不创建新对象 ||
|一句话记住：Sentinel的滑动窗口像"环形跑道"——跑完一圈回到起点，旧的记录自动被覆盖"
LeapArray 数据结构
// Sentinel 核心数据结构（简化）
public class LeapArray<T> {
int windowLengthInMs; // 每格时长（默认500ms）
int sampleCount; // 格子数（默认2）
int intervalInMs; // 窗口总时长（默认1000ms）
// 环形数组 —— 核心存储 👈
AtomicReferenceArray<WindowWrap<T>> array;
}
// 每个格子
public class WindowWrap<T> {
long windowStart; // 格子起始时间
T value; // 统计数据（MetricBucket）
}
默认配置：1秒窗口，2个格子
array[0]: WindowWrap{start=1000ms, value=Bucket{pass=5, block=1}}
array[1]: WindowWrap{start=1500ms, value=Bucket{pass=3, block=0}}
↑ ↑
0-500ms的统计 500-1000ms的统计
总QPS = array[0].value.pass + array[1].value.pass = 8
格子定位：时间到索引的映射
// 根据当前时间计算格子索引
int calculateTimeIdx(long timeMillis) {
return (int)(timeMillis / windowLengthInMs) % sampleCount;
}
// 计算格子应该的起始时间
long calculateWindowStart(long timeMillis) {
return timeMillis – timeMillis % windowLengthInMs;
}
示例：windowLengthInMs=500, sampleCount=2
timeMillis=1200 → idx = 1200/500 % 2 = 0, start = 1000
timeMillis=1700 → idx = 1700/500 % 2 = 1, start = 1500
timeMillis=2200 → idx = 2200/500 % 2 = 0, start = 2000 👈 复用array[0]
当时间推进到新格子时，旧的格子会被覆盖——这就是"滑动"：不是物理移动数组，而是时间推进后旧格子自然过期。
数据写入：CAS 更新无锁
public WindowWrap<T> currentWindow(long timeMillis) {
int idx = calculateTimeIdx(timeMillis);
long windowStart = calculateWindowStart(timeMillis);
while (true) {
WindowWrap<T> old = array.get(idx);
if (old == null) {
// 格子为空，创建新的
WindowWrap<T> wrap = new WindowWrap<>(windowStart, newBucket());
if (array.compareAndSet(idx, null, wrap)) { // 👈 CAS
return wrap;
}
} else if (windowStart == old.windowStart) {
// 时间匹配，直接用
return old;
} else if (windowStart > old.windowStart) {
// 时间已过期，覆盖旧格子 👈
if (old.tryLock()) {
try {
old.resetTo(windowStart); // 重置起始时间+清空数据
return old;
} finally {
old.unlock();
}
}
}
// CAS 失败或锁竞争，自旋重试
}
}
关键点：
- 格子为空时用 CAS 创建，避免加锁
- 格子过期时用锁覆盖，保证数据重置的原子性
- 格子时间匹配时直接返回，零开销
数据统计：累加所有有效格子
public List<WindowWrap<T>> list(long timeMillis) {
int idx = calculateTimeIdx(timeMillis);
long windowStart = calculateWindowStart(timeMillis);
List<WindowWrap<T>> result = new ArrayList<>();
for (int i = 0; i < array.length(); i++) {
WindowWrap<T> wrap = array.get(i);
if (wrap == null) continue;
// 只统计窗口内的格子（过期的不算） 👈
if (isWindowDeprecated(wrap, timeMillis)) continue;
result.add(wrap);
}
return result;
}
// 判断格子是否过期
boolean isWindowDeprecated(WindowWrap wrap, long timeMillis) {
return timeMillis – wrap.windowStart > intervalInMs;
}
示例：当前时间 = 2000ms
array[0]: start=1000ms → 2000-1000=1000ms = intervalInMs → 刚好过期 👈
array[1]: start=1500ms → 2000-1500=500ms < intervalInMs → 有效 ✅
统计QPS = array[1].pass = 3（只算有效格子）
Sentinel 滑动窗口全景
数据结构
├── LeapArray —— 环形数组
├── WindowWrap —— 格子（起始时间+统计数据）
└── MetricBucket —— 统计值（pass/block/exception/rt）
核心机制
├── 格子定位 —— 时间取模算索引
├── 数据写入 —— CAS无锁 + 过期覆盖
├── 数据统计 —— 遍历有效格子累加
└── 滑动本质 —— 不是物理移动，是时间推进后旧格子自然过期
配置
├── 默认1秒窗口分2格
├── 统计精度500ms
└── 可配置：sampleCount越大精度越高
口诀：环形数组存格子，时间取模算索引；
CAS写入无锁快，过期格子直接覆盖；
统计只算窗口内，旧数据自然淘汰；
不创建新对象省内存，高并发下性能好
回答技巧与点评
标准回答：Sentinel 用 LeapArray 实现滑动窗口：环形数组存 WindowWrap 格子，每个格子记录起始时间和统计数据。格子索引通过时间取模计算，写入时用 CAS 无锁更新，格子过期后覆盖重置。统计时遍历所有格子，跳过超出窗口时间的过期格子。默认 1 秒窗口分 2 格（500ms 精度），环形数组固定大小，不创建新对象。
加分回答
面试官点评
这道题考的是你对 流量统计实现 的理解深度。最忌讳的回答是只知道"滑动窗口"四个字——面试官想听的是 LeapArray 的数据结构（环形数组+WindowWrap）和 滑动机制（时间取模定位+过期覆盖）。能画出环形数组示意图，再讲清 CAS 写入，就是高分回答。
原文阅读
内容有帮助？点赞、收藏、关注三连！评论区等你 💪
