面试官问,如何在十亿级别用户中检查用户名是否存在?

2024-01-21

面试官问,如何在十亿级别用户中检查用户名是否存在?

前言

  • 不知道大家有没有留意过,在使用一些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

布隆过滤器方案

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

  • 那究竟什么布隆过滤器呢?

  • 布隆过滤器 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)) 快速查找一个元素是否存在于集合中,无需遍历整个集合。

  • 缺点:

  • 误判率存在 :布隆过滤器在判断元素是否存在时,有一定的误判率。这意味着在某些情况下,它可能会错误地报告元素存在,但不会错误地报告元素不存在。

  • 不能删除元素 :布隆过滤器通常不支持从集合中删除元素,因为删除一个元素会影响其他元素的哈希值,增加了误判率。

总结

  • Redis 布隆过滤器的方案为大数据量下唯一性验证提供了一种基于内存的高效解决方案,它需要在内存消耗和错误率之间取得一个平衡点。当然布隆过滤器还有更多应用场景,比如防止缓存穿透、防止恶意访问等。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

面试官问,如何在十亿级别用户中检查用户名是否存在? 的相关文章

  • UcanaccessSQLException:UCAExc:::3.0.1 表达式的数据类型不是布尔值

    我有一张如下图所示的表格 我需要获取其库尔德语单词包含的所有英语单词 r 所以我不能使用 select English from Table1 where Kurdish like 因为它还接受另一个单词中的子字符串 例如 当我尝试在查询中
  • 检查从 arrayadapter 获取的复选框

    我有标题清单 CheckBox 我想控制默认检查哪一个 所以我试图获得正确的视图并检查它 但由于某种原因它不起作用 知道为什么吗 form checkbox item xml
  • Java:while循环冻结程序

    我正在制作一个游戏 我需要每 3 秒更新一次 JProgressBar 为此 我使用 while 循环 问题是我的程序由于 while 循环而冻结 我在其他问题中读到它 他们没有帮助我解决这个问题 我不知道如何解决 这是我的代码 publi
  • 从另一个进程捕获 system.out 消息

    我有一个 JVM 1 它启动 JVM 2 我希望能够在 JVM 1 中监视来自 JVM 2 的 System out println 调用 直接的方法是 JVM A 执行系统命令来启动 JVM B 然后 JVM A 读取 B 的所有输出 S
  • 如何将完整的日期格式拆分为日期和时间?

    我有很多格式为我的示例所示的字符串 我必须解析它们 我正在尝试确定今天是哪根弦 我的问题是 时间快到了 我只需要比较那个日期 接下来我想检查时间是否在 after 和 before 的两个时间戳 HH mm ss 之间 但存在问题 日期几乎
  • Glassfish 4 - JDBC 领域

    Glassfish 4 中的密码加密算法和摘要算法有什么区别 因为Password加密算法不能为空 所以我使用了MD5 Encoding使用了Hex 摘要算法为空 因此默认为 SHA 256 但是 如果我使用 JAAS 制作一个简单的登录应
  • 模式更新后 jOOQ 生成的类的运行时验证?

    我用org jooq util DefaultGenerator在构建过程中生成 jOOQ 类来表示我的数据库模式 当应用程序运行时 架构预计会在应用程序不知情的情况下发生更改 此类更改可能与已生成的代码兼容 也可能不兼容 如何在运行时检测
  • AMQP Spring 集成错误处理

    我的集成流程如下所示 Bean public IntegrationFlow auditFlow Qualifier eventLoggingConnectionFactory ConnectionFactory connectionFac
  • Java 表达式树 [关闭]

    Closed 这个问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 是否有相当于 net的 LINQ 下的表达式树JVM 我想实现一些类似 LINQ 的代码结构Scala
  • 我可以使用 Selenium Webdriver 测试元素的顺序吗?

    有一个表单 其中有 3 个字段 具有 3 个不同的 ID fieldset div div fieldset
  • Log4j 2.0 中发现 ClassNotFoundException

    我已经设置了 log4j12 api beta2 jar 的构建路径 但它给出了 以下错误请帮我解决这个问题我的代码如下 java 文件 package com sst log4j class Product private int pro
  • Eclipse Juno 指标插件

    Eclipse JUNO 版本有哪些 Eclipse 指标插件 我尝试了一些通用指标插件 但没有一个能够在 Eclipse 的 JUNO 版本中正常运行 差点忘了 我们正在使用 Java 作为编程语言 我想要诸如圈复杂度 代码行数 方法长度
  • “强制更新快照/版本” - 这是什么意思

    在 Maven 项目中 选择 更新项目 时 有一个名为 强制更新快照 版本 的选项 它有什么作用 强制更新快照 版本 就像运行以下命令 mvn U install U 也可以用作 update snapshot 看here http boo
  • Web 服务客户端的 AXIS 与 JAX-WS

    我决定用Java 实现Web 服务客户端 我已经在 Eclipse 中生成了 Axis 客户端 并使用 wsimport 生成了 JAS WS 客户端 两种解决方案都有效 现在我必须选择一种来继续 在选择其中之一之前我应该 考虑什么 JAX
  • 使用Powershell访问远程Oracle数据库

    我需要能够连接到我的网络上基于 Windows 7 的 Oracle 服务器 32 位 Oracle XE 我需要连接的机器运行 Windows 7 64 位 两台机器上都安装了 Powershell 我已在 64 位计算机上安装了 Ora
  • 在Java内存管理中,“PS”代表什么?

    每当我看到 Java 中对内存的引用时 各种空格总是以 PS 为前缀 PS 是什么意思 它开始困扰我 到目前为止我唯一的猜测是 泳池空间 但这将是多余的 例子 PS伊甸园空间 PS 幸存者空间 PS 终身空间 老一代 PS Perm Gen
  • java mysql 准备好的语句

    我正在尝试使用 java 向数据库中进行简单的插入 它告诉我我的 sql 语法已关闭 但是 当我复制打印出来的字符串并将其放入 phpmyadmin 中的 sql 命令中时 它会正确执行该命令 并且我似乎无法弄清楚 java 中的字符串查询
  • 背景图像隐藏其他组件,例如按钮标签等,反之亦然

    如何解决此代码中组件的隐藏问题 代码运行没有错误 但背景图片不显示 如何更改代码以获取背景图像 使用验证方法时 它在validation 中创建错误 public class TEST public TEST String strm Jan
  • Android Webview:无法调用确定的可见性() - 从未见过 pid 的连接

    我有一个 Android Webview 当我单击链接下载文件 pdf 图像等 时 我收到一条错误消息 Error message Cannot call determinedVisibility never saw a connectio
  • 将其元素添加到另一个列表后清除列表

    我正在做一个程序 它获取更多句子作为参数 我制作了 2 个列表 一个称为 propozitie 其中包含每个句子 另一个称为 propozitii 其中包含所有句子 问题是 当我在遇到 后清除 propozitie 列表时 它也会清除 pr

