案例落地实战 HyperLogLog GEO Bitmap

面试题

抖音电商直播，主播介绍的商品有评论，1 个商品对应一系列的评价，排序 + 展示取前 10 条记录
用户在手机 App 上的签到打卡信息：1 天对应 1 系列用户的签到记录，新浪微博、钉钉打卡签到，如何统计？
应用网站上的网页访问信息：1 个网页对应 1 系列的访问点击，淘宝网首页，每天有多少人浏览首页？
你们公司系统上线后，说一下 UV、PV、DUA 分别是多少？
记录对集合中的数据进行统计
- 在移动应用中，需要统计每天的新增用户数和第 2 天的留存用户数；
- 在电商网站的商品评论中，需要统计评论列表中的最新评论；
- 在签到打卡中，需要统计一个月内连续打卡的用户数；
- 在网页访问记录中，需要统计独立访客（Unique Visitor，UV）量。
- 类似今日头条、抖音、淘宝这样的额用户访问级别都是亿级的，请问如何处理？
亿级数据的收集 + 清洗 + 统计 + 展现（存的进 + 取得快 + 多维度）

统计的类型

亿级系统中常见的四种统计

聚合统计

统计多个集合元素的聚合结果，即交并差等集合统计
相关命令
交并差集和聚合函数的应用

排序统计

抖音短视频最新评论留言的场景，请你设计一个展现列表。考察你的数据结构和设计思路

设计案例和回答思路

127.0.0.1:6379> ZADD itemz 1 v1 2 v2 3 v3
(integer) 3
127.0.0.1:6379> ZRANGE itemz 0 2
1) "v1"
2) "v2"
3) "v3"
127.0.0.1:6379> ZREVRANGE itemz 0 2
1) "v3"
2) "v2"
3) "v1"
127.0.0.1:6379> ZRANGEBYSCORE itemz 1 4
1) "v1"
2) "v2"
3) "v3"
127.0.0.1:6379> ZRANGEBYSCORE itemz 1 4 limit 0 5
1) "v1"
2) "v2"
3) "v3"
127.0.0.1:6379>

在面对需要展示最新列表、排行榜等场景时，如果数据更新频繁或者需要分页显示，建议使用 ZSet

二值统计

集合元素的取值就只有 0 和 1 两种。在钉钉上班签到打卡的场景中，我们只用记录有签到(1)或没签到(0)
见 Bitmap

基数统计

指统计一个集合中不重复的元素个数
见 HyperLogLog

HyperLogLog

术语概述

UV：Unique Visitor，独立访客，一般理解为客户端 IP，需要去重考虑
PV：Page View，页面浏览量，不用去重
DAU：Daily Active User，日活跃用户量，登录或者使用了某个产品的用户数（去重复登录的用户），常用于反应网站、互联网应用或者网络游戏的运营情况
MAU：Monthly Active User，月活跃用户量

需求概述

很多计数类场景，比如每日注册 IP 数、每日访问 IP 数、页面实时访问数 PV、访问用户数 UV等。

因为主要的目标高效、巨量地进行计数，所以对存储的数据的内容并不太关心。也就是说它只能用于统计巨量数量，不太涉及具体的统计对象的内容和精准性。

统计单日一个页面的访问量(PV)，单次访问就算一次。

统计单日一个页面的用户访问量(UV)，即按照用户为维度计算，单个用户一天内多次访问也只算一次。

多个key的合并统计，某个门户网站的所有模块的PV聚合统计就是整个网站的总PV。

HyperLogLog 概述

基数是一种数据集，去重复后的真实个数

(全集) = {2, 4, 6, 8, 77, 39, 4, 8, 10}
去掉重复的内容
基数 = {2, 4, 5, 6, 77, 39, 10} = 7

去重复统计功能的基数估计算法 —— HyperLogLog

Redis 在 2.8.9 版本添加了 HyperLogLog 的结构。

Redis HyperLogLog 是用来做基数统计的算法，HyperLogLog 的优点是，在输入元素的数量或者体积非常非常大时，计算基数所需的空间总是固定的、并且是很小的。

在 Redis 里面，每个 HyperLogLog 键只需要花费 12KB 内存，就可以计算接近 $2^{64}$ 个不同元素的基数。这和计算基数时，元素越多越耗费内存就越多的集合形成鲜明对比。

但是，因为 HyperLogLog 只会根据输入元素来计算基数，而不会存储输入元素本身，所以 HyperLogLog 不能像集合那样，返回输入的各个元素。
用于统计一个集合中不重复的元素个数，就是对集合去重复后剩余元素的计算（去重后的真实数据）

基本命令

命令	作用
pfadd key element ...	将所有元素添加到 key 中
pfcount key	统计 key 的估算值（不精确）
pgmerge new_key key1 key2 ...	合并 key 至新 key

