数据结构与算法简记--剖析微服务接口鉴权限流背后的数据结构和算法

关键词：

微服务鉴权限流剖析

---

 微服务

• 把复杂的大应用，解耦拆分成几个小的应用。
• 有利于团队组织架构的拆分，毕竟团队越大协作的难度越大；
• 每个应用都可以独立运维，独立扩容，独立上线，各个应用之间互不影响。
• 有利就有弊：
  • 大应用拆分成微服务之后，服务之间的调用关系变得更复杂，平台的整体复杂熵升高，出错的概率、debug 问题的难度都高了好几个数量级。
• 为了解决这些问题，服务治理便成了微服务的一个技术重点。

服务治理

• 简单点讲，就是管理微服务，保证平台整体正常、平稳地运行。
• 涉及的内容：鉴权、限流、降级、熔断、监控告警等等。
• 服务治理功能的实现，底层依赖大量的数据结构和算法。这里拿其中的鉴权和限流这两个功能，剖析一下实现过程中用到的数据结构和算法。

鉴权

• 有一个微服务叫用户服务（User Service）。它提供很多用户相关的接口，比如获取用户信息、注册、登录等，给公司内部的其他应用使用。
• 并不是公司内部所有应用，都可以访问这个用户服务，也并不是每个有访问权限的应用，都可以访问用户服务的所有接口。
• 

•  

  需要实现接口鉴权功能

  • 事先将应用对接口的访问权限规则设置好。

  • 当某个应用访问其中一个接口的时候，可以拿应用的请求 URL，在规则中进行匹配。

  • 如果匹配成功，就说明允许访问；

  • 如果没有可以匹配的规则，说明这个应用没有这个接口的访问权限，就拒绝服务。 

• 如何实现快速鉴权？
  • 用什么数据结构来存储规则?
  • 用户请求 URL 在规则中快速匹配，用什么的算法？
  • 不同的规则和匹配模式，对应的数据结构和匹配算法也是不一样。
• 如何实现精确匹配规则？
  • 简单规则
  • 
  • 不同的应用对应不同的规则集合，可以采用散列表来存储这种对应关系。
  • 每个应用对应的规则集合，该如何存储和匹配？
    • 可以将每个应用对应的权限规则，存储在一个字符串数组中。
    • 当用户请求到来时，拿用户的请求 URL，在这个字符串数组中逐一匹配，匹配的算法就是我们之前学过的字符串匹配算法（比如 KMP、BM、BF 等）。
    • 规则不会经常变动，所以，为了加快匹配速度，可以按照字符串的大小给规则排序，把它组织成有序数组这种数据结构。
    • 当要查找某个 URL 能否匹配其中某条规则的时候，可以采用二分查找算法，在有序数组中进行匹配。
• 如何实现前缀匹配规则？
  • 稍微复杂的匹配模式：只要某条规则可以匹配请求 URL 的前缀，这条规则就能够跟这个请求 URL 匹配。
    
  • 
  • Trie 树非常适合用来做前缀匹配
  • 可以将每个用户的规则集合，组织成 Trie 树这种数据结构。
  • Trie 树中的每个节点不是存储单个字符，而是存储接口被“/”分割之后的子目录（比如“/user/name”被分割为“user”“name”两个子目录）。
  • 同样的，规则不会经常变动，所以，在 Trie 树中，可以把每个节点的子节点们，组织成有序数组这种数据结构。
  • 当在匹配的过程中，可以利用二分查找算法，决定从一个节点应该跳到哪一个子节点。
  • 

• 如何实现模糊匹配规则？

  • 更加复杂的匹配模式：规则中包含通配符，比如“**”表示匹配任意多个子目录，“*”表示匹配任意一个子目录。只要用户请求 URL 可以跟某条规则模糊匹配，这条规则适用于这个请求。
  • 

  • 可以借助正则表达式那个例子的解决思路，来解决这个问题。采用回溯算法，拿请求 URL 跟每条规则逐一进行模糊匹配。

  • 回溯算法复杂度是非常高，如何优化？

    •  把不包含通配符的规则和包含通配符的规则分开处理（分治思想）：

    • 把不包含通配符的规则，组织成有序数组或者 Trie 树进行精确或前缀匹配（具体组织成什么结构，视具体的需求而定，是精确匹配，就组织成有序数组，是前缀匹配，就组织成 Trie 树）。

    • 剩下的是少数包含通配符的规则，只要把它们简单存储在一个数组中就可以了。尽管匹配起来会比较慢，但是毕竟这种规则比较少，所以这种方法也是可以接受的。

    • 当接收到一个请求 URL 之后，先在不包含通配符的有序数组或者 Trie 树中查找。如果能够匹配，就不需要继续在通配符规则中匹配了；如果不能匹配，就继续在通配符规则中查找匹配。

