详解布隆过滤器,实现分布式布隆过滤器

2024-06-03 19:52

本文主要是介绍详解布隆过滤器,实现分布式布隆过滤器,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

什么是布隆过滤器?

原理

布隆过滤器是一种基于位数组(bit array)和多个哈希函数的数据结构。其核心原理是:

  1. 初始化一个长度为m的位数组,所有位初始化为0。
  2. 使用k个不同的哈希函数将元素映射到位数组中的k个位置。
  3. 当插入一个元素时,使用k个哈希函数计算该元素的k个哈希值,并将位数组中对应位置的值设为1。
  4. 当查询一个元素是否存在时,使用同样的k个哈希函数计算该元素的k个哈希值,并检查位数组中对应位置的值是否都为1。如果有一个位置的值为0,则该元素肯定不在集合中;如果所有位置的值都为1,则该元素可能在集合中。  

优点

  1. 空间效率高:布隆过滤器通过使用位数组和哈希函数,可以在相对较小的空间内表示一个大型集合。这使得它特别适合内存受限的应用场景。

  2. 插入和查询速度快:插入和查询操作都只需要O(k)的时间复杂度(k为哈希函数的数量),非常高效。哈希函数的计算和位数组的访问都可以在常数时间内完成。

  3. 无需存储实际元素:布隆过滤器只需要存储哈希值,并不需要存储实际的元素数据,因此它能有效地节省存储空间。

  4. 适用于分布式系统:布隆过滤器可以轻松地分布在多个节点上,通过分布式哈希算法进行管理,适用于大规模分布式系统。

  5. 扩展性好:一些扩展版本的布隆过滤器,如可扩展布隆过滤器(Scalable Bloom Filter),可以动态调整大小,适应不断增长的数据集。

缺点

  1. 存在误判率:布隆过滤器有一定的误判率,即可能会误判一个不在集合中的元素为存在。误判率取决于位数组的大小、哈希函数的数量和存储的元素数量。这是由于哈希冲突产生的。

  2. 无法删除元素:基本布隆过滤器不支持删除操作,因为无法确定一个位置上的1是由哪个元素设置的。虽然计数布隆过滤器(Counting Bloom Filter)可以支持删除操作,但代价是需要更多的空间。

  3. 初始化参数选择复杂:选择合适的位数组大小和哈希函数数量是一个复杂的问题。位数组太小或哈希函数数量太少会增加误判率,而位数组太大或哈希函数数量太多则会浪费空间和时间。

  4. 不适用于动态集:基本布隆过滤器在初始化时需要确定位数组的大小,这对于元素数量动态变化的场景并不友好。可扩展布隆过滤器虽然可以动态调整大小,但实现较为复杂。

  5. 不支持元素的完整存储和检索:布隆过滤器只能判断元素是否存在于集合中,无法存储和检索元素的实际内容。

应用场景

布隆过滤器在很多应用场景中都有广泛的应用:

  1. 缓存系统:在缓存系统中,布隆过滤器可以用来快速判断一个请求是否命中缓存,避免不必要的数据库查询,解决缓存穿透问题。

  2. 垃圾邮件过滤:邮件系统可以使用布隆过滤器来快速判断一封邮件是否是垃圾邮件。

  3. 网络爬虫:在网络爬虫中,布隆过滤器可以用来记录已经访问过的URL,避免重复抓取。

  4. 数据库去重:在大规模数据处理中,布隆过滤器可以用来快速判断一个记录是否已经存在,避免重复存储。

  5. 分布式系统:在分布式系统中,布隆过滤器可以用来快速判断一个数据是否存在于某个节点上,提高查询效率。

布隆过滤器的实现

常用的几种有单体项目下,使用Guava包下的BloomFilter,分布式下使用Redission的RBloomFilter,这些都是写好的布隆过滤器,接下来将基于redis和jedis实现一个手写的分布式布隆过滤器

分布式布隆过滤器的实现

分布式布隆过滤器在大规模分布式系统中应用广泛,它的实现主要涉及以下几个方面:

  1. 位数组的分布:将位数组分布在多个节点上,每个节点存储部分位数组。
  2. 哈希函数:使用多个哈希函数来保证均匀分布。
  3. 一致性哈希:用来管理节点和数据之间的映射关系,保证负载均衡和容错。

