面試官問，如何在十億級別用戶中檢查用戶名是否存在？
作者：JAVA旭陽
Redis 布隆過濾器的方案為大數(shù)據(jù)量下唯一性驗證提供了一種基于內(nèi)存的高效解決方案，它需要在內(nèi)存消耗和錯誤率之間取得一個平衡點。當(dāng)然布隆過濾器還有更多應(yīng)用場景，比如防止緩存穿透、防止惡意訪問等。
前言
不知道大家有沒有留意過，在使用一些app注冊的時候，提示你用戶名已經(jīng)被占用了，需要更換一個，這是如何實現(xiàn)的呢？你可能想這不是很簡單嗎，去數(shù)據(jù)庫里查一下有沒有不就行了嗎，那么假如用戶數(shù)量很多，達(dá)到數(shù)億級別呢，這又該如何是好？
數(shù)據(jù)庫方案
第一種方案就是查數(shù)據(jù)庫的方案，大家都能夠想到，代碼如下：
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.");
}
}
}這種方法會帶來如下問題：
- 性能問題，延遲高 。 如果數(shù)據(jù)量很大，查詢速度慢。另外，數(shù)據(jù)庫查詢涉及應(yīng)用程序服務(wù)器和數(shù)據(jù)庫服務(wù)器之間的網(wǎng)絡(luò)通信。建立連接、發(fā)送查詢和接收響應(yīng)所需的時間也會導(dǎo)致延遲。
- 數(shù)據(jù)庫負(fù)載過高。頻繁執(zhí)行 SELECT 查詢來檢查用戶名唯一性，每個查詢需要數(shù)據(jù)庫資源，包括CPU和I/O。
- 可擴展性差。數(shù)據(jù)庫對并發(fā)連接和資源有限制。如果注冊率繼續(xù)增長，數(shù)據(jù)庫服務(wù)器可能難以處理數(shù)量增加的傳入請求。垂直擴展數(shù)據(jù)庫（向單個服務(wù)器添加更多資源）可能成本高昂并且可能有限制。
緩存方案
為了解決數(shù)據(jù)庫調(dià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();
}
}這個方案最大的問題就是內(nèi)存占用過大，假如每個用戶名需要大約 20 字節(jié)的內(nèi)存。你想要存儲10億個用戶名的話，就需要20G的內(nèi)存。
總內(nèi)存 = 每條記錄的內(nèi)存使用量 * 記錄數(shù) = 20 字節(jié)/記錄 * 1,000,000,000 條記錄 = 20,000,000,000 字節(jié) = 20,000,000 KB = 20,000 MB = 20 GB
布隆過濾器方案
直接緩存判斷內(nèi)存占用過大，有沒有什么更好的辦法呢？布隆過濾器就是很好的一個選擇。
那究竟什么布隆過濾器呢？
布隆過濾器（Bloom Filter）是一種數(shù)據(jù)結(jié)構(gòu)，用于快速檢查一個元素是否存在于一個大型數(shù)據(jù)集中，通常用于在某些情況下快速過濾掉不可能存在的元素，以減少后續(xù)更昂貴的查詢操作。布隆過濾器的主要優(yōu)點是它可以提供快速的查找和插入操作，并且在內(nèi)存占用方面非常高效。
具體的實現(xiàn)原理和數(shù)據(jù)結(jié)構(gòu)如下圖所示：
圖片
布隆過濾器的核心思想是使用一個位數(shù)組（bit array）和一組哈希函數(shù)。
- 位數(shù)組（Bit Array） ：布隆過濾器使用一個包含大量位的數(shù)組，通常初始化為全0。每個位可以存儲兩個值，通常是0或1。這些位被用來表示元素的存在或可能的存在。
- 哈希函數(shù)（Hash Functions） ：布隆過濾器使用多個哈希函數(shù)，每個哈希函數(shù)可以將輸入元素映射到位數(shù)組的一個或多個位置。這些哈希函數(shù)必須是獨立且具有均勻分布特性。
那么具體是怎么做的呢？
- 添加元素：如上圖所示，當(dāng)將字符串“xuyang”，“alvin”插入布隆過濾器時，通過多個哈希函數(shù)將元素映射到位數(shù)組的多個位置，然后將這些位置的位設(shè)置為1。
- 查詢元素：當(dāng)要檢查一個元素是否存在于布隆過濾器中時，通過相同的哈希函數(shù)將元素映射到位數(shù)組的相應(yīng)位置，然后檢查這些位置的位是否都為1。如果有任何一個位為0，那么可以確定元素不存在于數(shù)據(jù)集中。但如果所有位都是1，元素可能存在于數(shù)據(jù)集中，但也可能是誤判。
本身redis支持布隆過濾器的數(shù)據(jù)結(jié)構(gòu)，我們用代碼簡單實現(xiàn)了解一下：
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()) {
// 創(chuàng)建一個名為 "usernameFilter" 的布隆過濾器，需要指定預(yù)計的元素數(shù)量和期望的誤差率
jedis.bfCreate("usernameFilter", 10000000, 0.01);
// 將用戶名添加到布隆過濾器
jedis.bfAdd("usernameFilter", "alvin");
// 檢查用戶名是否已經(jīng)存在
boolean exists = jedis.bfExists("usernameFilter", "alvin");
System.out.println("Username exists: " + exists);
}
}
}在上述示例中，我們首先創(chuàng)建一個名為 "usernameFilter" 的布隆過濾器，然后使用 bfAdd 將用戶名添加到布隆過濾器中。最后，使用 bfExists 檢查用戶名是否已經(jīng)存在。
優(yōu)點：
- 節(jié)約內(nèi)存空間，相比使用哈希表等數(shù)據(jù)結(jié)構(gòu)，布隆過濾器通常需要更少的內(nèi)存空間，因為它不存儲實際元素，而只存儲元素的哈希值。如果以 0.001 誤差概率存儲 10 億條記錄，只需要 1.67 GB 內(nèi)存，對比原來的20G，大大的減少了。
- 高效的查找， 布隆過濾器可以在常數(shù)時間內(nèi)（O(1)）快速查找一個元素是否存在于集合中，無需遍歷整個集合。
缺點：
- 誤判率存在：布隆過濾器在判斷元素是否存在時，有一定的誤判率。這意味著在某些情況下，它可能會錯誤地報告元素存在，但不會錯誤地報告元素不存在。
- 不能刪除元素：布隆過濾器通常不支持從集合中刪除元素，因為刪除一個元素會影響其他元素的哈希值，增加了誤判率。
總結(jié)
Redis 布隆過濾器的方案為大數(shù)據(jù)量下唯一性驗證提供了一種基于內(nèi)存的高效解決方案，它需要在內(nèi)存消耗和錯誤率之間取得一個平衡點。當(dāng)然布隆過濾器還有更多應(yīng)用場景，比如防止緩存穿透、防止惡意訪問等。
責(zé)任編輯：武曉燕
來源：
JAVA旭陽
