高并发面试问题

漏桶

漏桶的原理比较简单，要求进入漏桶，漏桶以一定的速率漏水。请求太多的时候，水直接溢出来了。可见漏桶可以迫使数据传输速度受限。如图所示，将请求比作水滴，水首先落入桶中，穿过漏洞，以有限的速度出来。水来的太猛，出来的又不够快，就会导致水直接溢出，也就是拒绝服务。

图片来自网络。

漏桶的出水速度是恒定的，也就是说瞬时流量大的话大部分请求都会被丢弃(所谓的溢出)。

令牌桶算法

令牌桶算法的原理是系统以一定的速率将令牌放入桶中。如果有请求，该请求将从桶中取出令牌。如果它可以获得令牌，它可以继续完成请求，否则它将等待或拒绝服务。该算法优于漏桶算法，因为它可以处理突发请求。

图片来自网络。

漏桶和令牌桶算法的选择

两者的主要区别在于漏桶可以强行限制数据处理速率，而不管系统是否空闲。令牌桶算法可以限制平均数据处理速率，同时允许一些突发流量。怎么理解上面的意思？漏桶，比如系统吞吐量是120/s，业务请求是130/s，用漏斗限制流量，多余的请求会被等待或丢弃。对于令牌桶算法，每秒产生100个令牌，系统容量为200个令牌。正常情况下，当服务请求为100/s时，可以正常处理请求。当流量突发时，例如200个请求，由于系统容量的原因，有200个令牌可以同时处理这200个请求。在漏桶的情况下，只能处理100个请求，其他请求都在等待或被丢弃。