技术实践第十期｜令牌桶算法在小程序数据采集中的应用
官方小二*更新于2022-3-18*
亲爱的开发者们，
🙋大家好，本期技术实践内容是由友盟+研发团队的云猫同学为开发者们倾情奉上：令牌桶算法在小程序数据采集中的应用。我们一起来看看吧！
✍️想要进行技术探讨的开发者们，欢迎大家在帖子下方踊跃留言哦！
🎩更多技术干货分享，请持续期待～
*作者：云猫*
可能有的同学会觉得小程序发送请求不就是调用一下wx.request就可以了吗，它能有多复杂，还涉及算法？这是肯定是过度设计！(没错，我就是要用高射炮打蚊子[傲娇脸.jpg])，实际上数据采集是一个非常特别的场景，往往数据以日志形式发送，在应用生命周期的任何时候都有可能产生不定数量和类型的日志，如果立即发送这些数据可能导致同时发送过多的请求，并有可能过度挤占用户的请求通道，如何优雅的去发送这些日志，是sdk开发同学需要特别注意的。
01 背景介绍
U-APM 应用性能监控平台这个场景需要采集大量的应用性能和错误数据，要求尽量减少对客户端性能的影响，又要尽可能的提高发送成功率，还要照顾到服务器压力成本。经过不断探索，最后受到服务端限流算法的启发，找到了一种在小程序客户端上可行的相对优雅的发送方案，本文就详细讲述了该方案的原理和关键思路。
02 令牌桶算法简介
限流算法是服务端高并发场景常用算法，常见的有令牌桶算法、漏桶算法、滑窗算算法、计数器算法等。令牌桶算法是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。
令牌桶有以下特点：
- 令牌按固定的速率被放入令牌桶中
- 当桶满时，新添加的令牌被丢弃或拒绝
- 如果桶中的令牌不足 ，且请求将被限流（丢弃或阻塞等待）,在sdk采集场景中考虑数据准确性，限流方式采取阻塞等待。
03 为什么要做客户端限流
通常大家提到限流，一般都会想到是服务端应对高并发策略，期望在有限的资源下更好的支持业务请求。通常来讲，限流也需要客户端来配合，主要有以下几点原因。
有限的客户端资源
客户端限流相比服务端限流，可以在流量到达服务端之前进行一定程度的控制，从而在一定程度上减小服务端的压力，并且把客户端的负载作为流控的因素可以充分利用客户端的空闲资源来尽快发送积压数据。
更低的服务端开销
虽然当前大数据云计算技术都有一定程度上的自动扩容能力，但如果不对请求进行限流，那么可能会出现单个客户端短时间发送过多的数据，损害整体服务性能，间接损害了其他用户的数据发送，另外客户端限流算法是利用端上的资源来实施，可以减小服务端实施限流的额外开销。
更精细的数据发送控制
可以根据不同类型的日志数据，适配不同的发送策略，并且对整个发送过程产生一定程度的流量削峰，流量平滑的作用。
更准确的流量峰值估算
有了客户端的限流，就可以比较准确评估单个客户端的发送极限，然后就可以根据客户端的接入量级来评估服务端的峰值。
04 为什么选择令牌桶算法
令牌桶算法相比其他算法，在控制发送速率的同时，同时兼顾了一定程度的突发数据的发送，换句话说就是， 宏观上看，数据是按照令牌生成的速度发送的，而局部又允许有条件的突发。这个优点使得sdk可以在发送队列积压后，在不突破发送限制（当前剩余令牌数和剩余的并发请求数）的前提下尽快发送数据。
05 落地方案
实际落地方案要比单纯的令牌桶算法更复杂一些，不过核心理念是相同的。在实现过程中，小程序并发需要控制在10个以内，另外需要对请求协议做优化，使得任意日志可以合并发送，并在一定的时间窗口内，对日志进行有条件(日志数量和大小)合并。最后再通过发送器，发送给服务端。但处于篇幅考虑，本文只对讲发送策略，不对日志合并策略进行详细阐述了，后续会发专门的文章来详细说明。以下是示意代码(去掉日志合并，与并发限制后)纯令牌桶的策略
let CUR_TICKET_COUNT = 5; // 当前桶中令牌数量
const MAX_TICKET_COUNT = 10; // 桶中最大令牌数量
const MIN_TICKET_COUNT = 0; // 桶中最小令牌数量
const SPEED = 5; // 令牌生成速度
const tasks = []; // 任务队列
// 令牌生成器
setInterval(() => {
if (CUR_TICKET_COUNT < MAX_TICKET_COUNT) {
CUR_TICKET_COUNT++;
}
}, 1000 / SPEED);
// 任务发送器
setInterval(() => {
while (tasks.length > 0 && CUR_TICKET_COUNT > MIN_TICKET_COUNT) {
CUR_TICKET_COUNT--;
tasks.pop()();
}
}, 1000 / SPEED);
令牌桶速率 v=5(每秒产生5个令牌)，令牌桶最大容量h=10(考虑到小程序容器最大并发为10)，桶内令牌数量c = 5 (初始令牌数量为5，考虑到0号日志需要在较早时机发送)，以及缓冲队列q
1.初始化令牌生成器，设置一个定时器每(1/v)秒生成1个令牌(c+1)，当令牌数量超过令牌桶容量h时，c = h
2. 初始化任务执行器，每(1/v)秒检查令牌数量c和缓冲队列q，如果有剩余令牌(c>0)并且缓冲队列q中有剩余任务，则依次取出任务，同时消耗一个令牌(c-1) , 然后执行任务
06 落地效果
模拟同时发送100条日志的场景
未采用限流算法的请求序列
可以看到1.6秒内连续发送了100个请求，导致用户的请求www.umeng.com 优先级很低，直到1.5秒后才开始加入进入请求队列，在真实场景下，将阻塞用户的业务接口1.5秒。
采用限流算法的请求序列
可以看到在开启限流后,前10个请求迅速消耗了桶里的令牌，此时令牌不足，进入阻塞等待队列，直到新的令牌生成，此时令牌消耗速度大于令牌生成速度，因此后续的请求将按照令牌生成速度，平均每秒4个请求，此时用户请求是可以正常发送不被阻塞，可以看到图中用户的业务请求www.umeng.com 的请求优先级要高于数据采集请求。
07 关于发送速度的思考
上面的实验可以清楚看到，实施限流后，在请求击穿桶容量h后，数据发送速度是明显低于同时发起大量请求。所以有的同学会认为这个方案会降低数据发送的速度，这个问题是客观存在的，但是鱼与熊掌不可兼得的情况下，我们实际发送前会对日志进行合并，大约每10条日志会被合并为一个请求，也即是说在突发情况下，每秒可以发送令牌桶容量的十倍的日志量(10h=100)，在平均情况下，每秒发送的日志量为10v=50条日志,这个是能够满足大多数的发送速度要求的。另外对于桶被击穿后的缓冲器的实现，可以加入本地缓存，进行持久化，因为限速导致的未能发送的数据，可以在下次启动时发送。
08 总结
令牌桶算法不仅可以用在服务端，而且非常适合应用于客户端数据采集场景，有这个领域需求的同学不妨尝试下这个限流算法。
🎩「往期精彩回顾」👉：
技术实践第九期｜前端开发：Vue.js中事件修饰符和按键修饰符的使用
技术实践第八期｜前端开发：JavaScript中数组去重的方法汇总
排队理论白话文；
想象一个小商店，只有一个柜台和一个浏览区域，一次只能有一个人在柜台，没有人不买东西就离开。所以系统大致是：
入口→浏览→柜台→出口
如果人们进入商店的速度（称为到达率）是他们离开的速度（称为退出率），则系统是稳定的。相比之下，到达率超过退出率将代表一个不稳定的系统，其中商店中等待的顾客数量将逐渐增加到无穷大。
利特尔定律告诉我们，商店L中的平均顾客数量是有效到达率 λ乘以顾客在商店W中花费的平均时间，或者简单地说：
{\displaystyle L=\lambda W}
假设客户以每小时 10 人的速度到达，平均停留 0.5 小时。这意味着我们应该找到商店中任何时候的平均顾客数量为 5。
{\displaystyle L=10\times 0.5=5}
现在假设商店正在考虑做更多的广告以将到达率提高到每小时 20 个。商店必须准备好接待平均 10 位顾客，或者必须将每位顾客在店内停留的时间减少到 0.25 小时。商店可以通过更快地结账或增加更多柜台来实现后者。
我们可以将利特尔定律应用于商店内的系统。例如，考虑计数器及其队列。假设我们注意到排队和柜台平均有 2 位顾客。我们知道到达率是每小时 10 人次，因此客户必须平均花费 0.2 小时退房。
{\displaystyle W={\frac {L}{\lambda }}={\frac {2}{10}}=0.2}
我们甚至可以将利特尔定律应用于柜台本身。柜台的平均人数将在 (0, 1) 范围内，因为一次最多只能有一个人在柜台。在这种情况下，柜台的平均人数也称为柜台的利用率。
但是，由于现实中的商店通常空间有限，因此最终会变得不稳定。如果到达率远大于退出率，商店最终将开始溢出，因此任何新到达的客户都将被拒绝（并被迫去其他地方或稍后再试），直到再次有可用空间在商店。这也是到达率和有效到达率之间的差异，其中到达率大致对应于顾客到达商店的速度，而有效到达率对应于顾客进入商店的速度。然而，在一个无限大小且没有损失的系统中，两者是相等的。