布隆过滤器

1. 前言在前些年的开发中就遇到几个相似的场景： 场景1场景：我以后业务表构造冗余了人员的信息字段，当人员的根本信息产生变更或删除时，会推送MQ。我以后业务监听到有人员信息变更的MQ音讯，会查数据库，看看该人员在以后表中是否存在。如果存在则更新，如果不存在则无需解决。 问题：每当监听到人员变更的的MQ音讯，就须要查问表中是否存在，给数据库带来耗费。 尝试计划：将以后表中的所有人员ID，存入redis Set汇合中。在监听到人员变更的MQ音讯时，先去Set中检查一下是否存在。如果存在再去更新数据库。 尝试计划的问题：当人员数量几十万的时候，redis Set汇合也会很大，redis key太大影响性能，检查人员是否存在也会变慢。 场景2咱们有些高频调用的查问接口，因为调用频率高，查库简单，因而曾经做了缓存。缓存的策略是：如果查问对应的缓存key存在，则从缓存获取；如果不存在，则在查库，如果查库能取得有效值，再将后果存入缓存。 带来的问题：接口对外裸露后，因为前台调用方不可控，可能总会查问不存在的key。造成缓存穿透，频繁的有效查库。 尝试计划：针对缓存穿透，当查问某个key，在库中不存在时。在缓存中仍然创立一个key，value设为null。 尝试计划的问题：设为null的key，就只有等过期工夫到了后，自行删除。有些时候上一秒查库不存在，给对应的key缓存了一个为null的value。但下一秒库中有了，走缓存拿到的仍然是null。 更好的解决方案对于下面可能遇到的问题，和尝试的解决方案，有一个更好的解决方案：布隆过滤器。 能够了解为场景1外面的那个Set，只不过容量更小，检索性能更高。那么针对场景2缓存穿透的问题，将所有的缓存key存入布隆过滤器中，如果在过滤器中的key，再通过缓存、数据库获取。 2. 布隆过滤器布隆过滤器（Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。次要用于判断一个元素是否在一个汇合中。 通常咱们会遇到很多要判断一个元素是否在某个汇合中的业务场景，个别想到的是将汇合中所有元素保存起来，而后通过比拟确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。然而随着汇合中元素的减少，咱们须要的存储空间也会出现线性增长，最终达到瓶颈。同时检索速度也越来越慢。上述三种构造的检索工夫复杂度别离为： O(n)：链表O(logn)：树O(1)：哈希表这个时候，布隆过滤器（Bloom Filter）就应运而生。 2.1. 原理当一个元素被退出汇合时，通过N个Hash函数将这个元素进行Hash，算出一个整数索引值，而后对数组长度进行取模运算，从而失去一个地位，每个Hash函数都会失去一个不同的地位，而后再把位数组中的几个地位点都置为1。 检索时，也会把哈希的几个地位算进去，而后看看位数组中对应的几个地位是否都为1，只有有一个位为0，那么就阐明布隆过滤器里不存在这个元素。 然而，这几个地位都为1，并不能齐全阐明这个元素就肯定存在其中。因为散列函数是会有碰撞的，不同的输出，可能在哈希后为同一个地位。即有可能这些地位为1是因为其余元素的存在，这就是布隆过滤器会呈现误判的起因。 因而查问某个变量的时候咱们只有看看这些点是不是都是 1 就能够大概率晓得汇合中有没有它了 如果这些点有任何一个 0，则被查问变量肯定不在。如果都是 1，则被查问变量很可能存在。2.2. 个性与优缺点1. 不存在时肯定不存在一个元素如果判断后果为存在的时候元素不肯定存在，然而判断后果为不存在的时候则肯定不存在。 起因：布隆过滤器的误判是指多个输出通过哈希之后，在雷同的bit位的值置1了，这样就无奈判断到底是哪个输出产生的，因而误判的本源在于雷同的 bit 位被屡次映射且置 1。 2. 只增不删布隆过滤器能够增加元素，然而不能删除元素。因为删掉元素会导致误判率减少。 起因：上述起因中的状况，多个输出通过哈希之后，在雷同的bit位的值置1了，也造成了布隆过滤器的删除问题。因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果咱们间接删除这一位的话，会影响其余的元素。 如果须要删除一批元素，能够思考从新初始化一个布隆过滤器，替换原来的。 3. 长处占用空间极小，插入和查问速度极快；布隆过滤器能够示意选集，其它任何数据结构都不能；3. 毛病误算率随着元素的减少而减少；个别状况下无奈删除元素；2.3. 利用场景基于上述的性能，咱们大抵能够把布隆过滤器用于以下的场景之中： 1. 大数据判断是否存在来实现去重这就能够实现出上述的去重性能，如果你的服务器内存足够大的话，那么应用 HashMap 可能是一个不错的解决方案，实践上工夫复杂度能够达到 O(1) 的级别，然而当数据量起来之后，还是只能思考布隆过滤器。 2. 判断用户是否拜访过判断用户是否浏览过某视频或文章，比方抖音或头条，当然会导致肯定的误判，但不会让用户看到反复的内容。 3. 爬虫/邮箱等零碎的过滤平时不晓得你有没有留神到有一些失常的邮件也会被放进垃圾邮件目录中，这就是应用布隆过滤器误判导致的。 4. 人造适宜缓存穿透场景布隆过滤器人造就能应答缓存穿透的场景。 首先，布隆过滤器的利用策略正好和缓存是相同的： 缓存策略：缓存中不存在的，再去查db。布隆过滤器策略：过滤器中存在的，再去查缓存（db）。而后，因为它的个性：一个元素如果判断后果为存在的时候元素不肯定存在，然而判断后果为不存在的时候则肯定不存在。 这表明它的误判率并不影响它的策略： 当判断后果为存在时：不肯定存在。带来的不好的后果，顶多就是多查一次缓存。当判断后果为不存在时：肯定不存在。策略中判断不存在时，以后申请就会被拦挡，这方面是没有误判的。所以说，布隆过滤器人造适宜缓存穿透的场景，它的误判率对与该场景没有丝毫影响。 2.4. 实现有很多布隆过滤器的实现，就如同之前将限流器的实现有 guava 和 redisson，布隆过滤器的实现也一样。 ...

