做信息流服务端的左发一定会遇到用户历史数据的集合，对于一些有限信息流（因DT数据中心的推荐数据变化较慢，推荐量不大），历史数据可以使用一般的hash结构来实现，存储用户的访问历史数据，我们曾经有块业务就是这样，用户从第一屏开始请求到最后一屏，整个过程的信息流数据不能出现已经访问的内容，于是我们使用了一个hash结构，而且在访问完所有内容之后下次再进入时进行清除历史数据以防止用户无数据。但对于一些无限信息流（DT推荐数据变化较快，甚至是实时变化的情况），此时就需要长时间甚至永久记录用户的历史已看数据）。从而实现用户在每次访问的时候在给用户展现数据前对数据进行过滤，对已阅读过的数据进行过滤。本文地址:http://www.04007.cn/article/689.html,未经许可,不得转载.
一般的实现方法，可能使用KV存储进行get/Set判断，也可以考虑使用hashMap数据结构，这种方式在数据量小的时候都是完全可以的，但随着数据量的急剧增大，hash数据的存储以及在查询方面都会存一些问题，比如占用内存较大的问题。这时我们就可以了解一下redis的HyperLogLog数据结构以及布隆过滤器了。本文地址:http://www.04007.cn/article/689.html,未经许可,不得转载.
HyperLogLog与布隆过滤器都是针对大数据统计存储应用场景下的知名算法。HyperLogLog是在大数据的情况下关于数据基数的空间复杂度优化实现，布隆过滤器是在大数据情况下关于检索一个元素是否在一个集合中的空间复杂度优化后的实现，它是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。比起hashmap它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的，虽然牺牲了一个小概率的准确性，但可以达到工程上的需求，对于准确度要求不是特别高，但数据量巨大的场景是非常合适的，比如上面提到的信息流内容判断是否在用户已阅历史中。
布隆过滤器原理如下图：我们在集合中存储有三个元素x,y,z，但实际其并未存储这三个原始元素（空间占用较大），而是将这三个元素各通过一些hash算法将其对应到一个超大的位数组（初始时各位置的值均为1）上，从图中可看到其是通过三种hash算法将x,y,z计算出的hash值映射到位数组并将位数组上的值置成1。当我们判断x是否在集合中时，对x也进行同样的hash计算找到位置，如果位置上的值都是1，说明x可能存在，如果我们对于t进行hash计算，发现对应的三个位置中有一个位置不存在，说明t一定不存在。这就能基本实现我们的历史已阅文章的判断上了。原理图如下：本文地址:http://www.04007.cn/article/689.html,未经许可,不得转载.
本文地址:http://www.04007.cn/article/689.html,未经许可,不得转载.
比如我们刷头条的信息流文章，每一个用户已经看过的文章ID都单独存在redis中的HyperLogLog结构中，而当这个用户来刷新信息流的时候，我们取到了一个文章ID列表，然后逐个将文章ID扔到HyperLogLog结构中判断这个ID是否存在，如果返回false，则表示这篇文章一定没有看过，于是我们就可以将这篇文章推给用户。如果返回true，则这篇文章有可能用户看过，这个时候可以过滤这篇文章，从而可以保证用户看到的所有文章一定是其没有看过的。而使用REDIS中的HyperLogLog可以支持的已看历史文章数据级占用内存有效率在数据量大的时候肯定优于redis的hash，因为上面说过的HyperLogLog并未存储每篇文章的ID值，而只是把这些ID值hash处理后转化为了对应位上的1/0标志，因而内存占用很少，而其计算量就是对key的几次hash计算。本文地址:http://www.04007.cn/article/689.html,未经许可,不得转载.
本文地址:http://www.04007.cn/article/689.html 未经许可,不得转载. 手机访问本页请扫描右下方二维码.
|
|
手机扫码直接打开本页面 |
