1.7 布隆过滤器

其数据结构包含一个大型的位数组和若干个不一样的无偏hash函数。所谓无偏即能够把元素的hash值计算得比较均匀,让元素被映射到位数组中的位置比较随记。

输入

预计元素数量:n
错误率:f

输出

位数组长度 l
hash函数的最佳数量 k

[code lang=”cpp”] k = 0.7 * (l / n) f = 0.6185 ^ (l / n) [/code]

空间占用估计

http://krisives.github.io/bloom-calculator/

误判率

[code lang=”shell”] f = (1 – 0.5^t) * k # k 是 hash函数的最佳数量 [/code]

应用

爬虫重复URL过滤
NoSQL数据库领域,降低磁盘IO
垃圾邮箱过滤

1.9 漏斗限流

维护漏斗属性:漏斗容量、漏嘴流水速率、漏斗剩余容量与上一次漏水时间。

每次灌水(请求)前,进行计算给漏斗腾出空间。能够腾出多少空间根据时间过去了多久(上一次漏水时间)以及流水速率有关。然后,判断当前请求是否具有足够空间。如果有,那么减少空间;如果没有,那么过滤请求。

为了实现这个过程,可以将一些漏斗的属性存储到一个Hash数据结构中。但是,有个问题,需要将“从Redis读取Hash数据结构到内存,随之在内存进行逻辑运算,最后将计算结果写回Redis”这些操作进行原子化。那么就需要进行加锁,而一旦加锁就意味着有加锁失败的可能,加锁失败就需要选择重试或者放弃。

如果重试,那么性能就会下降;如果放弃,那么会影响用户体验。

扩展

Redis-Cell扩展,将上述漏斗算法中的操作进行了原子化,并提供相应的指令。

Share:

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.