邯郸县:源码剖析 Alibaba sentinel 滑动窗口实现原理(文末附原理图)

admin 2个月前 (04-26) 科技 4 0

要实现限流、熔断等功能,首先要解决的问题是若何实时采集服务(资源)挪用信息。例如将某一个接口设置的限流阔值 1W/tps,那首先若何判断当前的 TPS 是多少?Alibaba Sentinel 接纳滑动窗口来实现实时数据的统计。

温馨提醒:若是对源码不太感兴趣,可以先跳到文末,看一下滑动窗口的设计原理图,再决议是否需要阅读源码。

@

目录
  • 1、滑动窗口焦点类图
  • 2、滑动窗口实现原理
    • 2.1 ArrayMetric
    • 2.2 LongAdder
      • 2.2.1 类图与焦点属性
      • 2.2.2 currentWindow() 详解
      • 2.2.3 isWindowDeprecated() 详解
      • 2.2.4 getPreviousWindow() 详解
      • 2.2.5 滑动窗口图示
  • 3、OccupiableBucketLeapArray 详解
    • 3.2 组织函数
    • 3.3 newEmptyBucket
    • 3.4 resetWindowTo
    • 3.5 addWaiting

1、滑动窗口焦点类图


我们先对上述焦点类做一个简朴的先容,重点关注焦点类的作用与焦点属性(重点需要探讨其焦点数据结构)。

  • Metric
    指标网络焦点接口,主要界说一个滑动窗口中乐成的数目、异常数目、壅闭数目,TPS、响应时间等数据。
  • ArrayMetric
    滑动窗口焦点实现类。
  • LeapArray
    滑动窗口顶层数据结构,包罗一个一个的窗口数据。
  • WindowWrap
    每一个滑动窗口的包装类,其内部的数据结构用 MetricBucket 示意。
  • MetricBucket
    指标桶,例如通过数目、壅闭数目、异常数目、乐成数目、响应时间,已通过未来配额(抢占下一个滑动窗口的数目)。
  • MetricEvent
    指标类型,例如通过数目、壅闭数目、异常数目、乐成数目、响应时间等。

2、滑动窗口实现原理

2.1 ArrayMetric

滑动窗口的入口类为 ArrayMetric ,我们先来看一下其焦点代码。

private final LeapArray<MetricBucket> data;   // @1
public ArrayMetric(int sampleCount, int intervalInMs) {    // @2
    this.data = new OccupiableBucketLeapArray(sampleCount, intervalInMs);
}
public ArrayMetric(int sampleCount, int intervalInMs, boolean enableOccupy) {   // @3
	if (enableOccupy) {
		this.data = new OccupiableBucketLeapArray(sampleCount, intervalInMs);
	} else {
		this.data = new BucketLeapArray(sampleCount, intervalInMs);
	}
}

代码@1:ArrayMetric 类唯一的属性,用来存储各个窗口的数据,这个是接下来我们探讨的重点。

代码@2,代码@3 该类提供了两个组织方式,其焦点参数为:

  • int intervalInMs
    示意一个采集的时间距离,例如1秒,1分钟。
  • int sampleCount
    在一个采集距离中抽样的个数,默以为 2,例如当 intervalInMs = 1000时,抽象两次,则一个采集距离中会包罗两个相等的区间,一个区间就是滑动窗口。
  • boolean enableOccupy
    是否允许抢占,即当前时间戳已经到达限制后,是否可以占用下一个时间窗口的容量,这里对应 LeapArray 的两个实现类,若是允许抢占,则为 OccupiableBucketLeapArray,否则为 BucketLeapArray。

注重,LeapArray 的泛型类为 MetricBucket,意思就是指标桶,可以以为一个 MetricBucket 工具可以存储一个抽样时间段内所有的指标,例如一个抽象时间段中通过数目、壅闭数目、异常数目、乐成数目、响应时间,实在现的秘密在 LongAdder 中,本文先纰谬该类举行详细先容,后续文章会单独来探讨实在现原理。

这次,我们先不去看子类,反其道而行,先去看看其父类。

2.2 LongAdder

2.2.1 类图与焦点属性


