区块链技术博客
www.b2bchain.cn

源码解读四:滑动窗口数据统计求职学习资料

本文介绍了源码解读四:滑动窗口数据统计求职学习资料,有助于帮助完成毕业设计以及求职,是一篇很好的资料。

对技术面试,学习经验等有一些体会,在此分享。

源码解读四:滑动窗口数据统计

  • 源码解读四:滑动窗口数据统计
    • 概述
    • 思路
    • 代码实现
      • LeapArray

概述

本篇章我们分析在 Sentinel 中的核心算法:滑动窗口数据统计算法。这是一个高性能的,应对写大于读场景的统计算法。流控的前提首先就是统计当前的访问数据,判断访问数据是否超过阈值,超过则触发一定的行为。这就是流控的基本逻辑。显然,这里面统计当前访问数据就是一个最为基础也是最为重要的事情。

在 Sentinel 中,统计访问数据是通过一种被命名为滑动窗口的数据结构来实现的。那下面,我们就来分析下这个滑动窗口的原理和代码实现。

思路

实现限流,需要解决的实际上是高性能的统计问题。只有高效的统计单位时间内的请求数量后,才能根据请求数量是否超出限制,来判断下一次请求是否被允许。

Sentinel 采用的是滑动窗口的方式。可以形象的想象为一条无限延展的时间线,上面有个窗口,窗口随着时间的进行不断的向前移动,访问数据落在时间轴上,在滑动窗口的范围内则是纳入统计的数据。可以用图的形式进行类比,以下是统计周期为 1S 的滑动窗口示意。

在 0~0.5S 的时候

源码解读四:滑动窗口数据统计

image-20201023000643449

在 0.5~1S 的时候

源码解读四:滑动窗口数据统计

image-20201023000619994

在 1~1.5S 的时候

源码解读四:滑动窗口数据统计

image-20201023000607233

在 1.5~2S 的时候

源码解读四:滑动窗口数据统计

image-20201023000718915

从时间窗口的滑动情况可以看出,在刚开始统计的时候,时间窗口还没有完整显露。在 0.5~1S 这个时间段,滑动窗口出现完整,并且随后不断向前滑动。窗口不断的向前滑动的过程,就是时间流逝的过程。这里面需要引入两个定义:

  • 统计周期
  • 窗口长度

统计周期,顾名思义,就是在多长的时间跨度内,对数据进行统计。比如上面的例子当中,统计周期就是 1S 。窗口长度,就是统计周期的精度。或者说,将统计周期等分之后的区块的长度。在上面的例子中,窗口长度就是 0.5S 。

统计周期是滑动窗口的总体长度,窗口长度是滑动窗口的移动间隔,也就是区块的长度。窗口长度这个词非常的不好,代表的含义和名称本身是不吻合的。但是为了和 Sentinel 中代码变量名windowLengthInMs保持一致,后续的文章中仍然使用窗口长度这个词。为了方便理解,后续我们将这个区块解释为取样窗口。也就是说,滑动窗口是由一系列等长连续的取样窗口构成的。

统计周期不用说明,自然是统计一段时间内的数据。窗口长度的作用,是让这个统计数据在发挥作用的时候,能够更加的平滑。

举个例子,如果统计周期和窗口长度都是 1S 。假定系统允许的 QPS 是 10。在 0.9S 的时刻发生了 10 个请求。当时间来到 1~2S 区间的时候,滑动窗口向前移动了,此时又可以再次发生 10 个请求。假定在 1.1S 的时刻发生了 10 个请求,这是被该滑动窗口所允许的。但是这样一来,实际上在 0.5~1.5S 这个时间段内,一共发生了 20 个请求,这实际上违背了 QPS 的限制要求。

如果在上面的例子中,统计周期不变仍然是 1S,但是窗口长度变为 0.5S ,情况则会变的不同。在 0.9S 的时刻发生了 10个请求,当时间来到 1~1.5S 的区间时,由于滑动窗口在 0.5~1S 的部分仍然有效,因此原本可以在 1.1S 这个时刻产生的请求现在不能产生了。这就避免了在 0.5~1.5S 这个时间区间的请求个数突破系统允许上限。

从例子可以看到,如果只有统计周期,对于突发流量是没有办法进行保障的。统计周期结合窗口长度,能产生的效果是任一在跨度为“统计周期 – 窗口长度”的时间范围内,请求不会超过系统限制。显然,统计周期越长,能够获取的有效数据的时间跨度就越大,但是需要存储的数据也是更多。窗口长度越短,对流量控制的时间范围就越大,但是计算的压力也是更大。

代码实现

说过了滑动窗口实现的思路,来看下具体的代码实现。首先来看下类图