限流

• 对接口调用的频率进行限制。比如每秒钟不能超过 100 次调用，超过之后，就拒绝服务。
• 在很多场景中，发挥着重要的作用。比如在秒杀、大促、双 11、618 等场景中，限流已经成为了保证系统平稳运行的一种标配的技术解决方案。
• 按照不同的限流粒度分类：
  • 每个接口限制不同的访问频率
  • 给所有接口限制总的访问频率
  • 限制某个应用对某个接口的访问频率
• 如何实现精准限流？
  • 固定时间窗口限流算法：
    • 选定一个时间起点，之后每当有接口请求到来，将计数器加一。
    • 如果在当前时间窗口内，根据限流规则（比如每秒钟最大允许 100 次访问请求），出现累加访问次数超过限流值的情况时，我们就拒绝后续的访问请求。
    • 当进入下一个时间窗口之后，计数器就清零重新计数。
    • 
    • 缺点：限流策略过于粗略，无法应对两个时间窗口临界时间内的突发流量：
      • 第一个 1s 时间窗口内，100 次接口请求都集中在最后 10ms 内。
      • 第二个 1s 的时间窗口内，100 次接口请求都集中在最开始的 10ms 内。
      • 虽然两个时间窗口内流量都符合限流要求（≤100 个请求），但在两个时间窗口临界的 20ms 内，会集中有 200 次接口请求。
      • 固定时间窗口限流算法并不能对这种情况做限制，所以，集中在这 20ms 内的 200 次请求就有可能压垮系统。
  • 滑动时间窗口限流算法
    • 假设限流的规则是，在任意 1s 内，接口的请求次数都不能大于 K 次。
    • 维护一个大小为 K+1 的循环队列，用来记录 1s 内到来的请求。注意，这里循环队列的大小等于限流次数加一，因为循环队列存储数据时会浪费一个存储单元。
    • 当有新的请求到来时，将与这个新请求的时间间隔超过 1s 的请求，从队列中删除。
    • 再来看循环队列中是否有空闲位置：
      • 如果有，则把新请求存储在队列尾部（tail 指针所指的位置）；
      • 如果没有，则说明这 1 秒内的请求次数已经超过了限流值 K，所以这个请求被拒绝服务。
    • 

    •  

       只能在选定的时间粒度上限流，对选定时间粒度内的更加细粒度的访问频率不做限制。

    • 王争限流框架：https://github.com/wangzheng0822/ratelimiter4j

 

 

 

微服务网关鉴权：gateway使用网关限流使用用户密码加密jwt鉴权(代码片段)

...流的实现能够使用BCrypt实现对密码的加密与验证了解加密算法能够使用JWT实现微服务鉴权1.微服务网关Gateway1.1微服务网关概述不同的微服务一般会有不同的网络地址，而外部客户端可能需要调用多个服务的接口才能完成一个... 查看详情

微服务网关鉴权：gateway使用网关限流使用用户密码加密jwt鉴权(代码片段)

...流的实现能够使用BCrypt实现对密码的加密与验证了解加密算法能够使用JWT实现微服务鉴权1.微服务网关Gateway1.1微服务网关概述不同的微服务一般会有不同的网络地址，而外部客户端可能需要调用多个服务的接口才能完成一个... 查看详情

springcloud微服务架构中使用自定义注解实现简单的权限控制与权限开关(代码片段)

前言在微服务架构下开发权限控制一般的做法是，独立开发一个专门用于鉴权的服务，其它服务每次请求接口时都调用鉴权服务鉴权，这样做的好处是，代码耦合低，权限控制功能好扩展，其坏处是每次鉴... 查看详情

springcloud微服务架构中使用自定义注解实现简单的权限控制与权限开关(代码片段)

前言在微服务架构下开发权限控制一般的做法是，独立开发一个专门用于鉴权的服务，其它服务每次请求接口时都调用鉴权服务鉴权，这样做的好处是，代码耦合低，权限控制功能好扩展，其坏处是每次鉴... 查看详情

密码加密与微服务鉴权jwt(代码片段)

...到安全，绝不能明文的方式保存密码。密码应该通过哈希算法进行加密。有很多标准的算法比如SHA或者MD5，结合salt(盐)是一个不错的选择。SpringSecurity提供了BCryptPasswordEncoder类,实现Spring的PasswordEncoder接口使用BCrypt强哈希方法来加... 查看详情

