面试题

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

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

5. 在移动应用中，需要统计每天的新增用户数和第2天的留存用户数；
6. 在电商网站的商品评论中，需要统计评论列表中的最新评论；
7. 在签到打卡中，需要统计一个月内连续打卡的用户数；
8. 在网页访问记录中，需要统计独立访客（Unique Visitor，UV）量。

需求
亿级数据的收集+清洗+统计+展现

常见统计类型

亿级系统常见统计方式

聚合统计

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

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

排序统计

• 抖音短视频最新评论留言的场景，请你设计一个展现列表。

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

二值统计

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

基数统计

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

Hyperloglog

去重统计估计算法

专有名词

UV（Unique Visitor）独立访客

需要去重考虑

PV（Page View）页面浏览量

不用去重

DAU（Daily Active User）日活跃用户量

登录或者使用了某个产品的用户数（去重复登录的用户）
常用于反映网站、互联网应用或者网络游戏的运营情况

MAU（Monthly Active User）

月活跃用户量

需求

1. 很多计数类场景，比如 每日注册 IP 数、每日访问 IP 数、页面实时访问数 PV、访问用户数 UV等。
2. 因为主要的目标高效、巨量地进行计数，所以对存储的数据的内容并不太关心。
3. 也就是说它只能用于统计巨量数量，不太涉及具体的统计对象的内容和精准性。
4. 统计单日一个页面的访问量(PV)，单次访问就算一次。
5. 统计单日一个页面的用户访问量(UV)，即按照用户为维度计算，单个用户一天内多次访问也只算一次。
6. 多个key的合并统计，某个门户网站的所有模块的PV聚合统计就是整个网站的总PV。

问题
如果数据显较大亿级统计,使用bitmaps同样会有问题。

bitmap是通过用位bit数组来表示各元素是否出现，每个元素对应一位，所需的总内存为N个bit。

基数计数则将每一个元素对应到bit数组中的其中一位，比如bit数组010010101(按照从零开始下标，有的就是1、4、6、8)。

新进入的元素只需要将已经有的bit数组和新加入的元素进行按位或计算就行。这个方式能大大减少内存占用且位操作迅速。

但是，假设一个样本案例就是一亿个基数位值数据，一个样本就是一亿
如果要统计1亿个数据的基数位值,大约需要内存100000000/8/1024/1024约等于12M,内存减少占用的效果显著。

这样得到统计一个对象样本的基数值需要12M。
如果统计10000个对象样本(1w个亿级),就需要117.1875G将近120G，可见使用bitmaps还是不适用大数据量下(亿级)的基数计数场景，

但是bitmaps方法是精确计算的。

原理

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

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

亿级UV的Redis统计方案

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

// 用于产生模拟后台访问数据
@Service
@Slf4j
public class HyperLogLogService
{@Resourceprivate RedisTemplate redisTemplate;/*** 模拟后台有用户点击首页，每个用户来自不同ip地址*/@PostConstructpublic 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();}}

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

GEO

是zset

面试题

外卖软件中附近的美食店铺、打车软件附近的车辆等等。那这种附近各种形形色色的XXX地址位置选择

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

命令

GEOADD

GEOADD city 116.403963 39.915119 "天安门" 116.403414 39.924091 "故宫" 116.024067 40.362639 "长城"

获取某位置的经纬度GEOPOS

GEOPOS city 天安门 故宫

返回坐标的Geohash表示GEOHASH

GEOHASH city 天安门 故宫 长城

两个位置之间距离GEODIST

GEODIST city 天安门 长城 km

m 米
km 千米
ft 英尺
mi 英里

半径范围内的坐标GEORADIUS

GEORADIUS city 116.418017 39.914402 10 km withdist withcoord count 10 withhash desc

• WITHDIST: 在返回位置元素的同时， 将位置元素与中心之间的距离也一并返回。 距离的单位和用户给定的范围单位保持一致。
• WITHCOORD: 将位置元素的经度和维度也一并返回。
• WITHHASH: 以 52 位有符号整数的形式， 返回位置元素经过原始 geohash 编码的有序集合分值。 这个选项主要用于底层应用或者调试， 实际中的作用并不大
• COUNT 限定返回的记录数。

半径范围内坐标中心点是给定元素GEORADIUSBYMEMBER

GEORADIUSBYMEMBER city 天安门 km withdist withcoord count 10 withhash desc

Bitmap

面试题

1. 日活统计
2. 连续签到打卡
3. 最近一周的活跃用户
4. 统计指定用户一年之中的登陆天数
5. 某用户哪几天登陆过，哪几天没有登陆，全年中登录的天数共计多少

作用场景

