面试题：Redis（五）

1. 面试题

面试问

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

 

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

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

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

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

痛点：

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

 2. 亿级系统的四种常见统计

2.1 聚合统计

多个集合的交并差集就是聚合统计

2.2 排序统计

抖音短视频下的评论如何进行正序、反序，按页面进行排序？此时排序统计（ZSet）可解决该问题

 当涉及到排行榜、最新列表等等的展示可用ZSet这种有序集合进行排序统计

2.3 二值统计

集合的取值只有0和1两种取值，可用于签到、打卡等场景

常用bitmap进行解决该问题 

2.4. 基数统计

统计一个集合中不重复的元素

常用hypelroglog 

Redis十大常见数据类型跳转链接 

3. HyperLogLog

3.1 常见名词

UV：Unique Visitor 独立访客，一般理解为用户IP，需去重考虑

PV：Page View 页面浏览量，不用去重

DAU： Daily Active User 日活跃用户量，某产品登录或使用的用户数（需去重）

MAU：Monthly Active User 月活跃用户量

3.2 需求

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

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

 

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

 

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

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

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

 3.3 原理

问题引入 

去重复统计不止一种，还有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方法是精确计算的。

解决方案

通过牺牲准确率来换取空间，对于不要求绝对准确率的场景下可以使用，因为概率算法不直接存储数据本身，

通过一定的概率统计方法预估基数值，同时保证误差在一定范围内，由于又不储存数据故此可以大大节约内存。

 

HyperLogLog就是一种概率算法的实现。

HyperLogLog只是进行不重复的基数统计，既不是集合也不存储数据，只是记录数量，不记录具体内容，hyperloglog提供的是不精确的去重计算方案，牺牲精确性来换取空间，但误差仅仅是0.81%左右

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

 

4. GEO 

4.1 面试题

面试题说明：

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

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

 

会有什么问题呢？

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

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

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

4.2 需求

 

GEORADIUS 以给定的经纬度为中心，返回某一半径内的所有元素 

5. BitMap

5.1 面试题

 5.2 概述

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

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