LeapArray 的焦点属性如下:

  • int windowLengthInMs
    每一个窗口的时间距离,单元为毫秒。
  • int sampleCount
    抽样个数,就一个统计时间距离中包罗的滑动窗口个数,在 intervalInMs 相同的情形下,sampleCount 越多,抽样的统计数据就越正确,响应的需要的内存也越多。
  • int intervalInMs
    一个统计的时间距离。
  • AtomicReferenceArray<WindowWrap< T>> array
    一个统计时间距离中滑动窗口的数组,从这里也可以看出,一个滑动窗口就是使用的 WindowWrap< MetricBucket > 来示意。

上面的各个属性的寄义是从其组织函数得出来的,请其看组织函数。

public LeapArray(int sampleCount, int intervalInMs) {
    AssertUtil.isTrue(sampleCount > 0, "bucket count is invalid: " + sampleCount);
    AssertUtil.isTrue(intervalInMs > 0, "total time interval of the sliding window should be positive");
    AssertUtil.isTrue(intervalInMs % sampleCount == 0, "time span needs to be evenly divided");
    this.windowLengthInMs = intervalInMs / sampleCount;
    this.intervalInMs = intervalInMs;
    this.sampleCount = sampleCount;
    this.array = new AtomicReferenceArray<>(sampleCount);
}

那我们继续来看 LeapArray 中的方式,深入探讨滑动窗口的实现细节。

2.2.2 currentWindow() 详解

该方式主要是凭据当前时间来确定处于哪一个滑动窗口中,即找到上图中的 WindowWrap,该方式内部就是挪用其重载方式,参数为系统的当前时间,故我们重点来看一下重载方式的实现。

public WindowWrap<T> currentWindow(long timeMillis) { 
	if (timeMillis < 0) {
		return null;
	}
	int idx = calculateTimeIdx(timeMillis);  // @1
	long windowStart = calculateWindowStart(timeMillis); // @2
	while (true) { // 死循环查找当前的时间窗口,这里之所有需要循环,是由于可能多个线程都在获取当前时间窗口。
		WindowWrap<T> old = array.get(idx);  // @3
       		 if (old == null) {  // @4
			WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
           		 if (array.compareAndSet(idx, null, window)) {  // @5
				return window;
           		 } else {
				Thread.yield();
           		 }
       		 } else if (windowStart == old.windowStart()) { // @6
			return old;
       		 } else if (windowStart > old.windowStart()) {  // @7
			if (updateLock.tryLock()) {
               			 try {
					return resetWindowTo(old, windowStart);
                		} finally {
					updateLock.unlock();
              			}
           		 } else {
				Thread.yield();
            		}
        	} else if (windowStart < old.windowStart()) { // @8
            		return new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
        	}
    	}
}

代码@1:盘算当前时间会落在一个采集距离 ( LeapArray ) 中哪一个时间窗口中,即在 LeapArray 中属性 AtomicReferenceArray <WindowWrap< T>> array 的下标。实在现算法如下:

  • 首先用当前时间除以一个时间窗口的时间距离,得出当前时间是多少个时间窗口的倍数,用 n 示意。
  • 然后我们可以看出从一系列时间窗口,从 0 最先,一起向前转动 n 隔获得当前时间戳代表的时间窗口的位置。现在我们要定位到这个时间窗口的位置是落在 LeapArray 中数组的下标,而一个 LeapArray 中包罗 sampleCount 个元素,要获得其下标,则使用 n % sampleCount 即可。

代码@2:盘算当前时间戳所在的时间窗口的最先时间,即要盘算出 WindowWrap 中 windowStart 的值,实在就是要算出小于当前时间戳,并且是 windowLengthInMs 的整数倍最大的数字,Sentinel 给出是算法为 ( timeMillis - timeMillis % windowLengthInMs )。

代码@3:实验从 LeapArray 中的 WindowWrap 数组查找指定下标的元素。

代码@4:若是指定下标的元素为空,则需要建立一个 WindowWrap 。 其中 WindowWrap 中的 MetricBucket 是挪用其抽象方式 newEmptyBucket (timeMillis),由差别的子类去实现。