源码解读四:滑动窗口数据统计

LeapArray

这是统计类的基类,统计和计算功能都在这个类当中实现了。而不同的子类,在细微的功能差别上实现了区别。

首先来看下初始化的要素。在初始化的时候,传入两个参数intervalInMssampleCount。前者就是统计周期,后者是统计周期的取样个数。前者除以后者就能得到取样窗口长度。显然,一个跨度为intervalInMs的滑动窗口是由sampleCount个取样窗口构成。创建一个长度为sampleCount的由取样窗口构成的数组就可以代表滑动窗口。

下面是LeapArray的属性,如下

protected int sampleCount;//取样个数 protected int intervalInMs;//统计周期 protected int windowLengthInMs;//窗口长度,通过统计周期除以取样个数得到 protected final AtomicReferenceArray<WindowWrap<T>> array;//整个数组代表着滑动窗口

WindowWrap是取样窗口,其存储着 3 个属性,如下

private final long windowLengthInMs;//窗口长度 private long windowStart;//本取样窗口的起始时间戳 private T value;//取样窗口的统计数据

在框架启动的时候,窗口长度就是固定的,所以这里是final进行修饰。每一个取样窗口都代表着一段时间,所以每一个窗口都有一个时间起始点时间戳,也就是windowStart。而这段时间内统计的数据内容,就用value来存储。WindowWrap是一个泛型类,将存储的统计类内容交给外部来定制。目前代码中有几种使用:

  • MetricBucket,统计流控测量事件。该类本身存储好几种统计信息,包含响应时间、成功次数、错误次数等。
  • SimpleErrorCounter,统计错误次数。
  • SlowRequestCounter,统计慢请求次数。

源码解读四:滑动窗口数据统计

  • 源码解读四:滑动窗口数据统计
    • 概述
    • 思路
    • 代码实现
      • LeapArray

概述

本篇章我们分析在 Sentinel 中的核心算法:滑动窗口数据统计算法。这是一个高性能的,应对写大于读场景的统计算法。流控的前提首先就是统计当前的访问数据,判断访问数据是否超过阈值,超过则触发一定的行为。这就是流控的基本逻辑。显然,这里面统计当前访问数据就是一个最为基础也是最为重要的事情。

在 Sentinel 中,统计访问数据是通过一种被命名为滑动窗口的数据结构来实现的。那下面,我们就来分析下这个滑动窗口的原理和代码实现。

思路

实现限流,需要解决的实际上是高性能的统计问题。只有高效的统计单位时间内的请求数量后,才能根据请求数量是否超出限制,来判断下一次请求是否被允许。

Sentinel 采用的是滑动窗口的方式。可以形象的想象为一条无限延展的时间线,上面有个窗口,窗口随着时间的进行不断的向前移动,访问数据落在时间轴上,在滑动窗口的范围内则是纳入统计的数据。可以用图的形式进行类比,以下是统计周期为 1S 的滑动窗口示意。

在 0~0.5S 的时候

源码解读四:滑动窗口数据统计

image-20201023000643449

在 0.5~1S 的时候

源码解读四:滑动窗口数据统计

image-20201023000619994

在 1~1.5S 的时候

源码解读四:滑动窗口数据统计

image-20201023000607233

在 1.5~2S 的时候

源码解读四:滑动窗口数据统计

image-20201023000718915

从时间窗口的滑动情况可以看出,在刚开始统计的时候,时间窗口还没有完整显露。在 0.5~1S 这个时间段,滑动窗口出现完整,并且随后不断向前滑动。窗口不断的向前滑动的过程,就是时间流逝的过程。这里面需要引入两个定义:

  • 统计周期
  • 窗口长度

统计周期,顾名思义,就是在多长的时间跨度内,对数据进行统计。比如上面的例子当中,统计周期就是 1S 。窗口长度,就是统计周期的精度。或者说,将统计周期等分之后的区块的长度。在上面的例子中,窗口长度就是 0.5S 。

统计周期是滑动窗口的总体长度,窗口长度是滑动窗口的移动间隔,也就是区块的长度。窗口长度这个词非常的不好,代表的含义和名称本身是不吻合的。但是为了和 Sentinel 中代码变量名windowLengthInMs保持一致,后续的文章中仍然使用窗口长度这个词。为了方便理解,后续我们将这个区块解释为取样窗口。也就是说,滑动窗口是由一系列等长连续的取样窗口构成的。

统计周期不用说明,自然是统计一段时间内的数据。窗口长度的作用,是让这个统计数据在发挥作用的时候,能够更加的平滑。