1. 用户是否登陆过Y、N，比如京东每日签到送京豆
2. 电影、广告是否被点击播放过
3. 钉钉打卡上下班，签到统计

布隆过滤器BloomFilter

需求

1. 现有50亿个电话号码，现有10万个电话号码，如何要快速准确的判断这些电话号码是否已经存在?
2. 安全连接网址，全球数10亿的网址判断
3. 黑名单校验，识别垃圾邮件
4. 白名单校验，识别出合法用户进行后续处理

概述

由一个初值都为零的bit数组和多个哈希函数构成，1用来快速判断集合中是否存在某个元素
本质就是判断具体数据是否存在于一个大的集合中

布隆过滤器是一种类似set的数据结构，国只是统计结果在巨量数据下有点小瑕疵，不够完美

作用

高效地插入和查询，占用空间少，返回的结果是不确定性+不够完美。

重点

1. 一个元素如果判断结果:存在时，元素不一定存在但是判断结果为不存在时，则一定不存在。
2. 布隆过滤器可以添加元素，但是不能删除元素由于涉及hashcode判断依据，删掉元素会导致误判率增加。

原理

概述原理

布隆过滤器是专门用来解决去重问题的高级数据结构

实质就是一个大型位数组和几个不同的无偏hash函数(无偏表示分布均匀)。由一个初值都为零的bit数组和多个个哈希函数构成，用来快速判断某个数据是否存在。但是跟 HyperLogLog 一样，它也一样有那么一点点不精确，也存在一定的误判概率

添加、查询元素过程

• 添加key时
  使用多个hash函数对key进行hash运算得到一个整数索引值，对位数组长度进行取模运算得到一个位置，每个hash函数都会得到一个不同的位置，将这几个位置都置1就完成了add操作。

• 查询key时
  只要有其中一位是零就表示这个key不存在，但如果都是1，则不一定存在对应的key。

结论：有，是可能有 无，是肯定无

举例
当有变量被加入集合时，通过N个映射函数将这个变量映射成位图中的N个点，把它们置为 1（假定有两个变量都通过 3 个映射函数）。

如果这些点，有任何一个为零则被查询变量一定不在，如果都是 1，则被查询变量很可能存在

• 为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。（见上图3号坑两个对象都1）

缓存穿透解决方案：
正是基于布隆过滤器的快速检测特性，我们可以在把数据写入数据库时，使用布隆过滤器做个标记。当缓缺失后，应用查询数据库时，可以通过查询布降过滤器快速判断数据是否存在。如果不存在，就不用再去据库中查询了。这样一来，即使发生缓存穿透了，大量请求只会查询Redis和布隆过滤器，而不会积压到据库，也就不会影响数据库的正常运行。布降过滤器可以使用Redis实现，本身就能承担较大的并发访问力。

Hash冲突：https://segmentfault.com/a/1190000022553292

使用步骤

1. 初始化Bitmap
   布隆过滤器 本质上 是由长度为 m 的位向量或位列表（仅包含 0 或 1 位值的列表）组成，最初所有的值均设置为 0
   
2. 添加对应占位

当我们向布隆过滤器中添加数据时，为了尽量地址不冲突，会使用多个 hash 函数对 key 进行运算，算得一个下标索引值，然后对位数组长度进行取模运算得到一个位置，每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。

例如：我们添加一个字符串wmyskxz，对字符串进行多次hash(key) → 取模运行→ 得到坑位

3. 判断是否存在
   向布隆过滤器查询某个key是否存在时，先把这个 key 通过相同的多个 hash 函数进行运算，查看对应的位置是否都为 1，
   只要有一个位为零，那么说明布隆过滤器中这个 key 不存在；
   如果这几个位置全都是 1，那么说明极有可能存在；
   因为这些位置的 1 可能是因为其他的 key 存在导致的

例如：在 add 了字符串wmyskxz数据之后，很明显下面1/3/5 这几个位置的 1 是因为第一次添加的 wmyskxz 而导致的；此时我们查询一个没添加过的不存在的字符串inexistent-key，它有可能计算后坑位也是1/3/5

使用场景

1. 解决缓存穿透问题：redis结合Bitmap使用

把已存在数据的key存在布隆过滤器中，相当于redis前面挡着一个布隆过滤器。

当有新的请求时，先到布隆过滤器中查询是否存在：
如果布隆过滤器中不存在该条数据则直接返回；
如果布隆过滤器中已存在，才去查询缓存redis，如果redis里没查询到则再查询Mysql数据库

2. 黑名单校验
3. 安全连接网址，亿级数量判断

手写布隆过滤器案例

初始化白名单用户到布隆过滤器

