算法实战4 - 微服务鉴权限流背后的数据结构和算法
本章关键词
鉴权、限流
微服务是最近兴起的概念，简单来说，就是把复杂的大应用，解耦拆分成几个小应用。这样的好处有很多。比如，这样做有利于团队组织架构的拆分；每个应用可以独立运维、扩容、上线。
但是，微服务架构也有弊端，那就是将大应用拆分成微服务后，服务之间的调用关系变得非常复杂，出错的概率、debug 的难度都高出了很多。为了解决这种问题，对各个服务之间的治理就成为了重点。
服务治理的内容很多，比如鉴权、限流、降级、熔断、监控等。这里，我们就看一看鉴权和限流中，都使用了怎样的数据结构和算法。
鉴权
假设我们有一个微服务叫用户服务（User Service）。它提供很多用户相关的接口，但是不同用户能使用的接口是不同的（不同用户的授权不同）。鉴定一个应用是否有权力访问某个接口，这就是典型的鉴权。
这里为你举个例子，服务有 4 个接口，同时有 A、B、C、D 四个应用，他们有不同的权限：
什么是鉴权.jpg
如图，由应用延伸出来的黄色箭头代表了微服务为不同应用设置的权限规则。如果某应用没有访问某接口的权限，服务就会被拒绝。
鉴权实现
实现鉴权的方法有很多，这里使用 HTTP 接口，通过用户请求 URL 实现鉴权。
授权的规则很多，大致可以分为三种：精准匹配、前缀匹配、模糊匹配。不同匹配模式使用的不同的方法实现，我们依次来看：
1.实现精确匹配规则
这是最简单的一种匹配模式。当 URL 和接口规则精确匹配时，请求才会被接受：
精准鉴权.jpg
不同应用对应不同的规则集合，我们可以使用散列表存储这种对应关系。下面我们要关心的是，不同应用对应的规则集合，该如何存储和匹配
对精准匹配模式，我们只需要对 URL 和规则进行逐一匹配即可，匹配的算法使用常见的字符串匹配算法即可（如 KMP、BM、BF 等）。
规则变动较少，我们可以使用数组存储规则。为了加快匹配，我们可以对规则进行排序，然后使用二分查找的方法加速匹配，这时的数组就是有序数组了。
总结：使用有序数组 + 二分查找实现精确匹配。
2.实现前缀匹配规则
这种匹配相对复杂一些：只要请求 URL 的前缀和某条规则匹配，服务就接受这个请求：
前缀鉴权.jpg
同样，用散列表存储不同应用的规则集合，下面讲解如何实现用户下的前缀匹配
提到前缀匹配，我们可以很自然地联想到 Trie树 ，我们说过，Trie树 非常适合进行前缀匹配。
不过，在这里，Trie树 中的结点不是存储单个字符，而是存储一个子目录。由于规则不会频繁变动，你可以使用 有序数组+二分查找 实现对子节点查找：
前缀鉴权-Trie树.jpg
总结：使用 Trie树 完成前缀匹配，在向子节点查找时依然可以使用 有序数组+二分查找 实现查找。
3.实现模糊匹配规则
这种规则更加复杂，规则中使用了通配符，如 “*” 表示匹配任意多个子目录。“” 表示匹配任意一个子目录。只要应用请求 URL 符合模糊匹配规则，服务就会得到相应：
模糊鉴权.jpg
应用间的规则区分可以使用散列表，这里不多说了。
提到使用通配符，你应该马上就能想到在回溯算法中讲到的正则表达式。没错，我们可以使用相同的思路，用回溯思想完成匹配。
但是，你一定会想到，回溯算法的时间复杂度非常高。那么，有没有什么方法可以提升匹配的性能呢？
实际上，一个应用并不会每次匹配都使用模糊匹配。所以，我们可以将请求分类，把不包含通配符的请求直接用前两种方法匹配。当发下请求 URL 中包含通配符时，才使用回溯算法进行模糊匹配。
总结：使用回溯算法像匹配正则那样进行模糊匹配，当然，你可以想办法先将非模糊匹配的请求过滤掉，这样可以大大提升性能。
限流
限流，顾名思义。就是限制对接口调用的频率。比如每秒钟调用不能超过 100 次。
限流可以保证服务不被突然到来的高频访问压垮，在保证系统平稳运行中发挥着重要作用。
如何实现限流？
1.固定时间窗口限流
有很多种方法可以实现限流，在这里，先介绍一种最简单的限流算法：固定时间窗口限流。这种算法可以保障在单位时间内访问次数不会高于某个阈值，下图展现了一个限流的例子：
限流-固定时间窗口.jpg
这种限流策略非常容易实现：我们设置一个计数器，这种计数器在 1s 后就会清零。在这期间，服务每接受一次请求就将计数器 +1 ，当计数器超过阈值时，就拒绝服务。
你可能发现了，这种限流方法非常粗糙，无法应对两个时间间隔间的突发情况。以下图为例，限流阈值为 100，但是当请求集中到来时，会在 20ms 内响应 200 次请求，这种情况可能会压垮系统：
固定时间窗口限流的缺陷.jpg
对这种问题，我们可以使用滑动窗口限流
2.滑动时间窗口限流
我们的限流规则是：维护一个大小为 k+1 的循环队列（限流阈值为 k ，大小 +1 是因为循环队列会浪费一个空间），用于记录 1s 内到来的请求。
当有新请求到来时，我们首先将请求时间超过 1s 的请求从队列中删除，然后处理新的请求。如果此时队列中仍有空余空间，就处理请求；如果没用空间，证明访问过于频繁，就拒绝请求。
这里给你一个例子，我们将阈值设置为 6 ：
滑动窗口限流.jpg
这样，我们实现了一种更加平滑的限流，但是它依然存在问题：如果在过去的 1s 内没有请求，队列被清空，然后突然在 10ms 内到来的 k 次请求，服务依然会接受。但是这样的访问频率显然过高。
针对这个问题，还可以使用其它的算法处理，但是在这里就不详细讲解了。如果感兴趣，可以自己去研究一下 令牌桶算法、漏桶算法等。
总结
这节中我们讲解了微服务中的鉴权 和 限流
鉴权：
- 使用散列表保存不同应用（用户）的请求规则
- 精确匹配：使用有序数组保存规则集，使用二分查找进行规则查找和匹配
- 前缀匹配：使用 Trie树 保存规则集，在节点中也可以使用 有序数组+二分查找 加速匹配
- 模糊匹配：使用回溯算法处理包含通配符的匹配，对不包含通配符的情况，使用前两种匹配方法
限流：
- 固定时间窗口限流：使用计数器限流，但是不够平滑
- 滑动时间窗口限流：使用循环队列限流，相对平滑，但是依然无法应对特殊情况下的高频请求
以上就是本节的全部内容，希望对你有所启发
注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我使用了大量的原文、代码和截图，如果想要了解具体内容，可以前往极客时间