举个例子,如果统计周期和窗口长度都是 1S 。假定系统允许的 QPS 是 10。在 0.9S 的时刻发生了 10 个请求。当时间来到 1~2S 区间的时候,滑动窗口向前移动了,此时又可以再次发生 10 个请求。假定在 1.1S 的时刻发生了 10 个请求,这是被该滑动窗口所允许的。但是这样一来,实际上在 0.5~1.5S 这个时间段内,一共发生了 20 个请求,这实际上违背了 QPS 的限制要求。

如果在上面的例子中,统计周期不变仍然是 1S,但是窗口长度变为 0.5S ,情况则会变的不同。在 0.9S 的时刻发生了 10个请求,当时间来到 1~1.5S 的区间时,由于滑动窗口在 0.5~1S 的部分仍然有效,因此原本可以在 1.1S 这个时刻产生的请求现在不能产生了。这就避免了在 0.5~1.5S 这个时间区间的请求个数突破系统允许上限。

从例子可以看到,如果只有统计周期,对于突发流量是没有办法进行保障的。统计周期结合窗口长度,能产生的效果是任一在跨度为“统计周期 – 窗口长度”的时间范围内,请求不会超过系统限制。显然,统计周期越长,能够获取的有效数据的时间跨度就越大,但是需要存储的数据也是更多。窗口长度越短,对流量控制的时间范围就越大,但是计算的压力也是更大。

代码实现

说过了滑动窗口实现的思路,来看下具体的代码实现。首先来看下类图

源码解读四:滑动窗口数据统计

LeapArray

这是统计类的基类,统计和计算功能都在这个类当中实现了。而不同的子类,在细微的功能差别上实现了区别。

首先来看下初始化的要素。在初始化的时候,传入两个参数intervalInMssampleCount。前者就是统计周期,后者是统计周期的取样个数。前者除以后者就能得到取样窗口长度。显然,一个跨度为intervalInMs的滑动窗口是由sampleCount个取样窗口构成。创建一个长度为sampleCount的由取样窗口构成的数组就可以代表滑动窗口。

下面是LeapArray的属性,如下

protected int sampleCount;//取样个数 protected int intervalInMs;//统计周期 protected int windowLengthInMs;//窗口长度,通过统计周期除以取样个数得到 protected final AtomicReferenceArray<WindowWrap<T>> array;//整个数组代表着滑动窗口

WindowWrap是取样窗口,其存储着 3 个属性,如下

private final long windowLengthInMs;//窗口长度 private long windowStart;//本取样窗口的起始时间戳 private T value;//取样窗口的统计数据

在框架启动的时候,窗口长度就是固定的,所以这里是final进行修饰。每一个取样窗口都代表着一段时间,所以每一个窗口都有一个时间起始点时间戳,也就是windowStart。而这段时间内统计的数据内容,就用value来存储。WindowWrap是一个泛型类,将存储的统计类内容交给外部来定制。目前代码中有几种使用:

  • MetricBucket,统计流控测量事件。该类本身存储好几种统计信息,包含响应时间、成功次数、错误次数等。
  • SimpleErrorCounter,统计错误次数。
  • SlowRequestCounter,统计慢请求次数。

源码解读四:滑动窗口数据统计

  • 源码解读四:滑动窗口数据统计
    • 概述
    • 思路
    • 代码实现
      • LeapArray

概述

本篇章我们分析在 Sentinel 中的核心算法:滑动窗口数据统计算法。这是一个高性能的,应对写大于读场景的统计算法。流控的前提首先就是统计当前的访问数据,判断访问数据是否超过阈值,超过则触发一定的行为。这就是流控的基本逻辑。显然,这里面统计当前访问数据就是一个最为基础也是最为重要的事情。

在 Sentinel 中,统计访问数据是通过一种被命名为滑动窗口的数据结构来实现的。那下面,我们就来分析下这个滑动窗口的原理和代码实现。

思路

实现限流,需要解决的实际上是高性能的统计问题。只有高效的统计单位时间内的请求数量后,才能根据请求数量是否超出限制,来判断下一次请求是否被允许。

Sentinel 采用的是滑动窗口的方式。可以形象的想象为一条无限延展的时间线,上面有个窗口,窗口随着时间的进行不断的向前移动,访问数据落在时间轴上,在滑动窗口的范围内则是纳入统计的数据。可以用图的形式进行类比,以下是统计周期为 1S 的滑动窗口示意。

在 0~0.5S 的时候

源码解读四:滑动窗口数据统计

image-20201023000643449

在 0.5~1S 的时候

源码解读四:滑动窗口数据统计

image-20201023000619994

在 1~1.5S 的时候

源码解读四:滑动窗口数据统计

