布隆过滤器(bloom filter)介绍以及php和redis实现布隆过滤器实现方法

引言

在介绍布隆过滤器之前我们首先引入几个场景。

场景一

在一个高并发的计数系统中,如果一个key没有计数,此时我们应该返回0。但是访问的key不存在,相当于每次访问缓存都不起作用了。那么如何避免频繁访问数量为0的key而导致的缓存被击穿?

有人说, 将这个key的值置为0存入缓存不就行了吗?这是确实是一种解决方案。当访问一个不存在的key的时候,设置一个带有过期时间的标志,然后放入缓存。不过这样做的缺点也很明显:浪费内存和无法抵御随机key攻击。

场景二

在一个黑名单系统中,我们需要设置很多黑名单内容。比如一个邮件系统,我们需要设置黑名单用户,当判断垃圾邮件的时候,要怎么去做。比如爬虫系统,我们要记录下来已经访问过的链接避免下次访问重复的链接。

在邮件很少或者用户很少的情况下,我们用普通数据库自带的查询就能完成。在数据量太多的时候,为了保证速度,通常情况下我们会将结果缓存到内存中,数据结构用hash表。这种查找的速度是O(1),但是内存消耗也是惊人的。打个比方,假如我们要存10亿条数据,每条数据平均占据32个字节,那么需要的内存是64G,这已经是一个惊人的大小了。

一种解决思路

能不能有一种思路,查询的速度是O(1),消耗内存特别小呢?前辈门早就想出了一个很好的解决方案。由于上面说的场景判断的结果只有两种状态(是或者不是,存在或者不存在),那么对于所存的数据完全可以用位来表示。数据本身则可以通过一个hash函数计算出一个key,这个key是一个位置,而这个key所对的值就是0或者1(因为只有两种状态),如下图:

(更多…)

你可能还喜欢下面这些文章

gcc/g++编译参数详解

编译步骤gcc 与 g++ 分别是 gnu 的 c & c++ 编译器。gcc/g++ 在执行编译工作的时候,总共需要4步:预处理,生成 .i 的文件将预处理后的文件转换成汇编语言, 生成文件 .s 有汇编变为目标代码(机器代码)生成 .o 的文件连接目标代码, 生成可执行程序 参数详解-x language filename参数含义为指定文件所使用的语言。根据约定,C语言的后缀名称为".c",而 C++ 的后缀名为".cpp"或".cc",但如果你的源代码后缀不约定的那几种,那么需要使用-x参数来指定文件所使用的语言。这个参数对他后面的文件名都起作用。 可以使用的参数吗有下面的这些:

iterm2 使用 rz、sz 的方法

如果没有额外的设置,iterm2 使用 rzsz 的时候会卡在这个时候就需要使用iterm2提供的trigger来实现rzsz的功能。第一步:本机安装rzsz使用rzsz之前本地也需要安装如果没有安装brew,请先安装brew,mac必备的包管理器!第二步:创建发送和接收脚本发送文件的脚本如下,可以复制下面的内容,保存在 /usr/local/bin/iterm2-send-zmodem.sh中。接收文件的脚本如下,同样可以复制保存在/usr/local/bin/iterm2-recv-zmodem.sh第三步:设置Triggerteigger需要设置两个,一个实发送文件的trigger,一个

使用sublime+platuml高效画图

程序员难免要经常画流程图,状态图,时序图等。以前经常用 visio 画,经常为矩形画多大,摆放在哪等问题费脑筋。有时候修改文字后,为了较好的显示效果不得不再去修改图形。今天介绍的工具是如何使用 Sublime + PlantUML 的插件画流程图,状态图,时序图等。这是一种程序员看了就会爱上的画图方式:自然,高效。什么是 PlantUMLPlantUML 是一个画图脚本语言,用它可以快速地画出:时序图流程图用例图状态图组件图简单地讲,我们使用 visio 画图时需要一个一个图去画,但使用 PlantUML 只需要用文字表达出图的内容,然后就可以直接生成图片。看一个最简单的例子:软件安装这些软件