一、什么是布隆过滤器（BoomFilter）Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地示意一个汇合，并能判断一个元素是否属于这个汇合。它实际上是一个很长的二进制向量和一系列随机映射函数。 特点总结为如下： 空间效率高的概率型数据结构，用来查看一个元素是否在一个汇合中。对于一个元素检测是否存在的调用，BloomFilter会通知调用者两个后果之一：可能存在或者肯定不存在。二、应用场景解决缓存穿透咱们常常会把一部分数据放在Redis等缓存，比方产品详情。这样有查问申请进来，咱们能够依据产品Id间接去缓存中取数据，而不必读取数据库，这是晋升性能最简略，最广泛，也是最无效的做法。个别的查问申请流程是这样的：先查缓存，有缓存的话间接返回，如果缓存中没有，再去数据库查问，而后再把数据库取出来的数据放入缓存，所有看起来很美妙。然而如果当初有大量申请进来，而且都在申请一个不存在的产品Id，会产生什么？既然产品Id都不存在，那么必定没有缓存，没有缓存，那么大量的申请都怼到数据库，数据库的压力一下子就上来了，还有可能把数据库打死。尽管有很多方法都能够解决这问题，然而咱们的配角是“布隆过滤器”，没错，“布隆过滤器”就能够解决（缓解）缓存穿透问题。至于为什么说是“缓解”，看上来你就明确了。大量数据，判断给定的是否在其中当初有大量的数据，而这些数据的大小曾经远远超出了服务器的内存，当初再给你一个数据，如何判断给你的数据在不在其中。如果服务器的内存足够大，那么用HashMap是一个不错的解决方案，实践上的工夫复杂度能够达到O(1)，然而当初数据的大小曾经远远超出了服务器的内存，所以无奈应用HashMap，这个时候就能够应用“布隆过滤器”来解决这个问题。然而还是同样的，会有肯定的“误判率”。进行垃圾邮件过滤(垃圾数据过滤)网页爬虫对 URL 的去重，防止爬取雷同的 URL 地址三、实现原理布隆过滤器的外围实现是一个超大的位数组和几个哈希函数。假如位数组的长度为 m，哈希函数的个数为 k。以上图为例，具体的操做流程：假如汇合外面有 3 个元素 {x, y, z}，哈希函数的个数为 3。首先将位数组进行初始化，将外面每一个位都设置位 0。对于汇合外面的每个元素，将元素顺次通过 3 个哈希函数进行映射，每次映射都会产生一个哈希值，这个值对应位数组下面的一个点，而后将位数组对应的地位标记为 1。查问 W 元素是否存在汇合中的时候，一样的办法将 W 通过哈希映射到位数组上的 3 个点。若是 3 个点的其中有一个点不为 1，则可能判断该元素必然不存在汇合中。反之，若是 3 个点都为 1，则该元素可能存在汇合中。留神：此处不能判断该元素是否必然存在汇合中，可能存在必然的误判率。可能从图中可能看到：假如某个元素通过映射对应下标为 四、五、6 这 3 个点。尽管这 3 个点都为 1，可是很显著这 3 个点是不一样元素通过哈希取得的地位，所以这种情况阐明元素尽管不在汇合中，也可能对应的都是 1，这是误判率存在的原因。 劣势相比于其它的数据结构，布隆过滤器在空间和工夫方面都有微小的长处。布隆过滤器存储空间和插入/查问工夫都是常数。另外，Hash 函数相互之间没有关系，不便由硬件并行实现。布隆过滤器不须要存储元素本人，在某些对窃密要求很是严格的场合有长处。布隆过滤器可能示意选集，其它任何数据结构都不能。 毛病可是布隆过滤器的毛病和劣势同样显著。误算率（False Positive）是其中之一。随着存入的元素数量增长，误算率随之增长（误判补救办法是：再创立一个小的白名单，存储那些可能被误判的信息）。可是若是元素数量太少，则应用散列表足矣。另外，通常情况下不能从布隆过滤器中删除元素。咱们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可能了。然而要保障平安的删除元素并不是如此简略。首先咱们必须保障删除的元素确实在布隆过滤器外面. 这一点单凭这个过滤器是没法保障的。另外计数器回绕也会造成问题。 四、举荐应用Guava的布隆过滤器 Maven： <dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>22</version></dependency>建设 BloomFilter 对象，须要传入 Funnel 对象，预估的元素个数，误判率。 BloomFilter<String> filter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), 1000,0.01);应用 put 办法增加元素： filter.put("test");应用 mightContain 办法判断元素是否存在： ...

