后端文档教程【免费下载链接】system-design-101Explain complex systems using visuals and simple terms. Help you prepare for system design interviews.项目地址https://gitcode.com/GitHub_Trending/sy/system-design-101点击查看免费下载在搜索引擎的网页抓取体系中URL 去重是一个必须解决的基础问题同一链接可能被多入口重复发现重复抓取不仅浪费带宽、计算与存储资源还会给目标站点带来无谓的访问压力。本指南源于 system-design-101 仓库 中 《How to Avoid Crawling Duplicate URLs at Google Scale?》 一文系统梳理三种去重候选方案并深入讲解被业界首选的布隆过滤器Bloom Filter——从位向量原理、哈希函数选择到工程参数权衡。读完本文你将理解为什么在数十亿级 URL 的规模下布隆过滤器能以极低内存代价完成一定不存在的精准判定并掌握它在缓存穿透防护等场景中的实战用法。一、问题背景Google 规模下的 URL 去重爬虫Crawler的工作方式是沿着已发现页面中的链接不断发现新 URL而网页之间的互相引用使同一个 URL 极容易被重复发现。若不做去重会导致同一网页被重复抓取浪费网络带宽与目标站点资源重复解析、索引消耗大量 CPU 与存储抓取队列膨胀降低整体抓取效率。在 Google 这种量级下URL 数量以十亿甚至更高计去重判定必须在极低内存占用、极低时延下完成并且要能随抓取集群水平扩展。原文档给出了三条可选的技术路线并明确推荐第三种——布隆过滤器。二、三种去重方案Set、数据库与布隆过滤器原文档将候选方案归纳为三种各自的取舍非常清晰方案思路优点缺点Option 1Set 数据结构把已抓取 URL 放进内存 Set新 URL 到来时做成员判断判断速度快语义精确内存开销大不省空间URL 数量达到十亿级后内存不可承受Option 2数据库存储 URL将 URL 持久化到数据库查询是否已存在可持久化、容量理论上可扩展每次去重都是一次数据库查询数据库负载会非常高成为瓶颈Option 3布隆过滤器用概率型数据结构做成员判断内存占用极小、查询 O(k)k 为哈希函数个数且与集合大小无关存在假阳性可能误判为存在无法删除元素原文档的结论是Option 3 为首选它牺牲精确性换取空间效率恰好匹配大规模爬虫去重的核心诉求——绝大多数场景下我们只需要排除确定不存在的 URL少量的假阳性最多导致个别重复抓取成本可控。三、布隆过滤器原理1970 年诞生的概率数据结构布隆过滤器由 Burton Howard Bloom 于 1970 年提出原文即引用了这一出处。它被定义为一个概率型数据结构用于测试某个元素是否属于一个集合其判断语义是false返回不存在元素绝对不在集合中true返回可能存在元素可能在集合中。也就是说假阳性false positive是可能的假阴性false negative是不可能的。这个不对称的性质正是它敢于被大规模使用的底气宁可多抓一次也绝不漏掉一个。布隆过滤器的基础数据结构是位向量Bit Vector——一个只存 0/1 的位数组每一位代表一个哈希后的位置。原文档通过两步来说明它的工作机制。Step 1添加元素——写入位要把一个元素加入布隆过滤器把它喂给3 个不同的哈希函数A、B、C然后在结果对应的位下标上置 1。原文档给出了一个关键示例两个 URL www.myweb1.com 和 www.myweb2.com 都标记了索引 5 的位为 1。这正是布隆过滤器产生假阳性的根源一个位可能被其他元素置位。当位数组被越来越多的元素写入后不同元素哈希到的位会互相重叠单个位为 1 不再能证明某个特定元素写入过它。Step 2成员检测——读取位要测试一个 URL 字符串是否已存在同样用哈希函数 A、B、C 对该字符串求值然后检查对应三个位三个位全部为 1→ URL可能存在于数据集中可能是真阳性也可能是假阳性任意一个位为 0→ URL一定不存在于数据集中。判断一定不存在的成立依据是如果该元素确实被写入过它写入时置 1 的那几个位必然都还是 1布隆过滤器只置位、永不复位。反之只要有一位是 0就证明该元素从未被写入。上述添加与检测两步是布隆过滤器的完整操作模型全部操作只需要 O(k) 次哈希与位读写与集合规模 n 无关这使它在海量数据下保持恒定低时延。四、哈希函数的选择均匀分布与速度原文档明确指出哈希函数的选择至关重要必须均匀分布且足够快。均匀分布保证元素被均匀撒到整个位数组上避免某些位被过度集中写入。若哈希分布不均匀位数组局部拥挤假阳性率会迅速恶化。足够快因为每次添加和检测都要执行 k 次哈希哈希函数本身的速度直接决定吞吐量在大规模抓取场景这个常数因子会被放大到显著程度。原文档给出了业界主流选型作为佐证RedisBloom 与 Apache Spark 使用 MurmurHashmurmurInfluxDB 使用 xxHashxxhash。这也印证了布隆过滤器不是用一个通用哈希就行——工程上往往会为它专门挑选高速、低碰撞的非加密哈希族Murmur、xxHash 等而非昂贵的加密哈希。五、工程参数内存与假阳性率的取舍虽然原文档未展开公式但这是把布隆过滤器落地到生产环境必须掌握的配套知识。设位数组长度为 m位、待写入元素数量为 n、哈希函数个数为 k工程上常用的近似公式为假阳性率 ≈(1 - e^(-k·n/m))^k给定 m 与 n使假阳性率最低的最优哈希函数个数为k (m/n)·ln2。实际操作步骤通常是根据可接受的内存预算确定 m或根据可接受的假阳性率倒推 m由公式求出 k取整数用 m/n 估算内存例如 10 亿个 URL、k7 时位数组约需要m k·n/ln2 ≈ 10 GB量级——相比存储完整 URL 字符串每个 URL 数十到数百字节还要再乘上 Set 的指针与哈希桶开销节省空间的效果非常可观。布隆过滤器的省内存不是魔法而是用可量化的假阳性率换来的工程上应在抓取重复成本与误判容忍度之间取平衡。六、仓库内的延伸应用缓存穿透与缓存击穿防护布隆过滤器在本仓库中的应用远不止爬虫去重多篇指南把它作为**缓存穿透Cache Penetration / Cache Miss Attack**的标准解法可互为印证《Cache Miss Attack》 描述当查询的 key 在数据库和缓存中都不存在时每次请求都会穿透到数据库恶意用户可用大量此类 key 打垮数据库。该文给出的解法之一正是布隆过滤器——如果 key 不在数据集中说明它既不在缓存也不在数据库中查询不会命中缓存或数据库层从而在入口处直接拦截不存在的 key。《How Can Cache Systems Go Wrong?》 在Cache Penetration一节同样建议先用布隆过滤器检查 key 是否存在如果不存在就可以避免打到数据库。《The Ultimate Redis 101》 在介绍 Redis 模块生态时列出了RedisBloom——一个将布隆过滤器作为模块化能力提供给生产系统的实现与原文RedisBloom 使用 murmur 哈希的表述一致。从源码结构看本仓库的文档体系由 scripts/readme.ts 统一管理每篇指南以 frontmattertitle、description、createdAt、categories、tags为元数据分类目录存放于 data/categories正文存放于 data/guidesREADME 的目录即由该脚本按分类与创建时间自动生成。爬虫去重这篇指南在 README 中被归入Software Development分类与算法与数据结构主题并置。七、局限性不可删除与假阳性代价理解布隆过滤器也要知道它的边界不支持删除元素普通布隆过滤器只有置位没有复位因为无法区分某一位是被当前元素还是其他元素置 1。需要删除时可升级为计数布隆过滤器Counting Bloom Filter用计数器数组替代位数组代价是内存成倍上升假阳性不可消除它会偶尔放行其实已抓取过的 URL导致少量重复抓取在爬虫场景中通常可接受但在要求绝对精确的场景如支付、权限判定需要额外兜底容量是设计时参数位数组长度 m 与哈希函数个数 k 在创建时确定元素数量 n 超出设计容量后假阳性率会急剧上升扩容需要重建。因此合理的工程姿势是把布隆过滤器当作前置过滤器用它低成本挡掉确定不存在的绝大多数请求对可能存在的少量元素再走精确判定或直接放行而不是替代所有精确数据结构。八、小结与延伸阅读回到原文档的核心结论面对 Google 量级的 URL 去重Set 很快但不省内存数据库可行但负载过高布隆过滤器则同时满足了小内存 快判定 无假阴性三项诉求——假阳性换来的是空间与速度的数量级优势而宁可多抓不可漏抓的语义恰好与爬虫业务完全匹配。如果想继续深入可在本仓库中阅读系统设计与基础概念总览README了解本文档在知识体系中的位置Cache Miss Attack看布隆过滤器如何拦截缓存穿透攻击How Can Cache Systems Go Wrong?对照缓存穿透、缓存击穿、缓存雪崩的完整解法矩阵The Ultimate Redis 101了解 RedisBloom 等生产级模块化实现scripts/readme.ts了解本仓库文档的元数据组织与目录生成机制。布隆过滤器是用简单结构解决规模问题的经典代表一段位数组加几个精心挑选的哈希函数就撑起了搜索引擎、分布式缓存、数据库中间件等无数基础设施的去重与过滤职责。赞分享后端文档教程【免费下载链接】system-design-101Explain complex systems using visuals and simple terms. Help you prepare for system design interviews.项目地址https://gitcode.com/GitHub_Trending/sy/system-design-101点击查看免费下载相关推荐Sign Language Recognition with MediaPipe构建实时手语手势识别系统Sign Language Recognition with MediaPipe构建实时手语手势识别系统 手语是听障人士与外界沟通的重要桥梁但传统交流方式存如何用Go实现布隆过滤器learning_tools中Redis布隆过滤器实现如何用Go实现布隆过滤器learning_tools中Redis布隆过滤器实现 布隆过滤器是一种高效的概率型数据结构用于快速判断一个元素是否存在于某个集合中示例工程批量网页管理神器如何用Open Multiple URLs扩展10倍提升工作效率批量网页管理神器如何用Open Multiple URLs扩展10倍提升工作效率 你是否还在为每天需要同时打开几十个网页而烦恼复制粘贴、逐个点击、标签页混乱上一篇dstack任务和服务配置详解从简单作业到复杂部署下一篇APOLLO报0 databases怎么办iOS取证数据权限错误排查与chmod/chown修复完整清单创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 System Design 101：Google 级爬虫如何用布隆过滤器避免重复 URL 抓取
后端文档教程【免费下载链接】system-design-101Explain complex systems using visuals and simple terms. Help you prepare for system design interviews.项目地址https://gitcode.com/GitHub_Trending/sy/system-design-101点击查看免费下载在搜索引擎的网页抓取体系中URL 去重是一个必须解决的基础问题同一链接可能被多入口重复发现重复抓取不仅浪费带宽、计算与存储资源还会给目标站点带来无谓的访问压力。本指南源于 system-design-101 仓库 中 《How to Avoid Crawling Duplicate URLs at Google Scale?》 一文系统梳理三种去重候选方案并深入讲解被业界首选的布隆过滤器Bloom Filter——从位向量原理、哈希函数选择到工程参数权衡。读完本文你将理解为什么在数十亿级 URL 的规模下布隆过滤器能以极低内存代价完成一定不存在的精准判定并掌握它在缓存穿透防护等场景中的实战用法。一、问题背景Google 规模下的 URL 去重爬虫Crawler的工作方式是沿着已发现页面中的链接不断发现新 URL而网页之间的互相引用使同一个 URL 极容易被重复发现。若不做去重会导致同一网页被重复抓取浪费网络带宽与目标站点资源重复解析、索引消耗大量 CPU 与存储抓取队列膨胀降低整体抓取效率。在 Google 这种量级下URL 数量以十亿甚至更高计去重判定必须在极低内存占用、极低时延下完成并且要能随抓取集群水平扩展。原文档给出了三条可选的技术路线并明确推荐第三种——布隆过滤器。二、三种去重方案Set、数据库与布隆过滤器原文档将候选方案归纳为三种各自的取舍非常清晰方案思路优点缺点Option 1Set 数据结构把已抓取 URL 放进内存 Set新 URL 到来时做成员判断判断速度快语义精确内存开销大不省空间URL 数量达到十亿级后内存不可承受Option 2数据库存储 URL将 URL 持久化到数据库查询是否已存在可持久化、容量理论上可扩展每次去重都是一次数据库查询数据库负载会非常高成为瓶颈Option 3布隆过滤器用概率型数据结构做成员判断内存占用极小、查询 O(k)k 为哈希函数个数且与集合大小无关存在假阳性可能误判为存在无法删除元素原文档的结论是Option 3 为首选它牺牲精确性换取空间效率恰好匹配大规模爬虫去重的核心诉求——绝大多数场景下我们只需要排除确定不存在的 URL少量的假阳性最多导致个别重复抓取成本可控。三、布隆过滤器原理1970 年诞生的概率数据结构布隆过滤器由 Burton Howard Bloom 于 1970 年提出原文即引用了这一出处。它被定义为一个概率型数据结构用于测试某个元素是否属于一个集合其判断语义是false返回不存在元素绝对不在集合中true返回可能存在元素可能在集合中。也就是说假阳性false positive是可能的假阴性false negative是不可能的。这个不对称的性质正是它敢于被大规模使用的底气宁可多抓一次也绝不漏掉一个。布隆过滤器的基础数据结构是位向量Bit Vector——一个只存 0/1 的位数组每一位代表一个哈希后的位置。原文档通过两步来说明它的工作机制。Step 1添加元素——写入位要把一个元素加入布隆过滤器把它喂给3 个不同的哈希函数A、B、C然后在结果对应的位下标上置 1。原文档给出了一个关键示例两个 URL www.myweb1.com 和 www.myweb2.com 都标记了索引 5 的位为 1。这正是布隆过滤器产生假阳性的根源一个位可能被其他元素置位。当位数组被越来越多的元素写入后不同元素哈希到的位会互相重叠单个位为 1 不再能证明某个特定元素写入过它。Step 2成员检测——读取位要测试一个 URL 字符串是否已存在同样用哈希函数 A、B、C 对该字符串求值然后检查对应三个位三个位全部为 1→ URL可能存在于数据集中可能是真阳性也可能是假阳性任意一个位为 0→ URL一定不存在于数据集中。判断一定不存在的成立依据是如果该元素确实被写入过它写入时置 1 的那几个位必然都还是 1布隆过滤器只置位、永不复位。反之只要有一位是 0就证明该元素从未被写入。上述添加与检测两步是布隆过滤器的完整操作模型全部操作只需要 O(k) 次哈希与位读写与集合规模 n 无关这使它在海量数据下保持恒定低时延。四、哈希函数的选择均匀分布与速度原文档明确指出哈希函数的选择至关重要必须均匀分布且足够快。均匀分布保证元素被均匀撒到整个位数组上避免某些位被过度集中写入。若哈希分布不均匀位数组局部拥挤假阳性率会迅速恶化。足够快因为每次添加和检测都要执行 k 次哈希哈希函数本身的速度直接决定吞吐量在大规模抓取场景这个常数因子会被放大到显著程度。原文档给出了业界主流选型作为佐证RedisBloom 与 Apache Spark 使用 MurmurHashmurmurInfluxDB 使用 xxHashxxhash。这也印证了布隆过滤器不是用一个通用哈希就行——工程上往往会为它专门挑选高速、低碰撞的非加密哈希族Murmur、xxHash 等而非昂贵的加密哈希。五、工程参数内存与假阳性率的取舍虽然原文档未展开公式但这是把布隆过滤器落地到生产环境必须掌握的配套知识。设位数组长度为 m位、待写入元素数量为 n、哈希函数个数为 k工程上常用的近似公式为假阳性率 ≈(1 - e^(-k·n/m))^k给定 m 与 n使假阳性率最低的最优哈希函数个数为k (m/n)·ln2。实际操作步骤通常是根据可接受的内存预算确定 m或根据可接受的假阳性率倒推 m由公式求出 k取整数用 m/n 估算内存例如 10 亿个 URL、k7 时位数组约需要m k·n/ln2 ≈ 10 GB量级——相比存储完整 URL 字符串每个 URL 数十到数百字节还要再乘上 Set 的指针与哈希桶开销节省空间的效果非常可观。布隆过滤器的省内存不是魔法而是用可量化的假阳性率换来的工程上应在抓取重复成本与误判容忍度之间取平衡。六、仓库内的延伸应用缓存穿透与缓存击穿防护布隆过滤器在本仓库中的应用远不止爬虫去重多篇指南把它作为**缓存穿透Cache Penetration / Cache Miss Attack**的标准解法可互为印证《Cache Miss Attack》 描述当查询的 key 在数据库和缓存中都不存在时每次请求都会穿透到数据库恶意用户可用大量此类 key 打垮数据库。该文给出的解法之一正是布隆过滤器——如果 key 不在数据集中说明它既不在缓存也不在数据库中查询不会命中缓存或数据库层从而在入口处直接拦截不存在的 key。《How Can Cache Systems Go Wrong?》 在Cache Penetration一节同样建议先用布隆过滤器检查 key 是否存在如果不存在就可以避免打到数据库。《The Ultimate Redis 101》 在介绍 Redis 模块生态时列出了RedisBloom——一个将布隆过滤器作为模块化能力提供给生产系统的实现与原文RedisBloom 使用 murmur 哈希的表述一致。从源码结构看本仓库的文档体系由 scripts/readme.ts 统一管理每篇指南以 frontmattertitle、description、createdAt、categories、tags为元数据分类目录存放于 data/categories正文存放于 data/guidesREADME 的目录即由该脚本按分类与创建时间自动生成。爬虫去重这篇指南在 README 中被归入Software Development分类与算法与数据结构主题并置。七、局限性不可删除与假阳性代价理解布隆过滤器也要知道它的边界不支持删除元素普通布隆过滤器只有置位没有复位因为无法区分某一位是被当前元素还是其他元素置 1。需要删除时可升级为计数布隆过滤器Counting Bloom Filter用计数器数组替代位数组代价是内存成倍上升假阳性不可消除它会偶尔放行其实已抓取过的 URL导致少量重复抓取在爬虫场景中通常可接受但在要求绝对精确的场景如支付、权限判定需要额外兜底容量是设计时参数位数组长度 m 与哈希函数个数 k 在创建时确定元素数量 n 超出设计容量后假阳性率会急剧上升扩容需要重建。因此合理的工程姿势是把布隆过滤器当作前置过滤器用它低成本挡掉确定不存在的绝大多数请求对可能存在的少量元素再走精确判定或直接放行而不是替代所有精确数据结构。八、小结与延伸阅读回到原文档的核心结论面对 Google 量级的 URL 去重Set 很快但不省内存数据库可行但负载过高布隆过滤器则同时满足了小内存 快判定 无假阴性三项诉求——假阳性换来的是空间与速度的数量级优势而宁可多抓不可漏抓的语义恰好与爬虫业务完全匹配。如果想继续深入可在本仓库中阅读系统设计与基础概念总览README了解本文档在知识体系中的位置Cache Miss Attack看布隆过滤器如何拦截缓存穿透攻击How Can Cache Systems Go Wrong?对照缓存穿透、缓存击穿、缓存雪崩的完整解法矩阵The Ultimate Redis 101了解 RedisBloom 等生产级模块化实现scripts/readme.ts了解本仓库文档的元数据组织与目录生成机制。布隆过滤器是用简单结构解决规模问题的经典代表一段位数组加几个精心挑选的哈希函数就撑起了搜索引擎、分布式缓存、数据库中间件等无数基础设施的去重与过滤职责。赞分享后端文档教程【免费下载链接】system-design-101Explain complex systems using visuals and simple terms. Help you prepare for system design interviews.项目地址https://gitcode.com/GitHub_Trending/sy/system-design-101点击查看免费下载相关推荐Sign Language Recognition with MediaPipe构建实时手语手势识别系统Sign Language Recognition with MediaPipe构建实时手语手势识别系统 手语是听障人士与外界沟通的重要桥梁但传统交流方式存如何用Go实现布隆过滤器learning_tools中Redis布隆过滤器实现如何用Go实现布隆过滤器learning_tools中Redis布隆过滤器实现 布隆过滤器是一种高效的概率型数据结构用于快速判断一个元素是否存在于某个集合中示例工程批量网页管理神器如何用Open Multiple URLs扩展10倍提升工作效率批量网页管理神器如何用Open Multiple URLs扩展10倍提升工作效率 你是否还在为每天需要同时打开几十个网页而烦恼复制粘贴、逐个点击、标签页混乱上一篇dstack任务和服务配置详解从简单作业到复杂部署下一篇APOLLO报0 databases怎么办iOS取证数据权限错误排查与chmod/chown修复完整清单创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考