关注我,你的眼睛会辣
来源|懂点技术
作者|技术王大拿
编辑|猿姐
我们把订单获取下来之后, 要进行下一步的处理, 比如扔到CRM中做消费者的识别, 或者扔进大数据系统做BI分析, 或者来个振奋人心的实时投屏。
因为一笔订单会产生多次事件,即便是同一个事件, 消息数据也可能会产生多条记录, 所以我们要对订单号判断是否已经投递过, 让同一笔订单在某些流程中只会传递到后端一次, 即去掉重复。
传统做法我们把数据放到数据库里, 或者是Key-Value型存储. 但是即使64G内存, 几百万的订单数据就会将其填满。 即使只存订单ID, 这点内存对于双十一这种场景也是杯水车薪。 而如果用硬盘, 则会大幅降低判重速度, 甚至拖慢整个系统的订单处理速度。 要知道对于订单的去重判断, 至少存储1个月的数据来实现比较可靠的结果。
所以我们的做法是这样的: 开一个二进制的内存区, 针对每一条进来的订单:
-
用一个Hash函数 (f1) 对订单id进行运算, 比如简单的timer33就行。
-
将得到的hash结果数字再对内存区总长度取模。 会得到一个数字 n1.
-
我们把内存区 n1 的位置填为1.
然后我们再换几种hash实现, 分别对应的函数式f2, f3, f4, f5. 结果分别是n2, n3, n4, n5.
将这些n1, n2, n3, n4, n5位置都填充为1.
当再来一条订单时, 我们重新用f1…f5对它的订单号进行运算, 然后将结果值分别到这个二进制区域做比对, 只要有任何一个位置为0, 则意味着该数据一定不存在于已有集合里。
就这样,因为并不需要将订单号本身存放在二进制区域内, 我们用有限的空间完成了对海量订单号的判断.
这个做法就是Bloom Filter, 也会被翻译为布隆过滤器。 在分布式系统, 垃圾电子邮件判断上也是大显身手, 尤其适合以小博大。 比如mongodb就用Bloom Filter作为数据存储的索引。
随着已存在集合的数据越来越多, 二进制区域的位置越来越多的被“染色”。 判断就会出现不准确的情况。
BloomFilter是一个概率游戏,判断不在, 则一定不在。 但是判断在, 则可能不在。
在这篇资料 http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html , 使用5个hash函数,二进制位的长度是保存项20倍时, 误判率在 0.00053. 准确率是99.95%。 也就是说, 如果要对一百万的订单数据做去重时, 我们只需要200多M的内存空间就足够了.
还有一个问题没解决啊。 当数据存储几个月, 数据量太大导致准去率下降怎么办?
Bloom Filter还有一种实现叫做Counting Bloom Filter. 经常简写为CBF, 在基础BF上增加了Counting信息, 这样该BF块就支持Remove了。 但是依然不适合本场景,因为没办法把数据倒放一遍做Remove, 当做扩展阅读吧。
那还能怎么办?
好办, 开30个BloomFilter, 每个订单来时对30个块均染色, 每天过期一个块, 新建一个块。
简单吗? 粗暴吗?
本项目源码已经放在
https://github.com/shopex/uniq
来点个星星吧
牛B程序猿
孤独地写程序时,你需要一些陪伴,一些快乐,一些”干“货。
扫码关注!