Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >如何在十亿用户中检查某个用户名是否存在?

如何在十亿用户中检查某个用户名是否存在?

原创
作者头像
Power
发布于 2025-04-01 16:13:04
发布于 2025-04-01 16:13:04
34500
代码可运行
举报
运行总次数:0
代码可运行

前言

不知道大家有没有注意到,有些APP注册的时候,会提示用户名已经被占用,需要更换一个。

实现这个功能的方式有很多种,现在我们来逐一看一下不同设计方案的优缺点。

数据库方案

这种方式实现起来最简单,但是在数据量大的情况下,比如十亿用户数据时会带来以下问题:

  1. 存在延迟比较大的性能问题,如果数据量很大,查询速度会变慢,而且数据库查询涉及到应用服务器数据库服务器之间的网络通信,建立连接、发送查询、接收响应所需的时间也会导致延迟。
  2. 数据库负载过大。频繁执行 SELECT 查询来检查用户名的唯一性,每个查询都会消耗数据库资源,包括 CPU 和 I/O 资源。
  3. 可扩展性差。数据库对并发连接和资源有限制。如果注册率持续上升,数据库服务器可能难以处理不断增加的传入请求。数据库的垂直扩展(向单个服务器添加更多资源)可能成本高昂,并且可能存在局限性。

缓存解决方案

为了解决检查用户名唯一性的数据库调用的性能问题,我们可以引入高效的 Redis 缓存方案。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
import org.redisson.Redisson;  
import org.redisson.api.RedissonClient;  
import org.redisson.config.Config;  
import org.redisson.api.RMap;  
  
public class UserExistenceChecker {  
  
    // Redis hash map name to store user information  
    private static final String USER_HASH_NAME = "users";  
  
    public static void main(String[] args) {  
        // Create a Redisson client  
        RedissonClient redisson = createRedissonClient();  
  
        // Retrieve the hash map to store user information  
        RMap<String, String> users = redisson.getMap(USER_HASH_NAME);  
  
        // Add a user to the hash map  
        users.put("user123", "someUserInfo"); // Here "someUserInfo" could be a JSON string, UUID, etc.  
  
        // Check if a user exists  
        boolean exists = users.containsKey("user123");  
        System.out.println("User 'user123' exists? " + exists);  
  
        // Check for a non-existent user  
        exists = users.containsKey("user456");  
        System.out.println("User 'user456' exists? " + exists);  
  
        // Shutdown the Redisson client  
        redisson.shutdown();  
    }  
  
    // Helper method to create a Redisson client  
    private static RedissonClient createRedissonClient() {  
        Config config = new Config();  
        config.useSingleServer()  
                .setAddress("redis://127.0.0.1:6379") // Adjust to your Redis address  
                .setPassword("yourpassword"); // Provide your Redis password if any  
  
        return Redisson.create(config);  
    }  
}

这个方案最大的问题是内存占用过大,假设每个用户名大约需要15字节的内存,如果要存储10亿个用户名,就需要15GB的内存。

总内存 = 每条记录的内存使用量 * 记录数 = 15 字节/记录 * 1,000,000,000 条记录 = 15,000,000,000 字节 ≈ 15,000,000 KB ≈ 15,000 MB ≈ 15 GB

布隆过滤器方案

如果直接通过缓存进行判断,会占用过多的内存,有没有更好的办法?Bloom Filter 是一个很不错的选择。

什么是布隆过滤器?

Bloom Filter 是一种高度节省空间的随机数据结构,它用一个位数组来简洁地表示一个集合,并可以判断某个元素是否属于这个集合。

Bloom Filter 的这种高效是有代价的:在判断某个元素是否属于某个集合时,有可能错误地将不属于该集合的元素认为是属于该集合(false positive)。

因此,Bloom Filter 并不适合“零错误”的应用场景,但在可以容忍较低错误率的应用场景中,Bloom Filter 通过极少的错误实现了存储空间的大幅节省。

结构

从上面的分析可以知道,布隆过滤器的核心思想是利用一个位数组(bit array)和一组哈希函数

位数组,每个位最初为 0:

在插入值x时,分别使用k个哈希函数(图中3个)对x的值进行哈希运算,并将哈希值与布隆过滤器的容量(位数组长度)取余数,并将结果所代表的相应位的值设置为1。