前言很久没写文章了，明天来学习下赫赫有名的 布隆过滤器 。 注释什么是布隆过滤器这个牛轰轰的神器是布隆这位大牛在 1970 年创造的，是一个二进制向量数据结构，过后专门解决数据查问问题。能够用来通知你 某样货色肯定不存在或者可能存在。 相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，然而毛病是其返回的后果是概率性的，而不是确切的。 布隆过滤器有什么用说起布隆过滤器的作用能够大家可能首先想到的就是Redis缓存穿透，那咱们先来说说什么是缓存穿透？ 你必定上过京东、淘宝这样的购物网站，不知有没有留神过：在咱们日常开发中，其实每一个页面的 URL 网址是和具体的商品对应的。 比如说，以后我标红的 857，就是咱们商品的 sku 编号，你能够了解为是这个商品型号的惟一编码。这里商品编号为 857，那显示的页面天然也是对应的内容。 比方在 618 当天，数亿网友 shopping 剁手时，商城利用同时收到海量申请，要求拜访、下单、领取，这时机器如何顶得住呢？这就波及咱们零碎的架构了，来看一下。 首先作为商城的用户，他发动一个申请，比方这里还是要查看 857 号的商品。 这时作为商城应用程序，它会向后盾的 Redis 缓存服务器进行查问。 如果缓存数据库中没有 857 号的商品数据，咱们程序就须要在后盾的数据库服务器中进行查问，并且填充至 Redis 服务器，这是一个失常的操作流程。 那么在长时间积攒后，咱们的缓存服务器外面的数据可能就是这个样子的。为了好了解，这里我假如商城有 1000 件商品，编号从 1~1000。 此时此刻作为商城用户，如果查问 857 号商品时，商城利用就不再须要从 MySQL 数据库中进行数据提取，间接从 Redis 服务器中将数据提取并返回就能够了。因为 Redis 它是基于内存的，无论是从吞吐量还是处理速度来说，都要比传统的 MySQL 数据库快很多倍。 随着工夫一直积攒，那么在 Redis 的服务器中应该会存储编号从 1~1000 的所有商品数据缓存。 Redis 面临的安全隐患：缓存穿透 大家请留神以后缓存中只有 1~1000 号数据。假如如果是同行歹意竞争，或者由第三方公司研发了爬虫机器人，在短时间内批量的进行数据查问，而这些查问的编号则是之前数据库中不存在的，比方当初看到的 8888、8889、8890 这些都是不存在的。 此时咱们零碎就会遇到一个重大的安全隐患：因为商城利用在向后盾 Redis 查问时，因为缓存中没有这条数据，它就进而到了数据库服务器中进行查问。 【有效申请超高并发，会导致解体】 要晓得数据库服务器对于刹时超高并发的拜访承载能力并不强。所以在短时间内，由爬虫机器人或者流量攻打机器人发来的这些有效的申请，都会霎时的灌入到数据库服务器中，对咱们的零碎的性能造成极大的影响，甚至会产生零碎解体。 而这种绕过 Redis 服务器，间接进入后盾数据库查问的攻击方式，咱们就称之为缓存穿透。 ...

