Redis系列之进阶篇（下）
前言
上一期我们学习了Redis的一些高级应用，今天我们来继续学习Redis的高级技术。
这篇文章主要内容是：
布隆过滤器
限流
GeoHash
-
Scan
本文所学知识点过多，请做好实践。
1. 布隆过滤器
布隆过滤器是一种高级数据结构，专门用于解决去重和检测某个对象是否存在的问题。
布隆过滤器就像一个不怎么精确的set结构，当你使用它的contains方法判断某个对象是否存在时，它可能会误判。布隆过滤器实际上并不是特别不精确，只是会有较小的误判概率。
所谓的误判就是：当布隆过滤器说某个值不存在的时候，那么这个值就一定不存在；当它说一个值存在的时候，那么这个值可能存在，也可能不存在。之所以出现误判，不过是因为这个值和它知道的某个值比较相似。
1.1 简单使用
Redis4.0提供了插件功能，布隆过滤器作为一个插件加载到Redis Server中，给Redis提供了强大的布隆去重功能。
布隆过滤器有两个基本指令，bf.add和bf.exists。bf.add添加元素，bf.exists查询元素是否存在。
> bf.add user keben
> bf.add user zhangsan
> bf.add user zhaosi
> bf.exists user keben
> bf.madd user xiaoming zhangwu wanger # 批量添加
> bf.mexists user xiaoming zhangwu wanger # 批量判断是否存在
1.2 自定义参数
Redis提供了自定义参数的布隆过滤器，来降低误判率，只需要在add之前使用bf.reserve指令创建。如若对应的key已经存在，bf.reserve会报错。
bf.reserve有三个参数,分别是key,error_rate（错误率）和initial_size。
error_rate越低，需要的空间越大。
initial_size表示预计放入的元素数量，当实际数量超过这个数值时，误判率会上升。
1.3 原理概括
每个布隆过滤器对应到Redis的数据结构里面就是一个大型的位数组和几个不一样的无偏hash函数。所谓无偏就是能够把元素的hash值算的比较均匀，让元素被hash映射到位数组中的位置比较随机。
向布隆过滤器插入key的时候，会对key进行hash，获取一个整数索引，然后对位数组长度进行取模运算获取一个位置。再把位数组的这几个位置都置为1。
向布隆过滤器查询是否存在的时候，和add是相同，也会把hash的几个位置都算出来，看看位数组中这几个位是否都为1，只要有一个位为0，说明布隆过滤器中这key不存在。如果几个位置都为1，并不能说明这个key就一定存在，因为这些位被置为1可能是因为其他key导致的。
2. 限流
限流算法在分布式领域下是一个经常被提起的话题，当系统的处理能力有限时，如何阻止计划外的请求继续对系统施压，这是一个需要重视的问题。除了控制流量，限流还有一个应用目的是控制用户行为，避免垃圾请求。
==注意Redis中的限流只是添加用户的行为记录，根据行为记录是否超标来进行真实的行为操作==
2.1 简单限流
来看下一个常见的，简单的限流策略。系统要限定用户的某个行为在指定时间内只能发生N次。
// 指定用户userId指定行为actionkey在一定时间内period只能执行maxCount次
publci void isActionAllowed(Long userId,String actionKey,Integer period,Integer maxCount){
String key = String.format("hist:%s:%s",userId,actionKey);
// 获取当前时间
long nowTs = System.currentTimeMillis();
// 创建连接管道，后续几个都是对同一key处理，使用管道提升redis存取效率
Pipeline pipe = jedis.pipelined();
// 开始事务
pipe.multi();
// 添加当前时间的行为
pip.zadd(key,nowTs,""+nowTs);
// 移除当前时间减去（特定时间）前的所有行为记录
pipe.zremrangeByScore(key,0,nowTs - period * 1000);
// 剩余的就是指定时间段内的所有行为记录
Response<Long> count = pipe.zcard(key);
// 设置过期时间
pipe.expire(key,period + 1);
pipe.exec();
pipe.close();
// 验证是否超过限制
return count.get() <= maxCount;
}
上述方案也有缺点，因为它要记录限定时间内的所有行为记录，如果这个量大，比如“限定60s内操作不能超过100万次”之类，它就不适合做这样的限流，因为会消耗大量的存储空间。
2.2 漏斗限流
漏斗限流是最常用的限流方法之一，显然，这个算法的灵感来自于漏斗的结构。
漏斗容量是有限的，若将漏嘴堵住，然后一直灌水，它就会变满，再也转不进去。如果将漏嘴放开，水就会一直流，流走一部分之后就又可以继续往里面灌水。如果漏嘴流水速率大于灌水的速率，那么漏斗永远都装不满。如果漏嘴流水速率小于灌水的速率，那么一旦漏斗满了，灌水就需要暂停并等待漏斗腾出一部分空间。
所以漏斗的剩余空间就代表着当前行为可以持续进行的数量，漏嘴的漏水速率代表着系统允许该行为的最大频率。
/**
* 根据给定的漏斗参数检查是否允许访问
*
* @param username 用户名
* @param action 操作
* @param capacity 漏斗容量
* @param allowQuota 每单个单位时间允许的流量
* @param perSecond 单位时间（秒）
* @return 是否允许访问
*/
public boolean isActionAllowed(String username, String action, int capacity, int allowQuota, int perSecond) {
String key = "funnel:" + action + ":" + username;
if (!funnelMap.containsKey(key)) {
funnelMap.put(key, new Funnel(capacity, allowQuota, perSecond));
}
Funnel funnel = funnelMap.get(key);
return funnel.watering(1);
}
private static class Funnel {
private int capacity;
private float leakingRate;
private int leftQuota;
private long leakingTs;
public Funnel(int capacity, int count, int perSecond) {
this.capacity = capacity;
// 因为计算使用毫秒为单位的
perSecond *= 1000;
this.leakingRate = (float) count / perSecond;
}
/**
* 根据上次水流动的时间，腾出已流出的空间
*/
private void makeSpace() {
long now = System.currentTimeMillis();
long time = now - leakingTs;
int leaked = (int) (time * leakingRate);
if (leaked < 1) {
return;
}
leftQuota += leaked;
// 如果剩余大于容量，则剩余等于容量
if (leftQuota > capacity) {
leftQuota = capacity;
}
leakingTs = now;
}
/**
* 漏斗漏水
*
* @param quota 流量
* @return 是否有足够的水可以流出（是否允许访问）
*/
public boolean watering(int quota) {
makeSpace();
int left = leftQuota - quota;
if (left >= 0) {
leftQuota = left;
return true;
}
return false;
}
}
其中mackSpace方法是漏斗算法的核心，其在每次灌水前都会被调用以触发漏水，给漏斗腾出空间。能腾出的空间取决于过去了多久以及流水的速率。
这种限流方式还是会有问题，我们无法保证整个过程的原子性。从hash结构中取值，然后在内存中运算，再回填到hash结构，这三个过程无法原子化，意味着需要进行加锁控制，而一旦加锁，就可能会出现加锁失败的可能，就需要选择重试或放弃。如若重试就会性能下降，如若放弃就会影响用户体验。
2.3 Redis-Cell
Redis4.0提供了一个限流Redis模块，她叫Redis-Cell。该模块使用了漏斗算法，并提供了原子的限流指令。
该模块只有1条指令cl.throttle。
cl.throttle keben 15 30 60 1
# keben key
# 15 capacity 这是漏斗容量
# 30 60 30 operations / 60 seconds 这是漏水速率
# 1 need 1 quota (可选参数，默认为1)
> cl.throttle keben 15 30 60 1
1) (integer) 0 # 0 表示允许 1 表示拒绝
2) (integer) 15 # 漏斗容量 capacity
3) (integer) 14 # 漏斗剩余空间 left_quota
4) (integer) -1 # 如果被拒绝,需要多长时间后再试
5) (integer) 2 # 多长时间后,漏斗完全空下来
3. GeoHash
Redis在3.2版本增加了地图位置Geo模块，让我们可以使用Redis来实现类似于微信的“附近的人”,共享单车的“附近的车”的功能。
GeoHash是业界比较通用的地理位置距离排序算法。GeoHash是将二维的经纬度数据映射到一维的整数，这样所有的元素都将挂载到一条线上，距离靠近的二维坐标映射到一维后的点之间的距离也会很接近。当我们想要计算“附近的人”，直接将目标位置映射到这条线上，然后在这个一维的线上获取附近的点就行了。
它将整个地球看成一个二维平面，然后划分成了一系列正方形的方格，就好比围棋棋盘。所有的地图元素坐标都将放置于唯一的方格中。方格越小，坐标越精确。然后对这些方格进行整数编码，越是靠近的方格编码越是接近。那如何编码呢？一个最简单的方案就是切蛋糕法。设想一个正方形的蛋糕摆在你面前，二刀下去均分分成四块小正方形，这四个小正方形可以分别标记为 00,01,10,11 四个二进制整数。然后对每一个小正方形继续用二刀法切割一下，这时每个小小正方形就可以使用 4bit 的二进制整数予以表示。然后继续切下去，正方形就会越来越小，二进制整数也会越来越长，精确度就会越来越高。编码之后，每个地图元素的坐标都将变成一个整数，通过这个整数可以还原出元素的坐标，整数越长，还原出来的坐标值的损失程度就越小。对于「附近的人」这个功能而言，损失的一点精确度可以忽略不计。
GeoHash算法会对上述编码的整数继续做一次base32编码(0 ~ 9,a ~ z)变成一个字符串。Redis中经纬度使用52位的整数进行编码，放进zset中，zset的value元素是key，score是GeoHash的52位整数值。在使用Redis进行Geo查询时，其内部对应的操作其实只是zset(skiplist)的操作。通过zset的score进行排序就可以得到坐标附近的其它元素，通过将score还原成坐标值就可以得到元素的原始坐标
总之，Redis中处理这些地理位置坐标点的思想是: 二维平面坐标点 --> 一维整数编码值 --> zset(score为编码值) --> zrangebyrank(获取score相近的元素)、zrangebyscore --> 通过score(整数编码值)反解坐标点 --> 附近点的地理位置坐标。
3.1 基本用法
【增加】
geoadd 指令携带集合名称以及多个经纬度名称三元组
> geoadd user 114.11342 39.12231 keben
> geoadd user 115.12345 38.12658 xiaocai
【距离】
geodist指令可以用来计算两个元素之间的距离，携带集合名称，两个名称和距离单位。单位可以是m,km,ml和ft,分别表示米,千米,英里和尺。
> geodist user keben xiaocai km
【获取元素位置】
geopos指令可以用来获取集合中的任意元素的经纬度坐标，可以一次获取多个
> geopos user keben
> geopos user keben xiaocai
【获取元素的hash值】
geohash可以获取元素的经纬度编码字符串,用这个编码可以直接取geohash.org上直接定位。
> geohash user keben
【附近的人】
georadiusbymember指令是最关键的指令之一，它可以用来查找指定元素附近的其他元素
# 范围20公里以内最多3个元素按照距离正排,不排除自身
> georadiusbymember user keben 20 km count 3 asc
# 范围20公里以内最多3个元素按照距离倒排
> georadiusbymember user keben 20km count 3 desc
# 三个可选参数 withcoord,withdist,withhash 用来携带附加参数
# withdist 很有用, 用来显示距离
【查询附近的元素】
georadius可以根据用户的定位来计算“附近的车”等。它的参数和georadiusbymember基本一致，唯一的差别是将目标元素改为了经纬度坐标值。
> georadius user 116.645322 39.890843 20 km withdist count 3 asc
在使用时注意，车的数据，人的数据可能会有百万甚至上千万条，如果使用redis的Geo数据结构，它们全部都放在一个zset集合中。如果在redis集群下，集合可能会从一个节点迁移到另一个节点，如果单个key的数据过大，会对集群的迁移工作造成较大影响，单个key的数据量不宜超过1M，否则会使得集群迁移变得卡顿，影响线上服务正常运行。
建议Geo数据使用单独的Redis部署，不适用集群环境。如果数据量过亿，就需要对Geo数据进行拆分，按照国家，省份等。
4. Scan
在平时线上 Redis 维护工作中，有时候需要从 Redis 实例成千上万的 key 中找出特定前缀的 key 列表来手动处理数据，可能是修改它的值，也可能是删除 key。这里就有一个问题，如何从海量的 key 中找出满足特定前缀的 key 列表来？
4.1 keys
Redis 提供了一个简单暴力的指令 keys 用来列出所有满足特定正则字符串规则的 key。
> keys *
> keys kob*
> keys ko*e
这个指令使用非常简单，但有两个明显缺点。
- 没有offset，limit参数，一次性显示所有满足条件的key，如果有上百万满足条件的key，同样会一次显示完。
- keys算法是遍历算法，复杂度是O(n)，如若实例中上千万以上的key，这个指令会导致redis服务卡顿。
4.2 scan
Redis 为了解决这个问题，它在 2.8 版本中加入了大海捞针的指令——scan。scan 相比keys 具备有以下特点：
- 复杂度虽然也是 O(n)，但是它是通过游标分步进行的，不会阻塞线程;*
- 提供 limit 参数，可以控制每次返回结果的最大条数，limit 只是一个 hint，返回的结果可多可少;
- 同 keys 一样，它也提供模式匹配功能;
- 服务器不需要为游标保存状态，游标的唯一状态就是 scan 返回给客户端的游标整数;
- 返回的结果可能会有重复，需要客户端去重复，这点非常重要;
- 遍历的过程中如果有数据修改，改动后的数据能不能遍历到是不确定的;
- 单次返回的结果是空的并不意味着遍历结束，而要看返回的游标值是否为零;
scan 参数提供了三个参数，第一个是 cursor 整数值，第二个是 key 的正则模式，第三个是遍历的 limit hint。第一次遍历时，cursor 值为 0，然后将返回结果中第一个整数值作为下一次遍历的 cursor。一直遍历到返回的 cursor 值为 0 时结束。
> scan 0 match key88* count 1000
> scan 122 match key88* count 1000
scan 指令是一系列指令，除了可以遍历所有的 key 之外，还可以对指定的容器集合进行遍历。比如 zscan 遍历 zset 集合元素，hscan 遍历 hash 字典的元素、sscan 遍历 set 集合的元素。
注意平日开发中尽量避免大key的产生。如若定位具体大key请使用“redis-cli -h 127.0.0.1 -p 7001 –-bigkeys -i 0.1” 这条指令每隔100条scan指令就会休眠0.1s。
预知后事如何，请看下回分解。
