redis数据结构与精准限流

àì夳堔傛蜴生んèń 2023-06-30 08:58 12阅读 0赞

Redies  
key -value

value存在如下类型：  
set  
Sortedset  
map  
string  
list

list-列表：  
ziplist：压缩列表：  
类似数组，但不同于数组，  
1）单一压缩列表中支持存储不同大小的数据，所以更加节省空间，这也是压缩的含义。  
2) 因为上面的特性，压缩列表不可以通过下标直接定位元素  
为什么要使用压缩散列表：没有多余的指针等，节省空间

使用条件如下：  
列表数据个数小于512个  
列表中保存的单个数据小于64字节

双向链表  
除了节点定义包含 左节点 值 右节点之外，  
它额外定义一个 list 结构体，来组织链表的首、尾指针，还有长度等信息。这样，在使用的时候就会非常方便。

hash-字典：  
1）压缩列表：条件同上  
2）散列表：会自动扩容(为了性能)和缩容(节约内存)；  
在扩容的时候，一般的做法是做大量的数据迁移和hash值的重新计算，会导致服务停顿。Redis采用的方式就是采用渐进是的扩容和缩容策略。

set-集合：  
1）有序数组，场景：数据都是整数，并且元素个数小于512个  
2）散列表

sortedset-有序集合：  
压缩列表：元素小于64字节，元素个数小于128个  
跳表

为了断电时能够恢复已有的数据：  
所以能够进行持久化，可以手动触发或者是配置(时间+改动次数），持久化的方案：  
1）清除原有的存储结构，仅仅存储数据到磁盘中，节约磁盘，但是恢复慢。  
2）保留原有的存储结构，  
3）记录操作过的指令，但是一直累加吗

为什么redis刚开始都是采用压缩列表？  
因为压缩列表比较节省空间，而且压缩列表因为支持不同大小的数据，导致并不能根据下标直接定位数据，只能遍历获取；但是数据量大了以后，需要获取连续的大的空间就不太好。

鉴权限流背后的数据结构  
鉴权url处理，用/分割，获取不同的  
散列表存储 url 和 规则之间的关系。 key:url  value:规则  
精准匹配：kmp,sunday  
前缀匹配：trie树，组织成有序数组这种数据结构。当在匹配的过程中，我们可以利用二分查找算法，决定从一个节点应该跳到哪一个子节点。  
模糊匹配：参考回溯算法的正则表达式。

如何实现精准限流：  
固定时间窗口限流算法：  
选点时间点，之后没有请求进入，计数器加1.在当前时间窗口内，出现访问次数超过限流值的情况时，我们拒绝后续的访问请求。当进入下一个时间窗口，计数器清零。

问题：无法应对两个时间窗口临接时间的突发流量。  
限流规则：每秒钟不能超过 100 次接口请求。第一个 1s 时间窗口内，100 次接口请求都集中在最后 10ms 内。在第二个1s的时间窗口内，100次接口请求都集中在最开始的10ms内。虽然两个时间窗口内流量都符合限流要求（≤100 个请求），但在两个时间窗口临界的 20ms 内，会集中有 200 次接口请求。

对固定时间窗口限流算法稍加改造。我们可以限制任意时间窗口（比如1s）内，接口请求数都不能超过某个阈值（ 比如 100 次）。因此，相对于固定时间窗口限流算法，这个算法叫滑动时间窗口限流算法。

流量经过滑动时间窗口限流算法整形之后，可以保证任意一个 1s 的时间窗口内，都不会超过最大允许的限流值，从流量曲线上来看会更加平滑。那具体到实现层面，我们该如何来做呢？  
我们假设限流的规则是，在任意 1s 内，接口的请求次数都不能大于 K 次。我们就维护一个大小为 K+1 的循环队列，用来记录 1s 内到来的请求。注意，这里循环队列的大小等于限流次数加一，因为循环队列存储数据时会浪费一个存储单元。当有新的请求到来时，我们将与这个新请求的时间间隔超过 1s 的请求，从队列中删除。然后，我们再来看循环队列中是否有空闲位置。如果有，则把新请求存储在队列尾部（tail 指针所指的位置）；如果没有，则说明这 1 秒内的请求次数已经超过了限流值 K，所以这个请求被拒绝服务。