面试题:海量数据处理利器(关于海量数据处理分析的经验总结)

  本篇文章为你整理了面试题:海量数据处理利器(关于海量数据处理分析的经验总结)的详细内容,包含有海量数据的处理 关于海量数据处理分析的经验总结 海量数据解决方案 海量数据处理与大数据技术实战 面试题:海量数据处理利器,希望能帮助你了解 面试题:海量数据处理利器。

  目录概念原理布隆过滤器的使用场景简单模拟布隆过滤器Guava布隆过滤器Redis布隆过滤器布谷鸟过滤器

  作者:小牛呼噜噜 https://xiaoniuhululu.com
 

  计算机内功、JAVA底层、面试相关资料等更多精彩文章在公众号「小牛呼噜噜 」

  通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间也会呈现线性增长,最终达到瓶颈。同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为O(n), O(logn), O(1)。这个时候,布隆过滤器就应运而生。
 

  布隆过滤器(Bloom Filter)是1970年由布隆提出的。布隆过滤器其实就是一个很长的二进制向量和一系列随机映射函数。可以用于快速检索一个元素是否在一个集合中出现的方法。

  如果想判断一个元素是不是在一个集合里,我们一般想到的是将所有元素保存起来,然后通过比较确定。我们熟悉的链表,树等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间越来越大,检索速度也越来越慢。不过世界上还有一种叫作散列表(又叫哈希表)的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列中的一个点。这样一来,我们只要看看这个点是不是 1 就知道可以集合中有没有它了。这其实就是布隆过滤器的基本思想。

  Hash算法面临的问题就是hash冲突。假设 Hash 函数是良好的,如果我们的位阵列长度为 m 个点,那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳 m/100 个元素。显然这就不叫空间有效了(Space-efficient)。解决方法:就是使用多个 Hash算法,如果它们有一个说元素不在集合中,那肯定就不在。如果它们都说在,有一定可能性它们在说谎,虽然概率比较低。

  算法:

  首先需要k个hash函数,每个函数可以把key散列成为1个整数

  初始化时,需要一个长度为n比特的数组,每个比特位初始化为0

  某个key加入集合时,用k个hash函数计算出k个散列值,并把数组中对应的比特位置为1

  判断某个key是否在集合时,用k个hash函数计算出k个散列值,并查询数组中对应的比特位,如果所有的比特位都是1,认为在集合中。

  其优点:

  空间效率和查询时间都比一般的算法要好的多,比如增加和查询元素的时间复杂为O(N)

  由于不需要存储key,所以特别节省存储空间。

  保密性强,布隆过滤器不存储元素本身~~

  其缺点:

  由于采用hash算法,可能出现hash冲突,导致有一定的误判率,但是可以通过调整参数来降低

  
布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了,这样就无法判断究竟是哪个输入产生的,因此误判的根源在于相同的 bit 位被多次映射且置 1。

  
无法获取元素本身

  由于hash算法导致hash冲突必然存在,所以删除元素是很困难的,而且删掉元素会导致误判率增加。

  布隆过滤器的使用场景

  我们可以充分利用布隆过滤器的特点:如果布隆过滤器说有一个说元素不在集合中,那肯定就不在。如果布隆过滤器说在,有一定可能性它在说谎。

  比较热门的场景就是:解决Redis缓存穿透问题

  
缓存穿透: 指用户的请求去查询缓存和数据库中都不存在的数据,可用户还是源源不断的发起请求,导致每次请求都会打到数据库上,从而压垮数据库

  
邮件过滤,使用布隆过滤器来做邮件黑名单过滤,还有重复推荐内容过滤,网址过滤, web请求访问拦截器,等等

  许多数据库内置布隆过滤器,用于判断数据是否存在,可以减少数据库很多不必要的磁盘IO操作

  简单模拟布隆过滤器

  我们来看一个例子:

  

public class MyBloomFilter {

 

   * 一个长度为10 亿的比特位

   private static final int DEFAULT_SIZE = 256 22;

   * 为了降低错误率,使用加法hash算法,所以定义一个8个元素的质数数组