查找过程类似于插入过程,同样使用k个哈希函数对要查找的值进行哈希处理,只有哈希处理后得到的每个比特位的值为1时,才表示该值“可能”存在;反之,如果任意一个比特位的值为0,则表示该值一定不存在。例如y1一定不存在,而y2则可能存在。

Redis是支持Bloom filter这种数据结构的,我们来使用Redisson客户端简单实现一下代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;

public class UserExistenceChecker {

    // Name of the Bloom Filter in Redis
    private static final String BLOOM_FILTER_NAME = "user_existence_filter";

    public static void main(String[] args) {
        // Create a Redisson client
        RedissonClient redisson = createRedissonClient();

        // Retrieve or create a Bloom Filter instance
        // Expected number of elements and false positive probability are parameters
        RBloomFilter<String> bloomFilter = redisson.getBloomFilter(BLOOM_FILTER_NAME);
        bloomFilter.tryInit(100000L, 0.001); // Initialize the Bloom Filter with expected elements and false positive rate

        // Add a user to the Bloom Filter
        bloomFilter.add("user123");

        // Check if a user exists
        boolean exists = bloomFilter.contains("user123"); // Should return true
        System.out.println("User 'user123' exists? " + exists);

        // Check for a non-existent user (might falsely report as true due to Bloom Filter's nature)
        exists = bloomFilter.contains("user456"); // Assuming not added, should ideally return false, but could be a false positive
        System.out.println("User 'user456' exists? " + exists);

        // Shutdown the Redisson client
        redisson.shutdown();
    }

    // Helper method to create a Redisson client
    private static RedissonClient createRedissonClient() {
        Config config = new Config();
        config.useSingleServer()
                .setAddress("redis://127.0.0.1:6379"); // Adjust to your Redis address
//                .setPassword("yourpassword"); // Provide your Redis password if any

        return Redisson.create(config);
    }
}

优点:

  • 节省内存空间:相比使用哈希表等数据结构,布隆过滤器通常需要更少的内存空间,因为它不存储实际的元素,而只存储元素的哈希值。如果存储10亿条记录,误差probability为0.001,则只1.67 GB需要 的内存。相比原来的15G,已经大大减少了。
  • 高效查找:布隆过滤器可以在常数时间内快速判断某个元素是否存在于集合中(O(1)),而不需要遍历整个集合。

缺点

  • 存在误报率: Bloom filter 在判断某个元素是否存在的时候,存在一定的误报率。这意味着在某些情况下,它可能会误报某个元素存在,但不会误报某个元素不存在。不过这一般影响不大。
  • 不能删除元素:布隆过滤器通常不支持从集合中删除元素,因为删除一个元素会影响其他元素的哈希值,增加误报率。

如何保证布隆过滤器方案没有误报?

这里可以考虑将Bloom filter与数据库相结合的方案。

使用Bloom Filter判断某个元素是否存在的时候,有一定概率会误报该元素存在,但是不会误报该元素不存在。

所以,当使用布隆过滤器判断某个元素不存在的时候,可以直接信任这个结果并返回。如果判断某个元素存在,此时不要完全信任它的判断,而是去数据库中查询真正的结果。

因为确定某个元素存在的概率已经很低了,所以实际访问数据库的量也会很小,整体压力不是很大。

可以从布隆过滤器中删除元素吗?

为什么 Bloom Filter 中的元素不能被删除呢?我们举一个例子来说明。

比如我们要从集合中删除成员“Jerry”,那么我们首先会用k(图中为2)个哈希函数来计算。由于“Jerry”已经是集合中的成员,所以位数组中对应位置肯定是1。如果要删除这个成员“Jerry”,我们需要将计算出的位置上的1全部设置为0。下图中,只需要将索引位置2和5的值都设置为0即可。

问题来了!现在我们假设“Tom”也已经是集合中的一个元素了。如果我们需要查询“Tom”是否在这个集合中,经过哈希函数计算后,我们会判断第三位和第五位是否为1。这时候我们得到的结果是第五位为0,也就是“Tom”不属于这个集合。很显然,这里是一个false positive。

