场景题 | 月亮湾

40亿个QQ号，限制1G内存，如何去重？

典型回答 10位数字的QQ号，想要去重，又不给那么多的空间，该如何实现呢？ 40亿个unsigned int，如果直接用内存存储的话，需要： 4*4000000000 /1024/1024/1024 = 14.9G ，考虑到其中有一些重复的话，那1G的空间也基本上是不够用的。想要实现这个功能，可以借助位图。 ✅什么是BitMap？有什么用？使用位图的话，一个数字只需要占用1个bit，那么40亿个数字也就是： 4000000000 * 1 /8 /1024/1024 = 476M 相比于之前的14.9G来说，大大的节省了很多空间。但是其实，如果有 bitmap 存数字的话，就不是存4000000000个了，因为数字最大有10位数，其实是需要9999999999（10个9）个bit 用来存储，那其实是： 10000000000*1/8/1024/1024=1192M，那也是比14.9G 要小很多的。比如要把我的QQ号"907607222"放到Bitmap中，就需要找到第907607222这个位置，然后把他设置成1就可以了。这样，把40亿个数字都放到Bitmap之后，所有位置上是1的表示存在，不为1的表示不存在，相同的QQ号只需要设置一次1就可以了，那么，最终就把所有是1的数字遍历出来就行了。

5亿条数据放到布隆过滤器中，大概需要多大内存？如何估算？

典型回答 ✅什么是布隆过滤器，实现原理是什么？如果你看过布隆过滤器的实现原理，那么就应该知道，他能占用多少内存，不仅仅取决于他要存多少数据进去，还取决于你设置的误判率是多少，以及你设置的bitset的长度，以及用到的hash函数的个数。每一个数据指标不一样最终的结果可能都不一样的。肯定是误判率越低，占的内存越大了。有一个比较通用的内存估算公式：布隆过滤器的内存占用（位数组大小 **m**）与元素数量 **n** 和预期误判率 **p** 满足以下关系：公式推导过程：https://developer.aliyun.com/article/743706 ，就不展开写了，大家可以去看下。 m: 位数组大小（单位：bit） n: 元素数量 p: 预期误判率假设存储5亿数据，误判率是0.001，那么：n = 500000000，p=0.001，那么ln(0.001)=−6.9078，(ln2)^2=0.4805，带入公式： 0.4805 这么多个bit转成G的话，那么就是 7187304890.74/8/1024/1024/1024 = 0.836G 那么总结下，如果是千分之一的误判率，5亿数据占用内存大概0.836G，既856M，如果误判率是百分之一的话，占用内存大概是0.557G，既571M。

A线程获取Redis分布式锁，但那一刻做了主从的切换，B线程能获取到锁吗？

典型回答这个问题，其实本质上想问的就是Redis分布式锁的单点问题。问题是这样的：当使用集群模式部署的时候，如果master一个客户端在master节点加锁成功了，然后没来得及同步数据到其他节点上，他就挂了，那么这时候如果选出一个新的节点，再有客户端来加锁的时候，就也能加锁成功，因为数据没来得及同步，新的master会认为这个key是不存在的。所以，基于以上的情况来说，A线程获取Redis分布式锁，但那一刻做了主从的切换，B线程能不能获取到锁有以下几种情况： 1、如果已完成主从同步，那么B线程无法加锁成功。 2、如果未来得及做主从同步，那么B线程可以加锁成功。扩展知识如何避免单点问题的发生？ ✅什么是RedLock，他解决了什么问题？ RedLock被废弃 ✅Redisson 中为什么要废弃 RedLock，该用啥？

Redis和MySQL的一次普通查询，RT在什么范围内是合理的？

典型回答 Redis是基于内存的，MySQL是基于磁盘的（非Memory引擎），所以Redis要比MySQL快，一次RT要分两部分，一部分是网络交互的耗时，一部分是命令（SQL）执行的耗时。但是不管怎么说，Redis都要比MySQL快得多。先说下纯命令（SQL）执行耗时情况。 Redis命令执行耗时 Redis的简单命令（如GET、SET）执行耗时大概在0.1ms~1ms（100-1000微秒）。复杂命令（如**ZADD**、**HSET**）的执行耗时大概在1ms~5ms左右。下图是阿里云给出的Redis和云上服务的对比图，可以看到，Redis的P99基本都在1毫秒以内的。（测试环境：标准架构（双副本），不启用集群， 8 GB）测评地址：https://help.aliyun.com/zh/redis/support/performance-whitepaper-of-community-edition-instances MySQL的SQL运行耗时首先，对于MySQL来说，命中索引、命中buffer pool，无join等等都对性能有很大的影响。但是还是能给出一些大致的范围的。如果一个查询，直接命中buffer pool并且通过主键查询，那么可能在2ms以内也能返回。比Redis慢不了多少。如果没有命中buffer pool，就需要去磁盘读取，这时候就需要更多的耗时了，一般我们认为一次查询如果超过1秒钟算是慢SQL了，所以，一个正常的查询语句，应该在1000ms内返回，我们普遍认为200ms-500ms以内算是比较好的一个性能了。以上说的不包括任何的网络交互的时长，还要再加上网络耗时，那么网络耗时怎么算的呢？网络耗时一次HTTP交互过程包括DNS解析、TCP握手、LS握手、HTTP请求、HTTP响应几个步骤了。那么一次请求（非HTTP 3.0的情况）就是： 1 2 3 4 5 DNS解析（5ms~300ms） → TCP握手（1.5×RTT） → TLS握手（1×RTT） → HTTP请求/响应（1×RTT）总耗时 = DNS + 3.5×RTT 大概3.5个RTT加上DNS解析的耗时了。 ...

一次RPC请求，客户端显示超时，但是服务端不超时，可能是什么原因？

典型回答我们都知道，一次RPC调用是从客户端发起，然后请求到服务端，再响应给客户端的过程。一般来说，一次调用过程中，主要的耗时都是在服务端的同步代码执行上。但是，有的时候，会非常诡异的出现客户端显示超时，但服务端并未超时的情况。一般就是客户端通过监控报警报出来某个接口存在超时（比如超过3000ms还没返回），然后对应的接口提供者，他通过查看监控，以及查看自己的日志发现自己并没有超时（比如200ms就返回了）。那么，如果出现这个现象，可能是什么原因呢？网络延迟或丢包（主要）：一起请求的RT除了包括服务端的执行时长以外，还有一个重要的部分那就是网络交互的时长，而如果存在网络问题，那么可能导致请求在传输过程中延迟或丢失。如果服务端在处理请求之前或处理过程中遇到网络延迟，可能会导致实际处理时间超出预期，从而触发客户端的超时机制。这种是最常见的一种情况，可以通过查看TCP重传率来查看服务端及客户端的网络是否存在延迟的情况。 ✅什么是TCP重传率，有什么用？如何查看？服务端和客户端超时配置不一致（主要）：RPC调用通常既有客户端的超时设置，也有服务端的超时设置。如果客户端的超时阈值设置得比服务端的超时阈值更低（即客户端配置2000ms超时，但是服务端配置的是3000ms超时），那么即使服务端没有超时，客户端也可能因为超过其自身的超时阈值而报告超时。客户端处理能力（次要）：如果客户端在处理请求时遇到资源瓶颈（如CPU、内存限制）或者客户端正在处理大量的并发请求，可能会导致某些请求处理时间较长，从而触发出现超时的现象。

为什么一定要做限流？不应该服务好客户吗？不应该是加机器吗？

典型回答在我们的八股文中，有个限流的方案，被咱们的兄弟的 leader给怼了。他是这么说的：我是这么回复的：我再展开说说。 1、客户第一客户第一是没错，我们是需要服务好客户，让客户用的爽，尽可能的抗更大的流量。这没毛病，但是这个和我们做限流的方案也不冲突。因为我们做限流恰恰是为了客户着想，因为我做了限流，最多是有些客户可能被限流了，暂时无法访问，但是不至于我的系统直接崩了。稍后可能很快就恢复了。而且，客户来了你就让他访问，那你咋确定这些客户是正常的客户？一堆灰黑产盯上你了，来 DDOS 你，你不做限流，还是无脑加机器去服务他们么？ 2、突发流量限流限的是什么，是突发流量，比如说我系统最高 QPS 也就1000，我经过压测，系统能抗1200，我限流1200，这是比较常见的做法了。啥叫突发流量，就是你提前没能预测到的。好了，现在突发流量来了，你没有限流。你咋办？你说你加机器？ ok，你经历过那种绝望吗？就是突发流量直接把你的服务器打挂了，你想扩容，你想加机器，根本不给你机会，机器起来就挂，起来就挂，起来就挂。你加机器有啥用？根本就没用，因为完全不给你加的机会。 3、自我保护限流是什么？是自我保护，是我系统的最后一道防线。在极端情况下，我可以直接开启限流，然后我才有机会可以去排查流量来源，去扩容。你连限流都没有，你只能眼睁睁看着你的服务器被打挂，别无他法。 4、保护别人 MD，你自己把 X 装了。你考虑你下游了吗？你一点限流手段不做，来了你就抗，下游也和你一起扛？他实在扛不住了，说：哥，帮忙限个流吧。你说：限个坤8，给我硬抗？？？？ 5、加机器确实，加机器是最有效的抗流量的办法，我从不否认，能让我无限加机器，我懒得做任何技术优化。机器资源拉满，机器数拉满，网络带宽拉满！那如果是这样？要一个高级开发有啥用？会写代码就行了，反正啥问题都不用考虑，资源可劲用。做程序员，还是得有点技术追求不是吗。

代码中使用长事务，会带来哪些问题？

典型回答 **长事务通常是指在数据库系统中，运行时间较长、执行时间跨度较大的事务。**我们应该尽可能的避免长事务，主要由以下几个原因： 1、**事务的执行时间长，就会持续占用数据库的连接。**因为数据库的连接数是有固定限制的，被长时间占用就会使得其他的事务无法获得连接，导致数据库的整体吞吐量下降。 2、事务中如果加了锁，那么锁会一直在事务中被持有，那么就会导致锁冲突多，导致数据库吞吐量下降，甚至可能会导致大量的死锁问题。在MySQL的官网中，提到了3个和长事务有关的问题： 3、InnoDB使用MVCC来实现并发控制，长事务会导致旧版本的数据持续存在，影响数据库的清理操作（如Purging），从而影响整体性能。详见： ✅undolog会一直存在吗？什么时候删除？ 4、当在长事务中修改或删除行时，如果其他使用 READ COMMITTED和 REPEATABLE READ隔离级别的事务读取这些相同的行，则它们必须做更多的工作来重建旧数据。（这里主要指的是undolog的生成） 5、当一个长事务修改一个表时，可能会导致其他事务对该表的查询不使用覆盖索引技术。详见： ✅二级索引在索引覆盖时如何使用MVCC？所以我们应该尽可能的拆分长事务，在一个事务中，不要干太多的事儿，尤其是一些和数据库操作无关的内存计算、远程调用等等。以及一些普通的查询，也可以先在事务外查询，然后在更新的时候再开启事务。所以，尽可能的使用编程式事务来代替声明式事务，因为声明式事务的粒度都是整个方法级别的，和容易导致长事务。

你认为分布式架构一定比单体架构要好吗？

典型回答这种问题一问出来，答案肯定是不一定。因为他说的太绝对了。单体架构就是把所有的东西都部署在一起，比如一个论坛系统，他把用户、发帖、评论、点赞、搜索等等全都部署在一个应用中。甚至有的更加极致的，把数据都部署在同一个服务器上面。先来介绍下各自的优缺点。单体架构的好处： 1、开发、测试部署都非常简单，只需要在一个项目中做开发，部署也只需要部署一个应用就行了。 2、不需要网络交互，除了和数据库、redis 之间的交互以外，应用的代码都在一起了，不需要通过 HTTP、RPC、MQ 等等去和其他的分布式系统交互，一个单体都搞定。那就能大大的降低网络延迟。 3、不需要考虑分布式问题。比如分布式事务、分布式锁、分布式 id 等等，完全不需要考虑，只需要解决好本地事务，单机并发就行了。但是单体架构同样存在着一些缺点： 1、单机性能存在瓶颈，这个很容易理解，随着你的业务增长，对性能、存储等等的要求会越来越高，但是单机的硬件资源毕竟是有限的。 2、开发效率低。虽然单体的开发比较简单的，但是随着变动多的时候，效率也会有所影响，大家都在一个应用上开发，就会有各种互相影响，每次做代码合并的时候都会无比痛苦。还有就是单体的代码会越来越多，越来越庞大，到最后基本上很难改。 3、单点故障问题。单体应用大家都在一起，共用一个 JVM，共用内存，共用 CPU，一旦某个模块出了问题了，导致了 OOM、CPU 飙高等等，影响面会很大，把所有的功能都影响了。 4、技术栈单一，落后。很多单体都技术栈很旧，主要是因为大家的代码都在一起，各种功能都在一起了，你没啥发挥空间。还有就是很多东西你也用不上，像 MQ，单体你用它干啥呢？像分布式事务，你没有这个场景啊。分布式架构的好处： 1、容易扩展，这个是最大的好处了。可以通过应用拆分、加机器的方式，快速的做扩展，抗更高的并发，更大的业务量。 2、模块化开发，互相独立。这个好处可太好了。大家互相不影响，你干你的，我干我的。互相只需要依赖一下对方的API 就行了。而且即使你的应用挂了，对我来说影响可能有，但是我不至于也跟着挂 3、减少了单点故障，这个比较好理解了。和上面这条类似。 4、技术栈多样。因为大家拆分的比较细，所以有格子的自主权，而且分布式各种场景的问题也都能遇到。但是，他也有缺点的： 1、运维复杂：分布式系统，你就需要管理多个服务的部署、监控、日志、故障恢复等等。还得设计和实现服务发现机制和负载均衡策略。总之就是很多活需要干。 2、CAP：CAP理论大家都知道，这就是因为分布式带来的，随之而来的就是你可用性、一致性这些问题，伴随着的就是分布式事务、SLA等等这些技术问题的保障和解决。难！ 3、问题分析，分布式系统，一个请求下来要经过很多不同的系统，一旦出现了问题，排查起来也挺复杂的，所以就需要引入分布式链路追踪的工具啥的。说了这么多区别，其实就是不同架构都有好处和坏处，各自都有使用的场景。对于一些项目规模较小，团队人数不多，开发周期短，技术要求不复杂的项目，单体就够了。而只有那些，项目规模大，需求复杂，业务增长快，需支持高并发和高可用性的，才需要考虑上分布式、微服务这些玩意。

做一个过滤黑名单网址的系统，你觉得要怎么实现，会用到哪些数据结构？

典型回答要实现一个过滤黑名单网址的系统，我们需要考虑的因素有很多，比如黑名单的存储、匹配和查询的性能、系统扩展性等。可以使用的数据结构有以下几个。逐一来分析一下。哈希表（Hash Table）：可以用哈希表存储每个黑名单网址的域名或完整URL，查询时只需将请求URL进行哈希并查表即可。优点是可以在 O(1)时间复杂度上进行高效的数据查询。但是缺点是不支持模糊匹配和前缀匹配，以及对内存耗费比较大。在关于敏感词过滤的介绍中，我们前缀树也可以用来解决我们的黑地址的场景。 ✅如何实现敏感词过滤？前缀树，也被称为Trie树，是一种用于快速检索字符串数据集中的键的树形数据结构。可以使用Trie树存储域名和URL前缀。如果要判断某个域名是否属于黑名单，可以进行前缀匹配，从而发现某些子域名是否也属于黑名单。他能解决哈希表不支持前缀查询的问题。但是他同样有一个缺点，那就是比较耗内存的问题仍然没有解决。 **布隆过滤器（Bloom Filter）****，**我们也介绍过，这个是一个非常适合使用在黑名单场景的数据结构。因为他底层是基于 bitmap 实现的，每一个地址存储下来只需要一个 bit，所以内存占用比较小。但是他的缺点也比较明显，那就是存在误判的问题，以及无法做删除。具体原因详见：为什么黑名单适合用布隆过滤器？因为黑名单应该是比较少的，大多数的地址应该是不在黑名单中的。而布隆过滤器如果返回不存在，那么说明数据一定是不存在的，不存在误判的情况。所以在误判率可控（一般都是我们设置的）的情况下，对于大部分请求来说，都可以直接通过布隆过滤器判断后返回。而对于一些少量的请求，如果被判断为存在，那么就再去其他存储中查询下做二次判断即可。 ✅什么是布隆过滤器，实现原理是什么？那么，就没有一个好一点的方案了吗。有，那就是组合防范，即基于布隆过滤器+哈希表/前缀树。布隆过滤器可以用作一个第一层的筛选器，如果判断元素不在黑名单中，则直接放行。如果认为元素可能在黑名单中，则进一步进行精确查找（如通过哈希表或Trie）。以上是从数据结构角度说的，也就是说直接把黑名单放到内存中，可以用这样的方案来做，但是其实基本没人这么做，因为都放到内存，内存扛不住啊。所以，如果真的是一个方案设计？最终还得靠存储，那么实际上的方案应该是本地缓存+Redis+数据库。在本地缓存和Redis 中，可以用布隆过滤器这种数据结构，然后数据库的索引我们可以选择用 hash 索引结构那么其实就变成了一个以下的方案（这里的本地缓存可选）：

在100M内存下存储一亿个整数，其范围在１到2亿，如何快速判断给定到一个整数值是否存在？

典型回答这是一个比较典型的海量数据处理的问题，在优先内存情况下进行数据排序、判断是否存在等。主要考察面试者对大数据量计算的经验和思考方式。同时也考察面试者是否有对一些数据库、数据处理中间件原理有过深入的了解。一般来说有以下几个方案：方案一（内存不够）使用Java的list、hashSet提供的方法：list.contains() 、set.contains() 时间复杂度分析： list的contains方法底层是通过遍历整个list，挨个元素进行比对，找出期望值，其时间复杂度为O(n) hashSet底层本质是个hashMap，在进行add时，将值存入hashMap的key中，contains时对值进行hash后查找，其时间复杂度为O(1) 内存空间占用分析：整数范围在Integer.MAX_VALUE之内，占4个字节 list和set都要存储所有元素 list的空间计算：100,000,000（整数数量） × 4（字节 / 整数） = 400,000,000（字节）需要注意的是，这只是粗略的估计。实际的内存占用可能会受到 Java 虚拟机的优化和内存管理策略的影响。此外，还要考虑 List 对象本身的内存开销，以及其他可能的因素（如对象引用、空间对齐等）对内存占用的影响。因此，实际内存占用可能会略高于这个估算值。 hashSet的空间计算：100,000,000（整数数量） × 8（字节 / 整数） = 800,000,000（字节）由于 hashSet 使用了hashMap数据结构，还需要考虑额外的内存开销用于存储散列桶、链表或红黑树等信息。这个开销通常是每个元素 3~4 倍左右，取决于具体实现和负载因子等因素。假设每个元素的额外开销为 2 倍，那么每个整数占用的内存空间为：4 字节 × 2 = 8 字节。显然时间复杂度只有hashSet能胜任，对于内存空间早已超出给定的100M限制。方案2（可行）使用bitmap算法降低内存空间，且时间复杂度为O(1) ✅什么是BitMap？有什么用？ java.util.BitSet是java中bitmap算法的实现，可以初始化一个2亿的BitSet，并把1到2亿通过bitSet.set()方法设置进去，并通过bitSet.get()方法判断期望值是否存在。内存空间占用分析：2,0000,0000（位） ÷ 8（位 / 字节） ÷ 1024（字节 / KB） ÷ 1024（KB/MB） ≈ 23.84 MB 显然bitmap在时间复杂度和空间占用上都完全满足需求。扩展知识上述方案2中，存在一个问题：我们要初始化2个亿的bit数组去承载1个亿的数据需求，有点高射炮打蚊子的感觉。工作中我们并不能百分之百确定一个长期运营的产品用户产生的数据量有多大，同时业务需求也不会只是在海量数据里找出一个值那么简单。通常会有如下几个场景： ...

留言给博主