03 纸上得来终觉浅(下)
基于Redis6，本章节主要介绍了Rdis的一些主要应用场景，包含了：大数据的过滤，分布式锁设计，并讲解了有趣的布隆过滤器原理，HyperLogLog 原理，二进制位数与存储大小计算的常识
大数据过滤
需求场景
某平台需要给用户不断推荐新的新闻内容，它每次推荐时要进行去重，去掉那些已经看过的内容，请问怎么去做？
大部分人的第一反应是通过Set来存储新闻的唯一编号，利用set天然去重。
当然我们的解决方案不可能这么简单，试想下如此多的历史记录全部缓存起来，那得浪费掉多大存储空间呀？且访问是按照线性增长的，时间越久性能就越差，宝贵内存资源浪费也越严重。此时我们就可以使用Redis中的布隆过滤器来解决。
布隆过滤器就是专门用来解决这种去重问题的，可以节约大量的空间，但存在一定的误判。
我们可以把布隆过滤器看成一个不那么精确的set，当它说某个值存在时，可能是不存在的；但是当它说不存在，那肯定是不存在的。用在上面场景里就是：当它说新闻是新的时候，那一定是新的；当它说新闻不是新的时候，有可能是新的，这个结果满足了上述场景要求。
插件安装使用
布隆过滤器是以插件的形式发挥作用的，可以前往Releases · RedisBloom/RedisBloom · GitHub进行下载源码编译安装，遵从以下步骤
- 解压缩后使用
make编译生成动态链接库redisbloom.so - 拷贝动态链接库：
cp redisbloom.so usr/local/bin/ - redis.conf配置文件中添加动态链接库：
loadmodule redisbloom.so - 重启redis
布隆过滤器主要操作：
模拟新闻编号判断：
好像很准确啊，一个也没有误判，那是因为我们数据量太小。根据笔者实验，一般几百数据量的情况下就会出现误判。
另外其实我们是可以通过bf.reserve 参数来重新设置过滤器的误判率的：
在我们实际的互联网环境下，有很多技术都利用了布隆过滤器的原理，比如爬虫系统判断URL是否爬过。
还有NOSQL领域的： HBase、Cassandra 还有 LevelDB、RocksDB 内部都有布隆过滤器结构，布隆过滤器可以显著降低数据库的 IO 请求数量。当用户来查询某个 row 时，可以先通过内存中的布隆过滤器过滤掉大量不存在的 row 请求，然后再去磁盘进行查询。
邮箱系统的垃圾邮件过滤功能也普遍用到了布隆过滤器，因为用了这个过滤器，所以平 时也会遇到某些正常的邮件被放进了垃圾邮件目录中，这个就是误判所致，概率很低。
分布式锁设计
基于Redis的分布式锁设计一般分为单机的redis和集群的redis
单个Redis分布式锁
业界通用的设计方案就是利用SETNX 和 DEL 命令组合来实现加锁和释放锁操作。伪代码如下：
// 加锁
SETNX lock_key 1
// 业务逻辑
DO THINGS
// 释放锁
DEL lock_key
//超时释放
Expire lock_key
上述伪代码还存在两个潜在风险：1 业务逻辑发生异常或宕机，导致释放机制失效；2 业务逻辑执行时间过长，锁超时或被其它线程释放了，导致并发问题
第一个风险我们可以加上一个异常捕获，先解决异常情况下的锁释放问题，然后利用redis提供的新方法：
SET key value [EX seconds | PX milliseconds] [NX]
命令示例：Set lock:bizxxx true ex 5 nx
让redis保证SETNX和Expire指令的原子性；
第二个风险我们可以引入随机数(客户端唯一标识也行)，验证随机数保证了锁不会被其它线程释放掉，由于随机数的判断和删除缺乏原子性，我们还需要引入LUA脚本，保证随机数品判断匹配和删除的逻辑的原子性。
整个过程伪代码：
//unlock.script是Lua脚本
redis-cli --eval unlock.script lock_key , unique_value
//释放锁 比较unique_value是否相等，避免误释放
if redis.call("get",KEYS[1]) == ARGV[1] then
return redis.call("del",KEYS[1])
else
return 0
end
Redis集群分布式锁
当我们要实现高可靠的分布式锁时，就不能只依赖单个的命令操作了，我们需要按照一定的步骤和规则(分布式锁算法)进行加解锁操作，否则，就可能会出现锁无法工作的情况。
Redis 的开发者 Antirez 提出了分布式锁算法 Redlock。
Redlock 算法的基本思路，是让客户端和多个独立的 Redis 实例依次请求加锁，如果客户端能够和半数以上的实例成功地完成加锁操作，那么我们就认为，客户端成功地获得分布式锁了，否则加锁失败。
这样一来，即使有单个 Redis 实例发生故障，因为锁变量在其它实例上也有保存，所以，客户端仍然可以正常地进行锁操作，锁变量并不会丢失。
整个分布式加锁可以分为3个步骤：
- 1 客户端获取当前时间
- 2 客户端按顺序依次向 N 个 Redis 实例执行加锁操作
- 3 一旦客户端完成了和所有 Redis 实例的加锁操作，客户端就要计算整个加锁过程的总耗时
加锁成功要满足两个条件：1 客户端从超过半数（大于等于 N/2+1）的 Redis 实例上成功获取到了锁；2 客户端获取锁的总耗时没有超过锁的有效时间。
在满足了这两个条件后，我们需要重新计算这把锁的有效时间，计算的结果是锁的最初有效时间减去客户端为获取锁的总耗时。如果锁的有效时间已经来不及完成共享数据的操作了，我们可以释放锁，以免出现还没完成数据操作，锁就过期了的情况。
当然不推荐大家去根据算法去实现分布式锁，可以的话还是采用开源或已成熟的解决方案
分布式锁小结
我个人认为Redis的分布式锁是一个比较轻量的解决方案，可以满足我们99%的业务场景，但是如果你的业务要求是99.99%，甚至更高，那么你应该采用其它分布式锁技术比如：zk、etcd等，确保万无一失。
附录一：位数与存储大小计算
要计算多少位数需要多少个字节来保存，我们首先要清楚2的多少次方的计算结果能覆盖我们要保存的数据位数。
比如我们要保存一个10位数，10位数在数值大小上是十亿，我们要保证覆盖最大十亿数，那么到达百亿就能满足了。
根据2的指数运算：
2的34次方的时候达到了百亿，也就是2的34次方对应需要多少个字节呢？我们都知道1个字节占8位，34位大约是4.25个字节。
但是我们要知道在计算机语言中，数据是有类型的，int型最大的能表示的数为2的32次方，也就是十亿级别的，既然int型数据不能满足要求，那就只能采用long类型了
long的类型能表示的数为2的64次方，这个数太大了，足足有20位，满足10位数绰绰有余，而64位，占了8个字节。
附录二：HyperLogLog 原理
HyperLogLog使用非常简单，其实现依据说起来也很简单，但是证明理解起来就没那么简单了，需要用到概率学的知识
先讲下依据，HyperLogLog 是利用概率结果来估算实验次数，是不是看起来有点神奇和懵逼？
举个具体的例子：某天吃完饭，你和你女朋友玩抛硬币游戏，你女朋友负责抛硬币，她抛了的轮数记为n，每一次都会记录正面是在本轮中第K次出现的。然后她告诉你K的最大值，让你猜n的值。
作为理工男的你马上意识到这是个伯努利过程在脑海里进行了概率计算：
算了下kmax在回合出现的概率是(1/2)^k * max，得到： n = 2^k * max，当你女朋友告诉你最大K=3，你胸有成竹的脱口而出：8！
结局是她只抛了1次，于是你输了，负责刷碗。
并不是你的计算不对，而是单次的概率不符合大数定律，而Philippe Flajolet教授吸取了你的教训，引入了桶的概念，再利用调和平均数减少误差。
其中m是桶的数量，const是修正常数，它的取值会根据m而变化。
笔者写了一个简化版测试程序，计算了下误差值，真实算法更复杂，误差值也更低
100000 96673.07 误差：0.03
200000 196276.45 误差：0.02
300000 295135.37 误差：0.02
400000 396655.24 误差：0.01
500000 506963.14 误差：0.01
600000 603743.24 误差：0.01
700000 759724.06 误差：0.09
800000 803806.54 误差：0.00
900000 892418.41 误差：0.01
上面代码用了1024个桶，而在 Redis 的 HyperLogLog 实现中用到的是 16384 个桶，也就是 2^14，每个桶的 maxbits 需要 6 个 bits 来存储，最大可以表示 maxbits=63，于是总共占用内存就是 2^14 * 6 / 8 = 12k 字节。
帮助我们理解原理的工具：Sketch of the Day: HyperLogLog — Cornerstone of a Big Data Infrastructure – AK Tech Blog (neustar.biz)
附录三：布隆过滤器原理
每个布隆过滤器对应到 Redis 的数据结构里面就是一个大型的位数组和几个不一样的无偏 hash 函数。所谓无偏就是能够把元素的hash值算得比较均匀。
向布隆过滤器中添加 key 时，会使用多个 hash 函数对 key 进行 hash 算得一个整数索引值然后对位数组长度进行取模运算得到一个位置，每个hash函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。