在程序的世界中，布隆过滤器是程序员的一把利器，利用它能够疾速地解决我的项目中一些比拟辣手的问题。如网页 URL 去重、垃圾邮件辨认、大汇合中反复元素的判断和缓存穿透等问题。 布隆过滤器（Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器能够用于检索一个元素是否在一个汇合中。它的长处是空间效率和查问工夫都比个别的算法要好的多，毛病是有肯定的误识别率和删除艰难。 浏览更多对于 Angular、TypeScript、Node.js/Java 、Spring 等技术文章，欢送拜访我的集体博客 ——全栈修仙之路一、布隆过滤器简介当你往简略数组或列表中插入新数据时，将不会依据插入项的值来确定该插入项的索引值。这意味着新插入项的索引值与数据值之间没有间接关系。这样的话，当你须要在数组或列表中搜寻相应值的时候，你必须遍历已有的汇合。若汇合中存在大量的数据，就会影响数据查找的效率。 针对这个问题，你能够思考应用哈希表。利用哈希表你能够通过对 “值” 进行哈希解决来取得该值对应的键或索引值，而后把该值寄存到列表中对应的索引地位。这意味着索引值是由插入项的值所确定的，当你须要判断列表中是否存在该值时，只须要对值进行哈希解决并在相应的索引地位进行搜寻即可，这时的搜寻速度是十分快的。 bf-array-vs-hashtable.jpg 依据定义，布隆过滤器能够查看值是 “可能在汇合中” 还是 “相对不在汇合中”。“可能” 示意有肯定的概率，也就是说可能存在肯定为误判率。那为什么会存在误判呢？上面咱们来剖析一下具体的起因。 布隆过滤器（Bloom Filter）实质上是由长度为 m 的位向量或位列表（仅蕴含 0 或 1 位值的列表）组成，最后所有的值均设置为 0，如下图所示。 bf-bit-vector.jpg 为了将数据项增加到布隆过滤器中，咱们会提供 K 个不同的哈希函数，并将后果地位上对应位的值置为 “1”。在后面所提到的哈希表中，咱们应用的是单个哈希函数，因而只能输入单个索引值。而对于布隆过滤器来说，咱们将应用多个哈希函数，这将会产生多个索引值。 bf-input-hash.jpg 如上图所示，当输出 “semlinker” 时，预设的 3 个哈希函数将输入 2、4、6，咱们把相应地位 1。假如另一个输出 ”kakuqo“，哈希函数输入 3、4 和 7。你可能曾经留神到，索引位 4 曾经被先前的 “semlinker” 标记了。此时，咱们曾经应用 “semlinker” 和 ”kakuqo“ 两个输出值，填充了位向量。以后位向量的标记状态为： bf-input-hash-1.jpg 当对值进行搜寻时，与哈希表相似，咱们将应用 3 个哈希函数对 ”搜寻的值“ 进行哈希运算，并查看其生成的索引值。假如，当咱们搜寻 ”fullstack“ 时，3 个哈希函数输入的 3 个索引值别离是 2、3 和 7： ...

明天的文章和大家一起来学习大数据畛域一个常常用到的算法——布隆过滤器。如果看过《数学之美》的同学对它应该并不生疏，它常常用在汇合的判断上，在海量数据的场景当中用来疾速地判断某个元素在不在一个宏大的汇合当中。它的原理不难，然而设计十分奇妙，。 欢送各位进群973961276一起聊聊技术吹吹牛，每周都会有几次抽奖送专业书籍的流动，奖品虽不甚值钱，但也算个彩头不是 原理在我之前的了解当中，如果想要判断某个元素在不在汇合当中，经典的构造应该是均衡树和hash table。然而无论是哪一种办法，都逃不开一点，都须要存储原值。 比方在爬虫场景当中，咱们须要记录下之前爬过的网站。咱们要将之前的网址全副都存储在容器里，而后在遇到新网站的时候去判断是否曾经爬过了。在这个问题当中，咱们并不关怀之前爬过的网站有哪些，咱们只关怀当初的网站有没有在之前呈现过。也就是说之前呈现过什么不重要，当初的有没有呈现过才重要。 咱们利用均衡树或者是Trie或者是AC自动机等数据结构和算法能够实现高效的查找，然而都离不开存储下所有的字符串。设想一下，一个网址大略上百个字符，大概0.1KB，如果是一亿个网址，就须要10GB了，如果是一百亿一千亿呢？显然这么大的规模就很麻烦了，明天要介绍的布隆过滤器就能够解决这个问题，而且不须要存储下原值，这是一个十分奇妙的做法，让咱们一起来看下它的原理。 布隆过滤器自身的构造非常简单，就是一个一维的bool型的数组，也就是说每一位只有0或者1，是一个bit，这个数组的长度是m。对于每个新增的项，咱们应用K种不同的hash算法对它计算hash值。所以咱们能够失去K个hash值，咱们用hash值对m取模，假如是x。刚开始的时候数组内全部都是0，咱们把所有x对应的地位标记为1。 举个例子，假如咱们一开始m是10，K是3。咱们遇到第一个插入的值是”线性代数“，咱们对它hash之后失去1，3，5，那么咱们将对应的地位标记成1. 而后咱们又遇到了一个值是”高等数学“，hash之后失去1，8，9，咱们还是将对应地位赋值成1，会发现1这个地位对应的值曾经是1了，咱们疏忽就好。 如果这个时候咱们想要判断”概率统计”有没有呈现过，怎么办？很简略，咱们对“概率统计”再计算hash值。假如失去1，4，5，咱们去遍历一下对应的地位，发现4这个地位是0，阐明之前没有增加过“概率统计”，显然“概率统计”没有呈现过。 然而如果“概率统计”hash之后的后果是1，3，8呢？咱们判断它呈现过就错了，答案很简略，因为尽管1，3，8这个hash组合之前没有呈现过，然而对应的地位都在其余元素中呈现过了，这样就呈现误差了。所以咱们能够晓得，布隆过滤器对于不存在的判断是精确的，然而对于存在的判断是有可能有谬误的。 零根底和大三大四的敌人看这里>>c/c++ 企业级我的项目实战曾经工作了想持续自我晋升跳槽涨薪的工程师看这里>>c/c++ linux服务器高级架构师学习 代码布隆过滤器的原理很简略，明确了之后，咱们很容易写出代码： # 插入元素def BloomFilter(filter, value, hash_functions): m = len(filter) for func in hash_functions: idx = func(value) % m filter[idx] = True return filter # 判断元素def MemberInFilter(filter, value, hash_functions): m = len(filter) for func in hash_functions: idx = func(value) % m if not filter[idx]: return False return True 错误率计算之前的例子当中应该展现得很明确了，布隆过滤器尽管好用，然而会存在bad case，也就是判断谬误的状况。那么，这种错误判断产生的概率有多大呢？ 这个概率的计算也不难：因为数组长度是mm，所以插入一个bit它被置为1的概率是1m1m，插入一个元素须要插入k个hash值，所以插入一个元素，某一位没有被置为1的概率是(1−1m)k(1−1m)k。插入n个元素之后，某一位仍旧为0的概率是(1−1m)nk(1−1m)nk，它变成1的概率是1−(1−1m)nk1−(1−1m)nk。 ...

