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