极客时间真的是个好东西，每课10-15分钟的篇幅，让我们可以利用碎片化的时间夯实基础、学习新技术。本人购买的第一堂课是王争老师的《数据结构与算法之美》。记得上大学的第一堂计算机导论课，老师就告诉我们，程序=数据结构+算法。之前没好好学，也不怎么知道其中的奥义，经过这么多年的学生生涯以及几年的工作经历真真的觉得数据结构和算法是程序员的立身之本啊！此番，想借这个机会，把这块难啃的骨头好好啃一下，不说能啃烂吧，也希望自己在学习过程中能有所积累和进步，并且学以致用！
一、鉴权
鉴权是微服务之间相互调用的合法性校验。借用老师在文中的例子，假如我们的用户服务对外提供用户查询、用户注册、用户登录三个接口，不同的app可以调用的接口有差别，如app1可以调用查询和注册、app2可以调用注册和登录等等。这就需要对不同的app制定相应的访问规则。在基于http接口的微服务调用中，规则可以基于url进行制定。这个场景下，应用及应用的访问规则，是以键值的形式存在的，是典型的字典场景，因此可以使用哈希表来保存用户的访问规则。键存储的是应用的标识，值存储的是该应用的访问规则。至于规则的匹配，又可以分为以下三种：
- 精确匹配
将访问规则数组按照url字符串的顺序进行排序，匹配时可以使用二分查找来进行查找，时间复杂度是log（n）。 - 前缀匹配
前缀匹配可以使用Tri树进行匹配。这种算法还没有学习到，之后学完后会在此补充。 - 模糊匹配
这里的模糊匹配是指带有通配符的匹配，如XXX/**/YYY表示XXX和YYY之间可能有n个子目录。这种的话可以采用回溯法进行匹配。
二、限流
限流也是保证微服务稳定的一项重要的手段，指的是限制一定时间段内服务的调用次数。主要有两种实现方式：
- 固定时间窗口限流
这种方式是在系统开始接收调用请求开始就设置一个定时器和计数器，每当有请求到达时，计数器就加1，直至在定时器的时间间隔内到达计数器阈值时，拒绝后面到达的请求，当到达下一个时钟周期时，计数器会被重置。
这种方式实现起来比较容易，但是会存在两个时间窗口相邻处短时间大规模请求压力的问题。比如系统的阈值是1s 10个请求，前一个时间窗口的请求都集中在后10ms内，后一个时间窗口的请求都集中在前10ms内，这样就相当于在20ms的时间窗口内系统要应对20个请求，两倍于阈值的数量。这有可能是系统所无法承受的，限流器也就没法达到它应有的目的了。 - 滑动时间窗口限流
滑动时间窗口的方式，是借助一个循环队列，队列的大小就是限流器的阈值，同时还会记录请求到达的时间。新请求到达时，会从队列里删除已经超出时间窗口宽度的请求，然后入队。入队失败的话，就证明被限制流量了，否则请求可以被正常处理。
网友评论