关于redis:Redis-实战-08-实现自动补全分布式锁和计数信号量

主动补全 `P109`

主动补全在日常业务中随处可见，应该算一种最常见最通用的性能。理论业务场景必定要包含蕴含子串的状况，其实这在肯定水平上转换成了搜寻性能，即蕴含某个子串的串，且优先展现前缀匹配的串。如果仅蕴含前缀，那么能够应用 Trie 树，但在蕴含其余的状况下，应用数据库 / ES 自身自带查问就足够了。能够依照四种状况（准确匹配、前缀、后缀、蕴含（也可将后两种交融成蕴含）），别离查问后果，直至达到数据条数下限或者全副查问结束。但这种应用办法有毛病：查问次数多、难以分页。不过理论场景中须要补全的状况都只有第一页的数据即可。

主动补全最近联系人 `P110`

需要： 记录最近分割过的 100 集体名，并反对对输出的串进行主动补全。P110

数据量很小，所以能够在 Redis 中用列表保护最近联系人，而后在内存中进行过滤可主动补全的串。

步骤： P111

保护长度为 100 的最近联系人列表
1. 如果指定的联系人已在列表中，则从列表中移除 (LREM)
2. 将指定的联系人增加到列表最后面 (LPUSH)
3. 如果增加实现后，列表长度超过 100，则对列表进行修剪，仅保留列表后面的 100 个联系人 (LTRIM)
获取整个最近联系人列表，在内存中依据四种状况进行过滤即可

通讯录主动补全 `P112`

需要： 有很多通讯录，每个通讯录中有几千个人（仅蕴含小写英文字母），尽量减少 Redis 传输给客户端的数据量，实现前缀主动补全。P112

