如何在十亿级别用户中检查用户名是否存在？

妖狐艹你老母 2024-02-20 10:42 53阅读 0赞

不知道大家有没有留意过，在使用一些app注册的时候，提示你用户名已经被占用了，需要更换一个，这是如何实现的呢？你可能想这不是很简单吗，去数据库里查一下有没有不就行了吗，那么假如用户数量很多，达到数亿级别呢，这又该如何是好？

数据库方案  
第一种方案就是查数据库的方案，大家都能够想到，代码如下：

public class UsernameUniquenessChecker {
        
        private static final String DB_URL = "jdbc:mysql://localhost:3306/your_database";
        private static final String DB_USER = "your_username";
        private static final String DB_PASSWORD = "your_password";
    
        public static boolean isUsernameUnique(String username) {
        
            try (Connection conn = DriverManager.getConnection(DB_URL, DB_USER, DB_PASSWORD)) {
        
                String sql = "SELECT COUNT(*) FROM users WHERE username = ?";
                try (PreparedStatement stmt = conn.prepareStatement(sql)) {
        
                    stmt.setString(1, username);
                    try (ResultSet rs = stmt.executeQuery()) {
        
                        if (rs.next()) {
        
                            int count = rs.getInt(1);
                            return count == 0; // If count is 0, username is unique
                        }
                    }
                }
            } catch (SQLException e) {
        
                e.printStackTrace();
            }
            return false; // In case of an error, consider the username as non-unique
        }
    
        public static void main(String[] args) {
        
            String desiredUsername = "new_user";
            boolean isUnique = isUsernameUnique(desiredUsername);
            if (isUnique) {
        
                System.out.println("Username '" + desiredUsername + "' is unique. Proceed with registration.");
            } else {
        
                System.out.println("Username '" + desiredUsername + "' is already in use. Choose a different one.");
            }
        }
    }

这种方法会带来如下问题：

性能问题，延迟高 。 如果数据量很大，查询速度慢。另外，数据库查询涉及应用程序服务器和数据库服务器之间的网络通信。建立连接、发送查询和接收响应所需的时间也会导致延迟。  
数据库负载过高。频繁执行 SELECT 查询来检查用户名唯一性，每个查询需要数据库资源，包括CPU和I/O。  
可扩展性差。数据库对并发连接和资源有限制。如果注册率继续增长，数据库服务器可能难以处理数量增加的传入请求。垂直扩展数据库（向单个服务器添加更多资源）可能成本高昂并且可能有限制。

缓存方案

为了解决数据库调用用户名唯一性检查的性能问题，引入了高效的Redis缓存。

public class UsernameCache {
        
    
        private static final String REDIS_HOST = "localhost";
        private static final int REDIS_PORT = 6379; 
        private static final int CACHE_EXPIRATION_SECONDS = 3600; 
    
        private static JedisPool jedisPool;
    
        // Initialize the Redis connection pool
        static {
        
            JedisPoolConfig poolConfig = new JedisPoolConfig();
            jedisPool = new JedisPool(poolConfig, REDIS_HOST, REDIS_PORT);
        }
    
        // Method to check if a username is unique using the Redis cache
        public static boolean isUsernameUnique(String username) {
        
            try (Jedis jedis = jedisPool.getResource()) {
        
                // Check if the username exists in the Redis cache
                if (jedis.sismember("usernames", username)) {
        
                    return false; // Username is not unique
                }
            } catch (Exception e) {
        
                e.printStackTrace();
                // Handle exceptions or fallback to database query if Redis is unavailable
            }
            return true; // Username is unique (not found in cache)
        }
    
        // Method to add a username to the Redis cache
        public static void addToCache(String username) {
        
            try (Jedis jedis = jedisPool.getResource()) {
        
                jedis.sadd("usernames", username); // Add the username to the cache set
                jedis.expire("usernames", CACHE_EXPIRATION_SECONDS); // Set expiration time for the cache
            } catch (Exception e) {
        
                e.printStackTrace();
                // Handle exceptions if Redis cache update fails
            }
        }
    
        // Cleanup and close the Redis connection pool
        public static void close() {
        
            jedisPool.close();
        }
    }

这个方案最大的问题就是内存占用过大，假如每个用户名需要大约 20 字节的内存。你想要存储10亿个用户名的话，就需要20G的内存。

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

布隆过滤器方案

直接缓存判断内存占用过大，有没有什么更好的办法呢？布隆过滤器就是很好的一个选择。

那究竟什么布隆过滤器呢？  
布隆过滤器的原理（二进制 + 哈希函数）  
假设布隆过滤器由 20位二进制、 3个哈希函数组成，每个元素经过哈希函数处理都能生成一个索引位置。

布隆过滤器的基础操作有两个：添加、查询

**添加元素：** 将每一个哈希函数生成的索引位置都设为 1