127.0.0.1:6379> pfadd hll01 1 3 4 5 7 9
(integer) 1
127.0.0.1:6379> pfadd hll02 2 4 4 4 6 8 9
(integer) 1
127.0.0.1:6379> pfcount hll02
(integer) 5
127.0.0.1:6379> pfmerge distResult hll01 hll02
OK
127.0.0.1:6379> pfcount distResult
(integer) 9
127.0.0.1:6379>

HyperLogLog 如何做的？如何演化出来的？

去重复统计的方式

HashSet
Bitmap

如果数据显较大亿级统计，使用 Bitmap 同样会有这个问题。Bitmap 是通过用位 bit 数组来表示各元素是否出现，每个元素对应一位，所需的总内存为 N 个 bit。

基数计数则将每一个元素对应到 bit 数组中的其中一位，比如 bit 数组 010010101（按照从零开始下标，有的就是1、4、6、8）。新进入的元素只需要将已经有的bit数组和新加入的元素进行按位或计算就行。这个方式能大大减少内存占用且位操作迅速。

但是假设一个样本案例就是一亿个基数位值数据，一个样本就是一亿。如果要统计 1 亿个数据的基数位值，大约需要内存 100000000/8/1024/1024 约等于 12M，内存减少占用的效果显著。这样得到统计一个对象样本的基数值需要 12M。如果统计 10000 个对象样本（1w 个亿级），就需要 117.1875G 将近 120G，可见使用 Bitmap 还是不适用大数据量下(亿级)的基数计数场景，但是 Bitmap 方法是精确计算的。
结论：样本元素越多，内存消耗急剧增大，难以管控以及各种慢，对于亿级统计不太合适。
解决方法：概率算法

通过牺牲准确率来换取空间，对于不要求绝对准确率的场景下可以使用，因为概率算法不直接存储数据本身，通过一定的概率统计方法预估基数值，同时保证误差在一定范围内，由于又不储存数据故此可以大大节约内存。
HyperLogLog 就是一种概率算法的实现。

原理说明

只是进行不重复的基数统计，不是集合也不保存数据，只记录数量而不是具体内容。

HyperLogLog 提供不精确的去重计数方案，牺牲准确率来换取空间，误差仅仅只是 0.81% 左右。

参考网址：http://antirez.com/news/75 (opens in a new tab)

淘宝网站首页亿级 UV 的 Redis 统计方案

需求

UV 的统计需要去重，一个用户一天内的多次访问只能算作一次；
淘宝，天猫首页的 UV，平均每天时 1~1.5 个亿左右；
每天存 1.5 亿的 IP，访问者来了后先去查询是否存在，不存在则加入。

方案讨论

MySQL
Redis 的 hash 结构存储

<keyDay, <ip, 1>>，按照 ipv4 的结构来说明，每个 ipv4 的地址最多是 15 个字节（xxx.xxx.xxx.xxx）

一天 1.5 亿 * 15 个字节 = 2G，一个月 60G，占用巨大
HyperLogLog

Redis 使用了 $2^{14}$ = 16384 个桶，按照上面的标准差，误差为 0.81% ，精度相当高。Redis 使用一个 long 类型哈希值的前 14 个比特用来确定桶编号，剩下的 50 个比特用来做基数估计。而 $2^{6}$ = 64，所以只需要用 6 个比特表示下标值。在一般情况下，一个 HpyterLogLog 数据结构占用内存的大小为 16384 * 6 / 8 = 12KB，Redis 将这种情况称为密集（dense）存储。

代码实现

HyperLogLogService.java

@Service
@Slf4j
public class HyperLogLogService
{
    @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();
    }
 
}

HyperLogLogController.java

@Api(description = "淘宝亿级UV的Redis统计方案")
@RestController
@Slf4j
public class HyperLogLogController
{
    @Resource
    private RedisTemplate redisTemplate;
 
    @ApiOperation("获得IP去重后的首页访问量")
    @RequestMapping(value = "/uv",method = RequestMethod.GET)
    public long uv()
    {
        //pfcount
        return redisTemplate.opsForHyperLogLog().size("hll");
    }
 
}

GEO

GEO 概述

面试题

移动互联网时代 LBS 应用越来越多，交友软件中附近的小姐姐、外卖软件中附近的美食店铺、打车软件附近的车辆等等。那这种附近各种形形色色的地址位置选择是如何实现的？又会遇到什么问题呢？

查询性能问题，如果并发高，数据量大这种查询是要搞垮 MySQL 数据库的。
一般 MySQL 查询的是一个平面矩形访问，而叫车服务要以我为中心 N 公里为半径的圆形覆盖。
精准度的问题，我们知道地球不是平面坐标系，而是一个圆球，这种矩形计算在长距离计算时会有很大误差，MySQL 不合适。