image-20201023000607233

在 1.5~2S 的时候

源码解读四:滑动窗口数据统计

image-20201023000718915

从时间窗口的滑动情况可以看出,在刚开始统计的时候,时间窗口还没有完整显露。在 0.5~1S 这个时间段,滑动窗口出现完整,并且随后不断向前滑动。窗口不断的向前滑动的过程,就是时间流逝的过程。这里面需要引入两个定义:

  • 统计周期
  • 窗口长度

统计周期,顾名思义,就是在多长的时间跨度内,对数据进行统计。比如上面的例子当中,统计周期就是 1S 。窗口长度,就是统计周期的精度。或者说,将统计周期等分之后的区块的长度。在上面的例子中,窗口长度就是 0.5S 。

统计周期是滑动窗口的总体长度,窗口长度是滑动窗口的移动间隔,也就是区块的长度。窗口长度这个词非常的不好,代表的含义和名称本身是不吻合的。但是为了和 Sentinel 中代码变量名windowLengthInMs保持一致,后续的文章中仍然使用窗口长度这个词。为了方便理解,后续我们将这个区块解释为取样窗口。也就是说,滑动窗口是由一系列等长连续的取样窗口构成的。

统计周期不用说明,自然是统计一段时间内的数据。窗口长度的作用,是让这个统计数据在发挥作用的时候,能够更加的平滑。

举个例子,如果统计周期和窗口长度都是 1S 。假定系统允许的 QPS 是 10。在 0.9S 的时刻发生了 10 个请求。当时间来到 1~2S 区间的时候,滑动窗口向前移动了,此时又可以再次发生 10 个请求。假定在 1.1S 的时刻发生了 10 个请求,这是被该滑动窗口所允许的。但是这样一来,实际上在 0.5~1.5S 这个时间段内,一共发生了 20 个请求,这实际上违背了 QPS 的限制要求。

如果在上面的例子中,统计周期不变仍然是 1S,但是窗口长度变为 0.5S ,情况则会变的不同。在 0.9S 的时刻发生了 10个请求,当时间来到 1~1.5S 的区间时,由于滑动窗口在 0.5~1S 的部分仍然有效,因此原本可以在 1.1S 这个时刻产生的请求现在不能产生了。这就避免了在 0.5~1.5S 这个时间区间的请求个数突破系统允许上限。

从例子可以看到,如果只有统计周期,对于突发流量是没有办法进行保障的。统计周期结合窗口长度,能产生的效果是任一在跨度为“统计周期 – 窗口长度”的时间范围内,请求不会超过系统限制。显然,统计周期越长,能够获取的有效数据的时间跨度就越大,但是需要存储的数据也是更多。窗口长度越短,对流量控制的时间范围就越大,但是计算的压力也是更大。

代码实现

说过了滑动窗口实现的思路,来看下具体的代码实现。首先来看下类图

源码解读四:滑动窗口数据统计

LeapArray

这是统计类的基类,统计和计算功能都在这个类当中实现了。而不同的子类,在细微的功能差别上实现了区别。

首先来看下初始化的要素。在初始化的时候,传入两个参数intervalInMssampleCount。前者就是统计周期,后者是统计周期的取样个数。前者除以后者就能得到取样窗口长度。显然,一个跨度为intervalInMs的滑动窗口是由sampleCount个取样窗口构成。创建一个长度为sampleCount的由取样窗口构成的数组就可以代表滑动窗口。

下面是LeapArray的属性,如下

protected int sampleCount;//取样个数 protected int intervalInMs;//统计周期 protected int windowLengthInMs;//窗口长度,通过统计周期除以取样个数得到 protected final AtomicReferenceArray<WindowWrap<T>> array;//整个数组代表着滑动窗口

WindowWrap是取样窗口,其存储着 3 个属性,如下

private final long windowLengthInMs;//窗口长度 private long windowStart;//本取样窗口的起始时间戳 private T value;//取样窗口的统计数据

在框架启动的时候,窗口长度就是固定的,所以这里是final进行修饰。每一个取样窗口都代表着一段时间,所以每一个窗口都有一个时间起始点时间戳,也就是windowStart。而这段时间内统计的数据内容,就用value来存储。WindowWrap是一个泛型类,将存储的统计类内容交给外部来定制。目前代码中有几种使用:

  • MetricBucket,统计流控测量事件。该类本身存储好几种统计信息,包含响应时间、成功次数、错误次数等。
  • SimpleErrorCounter,统计错误次数。
  • SlowRequestCounter,统计慢请求次数。

部分转自互联网,侵权删除联系

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 源码解读四:滑动窗口数据统计求职学习资料
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们