定义PV是page view的缩写，即页面浏览量，通常是衡量一个网络新闻频道或网站甚至一条网络新闻的主要指标。网页浏览数是评价网站流量最常用的指标之一，简称为PVUV是unique visitor的简写，是指通过互联网访问、浏览这个网页的自然人。 通过以上的概念，可以清晰的看出pv是比较好设计的，网站的每一次被访问，pv都会增加，但是uv就不一定会增加了，uv本质上记录的是按照某个标准划分的自然人，这个标准其实我们可以自己去定义，比如：可以定义同一个IP的访问者为同一个UV，这也是最常见的uv定义之一，另外还有根据cookie定义等等。无论是pv还是uv，都需要一个时间段来加以描述，平时我们所说的pv，uv数量指的都是24小时之内（一个自然日）的数据。 pv相比较uv来说，技术上比较容易一些，今天咱们就来说一说uv的统计，为什么说uv的统计相对来说比较难呢，因为uv涉及到同一个标准下的自然人的去重，尤其是一个uv千万级别的网站，设计一个好的uv统计系统也许并非想象的那么容易。 那我们就来设计一个以一个自然日为时间段的uv统计系统，一个自然人（uv）的定义为同一个来源IP（当然你也可以自定义其他标准），数据量级别假设为每日千万uv的量级。 注意：今天我们讨论的重点是获取到自然人定义的信息之后如何设计uv统计系统，并非是如何获取自然人的定义。uv系统的设计并非想象的那么简单，因为uv可能随着网站的营销策略会出现瞬间大流量，比如网站举办了一个秒杀活动。基于DB方案服务端编程有一句名言曰：没有一个表解决不了的功能，如果有那就两个表三个表。一个uv统计系统确实可以基于数据库来实现，而且也不复杂，uv统计的记录表可以类似如下（不要太纠结以下表设计是否合理）： 字段类型描述IPvarchar(30)客户端来源ipDayIDint时间的简写，例如 20190629其他字段int其他字段描述当一个请求到达服务器，服务端每次需要查询一次数据库是否有当前IP和当前时间的访问记录，如果有，则说明是同一个uv，如果没有，则说明是新的uv记录，插入数据库。当然以上两步也可以写到一个sql语句中： if exists( select 1 from table where ip='ip' and dayid=dayid )　Begin　return 0　Endelse　Begin insert into table .......　End所有基于数据库的解决方案，在数据量大的情况下几乎都更容易出现瓶颈。面对每天千万级别的uv统计，基于数据库的这种方案也许并不是最优的。 优化方案面对每一个系统的设计，我们都应该沉下心来思考具体的业务。至于uv统计这个业务有几个特点： 每次请求都需要判断是否已经存在相同的uv记录持久化uv数据不能影响正常的业务uv数据的准确性可以忍受一定程度的误差哈希表基于数据库的方案中，在大数据量的情况下，性能的瓶颈引发原因之一就是：判断是否已经存在相同记录，所以要优化这个系统，肯定首先是要优化这个步骤。根据菜菜以前的文章，是否可以想到解决这个问题的数据结构，对，就是哈希表。哈希表根据key来查找value的时间复杂度为O（1）常数级别，可以完美的解决查找相同记录的操作瓶颈。也许在uv数据量比较小的时候，哈希表也许是个不错的选择，但是面对千万级别的uv数据量，哈希表的哈希冲突和扩容，以及哈希表占用的内存也许并不是好的选择了。假设哈希表的每个key和value 占用10字节，1千万的uv数据大约占用 100M，对于现代计算机来说，100M其实不算大，但是有没有更好的方案呢？ 优化哈希表基于哈希表的方案，在千万级别数据量的情况下，只能算是勉强应付，如果是10亿的数据量呢？那有没有更好的办法搞定10亿级数据量的uv统计呢？这里抛开持久化数据，因为持久化设计到数据库的分表分库等优化策略了，咱们以后再谈。有没有更好的办法去快速判断在10亿级别的uv中某条记录是否存在呢？为了尽量缩小使用的内存，我们可以这样设计，可以预先分配bit类型的数组，数组的大小是统计的最大数据量的一个倍数，这个倍数可以自定义调整。现在假设系统的uv最大数据量为1千万，系统可以预先分配一个长度为5千万的bit数组，bit占用的内存最小，只占用一位。按照一个哈希冲突比较小的哈希函数计算每一个数据的哈希值，并设置bit数组相应哈希值位置的值为1。由于哈希函数都有冲突，有可能不同的数据会出现相同的哈希值，出现误判，但是我们可以用多个不同的哈希函数来计算同一个数据，来产生不同的哈希值，同时把这多个哈希值的数组位置都设置为1，从而大大减少了误判率，刚才新建的数组为最大数据量的一个倍数也是为了减小冲突的一种方式（容量越大，冲突越小）。当一个1千万的uv数据量级，5千万的bit数组占用内存才几十M而已，比哈希表要小很多，在10亿级别下内存占用差距将会更大。 以下为代码示例： class BloomFilter { BitArray container = null; public BloomFilter(int length) { container = new BitArray(length); } public void Set(string key) { var h1 = Hash1(key); var h2 = Hash2(key); var h3 = Hash3(key); var h4 = Hash4(key); container[h1] = true; container[h2] = true; container[h3] = true; container[h4] = true; } public bool Get(string key) { var h1 = Hash1(key); var h2 = Hash2(key); var h3 = Hash3(key); var h4 = Hash4(key); return container[h1] && container[h2] && container[h3] && container[h4]; } //模拟哈希函数1 int Hash1(string key) { int hash = 5381; int i; int count; char[] bitarray = key.ToCharArray(); count = bitarray.Length; while (count > 0) { hash += (hash << 5) + (bitarray[bitarray.Length - count]); count--; } return (hash & 0x7FFFFFFF) % container.Length; } int Hash2(string key) { int seed = 131; // 31 131 1313 13131 131313 etc.. int hash = 0; int count; char[] bitarray = (key+"key2").ToCharArray(); count = bitarray.Length; while (count > 0) { hash = hash * seed + (bitarray[bitarray.Length - count]); count--; } return (hash & 0x7FFFFFFF)% container.Length; } int Hash3(string key) { int hash = 0; int i; int count; char[] bitarray = (key + "keykey3").ToCharArray(); count = bitarray.Length; for (i = 0; i < count; i++) { if ((i & 1) == 0) { hash ^= ((hash << 7) ^ (bitarray[i]) ^ (hash >> 3)); } else { hash ^= (~((hash << 11) ^ (bitarray[i]) ^ (hash >> 5))); } count--; } return (hash & 0x7FFFFFFF) % container.Length; } int Hash4(string key) { int hash = 5381; int i; int count; char[] bitarray = (key + "keykeyke4").ToCharArray(); count = bitarray.Length; while (count > 0) { hash += (hash << 5) + (bitarray[bitarray.Length - count]); count--; } return (hash & 0x7FFFFFFF) % container.Length; } }测试程序为： ...

前言布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。而在Java中有个BitSet（位向量），我们可以基于BitSet实现一个简单实用的布隆过滤器。实现代码import java.util.BitSet;/** * 布隆过滤器 * @author RJH * create at 2019-03-25 /public class BloomFilter<T> { private BitSet data; public BloomFilter() { this.data = new BitSet(); } /* * 将元素加入到过滤器 * @param t / public void add(T t){ if(t==null){//为null时，索引为0 data.set(0); }else{ data.set(t.hashCode()); } } /* * 判断元素是否在过滤器中<br/> * @param t * @return true为存在，false为不存在 */ public boolean filter(T t){ if(t==null){//为null时，索引为0 return data.get(0); }else{ return data.get(t.hashCode()); } }}

前言最近有朋友问我这么一个面试题目：现在有一个非常庞大的数据，假设全是 int 类型。现在我给你一个数，你需要告诉我它是否存在其中(尽量高效)。需求其实很清晰，只是要判断一个数据是否存在即可。但这里有一个比较重要的前提：非常庞大的数据。常规实现先不考虑这个条件，我们脑海中出现的第一种方案是什么？我想大多数想到的都是用 HashMap 来存放数据，因为它的写入查询的效率都比较高。写入和判断元素是否存在都有对应的 API，所以实现起来也比较简单。为此我写了一个单测，利用 HashSet 来存数据（底层也是 HashMap ）；同时为了后面的对比将堆内存写死：-Xms64m -Xmx64m -XX:+PrintHeapAtGC -XX:+HeapDumpOnOutOfMemoryError 为了方便调试加入了 GC 日志的打印，以及内存溢出后 Dump 内存。 @Test public void hashMapTest(){ long star = System.currentTimeMillis(); Set<Integer> hashset = new HashSet<>(100) ; for (int i = 0; i < 100; i++) { hashset.add(i) ; } Assert.assertTrue(hashset.contains(1)); Assert.assertTrue(hashset.contains(2)); Assert.assertTrue(hashset.contains(3)); long end = System.currentTimeMillis(); System.out.println(“执行时间：” + (end - star)); }当我只写入 100 条数据时自然是没有问题的。还是在这个基础上，写入 1000W 数据试试：执行后马上就内存溢出。可见在内存有限的情况下我们不能使用这种方式。实际情况也是如此；既然要判断一个数据是否存在于集合中，考虑的算法的效率以及准确性肯定是要把数据全部 load 到内存中的。Bloom Filter基于上面分析的条件，要实现这个需求最需要解决的是如何将庞大的数据 load 到内存中。而我们是否可以换种思路，因为只是需要判断数据是否存在，也不是需要把数据查询出来，所以完全没有必要将真正的数据存放进去。伟大的科学家们已经帮我们想到了这样的需求。Burton Howard Bloom 在 1970 年提出了一个叫做 Bloom Filter（中文翻译：布隆过滤）的算法。它主要就是用于解决判断一个元素是否在一个集合中，但它的优势是只需要占用很小的内存空间以及有着高效的查询效率。所以在这个场景下在合适不过了。Bloom Filter 原理下面来分析下它的实现原理。官方的说法是：它是一个保存了很长的二级制向量，同时结合 Hash 函数实现的。听起来比较绕，但是通过一个图就比较容易理解了。如图所示：首先需要初始化一个二进制的数组，长度设为 L（图中为 8），同时初始值全为 0 。当写入一个 A1=1000 的数据时，需要进行 H 次 hash 函数的运算（这里为 2 次）；与 HashMap 有点类似，通过算出的 HashCode 与 L 取模后定位到 0、2 处，将该处的值设为 1。A2=2000 也是同理计算后将 4、7 位置设为 1。当有一个 B1=1000 需要判断是否存在时，也是做两次 Hash 运算，定位到 0、2 处，此时他们的值都为 1 ，所以认为 B1=1000 存在于集合中。当有一个 B2=3000 时，也是同理。第一次 Hash 定位到 index=4 时，数组中的值为 1，所以再进行第二次 Hash 运算，结果定位到 index=5 的值为 0，所以认为 B2=3000 不存在于集合中。整个的写入、查询的流程就是这样，汇总起来就是：对写入的数据做 H 次 hash 运算定位到数组中的位置，同时将数据改为 1 。当有数据查询时也是同样的方式定位到数组中。一旦其中的有一位为 0 则认为数据肯定不存在于集合，否则数据可能存在于集合中。所以布隆过滤有以下几个特点：只要返回数据不存在，则肯定不存在。返回数据存在，但只能是大概率存在。同时不能清除其中的数据。第一点应该都能理解，重点解释下 2、3 点。为什么返回存在的数据却是可能存在呢，这其实也和 HashMap 类似。在有限的数组长度中存放大量的数据，即便是再完美的 Hash 算法也会有冲突，所以有可能两个完全不同的 A、B 两个数据最后定位到的位置是一模一样的。这时拿 B 进行查询时那自然就是误报了。删除数据也是同理，当我把 B 的数据删除时，其实也相当于是把 A 的数据删掉了，这样也会造成后续的误报。基于以上的 Hash 冲突的前提，所以 Bloom Filter 有一定的误报率，这个误报率和 Hash 算法的次数 H，以及数组长度 L 都是有关的。自己实现一个布隆过滤算法其实很简单不难理解，于是利用 Java 实现了一个简单的雏形。public class BloomFilters { /** * 数组长度 / private int arraySize; /* * 数组 / private int[] array; public BloomFilters(int arraySize) { this.arraySize = arraySize; array = new int[arraySize]; } /* * 写入数据 * @param key / public void add(String key) { int first = hashcode_1(key); int second = hashcode_2(key); int third = hashcode_3(key); array[first % arraySize] = 1; array[second % arraySize] = 1; array[third % arraySize] = 1; } /* * 判断数据是否存在 * @param key * @return / public boolean check(String key) { int first = hashcode_1(key); int second = hashcode_2(key); int third = hashcode_3(key); int firstIndex = array[first % arraySize]; if (firstIndex == 0) { return false; } int secondIndex = array[second % arraySize]; if (secondIndex == 0) { return false; } int thirdIndex = array[third % arraySize]; if (thirdIndex == 0) { return false; } return true; } /* * hash 算法1 * @param key * @return / private int hashcode_1(String key) { int hash = 0; int i; for (i = 0; i < key.length(); ++i) { hash = 33 * hash + key.charAt(i); } return Math.abs(hash); } /* * hash 算法2 * @param data * @return / private int hashcode_2(String data) { final int p = 16777619; int hash = (int) 2166136261L; for (int i = 0; i < data.length(); i++) { hash = (hash ^ data.charAt(i)) * p; } hash += hash << 13; hash ^= hash >> 7; hash += hash << 3; hash ^= hash >> 17; hash += hash << 5; return Math.abs(hash); } /* * hash 算法3 * @param key * @return */ private int hashcode_3(String key) { int hash, i; for (hash = 0, i = 0; i < key.length(); ++i) { hash += key.charAt(i); hash += (hash << 10); hash ^= (hash >> 6); } hash += (hash << 3); hash ^= (hash >> 11); hash += (hash << 15); return Math.abs(hash); }}首先初始化了一个 int 数组。写入数据的时候进行三次 hash 运算，同时把对应的位置置为 1。查询时同样的三次 hash 运算，取到对应的值，一旦值为 0 ，则认为数据不存在。实现逻辑其实就和上文描述的一样。下面来测试一下，同样的参数：-Xms64m -Xmx64m -XX:+PrintHeapAtGC @Test public void bloomFilterTest(){ long star = System.currentTimeMillis(); BloomFilters bloomFilters = new BloomFilters(10000000) ; for (int i = 0; i < 10000000; i++) { bloomFilters.add(i + “”) ; } Assert.assertTrue(bloomFilters.check(1+"")); Assert.assertTrue(bloomFilters.check(2+"")); Assert.assertTrue(bloomFilters.check(3+"")); Assert.assertTrue(bloomFilters.check(999999+"")); Assert.assertFalse(bloomFilters.check(400230340+"")); long end = System.currentTimeMillis(); System.out.println(“执行时间：” + (end - star)); }执行结果如下：只花了 3 秒钟就写入了 1000W 的数据同时做出来准确的判断。当让我把数组长度缩小到了 100W 时就出现了一个误报，400230340 这个数明明没在集合里，却返回了存在。这也体现了 Bloom Filter 的误报率。我们提高数组长度以及 hash 计算次数可以降低误报率，但相应的 CPU、内存的消耗就会提高；这就需要根据业务需要自行权衡。Guava 实现刚才的方式虽然实现了功能，也满足了大量数据。但其实观察 GC 日志非常频繁，同时老年代也使用了 90%，接近崩溃的边缘。总的来说就是内存利用率做的不好。其实 Google Guava 库中也实现了该算法，下面来看看业界权威的实现。-Xms64m -Xmx64m -XX:+PrintHeapAtGC @Test public void guavaTest() { long star = System.currentTimeMillis(); BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 10000000, 0.01); for (int i = 0; i < 10000000; i++) { filter.put(i); } Assert.assertTrue(filter.mightContain(1)); Assert.assertTrue(filter.mightContain(2)); Assert.assertTrue(filter.mightContain(3)); Assert.assertFalse(filter.mightContain(10000000)); long end = System.currentTimeMillis(); System.out.println(“执行时间：” + (end - star)); }也是同样写入了 1000W 的数据，执行没有问题。观察 GC 日志会发现没有一次 fullGC，同时老年代的使用率很低。和刚才的一对比这里明显的要好上很多，也可以写入更多的数据。源码分析那就来看看 Guava 它是如何实现的。构造方法中有两个比较重要的参数，一个是预计存放多少数据，一个是可以接受的误报率。我这里的测试 demo 分别是 1000W 以及 0.01。Guava 会通过你预计的数量以及误报率帮你计算出你应当会使用的数组大小 numBits 以及需要计算几次 Hash 函数 numHashFunctions 。这个算法计算规则可以参考维基百科。put 写入函数真正存放数据的 put 函数如下：根据 murmur3_128 方法的到一个 128 位长度的 byte[]。分别取高低 8 位的到两个 hash 值。再根据初始化时的到的执行 hash 的次数进行 hash 运算。bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);其实也是 hash取模拿到 index 后去赋值 1.重点是 bits.set() 方法。其实 set 方法是 BitArray 中的一个函数，BitArray 就是真正存放数据的底层数据结构。利用了一个 long[] data 来存放数据。所以 set() 时候也是对这个 data 做处理。在 set 之前先通过 get() 判断这个数据是否存在于集合中，如果已经存在则直接返回告知客户端写入失败。接下来就是通过位运算进行位或赋值。get() 方法的计算逻辑和 set 类似，只要判断为 0 就直接返回存在该值。mightContain 是否存在函数前面几步的逻辑都是类似的，只是调用了刚才的 get() 方法判断元素是否存在而已。总结布隆过滤的应用还是蛮多的，比如数据库、爬虫、防缓存击穿等。特别是需要精确知道某个数据不存在时做点什么事情就非常适合布隆过滤。这段时间的研究发现算法也挺有意思的，后续应该会继续分享一些类似的内容。如果对你有帮助那就分享一下吧。本问的示例代码参考这里：https://github.com/crossoverJie/JCSprout你的点赞与分享是对我最大的支持 ...