Go入门:六、常用标准库

这是我的Go学习的第六篇笔记,也是Go入门的最后一篇笔记。在大多数语言中,了解了变量和数据类型,流程控制,函数,面向对象,再加上标准库,就可以用这门语言去写一些项目了。首先让我想想,在工作中通常会用语言频繁处理什么问题或者处理什么数据?最常见的应该是各种字符串操作,日期和时间,读写文件、socket等IO相关的操作!字符串处理 — StringsString提供了一组处理字符串的操作,常用的有:判断一个字符串是否在另一个字符串中分割字符串为[]string和组合[]string为一个字符串字符串替换...太多了,就不一一列举了,这里列出一些常用的字符串操作。字符串判断字符串分割与合并字符串转换

Go入门:四、面向对象

这是我的Go学习笔记的第四篇,面向对象!现代语言几乎都会面向对象进行了支持!当然,Go也具备面向对象的特性!我的语言学习过程一般分为下面几个:1. 变量和数据类型2. 流程控制方法3. 函数声明和调用4. 面向对象5. 语言特性6. 标准库Go语言中的面向对象有点特殊。在Go语言里面,没有显式的class、extends等面向对象语言经常使用的关键词,但是却有面向对象的特性。看看Go怎么实现的把!创建一个类按照我的理解,类实际上就是某种模板,这个模板里面含有有限多个属性和方法。在Go里面,定义这个模板的语法使用type来实现!比如单个int类型可以构成一个类(没错,你甚至可以在int数据类型上

signal函数详解

signal作用是为信号注册一个处理器。这里的“信号”是软中断信号,这种信号来源主要有三种:程序错误:比如除0,非法内存访问。外部信号:终端Ctrl-C产生的SIGINT信号,定时器产生的SIGALERM。显示请求:kill函数发送的任意信号。当kill一个进程的时候,默认会发送SIGTERM信号,此时这个信号只有默认处理操作(SIG_DFL),直接中断进程执行。如果此时该进程正在执行一个任务,直接终止该进程会导致任务没有完成。这个时候为SIGTERM信号注册一个信号处理函数就十分有必要。介绍参数sig要设置信号处理函数的信号。它可以是实现定义值或下例值之一:SIGABRTSIGFPESIGI

C++动态内存管理

C++中,动态内存管理是通过一对运算符来完成:new 和 delete。new操作符在内存中为对象分配空间并返回一个指向该对象的指针,delete接收一个动态对象的指针,销毁该对象,并释放与之相关的内存。手动管理内存看起来只有这两个操作,似乎很轻松,但实际上这是一件非常繁琐的事情,分配了内存但没有释放内存的场景发生的概率太大了!回想一下,你有多少次打开抽屉却没关上,拿出来的护肤品擦完脸之后却忘了放回去,吃完饭却忘了洗碗。类似这种没有收尾的事情我做的太多了。(以上这些都是在实际生活中我爱人批评我的点)我连这种明面上的事情都能忘记收尾,何况分配内存!所以为了世界和平,我放弃了手动管理内存。好在C+

C++右值引用和移动

Attention:this blog is a translation of https://www.internalpointers.com/post/c-rvalue-references-and-move-semantics-beginners ,which is posted by @internalpoiners.一、前言在我的前一篇文章里,我解释了右值背后的逻辑。核心的思想就是:在C++中你总会有一些临时的、生命周期较短的值,这些值无论如何你都无法改变。令人惊喜的是,现代C++(通常指C++0x或者更高的版本)引入了右值引用(rvalue reference)的概念:它是一个新的

C++入门:三、函数

这是我学习C++的第三篇笔记,函数。我的学习路径是现在学习的是函数的声明、定义、调用等相关知识。函数声明和定义函数的声明包含返回类型,函数名字,0个或者多个形参,无函数体,通常在头文件中对函数进行声明。函数的定义包含返回类型,函数名字,0个或多个形参,以及函数体。比如写一个求阶乘的函数,可以写成下面这样写一些简单的函数大多数语言都差不多,不过可惜每种语言或多或少都有自己的特色,这是比较令人头秃的地方。函数的参数函数可以带有0或多个参数,每个参数都需要声明类型。参数传递可以传值和传引用。如果形参是引用类型,那么它将绑定到对应的实参中,我们成为传引用。否则,将会把实参的值拷贝后赋值给形参,我们成为

如何选择特征

特征工程是数据分析中最耗时间和精力的一部分工作,它不像算法和模型那样是确定的步骤,更多是工程上的经验和权衡。因此没有统一的方法。这里只是对一些常用的方法做一个总结。本文关注于特征选择部分。后面还有两篇会关注于特征表达和特征预处理。1. 特征的来源在做数据分析的时候,特征的来源一般有两块,一块是业务已经整理好各种特征数据,我们需要去找出适合我们问题需要的特征;另一块是我们从业务特征中自己去寻找高级数据特征。我们就针对这两部分来分别讨论。2.  选择合适的特征我们首先看当业务已经整理好各种特征数据时,我们如何去找出适合我们问题需要的特征,此时特征数可能成百上千,哪些才是我们需要的呢?第一

数据结构学习笔记:树

树是一种层次关系,在日常生活非常常见,比如社会关系,亲缘关系,文件管理。

一棵树是一些节点的集合,这个集合可以是空集,若非空,则一棵树由称作为根的节点r以及0个或者多个非空的(子)树组成,这些子树中的每一棵都是被来自根r的一条有向的边所连接。

一种数据结构需要包含一些操作,树这种数据结构有增加,删除,查找,修改。

节点

节点的度:节点子树的个数。

叶子节点:没有儿子的节点,也就是度为0的节点。

节点的层次:规定跟节点在1层,其他节点的层次为父节点的层次加1。

节点的高:节点的高为从这个节点到叶子的最长路径,所有树叶的高都是0。

节点的深度:从跟节点到该节点的唯一路径长,根的深度为0。

节点定义

typedef struct TreeNode *PtrToNode;

struct TreeNode
{
    ElementType Element;
    PtrToNode FitstChild;
    PtrNode NextSibling;
}

(更多…)

你可能还喜欢下面这些文章

一致性哈希的php实现

未来项目可能要上memcache集群,memcache集群的key分配完全在客户端完成,服务端不做任何处理,这里对key进行分配节点的最优方式就是使用一致性哈希。记得以前用mysql进行分库分表的时候,通常会用一个求余作为哈希函数,这样一些id就能对应相应的表了。不过使用mysql的时候,我们不需要考虑这些节点失效问题,以及节点增加或者减少的问题(在此之前应该做好足够的计划和准备),但是对于缓存,通常就比较宽松了,允许节点失效问题,但是普通的hash分配在节点失效之后,大部分的缓存位置都改变了,这显然个灾难,这个时候就要考虑一致性hash了,在增加或者删除节点,只有小部分的key会受影响。一致

使用php curl 的并发能力可以做什么

在php中,没有多线程让编程变得简单。但在一些需要并发提升性能的场景下,显得有些无能为力,比如发起一些http请求。但好在curl扩展可以让我们“并发”去请求网络资源。利用这个特点,我们能做很多有趣的事情。最基础的,并发请求网络资源,提升处理速度。并发访问代码<?phpclass ConcurrencyHTTP { private $_requests; private $_callbacks; private $_currentIndex = 0; public function get($url, $header = array(), $timeout = 3

shell中map的使用

bash 4.1.2 版本增加了map数据结构。map是一种常用的数据结构,通过map可以将key映射到一个value。使用方法map在使用之前需要先声明,声明的方式如下map需要先声明再使用。参数-A表示声明的变量是一个map。需要注意的是这里的A是大写的字母A。赋值操作map的赋值有两种方式,一种是直接给map赋值,如下:另一种是使用下标给map添加key-value对输出所有的key在文中最开始提到map的使用需要先声明,在没有声明的情况下此处会输出一个0,如下图:输出所有value输出map长度遍历,根据key找到对应的value遍历所有的key遍历所有的value问题FAQQ:为什么

介绍一款工具,memcacheadmin,使用php制作的memcached管理监控工具

MemAdmin是一款可视化的Memcached管理与监控工具,使用PHP开发,体积小,操作简单。主要功能: 服务器参数监控:STATS、SETTINGS、ITEMS、SLABS、SIZES实时刷新 服务器性能监控:GET、DELETE、INCR、DECR、CAS等常用操作命中率实时监控 支持数据遍历,方便对存储内容进行监视 支持条件查询,筛选出满足条件的KEY或VALUE 数组、JSON等序列化字符反序列显示 兼容memcache协议的其他服务,如Tokyo Tyrant (遍历功能除外) 支持服务器连接池,多服务器管理切换方便简洁guthub地址:https://github.com/ju

c++ 标准库二分查找

C++标准库中的二分查找可以通过和函数实现。这两个函数都在头文件中定义,并接受一个排序的范围(例如,,,等)以及一个要查找的值。返回指向在范围中第一个不小于(即大于或等于)给定值的元素的迭代器。则返回指向在范围中第一个大于给定值的元素的迭代器。下面是一个使用进行二分查找的例子:在这个例子中,我们首先定义了一个排序的,然后定义了一个目标值。我们使用查找,然后检查返回的迭代器是否指向。如果是,我们就打印出在中的位置。否则,我们打印出未找到的消息。如果你想查找的是范围中是否包含特定的值,并且不关心具体的位置,你可以将和的结果进行比较。如果它们相同,那么范围中不包含该值。否则,范围中包含该值。请注意,

mongo读写分离的一些坑

在使用mongo副本集的时候就在想,这些副本不用来读太浪费了,再翻阅php的mongodb驱动,发现一个美好的readPreference,可以设定读取的优先级,其中就有优先读取副本,甚至还可以设定读取最小网络延迟的节点,具体可以参考:http://php.net/manual/zh/mongodb-driver-readpreference.construct.php愿望是美好的,然而使用的过程中当我优先读取secondary时候,经常发现有的读取时间在几秒甚至几十秒的情况,也是醉了。于是经过一番搜索,发现有一个博客提到了这个问题,在官方文档中有说明,原文如下:How does concur

命令行下的mongo初试

从连接mongo开始,熟悉一下命令行下面的mongo使用连接普通连接mongo mongodb://ip:port查看数据库show dbs选择或者创建数据库use mydb创建一个集合比如创建一个mycollection的集合db.createCollection('mycollection')显示数据库中所有的集合show collections向集合中写入数据假设我们创建了一个mycollection集合,实际上当我们没有创建mycollection集合的时候,执行下面的命令mongo会自动创建一个mycollection集合db.mycollection.insert({"foo",'

python学习笔记:二、 流程控制

根据如何学习一门新的语言这篇文章的指导,现在的步骤就是学习这门语言的流程控制了。通常来讲,流程控制有顺序,选择,循环这几种。python也不例外,也有这三种流程控制。下面的一一学习。顺序顺序语句很简单,从上往下依次顺序执行。如:a = 1b = 2print(a+b)上面的语句就是顺序执行的语句。选择选择通常使用if和switch,但python中只有if这一个选择语句。语法是:if 满足条件1: 语句1elif 不满足条件1满足1条件2 语句2else 都不满足 语句3比如用一个实际的例子a = 1b = 2if a > b: print('a>b')el