@PostConstruct
public void init(){//白名单客户预加载到布隆过滤器String uid = "customer:12";//1 计算hashcode，由于可能有负数，直接取绝对值int hashValue = Math.abs(uid.hashCode());//2 通过hashValue和2的32次方取余后，获得对应的下标坑位long index = (long) (hashValue % Math.pow(2, 32));log.info(uid+" 对应------坑位index:{}",index);//3 设置redis里面bitmap对应坑位，该有值设置为1redisTemplate.opsForValue().setBit("whitelistCustomer",index,true);}

布隆过滤器检查

@Component
@Slf4j
public class CheckUtils
{@Resourceprivate RedisTemplate redisTemplate;public boolean checkWithBloomFilter(String checkItem,String key){int hashValue = Math.abs(key.hashCode());long index = (long) (hashValue % Math.pow(2, 32));boolean existOK = redisTemplate.opsForValue().getBit(checkItem, index);log.info("----->key:"+key+"\t对应坑位index:"+index+"\t是否存在:"+existOK);return existOK;}
}

Controller

@RestController
@Slf4j
public class CustomerController
{@Resource private CustomerSerivce customerSerivce;@ApiOperation("数据库初始化2条Customer数据")@RequestMapping(value = "/customer/add", method = RequestMethod.POST)public void addCustomer() {for (int i = 0; i < 2; i++) {Customer customer = new Customer();customer.setCname("customer"+i);customer.setAge(new Random().nextInt(30)+1);customer.setPhone("1381111xxxx");customer.setSex((byte) new Random().nextInt(2));customer.setBirth(Date.from(LocalDateTime.now().atZone(ZoneId.systemDefault()).toInstant()));customerSerivce.addCustomer(customer);}}@ApiOperation("单个用户查询，按customerid查用户信息")@RequestMapping(value = "/customer/{id}", method = RequestMethod.GET)public Customer findCustomerById(@PathVariable int id) {return customerSerivce.findCustomerById(id);}@ApiOperation("BloomFilter案例讲解")@RequestMapping(value = "/customerbloomfilter/{id}", method = RequestMethod.GET)public Customer findCustomerByIdWithBloomFilter(@PathVariable int id) throws ExecutionException, InterruptedException{return customerSerivce.findCustomerByIdWithBloomFilter(id);}
}

Service

@Service
@Slf4j
public class CustomerSerivce
{public static final String CACHA_KEY_CUSTOMER = "customer:";@Resourceprivate CustomerMapper customerMapper;@Resourceprivate RedisTemplate redisTemplate;@Resourceprivate CheckUtils checkUtils;/*** 写操作* @param customer*/public void addCustomer(Customer customer){int i = customerMapper.insertSelective(customer);if(i > 0){//mysql插入成功，写进redisCustomer result = customerMapper.selectByPrimaryKey(customer.getId());//redis缓存keyString key = CACHA_KEY_CUSTOMER+customer.getId();//写进redisredisTemplate.opsForValue().set(key,result);}}public Customer findCustomerById(Integer customreId){Customer customer = null;//缓存redis的key名称String key = CACHA_KEY_CUSTOMER+customreId;customer = getCustomer(customreId, key);return customer;}/*** 白名单：whitelistCustomer*/public Customer findCustomerByIdWithBloomFilter (Integer customerId){Customer customer = null;//缓存key的名称String key = CACHA_KEY_CUSTOMER + customerId;//布隆过滤器check，无是绝对无，有是可能有//===============================================if(!checkUtils.checkWithBloomFilter("whitelistCustomer",key)){log.info("白名单无此顾客，不可以访问: "+key);return null;}//===============================================//1 查询rediscustomer = getCustomer(customerId, key);return customer;}private Customer getCustomer(Integer customreId, String key) {Customer customer;//1 先去redis查询customer = (Customer) redisTemplate.opsForValue().get(key);//2 redis有直接返回，没有再进去查询mysqlif (customer == null) {// 3 再去查询我们的mysqlcustomer = customerMapper.selectByPrimaryKey(customreId);// 3.1 mysql有，redis无if (customer != null) {//3.2 把mysq查询出来的数据回写redis，保持一致性redisTemplate.opsForValue().set(key, customer);}}return customer;}
}

优缺点

优点
高效地插入和查询，内存占用bit空间少
缺点

1. 不能删除元素。
2. 因为删掉元素会导致误判率增加，因为hash冲突同一个位置可能存的东西是多个共有的你删除一个元素的同时可能也把其它的删除了。
3. 存在误判，不能精准过滤：有，是很可能有；无，是肯定无。

布谷鸟过滤器：解决布隆过滤器不能删除缺点

为了解决布隆过滤器不能删除元素的问题，布谷鸟过滤器横空出世。

论文：
《Cuckoo Filter：Better Than Bloom》