网站建设申请总结,贵南网站建设,网站源码本地演示,vs网站模态框怎么做Redis 位图
开发过程中#xff0c;我们可能遇到这种场景记录用户的打卡情况#xff0c;签到情况#xff0c;这些场景只有两种结果#xff0c;有或者没有#xff0c;加入记录的数据量比较大#xff0c;比如用一年的数据#xff0c;如果用Redis中普通key/value#xff0…Redis 位图
开发过程中我们可能遇到这种场景记录用户的打卡情况签到情况这些场景只有两种结果有或者没有加入记录的数据量比较大比如用一年的数据如果用Redis中普通key/value每个用户要记录365个当用户上亿时候需要的存储就比较多了。Redis为解决这种勤快提供了位图的数据结构这样一条数据在位图中只需要占用1位365天就是365位一个字节8位你们就是46个字节左右这样大大节省空间位图的最小单位是bit每个bit只能取1或者0. 位图在Redis中就是普通字符串也就是byte数组。可以通过Redis命令get/set直接获取和设置整个位图的内容也可以使用getbit/setbit 等将byte看出位数组操作某一个位。
基本用法
Redis中提供位图的统计指令bitcount和位图查找指令bitpos bitcount统计指定范围内1 个数bitpos查找指定范围内出现的第一个0或者1。还是签到的案例我们通过bitcount统计用户一共签到多少天通过bitpos查找从那一天开始签到的。还可以指定范围参数[start, end]可以统计某个时间范围内用户签到多少天。注意此处的startend是字节的索引也就是说指定的范围必须是8的倍数1字节8位不能任意指定。如下案例
新docker-redis:0get w
hello
新docker-redis:0bitcount w
21
新docker-redis:0bitcount w 0 0 // 第一个字符中1 的位数
3
新docker-redis:0bitcount w 0 1//前两个字符中1 的位数
7
新docker-redis:0bitpos w 0 //第一个0 位
0
新docker-redis:0bitpos w 1//第一个1 位
1特殊的bitfield
Redis中setbit getbit指定的值都是单个位的如果要一次操作多个位就必须使用管道处理。Redis3.2 之后增加了一个强大的指令bitfield可以一次性处理多个位操作。bitfield 有三个基本指令getset incrby可以对指定位片段进行读写但最多只能处理64个连续位如果超过64个就得使用多个子指令bitfield可以一次执行多个指令。如下是he两个字符的bit位示意图
新docker-redis:0set w hello
OK
新docker-redis:0bitfield w get u4 0 //从第一位开始取4个位结果是无符号数u1) 6
新docker-redis:0bitfield w get u3 2 //从第三个位开始取3个位结果是无符号数u1) 5
新docker-redis:0bitfield w get i4 0 //从第一位开始取4个位结果有符号数i 0-正 1-负1) 6
新docker-redis:0bitfield w get i3 2 //从第三位开始取3个位结果是有符号i1) -3如上结果中有符号以上是第一个是按符号位算其他的才是值符号为0-正 1-负无符号标识非负数没有符合为获取到的位全是数值。有符号数最多获取64位无符号只能获取63位因为Redis协议中的integer是有符号数最大64位符号位占用一位所以只有63位数据位如果超出限制会提示参数错误。一次性执行多个指令
127.0.0.1:6379 bitfield w get u4 0 get u3 2 get i4 0 get i3 2
1) (integer) 6
2) (integer) 5
3) (integer) 6
4) (integer) -3bitfielt提供单个字节替换的功能因为1字节8为我们可以替换其中的一个8 位bit符来达到操作字节的目的如下面这个案例我们将hello中的第二个字符替换成hallo
127.0.0.1:6379 get w
hello
127.0.0.1:6379 bitfield w set u8 8 97 // 从第九位开始替换一个8bit的字节用97替换
1) (integer) 101
127.0.0.1:6379 get w
hallo同样的bitmap中也有自增命令incrby用来对指定范围的位进行自增操作因为自增的时候就可能出现数据溢出的风险Redis中默认是折返处理比如溢出后将溢出符号为丢弃如果8位无符号255加1 溢出变成0 也就是向上近位 1111 1111 变成1 0000 0000但是只有8 位所以第一位1 被舍弃变成最后的0 。bitfield指令提供溢出的操作行为默认是折返wrap还可以失败fail就是报错不执行饱和截断sat超过范围停留在最大值比如255 1 255,如下三个案例
//越界情况
127.0.0.1:6379 set w hello
OK
127.0.0.1:6379 bitfield w incrby u4 2 2 //从第三位开始对接下来4位无符号数1
1) (integer) 12
127.0.0.1:6379 bitfield w incrby u4 2 2
1) (integer) 14
127.0.0.1:6379 bitfield w incrby u4 2 1
1) (integer) 15
127.0.0.1:6379 bitfield w incrby u4 2 1 // 越界变为0
1) (integer) 0//饱和截断情况
127.0.0.1:6379 set w hello
OK
127.0.0.1:6379 bitfield w overflow sat incrby u4 2 2
1) (integer) 12
127.0.0.1:6379 bitfield w overflow sat incrby u4 2 2
1) (integer) 14
127.0.0.1:6379 bitfield w overflow sat incrby u4 2 1
1) (integer) 15
127.0.0.1:6379 bitfield w overflow sat incrby u4 2 1
1) (integer) 15//失败情况
127.0.0.1:6379 set w hello
OK
127.0.0.1:6379 bitfield w overflow fail incrby u4 2 3
1) (integer) 13
127.0.0.1:6379 bitfield w overflow fail incrby u4 2 2
1) (integer) 15
127.0.0.1:6379 bitfield w overflow fail incrby u4 2 1
1) (nil)Redis HyperLogLog
-Java web开发过程中经常需要统计网页的UV这个我们怎么实现之前我们统计PV只需要给每个网页分配一个Redis计数器就可以将key后缀加上日期每天一个每次请求incrby就行。但是UV需要区分不同的用户最笨的办法是每个也没分配一个set集合用来存储访问的用户ID但是这个方式是非常消耗内存的当有热点也没达到百万兵法时候当有N个热点也没时候那内存消耗将会是一个非常大的数量Redis中HyperLogLog引入来一个新的解决方案提供来不精确的去重计数方案虽然不精确但是标准误差也就0.81%而已对于统计UV的这种业务场景是完全能够接受的。
HyperLogLog使用方式
127.0.0.1:6379 pfadd code userq
(integer) 1
127.0.0.1:6379 pfadd code user1
(integer) 1
127.0.0.1:6379 pfcount code
(integer) 2如上Redis中HyperLogLog提供pfaddpfcount一个增加一个统计我们试了一把统计没有误差,我们执行100000 次add操作来测试他的误差以及性能
public class HypLogLogDemo {public static final String key code;public static void main(String[] args) {Jedis jedis JedisUtils.getJedis();for (int i 0; i 100000; i) {jedis.pfadd(key, user i);}long total jedis.pfcount(key);System.out.println(total);}
}
//输出99715如上结果相差285个按照0.285%的误差对于UV的统计需求误差可以忽略我们可以多次重复执行其实还是得到近似的结果说明他有去重的功能。
pfmerge
HypLogLog除了提供上面的两个命令还有一个merge功能用于将多个计数器累加成一个新的pf值比如多个内容相似的网页运营需要合并统计就可以用这个来统计。HyperLogLog这个数据结构占用内存异常的小只需要占用12KB内存如果统计的计数有亿级别那么对空间的节省是非常令人惊讶的
存储原理 HypLogLog有以下几个特点 实现比较困难能够用极少的内存来统计巨量的数据在Redis中实现的HyperLogLog只需要12k内存就能统计2^64个数据计数存在一定的误差0.81%误差可以被设置辅助计算因子进行降低 12K是一个什么概念1byte8bitlong类型是8字节64bit对应2^63-1 个数那假设有这么多个数从0 ~ 2 ^ 63-1,按照long以及1k1026字节内存总数应该是2 ^ 63-1 * 8.1024K这个远远超过来12k。
伯努力试验
HyperLogLog用极少内存完成巨量数据计算我们先需要了解他的数学原理伯努利试验概率论抛硬币一次得到正反概率都是50%假设一直抛硬币一直到得到一次正面记这位一次完整试验期间记录抛硬币的次数这个试验就是伯努利试验对于多次伯努利试验假设多次为n次每次试验抛次数为K抛K次得到正面因此第一次k1 依次类推第n次kn期间必然在n次试验中有一个最大抛次数k我们称为k_max。伯努利试验容易得出如下结论 n次伯努利过程抛次数不大于k_maxn次伯努利过程至少依次k_max 结合极大似然估算方法可以发现n和k_max的估算关联 n 2^(k_max)这种估算方法需要用概率论和数理统计方法推导证明此处略过。
第一次试验: 抛了3次才出现正面此时 k3n1
第二次试验: 抛了2次才出现正面此时 k2n2
第三次试验: 抛了6次才出现正面此时 k6n3
第n 次试验抛了12次才出现正面此时我们估算 n 2^12如上试验共三组k_max6n3代如公式3 ! 2^6。此处只能说明样本太少估算误差大。
估算优化
我们假设上面3次试验算一轮当n足够大估算误差才小例如我们进行100 轮然后每一轮取出k_max在取出平均数即k_max/100在估算数n下面是LogLog的估算公式 上面公式中DVLL对于的是ncontant是修正因子具体值不定可以根据时间情况分钟设置m代表试验轮次头上有一横的R就是平均数k_max_1…k_max_n/m。这种通过增加试验次数在取k_max平均数的算法优化就是LogLog的做法而HyperLogLog和LogLoe有一点区别不是用平均数而是调和平均数相对平均数更不容易受到大数的影响。如下案例
A月薪1000B月薪30000
平均数(100030000)/215500
调和平均数2/(1/1000 1/30000) ~ 1935.484显然调和平均数比平均数更准确表达事实情况下面是调和平均数的计算方式∑ 是累加符号 以上其实就是他的数学原理。
带入实际案例讲解
上面的内容中通过抛硬币的案例解释了伯努利实验通过k_max来估算n那么这种估算方法和我们UV统计方式有什么关联我们需求是统计APP或者网页的一个页面每天有多少个不同的用户点击进入的次数。同一个用户的反复点击进入记为1。HyperLogLog是按如下几个步骤操作
获取比特串
通过Hash函数将数据转为比特串比如输入一个用户id5我们转成101通过这种方式将访问用户数据和上面的抛硬币对应上比特串中0 代表反面1 代表正面如果一个数据最终被转成10010000那么按照从右到左从低位到高位看我们认为首次出现1 的时候代表正面。基于上面的估算结论我们可以通过多次试验的最大抛到正面的次数来预估总共进行了多少次实验同样更具存储的数据中转化后出现了1 的最大值k_max来估算出总量n。
分桶存储
分桶就是分开进行多轮次。抽象到计算机中存储可以看成是一个以单位是bit长度是L的大的数组S将S平均分成M组这里的M其实就是对应多少轮然后每组锁占有的比特个数是平均的设为P我们可以得出以下公式 L S.lengthL M * P以K为单位S占用内存 L / 8 / 1024 在Redis中HyperLogLog设置为 m16834p6L168346。占用内存为168346/8/1024 12K如下示意来标识他存储的结构 第0组 第1组 第2组 第3组 .... 第16833组
[000 000] [000 000] [000 000] [000 000] .... [000 000]对应存储规则
我们回到原始APP页面统计的具体问题中设APP主页的key为main 用户ididn n-0,1,23 …在这个统计问题中不同用户id标识了一个用户你们我们可以把用户id作为被hash的输入hashid 比特串不同的用户id必然有不同比特串每一个比特串也必然至少出现一次1 的位置我们类比每一个比特串就是一次伯努利试验现在要分轮次即分桶存储设定每个比特串钱w位转为10进制后其值就对应于所在的桶的下标1~16833。假设比特串的低两位用来计算桶下标此时有一个用户id的比特串是1001 0110 0001 1他的下标为 11(二进制) 12 ^ 0 12 ^ 1 3处于第三个桶。即第三轮上面案例中计算桶号后剩下的比特串 1001 0110 000 从低位到高位看第一次出现1 的位置是5 也就是说此时第三个桶第三轮试验中k_max 5, 5 对应二进制是 101又因为每个通有p个比特位单 p 3 时候便可以将101存进去三个比特位。模拟上面流程多个不同用户id就被分配到不同桶中区了并且每个桶有其k_max然后统计出main页面有多少用户点击量就是一次估算。最终结合所有桶中的k_max带入估算公式便得出我们的估算值。更具上面调和平均数的公式得出下面HyperLogLog的估算公式变量的意义和LogLog的一样 其中以下表示每个通的估计值对每个通估计值进行调和平均数求职
Redis中HyperLogLog的原理
首先Redis中HyperLogLog是他的意志高级数据结构他的实现有16384个桶即 2^14 16384每个桶有6位每个桶可以表达的最大数字是 2 ^ 5 2 ^ 4 2 ^ 3 2 ^ 2 2 ^ 1 63,二进制是111 111。对应pfadd key value命令存储时候value被hash成64 位即64bit位前14位用来分桶前14位的二进制转成10进制就是通标号。之所以选14位是因为2^14 16384 刚好最大的时候可以把桶利用完不造成浪费假设一个字符串的钱14位是00 0000 0000 0010其十进制是2 ^ 1 2,你们就会被放到编号是2 的桶
前14位全是1
2 ^ 13 2 ^ 12 ...... 2 ^ 5 2 ^ 4 2 ^ 3 2 ^ 2 2 ^ 1 2 ^ 0 16383 16384Index的转化规则 因为完整value是64位减去低位14位剩下高位50 位极端情况出现1 的位置是第50位次数index 50转二进制是 110010不超过6 bit数所以刚好可以被设置到第2 号桶中去因为50是最坏的情况类比第五十次才抛出正面最坏情况其他情况必然都能被存储到桶中如果不同value有相同的前面 14 位也就是两个用户hashuserid 得到的64位低位14 位相同但是后面出现1 的位置不同。那么比较原来的index是否比新的index打是则替换否则不变存储更大的数字最终一个key对应的16384 个桶都设置了很多的value每个桶有一个k_max此时调用pfcount 时候按前面介绍估算方法计算key的设置了多少次的value就得到对应统计值 value被转为64 位比特串最终被按照上做法记录到每个桶中64位转十进制2 ^ 64 ,HyperLogLog仅仅用了16384 * 6 /8/1024 12K存储空间就能够完成2 ^64 数量基数的数据统计。
布隆过滤器
上面HyperLogLog中如果我想知道某个userId是不是已经存储了发现找不到对应Redis命令来查找因为HyperLogLog只提供了addcount的功能没有提供contant功能。如果有这样的业务比如我们做用户推荐新闻推荐的时候他会给我们不停的推荐新内容怎么去掉已经看过的内容。推送去重这是一个问题用set存储历史记录太费内存在Redis高级数据结构中布隆过滤器Bloom Filter专门用来解决去重问题。并且空间上节省90%以上但是他会有一点不精确可能导致微小的误判。
Redis中的布隆过滤器
Redis4.0 才提供了bloomfilter但是他是作为一个插件加载到Redis server中给Redis提供了强大的布隆过滤功能布隆过滤器有两个基本指令 bf.add添加元素 一次只能添加一个元素bf.madd 添加元素一次可以添加多个bf.exists 判断是否存在一次判断一个bf.mexists 判断多个元素是否存在
布隆过滤器原理
每个bloomFilter 对应到Redis的数据结构就是一个大小的bitmap加上杰哥不一样的无偏hash函数如下面图f,g,h就是这样的hash函数。所谓的无偏就是能把元素值算的比较均匀让元素被hash后映射到位数字中的位置比较随机。 想bloomfilter中添加key时候会使用多个hash函数对key进行hash算得一个整数值然后对维数组长度进行取模运算得到这个整数在位数组中的位置每个hash函数都会算得一个不同的位置再把这个位数组的这几个位置都设置为1就完成add操作。所以其实一个key是会标记多个bit位这取决于他hash算法的个数每个hash都出来一个位置。减少重复率向bloomFilter询问key是否存在是也和add一样吧hash的几个位置算出看bitmao里面是不是都是1有一个是0 就一定不存在 。但是都是1 并不100%保证一定存在只是极有可能存在因为这些被设置为1 可能是其他key存在的hash位如果数组比较稀疏判断的正确率就高如果数组拥挤误判就高。bloomFilter使用之前可以指定其参数Redis提供了自定义参数的BloomFilter我们需要在add之前用bf.reserve显示的创建如果对于key已经存在你们bf.reserve会报错。bf.reserve有三个参数key error_rate错误率 initial_size预计数据大小 error_rate越低需要空间越大initial_size表示预计放入的元素数量当实际数量超过这个数误判就会上升所以需要提前设置一个较大的数值避免超过导致误判率升高如果不使用bf.reserver默认的error_rate是0.01默认的initial_size是100.
空间占用估计
bloomFilter空间占用有一个简单计算公式不推导了直接给吧有两个参数第一个语句元素数量n第二个错误率f 公式根据两个输入得到两个输出第一个输出是位数组的长度1也就是需要的存储空间大小bit第二个输出是hash函数的最佳数量k。hash函数的数量也直接影响错误率最佳数量会有最低错误率。
k 0.7 *(1/n) //约等于
f 0.6185^(1/n) 如上公式得出 位数越长1/n,错误率发越低位数月长1/nhash函数需要的最佳数量也越多影响计算效率当一个元素评价需要1字节8bit的指纹空间槽空间时候1/n 8错误率大概2%错误率0.1% 时候一个元素平均指纹空间14.377bit大约15bit 即使15bit也比set强因为这边是15位set存储取决于他存储的字符串大小不是一个量级。
元素超出误判率变化
当实际元素超过预计元素错误率会有多大变化这个也有公司引入参数t 表示实际元素和预计元素的倍数
f (1-0.5^t) ^k // 极限近似k是hash函数最佳数量-暂时就这些
上一篇Redis基础数据结构内部实现简单介绍 下一篇Redis流量控制策略