所以,原始的Bloom Filter是不支持删除元素的,但是Counting Bloom Filter可以。

Counting Bloom Filter 的出现解决了上述问题,它将标准 Bloom Filter 的位数组的每一位扩展为一个小的计数器,当插入一个元素时,分别将对应的 k(k 为哈希函数个数)个计数器的值加 1,当删除一个元素时,分别将对应的 k 个计数器的值减 1。

由此我们可以看出,Counting Bloom Filter 在 Bloom Filter 的基础上增加了一个删除操作,但代价是占用多几倍的存储空间。基本原理是不是很简单呢?看下面这张图,就能明白它和 Bloom Filter 的区别在哪里了。

计数器大小的选择

计数布隆过滤器与布隆过滤器的一个主要区别是,计数布隆过滤器用计数器代替了布隆过滤器中的一位。

那么 Counter 应该设多大呢?这里就需要考虑空间利用率的问题了。从利用率的角度来说,当然是越大越好,因为 Counter 越大,可以表示的信息就越多。但是 Counter 越大,意味着占用的资源越多,往往会造成很大的空间浪费。

所以在选择Counter的时候,我们应该尽可能的满足要求。Counter的具体计算比较复杂,涉及到一系列的数学公式,这里就不展开了,有兴趣的朋友可以参考论文第6、7页:《Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol》,里面具体阐述了这一点。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
品味布隆过滤器 Bloom filter的设计之美
你可能没想到: RocketMQ、 Hbase 、Cassandra 、LevelDB 、RocksDB 这些知名项目中都有布隆过滤器的身影。
勇哥java实战
2023/04/14
2.4K0
品味布隆过滤器 Bloom filter的设计之美
布隆过滤器 | 亿级数据处理原理与实战
布隆过滤器(英语:Bloom Filter)是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。
Rude3Knife的公众号
2020/05/15
2.1K0
布隆过滤器,一文总结快速掌握,你能够get多少?
假如有一个15亿用户的系统,每天有几亿用户访问系统,要如何快速判断是否为系统中的用户呢?
Java程序猿阿谷
2021/03/11
1.4K0
布隆过滤器,一文总结快速掌握,你能够get多少?
场景题:如何在1G内存下实现40亿QQ号去重?
当数据量较大时,使用常规方法进行判重是不可行的。例如,使用MySQL数据库或Java中的List.contains()或Set.contains()进行判重会导致内存不足或查询速度过慢等问题。
用户11397231
2025/06/02
640
场景题:如何在1G内存下实现40亿QQ号去重?
硬核 | Redis 布隆(Bloom Filter)过滤器原理与实战
在Redis 缓存击穿(失效)、缓存穿透、缓存雪崩怎么解决?中我们说到可以使用布隆过滤器避免「缓存穿透」。
码哥字节
2022/04/08
15.7K0
硬核 | Redis 布隆(Bloom Filter)过滤器原理与实战
重学SpringBoot3-集成Redis(五)之布隆过滤器
在高并发场景下,缓存是提升系统性能的重要手段。然而,常规缓存机制中,若遇到大量无效请求访问(请求的 key 不存在于缓存或数据库),就会导致 缓存穿透。为了应对这种问题,布隆过滤器 和 缓存空值 是应对缓存穿透的两大主流方案,布隆过滤器适用于大规模、复杂场景,缓存空值适用于小规模场景。布隆过滤器(Bloom Filter) 能够通过哈希算法判断一个 key 是否可能存在,减少无效请求对数据库的压力。
CoderJia
2024/10/18
3600
重学SpringBoot3-集成Redis(五)之布隆过滤器
场景题:假设有40亿QQ号,但只有1G内存,如何实现去重?
当数据量比较大时,使用常规的方式来判重就不行了。例如,使用 MySQL 数据库判重,或使用 List.contains() 或 Set.contains() 判重就不行了,因为数据量太大会导致内存放不下,或查询速度太慢等问题。
磊哥
2025/01/08
1740
场景题:假设有40亿QQ号,但只有1G内存,如何实现去重?
什么是布隆过滤器?如何解决高并发缓存穿透问题?
日常开发中,大家经常使用缓存,但是你知道大型的互联网公司面对高并发流量,要注意缓存穿透问题吗!!! 本文会介绍布隆过滤器,空间换时间,以较低的内存空间、高效解决这个问题。
微观技术
2021/07/28
6010
redis中的布隆过滤器
redis 在 4.0 的版本中加入了 module 功能,布隆过滤器可以通过 module 的形式添加到 redis 中,所以使用 redis 4.0 以上的版本可以通过加载 module来使用 redis 中的布隆过滤器。但是这不是最简单的方式,使用 docker 可以直接在 redis 中体验布隆过滤器。
名字是乱打的
2021/12/22
6660
BloomFilter怎么用?使用布隆过滤器来判断key是否存在?「建议收藏」
今天跟一个同事聊了一个问题,说最近在做推荐,如何判断用户是否看过这个片段呢?想了一下,正好可以使用布隆过滤器来完成这个需求。
全栈程序员站长
2022/11/16
1.3K0
BloomFilter怎么用?使用布隆过滤器来判断key是否存在?「建议收藏」
布隆过滤器
布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。
Vincent-yuan
2022/05/06
4710
布隆过滤器
最牛一篇布隆过滤器详解
我们之前讲了Redis的缓存雪崩、穿透、击穿。在文章里我们说了解决缓存穿透的办法之一,就是布隆过滤器,但是上次并没有讲如何使用布隆过滤器。
公众号 IT老哥
2020/10/27
7.9K1
最牛一篇布隆过滤器详解
布隆过滤器能解决哪些问题?
举个例子 : 有 50 亿个电话号码,现在给你 10 万个电话号码,如何快速准确的判断出这些号码是否存在?
用户11397231
2024/12/10
1150
布隆过滤器能解决哪些问题?
优化系统性能:深入探讨Web层缓存与Redis应用的挑战与对策
Web层缓存对于提高应用性能至关重要,它通过减少重复的数据处理和数据库查询来加快响应时间。例如,如果一个用户请求的数据已经缓存,服务器可以直接从缓存中返回结果,避免了每次请求都进行复杂的计算或数据库查询。这不仅提高了应用的响应速度,还减轻了后端系统的负担。
努力的小雨
2024/08/12
4270
Redis详解(十三)------ Redis布隆过滤器
本篇我们主要介绍如何用Redis实现布隆过滤器,但是在介绍布隆过滤器之前,我们首先介绍一下,为啥要使用布隆过滤器。
IT可乐
2020/06/03
2.7K0
40亿个QQ号,限制1G内存,如何去重?
4*4000000000 /1024/1024/1024 = 14.9G ,考虑到其中有一些重复的话,那1G的空间也基本上是不够用的。
程序员大彬
2023/09/06
4280
40亿个QQ号,限制1G内存,如何去重?
电商中如何高效的判断某用户已参加了某活动?
看了这个话题,我相信很多人都会说,这还不简单。某用户参加了某优惠活动,购买了某商品等,数据库中肯定有对应记录吧。查询一下不久好了!
业余草
2019/06/24
9330
电商中如何高效的判断某用户已参加了某活动?
不了解布隆过滤器?一文给你整的明明白白!
海量数据处理以及缓存穿透这两个场景让我认识了布隆过滤器 ,我查阅了一些资料来了解它,但是很多现成资料并不满足我的需求,所以就决定自己总结一篇关于布隆过滤器的文章。希望通过这篇文章让更多人了解布隆过滤器,并且会实际去使用它!
乔戈里
2019/12/11
9840
不了解布隆过滤器?一文给你整的明明白白!
SpringBoot系列之集成Redisson实现布隆过滤器
在高并发和大数据量的场景下,布隆过滤器是一种非常高效的存储结构,可以用于快速判断一个元素是否存在于集合中。本文将介绍如何在Spring Boot中集成Redisson来实现布隆过滤器,并通过一个订单查询的示例来展示其应用。
SmileNicky
2025/04/12
2460
redis学习之redis应用(四)
Redis Java客户端有很多的开源产品比如Redission、Jedis、lettuce
周杰伦本人
2022/10/25
4790
redis学习之redis应用(四)
推荐阅读
相关推荐
品味布隆过滤器 Bloom filter的设计之美
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验