代码@5:这里使用了 CAS 机制来更新 LeapArray 数组中的 元素,由于同一时间戳,可能有多个线程都在获取当前时间窗口工具,但该时间窗口工具还未建立,这里就是制止建立多个,导致统计数据被笼罩,若是用 CAS 更新乐成的线程,则返回新建好的 WindowWrap ,CAS 设置不乐成的线程继续跑这个流程,然后会进入到代码@6。

代码@6:若是指定索引下的时间窗口工具不为空并判断起始时间相等,则返回。

代码@7:若是原先存在的窗口最先时间小于当前时间戳盘算出来的最先时间,则示意 bucket 已被弃用。则需要将最先时间重置到新时间戳对应的最先时间戳,重置的逻辑将在下文详细先容。

代码@8:应该不会进入到该分支,由于当前时间算出来时间窗口不会比之前的小。

2.2.3 isWindowDeprecated() 详解

接下来我们来看一下窗口的过时机制。

public boolean isWindowDeprecated(/*@NonNull*/ WindowWrap<T> windowWrap) {
    return isWindowDeprecated(TimeUtil.currentTimeMillis(), windowWrap);
}
public boolean isWindowDeprecated(long time, WindowWrap<T> windowWrap) {
	return time - windowWrap.windowStart() > intervalInMs;
}

判断滑动窗口是否生效的依据是当系统时间与滑动窗口的最先时间戳的距离大于一个采集时间,即示意过时。即从当前窗口最先,通常包罗的有用窗口为 sampleCount 个有用滑动窗口。

2.2.4 getPreviousWindow() 详解

凭据当前时间获取前一个有用滑动窗口,其代码如下:

public WindowWrap<T> getPreviousWindow(long timeMillis) {
    if (timeMillis < 0) {
		return null;
    }
    int idx = calculateTimeIdx(timeMillis - windowLengthInMs); // @1
    timeMillis = timeMillis - windowLengthInMs;
    WindowWrap<T> wrap = array.get(idx);
    if (wrap == null || isWindowDeprecated(wrap)) {                 // @2
		return null;
    }
   if (wrap.windowStart() + windowLengthInMs < (timeMillis)) {   // @3
		return null;
    }
    return wrap;
}

实在现的要害点如下:
代码@1:用当前时间减去一个时间窗口距离,然后去定位所在 LeapArray 中 数组的下标。
代码@2:若是为空或已过时,则返回 null。
代码@3:若是定位的窗口的最先时间再加上 windowLengthInMs 小于 timeMills ,说明失效,则返回 null,通常是不会走到该分支。

2.2.5 滑动窗口图示

经由上面的剖析,虽然另有一个焦点方式 (resetWindowTo) 未举行剖析,但我们应该可以画出滑动窗口的实现的实现原理图了。

接下来对上面的图举行一个简朴的说明:下面的示例以采集距离为 1 s,抽样次数为 2。

首先会建立一个 LeapArray,内部持有一个数组,元素为 2,一最先举行采集时,数组的第一个,第二个下标都市 null,例如当前时间经由 calculateTimeIdx 定位到下标为 0,此时没有滑动窗口,会建立一个滑动窗口,然后该滑动窗口会采集指标,随着进入 1s 的后500ms,后会建立第二个抽样窗口。

然后时间前进 1s,又会定位到下标为 0 的地方,但此时不会为空,由于有上一秒的采集数据,故需要将这些采集数据抛弃 ( MetricBucket value ),然后重置该窗口的 windowStart,这就是 resetWindowTo 方式的作用。

在 ArrayMetric 的组织函数泛起了 LeapArray 的两个实现类型 BucketLeapArray 与 OccupiableBucketLeapArray。

其中 BucketLeapArray 比较简朴,在这里就不深入研究了, 我们接下来将重点探讨一下 OccupiableBucketLeapArray 的实现原理,即支持抢占未来的“令牌”。

3、OccupiableBucketLeapArray 详解

所谓的 OccupiableBucketLeapArray ,实现的头脑是当前抽样统计中的“令牌”已耗尽,即到达用户设定的相关指标的阔值后,可以向下一个时间窗口,即借用未来一个采样区间。接下来我们详细来探讨一下它的焦点实现原理。

