数据结构与算法之美
王争
前 Google 工程师
280067 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法

微服务是最近几年才兴起的概念。简单点讲,就是把复杂的大应用,解耦拆分成几个小的应用。这样做的好处有很多。比如,这样有利于团队组织架构的拆分,毕竟团队越大协作的难度越大;再比如,每个应用都可以独立运维,独立扩容,独立上线,各个应用之间互不影响。不用像原来那样,一个小功能上线,整个大应用都要重新发布。
不过,有利就有弊。大应用拆分成微服务之后,服务之间的调用关系变得更复杂,平台的整体复杂熵升高,出错的概率、debug 问题的难度都高了好几个数量级。所以,为了解决这些问题,服务治理便成了微服务的一个技术重点。
所谓服务治理,简单点讲,就是管理微服务,保证平台整体正常、平稳地运行。服务治理涉及的内容比较多,比如鉴权、限流、降级、熔断、监控告警等等。这些服务治理功能的实现,底层依赖大量的数据结构和算法。今天,我就拿其中的鉴权和限流这两个功能,来带你看看,它们的实现过程中都要用到哪些数据结构和算法。

鉴权背景介绍

以防你之前可能对微服务没有太多了解,所以我对鉴权的背景做了简化。
假设我们有一个微服务叫用户服务(User Service)。它提供很多用户相关的接口,比如获取用户信息、注册、登录等,给公司内部的其他应用使用。但是,并不是公司内部所有应用,都可以访问这个用户服务,也并不是每个有访问权限的应用,都可以访问用户服务的所有接口。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(46)

  • 最新
  • 精选
  • suke
    置顶
    老师能对限流相关的算法和数据结构多讲一讲么

    作者回复: 这是我之前开源的限流框架,你可以看看,比较详细了。而且里面还有一篇我发到infoq上的文章,讲设计思路。 https://github.com/wangzheng0822/ratelimiter4j

    14
    53
  • 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(更细时间粒度)是多少,你就无法限制了。

    2
    6
  • wjh_all_in
    请问一下,滑动窗口限流策略,清除过期数据的时机是新请求到达,这个是基于单位ms内不会有很大的并发的考虑吗?如果像淘宝这样的大流量电商,是不是需要更低精度的时间,不然清除数据的耗时,可能会使接口性能变差

    作者回复: 课程github上有详细的介绍文档,如果感兴趣可以去看下

    3
  • Tattoo
    “不同的应用对应不同的规则集合。我们可以采用散列表来存储这种对。。。”,这里如果匹配规则很多的话,不会发生很多的冲突的吗?

    作者回复: 散列表本身就有解决冲突的机制的

    1
  • xyf
    想问下如何对接口做数据域权限检验。比如调用方有权限调用查询项目接口,但是对于请求参数,如项目ID,鉴权系统能够判断调用者是否有权限访问这个项目。

    作者回复: 可以把参数拼到url中 或者重新设计鉴权规则

    1
  • Joker
    期待老师的题目,最近也在刷LeetCode,结合的效果肯定好!!!

    编辑回复: 哈哈 看来会给你惊喜了

    1
  • Flash
    思考题1:可以用优先级队列(根据请求时间构建小顶堆),最早的请求时间的放在堆顶。然后每次进来一个请求,就判断这个时间跟堆顶的时间差是否小于1S,并且堆的大小小于请求限制的次数,如果是就插入队列,如果不是,就限制。
    5
    45
收起评论
显示
设置
留言
46
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部