livegbs流媒体平台gb/t28181功能-视频直播流快照的安全控制配置播放回调鉴权接口控制播放权限(代码片段)

LiveGBS功能-视频直播流快照的安全控制配置播放回调鉴权接口控制播放权限1、直播流安全控制1.1、直播流开启控制1.2、直播流回调鉴权2、配置播放鉴权回调2.1、准备回调鉴权接口2.2、配置回调鉴权地址2.3、调试说明2.3.1、调试环... 查看详情

微服务架构中整合网关权限服务(代码片段)

前言：之前的文章有讲过微服务的权限系列和网关实现，都是孤立存在，本文将整合后端服务与网关、权限系统。安全权限部分的实现还讲解了基于前置验证的方式实现，但是由于与业务联系比较紧密，没有具体的示例。业务权... 查看详情

sa-token授权鉴权中心微服务

...Signature且用圆点连接​2.Header由两部分（Token类型加密算法名称）组成,并使用Base64编码​3.Payloadkv形式的数据即你想传递的数据（授权的话就是token信息）​4.Signature为了得到签名部分你必须有编码过的Header编码过... 查看详情

数据结构与算法简记--实现一个短网址系统(代码片段)

实现一个短网址系统短网址服务把一个长的网址转化成一个短的网址，访问这个短网址，就相当于访问原始的网址原始网址：https://github.com/wangzheng0822/ratelimiter4j短网址：http://t.cn/EtR9QEG上面第二个网址是通过新浪提供的短网址服... 查看详情

搭建springcloud微服务框架：spring-security-oauth服务接口鉴权

搭建微服务框架（服务接口鉴权）前面已经可以通过SpringCloud可以来构建对外的接口，现在来介绍一下怎么通过使用OAuth2来进行接口的鉴权。本文源地址：搭建微服务框架（服务接口鉴权）Github地址：SQuid介绍OAuth2网上介绍的例... 查看详情

3.爱收藏——系统架构

一、简介　　爱收藏系统，以微服务为核心，按照业务来划分模块，前后端分离。存储以关系型数据库为主，redis存储登录相关数据。前端使用vue开发，nginx作为静态文件服务器。使用docker部署，容器包括前后端服务、基础服务... 查看详情

微服务网关常用限流算法

常用算法有三种：计数器算法、漏斗桶算法、令牌桶算法，市面上最常用的是最后一个第一个：计数器算法   他维护的是单位时间内的最大请求量，因此极端情况可能造成服务抖动 第二个：漏斗桶算法，这种算法... 查看详情

sa-token实现分布式登录鉴权（redis集成前后端分离）

...证、权限认证、单点登录、OAuth2.0、分布式Session会话、微服务网关鉴权等一系列权限相关问题。功能结构图2.登录认证对于一些登录之后才能访问的接口（例如：查询我的账号资料），我们通常的做法是增加一层接口校验：如果... 查看详情

每日一博-微服务权限一二事

...、鉴权认证的处理方式授权的处理方式鉴权的处理方式微服务架构下的认证、授权、鉴权鉴权方案一鉴权方案二鉴权方案三其他方案小结概念普及关于权限，先了解几个核心的概念认证授权鉴权认证举个例子：输入用户... 查看详情

每日一博-微服务权限一二事

...、鉴权认证的处理方式授权的处理方式鉴权的处理方式微服务架构下的认证、授权、鉴权概念普及关于权限，先了解几个核心的概念认证授权鉴权认证举个例子：输入用户名/密码，点击登录后，后台执行的业务逻... 查看详情

自适应微服务治理背后的算法(代码片段)

前言go-zero群里经常有同学问：服务监控是通过什么算法实现的？滑动窗口是怎么工作的？能否讲讲这块的原理？熔断算法是怎么设计的？为啥没有半开半闭状态呢？本篇文章，来分析一下go-zero中指标统计背后的实现算法和逻辑... 查看详情

数据结构与算法简记：avl树

前面记录了二叉查找树，它在搜索方面的效率显而易见，可它也存在某种缺陷，假设我们连续插入较小或较大的数据，那么二叉查找树将会逐渐退变为一个线性结构，从而搜索就变为了线性查找，效率将会大打折扣。所以，我们... 查看详情

数据结构与算法简记--字符串匹配kmp算法

KMP算法比较难理解，准备有时间专门啃一下。 核心思想与BM算法一样：假设主串是a，模式串是b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过... 查看详情