3.1 类图
邯郸县:源码剖析 Alibaba sentinel 滑动窗口实现原理(文末附原理图) 第1张
我们重点关注一下 OccupiableBucketLeapArray 引入了一个 FutureBucketLeapArray 的成员变量,其命名叫 borrowArray,即为借用的意思。

3.2 组织函数

public OccupiableBucketLeapArray(int sampleCount, int intervalInMs) {
    super(sampleCount, intervalInMs);
    this.borrowArray = new FutureBucketLeapArray(sampleCount, intervalInMs);
}

从组织函数可以看出,不仅建立了一个通例的 LeapArray,对应一个采集周期,还会建立一个 borrowArray ,也会包罗一个采集周期。

3.3 newEmptyBucket

public MetricBucket newEmptyBucket(long time) {
	MetricBucket newBucket = new MetricBucket();   // @1
	MetricBucket borrowBucket = borrowArray.getWindowValue(time);  // @2
	if (borrowBucket != null) {  
		newBucket.reset(borrowBucket);  
	}
	return newBucket;
}

我们知道 newEmptyBucket 是在获取当前窗口时,对应的数组下标为空的时会建立。
代码@1:首先新建一个 MetricBucket。
代码@2:在新建的时刻,若是曾经有借用过未来的滑动窗口,则将未来的滑动窗口上网络的数据 copy 到新建立的采集指标上,再返回。

3.4 resetWindowTo

protected WindowWrap<MetricBucket> resetWindowTo(WindowWrap<MetricBucket> w, long time) {      
    w.resetTo(time);
    MetricBucket borrowBucket = borrowArray.getWindowValue(time);
    if (borrowBucket != null) {
        w.value().reset();
        w.value().addPass((int)borrowBucket.pass());
    } else {
        w.value().reset();
    }
    return w;
}

遇到过时的滑动窗口时,需要对滑动窗口举行重置,这里的思绪和 newEmptyBucket 的焦点头脑是一样的,即若是存在已借用的情形,在重置后需要加上在未来已使用过的允许,就不逐一展开了。

3.5 addWaiting

public void addWaiting(long time, int acquireCount) {
	WindowWrap<MetricBucket> window = borrowArray.currentWindow(time);
	window.value().add(MetricEvent.PASS, acquireCount);
}

经由上面的剖析,先做一个勇敢的预测,该方式应该是当前滑动窗口中的“令牌”已使用完成,借用未来的令牌。将在下文给出证实。

滑动窗口的实现原理就先容到这里了。人人可以根据上面的代码连系下图做一个明白。
邯郸县:源码剖析 Alibaba sentinel 滑动窗口实现原理(文末附原理图) 第2张

思考题,人人可以画一下 OccupiableBucketLeapArray 滑动窗口的图示。这部分内容也将在我的【中间件知识星球】中与列位星友一起探讨,迎接人人的加入。

推荐阅读:源码剖析 Alibaba Sentinel 专栏。
1、Alibaba Sentinel 限流与熔断初探(技巧篇)
2、源码剖析 Sentinel 之 Dubbo 适配原理

作者信息:丁威,《RocketMQ手艺内幕》作者,现在担任中通科技手艺平台部资深架构师,维护 中间件兴趣圈民众号,现在主要揭晓了源码阅读java聚集、JUC(java并发包)、Netty、ElasticJob、Mycat、Dubbo、RocketMQ、mybaits等系列源码。点击链接:加入笔者的知识星球,一起探讨高并发、分布式服务架构,分享阅读源码心得。

,

进入sunbet亚洲官网

欢迎进入sunbet亚洲官网!Sunbet 申博提供申博开户(sunbet开户)、SunbetAPP下载、Sunbet客户端下载、Sunbet代理合作等业务。

皇冠体育声明:该文看法仅代表作者自己,与本平台无关。转载请注明:邯郸县:源码剖析 Alibaba sentinel 滑动窗口实现原理(文末附原理图)

网友评论

  • (*)

最新评论

文章归档

    站点信息

    • 文章总数:516
    • 页面总数:0
    • 分类总数:8
    • 标签总数:840
    • 评论总数:172
    • 浏览总数:2692