专栏名称: 数据派THU

本订阅号是“THU数据派”的姊妹账号，致力于传播大数据价值、培养数据思维。

独家｜如何在数十亿用户中高效检索账号名是否已经存在？

数据派THU · 公众号 · 大数据 · 2024-10-24 17:00

正文

作者：Aditi Mishra





    
翻译：wwl
校对：zrx
本文约3000字，建议阅读7分钟
在这篇文章中，我们将探讨三种方法：传统的数据库查询、使用Redis的缓存策略以及使用布隆过滤器的优化方法。

简介

你是否遇到过注册APP时，发现你偏好的账户名已经被注册了？虽然这看起来可能只是一个小小的麻烦，但对于处理大量用户的应用程序来说，这是一个重大的技术挑战。判断用户名是否可用可以通过几种方式来实现，每种方式都有其优势和劣势。在这篇文章中，我们将探讨三种方法：传统的数据库查询、使用Redis的缓存策略以及使用布隆过滤器的优化方法。

方法1：数据库查询

检索账户名是否存在，最直接的方法是查询数据库。但是，随着用户量到达百万或数十亿，这种方法可能会变得低效，以下是主要缺点：

1.高延迟：在查询大型数据库时，由于延迟增加，性能可能会受到影响。每个查询都涉及应用程序和数据库服务器之间的网络通信，增加了延迟。

2.数据库负载重：频繁执行SELECT查询以检查用户名的唯一性会消耗大量的数据库资源，包括CPU和I/O。这可能导致瓶颈，特别是在高峰时段

3.扩展性问题：数据库在处理大量并发连接方面存在固有的限制。随着用户注册量的增加，数据库可能难以跟上节奏，导致性能下降。垂直扩展数据库（增加更多资源）可能成本高昂，并且有其局限性。

方法2：使用Redis的缓存策略

为了缓解数据库查询的性能问题，可以引入一个缓存层，例如Redis。这涉及将用户名存储在Redis hash map中，从而实现更快的检查。

代码实现：