思路： 应用有序汇合存储人名，利用有序汇合的个性：当成员的分值雷同时，将依据成员字符串的二进制程序进行排序。如果要查找 abc 前缀的字符串，那么实际上就是查找介于 abbz... 之后和 abd 之前的字符串。所以问题转化为：如何找到第一个排在 abc 之前的元素的排名和第一个排在 abd 之前的元素的排名。咱们能够结构两个不在有序汇合中的字符串 (abb{, abc{) 辅助定位，因为 { 是排在 z 后第一个不实用的字符，这样能够保障这两个字符串不存在与有序汇合中，且满足转化后的问题的限度。P113

综上： 通过将给定前缀的最初一个字符替换为第一个排在该字符前的字符，再再在开端拼接上左花括号，能够失去前缀的前驱 (predecessor)，通过给前缀的开端拼接上左花括号，能够失去前缀的后继 (successor)。

字符集：当解决的字符不仅仅限于 a~z 范畴，那么要解决好以下三个问题：P113
- 将所有字符转换为字节：应用 UTF-8、UTF-16 或者 UTF-32 字符编码（ 留神： UTF-16 和 UTF-32 只有大端版本可用于上述办法）
- 找出须要反对的字符范畴，确保所选范畴的后面和前面至多留有一个字符
- 应用位于范畴前后的字符别离代替反引号 ` 和左花括号 {

步骤： P114

使用思路中的办法找到前缀的前驱和后继（为了避免同时查问雷同的前缀呈现谬误，能够在前驱和后继之后增加上 UUID）
将前驱和后继插入到有序汇合里
查看前驱和后继的排名
取出他们之间的元素
从有序汇合中删除前驱和后继

通过向有序汇合增加元素来创立查找范畴，并在获得范畴内的元素之后移除之前增加的元素，这种技术还能够利用在任何已排序索引 (sorted index) 上，并且能通过改善（第七章介绍）利用于几种不同类型的范畴查问，且不须要通过增加元素来创立范畴。P115

分布式锁 `P115`

分布式锁在业务中也十分常见，可能防止在分布式环境中同时对同一个数据进行操作，进而能够防止并发问题。

导致锁呈现不正确行为，以及锁在不正确运行时的症状 `P119`

持有锁对过程因为操作工夫过长而导致锁被主动开释，但过程自身并不通晓这一点，甚至还可能会谬误地开释掉了其余过程持有但锁
一个持有锁并打算执行长时间操作但进行曾经解体，但其余想要获取锁但过程不晓得哪个过程持有锁，也无奈检测出持有锁但过程曾经解体，只能白白地浪费时间期待锁主动开释
在一个过程持有但锁过期之后，其余多个过程同时尝试去获取锁，并且都获取了锁
第一种状况和第三种状况同时呈现，导致有多个过程获取了锁，而每个过程都认为本人是惟一一个取得锁但过程

简略示例

// 在 conn 上获取 key 的锁，锁超时工夫为 expiryTime 毫秒，等待时间最长为 timeout 毫秒
func acquireLock(conn redis.Conn, key string, expiryTime int, timeout int) (token *int) {
    // 为了简化，用 纳秒工夫戳 当 token，理论应该用 UUID
    value := int(time.Now().UnixNano())

    for ; timeout >= 0; {
        // 尝试加锁
        _, err := redis.String(conn.Do("SET", key, value, "PX", expiryTime, "NX"))
        // 如果获取锁胜利，则间接返回 token 指针
        if err == nil {return &value}
        // 睡 1ms
        time.Sleep(time.Millisecond)
        timeout --
    }

    // timeout 内仍未胜利获取锁，则获取失败，返回 nil
    return nil
}

// 在 conn 上开释 key 的锁，且锁与 token 对应
func releaseLock(conn redis.Conn, key string, token int) error {
    // 用 lua 脚本保障原子性，只有 token 和值相等是才开释
    releaseLua := "if redis.call('get', KEYS[1]) == ARGV[1] then return redis.call('del', KEYS[1]) else return 0 end"
    script := redis.NewScript(1, releaseLua)
    result, err := redis.Int(script.Do(conn, key, token))
    if err != nil {return err}
    if result == 0 {return errors.New("release failure")
    }
    return nil
}

计数信号量 `P126`

计数信号量是一种锁，它能够让用户限度一项资源最多能同时被多少个过程拜访，通常用于限定可能同时应用的资源数量。P126

根本的计数信号量 `P126`

将多个信号量的持有者的信息存储到同一个有序汇合中，即为每个尝试获取的申请生成一个 UUID，并将这个 UUID 作为有序汇合的成员，而成员对应的分值则是尝试获取时的工夫戳。P127

获取信号量步骤： P127

清理有序汇合中所有已过期的 UUID（工夫戳 <= 过后工夫戳 – 过期工夫）
生成 UUID，应用过后工夫戳作为分值，将 UUID 增加到有序汇合外面
查看刚刚的 UUID 的排名
- 若排名低于可获取的信号量总数（成员排名从 0 开始计算），那么示意胜利获取了信号量
- 若排名等于或高于可获取的信号量总数，那么未获取胜利，须要将刚刚的 UUID 移除

开释信号量时间接从有序汇合中删除 UUID 即可。若返回值为 1，则表明胜利手动开释；若返回值为 0，则表明曾经因为过期而主动开释。P128

毛病：

所有信号量的过期工夫都须要一样：为了不便删除过期的 UUID
不偏心，依赖零碎工夫：
- 当多机环境下，A 的零碎工夫比 B 的零碎工夫快 10ms，那么当 A 获得了最初一个信号量的时候，B 只有在 10ms 内尝试获取信号量，那么就会造成 B 获取了不存在的信号量，导致获取的信号量超过了信号量的总数。P128
- 还可能造成信号量提前被其余零碎的获取申请开释

偏心的计数信号量 `P128`

为了实现偏心的计数信号量，即先收回获取申请的客户端可能获取到信号量。咱们须要在 Redis 中保护一个自增的计数器，每次收回获取申请前先对其自增，并应用自增后的值作为分值将对应的 UUID 插入到另一个有序汇合中。即本来的有序汇合仅用来查找并删除过期的 UUID，新的有序汇合用来获取排名判断申请是否胜利获取到信号量。同时为了放弃新的有序汇合及时删过期的 UUID，在本来的有序汇合执行完删除操作后，还要应用 ZINTERSTORE 命令，保留仅在本来有序汇合中呈现的 UUID (ZINTERSTORE count_set 2 count_set time_set WEIGHTS 1 0)。 留神： 若信号量获取失败，则须要及时删除本次插入的无用数据。

上述办法能在肯定水平上解决信号量获取数超过信号量总数的问题，但删除过期 UUID 的中央还是依赖本地工夫，所以尽量保障各个主机的零碎工夫差距要足够小。P131

自我思考：做到与零碎工夫无关

去除本来的有序汇合，仅留下计数器和计数值作为分值的有序汇合，并对于每个 UUID 都设置一个有过期工夫的键，每次移除前，遍历有序汇合，并查问其是否过期，并从有序汇合中删除所有已过期的 UUID。

这样做不仅能齐全达到与零碎工夫无关，还不会存在信号量获取数超过信号量总数的问题，且可能实现单个获取的信号量能有不同的过期工夫，也肯定水平上升高了工夫复杂度，不过会减少客户端与 Redis 服务器之间的交互次数。

刷新信号量 `P131`

信号量使用者可能在过期工夫内无奈解决完申请，此时就须要续约，缩短过期工夫。因为偏心的计数信号量已将工夫有序汇合和计数有序汇合离开，所以只须要在工夫有序汇合中对 UUID 执行 ZADD 即可，若执行失败，则已过期主动开释。P131

对于我刚刚提出的那种办法，有两种办法能够续约：

应用 lua 脚本保障原子性
先读取过期工夫
- 未过期：再应用带 XX 选项的 SET 命令设置新的过期工夫（须要加上原有的过期工夫），返回胜利则续约胜利，否则续约失败
- 已过期：续约失败

打消竞争条件 `P132`

两个过程 A 和 B 都在尝试获取残余的一个信号量时，即便 A 首先对计数器执行了自增操作，但只有 B 可能领先将本人的 UUID 增加到计数有序汇合中，并查看 UUID 的排名，那么 B 就能够胜利获取信号量。之后 A 再将本人的 UUID 增加到有序汇合里，并查看 UUID 排名，那么 A 也能够胜利获取信号量，最终导致获取的信号量多余信号量总数。P132

为了打消获取信号量时所有可能呈现的竞争条件，构建一个正确的计数信号量，咱们须要用到后面实现的带有超时性能的分布式锁。在想要获取信号量时，首先尝试获取分布式锁，若获取锁胜利，则继续执行获取信号量的操作；若获取锁失败，那么获取信号量也失败。P132

不同计数信号量的应用场景 `P133`

根本的计数信号量：对于多机系统工夫的差别不关怀，也不须要对信号量进行刷新，并且可能接管信号量的数量偶然超过限度
偏心的计数信号量：对于多机系统工夫的差别不是十分敏感，但依然可能接管信号量但数量偶然超过限度
正确的计数信号量：心愿信号量统一具备正确的行为

本文首发于公众号：满赋诸机（点击查看原文）开源在 GitHub：reading-notes/redis-in-action

关于redis:Redis-实战-08-实现自动补全分布式锁和计数信号量

主动补全 P109

主动补全最近联系人 P110

通讯录主动补全 P112

分布式锁 P115

导致锁呈现不正确行为，以及锁在不正确运行时的症状 P119

简略示例

计数信号量 P126

根本的计数信号量 P126

偏心的计数信号量 P128