《Redis深度历险》Chapter 1 Learn Note

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

1.7 布隆过滤器

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

输入

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

输出

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

k = 0.7 * (l / n)
f = 0.6185 ^ (l / n)

空间占用估计

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

误判率

f = (1 - 0.5^t) * k # k 是 hash函数的最佳数量

应用

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

1.9 漏斗限流

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

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

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

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

扩展

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


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...


分类: Redis, 技术, 随记 | 标签: , , , , | 评论 | Permalink

发表评论

电子邮件地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据