55 | 算法实战（四）：剖析微服务接口鉴权限流背后的数据结构和算法
王争
微服务是最近几年才兴起的概念。简单点讲，就是把复杂的大应用，解耦拆分成几个小的应用。这样做的好处有很多。比如，这样有利于团队组织架构的拆分，毕竟团队越大协作的难度越大；再比如，每个应用都可以独立运维，独立扩容，独立上线，各个应用之间互不影响。不用像原来那样，一个小功能上线，整个大应用都要重新发布。
不过，有利就有弊。大应用拆分成微服务之后，服务之间的调用关系变得更复杂，平台的整体复杂熵升高，出错的概率、debug 问题的难度都高了好几个数量级。所以，为了解决这些问题，服务治理便成了微服务的一个技术重点。
所谓服务治理，简单点讲，就是管理微服务，保证平台整体正常、平稳地运行。服务治理涉及的内容比较多，比如鉴权、限流、降级、熔断、监控告警等等。这些服务治理功能的实现，底层依赖大量的数据结构和算法。今天，我就拿其中的鉴权和限流这两个功能，来带你看看，它们的实现过程中都要用到哪些数据结构和算法。
鉴权背景介绍
以防你之前可能对微服务没有太多了解，所以我对鉴权的背景做了简化。
假设我们有一个微服务叫用户服务（User Service）。它提供很多用户相关的接口，比如获取用户信息、注册、登录等，给公司内部的其他应用使用。但是，并不是公司内部所有应用，都可以访问这个用户服务，也并不是每个有访问权限的应用，都可以访问用户服务的所有接口。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《数据结构与算法之美》，新⼈⾸单¥68
《数据结构与算法之美》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(46)
- 最新
- 精选
- suke置顶老师能对限流相关的算法和数据结构多讲一讲么
作者回复: 这是我之前开源的限流框架，你可以看看，比较详细了。而且里面还有一篇我发到infoq上的文章，讲设计思路。 https://github.com/wangzheng0822/ratelimiter4j
1453 
Monday鉴权的精确匹配用散列表的时间复杂度是O(1)，比顺序匹配O(n)和二分查找的效率都高啊。为什么不选用呢？作者回复: 小数据量的情况下，散列表在存储和匹配上并不一定比二分查找高呢
12
青铜5 周群力请教老师一个问题哈，为啥鉴权算法里，每个应用的规则要放到有序数组呢，放hash set会更好吧? 比如一个应用有两个规则:/user/a和/user/b，把这俩规则放hash set岂不是时间复杂度更低、更好呢作者回复: hash set对于小数据量也不一定比有序数组效率高呢。毕竟hash set还要计算哈希值、处理冲突等。
10
懒猫请教老师，鉴权那一部分如何用有序数组做二分查找呢，数组里存放的都是uri中的单词吗？在数组中怎么排序？字典序？这里的二分比较时怎么比较大小呢作者回复: 1. 存放的是uri字符串 2. 用字典序来排序 3. 比较两个字符串大小的算法你应该知道吧
6
金龟老师，文章里你说了这一句话'只能在选定的时间粒度上限流，对选定时间粒度内的更加细粒度的访问频率不做限制。'这里更加细粒度代表什么意思，我觉得已经解决了，最初时间窗口的问题呀。比如如果我限流5qps，那循环队列（元素内存时间）只留tail指针，只是要增加每次tail前进之前用当前时间和后一个元素时间进行一个差指，大于1秒前进，小于一秒拒绝请求。作者回复: 更细时间粒度的理解是这样的：比如你限制的是100次/s，那具体到10ms（更细时间粒度）是多少，你就无法限制了。
26- wjh_all_in请问一下，滑动窗口限流策略，清除过期数据的时机是新请求到达，这个是基于单位ms内不会有很大的并发的考虑吗？如果像淘宝这样的大流量电商，是不是需要更低精度的时间，不然清除数据的耗时，可能会使接口性能变差
作者回复: 课程github上有详细的介绍文档，如果感兴趣可以去看下
3 
Tattoo“不同的应用对应不同的规则集合。我们可以采用散列表来存储这种对。。。”，这里如果匹配规则很多的话，不会发生很多的冲突的吗？作者回复: 散列表本身就有解决冲突的机制的
1
xyf想问下如何对接口做数据域权限检验。比如调用方有权限调用查询项目接口，但是对于请求参数，如项目ID，鉴权系统能够判断调用者是否有权限访问这个项目。作者回复: 可以把参数拼到url中 或者重新设计鉴权规则
1
Joker期待老师的题目，最近也在刷LeetCode，结合的效果肯定好！！！编辑回复: 哈哈 看来会给你惊喜了
1
Flash思考题1：可以用优先级队列（根据请求时间构建小顶堆），最早的请求时间的放在堆顶。然后每次进来一个请求，就判断这个时间跟堆顶的时间差是否小于1S，并且堆的大小小于请求限制的次数，如果是就插入队列，如果不是，就限制。545
收起评论
