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导致的。

image

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 的二进制整数予以表示。然后继续切下去，正方形就会越来越小，二进制整数也会越来越长，精确度就会越来越高。编码之后，每个地图元素的坐标都将变成一个整数，通过这个整数可以还原出元素的坐标，整数越长，还原出来的坐标值的损失程度就越小。对于「附近的人」这个功能而言，损失的一点精确度可以忽略不计。

image

​ 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。

    预知后事如何，请看下回分解。