016-尚硅谷-Sentinel核心源码解析-滑动时间窗算法原理

好，呃，这个整体流程源码我们看过以后啊，下边。嗯，我们就来看。具体的这个滑动时间窗算法。但在看这个实验算算法之前啊，我们我们先要把这个原理搞明白了，然后再来说这个圆码的问题。嗯，这个原理是这样的，就是我们我们要想理解这个滑动时间窗。啊，限流算法，我们首先先要理解一下这个时间窗限流算法。给大家做了一些动画。咱们来看。看看这是时间窗限流算法啊，那么我这里边先规定好了，我的阈值是100。啊预值那QPS啊是100，然后呢，时间窗呃，长度是10T，那这个T是多少，你随便想让它，你认为它是多少就是多少，反正就十个时间单位。

然后呢，系统是这样的。它会系统启动以后啊，它会把这个时间啊，它会自动选一个。呃，时间窗口的起始零点啊，从这开始计时。按照你这个时间窗实T。大小在时间轴上给你分。就分成啊，这若干个这种这种时间窗口了，你想他吧，这十题到20题，这是一个实验窗。你看这现在是三个实验窗，然后呢，它会分别统计这些实验窗在里边，这个QPS。呃，比如说啊，比如说呃，或者咱们这样说吧，这个不是QPS这个假设就是数量吧。请求的数量啊，这样好理解。那么我我我就是这个时间窗内啊，呃，你那个请求数量是100。

啊，你不能超100，那如果在这个时间窗内，它是60。那那意味着这里边儿没有被限流，所有的请求全部通过了。二是80，那也全部通过了，就120。那这里边儿会有20个请求是没有通过的。对吧。那具体具体来说，当一个请求到达的时候啊，怎么样能判断它通过还是不通过，其实这个很简单，我们刚才讲过类似的东西。比如说。那就。这个请求到这儿是吧。很难的。嗯。换个颜色啊。啊，假设在这个时间。在这个时间点啊，到来一个请求，那这个请求能不能通过呢。

那你就他就在这个时间窗，他就现在他就看一下截止到目前，哎，我一共有多少请求啊，一看啊，这才40个了，没问题就通过了。然后又来一个请求，哎，再统计一下，这这这才50个了，没问题，那这些请求都能通过。他就是这样的。那这就是我们的时间窗线流算法。这个这种算法啊，其实看起来吧，倒好像没有啥问题，对吧。但实际上，这里面存在这样的一个问题。大家看假设啊。我这两边不是60吗？这60怎么来的？10T到16T的时候。这就来了十个请求。26T到20T的时候，我这来了50个请求。但你不管怎么样，十个50个，所以这这些请求从这开始算的话，这些请求都是能够通过的啊。

那这80个是怎么组成的呢？20题到26题。来了60个请求。然后26T到30T来了20个请求，这是80个整体，是不是在这个时间窗内也没有超过100这个阈值，所以他也都能通过。但是大家注意你看。从16T到26T。这是不是也是实体一个时间长。他到达的请求数量是多少？是110。实际上是超过阈值的。那按理说这里边儿实际上有的请求应该通不过才对。可是你要按照固这这种这种时间窗线流算法，或者说这叫固定时间窗线路算法，你的时间窗是固定死的。

他是能够通过的。所以他这边就存在这样这样一些这样一个问题。哎，有哥们说了，那你别管他，你中间他。反正人家在这个时间窗内没有超，在这个时间窗内也没有超，那你就让他通过呗。你注意啊。我们限流的目的是什么？我们限流的目的就是为了防止在某个时间段内。这个。突然间流量增加了。这种突发流量。突发流量有可能会引发什么猪血崩啊？所以你对于系统来说，实际上并不是指的你在某一个时间段内，你不要出现啊，超过阈值的，而在任意时间段内，而不是某一个这任意时间段内。你都不能超过这个阈值。这样的话才能提到。保护系统的作用。