分布式哈希算法

一致性哈希是一种用于分布式系统的哈希算法,能够有效地应对节点动态加入和退出的情况。它通过将所有节点和数据哈希到一个环上来实现数据的分布。主要包含以下步骤:

  1. 哈希环:将整个哈希空间组织成一个环,环的大小通常是哈希函数的输出范围。
  2. 节点哈希:将每个节点通过哈希函数映射到环上的一个点。
  3. 数据哈希:将每个数据通过相同的哈希函数映射到环上的一个点。
  4. 数据存储:数据存储在顺时针方向遇到的第一个节点上。
  5. 节点变动处理
    • 节点加入:重新分配一部分数据给新节点。
    • 节点退出:将其数据重新分配给其他节点。

分布式布隆过滤器的实现

下面是用Java和Jedis实现的分布式布隆过滤器示例。我们使用一致性哈希来分配数据,并用Redis存储位数组。

1. 一致性哈希实现

import java.util.SortedMap;
import java.util.TreeMap;public class ConsistentHashing {private final SortedMap<Integer, String> circle = new TreeMap<>();private final int replicas;public ConsistentHashing(int replicas) {this.replicas = replicas;}public void addNode(String node) {for (int i = 0; i < replicas; i++) {circle.put((node + i).hashCode(), node);}}public void removeNode(String node) {for (int i = 0; i < replicas; i++) {circle.remove((node + i).hashCode());}}public String getNode(String key) {if (circle.isEmpty()) {return null;}int hash = key.hashCode();if (!circle.containsKey(hash)) {SortedMap<Integer, String> tailMap = circle.tailMap(hash);hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();}return circle.get(hash);}
}

2. 分布式布隆过滤器实现 

