seo网站优化工具,国内国际时事最新消息,网页游戏传奇霸主,中国历任总经理名单限流算法
以固定时间窗口算法和滑动时间窗口算法为例#xff0c;展开两种限流算法的分析。
固定时间窗口算法
在固定的时间窗口内#xff0c;设置允许固定数量的请求进入。如果超过设定的阈值就拒绝请求或者排队。
具体的#xff0c;按照时间划分为若干个时间窗口#…限流算法
以固定时间窗口算法和滑动时间窗口算法为例展开两种限流算法的分析。
固定时间窗口算法
在固定的时间窗口内设置允许固定数量的请求进入。如果超过设定的阈值就拒绝请求或者排队。
具体的按照时间划分为若干个时间窗口每个时间窗口里面的设置的请求数量的阈值都是相同的。一旦某个时间窗口内的请求数量达到阈值就会拒绝新的请求或者进入排队状态。
缺点是无法计算跨相邻时间窗口的请求数量是否达到阈值。
滑动时间窗口算法
在固定时间窗口的基础上时间窗口的起点和终点不再固定而是随着时间推移而不断变化但是每个时间窗口的长度终点-起点始终是固定的也就是说整体会随着时间的推移而不断滑动。
但是每次时间窗口的移动都需要重新统计请求数量会有一些重叠区域重复计算的问题因此可以对时间窗口进行更细粒度的划分增加一些子时间窗口即样本窗口。这样对时间窗口内部的请求数量的计算就会变成对相应的样本窗口内部的请求数量的计算再求和。如果超过阈值同样会被限流。
源码分析
以 Sentinel 内部的 LeapArray 的 currentWindow 方法为例解析如何根据指定时间获取对应的样本窗口。
流程概述
1、将指定时间 / 时间窗口的长度默认500ms再 % 样本窗口总数量得到所属的新的样本窗口对应的下标 n。
2、再通过指定时间 - 指定时间 % 时间窗口的长度得到对应样本窗口的开始时间。
3、从缓存中获取指定下标 n 的旧的样本窗口如果该样本窗口不存在则进行创建并返回。
4、比较新样本窗口的开始时间 t1 与旧样本窗口的开始时间 t2分为三种情况。
如果 t1 t2说明新样本窗口与旧样本窗口是相同的则返回旧样本窗口。如果 t1 t2说明旧样本窗口的状态滞后则重置旧样本窗口的所有指标再使用 LongAdder 计算某一指标并进行更新最后返回更新后的样本窗口。如果 t1 t2说明时间发生了倒流一般不会发生则创建新的样本窗口并返回。
LeapArray
public WindowWrapT currentWindow(long timeMillis) {if (timeMillis 0) {return null;}// 计算指定时间所属的样本窗口的下标int idx calculateTimeIdx(timeMillis);// 计算指定时间所属的样本窗口的起始时间点long windowStart calculateWindowStart(timeMillis);/** Get bucket item at given time from the array.** (1) Bucket is absent, then just create a new bucket and CAS update to circular array.* (2) Bucket is up-to-date, then just return the bucket.* (3) Bucket is deprecated, then reset current bucket and clean all deprecated buckets.*/while (true) {WindowWrapT old array.get(idx);if (old null) {/** B0 B1 B2 NULL B4* ||_______|_______|_______|_______|_______||___* 200 400 600 800 1000 1200 timestamp* ^* time888* bucket is empty, so create new and update** If the old bucket is absent, then we create a new bucket at {code windowStart},* then try to update circular array via a CAS operation. Only one thread can* succeed to update, while other threads yield its time slice.*/WindowWrapT window new WindowWrapT(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));if (array.compareAndSet(idx, null, window)) {return window;} else {Thread.yield();}} else if (windowStart old.windowStart()) {/** B0 B1 B2 B3 B4* ||_______|_______|_______|_______|_______||___* 200 400 600 800 1000 1200 timestamp* ^* time888* startTime of Bucket 3: 800, so its up-to-date** If current {code windowStart} is equal to the start timestamp of old bucket,* that means the time is within the bucket, so directly return the bucket.*/return old;} else if (windowStart old.windowStart()) {/** (old)* B0 B1 B2 NULL B4* |_______||_______|_______|_______|_______|_______||___* ... 1200 1400 1600 1800 2000 2200 timestamp* ^* time1676* startTime of Bucket 2: 400, deprecated, should be reset** If the start timestamp of old bucket is behind provided time, that means* the bucket is deprecated. We have to reset the bucket to current {code windowStart}.* Note that the reset and clean-up operations are hard to be atomic,* so we need a update lock to guarantee the correctness of bucket update.** The update lock is conditional (tiny scope) and will take effect only when* bucket is deprecated, so in most cases it wont lead to performance loss.*/if (updateLock.tryLock()) {try {// 重置所有指标并计算PASS指标return resetWindowTo(old, windowStart);} finally {updateLock.unlock();}} else {Thread.yield();}} else if (windowStart old.windowStart()) {// 注意一般不会出现该情况该情况属于时间倒流return new WindowWrapT(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));}}
}calculateTimeIdx
private int calculateTimeIdx(/*Valid*/ long timeMillis) {// windowLengthInMs默认是500long timeId timeMillis / windowLengthInMs;// array数组的长度默认是2return (int)(timeId % array.length());
}计算指定时间所属的样本窗口的下标。
calculateWindowStart
protected long calculateWindowStart(/*Valid*/ long timeMillis) {return timeMillis - timeMillis % windowLengthInMs;
}计算指定时间所属的样本窗口的开始时间。
resetWindowTo
以 OccupiableBucketLeapArray 为例。
Override
protected WindowWrapMetricBucket resetWindowTo(WindowWrapMetricBucket w, long time) {// 将windowStart设置为指定时间即样本窗口的开始时间w.resetTo(time);// 获取样本窗口的统计数据MetricBucket borrowBucket borrowArray.getWindowValue(time);if (borrowBucket ! null) {// 重置所有指标w.value().reset();// 计算PASS指标w.value().addPass((int)borrowBucket.pass());} else {// 重置所有指标w.value().reset();}return w;
}MetricBucket#reset
public MetricBucket reset() {for (MetricEvent event : MetricEvent.values()) {// 重置所有指标counters[event.ordinal()].reset();}// 初始化minRt属性initMinRt();return this;
}MetricEvent 是一个枚举类包括PASS, BLOCK, EXCEPTION, SUCCESS, RT, OCCUPIED_PASS。
MetricBucket#initMinRt
private void initMinRt() {// 获取 csp.sentinel.statistic.max.rt 属性值默认 5000并初始化minRt属性this.minRt SentinelConfig.statisticMaxRt();
}MetricBucket#addPass
public void addPass(int n) {// 计算PASS指标add(MetricEvent.PASS, n);
}public MetricBucket add(MetricEvent event, long n) {// 底层使用LongAdder计算指标counters[event.ordinal()].add(n);return this;
}