所以这就是这种固定时间窗线路算法它存在的问题。那既然固定的它出问题了，那那怎么解决，我们让它不固定，哎，这就是滑动时间窗线了算法。他是怎么样做的啊，他是这样做的。我这个时间窗啊，不是固定死的。我这个时间是随着时间的推移。一直在动，你看到没，一直在动。什么意思呢？比如说。现在啊，就在这这在这个时间点上啊。到来一个请求，那这个请求能不能通过，我们就以它为例来分析啊，这个请求能能通过不能。是吧，我就查看一下，从这开始往前数。在这段时间，这正好也是个时间窗啊，刚才不是从这十题20题挪过来的吗？所以这就是个时间窗，那么这个时间窗里边你一共现在有多少？

请数量的请求你看哦。81共有80个，所以他能不能通过可以。他是可以通过的。然后呢，哎，他就通过了，紧接着时间又往前走，走走走到这儿，诶到这又来个请求。这。这请求能通过，不能。那那你得看一下，从这个时间点往前推，推一个时间窗，看一下这个里边统计一下这个里边有多少。数量的请求。你统计108，那不行了。这就。不能通过，这个请求是不能通过的，其实不光这个请求不能通过，那前面是不是。有八个请求，是不是都没通过呀，这是第九个。都没有通过。那这样的话，那是这这这是不是就把刚才那个问题解决了，就我们这种采用的这种滑动时间窗限流算法。

他统计的数据都是非常准确的。是不是都是非常准确的。所以在任意时间段他都不会出现。啊，这个这个通过预知的情况，那就保护了系统。可是。这个问题解决了，他又出现了新的问题。什么问题？大家看一下啊，你看现在这个滑动时间窗算法，它有什么问题。看看。这是我们这两个。分一点啊，分点一分点二。是吧，那。在分1.1的时候是这儿到这儿。从这开始到这结束是吧？啊，这是A点一的时候啊，这个请求能到不能，呃，能能能通过不能啊。

他要把整个从这到这所有的请求。是吧，数据进行一个统计。你得统计一遍啊。然后呢，紧接着。换个颜色。从这。到这儿是吧，这个请求到了，你说这个请求能过不能啊，啊，他要统计一下。这段。这个这个这个这个这个呃，停车的数量。大家想一下啊，你要做统计。这意味着什么？意意味着你得，你得计算的你得。消耗系统资源的，就从这儿到这儿。和从那到这，这都得去统计。那大家想一下，如果假设啊，这两个时间中间间隔非常非常小。

多少0.01T？0.01就1%啊，0.01。呃。T。那意味着什么？意味着整个镇里边儿。整个这里边儿。是不是99%的。都是重复的。而这个重复，你必须要重复统计。也就意味着什么，就是说这中间。全部这些工作，这个统计工作实际上是重复统计的。那这是什么？这就会带来很大的效率问题，因为请求高，这就主要为了防止高并发嘛，高并发是什么意思？一秒钟里边到达的请求数量非常庞大。那那那那你想想这么庞大的这种数据，你让他去往那儿重复性的统计。

所以它就带来了效率的问题了。所以，那这个问题又如何解决呢？他的解决方案。大家看啊，他的解决方案，这个解决方案稍微。嗯，理解起来啊，稍微有点复杂有点。有点有点不好理解啊，他是这样做的。首先呢，把整个这个时间轴。我给你划分成什么？这边又出现一种窗口，叫样本窗口。这每一个小格就是一个样本窗口，你注意我现在这儿说了样本窗口。长度是中是25T，你注意啊，现在这变了啊，这100这100T200T。这中间一共是100啊。啊，这每一个都是25对吧。然后呢？

嗯，我的时间窗是100T。然后单位时间窗样本数是四，就是我这个一个时间窗里边有四个样本窗口。就我这个样本窗口啊，长度要小于我们的。呃，这个时间窗，当然你要等于的话。不可能大于啊，要是等于的话，那实际上就变成了固定。实验长限量算法。所以我们要让小于，所以你看我这是四四个。四个的话。Hey。大的原理是什么意思啊，我们看这它大的原理其实也比较简单。就是我把这一个时间窗我跟你。分了。大家看我分成几块了，比如说从这到这儿。

