clxmm
clxmm
2024-09-14
目录

13案列bitmap-hyperlog-geo

# 1.面试题

# 1.1 面试题1

  • 抖音电商直播，主播介绍的商品有评论，1个商品对应了1系列的评论，排序+展现+取前10条记录
  • 用户在手机App上的签到打卡信息：1天对应1系列用户的签到记录，新浪微博、钉钉打卡签到，来没来如何统计？
  • 应用网站上的网页访问信息：1个网页对应1系列的访问点击，淘宝网首页，每天有多少人浏览首页？
  • 你们公司系统上线后，说一下UV、PV、DAU分别是多少？

# 1.2 面试题2

  • 记录对集合中的数据进行统计

    在移动应用中，需要统计每天的新增用户数和第2天的留存用户数；

    在电商网站的商品评论中，需要统计评论列表中的最新评论；

    在签到打卡中，需要统计一个月内连续打卡的用户数；

    在网页访问记录中，需要统计独立访客（Unique Visitor，UV）量。

痛点

类似今日头条、抖音、淘宝这样的额用户访问级别都是亿级的，请问如何处理？

# 1.3 需求痛点

  • 亿级数据的收集+清洗+统计+展现
  • 存的进+取得快+多维度
  • 真正有价值的是统计。。。。。。

# 2.统计的类型有哪些？

常见的四种统计

# 2.1 聚合统计

  • 统计多个集合元素的聚合结果，就是前面讲解过的交差并等集合统计

  • 命令

  • 交并差集和聚合函数的应用

# 2.2 排序统计

  • 抖音短视频最新评论留言的场景，请你设计一个展现列表。考察你的数据结构和设计思路
  • answer
    • zset
    • 在⾯对需要展示最新列表、排行榜等场景时，如果数据更新频繁或者需要分页显示，建议使⽤ZSet

# 2.3 二值统计

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

# 2.4 基数统计

  • 指统计⼀个集合中不重复的元素个数
  • 见hyperloglog

# 3.hyperloglog

# 3.1常见统计

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

# 3.2 需求

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

  • 因为主要的目标高效、巨量地进行计数，所以对存储的数据的内容并不太关心。

  • 也就是说它只能用于统计巨量数量，不太涉及具体的统计对象的内容和精准性。

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

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

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

# 3.3 是什么

  • 基数

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

  • 案例Case

  • 去重复统计功能的基数估计算法-就是HyperLogLog

# 3.4 HyperLogLog是如何做的

  • 基数统计就是HyperLogLog

  • 去重复统计你先会想到哪些方式？

    • HashSet
    • bitmap
      • 如果数据显较大亿级统计,使用bitmaps同样会有这个问题。bitmap是通过用位bit数组来表示各元素是否出现，每个元素对应一位，所需的总内存为N个bit。基数计数则将每一个元素对应到bit数组中的其中一位，比如bit数组010010101(按照从零开始下标，有的就是1、4、6、8)。新进入的元素只需要将已经有的bit数组和新加入的元素进行按位或计算就行。这个方式能大大减少内存占用且位操作迅速。

  • 结论

    • 样本元素越多内存消耗急剧增大，难以管控+各种慢，对于亿级统计不太合适，大数据害死人，o(╥﹏╥)o
    • 量变引起质变

  • 方法

    • 概率算法

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

  • 原理

    • 只是进行不重复的基数统计，不是集合也不保存数据，只记录数量而不是具体内容。
    • 有误差
      • Hyperloglog提供不精确的去重计数方案
      • 牺牲准确率来换取空间，误差仅仅只是0.81%左右
    • 来源
      • http://antirez.com/news/75

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

  • 需求

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

  • 方案

    • mysql

    • redis-hash

    • Hyperloglog

      为什么是只需要花费12Kb？

  • 代码

    import lombok.extern.slf4j.Slf4j;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.stereotype.Service;

import javax.annotation.PostConstruct;
import javax.annotation.Resource;
import java.util.Random;
import java.util.concurrent.TimeUnit;

/**
 * @auther zzyy
 * @create 2021-05-02 18:16
 */
@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();
    }

}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46

    controller

    @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");
    }

}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16

# 4.GEO

# 4.1 Redis之GEO

# 4.1.2 面试题

移动互联网时代LBS应用越来越多，交友软件中附近的小姐姐、外卖软件中附近的美食店铺、打车软件附近的车辆等等。

那这种附近各种形形色色的XXX地址位置选择是如何实现的？

会有什么问题呢？

  1. 查询性能问题，如果并发高，数据量大这种查询是要搞垮mysql数据库的

  2. 一般mysql查询的是一个平面矩形访问，而叫车服务要以我为中心N公里为半径的圆形覆盖。

  3. 精准度的问题，我们知道地球不是平面坐标系，而是一个圆球，这种矩形计算在长距离计算时会有很大误差，mysql不合适

# 4.1.2 地理经纬度

  • 经纬度

经度与纬度的合称组成一个坐标系统。又称为地理坐标系统，它是一种利用三度空间的球面来定义地球上的空间的球面坐标系统，能够标示地球上的任何一个位置。

  • 经线和纬线

是人们为了在地球上确定位置和方向的，在地球仪和地图上画出来的，地面上并线。

和经线相垂直的线叫做纬线(纬线指示东西方向)。纬线是一条条长度不等的圆圈。最长的纬线就是赤道。

因为经线指示南北方向，所以经线又叫子午线。 国际上规定，把通过英国格林尼治天文台原址的经线叫做0°所以经线也叫本初子午线。在地球上经线指示南北方向，纬线指示东西方向。

东西半球分界线：东经160° 西经20°

  • 经度和维度

经度(longitude)：东经为正数，西经为负数。东西经

纬度(latitude)：北纬为正数，南纬为负数。南北纬

# 4.1.3 获取经纬度

http://api.map.baidu.com/lbsapi/getpoint/

# 4.1.4 命令

Redis GEO | 菜鸟教程 (runoob.com) (opens new window)

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

  • 需求

    • 美团app附近的酒店
    • 找个单车

  • 架构设计

    • GEO

  • 代码

    @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();
    }

}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51

    service

    import lombok.extern.slf4j.Slf4j;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.data.geo.Distance;
import org.springframework.data.geo.GeoResults;
import org.springframework.data.geo.Metrics;
import org.springframework.data.geo.Point;
import org.springframework.data.geo.Circle;
import org.springframework.data.redis.connection.RedisGeoCommands;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.stereotype.Service;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RequestMapping;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @auther zzyy
 * @create 2022-12-25 12:11
 */
@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;
    }
}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82

# 5.bitmap

# 5.1 面试题

  • 日活统计
  • 最近一周的活跃用户
  • 统计指定用户一年之中的登陆天数

# 5.2 是什么

由0和1状态表现的二进制位的bit数组

# 5.3 能干什么

  • 用于状态统计
    • Y、N，类似AtomicBoolean
  • 看需求
    • 钉钉打卡上下班，签到统计
    • 电影、广告是否被点击播放过
    • 用户是否登陆过Y、N，比如京东每日签到送京豆

# 5.4签到

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

# 5.6命令

编辑 (opens new window)
#redis
上次更新: 2024/09/18, 22:15:40
12redis与mysql双写一致性
14布隆过滤器BloomFilter

← 14布隆过滤器BloomFilter→

最近更新
01
vue3
02-08
02
vue3-1
01-24
03
vue3
01-18
更多文章>
Theme by Vdoing | Copyright © 2024-2025 Evan Xu | MIT License