随机推荐

  • CAP与BASE理论

    CAP与BASE理论 CAP 一个分布式系统最多只能同时满足一致性 Consistency 可用性 Availability 和分区容错性 Partition tolerance 这三项中的两项 C一致性 状态的一致性 缓存 数据库 集群等
  • 图片翻译在线怎么用?分享翻译软件给你

    作为一个不擅长学习语言的人 我真是要被生活中似乎无处不在的英语搞蒙了 想象一下 你正在逛商场 想买一瓶洗护用品 拿起来却看到商品上满是看不懂英文说明 是不是一头雾水 或者 你在浏览社交媒体时 看到一张充满英文的趣味图片 却因为语言障碍而错过
  • 挖掘知识的宝藏:如何利用在线资源提升个人技能

    在这个信息爆炸的时代 互联网已经成为我们获取知识 提升技能的重要途径 无论是学习编程 提高语言能力 还是了解新的行业趋势 网络资源都为我们提供了无限可能 本文将探讨如何有效利用在线资源进行自我提升 一 选择合适的在线学习平台 首先 我们需要
  • 电脑操作系统的发展史:从初级到高级的演变

    自电脑诞生以来 操作系统作为其重要组成部分 不断推动着电脑技术的进步与发展 本文将带您回顾电脑操作系统的发展历程 探究其在不同阶段的特点与影响 一 早期操作系统 真空管与批处理 在电脑诞生初期 真空管技术占主导地位 此时的操作系统尚未形成完
  • 人工智能 AI 如何让我们的生活更加便利

    每个人都可以从新技术中获益 一想到工作或生活更为便利 简捷且拥有更多空余时间 谁会不为之高兴呢 借助人工智能 每天能够多一些空余时间 或丰富自己的业余生活 为培养日常兴趣爱好增添一点便利 从电子阅读器到智能家居 再到植物识别应用和智能室内花
  • 鸿蒙开发Flex、栅格布局详解

    Flex弹性布局 一 direction 1 FlexDirection Row 主轴为水平方向 子组件从起始端沿着水平方向开始排布 2 FlexDirection RowReverse 主轴为水平方向 子组件从终点端沿着FlexDirec
  • 独家 | 鸿蒙(HarmonyOS)开发详细学习笔记免费分享

    前言 华为宣布 将在1月18日 在北京 上海 杭州 南京 成都 厦门 武汉 长沙 8 大城市同时召开大会 届时将揭秘鸿蒙生态和 HarmonyOS NEXT 进阶新篇章 简单的来说就是 纯血鸿蒙系统 即将彻底揭晓 鸿蒙系统自推出来以来 就一
  • SpringBoot中整合ElasticSearch快速入门以及踩坑记录

    场景 若依前后端分离版手把手教你本地搭建环境并运行项目 若依前后端分离版手把手教你本地搭建环境并运行项目 本地运行若依前后端分离 CSDN博客 参考上面搭建项目 ElaticSearch Elasticsearch 是java开发的 基于
  • 会议设备:提升会议体验与效率的关键

    在当今高度信息化的社会 会议已成为企业 机构和团队之间交流与合作的重要方式 而会议设备的选择与使用 对于提升会议的体验与效率具有举足轻重的地位 本文将详细探讨会议设备的重要性 以及如何选择和使用合适的会议设备 以实现高效 顺畅的沟通 首先
  • Android Studio Android Flutter问题记录 - UNABLE TO FIND BUNDLED JAVA VERSION

    前言 有个紧急问题需要修复 本以为很快就能解决继续休假 没想到项目打开运行后Android端跑不起来了 iOS端正常运行 这就有点莫名其妙 明明放假前还是没问题的 难道我拉取的最新代码有问题 不会吧 谁放假还敲代码啊 樂 看了下最新的提交记
  • 30天精通Nodejs--第二十二天:express-认证和授权

    目录 引言 理解JWT及其工作原理 安装与引入JWT库 生成JWT令牌 验证JWT令牌 注意事项与最佳实践 结语 引言 在现代Web应用开发中 JSON Web Tokens JWT 作为一种轻量级 自包含且安全的标准 已被广泛用于实现用户
  • Kubernetes (十一) 存储——Secret配置管理

    一 简介 从文件创建 echo n admin gt username txt echo n westos gt password txt kubectl create secret generic db user pass from fi
  • AI在保护环境、应对气候变化中的作用

    对于AI生命周期数据领域的全球领导者而言 暂时搁置我们惯常的AI见解和AI生命周期数据内容产出 来认识诸如世界地球日这样的自然环境类活动日 似乎是个奇怪的事情 我们想要知道 数据是否真的会影响我们的地球环境 简而言之 是 确实如此 但作为一
  • 数据加密保障数据安全

    一 目标 1 1 预研需求 数据加密是安全领域中常用的安全措施 它们的主要作用是保护数据的机密性和完整性 以防止未经授权的访问 窃取 篡改或泄漏敏感信息 数据传输加密 保护敏感数据在传输过程中的安全 当数据通过网络传输时 它们可能会经过多个
  • AI在广告中的应用——预测性定位和调整

    营销人员的工作就是在恰当的时间将适合的产品呈现在消费者面前 从而增加他们购买的可能性 随着时间的推移 营销人员能够深入挖掘越来越精准的客户细分市场 他们不仅具备了实现上述目标的能力 而且这种能力还在呈指数级提升 在AI技术帮助下 现在的营销
  • Kubernetes (十二) 存储——Volumes配置管理

    一 卷的概念 官方地址 卷 Kubernetes https v1 24 docs kubernetes io zh cn docs concepts storage volumes 二 卷的类型及使用 emptyDir卷 1 创建编辑文件
  • JVM优化之 -Xss -Xms -Xmx -Xmn 参数设置

    JVM优化之 Xss Xms Xmx Xmn 参数设置 XmnXmsXmxXss有什么区别 Xmn Xms Xmx Xss都是JVM对内存的配置参数 我们可以根据不同需要区修改这些参数 以达到运行程序的最好效果 Xms 堆内存的初始大小 默
  • 图片编辑软件有哪些好用的?这几款快收藏吧

    你有没有过这样的经历 精心拍摄了一组照片 却发现有些角度不对 光线不够好 或者想要给图片加上一些特别的滤镜效果来达到心目中的样子 这时 你就需要一款合适的图片编辑软件了 但是 市面上的图片编辑软件琳琅满目 哪一款才是适合自己的呢 别担心 今
  • 30天精通Nodejs--第二十一天:express-依赖注入

    目录 引言 Express中的模块化实践 依赖注入 什么是依赖注入 Express中实现依赖注入 结语 引言 在构建大型且复杂的Node js Express应用程序时 良好的架构设计至关重要 模块化编程可以帮助我们把代码分解为可复用 易维
  • 面试官问,如何在十亿级别用户中检查用户名是否存在?

    面试官问 如何在十亿级别用户中检查用户名是否存在 前言 不知道大家有没有留意过 在使用一些app注册的时候 提示你用户名已经被占用了 需要更换一个 这是如何实现的呢 你可能想这不是很简单吗 去数据库里查一下有没有不就行了吗 那么假如用户数量