当前位置: 首页 > news >正文

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

什么是布隆过滤器?

原理

布隆过滤器是一种基于位数组(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}
}

相关文章:

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

什么是布隆过滤器&#xff1f; 原理 布隆过滤器是一种基于位数组&#xff08;bit array&#xff09;和多个哈希函数的数据结构。其核心原理是&#xff1a; 初始化一个长度为m的位数组&#xff0c;所有位初始化为0。使用k个不同的哈希函数将元素映射到位数组中的k个位置。当插…...

程序员职业素养:AI新时代下的机遇与挑战

目录 一、引言二、程序员职业素养的五大要点1. 技术能力2. 沟通能力3. 团队合作4. 责任心5. 敬业精神 三、实际案例解析四、程序员职业素养在实际工作中的应用五、AI新时代的程序员的职业发展建议六、总结七、结语 一、引言 在当今这个科技飞速发展的时代&#xff0c;程序员这…...

智能管理,无忧报修——高校校园报事报修系统小程序全解析

随着数字化、智能化的发展&#xff0c;高校生活也迎来了前所未有的变革。你是否还在为宿舍的水龙头漏水、图书馆的灯光闪烁而烦恼&#xff1f;你是否还在为报修流程繁琐、等待时间长而焦虑&#xff1f;今天&#xff0c;这一切都将成为过去式&#xff01;因为一款震撼高校圈的新…...

nc解决自定义参照字段前台保存后只显示主键的问题

