网站域名禁止续费,用js做网站登录,济南做网站找大标,无极兼职网前言 不知道大家有没有留意过#xff0c;在使用一些app或者网站注册的时候#xff0c;提示你用户名已经被占用了#xff0c;比如我们熟知的《英雄联盟》有些人不知道取啥名字#xff0c;干脆就叫“不知道取啥名”。 但是有这样困惑的可不止他一个#xff0c;于是就出现了“… 前言 不知道大家有没有留意过在使用一些app或者网站注册的时候提示你用户名已经被占用了比如我们熟知的《英雄联盟》有些人不知道取啥名字干脆就叫“不知道取啥名”。 但是有这样困惑的可不止他一个于是就出现了“不知道取啥名1”...“不知道取啥名99” 需要更换一个这是如何实现的呢你可能想这不是很简单吗去数据库里查一下有没有不就行了吗那么假如用户数量很多达到数亿级别呢这又该如何是好 解决思路 到底有哪些方案呢 数据库可行吗? 有什么缺点呢缓存呢还有什么更好的方法吗 具体实现方案 关系型数据库 遇事不决先想到数据库很多时候数据库虽说不是最好的方案但是都可以成为一种保底方案所以在面试的时候如果想到不到其他方案我们可以首先想到数据库这里所的当然是关系型数据库啦那数据库到底应该怎么实现呢说来也很简单将用户信息的name列设置为唯一索引这样有两个好处首先索引可以提升查询的效率同时还能利用唯一索引的特性将用户的名字自动去重查询的时候直接select id(或name) from user where name 用户名 如果能返回查询结果则说明用户已经存在需要重新写新的名字同时我还要告诉你这句SQL这样写还能避免回表查询这样也会在一定程度上提升查询的效率。 这种方案虽然实现了功能但是这样做会带来一个比较致命的问题那就是查询速度比较慢亿级别数据是很大的这时候还考虑mysql的话他的查询速度将会非常慢这样用户的体验将会非常不好有人可能会说了呀那你可以分库分表呀是的可以这么做但是就算分库分表你还是得扫描整个库表这种做法解决不了根本问题。同时数据库对并发连接和资源有限制。如果注册率继续增长数据库服务器可能难以处理数量增加的传入请求。比如像英雄联盟这种大型游戏突然有什么活动用户大批量涌入进行注册就会出现数据库难以处理持续增长的请求。 使用缓存 试想一下数据库能实现的话我们的缓存可以实现吗 对哦redis天生有set这种类型的数据我们可以设置一个key比如register_user然后每次注册用户直接向缓存添加用户名如果能成功则说明用户不重复不能添加成功则说明用户已经被注册。这些操作都是在缓存中进行的虽然查询速度会比mysql快但是又会引入一个新的问题那就是redis的大key问题。 这里补充一下什么是redis的大key问题: 普遍认同的规范是value 10kb即认定为大 key同时像listsethash 等容器类型的 redis key元素数量 5000即认定为大 key。 那大key会带来什么问题呢 大 key 会带来以下四种影响 客户端超时阻塞由于 Redis 执行命令是单线程处理然后在操作大 key 时会比较耗时那么就会阻塞 Redis从客户端这一视角看就是很久很久都没有响应。 引发网络阻塞每次获取大 key 产生的网络流量较大如果一个 key 的大小是 1 MB每秒访问量为 1000那么每秒会产生 1000MB 的流量这对于普通千兆网卡的服务器来说是灾难性的。 阻塞工作线程如果使用 del 删除大 key 时会阻塞工作线程这样就没办法处理后续的命令。 内存分布不均集群模型在 slot 分片均匀情况下会出现数据和查询倾斜情况部分有大 key 的 Redis 节点占用内存多QPS 也会比较大。 像我们这种业务场景必定是大key无疑了虽然我们也可以设计一些算法将key拆分分成不同的小key但是又有一个新的问题出现了假设我们每个用户名字占20个字节那1亿用户将会耗费20G左右的内存内存是比较珍稀且昂贵的资源我们一下就耗费20g资源能不能想个法子节约一下成本让老板觉得你是个人才以后每次你提离职老板都亲自挽留你并给你涨工资。(你还真别说我有同事就是这么干的而且还真成功了只能羡慕人家技术好啊) 布隆过滤器 直接缓存判断内存占用过大有没有什么更好的办法呢布隆过滤器就是很好的一个选择。 那究竟什么布隆过滤器呢 布隆过滤器Bloom Filter是一种数据结构用于快速检查一个元素是否存在于一个大型数据集中通常用于在某些情况下快速过滤掉不可能存在的元素以减少后续更昂贵的查询操作。 布隆过滤器的主要优点是它可以提供快速的查找和插入操作并且在内存占用方面非常高效。 结构如图所示布隆过滤器的核心思想是使用一个位数组bit array和一组哈希函数。 位数组Bit Array 布隆过滤器使用一个包含大量位的数组通常初始化为全0。每个位可以存储两个值通常是0或1。这些位被用来表示元素的存在或可能的存在。 哈希函数Hash Functions 布隆过滤器使用多个哈希函数每个哈希函数可以将输入元素映射到位数组的一个或多个位置。这些哈希函数必须是独立且具有均匀分布特性。哈希函数的个数越多产生误判的概率就越低。 那么具体是怎么做的呢 布隆过滤器的操作分为添加元素和查询元素两个阶段 添加元素如上图所示当将字符串“name1”“name2”插入布隆过滤器时通过多个哈希函数将元素映射到位数组的多个位置然后将这些位置的位设置为1。 查询元素当要检查一个元素是否存在于布隆过滤器中时通过相同的哈希函数将元素映射到位数组的相应位置然后检查这些位置的位是否都为1。如果有任何一个位为0那么可以确定元素不存在于数据集中。但如果所有位都是1元素可能存在于数据集中但也可能是误判。 说了那么多他的优点在哪呢 优点 节约内存空间相比使用哈希表等数据结构布隆过滤器通常需要更少的内存空间因为它不存储实际元素而只存储元素的哈希值。 有同学可能要问了呀你说更少就更少吗怎么证明他确实省像京东口号一样多快好省 这里公司可以参考公式 m -(n * ln(p)) / (ln(2)^2) 其中m 是所需要的位数n 是过滤器中元素的数量p 是期望的误判率。 举个例子 在这里给大家一个案例现在有1亿用户我们把误判率设为0.001在给定的条件下其中 n 是10^81亿p 是0.0010.1%我们可以将这些值带入公式中m -(10^8 * ln(0.001)) / (ln(2)^2) 运算后我们得到的结果 m 大约为2.88*10^9位。为了将位转换为字节1字节 8位我们需要除以8m_in_bytes m / 8这将得到大约3.6*10^8字节或者说约 0.36 GB 的内存需求。 相比原理的20G一下减少了19G还多而且查询的时候也是O(1)的时间复杂度对其他实现方案来说这将是一场屠杀 难道只有优点吗 缺点 布隆过滤器在判断元素是否存在时有一定的误判率。这意味着在某些情况下它可能会错误地报告元素存在但不会错误地报告元素不存在。不能删除元素布隆过滤器通常不支持从集合中删除元素因为删除一个元素会影响其他元素的哈希值增加了误判率。 参看文献 https://web.archive.org/web/20110930114037/http://en.wikipedia.org/wiki/Bloom_filter#Probability_of_false_positives https://blog.csdn.net/J_bean/article/details/135996254 https://juejin.cn/post/7293786247655129129 https://blog.csdn.net/weixin_62827806/article/details/136290340 本文由 mdnice 多平台发布