package main
import ("fmt""github.com/go-redis/redis/v8""context")
const ( USERNAME_HASH_MAP = "username_records"// Redis hash map name to store user information)
funcmain() { ctx := context.Background()
// Create a Redis client client := initializeRedisClient()
// Add a username to the hash map err := client.HSet(ctx, USERNAME_HASH_MAP, "john_doe", "userInfo").Err() // "userInfo" could be a JSON string, UUID, etc.if err != nil {  fmt.Println("Error adding username:", err)return }
// Check if a username exists isPresent, err := client.HExists(ctx, USERNAME_HASH_MAP, "john_doe").Result()if err != nil {  fmt.Println("Error checking username existence:", err)return } fmt.Printf("Username 'john_doe' exists? %v\n", isPresent)
// Check for a non-existent username isPresent, err = client.HExists(ctx, USERNAME_HASH_MAP, "jane_doe").Result()if err != nil {  fmt.Println("Error checking username existence:", err)return } fmt.Printf("Username 'jane_doe' exists? %v\n", isPresent)
// Close the Redis client connection err = client.Close()if err != nil {  fmt.Println("Error closing Redis client:", err) }}
// Helper function to create a Redis clientfuncinitializeRedisClient() *redis.Client {return redis.NewClient(&redis.Options{  Addr:     "127.0.0.1:6379", // Adjust to your Redis address  Password: "yourpassword",   // Provide your Redis password if any  DB:       0,                // use default DB })}

Redis缓存策略的挑战

内存消耗：每个存储在Redis中的用户名大约消耗15字节。对于十亿个用户名，这将需要大约15GB的内存。

扩展性：虽然比直接数据库查询更快，但在内存中存储大型数据集可能会很昂贵，并且可能需要谨慎管理以避免资源耗尽。

方法3 布隆过滤器：

当内存效率至关重要时，布隆过滤器（Bloom Filters）提供了一个有效的解决方案。布隆过滤器是一种空间效率高的概率型数据结构，它支持快速检查一个元素（如用户名）是否属于一个集合。它的问题在于，偶尔可能产生假阳性，即显示一个用户名已经存在，而实际上并不存在。

布隆过滤器是一种聪明且空间效率高的工具，用于检查一个元素是否属于一个集合。当你想要避免存储大量数据时，它尤其有用。但是，它的缺点是可能偶尔会告诉你一个元素在集合中，而实际上它并不在（假阳性），但它永远不会错过实际在集合中的项目（假阴性）。

它是怎么工作的？

布隆过滤器使用了bit 数组和几个hash函数
当你添加一个元素（比如用户名）时，过滤器会使用哈希函数将数组中的某些位翻转成1
要检查一个元素是否存在，它会将元素通过同样的哈希函数处理。如果所有对应的位都是1，那么元素可能在该集合中。如果任何一位是0，那么元素肯定不在该集合中。

为什么使用布隆过滤器？

效率：节省内存，能快速检查元素是否在集合中。
实用：可以减少不必要的数据库查询，防止网络服务器重复检查。

简而言之，当你需要快速、内存高效的成员资格测试时，布隆过滤器是一个强大的工具，只要你能够处理偶尔出现的假阳性情况。

以下是如何使用bloom包在Go语言中实现一个布隆过滤器的示例：

package main
import ("fmt"// https://pkg.go.dev/github.com/bits-and-blooms/bloom/v3#section-readme"github.com/bits-and-blooms/bloom/v3")
funcmain() {// Initialize a Bloom Filter filter := bloom.New(20*1000*1000, 5) // Capacity: 20 million, 5 hash functions
// Add a username to the Bloom Filter filter.AddString("john_doe")
// Check if a username exists exists := filter.TestString("john_doe") fmt.Printf("Username 'john_doe' exists? %v\n", exists)
// Check for a non-existent username exists = filter.TestString("jane_doe") fmt.Printf("Username 'jane_doe' exists? %v\n", exists)}

输出：

Username'john_doe' exists? trueUsername 'jane_doe' exists? False

Bloom Filters的可视化解释

下图直观地展示了Bloom Filter是怎么工作的。

a : 插入一个序列

序列“ACCGTAG”，检查这个序列是否在我们的集合中存在
k-mers：序列被切分成更小的部分，称为“k-mers”，类似分块或者分片。例如“ACCG”，“CCGT”，“CGTA“，“GTAG”
Hash k-mers，每个k-mers通过一些hash函数，这些hash 函数，接收k-mers，映射到bit array中的特定位置
Setting bits：对于每个k-mer，bit数组中的对应bit被设置为1。Bit 数组初始每个元素都是0，当我们添加了k-mers，对应的bit设置为1.

b : 检索一个序列

查询“CGTAT”：现在，在集合中检查是否存在序列“CGTAT”
K-mers：像前边一样，序列被切分为k-mers，如“CGTA”，“GTAT“
检索bits：这些k-mers经过hash function，我们检查bit array中的对应bit
如果对应的bit都是1，就像“CGTA“，则证明这个序列可能在集合中
如果有一个bit是0，如“GTAT“，则说明，这个序列一定不在集合中

总结

布隆过滤器的优点：这种方法在内存使用上高效，并且快速检查某物是否可能存在于一个集合中。
假阳性（False Positives）：有时，它可能错误地指示一个元素存在于集合中，而实际上并不存在（这就是“假阳性”）。
确定阴性（Definite Negatives）：如果检查表明一个元素不在集合中，那么这绝对是正确的。

这个图表直观地展示了如何使用布隆过滤器高效地检查数据在集合中的存在与否，使得它们在许多场景下都非常有用，比如过滤或加速。

原文标题：

How to Efficiently Check If a Username Exists Among Billions of Users

原文链接：

https://medium.com/@aditimishra_541/how-to-efficiently-check-if-a-username-exists-among-billions-of-users-7ed1e5c60489

编辑：王菁

翻译组招募信息

工作内容：需要一颗细致的心，将选取好的外文文章翻译成流畅的中文。如果你是数据科学/统计学/计算机类的留学生，或在海外从事相关工作，或对自己外语水平有信心的朋友欢迎加入翻译小组。

你能得到：定期的翻译培训提高志愿者的翻译水平，提高对于数据科学前沿的认知，海外的朋友可以和国内技术应用发展保持联系，THU数据派产学研的背景为志愿者带来好的发展机遇。

其他福利：来自于名企的数据科学工作者，北大清华以及海外等名校学生他们都将成为你在翻译小组的伙伴。

点击文末“阅读原文”加入数据派团队~

转载须知

如需转载，请在开篇显著位置注明作者和出处（转自：数据派ID：DatapiTHU），并在文章结尾放置数据派醒目二维码。有原创标识文章，请发送【文章名称-待授权公众号名称及ID】至联系邮箱，申请白名单授权并按要求编辑。

发布后请将链接反馈至联系邮箱（见下方）。未经许可的转载以及改编者，我们将依法追究其法律责任。

关于我们

数据派THU作为数据科学类公众号，背靠清华大学大数据研究中心，分享前沿数据科学与大数据技术创新研究动态、持续传播数据科学知识，努力建设数据人才聚集平台、打造中国大数据最强集团军。

新浪微博：@数据派THU

微信视频号：数据派THU

今日头条：数据派THU

点击“阅读原文”拥抱组织