import redis.clients.jedis.Jedis;
import java.nio.charset.StandardCharsets;
import com.google.common.hash.Hashing;public class DistributedBloomFilter {private ConsistentHashing consistentHashing;private int size;private int numHashFunctions;public DistributedBloomFilter(int replicas, int size, int numHashFunctions) {this.consistentHashing = new ConsistentHashing(replicas);this.size = size;this.numHashFunctions = numHashFunctions;}public void addNode(String host, int port) {consistentHashing.addNode(host + ":" + port);}public void removeNode(String host, int port) {consistentHashing.removeNode(host + ":" + port);}private static int[] getHashes(String value, int numHashes, int maxSize) {int[] hashes = new int[numHashes];for (int i = 0; i < numHashes; i++) {hashes[i] = Math.abs(Hashing.murmur3_128(i).hashString(value, StandardCharsets.UTF_8).asInt() % maxSize);}return hashes;}private Jedis getJedisClient(String value) {// 使用一致性哈希算法找到合适的节点String node = consistentHashing.getNode(value);// 解析节点信息并创建Jedis客户端实例String[] parts = node.split(":");return new Jedis(parts[0], Integer.parseInt(parts[1]));}public void add(String value) {// 计算哈希值int[] hashes = getHashes(value, numHashFunctions, size);try (Jedis jedis = getJedisClient(value)) {// 设置位数组的对应位置for (int hash : hashes) {jedis.setbit("bloom_filter", hash, true);}}}public boolean contains(String value) {// 计算哈希值int[] hashes = getHashes(value, numHashFunctions, size);try (Jedis jedis = getJedisClient(value)) {// 查询位数组的对应位置for (int hash : hashes) {if (!jedis.getbit("bloom_filter", hash)) {return false;}}}return true;}public static void main(String[] args) {// 创建布隆过滤器实例DistributedBloomFilter bloomFilter = new DistributedBloomFilter(3, 1000, 5);// 添加Redis节点bloomFilter.addNode("localhost", 6379);bloomFilter.addNode("localhost", 6380);bloomFilter.addNode("localhost", 6381);// 插入元素bloomFilter.add("apple");bloomFilter.add("banana");// 查询元素System.out.println(bloomFilter.contains("apple"));  // 输出: trueSystem.out.println(bloomFilter.contains("banana")); // 输出: trueSystem.out.println(bloomFilter.contains("cherry")); // 输出: false}
}

这篇关于详解布隆过滤器,实现分布式布隆过滤器的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1027951

相关文章

使用Python实现网页表格转换为markdown

《使用Python实现网页表格转换为markdown》在日常工作中,我们经常需要从网页上复制表格数据,并将其转换成Markdown格式,本文将使用Python编写一个网页表格转Markdown工具,需... 在日常工作中,我们经常需要从网页上复制表格数据,并将其转换成Markdown格式,以便在文档、邮件或

Python使用pynput模拟实现键盘自动输入工具

《Python使用pynput模拟实现键盘自动输入工具》在日常办公和软件开发中,我们经常需要处理大量重复的文本输入工作,所以本文就来和大家介绍一款使用Python的PyQt5库结合pynput键盘控制... 目录概述:当自动化遇上可视化功能全景图核心功能矩阵技术栈深度效果展示使用教程四步操作指南核心代码解析

SpringBoot实现文件记录日志及日志文件自动归档和压缩

《SpringBoot实现文件记录日志及日志文件自动归档和压缩》Logback是Java日志框架,通过Logger收集日志并经Appender输出至控制台、文件等,SpringBoot配置logbac... 目录1、什么是Logback2、SpringBoot实现文件记录日志,日志文件自动归档和压缩2.1、

Python实现pdf电子发票信息提取到excel表格

《Python实现pdf电子发票信息提取到excel表格》这篇文章主要为大家详细介绍了如何使用Python实现pdf电子发票信息提取并保存到excel表格,文中的示例代码讲解详细,感兴趣的小伙伴可以跟... 目录应用场景详细代码步骤总结优化应用场景电子发票信息提取系统主要应用于以下场景:企业财务部门:需

基于Python实现智能天气提醒助手

《基于Python实现智能天气提醒助手》这篇文章主要来和大家分享一个实用的Python天气提醒助手开发方案,这个工具可以方便地集成到青龙面板或其他调度框架中使用,有需要的小伙伴可以参考一下... 目录项目概述核心功能技术实现1. 天气API集成2. AI建议生成3. 消息推送环境配置使用方法完整代码项目特点

spring-gateway filters添加自定义过滤器实现流程分析(可插拔)

《spring-gatewayfilters添加自定义过滤器实现流程分析(可插拔)》:本文主要介绍spring-gatewayfilters添加自定义过滤器实现流程分析(可插拔),本文通过实例图... 目录需求背景需求拆解设计流程及作用域逻辑处理代码逻辑需求背景公司要求,通过公司网络代理访问的请求需要做请

使用Python获取JS加载的数据的多种实现方法

《使用Python获取JS加载的数据的多种实现方法》在当今的互联网时代,网页数据的动态加载已经成为一种常见的技术手段,许多现代网站通过JavaScript(JS)动态加载内容,这使得传统的静态网页爬取... 目录引言一、动态 网页与js加载数据的原理二、python爬取JS加载数据的方法(一)分析网络请求1

Spring Security介绍及配置实现代码

《SpringSecurity介绍及配置实现代码》SpringSecurity是一个功能强大的Java安全框架,它提供了全面的安全认证(Authentication)和授权(Authorizatio... 目录简介Spring Security配置配置实现代码简介Spring Security是一个功能强

SpringCloud使用Nacos 配置中心实现配置自动刷新功能使用

《SpringCloud使用Nacos配置中心实现配置自动刷新功能使用》SpringCloud项目中使用Nacos作为配置中心可以方便开发及运维人员随时查看配置信息,及配置共享,并且Nacos支持配... 目录前言一、Nacos中集中配置方式?二、使用步骤1.使用$Value 注解2.使用@Configur

Python+PyQt5实现MySQL数据库备份神器

《Python+PyQt5实现MySQL数据库备份神器》在数据库管理工作中,定期备份是确保数据安全的重要措施,本文将介绍如何使用Python+PyQt5开发一个高颜值,多功能的MySQL数据库备份工具... 目录概述功能特性核心功能矩阵特色功能界面展示主界面设计动态效果演示使用教程环境准备操作流程代码深度解