汕尾北京网站建设,自建网站做淘宝联盟,理财 网站模板 html,北京企业网站推广文章目录 面试题常见统计类型聚合统计排序统计二值统计基数统计 Hyperloglog专有名词UV#xff08;Unique Visitor#xff09;独立访客PV#xff08;Page View#xff09;页面浏览量DAU#xff08;Daily Active User#xff09;日活跃用户量MAU#xff08;Monthly Activ… 文章目录 面试题常见统计类型聚合统计排序统计二值统计基数统计 Hyperloglog专有名词UVUnique Visitor独立访客PVPage View页面浏览量DAUDaily Active User日活跃用户量MAUMonthly Active User 需求原理亿级UV的Redis统计方案 GEO面试题命令GEOADD获取某位置的经纬度GEOPOS返回坐标的Geohash表示GEOHASH两个位置之间距离GEODIST半径范围内的坐标GEORADIUS半径范围内坐标中心点是给定元素GEORADIUSBYMEMBER Bitmap面试题作用场景 布隆过滤器BloomFilter需求概述作用原理概述原理添加、查询元素过程使用步骤使用场景 手写布隆过滤器案例优缺点布谷鸟过滤器解决布隆过滤器不能删除缺点 面试题
抖音电商直播主播介绍的商品有评论1个商品对应了1系列的评论排序展现取前10条记录用户在手机App上的签到打卡信息:1天对应1系列用户的签到记录新浪微博、钉钉打卡签到来没来如何统计?应用网站上的网页访问信息:1个网页对应1系列的访问点击淘宝网首页每天有多少人浏览首页?你们公司系统上线后说一下UV、PV、DAU分别是多少? 记录对集合中的数据进行统计 在移动应用中需要统计每天的新增用户数和第2天的留存用户数在电商网站的商品评论中需要统计评论列表中的最新评论在签到打卡中需要统计一个月内连续打卡的用户数在网页访问记录中需要统计独立访客Unique VisitorUV量。
需求 亿级数据的收集清洗统计展现
常见统计类型 亿级系统常见统计方式 聚合统计
统计多个集合元素的聚合结果就是前面讲解过的交差并等集合统计 交并差集和聚合函数的应用
排序统计
抖音短视频最新评论留言的场景请你设计一个展现列表。
在面对需要展示最新列表、排行榜等场景时如果数据更新频繁或者需要分页显示建议使用ZSet
二值统计
集合元素的取值就只有0和1两种。 在钉钉上班签到打卡的场景中我们只用记录有签到(1)或没签到(0) bitmap
基数统计
指统计一个集合中不重复的元素个数 见hyperloglog
Hyperloglog 去重统计估计算法 专有名词
UVUnique Visitor独立访客
需要去重考虑
PVPage View页面浏览量
不用去重
DAUDaily Active User日活跃用户量
登录或者使用了某个产品的用户数去重复登录的用户 常用于反映网站、互联网应用或者网络游戏的运营情况
MAUMonthly Active User
月活跃用户量
需求
很多计数类场景比如 每日注册 IP 数、每日访问 IP 数、页面实时访问数 PV、访问用户数 UV等。因为主要的目标高效、巨量地进行计数所以对存储的数据的内容并不太关心。也就是说它只能用于统计巨量数量不太涉及具体的统计对象的内容和精准性。统计单日一个页面的访问量(PV)单次访问就算一次。统计单日一个页面的用户访问量(UV)即按照用户为维度计算单个用户一天内多次访问也只算一次。多个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地址位置选择 查询性能问题如果并发高数据量大这种查询是要搞垮mysql数据库的一般mysql查询的是一个平面矩形访问而叫车服务要以我为中心N公里为半径的圆形覆盖。精准度的问题我们知道地球不是平面坐标系而是一个圆球这种矩形计算在长距离计算时会有很大误差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 天安门 长城 kmm 米 km 千米 ft 英尺 mi 英里
半径范围内的坐标GEORADIUS
GEORADIUS city 116.418017 39.914402 10 km withdist withcoord count 10 withhash descWITHDIST: 在返回位置元素的同时 将位置元素与中心之间的距离也一并返回。 距离的单位和用户给定的范围单位保持一致。WITHCOORD: 将位置元素的经度和维度也一并返回。WITHHASH: 以 52 位有符号整数的形式 返回位置元素经过原始 geohash 编码的有序集合分值。 这个选项主要用于底层应用或者调试 实际中的作用并不大COUNT 限定返回的记录数。
半径范围内坐标中心点是给定元素GEORADIUSBYMEMBER
GEORADIUSBYMEMBER city 天安门 km withdist withcoord count 10 withhash descBitmap
面试题
日活统计连续签到打卡最近一周的活跃用户统计指定用户一年之中的登陆天数某用户哪几天登陆过哪几天没有登陆全年中登录的天数共计多少
作用场景
用户是否登陆过Y、N比如京东每日签到送京豆电影、广告是否被点击播放过钉钉打卡上下班签到统计
布隆过滤器BloomFilter
需求
现有50亿个电话号码现有10万个电话号码如何要快速准确的判断这些电话号码是否已经存在?安全连接网址全球数10亿的网址判断黑名单校验识别垃圾邮件白名单校验识别出合法用户进行后续处理
概述 由一个初值都为零的bit数组和多个哈希函数构成1用来快速判断集合中是否存在某个元素 本质就是判断具体数据是否存在于一个大的集合中 布隆过滤器是一种类似set的数据结构国只是统计结果在巨量数据下有点小瑕疵不够完美
作用
高效地插入和查询占用空间少返回的结果是不确定性不够完美。
重点
一个元素如果判断结果:存在时元素不一定存在但是判断结果为不存在时则一定不存在。布隆过滤器可以添加元素但是不能删除元素由于涉及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
使用步骤
初始化Bitmap 布隆过滤器 本质上 是由长度为 m 的位向量或位列表仅包含 0 或 1 位值的列表组成最初所有的值均设置为 0 添加对应占位
当我们向布隆过滤器中添加数据时为了尽量地址不冲突会使用多个 hash 函数对 key 进行运算算得一个下标索引值然后对位数组长度进行取模运算得到一个位置每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。
例如我们添加一个字符串wmyskxz对字符串进行多次hash(key) → 取模运行→ 得到坑位
判断是否存在 向布隆过滤器查询某个key是否存在时先把这个 key 通过相同的多个 hash 函数进行运算查看对应的位置是否都为 1 只要有一个位为零那么说明布隆过滤器中这个 key 不存在 如果这几个位置全都是 1那么说明极有可能存在 因为这些位置的 1 可能是因为其他的 key 存在导致的
例如在 add 了字符串wmyskxz数据之后很明显下面1/3/5 这几个位置的 1 是因为第一次添加的 wmyskxz 而导致的此时我们查询一个没添加过的不存在的字符串inexistent-key它有可能计算后坑位也是1/3/5
使用场景
解决缓存穿透问题redis结合Bitmap使用
把已存在数据的key存在布隆过滤器中相当于redis前面挡着一个布隆过滤器。
当有新的请求时先到布隆过滤器中查询是否存在 如果布隆过滤器中不存在该条数据则直接返回 如果布隆过滤器中已存在才去查询缓存redis如果redis里没查询到则再查询Mysql数据库
黑名单校验安全连接网址亿级数量判断
手写布隆过滤器案例 初始化白名单用户到布隆过滤器
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(customeri);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_CUSTOMERcustomer.getId();//写进redisredisTemplate.opsForValue().set(key,result);}}public Customer findCustomerById(Integer customreId){Customer customer null;//缓存redis的key名称String key CACHA_KEY_CUSTOMERcustomreId;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空间少 缺点
不能删除元素。因为删掉元素会导致误判率增加因为hash冲突同一个位置可能存的东西是多个共有的你删除一个元素的同时可能也把其它的删除了。存在误判不能精准过滤有是很可能有无是肯定无。
布谷鸟过滤器解决布隆过滤器不能删除缺点 为了解决布隆过滤器不能删除元素的问题布谷鸟过滤器横空出世。 论文 《Cuckoo FilterBetter Than Bloom》