咱们现在说的它啊。这个到这个，这是一个实验床。我这个人窗里边啊，给你分成了这样的几块，从那到这一块。两块。三块。四块五块假设啊，这几块长度是一样的啊，我画的这个不一样的，假设长度是一样的，那大家想一下。他怎么就解决了问题了？那这里边儿我。分1.1的时候，我统计是不是从这到这几个样本。样本窗口12345这五个样本窗口对吧。然后A点二的时候。统计几个样本窗口也是五个，哪五个1234变成这个。是配上这个五个。那他们重复的是几个，重复的中间这四个，这四个样本窗口。你里边已经有了多少的请求了，我都给你算好了。

你需要你这儿需要直接把这个数往下一加，就拿过来就有了，你需要把这四个数拿往这一加就有了，不用再重新统计了，都是统计好的。他就是这样解决的，这个思路就是这样的。我把窗口再给你分，分成什么？分成了样本窗口。分出来这这么多样本窗口。这样的话，这就问题就好解决了。这个问题就讲，那那现在咱们来举个例子啊，再举个例子。假设啊，嗯。这是125，在这125，假设这个一百三对吧，这个请求啊，在一百三的时候，我来第一个请求，你注意这是第一个请求啊，哎，那我就来了。啊，这个请求啊，过来以后。我算一下，我这儿给你弄一个。

数组，这数组长度是几？是四和这个样本窗口的。长度是一样的，是四。然后呢，你不是一百三吗？啊，我算出来你是在这儿呢，我就把你这个数给你加到这个A1上。那他这就增加了一了，那这个呢，原来没有，那它就是零。它就是零。然后呢？这个这个这个。继续啊，比如说又又又来了几个请求啊，在。这不是一百五吗？在一百五之前又来了几个请求，你来了我就加到他上面，来了就加到他上。是吧？啊，这请求一直来往上加到一百五了，我统计好这个数，那这个数就固定死了，A1就都就就固定固定了，因为时间已经过去一百五了，又到比如说100。啊，一百六那是在这里边的，在这个A2里边的，它的数据就已经固定了。

然后再来一个，我加到A2了，再来一个加到A2，再来一个加到A2。诶，当时间到了这儿了。这是175。是吧，过了175了，到一百八了。那它里边的数据也就固定了。到一百八了，过来一个请求，这个请求能不能通过呢？那好说呀。那我就从这儿开始。从这个时间点开始，你注意啊，我先。计算。我现在计算这个请求。他。在哪个。它在每一个呃时间窗。就从这儿开始，它这个实验窗啊，你注意它必须是什么，是这样的，他先说他在先计算啊，它在哪个样本窗口，一计算在这个样本窗口。再计算它在这个样本窗口里边。

这样本窗口在哪个时间窗。在哪个时间窗，怎么怎么就在哪个时间窗了。在这儿是吧，在这儿，然后呢，往前数就要往前数了。你在这个样本窗口那就算好了，我就从这儿到到这这段这个起起始时间我能算出来呀，是吧，哎，我算开这现在有几个请求。我我这个数就有了，然后再往前数，这不是一个吗？数几个，我长度是四啊，再往前数三个，拿一个两个，三个，把这三个。数拿过来配上它，加一块一算哦。超了100了没有，超这个100了没有，没有，那这个请求就可以通过。是不是这个意思，就是你这里边记得这个东西啊，记录的这个东西看什么。

就不用再统计了，只要这个时间点过去了。那么这个数就记到这儿了。你下一次想用的时候，直接把它拿过来就可以了。给你拿过来就可以了。所以。那这就是，哎。这就是这个改进他的一个思路。当然这个总体思路有了啊，后期我们后边要读这个源码的时候呢，嗯，他实际上实现起来要复杂，要比较复杂一些，但整体原理就是这样一个原理。那我们先理解一下啊，这个这个这个什么是啊，滑动时间窗。是吧，把这个原理先理解了啊。