system design 俄罗斯大叔系列
限速
一个client忽然发送异常多的请求。
可能有很多原因：
测试人员在压测、流量高峰、恶意攻击
可能导致的问题：
他占用了大量cpu、内存、硬盘、网络IO资源
导致其它用户的请求产生高延迟或高失败率
所以要引入限速：要么延迟解决要么立刻拒绝
为什么不用自动化扩展？
因为有可能太慢，还没扩完就崩了
为什么不用LB来限速？
因为每个部件情况不一样有的快有的慢，LB不能识别。所以需要定制服务来限速
为什么一定要用分布式？不能各自服务器独立解决吗？
还是上面的原因，we will need a solution where application servers will communicate with each other and share information about how many client requests each one of them processed so far.
Requirements：
Functional：
- allowRequest(request)
- return boolean
Non-Functional:
- low latency:make decision as soon as possible
- accurate: as accurate as we can get
- scalable: supports an arbitrarily large number of hosts in the cluster
- 容错和高可用呢？不重要。如果不知道是否限速，就不限。
solution：
从简单的方案开始，逐渐扩展。
so ① rules retriever：
是一个后台进程，每个rule指定每秒允许的特定客户端的请求数，并轮询检查是否有新rule或修改
rule自己定义并存在数据库，并且通过一个web服务来管理操作。并在内存中有存储。
请求到来时，第一件事是建立一个client identifier = key，是该client的唯一标识。
然后key传到rate limiter，rate limiter根据cache里的rule检查key，
如果match，rate limiter会检查这个client最后的请求是否超速。
如果没超，request就move further；如果超了，就拒绝请求rejected。
这时有三种选项：
①response 特定的status code
②延迟处理
③直接丢掉
总结：
需要一个数据库来存规则，这个数据库需要crud
需要一个过程定期检索规则，并将它放入内存
需要一个做决定的组件。（构建client key要单独还是放一起都可以）
接下来的几个走向：：：
——> 算法：实现rate limiter算法
——> OOD: 定义这个库的主要类和接口
——> 分布式留解决方案，server之间如何共享数据
算法：
-
Google Guava RateLimiter
-
滑动窗口
-
令牌桶算法：最简单。好理解易于实现。
每个桶有：可容纳的最大令牌量，当前可用的令牌数，令牌加入桶的速率
有请求到来时，从桶中取一个令牌。如果没有，就拒绝请求。
并且桶用恒定的速率填充令牌。
类和接口：
JobScheduler: 负责调度job和从规则库里检索规则
RulesCache：负责将规则存储在内存中
ClientIdentifier：构建唯一标识客户端的密钥
RateLimiter：负责决策
distributed：
有一个问题是，假设初始有三个桶，整个系统要求是每秒上限是4，初始时【每个桶内需要有4！】因为它们不知道请求要去哪个桶
然后当消耗完四个，假设A桶剩1，B桶剩2，C桶剩1
这时【这三个桶需要互相知道它们总共已经消耗了四个！】，所以下一刻这三个桶都更新成剩余0。
这时有一个问题，如果在三个桶互通消息的时候，又有请求进来了怎么办。
可用修改桶，让它允许负数令牌存在。
比如这时来了12个请求，共享消息后每个桶有-8个令牌，那么接下来两秒内都不允许有请求了。
所以关键是共享信息
第一种：全网状广播：tell everyone everything
如何发现host？
①先择第三方服务，监听每个host的心跳，新的来了就注册，心跳停止就注销。
②解析特定用户的信息，有特别用户存了所有人的信息。
③通过配置文件提供主机列表。但是不太灵活，每次更新都要重新部署。
但是只适合小cluster。需要大量消息。
第二种：gossip protocal
随机的对等选择形式实现：每个机器随机跳另一台机器并共享数据。（雅虎）
异步是它的优点，
缺点：消息冗余，不适合用在对实时性要求较高的场景下
第三种：distributed cache
pros：distributed cache cluster相对较小，服务cluster可独立扩展，可在不同团队之间共享。
第四种：coordination service 单主
依赖第三方组件，帮助选择领导者的协调服务。
每个人消息都发给leader，leader计算并返回结果
pros：有助于减少集群内广播的消息数量
可以用paxos、raft等共识算法来实现coordination service
cons：必须维护这个协调系统，它很复杂，必须很可靠，而且要确保选出有且只有一个领导者
第五种：random leader selection
如果每个leader对得票率消息共享，可能过计算但就不会出现选出多个leader的情况。
communication protocals 通信协议：how hosts talk to each other
两种选择：TCP UDP
TCP：保证数据安全及按顺序传递。但慢。
UDP：不保证收到所有data也不保证数据。但快。
integrate 集成这些组件
两种
① rate limiter 作为服务进程的一部分运行
作为类的集合分发
pros：更快。无需进程间调用，也就没有进程调用失败。
cons: 👇
② rate limiter 作为它自己的进程运行
两个库：守护进程本身和客户端，client和服务代码集成在一起 integrate
pros：可用不同的语言编写（守护进程而不是client），不用在代码级别集成。
有自己的内存空间，可用更好的控制服务和守护进程，内存分配可预测。
当有一个与集群种其它主机通信的守护进程时，很好用。
cons: 👆qi
其它：
如果有大量请求，是否会有大量桶在内存当中？
如果没有请求，可以不用把桶保存在内存里。请求间隔时常短时就创建放进内存，否则就删掉。
故障模式 failure scenarios：
守护进程fail，导致集群中其它主机无法看的这个失败的守护进程。所以这个机器失联了，但仍然继续执行任务。只是限制的请求更少罢了。
（通信：all 只允许4个。无法通信：每个允许4个，一共12个）
rule的管理：
需要引入一个自助服务工具，以便增删改rules
同步：synchronization
令牌桶中需要同步。更好的办法是在这个类中实现线程安全，like原子引用
令牌桶缓存需要同步，当删除不用桶、建立新桶时，会最终同步。所以需要用concurrentHashMap （线程安全）
大部分服务不会请求那么大，所以同步这一块不会增加太多开销成为瓶颈
client 应如何处理受限制的调用呢
重试。丢进队列。
exponential backoff and jitter 指数退避和抖动：
多次重试请求，但每次重试都等待更长的时间。
抖动增加了重试间隔的随机性以分散负载
最终选择：
小 cluster <x000 nodes, active buckets/sec < 10,000 :
UDP， gossip communication
大 hosts > 10,000
需要单独集群