nc解决自定义参照字段前台保存后只显示主键的问题 自定义参照类VoucherRefModel.java package nc.ui.jych.ref;import nc.ui.bd.ref.AbstractRefModel;/*** desc 凭证号参照* author hanh**/ public class VoucherRefModel extends AbstractRefModel {Overridepublic String[…...

鸿蒙全栈开发-一文读懂鸿蒙同模块不同模块下的UIAbility跳转详解

前言 根据第三方机构Counterpoint数据&#xff0c;截至2023年三季度末&#xff0c;HarmonyOS在中国智能手机操作系统的市场份额已经提升至13%。短短四年的时间&#xff0c;HarmonyOS就成长为仅次于安卓、苹果iOS的全球第三大操作系统。 因此&#xff0c;对于鸿蒙生态建设而言&a…...

【Python】使用 SQLObject orm 库快速将接口数据存入数据库

使用 SQLObject orm 库快速将接口数据存入数据库 文章目录 使用 SQLObject orm 库快速将接口数据存入数据库背景orm python 版本都有哪些&#xff1f; SQLObject 简单的使用 背景 因为测试需要&#xff0c;要将百万条数据接口查询数据存入数据库中&#xff0c;为了减少 mysql …...

@EnableResourceServer资源服务注解源码分析

文章目录 学习参考EnableResourceServer概要ResourceServerConfiguration属性定义configure(HttpSecurity)ResourceServerSecurityConfigurerinit(HttpSecurit)configure(HttpSecurity) 学习参考 Spring Security框架配置运行流程完整分析 - 【必看】 Security OAuth2 授权 &…...

SpringBoot实现图片文件上传和回显的两种方式

目录 一 功能需求 二 上传本地 2.1 实现文件上传的controller层 2.2 图片访问资源映射 二 上传OSS 一 功能需求 实现图片的上传和回显功能其实在业务中是非常常见的&#xff0c;比如需要上传头像&#xff0c;或者交易平台需要上传物品的图片等等&#xff0c;都需要上传和回…...

进程和计划任务以及步骤

进程 进程和程序有关&#xff0c;把该文件放到内存里&#xff0c;进程是动态的&#xff0c;不同时刻的状态不一样 内存&#xff1a;放置正在运行的程序和所需数据的位置 程序启动 ——》将相关文件和数据放到内存里 ——》进程&#xff08;processes&#xff09; 进程相关命令 …...

使用Python实现深度学习模型:序列到序列模型(Seq2Seq)

序列到序列&#xff08;Seq2Seq&#xff09;模型是一种深度学习模型&#xff0c;广泛应用于机器翻译、文本生成和对话系统等自然语言处理任务。它的核心思想是将一个序列&#xff08;如一句话&#xff09;映射到另一个序列。本文将详细介绍 Seq2Seq 模型的原理&#xff0c;并使…...

力扣283. 移动零

给定一个数组 nums&#xff0c;编写一个函数将所有 0 移动到数组的末尾&#xff0c;同时保持非零元素的相对顺序。 请注意 &#xff0c;必须在不复制数组的情况下原地对数组进行操作。 示例 1: 输入: nums [0,1,0,3,12] 输出:[1,3,12,0,0] 示例 2: 输入: nums [0] …...

二叉树的顺序结构(堆的实现)

前言 普通的二叉树是不适合用数组来存储的&#xff0c;因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结 构存储。 现实中我们通常把堆 ( 一种二叉树 ) 使用顺序结构的数组来存储&#xff0c;需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事&…...

2024大模型如何学习【附学习资料】

摘要&#xff1a; 通过深入了解本文中的这些细节&#xff0c;并在实际项目中应用相关知识&#xff0c;将能够更好地理解和利用大模型的潜力&#xff0c;不仅在学术研究中&#xff0c;也在工程实践中。通过不断探索新方法、参与项目和保持热情&#xff0c;并将其应用于各种领域&…...

计算机组成原理·考点知识点整理

根据往年考试题&#xff0c;对考点和知识点的一个整理。 校验编码 码距 一种编码的最小码距&#xff0c;其实就是指这种编码的码距。码距有两种定义&#xff1a; 码距所描述的对象含义 2 2 2 个特定的码其二进制表示中不同位的个数一种编码这种编码中任意 2 2 2 个合法编码的…...

python-datetime模块时间戳常用方法汇总

文章目录 datetime模块常用方法1、导入模块2、获取当前日期和时间3、获取当前日期4、创建特定日期或时间5、日期和时间的运算6、使用timedelta运算日期时间创建 timedelta 对象timedelta 的加减运算timedelta 的属性timedelta 的比较示例代码格式化日期和时间获取日期和时间的各…...

【Python报错】已解决ModuleNotFoundError: No module named ‘timm’

成功解决“ModuleNotFoundError: No module named ‘timm’”错误的全面指南 一、引言 在Python编程中&#xff0c;经常会遇到各种导入模块的错误&#xff0c;其中“ModuleNotFoundError: No module named ‘timm’”就是一个典型的例子。这个错误意味着你的Python环境中没有安…...

【设计模式】适配器模式(结构型)⭐⭐⭐

文章目录 1.概念1.1 什么是适配器模式1.2 优点与缺点 2.实现方式2.1 类适配器模式2.2 对象适配器模式 3 Java 哪些地方用到了适配器模式4 Spring 哪些地方用到了适配器模式 1.概念 1.1 什么是适配器模式 简单来说&#xff0c;适配器模式就是作为两个不兼容接口之间的桥梁。 1.…...

云原生周刊:Gateway API v1.1 发布 | 2024.6.3

开源项目推荐 Grafana Tanka Tanka 是 Grafana 开发的一款用于 Kubernetes 的灵活、可重用和简洁的配置工具,是使用 YAML 进行 Kubernetes 配置的一种替代方案。 pv-migrate pv-migrate 是一个 CLI 工具/kubectl 插件&#xff0c;可以轻松地将一个 Kubernetes PersistentVo…...

KotlinConf 2024:深入了解Kotlin Multiplatform (KMP)

KotlinConf 2024&#xff1a;深入了解Kotlin Multiplatform (KMP) 在近期的Google I/O大会上&#xff0c;我们推荐了Kotlin Multiplatform (KMP)用于跨移动、网页、服务器和桌面平台共享业务逻辑&#xff0c;并在Google Workspace中采用了KMP。紧接着&#xff0c;KotlinConf 2…...

探索ChatGPT-4在解决化学知识问题上的研究与应用

1. 概述 近年来&#xff0c;人工智能的发展主要集中在 GPT-4 等大型语言模型上。2023 年 3 月发布的这一先进模型展示了利用广泛知识应对从化学研究到日常问题解决等复杂挑战的能力。也开始进行研究&#xff0c;对化学的各个领域&#xff0c;从化学键到有机化学和物理化学&…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...