**查询元素是否存在：**  
如果有一个哈希函数生成的索引位置不为 1，就代表不存在（100%准确）  
如果每一个哈希函数生成的索引位置都为 1，就代表存在（存在一定的误判率）

![在这里插入图片描述][10428eaadcc943d7a4ed71b99b769d49.png]  
添加、查询的时间复杂度都是：O(k) ，k 是哈希函数的个数  
空间复杂度是：O(m) ，m 是二进制位的个数  
布隆过滤器的误判率（公式）  
误判率 p 受 3 个因素影响：二进制位的个数 m、哈希函数的个数 k、数据规模 n。

误判率 p 的公式：  
![在这里插入图片描述][ace1820c8a34472dbf364c2a71af910b.png]  
已知误判率 p、数据规模 n，求二进制位的个数 m、哈希函数的个数 k：

二进制位的个数 m：  
![在这里插入图片描述][aa663fe804314bc8a974ddb76f05f4c9.png]  
哈希函数的个数 k：  
![在这里插入图片描述][ac41cff6aebd4894bc3b5adf5d378ec9.png]

总结：

布隆过滤器（Bloom Filter）是一种数据结构，用于快速检查一个元素是否存在于一个大型数据集中，通常用于在某些情况下快速过滤掉不可能存在的元素，以减少后续更昂贵的查询操作。布隆过滤器的主要优点是它可以提供快速的查找和插入操作，并且在内存占用方面非常高效。

布隆过滤器的核心思想是使用一个位数组（bit array）和一组哈希函数。

位数组（Bit Array） ：布隆过滤器使用一个包含大量位的数组，通常初始化为全0。每个位可以存储两个值，通常是0或1。这些位被用来表示元素的存在或可能的存在。  
哈希函数（Hash Functions） ：布隆过滤器使用多个哈希函数，每个哈希函数可以将输入元素映射到位数组的一个或多个位置。这些哈希函数必须是独立且具有均匀分布特性。  
那么具体是怎么做的呢？

添加元素：如上图所示，当将字符串“xuyang”，“alvin”插入布隆过滤器时，通过多个哈希函数将元素映射到位数组的多个位置，然后将这些位置的位设置为1。  
查询元素：当要检查一个元素是否存在于布隆过滤器中时，通过相同的哈希函数将元素映射到位数组的相应位置，然后检查这些位置的位是否都为1。如果有任何一个位为0，那么可以确定元素不存在于数据集中。但如果所有位都是1，元素可能存在于数据集中，但也可能是误判。  
本身redis支持布隆过滤器的数据结构，我们用代码简单实现了解一下：

import redis.clients.jedis.Jedis;
    import redis.clients.jedis.JedisPool;
    import redis.clients.jedis.JedisPoolConfig;
    
    public class BloomFilterExample {
        
        public static void main(String[] args) {
        
            JedisPoolConfig poolConfig = new JedisPoolConfig();
            JedisPool jedisPool = new JedisPool(poolConfig, "localhost", 6379);
    
            try (Jedis jedis = jedisPool.getResource()) {
        
                // 创建一个名为 "usernameFilter" 的布隆过滤器，需要指定预计的元素数量和期望的误差率
                jedis.bfCreate("usernameFilter", 10000000, 0.01);
                
                // 将用户名添加到布隆过滤器
                jedis.bfAdd("usernameFilter", "alvin");
                
                // 检查用户名是否已经存在
                boolean exists = jedis.bfExists("usernameFilter", "alvin");
                System.out.println("Username exists: " + exists);
            }
        }
    }

在上述示例中，我们首先创建一个名为 “usernameFilter” 的布隆过滤器，然后使用 bfAdd 将用户名添加到布隆过滤器中。最后，使用 bfExists 检查用户名是否已经存在。

优点：

节约内存空间，相比使用哈希表等数据结构，布隆过滤器通常需要更少的内存空间，因为它不存储实际元素，而只存储元素的哈希值。如果以 0.001 误差概率存储 10 亿条记录，只需要 1.67 GB 内存，对比原来的20G，大大的减少了。  
高效的查找， 布隆过滤器可以在常数时间内（O(1)）快速查找一个元素是否存在于集合中，无需遍历整个集合。  
缺点：

误判率存在：布隆过滤器在判断元素是否存在时，有一定的误判率。这意味着在某些情况下，它可能会错误地报告元素存在，但不会错误地报告元素不存在。  
不能删除元素：布隆过滤器通常不支持从集合中删除元素，因为删除一个元素会影响其他元素的哈希值，增加了误判率。

[10428eaadcc943d7a4ed71b99b769d49.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/eaee8670b491402dbb7b93ca24b38e75.png
[ace1820c8a34472dbf364c2a71af910b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/31761619b787471d91e93f74b1241847.png
[aa663fe804314bc8a974ddb76f05f4c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/814a6d48a80c4c14a3d2d91a08f22273.png
[ac41cff6aebd4894bc3b5adf5d378ec9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/eeee8ef79e5d48d5bfe976961d787bcf.png