如何获得某个地址的经纬度

http://api.map.baidu.com/lbsapi/getpoint/ (opens in a new tab)

常用命令

https://redis.io/commands/ (opens in a new tab)

美团地图位置附近的酒店推送

需求分析

美团 App 附近的酒店
高德地图附近的人或者一公里以内的店铺
共享单车

架构设计

http://www.redis.cn/commands/geoadd.html (opens in a new tab)

代码实现

关键点 GEORADIUS 以给定的经纬度为中心，找出某一半径内的元素

GeoController.java

@Api(tags = "美团地图位置附近的酒店推送GEO")
@RestController
@Slf4j
public class GeoController {
    @Resource
    private GeoService geoService;
 
    @ApiOperation("添加坐标geoadd")
    @RequestMapping(value = "/geoadd",method = RequestMethod.GET)
    public String geoAdd() {
        return geoService.geoAdd();
    }
 
    @ApiOperation("获取经纬度坐标geopos")
    @RequestMapping(value = "/geopos",method = RequestMethod.GET)
    public Point position(String member) {
        return geoService.position(member);
    }
 
    @ApiOperation("获取经纬度生成的base32编码值geohash")
    @RequestMapping(value = "/geohash",method = RequestMethod.GET)
    public String hash(String member) {
        return geoService.hash(member);
    }
 
    @ApiOperation("获取两个给定位置之间的距离")
    @RequestMapping(value = "/geodist",method = RequestMethod.GET)
    public Distance distance(String member1, String member2) {
        return geoService.distance(member1,member2);
    }
 
    @ApiOperation("通过经度纬度查找北京王府井附近的")
    @RequestMapping(value = "/georadius",method = RequestMethod.GET)
    public GeoResults radiusByxy() {
        return geoService.radiusByxy();
    }
 
    @ApiOperation("通过地方查找附近,本例写死天安门作为地址")
    @RequestMapping(value = "/georadiusByMember",method = RequestMethod.GET)
    public GeoResults radiusByMember() {
        return geoService.radiusByMember();
    }
}

GeoService.java

@Service
@Slf4j
public class GeoService {
    public static final String CITY ="city";
 
    @Autowired
    private RedisTemplate redisTemplate;
 
    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();
    }
 
    public Point position(String member) {
        //获取经纬度坐标
        List<Point> list= this.redisTemplate.opsForGeo().position(CITY,member);
        return list.get(0);
    }
 
    public String hash(String member) {
        //geohash算法生成的base32编码值
        List<String> list= this.redisTemplate.opsForGeo().hash(CITY,member);
        return list.get(0);
    }
 
    public Distance distance(String member1, String member2) {
        //获取两个给定位置之间的距离
        Distance distance= this.redisTemplate.opsForGeo().distance(CITY,member1,member2, RedisGeoCommands.DistanceUnit.KILOMETERS);
        return distance;
    }
 
    public GeoResults radiusByxy() {
        //通过经度，纬度查找附近的,北京王府井位置116.418017,39.914402
        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;
    }
 
    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;
    }
}

Bitmap

面试题

日活统计
连续签到打卡
最近一周的活跃用户
统计指定用户一年之中的登录天数
某用户按照一年 365 天，哪几天登陆过？哪几天没有登录？全年中登录的天数共计多少？

概述

说明：用 String 类型作为底层数据结构实现的一种统计二值状态的数据类型

位图本质是数组，它是基于 String 数据类型的按位的操作。该数组由多个二进制位组成，每个二进制位都对应一个偏移量（我们可以称之为一个索引或者位格）。Bitmap 支持的最大位数是 $2^{32}$ 位，它可以极大的节约存储空间，使用 512M 内存就可以存储多大 42.9 亿的字节信息（ $2^{32}$ = 4294967296）。简而言之，就是由 0 和 1 状态表现的二进制位的 bit 数组。

应用场景

用于状态统计，比如京东签到；电影、广告是否被点击播放过；钉钉上班打开，签到统计。

案例

传统 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;

方法正确但是难以落地实现，签到用户量较小时该方案可行，但用户量上升，则数据量会很大。

解决痛点：

一条签到记录对应一条记录，会占据越来越大的空间；
一个月最多 31 天，刚好 int 类型是 32 位，这样一个 int 类型可以记录一个月的签到信息；
一条数据直接存储一个月的签到记录，不再是存储一天的签到记录。

基于 Redis 的 Bitmap 实现签到日历（按表-按位使用 Redis Bitmap）

在签到统计时，每个用户一天的签到用 1 个 bit 位就能表示，一个月（假设是 31 天）的签到情况用 31 个 bit 位就可以，一年的签到也只需要用 365 个 bit 位，根本不用太复杂的集合类型

Redis 与 MySQL 数据双写一致性工程落地案例布隆过滤器的实现和使用方法