Appearance
六、Redis新类型bitmap-hyperloglgo-GEO
1、统计
存的进+取得快+多统计
1、统计的类型有哪些？
1、聚合统计
统计多个集合元素的聚合结果，就是前面讲解过的交差并等集合统计
交并差集和聚合函数的应用
2、排序统计
抖音视频最新评论留言的场景，请你设计一个展现列表。考察你的数据结构和设计思路
list:
每个商品评价对应一个List集合，这个List包含了对这个商品的所有评论，而且会按照评论时间保存这些评论，
每来一个新评论就用LPUSH命令把它插入List的队头。但是，如果在演示第二页前，又产生了一个新评论，
第2页的评论不一样了。原因：
List是通过元素在List中的位置来排序的，当有一个新元素插入时，原先的元素在List中的位置都后移了一位，
原来在第1位的元素现在排在了第2位，当LRANGE读取时，就会读到旧元素。
zset:
在⾯对需要展示最新列表、排行榜等场景时，
如果数据更新频繁或者需要分页显示，建议使⽤ZSet
3、二值统计
集合元素的取值就只有0和1两种。
在钉钉上班签到打卡的场景中，我们只用记录有签到(1)或没签到(0)
见bitmap
4、基数统计
指统计⼀个集合中不重复的元素个数
见hyperloglog
2、bitmap
1、简介
- 现代计算机用二进制（位） 作为信息的基础单位， 1个字节等于8位， 例如“abc”字符串是由3个字节组成， 但实际在计算机存储时将其用二进制表示， “abc”分别对应的ASCII码分别是97、 98、 99， 对应的二进制分别是01100001、 01100010和01100011，如下图
合理地使用操作位能够有效地提高内存使用率和开发效率。
Redis提供了Bitmaps这个“数据类型”可以实现对位的操作：
Bitmaps本身不是一种数据类型， 实际上它就是字符串（key-value） ， 但是它可以对字符串的位进行操作。
Bitmaps单独提供了一套命令， 所以在Redis中使用Bitmaps和使用字符串的方法不太相同。 可以把Bitmaps想象成一个以位为单位的数组， 数组的每个单元只能存储0和1， 数组的下标在Bitmaps中叫做偏移量。
由0和1状态表现的二进制位的bit数组
2、基本命令
1、setbit
setbit key offset value
setbit 键 偏移位 只能零或者1
Bitmap的偏移量是从零开始算的
示例
- 每个独立用户是否访问过网站存放在Bitmaps中， 将访问的用户记做1， 没有访问的用户记做0， 用偏移量作为用户的id。
- 设置键的第offset个位的值（从0算起） ， 假设现在有20个用户，userid=1， 6， 11， 15， 19的用户对网站进行了访问， 那么当前Bitmaps初始化结果如图
- unique:users:20201106代表2020-11-06这天的独立访问用户的Bitmaps
- 很多应用的用户id以一个指定数字（例如10000） 开头， 直接将用户id和Bitmaps的偏移量对应势必会造成一定的浪费， 通常的做法是每次做setbit操作时将用户id减去这个指定数字。
- 在第一次初始化Bitmaps时， 假如偏移量非常大， 那么整个初始化过程执行会比较慢， 可能会造成Redis的阻塞。
2、getbit
getbit key offset示例
- 获取id=8的用户是否在2020-11-06这天访问过， 返回0说明没有访问过：
- 注：因为100根本不存在，所以也是返回0
3、bitcount
统计字符串被设置为1的bit数。一般情况下，给定的整个字符串都会被进行计数，通过指定额外的 start 或 end 参数，可以让计数只在特定的位上进行。start 和 end 参数的设置，都可以使用负数值：比如 -1 表示最后一个位，而 -2 表示倒数第二个位，start、end 是指bit组的字节的下标数，二者皆包含。
bitcount<key>[start end] 统计字符串从start字节到end字节比特值为1的数量
计算2022-11-06这天的独立访问用户数量
start和end代表起始和结束字节数， 下面操作计算用户id在第1个字节到第3个字节之间的独立访问用户数， 对应的用户id是11， 15， 19。
注意：redis的setbit设置或清除的是bit位置，而bitcount计算的是byte位置。
4、bitop
bitop and(or/not/xor) <destkey> [key…]
bitop是一个复合操作， 它可以做多个Bitmaps的and（交集） 、 or（并集） 、 not（非） 、 xor（异或） 操作并将结果保存在destkey中。
示例
2020-11-04 日访问网站的userid=1,2,5,9。
setbit unique:users:20201104 1 1
setbit unique:users:20201104 2 1
setbit unique:users:20201104 5 1
setbit unique:users:20201104 9 1
2020-11-03 日访问网站的userid=0,1,4,9。
setbit unique:users:20201103 0 1
setbit unique:users:20201103 1 1
setbit unique:users:20201103 4 1
setbit unique:users:20201103 9 1计算出两天都访问过网站的用户数量
bitop and unique:users:and:20201104_03
unique:users:20201103unique:users:20201104
计算出任意一天都访问过网站的用户数量（例如月活跃就是类似这种） ， 可以使用or求并集
3 、Bitmaps与set对比
- 假设网站有1亿用户， 每天独立访问的用户有5千万， 如果每天用集合类型和Bitmaps分别存储活跃用户可以得到表
- set和Bitmaps存储一天活跃用户对比
| 数据类型 | 每个用户id占用空间 | 需要存储的用户量 | 全部 |
|---|---|---|---|
| 集合类型 | 64位 | 50000000 | 64位*50000000 = 400MB |
| Bitmaps | 1位 | 100000000 | 1位*100000000 = 12.5MB |
- 很明显， 这种情况下使用Bitmaps能节省很多的内存空间， 尤其是随着时间推移节省的内存还是非常可观的
- set和Bitmaps存储独立用户空间对比
| 数据类型 | 一天 | 一个月 | 一年 |
|---|---|---|---|
| 集合类型 | 400MB | 12GB | 144GB |
| Bitmaps | 12.5MB | 375MB | 4.5GB |
- 但Bitmaps并不是万金油， 假如该网站每天的独立访问用户很少， 例如只有10万（大量的僵尸用户） ， 那么两者的对比如下表所示， 很显然， 这时候使用Bitmaps就不太合适了， 因为基本上大部分位都是0。
- set和Bitmaps存储一天活跃用户对比（独立用户比较少）
| 数据类型 | 每个userid占用空间 | 需要存储的用户量 | 全部内存量 |
|---|---|---|---|
| 集合类型 | 64位 | 100000 | 64位*100000 = 800KB |
| Bitmaps | 1位 | 100000000 | 1位*100000000 = 12.5MB |
4、实际案例
用于状态统计 Y、N，类似AtomicBoolean
- 用户是否登陆过Y、N，比如京东每日签到送京豆
- 电影、广告是否被点击播放过
- 钉钉打卡上下班，签到统计
- 日活统计
- 连续签到打卡
- 最近一周的活跃用户
- 统计指定用户一年之中的登陆天数
- 某用户按照一年365天，哪几天登陆过？哪几天没有登陆？全年中登录的天数共计多少？
1、京东签到领取京豆
签到日历仅展示当月签到数据
签到日历需展示最近连续签到天数
假设当前日期是20210618，且20210616未签到
若20210617已签到且0618未签到，则连续签到天数为1
若20210617已签到且0618已签到，则连续签到天数为2
连续签到天数越多，奖励越大
所有用户均可签到
截至2020年3月31日的12个月，京东年度活跃用户数3.87亿，同比增长24.8%，环比增长超2500万，此外，2020年3月移动端日均活跃用户数同比增长46%假设10%左右的用户参与签到，签到用户也高达3千万。。。
1、小厂方法，传统mysql方式
CREATE TABLE user_sign
(
keyid BIGINT NOT NULL PRIMARY KEY AUTO_INCREMENT,
user_key VARCHAR(200),#京东用户ID
sign_date DATETIME,#签到日期(20210618)
sign_count INT #连续签到天数
)
INSERT INTO user_sign(user_key,sign_date,sign_count)
VALUES ('20210618-xxxx-xxxx-xxxx-xxxxxxxxxxxx','2020-06-18 15:11:12',1);
SELECT
sign_count
FROM
user_sign
WHERE
user_key = '20210618-xxxx-xxxx-xxxx-xxxxxxxxxxxx'
AND sign_date BETWEEN '2020-06-17 00:00:00' AND '2020-06-18 23:59:59'
ORDER BY
sign_date DESC
LIMIT 1;方法正确但是难以落地实现，o(╥﹏╥)o。
签到用户量较小时这么设计能行，但京东这个体量的用户（估算3000W签到用户，一天一条数据，一个月就是9亿数据）
对于京东这样的体量，如果一条签到记录对应着当日用记录，那会很恐怖......
如何解决这个痛点？
1 一条签到记录对应一条记录，会占据越来越大的空间。
2 一个月最多31天，刚好我们的int类型是32位，那这样一个int类型就可以搞定一个月，32位大于31天，当天来了位是1没来就是0。
3 一条数据直接存储一个月的签到记录，不再是存储一天的签到记录。
2、大厂方法，基于Redis的Bitmaps实现签到日历 -- 建表-按位-redis bitmap
在签到统计时，每个用户一天的签到用1个bit位就能表示，
一个月（假设是31天）的签到情况用31个bit位就可以，一年的签到也只需要用365个bit位，根本不用太复杂的集合类型
3、setbit和getbit案例说明
按照天
按照年
按年去存储一个用户的签到情况，365 天只需要 365 / 8 ≈ 46 Byte，1000W 用户量一年也只需要 44 MB 就足够了。
假如是亿级的系统，
每天使用1个1亿位的Bitmap约占12MB的内存（10^8/8/1024/1024），10天的Bitmap的内存开销约为120MB，内存压力不算太高。在实际使用时，最好对Bitmap设置过期时间，让Redis自动删除不再需要的签到记录以节省内存开销。
4、bitmap的底层编码说明，get命令操作如何
实质是二进制的ascii编码对应
redis里用type命令看看bitmap实质是什么类型？？？ String
man ascii
设置命令
两个setbit命令对k1进行设置后，对应的二进制串就是0100 0001
二进制串就是0100 0001对应的10进制就是65，所以见下图：
5、strlen
不是字符串长度而是占据几个字节，超过8位后自己按照8位一组一byte再扩容
6、bitcount
全部键里面含有1的有多少个？
一年365天，全年天天登陆占用多少字节
7、bitop
连续2天都签到的用户
加入某个网站或者系统，它的用户有1000W，做个用户id和位置的映射
比如0号位对应用户id：uid-092iok-lkj
比如1号位对应用户id：uid-7388c-xxx
3、hyperloglog
1、简介
在工作当中，我们经常会遇到与统计相关的功能需求，比如统计网站PV（PageView页面访问量）,可以使用Redis的incr、incrby轻松实现。
但像UV（UniqueVisitor，独立访客）、独立IP数、搜索记录数等需要去重和计数的问题如何解决？这种求集合中不重复元素个数的问题称为基数问题。
- 解决基数问题有很多种方案：
- 数据存储在MySQL表中，使用distinct count计算不重复个数
- 使用Redis提供的hash、set、bitmaps等数据结构来处理
- 以上的方案结果精确，但随着数据不断增加，导致占用空间越来越大，对于非常大的数据集是不切实际的。
- 能否能够降低一定的精度来平衡存储空间？Redis推出了HyperLogLog
- Redis HyperLogLog 是用来做基数统计的算法，HyperLogLog 的优点是，在输入元素的数量或者体积非常非常大时，计算基数所需的空间总是固定的、并且是很小的。
- 在 Redis 里面，每个 HyperLogLog 键只需要花费 12 KB 内存，就可以计算接近 2^64 个不同元素的基数。这和计算基数时，元素越多耗费内存就越多的集合形成鲜明对比。
- 但是，因为 HyperLogLog 只会根据输入元素来计算基数，而不会储存输入元素本身，所以 HyperLogLog 不能像集合那样，返回输入的各个元素。
去重复统计功能的基数估计算法-就是HyperLogLog
基数统计就是HyperLogLog
基数:是一种数据集，去重复后的真实个数
用于统计一个集合中不重复的元素个数，就是对集合去重复后剩余元素的计算
2、UV、PV、DAU、MAU介绍
1、UV
Unique Visitor，独立访客，一般理解为客户端IP
需要去重考虑
2、PV
Page View，页面浏览量
不用去重
3、DAU
Daily Active User 日活跃用户量
登录或者使用了某个产品的用户数(去重复登录的用户)
常用于反映网站、互联网应用或者网络游戏的运营情况
4、MAU
MonthIy Active User
月活跃用户量
3、基本命令
1、pfadd
sh
pfadd <key>< element> [element ...] 添加指定元素到 HyperLogLog 中
示例
- 将所有元素添加到指定HyperLogLog数据结构中。如果执行命令后HLL估计的近似基数发生变化，则返回1，否则返回0。
2、pfcount
sh
pfcount<key> [key ...]- 计算HLL的近似基数，可以计算多个HLL，比如用HLL存储每天的UV，计算一周的UV可以使用7天的UV合并计算即可
示例
3、pfmerge
sh
pfmerge<destkey><sourcekey> [sourcekey ...]- 将一个或多个HLL合并后的结果存储在另一个HLL中，比如每月活跃用户可以使用每天的活跃用户来合并计算可得
示例
4、实际案例
- 统计某个网站的UV、统计某个文章的UV
- 用户搜索网站关键词的数量
- 统计用户每天搜索不同词条个数
5、HyPerLogLog如何做的？如何演化出来的？
1、去重复统计哪些方式？
- HashSet
- bitmap
如果数据显较大亿级统计,使用bitmaps同样会有这个问题。
bitmap是通过用位bit数组来表示各元素是否出现，每个元素对应一位，所需的总内存为N个bit。
基数计数则将每一个元素对应到bit数组中的其中一位，比如bit数组010010101(按照从零开始下标，有的就是1、4、6、8)。
新进入的元素只需要将已经有的bit数组和新加入的元素进行按位或计算就行。这个方式能大大减少内存占用且位操作迅速。
But，假设一个样本案例就是一亿个基数位值数据，一个样本就是一亿
如果要统计1亿个数据的基数位值,大约需要内存100000000/8/1024/1024约等于12M,内存减少占用的效果显著。
这样得到统计一个对象样本的基数值需要12M。
如果统计10000个对象样本(1w个亿级),就需要117.1875G将近120G，可见使用bitmaps还是不适用大数据量下(亿级)的基数计数场景，
但是bitmaps方法是精确计算的。
样本元素越多内存消耗急剧增大，难以管控+各种慢，对于亿级统计不太合适，大数据害死人，o(╥﹏╥)o
概率算法：
通过牺牲准确率来换取空间，对于不要求绝对准确率的场景下可以使用，因为概率算法不直接存储数据本身，
通过一定的概率统计方法预估基数值，同时保证误差在一定范围内，由于又不储存数据故此可以大大节约内存。
HyperLogLog就是一种概率算法的实现。
2、原理说明
只是进行不重复的基数统计，不是集合也不保存数据，只记录数量而不是具体内容。
有误差
- 非精确统计
牺牲准确率来换取空间，误差仅仅只是0.81%左右
这个误差如何来的?论文地址和出处
6、实际案例-天猫网站首页亿级UV的Redis统计方案
1、需求
- UV的统计需要去重，一个用户一天内的多次访问只能算作一次
- 淘宝、天猫首页的UV，平均每天是1~1.5个亿左右
- 每天存1.5个亿的IP，访问者来了后先去查是否存在，不存在加入
2、方案
- mysql （不可用）
- 用redis的hash结构存储
redis——hash = <keyDay,<ip,1>>
按照ipv4的结构来说明，每个ipv4的地址最多是15个字节(ip = "192.168.111.1"，最多xxx.xxx.xxx.xxx)
某一天的1.5亿 * 15个字节= 2G，一个月60G，redis死定了。o(╥﹏╥)o
- hyperloglog
为什么是12Kb？
每个桶取6位，16384*6÷8 = 12kb，每个桶有6位，最大全部都是1，值就是63
java
@Resource
private RedisTemplate redisTemplate;
@ApiOperation("获得IP去重后的首页访问量")
@RequestMapping(value = "/uv",method = RequestMethod.GET)
public long uv()
{
//pfcount
return redisTemplate.opsForHyperLogLog().size("hll");
}
@Resource
private RedisTemplate redisTemplate;
/**
* 模拟后台有用户点击首页，每个用户来自不同ip地址
*/
@PostConstruct
public void init()
{
log.info("------模拟后台有用户点击首页，每个用户来自不同ip地址");
new Thread(() -> {
String ip = null;
for (int i = 1; i <=200; i++) {
Random r = new Random();
ip = r.nextInt(256) + "." + r.nextInt(256) + "." + r.nextInt(256) + "." + r.nextInt(256);
Long hll = redisTemplate.opsForHyperLogLog().add("hll", ip);
log.info("ip={},该ip地址访问首页的次数={}",ip,hll);
//暂停几秒钟线程
try { TimeUnit.SECONDS.sleep(3); } catch (InterruptedException e) { e.printStackTrace(); }
}
},"t1").start();
}4、GEO
1、简介
移动互联网时代LBS应用越来越多，交友软件中附近的小姐姐、外卖软件中附近的美食店铺、打车软件附近的车辆等等，那这种附近各种形形色色的XXX地址位置选择是如何实现的？
地球上的地理位置是使用二维的经纬度表示，经度范围 (-180, 180]，纬度范围 (-90, 90]，只要我们确定一个点的经纬度就可以名曲他在地球的位置。
例如滴滴打车，最直观的操作就是实时记录更新各个车的位置，
然后当我们要找车时，在数据库中查找距离我们(坐标x0,y0)附近r公里范围内部的车辆
select taxi from position where x0-r < x < x0 + r and y0-r < y < y0+r但是这样会有什么问题呢？
1.查询性能问题，如果并发高，数据量大这种查询是要搞垮数据库的
2.这个查询的是一个矩形访问，而不是以我为中心r公里为半径的圆形访问。
3.精准度的问题，我们知道地球不是平面坐标系，而是一个圆球，这种矩形计算在长距离计算时会有很大误差
2、原理
核心思想就是将球体转换为平面，区块转换为一点
GeoHash核心原理解析：https://www.cnblogs.com/LBSer/p/3310455.html
3、地理知识说明
1、经纬度
2、查询
4、基本命令
- GEOADD 多个经度(longitude)、纬度(latitude)、位置名称(member)添加到指定的 key 中
- GEOPOS 从键里面返回所有给定位置元素的位置（经度和纬度）
- GEODIST 返回两个给定位置之间的距离。
- GEORADIUS 以给定的经纬度为中心， 返回与中心的距离不超过给定最大距离的所有位置元素。
- GEORADIUSBYMEMBER 跟GEORADIUS类似
- GEOHASH返回一个或多个位置元素的 Geohash 表示
1、命令操作
- 如何获得某个地址的经纬度
- GEOADD添加经纬度坐标
命令如下：
GEOADD city 116.403963 39.915119 "天安门" 116.403414 39.924091 "故宫" 116.024067 40.362639 "长城"中文乱码如何处理:
- GEOPOS返回经纬度
- GEOHASH返回坐标的geohash表示
- geohash算法生成的base32编码值
3维变2维变1维
GEODIST 两个位置之间距离
后面参数是距离单位：
m 米
km 千米
ft 英尺
mi 英里
- GEORADIUS
georadius 以给定的经纬度为中心， 返回键包含的位置元素当中， 与中心的距离不超过给定最大距离的所有位置元素。
GEORADIUS city 116.418017 39.914402 10 km withdist withcoord count 10 withhash desc
WITHDIST: 在返回位置元素的同时， 将位置元素与中心之间的距离也一并返回。 距离的单位和用户给定的范围单位保持一致。
WITHCOORD: 将位置元素的经度和维度也一并返回。
WITHHASH: 以 52 位有符号整数的形式， 返回位置元素经过原始 geohash 编码的有序集合分值。 这个选项主要用于底层应用或者调试， 实际中的作用并不大
COUNT 限定返回的记录数。
当前位置(116.418017 39.914402),在王府井
- GEORADIUSBYMEMBER
5、实际案例-美团地图位置附近的酒店推送
1、需求
微信附近的人或者一公里以内的各种营业厅、加油站、理发店、超市.....
2、Redis的新类型GEO
http://www.redis.cn/commands/geoadd.html
java
public static final String CITY ="city";
@Autowired
private RedisTemplate redisTemplate;
@RequestMapping("/geoadd")
public String geoAdd()
{
Map<String, Point> map= new HashMap<>();
map.put("天安门",new Point(116.403963,39.915119));
map.put("故宫",new Point(116.403414 ,39.924091));
map.put("长城" ,new Point(116.024067,40.362639));
redisTemplate.opsForGeo().add(CITY,map);
return map.toString();
}
@GetMapping(value = "/geopos")
public Point position(String member) {
//获取经纬度坐标
List<Point> list= this.redisTemplate.opsForGeo().position(CITY,member);
return list.get(0);
}
@GetMapping(value = "/geohash")
public String hash(String member) {
//geohash算法生成的base32编码值
List<String> list= this.redisTemplate.opsForGeo().hash(CITY,member);
return list.get(0);
}
@GetMapping(value = "/geodist")
public Distance distance(String member1, String member2) {
Distance distance= this.redisTemplate.opsForGeo().distance(CITY,member1,member2, RedisGeoCommands.DistanceUnit.KILOMETERS);
return distance;
}
/**
* 通过经度，纬度查找附近的
* 北京王府井位置116.418017,39.914402
*/
@GetMapping(value = "/georadius")
public GeoResults radiusByxy() {
//这个坐标是北京王府井位置
Circle circle = new Circle(116.418017, 39.914402, Metrics.KILOMETERS.getMultiplier());
//返回50条
RedisGeoCommands.GeoRadiusCommandArgs args = RedisGeoCommands.GeoRadiusCommandArgs.newGeoRadiusArgs().includeDistance().includeCoordinates().sortAscending().limit(50);
GeoResults<RedisGeoCommands.GeoLocation<String>> geoResults= this.redisTemplate.opsForGeo().radius(CITY,circle, args);
return geoResults;
}
/**
* 通过地方查找附近
*/
@GetMapping(value = "/georadiusByMember")
public GeoResults radiusByMember() {
String member="天安门";
//返回50条
RedisGeoCommands.GeoRadiusCommandArgs args = RedisGeoCommands.GeoRadiusCommandArgs.newGeoRadiusArgs().includeDistance().includeCoordinates().sortAscending().limit(50);
//半径10公里内
Distance distance=new Distance(10, Metrics.KILOMETERS);
GeoResults<RedisGeoCommands.GeoLocation<String>> geoResults= this.redisTemplate.opsForGeo().radius(CITY,member, distance,args);
return geoResults;
}