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

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

引用

CSDN

1.

https://blog.csdn.net/tMb8Z9Vdm66wH68VX1/article/details/143227356

在当今互联网时代，许多应用程序需要处理数十亿用户的注册需求。如何高效地检查用户名是否已被注册，成为一个重要的技术挑战。本文将探讨三种解决方案：传统的数据库查询、使用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
)
func main() {
    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 client
func initializeRedisClient() *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"
)
func main() {
    // 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? true
Username '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）：如果检查表明一个元素不在集合中，那么这绝对是正确的。

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