   private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};

   * 相当于构建 8 个不同的hash算法

   private static HashFunction[] functions = new HashFunction[seeds.length];

   * 初始化布隆过滤器的 bitmap

   private static BitSet bitset = new BitSet(DEFAULT_SIZE);

   * 添加数据

   * @param value 需要加入的值

   public static void add(String value) {

   if (value != null) {

   for (HashFunction f : functions) {

   //计算 hash 值并修改 bitmap 中相应位置为 true

   bitset.set(f.hash(value), true);

   * 判断相应元素是否存在

   * @param value 需要判断的元素

   * @return 结果

   public static boolean contains(String value) {

   if (value == null) {

   return false;

   boolean ret = true;

   for (HashFunction f : functions) {

   ret = bitset.get(f.hash(value));

   //一个 hash 函数返回 false 则跳出循环

   if (!ret) {

   break;

   return ret;

   * 模拟用户在不在线。。。

   public static void main(String[] args) {

   for (int i = 0; i seeds.length; i++) {

   functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);

   // 添加1亿数据

   for (int i = 0; i 100000000; i++) {

   add(String.valueOf(i));

   String id = "123456789";

   add(id);

   System.out.println(contains(id)); //结果: true

   System.out.println("" + contains("234567890")); //结果: false

  class HashFunction {

   private int size;

   private int seed;

   public HashFunction(int size, int seed) {

   this.size = size;

   this.seed = seed;

   public int hash(String value) {

   int result = 0;

   int len = value.length();

   for (int i = 0; i len; i++) {

   result = seed * result + value.charAt(i);

   int r = (size - 1) result;

   return (size - 1) result;

  

 

  我们平时学习的时候可以去实现一下算法,但实际开发过程中,一般不推荐重复造轮子,简单的实现布隆过滤器, 我们一般可以用google.guava库

  Guava布隆过滤器

  首先引入依赖:

  

 dependency 

 

   groupId com.google.guava /groupId

   artifactId guava /artifactId

   version 28.0-jre /version

   /dependency

  

 

  举个例子:

  

// 创建布隆过滤器对象,预计包含的数据量:2000个,和允许的误差值0.01

 

  BloomFilter Integer filter = BloomFilter.create(

   Funnels.integerFunnel(),

   2000,

   0.01);

  System.out.println(filter.mightContain(10));// 判断指定元素是否存在

  System.out.println(filter.mightContain(20));

  filter.put(10);// 将元素添加进布隆过滤器

  filter.put(20);

  System.out.println(filter.mightContain(10));// 判断指定元素是否存在

  System.out.println(filter.mightContain(20));

  

 

  其中:当mightContain()方法返回_true_时,我们可以大概率确定该元素在过滤器中,但当过滤器返回_false_时,我们可以100%确定该元素不存在于过滤器中。
 

  布隆过滤器的 允许的误差值 越小,需要的存储空间就越大,对于不需要过于精确的场景,允许的误差值 设置稍大一点也可以。
 

  Guava 提供的布隆过滤器的实现还是很不错的,但是随着微服务、分布式的不断发展,对于微服务多实例的场景下就不太适用了,只适合单机,解决方案是:一般是借助Redis中的布隆过滤器

  Redis布隆过滤器

  Redis 4.0 的时候官方提供了插件机制,布隆过滤器正式登场。以下网站可以下载官方提供的已经编译好的可拓展模块。
 

  https://redis.com/redis-enterprise-software/download-center/modules

  这边使用docker安装,自己挑选合适的镜像

  

~ docker pull redislabs/rebloom:latest

 

  ~ docker run -p 6379:6379 --name redis-bloom redislabs/rebloom:latest

  ~ docker exec -it redis-bloom bash

  root@113d012d35:/data# redis-cli

  127.0.0.1:6379

  

 

  进入容器内部后,常用的命令:

  

//-------------------------常用命令

 

  BF.ADD --添加一个元素到布隆过滤器

  BF.EXISTS --判断元素是否在布隆过滤器

  BF.MADD --添加多个元素到布隆过滤器

  BF.MEXISTS --判断多个元素是否在布隆过滤器

  //-------------------------具体操作

  127.0.0.1:6379 BF.ADD myFilter hello

  (integer) 1

  127.0.0.1:6379 BF.ADD myFilter people

  (integer) 1

  127.0.0.1:6379 BF.EXISTS myFilter hello

  (integer) 1

  127.0.0.1:6379 BF.EXISTS myFilter people

  (integer) 1

  127.0.0.1:6379 BF.EXISTS myFilter github

  (integer) 0

  

 

  布谷鸟过滤器

  为了解决布隆过滤器不能删除元素的问题,布谷鸟过滤器应运而生。论文《Cuckoo Filter:Better Than Bloom》作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。但是其删除并不完美,存在误删的概率,还存在插入复杂度比较高等问题。由于使用较少,本文就不过多介绍了,感兴趣的自行了解文章。

  参考资料:
 

  https:///feily/articles/14048396.html
 

  https:///liyulong1982/p/6013002.html

  本篇文章到这里就结束啦,很感谢你能看到最后,如果觉得文章对你有帮助,别忘记关注我!更多精彩的文章
 

  以上就是面试题:海量数据处理利器(关于海量数据处理分析的经验总结)的详细内容,想要了解更多 面试题:海量数据处理利器的内容,请持续关注盛行IT软件开发工作室。

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: