后端系统设计面试题

169.如何设计一个点赞系统？

点赞系统看似简单，实则非常复杂，它可以从系统架构、库表设计、数据存储、性能优化、容灾备份等多个角度来思考设计。

我们可以由浅入深的向面试官来说出这个实现方案：

系统架构设计

从架构方面需要考虑：服务拆分、异步、缓存。

1）分布式架构

大流量场景下，可以将点赞功能独立成一个服务，解耦业务逻辑，便于扩展和维护。例如点赞服务压力倍增的时候，可以仅扩容点赞服务即可。

2）异步处理

只要涉及到大流量，且实时性并没有那么强烈的场景，就需要考虑异步。可以使用消息队列（如 Kafka、RocketMQ）来异步处理点赞请求，减少直接写数据库的压力。

3）缓存机制

除了异步，其实也可以利用缓存（如 Redis、Memcached）存储点赞数，减少数据库访问

库表设计

这边简单给一个库表设计供大家参考：

1）点赞记录表

1
2
3
4
5
6
7

CREATE TABLE like_record (
    id BIGINT AUTO_INCREMENT PRIMARY KEY,
    user_id BIGINT NOT NULL,
    item_id BIGINT NOT NULL,
    liked_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    UNIQUE KEY unique_user_item (user_id, item_id)
) ENGINE=InnoDB;

2）点赞数汇总表

1
2
3
4

CREATE TABLE like_count (
    item_id BIGINT PRIMARY KEY,
    like_count BIGINT DEFAULT 0
) ENGINE=InnoDB;

数据存储

上面我们提到了缓存，实际上很多公司除了用 MySQL 存储数据之外，还会利用缓存来存储这种高并发修改的数据。

例如使用 Redis 存储点赞数，承接实时的热数据，后续再将点赞数落库存储至 MySQL 中。即将热门的点赞数缓存到 Redis 中，设置适当的过期时间，定期同步到数据库。

有些大公司还会对缓存进行改造，保证缓存本身的数据持久性。

性能优化

1）数据库优化

例如为常用查询添加合适的索引。like_record 表的 user_id 和 item_id 字段。

如果整体的数据量过大，我们还根据 item_id 或 user_id 对数据进行分库分表，减少单个表的写压力。

2）缓存优化

处理上面提到的 Redis 分布式缓存，还可以利用本地缓存来减轻 Redis 的压力，但是要考虑好数据同步的问题。

3）异步批量处理

对于点赞数的写入，我们可以将一定时间窗口内的点赞请求批量更新到数据库，减少数据库的写操作。

如果用了缓存，那么可以使用定时任务定期将 Redis 中的数据同步到数据库，确保数据一致性。

容灾备份

一个系统的设计肯定需要考虑容灾备份，所以这点跟面试官提出来，会觉得你考虑周到，比较有经验。

1）数据备份

• 定期备份：对数据库进行定期备份，使用增量备份和全量备份相结合的策略。
• 异地备份：有条件的公司（几乎很少）会进行异地备份，防止极端情况发生。

2）高可用架构

• 数据库主从复制：使用 MySQL 主从复制或 Redis 主从复制，实现数据的高可用性。

3）容灾演练

定期进行容灾演练，确保在发生故障时系统能够快速恢复。有些公司还有混沌工程。

混沌工程是一种故意向系统注入故障以测试其恢复能力的做法。其目的是找出潜在的故障点，并在它们造成实际中断或其他破坏之前加以纠正

简单来说，例如随便把线上的一台服务停了，看看系统是否能正常运行，来测试故障情况下系统的稳定性。

454.让你设计一个 HashMap ，怎么设计？

这个问题我觉得可以从 HashMap 的一些关键点入手，例如 hash函数、如何处理冲突、如何扩容。

可以先说下你对 HashMap 的理解。

比如：HashMap 无非就是一个存储 <key,value> 格式的集合，用于通过 key 就能快速查找到 value。

基本原理就是将 key 经过 hash 函数进行散列得到散列值，然后通过散列值对数组取模找到对应的 index 。

所以 hash 函数很关键，不仅运算要快，还需要分布均匀，减少 hash 碰撞。

而因为输入值是无限的，而数组的大小是有限的所以肯定会有碰撞，因此可以采用拉链法来处理冲突。

为了避免恶意的 hash 攻击，当拉链超过一定长度之后可以转为红黑树结构。

当然超过一定的结点还是需要扩容的，不然碰撞就太严重了。

而普通的扩容会导致某次 put 延时较大，特别是 HashMap 存储的数据比较多的时候，所以可以考虑和 redis 那样搞两个 table 延迟移动，一次可以只移动一部分。

不过这样内存比较吃紧，所以也是看场景来 trade off （权衡）了。

不过最好使用之前预估准数据大小，避免频繁的扩容。

基本上这样答下来差不多了，HashMap 几个关键要素都包含了，接下来就看面试官怎么问了。

可能会延伸到线程安全之类的问题，反正就照着 currentHashMap 的设计答。

473.让你设计一个线程池，怎么设计？

这种设计类问题还是一样，先说下理解，表明你是知道这个东西的用处和原理的，然后开始 阐述。

基本上就是按照现有的设计来说，再添加一些个人见解。

线程池讲白了就是存储线程的一个容器，池内保存之前建立过的线程来重复执行任务，减少创建和销毁线程的开销，提高任务的响应速度，并便于线程的管理。

我个人觉得如果要设计一个线程池的话得考虑池内工作线程的管理、任务编排执行、线程池超负荷处理方案、监控。

初始化线程数、核心线程数、最大线程池都暴露出来可配置，包括超过核心线程数的线程空闲消亡配置。

任务的存储结构可配置，可以是无界队列也可以是有界队列，也可以根据配置分多个队列来分配不同优先级的任务，也可以采用 stealing 的机制来提高线程的利用率。

再提供配置来表明此线程池是 IO 密集还是 CPU 密集型来改变任务的执行策略。

超负荷的方案可以有多种，包括丢弃任务、拒绝任务并抛出异常、丢弃最旧的任务或自定义等等。

线程池埋好点暴露出用于监控的接口，如已处理任务数、待处理任务数、正在运行的线程数、拒绝的任务数等等信息。

我觉得基本上这样答就差不多了，等着面试官的追问就好。

注意不需要跟面试官解释什么叫核心线程数之类的，都懂的没必要。

当然这种开放型问题还是仁者见仁智者见智，我这个不是标准答案，仅供参考。

724.让你设计一个消息队列，怎么设计？

回答重点

设计类题目要先从大局上讲出需要设计的东西的重点，然后再等待面试官的继续提问，深挖。

1）首先我们需要明确地提出消息中间件的几个重要角色

• 分别是生产者、消费者、Broker、注册中心。

2）简述下消息中间件数据流转过程

• 无非就是生产者生成消息，发送至 Broker。
• Broker 可以暂缓消息。
• 然后消费者再从 Broker 获取消息，用于消费。

而注册中心用于服务的发现包括：Broker 的发现、生产者的发现、消费者的发现，当然还包括下线，可以说服务的高可用离不开注册中心。

3）然后开始简述实现要点，可以同通信讲起（这一段话都是关键词）

• 各模块的通信可以基于 Netty 然后自定义协议来实现。
• 注册中心可以利用 zookeeper、consul、eureka、nacos 等等。也可以像 RocketMQ 自己实现简单的 namesrv。

4）为了考虑扩容和整体的性能，采用分布式的思想

• 像 Kafka 一样采取分区理念，一个 Topic 分为多个 partition。
• 并且为保证数据可靠性，采取多副本存储，即 Leader 和 follower，根据性能和数据可靠的权衡提供异步和同步的刷盘存储。
• 并且利用选举算法保证 Leader 挂了之后 follower 可以顶上，保证消息队列的高可用。
• 也同样为了提高消息队列的可靠性利用本地文件系统来存储消息，并且采用顺序写的方式来提高性能。
• 可根据消息队列的特性利用内存映射、零拷贝进一步的提升性能，还可利用像 Kafka 这种批处理思想提高整体的吞吐。

至此就差不多了，该说的要点说的都差不多了，面试官心里已经想，这人好像有点东西。

还有一点需要注意：在说各设计要点的时候也要注意停顿，要留机会给面试官插话，让面试官充分参与你的设计

让面试官有参与感，让他感觉经过他的引导这个设计才逐步地完善。

让面试成为一场技术交流，这是面试的最高境界

732.让你设计一个 RPC 框架，怎么设计？

先直接跟面试官说下 RPC 框架基础的核心点：

其实就这么几点：

1）动态代理(屏蔽底层调用细节)

2）序列化(网络数据传输需要扁平的数据)

3）协议(规定协议，才能识别数据)

4）网络传输(I/O模型相关内容，一般用 Netty 作为底层通信框架即可)

注意，上面加粗的其实二字，一定要说，要注意语气，要显得你游刃有余，低调奢华。

这属于 RPC 框架的基础，生产级别的框架还需要注册中心作为服务的发现，且还需提供路由分组、负载均衡、异常重试、限流熔断等其他功能。

说到这就可以停下了，然后等面试官发问，正常情况下他会选一个点进行深入探讨，这时候我们只能见招拆招了。

下面我们来深入剖析下 RPC，从根上理解它。

RPC 全称是 Remote Procedure Call ，即远程过程调用，其对应的是我们的本地调用。

远程其实指的就是需要网络通信，可以理解为调用远程机器上的方法。

那可能有人说：我用 HTTP 调用不就是远程调用了，那不也叫 RPC 了？

不是的，RPC 的目的是：让我们调用远程方法像调用本地方法一样无差别。

来看下代码就很清晰，比如本来没有拆分服务都是本地调用的时候方法是这样写的：

1
2
3

public String getSth(String str) {
     return yesService.get(str);
}

如果 yesSerivce 被拆分出去，此时需要远程调用了，如果用 HTTP 方式，可能就是：

1
2
3
4
5

public String getSth(String str) {
    RequestParam param = new RequestParam();
    ......
    return HttpClient.get(url, param,.....);
}

此时需要关心远程服务的地址，还需要组装请求等等，而如果采用 RPC 调用那就是：

1
2
3
4
5
6

    public String getSth(String str) {
        // 看起来和之前调用没差？哈哈没唬你，
        // 具体的实现已经搬到另一个服务上了，这里只有接口。
        // 看完下面就知道了。
         return yesService.get(str);  
    }

所以说 RPC 其实就是用来屏蔽远程调用网络相关的细节，使得远程调用和本地调用使用一致，让开发的效率更高。

在了解了 RPC 的作用之后，我们来看看 RPC 调用需要经历哪些步骤。

RPC 调用基本流程

按上面的例子来说，yesService 服务实现被移到了远程服务上，本地没有具体的实现只有一个接口。

那这时候我们需要调用 yesService.get(str) ，该怎么办呢？

我们所要做的就是把传入的参数和调用的接口全限定名通过网络通信告知到远程服务那里。

然后远程服务接收到参数和接口全限定名就能选中具体的实现并进行调用。

业务处理完之后再通过网络返回结果，这就搞定了！

上面的操作这些就是由yesService.get(str) 触发的。

不过我们知道 yesService 就是一个接口，没有实现的，所以这些操作是怎么来的？

是通过动态代理来的。

RPC 会给接口生成一个代理类，所以我们调用这个接口实际调用的是动态生成的代理类，由代理类来触发远程调用，这样我们调用远程接口就无感知了。

动态代理想必大家都比较熟悉，最常见的就是 Spring 的 AOP 了，涉及的有 JDK 动态代理和 cglib。

在 Dubbo 中用的是 Javassist，至于为什么用这个其实梁飞大佬已经写了博客说明了。

他当时对比了 JDK 自带的、ASM、CGLIB(基于ASM包装)、Javassist。

经过测试最终选用了 Javassist。

梁飞：最终决定使用JAVAASSIST的字节码生成代理方式。 虽然ASM稍快，但并没有快一个数量级，而JAVAASSIST的字节码生成方式比ASM方便，JAVAASSIST只需用字符串拼接出Java源码，便可生成相应字节码，而ASM需要手工写字节码。

可以看到选择一个框架的时候性能是一方面，易用性也很关键。

说回 RPC 。

现在我们知道动态代理屏蔽了 RPC 调用的细节，使得用户无感知的调用远程服务，那调用的细节有哪些呢？

序列化

像我们的请求参数都是对象，有时候是定义的 DTO ，有时候是 Map ，这些对象是无法直接在网络中传输的。

你可以理解为对象是“立体”的，而网络传输的数据是“扁平”的，最终需要转化成“扁平”的二进制数据在网络中传输。

你想想，各对象分配在内存不同位置，各种引用，这看起来是不是有种立体的感觉？最终都是要变成一段01组成的数字传输给对方，这种就01组成的数字看起来是不是很“扁平”？

把对象转化成二进制数据的过程称为序列化，把二进制数据转化成对象的过程称为反序列化。

当然如何选择序列化格式也很重要。

比如采用二进制的序列化格式数据更加紧凑，采用 JSON 等文本型序列化格式可读性更佳，排查问题比较方便。

还有很多序列化选择，一般需要综合考虑通用性、性能、可读性和兼容性。

具体本文就不分析了，之后再专门写一篇分析各种序列化协议的。

RPC 协议

刚才也提到了只有二进制数据才能在网络中传输，那一堆二进制在底层看来是连起来的，它可不会管你哪些数据是哪个请求的，那接收方得知道呀，不然就不能顺利的把二进制数据还原成对应的一个个请求了。

于是就需要定义一个协议，来约定一些规范，制定一些边界使得二进制数据可以被还原。

比如下面一串数字按照不同位数来识别得到的结果是不同的。

所以协议其实就定义了到底如何构造和解析这些二进制数据。

我们的参数肯定比上面的复杂，因为参数值长度是不定的，而且协议常常伴随着升级而扩展，毕竟有时候需要加一些新特性，那么协议就得变了。

一般 RPC 协议都是采用协议头+协议体的方式。

协议头放一些元数据，包括：魔法位、协议的版本、消息的类型、序列化方式、整体长度、头长度、扩展位等。

协议体就是放请求的数据了。

通过魔法位可以得知这是不是咱们约定的协议，比如魔法位固定叫 233 ，一看我们就知道这是 233 协议。

然后协议的版本是为了之后协议的升级。

从整体长度和头长度我们就能知道这个请求到底有多少位，前面多少位是头，剩下的都是协议体，这样就能识别出来，扩展位就是留着日后扩展备用。

贴一下 Dubbo 协议：

可以看到有 Magic 位，请求 ID， 数据长度等等。

网络传输

组装好数据就等着发送了，这时候就涉及网络传输了。

网络通信那就离不开网络 IO 模型了。

网络 IO 分为这四种模型，具体以后单独写文章分析，这篇就不展开了。

一般而言我们用的都是 IO 多路复用，因为大部分 RPC 调用场景都是高并发调用，IO 复用可以利用较少的线程 hold 住很多请求。

一般 RPC 框架会使用已经造好的轮子来作为底层通信框架。

例如 Java 语言的都会用 Netty ，人家已经封装的很好了，也做了很多优化，拿来即用，便捷高效。

小结

RPC 通信的基础流程已经讲完了，回顾下之前的图：

响应返回就没画了，反正就是倒着来。

我再用一段话来总结一下：

服务调用方，面向接口编程，利用动态代理屏蔽底层调用细节将请求参数、接口等数据组合起来并通过序列化转化为二进制数据，再通过 RPC 协议的封装利用网络传输到服务提供方。

服务提供方根据约定的协议解析出请求数据，然后反序列化得到参数，找到具体调用的接口，然后执行具体实现，再返回结果。

这里面还有很多细节。

比如请求都是异步的，所以每个请求会有唯一 ID，返回结果会带上对应的 ID， 这样调用方就能通过 ID 找到对应的请求塞入相应的结果。

有人会问为什么要异步，那是为了提高吞吐。

当然还有很多细节，会在之后剖析 Dubbo 的时候提到，结合实际中间件体会才会更深。

真正工业级别的 RPC

以上提到的只是 RPC 的基础流程，这对于工业级别的使用是远远不够的。

生产环境中的服务提供者都是集群部署的，所以有多个提供者，而且还会随着大促等流量情况动态增减机器。

因此需要注册中心，作为服务的发现。

调用者可以通过注册中心得知服务提供者们的 IP 地址等元信息，进行调用。

调用者也能通过注册中心得知服务提供者下线。

还需要有路由分组策略，调用者根据下发的路由信息选择对应的服务提供者，能实现分组调用、灰度发布、流量隔离等功能。

还需要有负载均衡策略，一般经过路由过滤之后还是有多个服务提供者可以选择，通过负载均衡策略来达到流量均衡。

当然还需要有异常重试，毕竟网络是不稳定的，而且有时候某个服务提供者也可能出点问题，所以一次调用出错进行重试，减少业务的损耗。

还需要限流熔断，限流是因为服务提供者不知道会接入多少调用者，也不清楚每个调用者的调用量，所以需要衡量一下自身服务的承受值来进行限流，防止服务崩溃。

而熔断是为了防止下游服务故障导致自身服务调用超时阻塞堆积而崩溃，特别是调用链很长的那种，影响很大，比如A=>B=>C=>D=>E，然后 E 出了故障，你看ABCD四个服务就傻等着，慢慢的资源就占满了就崩了，全崩。

大致就是以上提到的几点，不过还能细化，比如负载均衡的各种策略、限流到底是限制总流量还是根据每个调用者指定限流量，还是上自适应限流等等。

740.让你设计一个短链系统，怎么设计？

先说一下回答思路：

1）简单描述下短链原理

2）后端设计

3）补充跳转设计

一个小小短链其实融合了很多知识点，能较为全面的考察一个候选人的综合实力。

原理

在浏览器输入短链后，请求打到短链服务，短链服务会根据 url 找到对应的长链重定向到长链地址，此时浏览器就会跳转网页定位到真正的地址。

所以本质原理就是短链服务器根据 url 定位到真正地址，然后通过重定向实现跳转。

后端设计

后端的主要功能是存储短链和长链的对应关系，并且能快速通过短链找到长链。

首先需要先生成短链，假设短链的域名是 dl.x

1）可以通过数据库自增 id 作为短链，往数据库插入一条长链，对应就会得到一个 id

如果用户访问了 dl.x/1 ，解析得到 1，通过主键就能定位到数据库记录，得到长链 https://www.code-nav.cn/course/1790274408835506178 。

这个方式很简单，通过主键查询也很快。

如果面试官问这样的方式有什么缺点，你再说：一旦短链量变多，自增 id 会变成很大，比如 9999999999999999，这样短链也不短了，而且数字有规律性，容易被人遍历出来。

没问就不用说。

2）哈希算法

可以通过 hash 算法将长链进行 hash 计算，得到固定的长度，比如通过 md5 计算可以得到固定的 128bit 数据，还有别的哈希函数，比如 MurMurHash，它既可以生成 128 bit 也可以生成 32bit，不过 32 bit 相比 128 bit 生成速度更慢，且 hash 碰撞的概率更高。

这里再提一嘴 MurMurHash 128bit 版本的速度是 md5 的十倍。

还有 crc32 ，得到的就是 32 位的哈希值，运算速度和 md5 差不多。

因此我们可以将长链通过 hash 得到固定的位数，我找了个网上的 MurmurHash2 例子，我们来看下

可以看到这么长的一个 url，直接变成了 2278507744，因此短链就是 dl.x/2278507744

但是这好像比我们平时在短信中看到的短链还长了一些，还能再缩短吗？

当然是可以的，还可以利用进制转化进一步缩短长度！

比如我们取 62 位的，最终的短链就是 dl.x/2ucnWU，这样看着是不是感觉就对了？同理上面的自增 id 也可以通过进制转化进一步缩短。

最终的数据库表结构的设计如下：

字段：

• id：主键
• short_url：短链
• long_url：原始长 URL
• user_id：用户 ID（如果需要关联用户）
• created_at：创建时间
• updated_at：更新时间

短链字段需要建立索引，因为很常见的查询就是通过短链得到长链。

跳转设计

我们已经了解到通过短链得到长链的过程，那么浏览器具体是如何在输入短链后自动跳到长链地址的呢？

答案就是重定向。这里就需要涉及到 HTTP 的知识点，服务器返回 301 或者 302 状态码，然后在 location 上写上长链的地址，浏览器就会自动识别动作，进行跳转。

这两个状态码还是有区别的：

1）301 表示永久重定向，即浏览器会默认缓存这次跳转的信息，下次用户在浏览器访问这个短链，浏览器不需要请求短链服务，会自动跳转到长链地址。

2）302 表示临时重定向，即浏览器不会缓存这次跳转信息，用户每次访问这个短链，都需要请求短链服务得到长链。

区别就是 301 可以降低短链服务器压力，因为后续用户访问都不需要请求短链后端服务，而 302 则需要每次访问，但是这样一来可以统计短链访问次数，做一些分析。

扩展

如果数据量大了，一张表存储所有短链数据就会有性能问题，因此需要分库分表。

如果是利用自增 ID 转换得到短链信息，在分库分表场景就会出现重复 ID 的情况，因此可以引入全局发号器来实现全局唯一 ID 分配，比如唯一 ID 可以利用雪花算法生成。

然后通过全局 ID 转化的短链数据作为分表的键即可，因为查询肯定是通过短链来查的。

还有哈希方法可能会导致哈希冲突，即不同的长链可能会生成一样的短链，我们可以将 short_url 作为唯一索引，这样就能保证唯一性，如果插入报错，则可以简单在长链后面拼个随机数，重新进行 hash，这样就能避免重复了。

还可以引入缓存，比如我们双十一做了一个营销活动，给很多用户推送了短信，此时肯定会有很多用户访问这个短信内的短链，此时我们就可以将短链相关信息放在缓存中，不需要查数据库，利用缓存提高性能。

补充为什么需要短链

一般短链会用在短信场景，因为短信有字数限制，超过一定字数收费不一样，所以太长的连接不合适。

再比如一些社交媒体平台对字数也会有限制。

还有一些二维码，如果 url 太长，生成的码也会比较复杂，比较难扫。

824.让你实现一个订单超时取消功能，怎么设计？

一般会通过定时任务或者消息队列的延迟消息来实现订单超时取消功能。

定时任务

定时任务的逻辑就是扫描已创建未支付的订单，判断订单的创建时间与当前时间的差值，如果已经超过了预设的超时时间，比如 10 分钟，那么就将订单状态更新为已取消。

比如可以每 1 分钟扫描一次表，直接根据当前时间和超时时间得到筛选的时间，比如当前是 14:00，那么 13:50 分之前创建的订单未付款其实都超时了，将这个时间和状态作为查询条件进行数据库查询，得到超时的订单，最后批量更新超时订单的状态。

通过时间+状态查询效率会更高，如果直接通过状态查询，然后在内存中判断时间，其实会有很多订单是还未过期的，这样效率就比较低。

并且需要限制每次查询的数量，比如一次 limit 200。

一般会采用分布式定时任务框架，例如 xxljob 等，如果涉及多机任务并发执行提升效率的情况，需要对订单进行分片，比如机器1 处理订单号 % 2 余 0、机器 2 处理订单号 % 1 余 0 的订单等等。

定时任务方案的缺点是超时时间比较不准确，如果 1 分钟执行一次任务，那么相差的时间可能就是一分钟，如果订单量很大的情况可能还会放大不准确的时间，因为任务处理也需要花费时间，且对数据库压力也会比较大，因为会集中扫表。

消息队列

消息队列例如 RocketMQ 会提供延迟消息功能，仅需在下单的时候发送一条延迟 10 分钟取消订单的消息。

10 分钟后，消费者会接受到这条消息，如果这条订单还未支付则取消订单，若已支付则忽略这条消息。

可以看到这种方案不会对数据库产生压力，因为消息队列本身天然实现削峰填谷，消费者可以按照自己的能力来把控消费速率，并且可以横向扩展，通过加机器的方式加快消费速度。

相对而言超时时间的控制能更精确，且对系统压力不大。

其它的还有可以利用 redis zset 来实现，score 设置为订单创建时间+超时时长，订单号为 member，这样就可以通过 score 排序，找到超过当前时间的订单，进行判断就好了。

826.让你实现一个分布式单例对象，如何实现？

所谓的单例一般指的是一个进程中一个类对应只有一个实例对象，也就是进程唯一。

而分布式，不过是一个机器部署多个服务，还是多个机器部署，本质上就是多进程，所以所谓的分布式单例指的是这个实例对应需要在多进程中保持唯一。

按照这个思路，我们仅需控制同一时刻，只会有一个进程使用这个单例对象即可，而分布式场景下的分布式锁就很容易实现这个功能。

多个进程竞争分布式锁，谁抢到锁，谁此时就可以使用这个单例对象，用完之后释放这个对象，并且释放锁，这样不就保证多进程中实例对象唯一了吗？

所以，我们需要在三方外部存储这个单例对象，每次进程用完单例对象后，再将对象的数据写回外部存储中，这样就能保证多个进程对这个单例对象的修改都同步，状态一致。

分布式锁可以用 redis 实现，三方外部存储也可以用 redis 实现。

总结下：每个进程使用这个类的时候，争抢分布式锁，如果抢到则从 redis 获取这个数据，反序列化成一个对象使用，使用完之后，将对象数据再序列化存储到 redis 中，覆盖之前的数据，最终释放锁。

844.商家想要知道自己店铺卖的最好的 top 50 商品，如何实现这个功能？

根据问题推断这个排行榜是一个动态的排行榜，店铺内商品一直在售卖，因此排行榜也会一直在变，所以如果利用数据库来排行计算效率会非常低，总不能每卖一单就利用数据库排序计算得到排行榜吧？

所以排除数据库这个方案。

应对数据库效率差的情况，我们常用的替代方案就是缓存，而 Redis 内有个 zset 可以实现排行榜的功能。

每个商家都对应有个 zset，score 存储商品售卖的数量，value 存储商品 ID。

每售卖一个商品，就可以利用 ZINCRBY 更新对应 score + 1，时间复杂度为 O（1）。

然后商家在查看 top 50 商品的时候，利用 zrevrange key 0 49 获取排行榜，底层存储用的是跳表，时间复杂度为 O（logN+M）,N 为总元素数，M 为返回的元素数。

846.朋友圈点赞功能如何实现，简单说说？

首先我们要理清朋友圈点赞具体需要涉及哪几个功能点：

1）存储点赞信息

需要存储哪些用户点赞了这条朋友圈，具体需要存储用户ID、点赞时间即可。

2）取消点赞

需要快速找到这名用户，将其移除点赞列表。

3）获取点赞列表

朋友圈需要展示点赞的用户头像列表信息.

核心就是这么三点，其实就是增删查，那用什么来实现比较合适呢？

实现快速存储和删除，Set 就挺合适，而且还能天然去重，但是常见的 HashSet 是无序的，朋友圈的点赞列表需要按时间顺序排序。

而 TreeSet 理论上可以支持这些功能，顺序按点赞时间排序，所以在内存中利用 TreeSet 来保存朋友圈数据。

但是数据保存在 Java 内存中不合理，因为应用重启一下不就没了？

同样是内存，我们可以联想到 Redis ，将数据存放到 Redis 里即可，Redis 也支持 aof 和 rbd 持久化。

并且 Redis 恰巧有个 zset 结构，可以满足我们的需求。

zset 的 key 可以设置此条朋友圈的 id，score 为点赞时间，value 为点赞用户 ID。

如果用户点赞，则将用户 id 和当前时间添加到 zset 中，时间复杂度为 O（logN），N 为排序集合内总元素数

如果用户取消点赞，则从 zset 中移除此用户，时间复杂度为 O（logN * M），N 为排序集合内总元素数，M 删除的元素数。

查看朋友圈点赞列表，调用 zset 的 zrange key 0 -1 即可，底层存储用的是跳表，时间复杂度为 O（logN+M），N 为排序集合内总元素数，M 为返回的元素数。

958.分布式锁一般都怎样实现？

分布式锁需要实现多个应用实例之间的临界资源竞争，因此它需要依赖三方组件才能实现这样的功能。

常见依赖 Redis、ZooKeeper 来实现分布式锁。

Redis 实现

基于缓存实现分布式锁性能上会有优势，可以使用 Redis SETNX （SET if Not eXists）实现分布式锁。

注意锁需要设置过期时间，防止应用程序崩溃导致锁没有释放而阻塞后面的所有操作。

获取锁：使用 jedis.set(lockKey, lockValue, "NX", "PX", lockTimeout) 尝试获取锁，NX 确保键不存在时才设置，PX 设置键的过期时间（毫秒）。

释放锁：使用 Lua 脚本确保只有持有锁的客户端才能删除锁。Lua 脚本会检查键的值是否等于 lockValue，如果是则删除该键。

简单示例如下，acquireLock 为获取锁，releaseLock 为释放锁：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

public class RedisDistributedLock {
    private static final String LOCK_SUCCESS = "OK";
    private static final Long RELEASE_SUCCESS = 1L;

    private Jedis jedis;
    private String lockKey;
    private String lockValue;
    private int lockTimeout;

    public RedisDistributedLock(Jedis jedis, String lockKey, int lockTimeout) {
        this.jedis = jedis;
        this.lockKey = lockKey;
        this.lockTimeout = lockTimeout;
        this.lockValue = UUID.randomUUID().toString();
    }

    public boolean acquireLock() {
        String result = jedis.set(lockKey, lockValue, "NX", "PX", lockTimeout);
        return LOCK_SUCCESS.equals(result);
    }

    public boolean releaseLock() {
        String releaseScript = 
            "if redis.call('get', KEYS[1]) == ARGV[1] then " +
            "return redis.call('del', KEYS[1]) " +
            "else return 0 end";
        Object result = jedis.eval(releaseScript, Collections.singletonList(lockKey), Collections.singletonList(lockValue));
        return RELEASE_SUCCESS.equals(result);
    }

    public static void main(String[] args) {
        // 创建一个 Jedis 连接实例
        Jedis jedis = new Jedis("localhost", 6379);

        // 创建分布式锁实例
        RedisDistributedLock lock = new RedisDistributedLock(jedis, "my_lock", 10000);

        // 尝试获取锁
        if (lock.acquireLock()) {
            try {
                // 执行你的业务逻辑
                System.out.println("Lock acquired, executing business logic...");
            } finally {
                // 释放锁
                lock.releaseLock();
                System.out.println("Lock released.");
            }
        } else {
            System.out.println("Unable to acquire lock, exiting...");
        }

        // 关闭 Jedis 连接
        jedis.close();
    }
}

注意 lockValue 需要保证唯一，防止被别的客户端释放了锁。

这里有个问题，如果业务还没执行完，则 Redis 的锁已经到期了怎么办？因此引入“看门狗”机制，即起一个后台定时任务，不断地给锁续期，如果锁释放了或客户端实例被关闭则停止续期，Redisson 提供了此功能。

注意：未指定超时时间的分布式锁才会续期，如果指定了超时时间则不会续期，默认 30s 超时，每 10s 续期一次，续期时长为 30s。

除了锁续期问题，还有单点故障问题，如果这台 Redis 挂了怎么办？分布锁就加不上了，业务就被阻塞了。

因此需要引入 Redis 主从，利用哨兵进行故障转移，但是这又会产生新的问题，如果 master 挂了，锁的信息还未传给 slave 节点，此时 slave 上是没加锁的，因此可能导致多个实例都成功上锁。

所以 Redis 作者又提出了 RedLock 即红锁，通过引入多个主节点共同加锁来解决单点故障问题（没有哨兵和 slave 了）。

比如现在有 5 个 Redis 节点（官方推荐至少 5 个），客户端获取当前时间 T1，然后依次利用 SETNX 对 5 个 Redis 节点加锁，如果成功 3 个及以上（大多数），再次获取当前时间 T2，如果 T2-T1 小于锁的超时时间，则加锁成功，反之则失败。

如果加锁失败则向全部节点调用释放锁的操作。

但是这个 redlock 还是有缺点的，首先它比较重，需要 5 个实例，成本不低。

其次如果发生时钟偏移，比如 5 个节点中有几个节点时间偏移了，导致锁提前超时了，那么有可能出现新客户端争抢到锁的情况，但是这个属于运维层面的问题。

还有一个就是 GC 问题，如果客户端抢到锁之后，发生了长时间的 GC 导致 redis 中锁都过期了，这样一来别的客户端就能得到锁了，且老客户端 GC 后正常执行后续的操作，导致并发修改，数据可能就不对了。不过这个问题无法避免，任何锁都可能会这样。

关于 RedLock 可以使用 Redisson ，它提供了 RedLock。

一般业务上，如果我们要使用 Redis 分布式锁，基本上使用 Redisson 客户端。

ZooKeeper

除了 Redis 还可以使用 ZooKeeper 的临时有序节点实现分布式锁。

临时 能保证超时释放，有序 能选出谁抢到了锁。

大致流程：多进程争抢创建 ZooKeeper 指定目录下的临时有序节点，创建序号最小的节点即抢到锁的进程，释放锁可以删除此节点，如果服务端挂了也会释放这个节点。

优点：如果本身已经引入了 ZooKeeper 则成本不大，实现比较简单。

缺点：相比于 Redis 性能没那么好，ZooKeeper 的写入只能写到主节点，然后同步到从节点。并且临时节点如果产生网络抖动，节点也会被删除，导致多个客户端抢到锁（当然有重试机制，产生的概率比较低）。

可使用 curator 客户端实现的分布式锁接口。

970.如果让你统计每个接口每分钟调用次数怎么统计？

最简单的可以使用 ConcurrentHashMap + AtomicInteger + 定时任务实现内存中的统计。

ConcurrentHashMap 的 key 为方法的名称、value 为 AtomicInteger 类型，记录调用次数，可以通过 aop 切面实现每个方法调用都记录到 ConcurrentHashMap 中，然后利用定时任务每 60 s 统计一次所有方法的数量，再清空 ConcurrentHashMap。

ConcurrentHashMap 保证多方法并发统计时线程安全，AtomicInteger 保证每次累计时线程安全。

看下代码就很清晰了：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

@Aspect
@Component
public class ApiCallAspect {

    private ConcurrentHashMap<String, AtomicInteger> apiCallCounts = new ConcurrentHashMap<>();

    @Before("execution(* com.example.controller.*.*(..))")
    public void recordApiCall(JoinPoint joinPoint) {
        String methodName = joinPoint.getSignature().getName();
        apiCallCounts.computeIfAbsent(methodName, k -> new AtomicInteger(0)).incrementAndGet();
    }

    public ConcurrentHashMap<String, AtomicInteger> getApiCallCounts() {
        return apiCallCounts;
    }

    public void reset() {
        apiCallCounts.clear();
    }

}


//每分钟
@Scheduled(fixedRate = 60000)
public void reportApiCallCounts() {
    ConcurrentHashMap<String, AtomicInteger> apiCallCounts = apiCallAspect.getApiCallCounts();
    apiCallCounts.forEach((apiName, count) -> {
       // 记录到 redis 或其他介质中
    });
    //清空记录
    apiCallCounter.reset();
}

优点：简单。

缺点：不准确，因为定时任务记录时候，ConcurrentHashMap 也一直在统计，所以最终的结果不一定是一分钟内的，而是超过一分钟的数据。且数据存储到内存中，如果意外宕机，数据就丢失了。

可以采用日志记录实现接口的统计。每次接口调用都用日志记录：接口名、时间戳等信息。

利用日志采集工具将日志统一发送并存储至 es 中（或者其他 NoSQL 中），利用 es 即可统计每分钟每个接口的调用量。

也可以利用 MQ，每次接口调用时都将接口名、时间戳封装发送消息，消费端可以将这些信息存储至 NoSQL 中，最终进行统计分析。

因为存储了时间戳，所以接口的调用次数是准确的。

1042.让你设计一个文件上传系统，怎么设计？

这种题目都是开放性的，面试过程中也不奢望聊出所有的设计细节，仅仅需要抛出一些大致的设计需求与要点，然后简单的方案实现思路即可。

关于文件上传系统有几个最主要的核心点需要解决：

1）如何支持超大文件上传

2）避免重复文件存储，节省空间

3）限流问题

大文件上传

假设有个 10 G 的文件需要上传，正常情况下是将文件转成流传到后端，如果不做任何处理，前端一直传，后端存储这些流直到传递完成，后端非常容易内存溢出，多来几个人，后端的内存至少需要几十个 G ，一般的后端服务都没有这么大的内存。

并且一旦出现网络抖动或者其他情况，前端传输失败，前面传的都白费了。所以必须需要将大文件进行切割传输，即切块传输。

所谓的切块很容易理解，举个很简单的例子，假设一个视频 60 分钟，我们将它切成 60 个 1 分钟的视频，合起来不就是完整的视频了？

后端分别存储切割的小视频，不需要等待所有文件传输完成合并存储，等到时候需要下载的时候，分块转成流给前端就好了。

总结一下：大文件需要前端分块传输给后端，后端分块存储，后面下载的时候，后端按序将分块文件给予前端即可。

避免存储重复文件

对于这点，很多同学都会想到用文件名判重，文件名相同的被识别为一个文件，这对于文件系统来说明显是不合理的，我拍个照命名为吴彦祖.png，假设吴彦祖也用我们的系统，他也上传了图片命名为吴彦祖.png。

怎么说？彦祖上传后下载一看，照片上的人是我，不是他，哈哈哈。

那应该用什么方式呢？

有个叫哈希摘要的东西，也就是计算文件的 md5(或者其他 hash 算法)，得到摘要，对比两个文件的摘要，如何摘要一致就可以认为是同一份文件。

摘要在文件场景非常常见，例如 jdk 的下载就会附上摘要，用来判别我们下载的文件是否被篡改，如果摘要一致说明文件没有被篡改过。

限流问题

文件上传需要占用的资源挺多，内存、磁盘、带宽等等，所以需要做一定的限制。

比如限制文件的最大值，防止恶意超大文件上传。

限制每天用户上传的次数、上传的频次间隔、上传的总文件大小量。

利用令牌桶或其他限流算法，限制同一时刻的上传用户数，防止后端压力过大和内存溢出问题。

监控后端内存，内存超过一定阈值后报警通知，灵活配置限流，保护后端系统安全。

切块以及存储简要流程

可以将文件切成 2m 每块，分块文件存储至服务器，分块记录存储到 redis 中，key 的设置可以是 userid + uuid（标明这次的文件）+ filename + seq（顺序）

之所以利用 redis 是因为性能高，其次可以设置过期时间，因为大文件上传存在传一半用户觉得太慢，取消上传，这时候之前上传的切块文件都应该被清理。

而 redis 可以自动过期 key ，后续监听到在这个 key 没了，就可以清理之前上传的无用切块文件，节省空间。

每次切块上传，都可以利用 md.update 更新 md5 摘要（固定大小不会因为大文件挤爆内存），等上传完毕就可以利用 md.digest 获取文件摘要，此时将 redis 的分块记录、切块文件数量、总大小、摘要等一切信息都落库即可。

上传文件的时候，前端将文件摘要信息传递至后端，后端从数据库查找是否有一致摘要，如果有则说明文件已存在，直接保存相关的信息，然后返回前端上传成功即可。

大致方案如何，面试中还是需要具体情况具体分析，每个面试官询问的角度都不同，如果你有实力，则投其所好，如果你有些地方比较强，则引导面试官询问你擅长的方向。

1086.让你设计一个分布式 ID 发号器，怎么设计？

一般在分库分表场景，就会有分布式 ID 的需求，因为需要有一个唯一标识来标记一个订单或者其他类似的数据等。

全局唯一 ID 有很多种实现，例如 UUID ，优势就是本地生成，很简单。但它是无序的，如果需要将唯一 ID 作为主键，则 UUID 不合适，首先是太长了，其次无序插入会导致数据页频繁分裂，性能不好。

在回答这个面试题的时候可以先提下 UUID，简单说下优缺点（UUID 的缺点其实侧面能体现出你对 MySQL 的了解，这都是小心机呀）。

常见的分布式 ID 实现有两种：

1）雪花算法

2）基于数据库

雪花算法

雪花算法用有 64bit，实际就用到了 63bit，最前面有一个 1bit 没用，图中就没画了。

其中 41bit 是时间戳，10bit 是机器 ID（可以表示 1024 台机器。如果有机房的划分，可以把 5bit 分给机房号，剩下 5bit 分给机器）。最后 12bit 是自增序列号，12bit 可以表示 2 的 12 次方个 ID。

可以看到，以时间戳打头可以保证趋势是有序性，其中分配了机器号避免了多机器之间重复 ID 的情况，后面的自增序号使得理论上每台机器每毫秒都可以产生 2 的 12 次方个 ID。

简述优点：

1）分布式 ID 从整体来看有序的。 2）简单、灵活配置，无序依赖外部三方组件。

缺点：

1）依赖时钟，如果发生时钟回拨，可能会导致重复 ID。

常见的 hutool 就有提供了雪花算法工具类。

面试官可能会问雪花算法的机器 ID 如何动态配置，因为现在机器都是动态扩容部署，机器数都是不固定的，如果机器 ID 没配置好，容易导致冲突。

可以借助 Redis 或者 zookeeper 来实现机器 ID 的分配。

redis 的执行是单线程的，机器启动时候调用 redis incr 即可得到自增 id ，可将这个 id 作为机器 ID。

zookeeper 的使用也很简单，机器启动时候可以利用 zookeeper 持久顺序节点特性，将注册成功的顺序号作为机器 ID。

基于数据库

对 MySQL 来说，直接利用自增 id 即可实现。

1
2

REPLACE INTO table(bizTag) VALUES ('order');
select last_insert_id();

将 bizTag 设为唯一索引，可以填写业务值（也可以不同业务多张表），REPLACE INTO 执行后自增 ID 会 + 1，通过 last_insert_id 即可获得自增的 ID 。

优点：简单、利用数据库就能实现，且 ID 有序。

缺点：性能不足。

可以利用 auto_increment_increment 和 auto_increment_offset 实现横向扩展。

比如现在有两台数据库，auto_increment_increment 都设置为 2，即步长是 2。第一台数据库表 auto_increment_offset 设置为 1，第二台数据库表 auto_increment_offset 设置为 2。

这样一来，第一台的 ID 增长值就是 1、3、5、7、9….，第二台的 ID 增加值就是 2、4、6、8、10….

这样也能保证全局唯一性，多加几台机器弥补性能问题，只要指定好每个表的步长和初始值即可。

不过单调递增特性没了，且加机器的成本不低，动态扩容很不方便。

这里我们可以思考下，每次操作数据库就拿一个 ID ，我们如果一次性拿 1000 个，那不就大大减少操作数据库的次数了吗？性能不就上去了吗？

重新设计下表，主要字段如下：

bizTag: 业务标识 maxId: 目前已经分配的最大 ID step: 步长，可以设置为 1000 那么每次就是拿 1000 ，设置成 1w 就是拿 1w 个

每次来获取 ID 的 SQL 如下：

1
2

UPDATE table SET maxId = max_id + step WHERE bizTag = xxx
SELECT maxId, step FROM table WHERE biz_tag = xxx

这其实就是批量思想，大大提升了 ID 获取的性能。

到这里可能面试官会追问，假设业务并发量很高，此时业务方一批 ID 刚好用完后，来获取下一批 ID ，因为当前数据库压力大，很可能就会产生性能抖动，即卡了一下才拿到 ID，从监控上看就是产生毛刺。

这样怎么处理？

其实这就是考察你是否有预处理思想，如果你看过很多开源组件就会发现预处理的场景很多，例如 RocketMQ commitlog 文件的分配就是预处理，即当前 commitlog 文件用完之前，就会有后台线程预先创建后面要用的文件，就是为了防止创建的那一刻的性能抖动。

同理，这个场景我们也可以使用预处理思想。

发号器服务可以本地缓存两个 buffer，业务方请求 ID 每次从其中一个 buffer 里取，如果这个 buffer 发现 ID 已经用了 20 %（或者另外的数量），则可以起一个后台线程，调用上面的 SQL 语句，先把下一批的 ID 放置到另一个 buffer 中。

当前面那个 buffer ID 都用完了，则使用另一个 buffer 取号，如此循环使用即可，这样就能避免毛刺问题。

将 ID 放在本地缓存性能好，即使服务重启了也没事，无法就是中间空了一点点 ID 罢了，整体还是有序的。

一些关键点

雪花算法面试官可能会追问如果时钟回拨了怎么办，理论上可以存储上一次发号的时间，如果当前发号的时间小于之前的发号时间，则说明时钟回拨，此时拒绝发号，可以报警或者重试（重试几次时间可能就回来了）。

数据库方案如果面试官说数据库故障怎么办？理论上数据库都故障了其实很多业务都无法执行下去。。这属于不可抗拒因素，但是我们有本地缓存，可以将 step 设置大一些，例如 qps 最高时候的 600 倍，这样至少有 10分钟的缓冲时间，可能数据库就恢复了。其次数据库可以做主从，但是主从会有复制延迟，导致 maxId 重复，这里可以采取和雪花算法对抗时钟回拨一样的套路，服务记录上次 maxId，如果发现 maxId 变小了，则再执行一次 update。

还有一点，数据库实现的 ID 是完全连续的，如果用在订单场景，竞对早上下一单，晚上下一单，两单一减就知道你今天卖了多少单，所以很不安全，因此这种 ID 不适合用在这种场景（再比如文章的 id 容易被爬虫简单按序一次性爬完）。

这一套如果跟面试官说下来，我相信这场面试你肯定稳了，整体设计没问题、还有很多性能方面的考虑并且还想到了安全性问题。

1190.什么是限流？限流算法有哪些？怎么实现的？

限流是什么？

首先来解释下什么是限流？

在日常生活中限流很常见，例如去有些景区玩，每天售卖的门票数是有限的，例如 2000 张，即每天最多只有 2000 个人能进去游玩。

那在我们工程上限流是什么呢？限制的是 「流」，在不同场景下「流」的定义不同，可以是每秒请求数、每秒事务处理数、网络流量等等。

而通常我们说的限流指代的是 限制到达系统的并发请求数，使得系统能够正常的处理 部分 用户的请求，来保证系统的稳定性。

限流不可避免的会造成用户的请求变慢或者被拒的情况，从而会影响用户体验。

因此限流是需要在用户体验和系统稳定性之间做平衡的，即我们常说的 trade off。

对了，限流也称流控（流量控制）。

为什么要限流？

前面，我们提到限流是为了保证系统的稳定性。

日常的业务上有类似秒杀活动、双十一大促或者突发新闻等场景，用户的流量突增，后端服务的处理能力是有限的，如果不能处理好突发流量，后端服务很容易就被打垮。

亦或是爬虫等不正常流量，我们对外暴露的服务都要以最大恶意去防备调用者。

我们不清楚调用者会如何调用我们的服务，假设某个调用者开几十个线程一天二十四小时疯狂调用你的服务，如果不做啥处理咱服务也算完了，更胜的还有DDos攻击。

还有对于很多第三方开放平台来说，不仅仅要防备不正常流量，还要保证资源的公平利用，一些接口都免费给你用了，资源都不可能一直都被你占着吧，别人也得调的。

当然加钱的话好商量。

小结一下

限流的本质是因为后端处理能力有限，需要截掉超过处理能力之外的请求，亦或是为了均衡客户端对服务端资源的公平调用，防止一些客户端饿死。

常见的限流算法

有关限流算法我给出了对应的图解和相关伪代码，有些人喜欢看图，有些人更喜欢看代码。

计数限流

最简单的限流算法就是计数限流了。

例如系统能同时处理 100 个请求，保存一个计数器，处理了一个请求，计数器就加一，一个请求处理完毕之后计数器减一。

每次请求来的时候看看计数器的值，如果超过阈值就拒绝。

非常简单粗暴，计数器的值要是存内存中就算单机限流算法。

如果放在第三方存储里，例如 Redis 中，集群机器访问就算分布式限流算法。

优点就是：简单粗暴，单机在 Java 中可用 Atomic 等原子类、分布式就 Redis incr。

缺点就是：假设我们允许的阈值是1万，此时计数器的值为 0， 当 1 万个请求在前 1 秒内一股脑儿的都涌进来，这突发的流量可是顶不住的。

缓缓地增加流量处理和一下子涌入对于程序来说是不一样的。

而且一般的限流都是为了限制在指定时间间隔内的访问量，因此还有个算法叫固定窗口。

固定窗口限流

它相比于计数限流主要是多了个时间窗口的概念，计数器每过一个时间窗口就重置。 规则如下：

• 请求次数小于阈值，允许访问并且计数器 +1；
• 请求次数大于阈值，拒绝访问；
• 这个时间窗口过了之后，计数器清零；

看起来好像很完美，实际上还是有缺陷的。

固定窗口临界问题

假设系统每秒允许 100 个请求，假设第一个时间窗口是 0-1s，在第 0.55s 处一下次涌入 100 个请求，过了 1 秒的时间窗口后计数清零，此时在 1.05 s 的时候又一下次涌入100个请求。

虽然窗口内的计数没超过阈值，但是全局来看在 0.55s-1.05s 这 0.5 秒内涌入了 200 个请求，这其实对于阈值是 100/s 的系统来说是无法接受的。

为了解决这个问题引入了滑动窗口限流。

滑动窗口限流

滑动窗口限流解决固定窗口临界值的问题，可以保证在任意时间窗口内都不会超过阈值。

相对于固定窗口，滑动窗口除了需要引入计数器之外还需要记录时间窗口内每个请求到达的时间点，因此对内存的占用会比较多。

规则如下，假设时间窗口为 1 秒：

• 记录每次请求的时间
• 统计每次请求的时间 至 往前推1秒这个时间窗口内请求数，并且 1 秒前的数据可以删除。
• 统计的请求数小于阈值就记录这个请求的时间，并允许通过，反之拒绝。

但是滑动窗口和固定窗口都无法解决短时间之内集中流量的突击。

我们所想的限流场景是：

每秒限制 100 个请求。希望请求每 10ms 来一个，这样我们的流量处理就很平滑，但是真实场景很难控制请求的频率，因此可能存在 5ms 内就打满了阈值的情况。

当然对于这种情况还是有变型处理的，例如设置多条限流规则。不仅限制每秒 100 个请求，再设置每 10ms 不超过 2 个。

再多说一句，这个滑动窗口可与TCP的滑动窗口不一样。

TCP的滑动窗口是接收方告知发送方自己能接多少“货”，然后发送方控制发送的速率。

接下来再说说漏桶，它可以解决时间窗口类的痛点，使得流量更加平滑。

漏桶算法

如下图所示，水滴持续滴入漏桶中，底部定速流出。

如果水滴滴入的速率大于流出的速率，当存水超过桶的大小的时候就会溢出。

规则如下：

• 请求来了放入桶中
• 桶内请求量满了拒绝请求
• 服务定速从桶内拿请求处理

可以看到水滴对应的就是请求。

它的特点就是宽进严出，无论请求多少，请求的速率有多大，都按照固定的速率流出，对应的就是服务按照固定的速率处理请求。

看到这想到啥，是不是和消息队列思想有点像，削峰填谷。

一般而言漏桶也是由队列来实现的，处理不过来的请求就排队，队列满了就开始拒绝请求。

看到这又想到啥，线程池不就是这样实现的嘛？

经过漏洞这么一过滤，请求就能平滑的流出，看起来很像很挺完美的？实际上它的优点也即缺点。

面对突发请求，服务的处理速度和平时是一样的，这其实不是我们想要的。

在面对突发流量我们希望在系统平稳的同时，提升用户体验即能更快的处理请求，而不是和正常流量一样，循规蹈矩的处理（看看，之前滑动窗口说流量不够平滑，现在太平滑了又不行，难搞啊）。

而令牌桶在应对突击流量的时候，可以更加的“激进”。

令牌桶算法

令牌桶其实和漏桶的原理类似，只不过漏桶是定速地流出，而令牌桶是定速地往桶里塞入令牌，然后请求只有拿到了令牌才能通过，之后再被服务器处理。

当然令牌桶的大小也是有限制的，假设桶里的令牌满了之后，定速生成的令牌会丢弃。

规则：

• 定速的往桶内放入令牌
• 令牌数量超过桶的限制，丢弃
• 请求来了先向桶内索要令牌，索要成功则通过被处理，反之拒绝

看到这又想到什么？Semaphore 信号量啊，信号量可控制某个资源被同时访问的个数，其实和咱们拿令牌思想一样，一个是拿信号量，一个是拿令牌。

只不过信号量用完了返还，而咱们令牌用了不归还，因为令牌会定时再填充。

再来看看令牌桶的伪代码实现，可以看出和漏桶的区别就在于一个是加法，一个是减法。

可以看出令牌桶在应对突发流量的时候，桶内假如有 100 个令牌，那么这 100 个令牌可以马上被取走，而不像漏桶那样匀速的消费。所以在应对突发流量的时候令牌桶表现的更佳。

小结令牌桶算法的优点

1）平滑的流量控制：令牌桶算法能够平滑处理请求流量，避免了突发流量对系统造成的冲击。

2）突发流量处理：由于桶的容量可以缓冲突发流量，系统可以在短时间内处理更多的请求，而不会立即拒绝。

令牌桶算法使用时的注意点：

1）桶容量的配置：

• 如果桶的容量设置过小，可能会导致系统频繁地拒绝请求，从而影响用户体验。
• 如果桶的容量设置过大，可能会导致系统在短时间内处理过多的请求，从而增加系统负担。

2）令牌生成速率：

• 令牌生成速率需要根据实际需求进行调整。如果速率设置过低，可能无法满足用户的请求；如果速率设置过高，可能会导致系统负担过重。

限流算法小结

上面所述的算法其实只是这些算法最粗略的实现和最本质的思想，在工程上其实还是有很多变型的。

从上面看来好像漏桶和令牌桶比时间窗口算法好多了，那时间窗口算法有什么用？

并不是的，虽然漏桶和令牌桶对比时间窗口对流量的整形效果更佳，流量更加得平滑，但是也有各自的缺点（上面已经提到了一部分）。

拿令牌桶来说，假设你没预热，那是不是上线时候桶里没令牌？没令牌请求过来不就直接拒了么？

这就误杀了，明明系统没啥负载现在。

再比如说请求的访问其实是随机的，假设令牌桶每20ms放入一个令牌，桶内初始没令牌，这请求就刚好在第一个20ms内有两个请求，再过20ms里面没请求，其实从40ms来看只有2个请求，应该都放行的，而有一个请求就直接被拒了。

这就有可能造成很多请求的误杀，但是如果看监控曲线的话，好像流量很平滑，峰值也控制的很好。

再拿漏桶来说，漏桶中请求是暂时存在桶内的，这其实不符合互联网业务低延迟的要求。

所以漏桶和令牌桶其实比较适合阻塞式限流场景，即没令牌我就等着，这样就不会误杀了，而漏桶本就是等着，比较适合后台任务类的限流。

而基于时间窗口的限流比较适合对时间敏感的场景，请求过不了您就快点儿告诉我，等的花儿都谢了。

单机限流和分布式限流

本质上单机限流和分布式限流的区别其实就在于 “阈值” 存放的位置。

单机限流就上面所说的算法直接在单台服务器上实现就好了，而往往我们的服务是集群部署的。

因此需要多台机器协同提供限流功能。

像上述的计数器或者时间窗口的算法，可以将计数器存放至 Redis 等分布式 K-V 存储中。

例如滑动窗口的每个请求的时间记录可以利用 Redis 的 zset 存储，利用ZREMRANGEBYSCORE 删除时间窗口之外的数据，再用 ZCARD计数。

像令牌桶也可以将令牌数量放到 Redis 中。

不过这样的方式等于每一个请求我们都需要去Redis判断一下能不能通过，在性能上有一定的损耗。

所以有个优化点就是 「批量获取」，每次取令牌不是一个一取，而是取一批，不够了再去取一批，这样可以减少对 Redis 的请求。

不过要注意一点，批量获取会导致一定范围内的限流误差。比如你取了 10 个此时不用，等下一秒再用，那同一时刻集群机器总处理量可能会超过阈值。

其实「批量」这个优化点太常见了，不论是 MySQL 的批量刷盘，还是 Kafka 消息的批量发送还是分布式 ID 的高性能发号，都包含了「批量」的思想。

当然，分布式限流还有一种思想是平分，假设之前单机限流 500，现在集群部署了 5 台，那就让每台继续限流 500 呗，即在总的入口做总的限流限制，然后每台机子再自己实现限流。

限流的难点

可以看到，每个限流都有个阈值，这个阈值如何定是个难点。

定大了服务器可能顶不住，定小了就“误杀”了，没有资源利用最大化，对用户体验不好。

我能想到的就是限流上线之后先预估个大概的阈值，然后不执行真正的限流操作，而是采取日志记录方式，对日志进行分析查看限流的效果，然后调整阈值，推算出集群总的处理能力，和每台机子的处理能力(方便扩缩容)。

然后将线上的流量进行重放，测试真正的限流效果，最终阈值确定，然后上线。

我之前还看过一篇耗子叔的文章，讲述了在自动化伸缩的情况下，我们要动态地调整限流的阈值很难。

于是基于TCP拥塞控制的思想，根据请求响应在一个时间段的响应时间P90或者P99值来确定此时服务器的健康状况，来进行动态限流。在他的 Ease Gateway 产品中实现了这套算法，有兴趣的同学可以自行搜索。

其实真实的业务场景很复杂，需要限流的条件和资源很多，每个资源限流要求还不一样。

限流组件

一般而言，我们不需要自己实现限流算法来达到限流的目的，不管是接入层限流还是细粒度的接口限流，都有现成的轮子使用，其实现也是用了上述我们所说的限流算法。

比如Google Guava 提供的限流工具类 RateLimiter，是基于令牌桶实现的，并且扩展了算法，支持预热功能。

阿里开源的限流框架 Sentinel 中的匀速排队限流策略，就采用了漏桶算法。

Nginx 中的限流模块 limit_req_zone，采用了漏桶算法，还有 OpenResty 中的 resty.limit.req库等等。

具体的使用还是很简单的，有兴趣的同学可以自行搜索，对内部实现感兴趣的同学可以下个源码看看，学习下生产级别的限流是如何实现的。

4680.如何设计一个秒杀功能？

回答重点

面试官针对这个问题不指望候选人可以系统地回答出完且可落地的方案。只是想考察候选人是否拥有高并发大流量场景下的处理思路或者说能考虑到的一些关键点。

针对秒杀场景，我们需要先和面试官说出以下几个需要解决的问题点：

1. 瞬时流量的承接
2. 防止超卖
3. 预防黑产
4. 避免对正常服务的影响
5. 兜底方案

然后可以从前后端两个视角向面试官阐述整体的设计点：

首先是前端：

• 利用 CDN 缓存静态资源（秒杀页面的 HTML、CSS、JS 等），减轻服务器的压力
• 客户端限流，在前端随机限流，降低请求量
• 按钮防抖，防止用户重复多次点击发出大量请求

其次是后端：

• Nginx（或其他接入层）做统一接入，负载均衡与流量过滤、限流
• 业务端限流，可以自定义实现本地 guava 限流或利用 sentinel 等
• 服务拆分，将秒杀功能拆分为独立的服务，避免对现有服务产生影响
• 秒杀数据的拆分和缓存，缓存可以使用分布式缓存或本地缓存方案，且需要缓存预热
• 精准地库存扣减，防止超卖发生
• 风控识别黑产，进行流量防控且需要动态黑名单机制
• 验证码、答题等手段预防脚本刷单
• 幂等操作，防止重复下单
• 业务手段降低并发量，例如通过预约、预售。
• 兜底方案，如果服务压力过大或者代码有漏洞，那么关闭秒杀直接返回秒杀结束，降低服务压力及时止损。

详细分析

瞬时流量的承接

一般情况下，秒杀的流量特性就是持续性短和大。

流量集中在活动即将开始的时候，会有很多用户开始持续性地刷新页面。前端资源的访问也需要损耗大量的资源，因此需要利用 CDN 缓存秒杀页面的一些静态资源，将这部分压力给到 CDN 厂商。

并且静态资源放在 CDN 厂商那之后，地理位置也距离用户更近，用户访问也就更快，体验上也更好！

秒杀页面可手动推给 CDN 预热。

秒杀流量还有个特点，就是大部分请求实际都是无效的，因为秒杀的商品库存往往都是个位数，而抢购的用户是其成千上万倍。

假设有 100 万的请求来抢购一台 iPhone，那么需要放这 100 万请求直接打到后端服务吗？显然不需要。

针对这个情况，我们就需要层层过滤请求。

例如前面提到的客户端限流，即在前端随机限流，降低请求量。说的更直白一些即部分用户点击抢购按钮，但是请求都发不到后端，直接前端代码返回秒杀结束。（如果预测量是在太大，可以这样操作，毕竟也是随机的）

如果前端请求发出来了，那么可以利用 nginx 统一接入，针对更大的流量可以在 nginx 前面再加 lvs。

lvs 四层转发请求打到多台 nginx 上， nginx 再负载均衡到多台后端服务，且 nginx 有限流功能，例如 ip 限流，还可以配置黑名单等等，其实已经可以拦截大量请求流量。

请求到达后端服务之前还可以再进行限流，比如使用 sentinel 再拦截一道。

最终请求打到后端服务，涉及到一些读取数据和写数据的操作。如果量级不大且数据库配置高，理论上可以用数据库来承接（数据库层面也是有优化的，后面介绍）。

这时候也可以利用缓存来承接读写，可以用本地缓存或分布式缓存，如 Redis。

最终一个相对而言比较完整的请求链路如下：

我把 DNS 解析也加上了，因为对一些大公司而言，DNS 其实也是一个分流的手段。

在量级没这么大的情况下，实际上的秒杀架构不需要如上图所示，例如不需要引入 lvs、本地缓存之类的。

库存扣减设计

先看一下正常扣减库存的思路：

这样的设计会有什么问题？并发问题，导致超卖。

此时可以加锁，比如利用数据库的锁，针对这个场景数据库常用的是乐观锁。

1
2

update inventory set available_inventory = available_inventory - 1
where sku_id = 1 and available_inventory > 0;

数据库热点行问题解决方案

如果使用这个语句，在高并发场景下，实际上就会产生热点行问题。

我之前公司基于数据库扣减方案，压测单台机子下单链路的并发只能达到 70。单个扣减库存的接口并发只有 200 就把数据库 CPU 压满了。（各公司实际内部业务不同，仅供参考）

数据库补丁优化

我们当时数据库用的是阿里云的 RDS，实际上有一个可落地的优化方案：Inventory hint + Returning。

如果你公司本身用的就是阿里云的 RDS，这个改造成本就很低，仅需在 SQL 上填写一些 hint 即可。

在 SQL 表名前加 /*+ COMMIT_ON_SUCCESS ROLLBACK_ON_FAIL TARGET_AFFECT_ROW(1)*/

1
2
3
4

update /*+ COMMIT_ON_SUCCESS ROLLBACK_ON_FAIL
  TARGET_AFFECT_ROW(1)*/ inventory 
 set available_inventory = available_inventory - 1
where sku_id = 1 and available_inventory > 0;

Inventory hint 原理简单介绍：

• COMMIT_ON_SUCCESS：当前语句执行成功就提交事务上下文。
• ROLLBACK_ON_FAIL：当前语句执行失败就回滚事务上下文。
• TARGET_AFFECT_ROW(NUMBER)：如果当前语句影响行数是指定的就成功，否则语句失败。

设置了这几个 hint 后，当前的语句会按照主键（或唯一键）分组，将相同行的请求修改分为一组，分组后仅组内第一条 SQL 需要抢锁，后续的都不需要申请锁，减少申请锁的流程。

然后组内第一条 SQL 已经遍历 B+树查询到数据了，后续组内库存扣减直接改即可，不用再次查询。且组内 SQL 都修改完之后，仅需一次分组提交事务即可。

根据阿里云介绍，结合 Inventory hint 单行 TPS 可达 3.1w：

还可以配合 Returning 使用：

1
2
3
4

CALL dbms_trans.returning("*", "update /*+ COMMIT_ON_SUCCESS ROLLBACK_ON_FAIL
  TARGET_AFFECT_ROW(1)*/ inventory 
 set available_inventory = available_inventory - 1
where sku_id = 1 and available_inventory > 0;");

正常情况下，如果我们 update 扣减了一次库存之后，如果想得知最新的库存，那么需要再执行一次 select 操作，而 Returning 可以直接返回实时的库存，减少一次查询。

利用 Returning，我们可以得知实时的库存，发现没库存后，可以直接设置一个标志位，表明秒杀已经结束，快速 fail 请求，降低服务的压力。

还有一个 Statement queue 我之前没用到，关于这几个 hint 的详情，可以查看这个介绍链接

库存拆分

除了数据库补丁优化，从业务角度，我们可以将库存进行拆分。

上面举例是 1 个库存，但有时候的秒杀的库存会更多，例如 1000 个库存，此时就可以将这 1000 个库存拆分成 100 个小库存，每个小库存内有 10 个库存。

这样其实就是人为的把热点行拆分了，可以把小库存分散到不同的表或者库中，等于将并发度提升了 10 倍。

看起来挺简单，实际对于整个库存扣减流程的改造还是挺大的，例如分桶的库存调配、创建库存时分桶的库存分配、表的映射、库的映射等等。

插入库存扣减流水

既然直接 update 有热点行问题，那么就将 update 改为 insert 。

实际上用户的购买从更新库存变成插入流水，然后异步定时将流水库存同步到剩余库存中。

这个手段确实避免了热点行的问题，但插入数据不好控制总的数据量，容易导致超卖。

可以跟面试官提一下这个方案，跟他说清这个方案是有超卖的问题。表明你知道这个思路，也知道这个方案的缺点。

这个思路实际上在非限制库存的热点行场景可以使用。

缓存

利用缓存来承接热点数据是很多人都熟知的方案，例如使用 Redis。

可以将库存提前同步到 Redis 中，然后利用 redis + lua 脚本控制库存的扣减。

lua 脚本的内容实际上很简单，我用文字来描述一下：

1. 根据商品 key 获取库存
2. 如果有则库存-1，返回新库存
3. 如果没库存，则返回没库存

redis + lua 可以保证操作的原子性，且性能足够优秀，因此是一个非常高效的库存扣减方案。

然后 redis 扣减完毕之后，可以发送一个异步消息（消息队列削峰填谷），后端服务异步消费把数据库中的库存给扣了，实现最终一致性。

看到这肯定有同学会问：“redis 操作成功后，mq发送失败怎么办？”

因此，我们还需要一个准实时对账机制，lua 脚本内不仅要扣减库存，还需要利用 zset 增加流水，score 设置为时间。定时拉取一段时间流水记录比对数据库的库存是否一致，如果不一致则补偿。

至于本地缓存，理论上性能更高，但是方案设计上会更复杂，因为库存被分配到多个应用中。需要在秒杀预热的时候，给后端服务预分配好库存，然后应用各自承接库存扣减，也需要做好对账，防止意外的发生。

预防黑产

大一点的公司都会有风控机制，借助一些算法对用户的来源、行为数据等等进行分析，如果发现不法分子，则将其加入到黑名单中。

脚本抢购实际上可以用验证码、答题等机制拦截，并且这种机制也可以打散用户的请求，降低瞬时流量高峰。

幂等设计

可以看这题：如何避免用户重复下单（多次下单未支付，占用库存）

业务手段

预约

例如 Nike 设计就是抢购，预约有一个比较长的时间段，例如 15 分钟。然后预约通过后等待最终抽签结果即可。

这样的设计通过一段时间的预约，可减少瞬时的压力，再异步通过后台实现抽签来间接解决秒杀的问题。

预售

例如现在的电商活动都搞定金预售。

通过下定让用户感觉这个商品已经到手了，不需要再等到双十一或者 618 零点准时抢购，均摊了请求，减少准点抢购的压力。

避免对正常服务的影响

大部分公司秒杀都是和正常服务糅合在一起的，没有做区分。

如果成本允许，且为了避免对正常业务产生影响，则可以将秒杀单独剥离出一套，独立域名、独立服务器部署等。

不过这样实现起来其实很麻烦，最终的数据还是需要同步的正常服务中的，成本比较大。

兜底方案

或许在真正的业务中，很少有人会做兜底方案，都仅考虑正向业务，但是兜底确实很重要！

所以在业务上的设计我们要尽量考虑异常极端情况，设计一个简单的兜底也比没兜底好。

在面试中，那就得疯狂兜底！向面试官展示出你的方案面面俱到！

针对秒杀，其实最简单的方案就是加个开关：关闭秒杀，直接返回秒杀结束。

这个兜底是为了避免极端情况发生，严重影响正常业务的进行或产生资损。

因为秒杀对用户而言本身是一个可以接受失败的场景，没抢到很正常。只要用户来参加我们的活动，营销目的也达到了，所以在严重影响正常业务进行或者发现代码出现漏洞，被人薅羊毛的情况下，关闭秒杀是最好的选择！

4945.即时通讯项目中怎么实现历史消息的下拉分页加载？

业务场景

一般在即时通讯项目（比如聊天室）中，我们会采用下拉分页的方式让用户加载历史消息记录。

区别于标准分页每次只展示当前页面的数据，下拉分页加载是 增量加载 的模式，每次下拉时会请求加载一小部分新数据，并放到已加载的数据列表中，从而形成无限滚动的效果，确保用户体验流畅。

比如用户有 10 条消息记录，以 5 条为单位进行分页，刚进入房间时只会加载最新的 5 条消息：

下拉后，会加载历史的第 6 - 10 条消息：

理解了业务场景后，再看下实现方案，为什么不建议使用传统分页实现下拉加载？

传统分页的问题

在传统分页中，数据通常是 基于页码或偏移量 进行加载的。如果数据在分页过程发生了变化，比如插入新数据、删除老数据，用户看到的分页数据可能会出现不一致，导致用户错过或重复某些数据。

举个例子，对于即时通讯项目，用户可能会持续收到新的消息。如果按照传统分页基于偏移量加载，第一页已经加载了第 1 - 5 行的数据，本来要查询的第二页数据是第 6 - 10 行（对应的 SQL 语句为 limit 5, 5），数据库记录如下：

结果在查询第二页前，突然用户又收到了 5 条新消息，数据库记录就变成了下面这样。原本的第一页，变成了当前的第二页！

这样就导致查询出的第二页数据，正好是之前已经查询出的第一页的数据，造成了消息重复加载。所以不建议采用这种方法。

推荐方案 - 游标分页

为了解决这种问题，可以使用游标分页。使用一个游标来跟踪分页位置，而不是基于页码，每次请求从上一次请求的游标开始加载数据。

一般我们会选择数据记录的唯一标识符（主键）、时间戳、或者具有排序能力的字段作为游标。比如即时通讯系统中的每个消息，通常都有一个唯一自增的 id，就可以作为游标。每次查询完当前页面的数据后，可以将最后一条消息记录的 id 作为游标值传递给前端（客户端）。

当要加载下一页时，前端携带游标值发起查询，后端操作数据库从 id 小于当前游标值的数据开始查询，这样查询结果就不会受到新增数据的影响。

对应的 SQL 语句为：

1
2
3
4

SELECT * FROM messages
WHERE id < :cursorId
ORDER BY id DESC
LIMIT 5;

扩展知识

使用游标的优点

使用游标分页除了能解决数据不一致（数据重复）的问题，还能起到性能优化的作用。

游标分页通常比基于偏移量（Offset）的分页更高效，因为传统的偏移分页需要跳过一定数量的记录，随着偏移量的增加，查询性能会下降。而游标分页只需要查询自上一个游标之后的记录，可以利用数据库索引进行快速定位，直接跳到该值的位置，从而减少了数据库的扫描和处理负担，提高了查询速度。

游标分页的应用场景

游标分页的应用场景很多，特别适用于增量数据加载、大数据量的高性能查询和处理。除了 IM 系统获取历史消息记录之外，常见场景还有社交媒体信息流、内容推荐系统、数据迁移备份等等。

如何选择游标字段

一般游标字段要具备以下特性：

1. 唯一性：要确保在分页过程中能够准确地定位记录。
2. 排序稳定性：游标字段的排序结果要相对稳定，避免分页过程中数据的丢失或重复。
3. 性能：游标字段一般要设置为索引，以确保分页操作的高效。
4. 避免频繁变化：避免使用频繁变化（实时更新）的字段，减少分页时记录丢失或重复的情况。

对于即时通讯项目的消息记录，除了 ID 之外，还可以选择时间戳作为游标。因为 IM 系统中，消息通常是按照时间顺序排列和查询的，时间戳提供了一种自然的排序方式，能够避免由于数据插入或删除造成的数据不一致问题。但是也要注意，如果时间戳的精度不够（如秒级），高并发情况下可能会出现时间戳重复，从而导致分页结果中的数据丢失或重复。

所以一种更规范的方案是，使用 时间戳加 ID 字段作为复合游标。在时间戳相同的情况下，通过 ID 确保唯一性和稳定性。

示例 SQL 语句如下：

1
2
3
4

SELECT * FROM messages
WHERE (timestamp < :cursorTimestamp OR (timestamp = :cursorTimestamp AND id < :cursorId))
ORDER BY timestamp DESC, id DESC
LIMIT 10;

9801.HashMap 是不是线程安全的？如果让你来实现一个线程安全的 HashMap 你要怎么设计？如果不用加锁你要怎么设计？

回答重点

HashMap 是 非线程安全 的。因为 HashMap 的内部实现并没有加锁，多个线程同时访问和修改时可能会引发数据竞争，导致数据不一致或陷入死循环等问题。

如何实现一个线程安全的 HashMap

要实现一个线程安全的 HashMap，有多种设计方案，下面是几种常见的实现方法：

使用 Collections.synchronizedMap

Java 提供了一个简单的方法，可以将非线程安全的 HashMap 包装为线程安全的版本：

1

Map<String, String> synchronizedMap = Collections.synchronizedMap(new HashMap<>());

这种方法通过在 HashMap 的方法上加 synchronized 锁实现线程安全。不过，这种方式对整个 Map 加锁，会导致较高的锁竞争和性能开销，尤其是在高并发情况下。

参考ConcurrentHashMap 的分段锁

使用分段锁（在 Java 8 之后更改为 CAS + 分段桶机制）来实现线程安全，同时避免了整个 Map 加锁的问题。

• 在 Java 7 中，ConcurrentHashMap 将 Map 划分为多个 Segment，每个 Segment 是一个小的 HashMap，只有在同一个 Segment 上有冲突时才会加锁，减少了锁的粒度。
• 在 Java 8 中，ConcurrentHashMap 引入了 CAS（Compare-And-Swap）操作和分段桶（Bucket）机制，大大减少了锁的使用，进一步提升了并发性能。

不使用锁的设计方案

如果要实现一个线程安全的 HashMap 且不使用锁，可以考虑以下几种方案：

CAS（Compare-And-Swap）+ 分段机制

可以借鉴 ConcurrentHashMap 的思想，使用分段机制结合 CAS 操作来减少锁的需求。以下是实现思路：

1. 分段机制：将 Map 分成多个分段（如 16 个分段），每个分段是一个小的 HashMap。通过 key 的 hash 值定位到具体的分段，这样可以减少锁的粒度。
2. CAS 操作：CAS 是一种无锁操作，可以避免传统锁带来的性能开销。CAS 操作检查某个变量是否等于期望值，如果是，则将其更新为新值；否则，返回失败。使用 CAS 操作可以在无锁的情况下实现线程安全的写入。
3. 内部状态控制：对于需要扩容的操作，可以借助 CAS 和重试机制。比如扩容时，只对需要扩容的分段进行扩展，而不是整个 Map，以减少性能影响。

Copy-on-Write 机制

Copy-on-Write 是一种无锁实现的思路，适合读多写少的场景。实现思路如下：

1. 每次写入操作（如 put 或 remove）时，复制当前的 Map，在副本上进行修改，然后将副本替换为当前的 Map。
2. 读取时始终访问当前的 Map 实例，保证不会受到写入操作的影响。

这种方式的缺点是每次写入都需要复制整个 Map，会带来较大的内存和性能开销，所以只适合读多写少的场景。

扩展知识

• 1923. 什么是 CAS？
• 464. Java 中的 CopyOnWriteArrayList 是什么？

11704.让你设计一个购物车功能，怎么设计？

回答重点

购物车主要功能包括：加购、商品列表展示和结算下单。

针对这几个功能，购物车至少需要包括：商品SKUID、数量、加购时间和勾选状态，具体的图片、标题、描述等可以实时获取，购物车不存储。

针对加购，需要考虑用户是否登录：

• 未登录用户：用 Cookie 或本地存储（如LocalStorage）暂存购物车数据，避免丢失。
• 登录用户：数据同步到数据库（如MySQL），这样就支持多端（PC、APP）同步。

商品列表展示，对用户是否登录情况下也有所区别：

• 未登录用户：Cookie 或本地存储（如LocalStorage）采用 json 格式存储即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

{
    "cart": [
        {
            "SKUID": 123,
            "timestamp": 1747036940,
            "count": 1,
            "selected": true
        },
        {
            "SKUID": 456,
            "timestamp": 1747036941,
            "count": 5,
            "selected": false
        }
    ]
}

• 登录用户：直接从数据库查询，注意 user_id 字段需要建立索引，优化查询

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

CREATE TABLE cart (  
    id BIGINT PRIMARY KEY AUTO_INCREMENT,  
    user_id BIGINT NOT NULL,  
    sku_id BIGINT NOT NULL,  
    count INT DEFAULT 1 COMMENT '数量',  
    selected TINYINT DEFAULT 1 COMMENT '是否选中结算',  
    create_time DATETIME DEFAULT CURRENT_TIMESTAMP,  
    update_time DATETIME DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,  
    KEY idx_user(user_id)
);  

结算下单后，从购物车中移除selected=true的商品，这个步骤可以异步操作，能接受一定的延时，因为一般来说用户下单后不会立刻访问购物车，而且即使访问了，数据还在影响不大。

不过现在有些产品的加购设计要求用户必须登录，比如京东网页版，点击加入购物车之后，自动跳转到登录页。

扩展知识

存储方案详解

未登录用户：

• Cookie：存储少量数据（如商品ID、数量），但有大小限制（约4KB），且客户端和服务端的每次交互，都会自动带着 Cookie 往返。
• LocalStorage：存储上限5-10MB，仅前端访问，不需要每次都带着，节省带宽，适合存大量商品数据。

登录用户：

除了利用数据库存储，也可以采用 Redis 来存储，比如用 Redis Hash 存储（Key=用户ID，Field=商品ID，Value=数量等数据）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

{
    "KEY": 1, // 用户id
    "VALUE": [
        {
            "FIELD": 123, //skuID
            "VALUE": {
                "timestamp": 1747036940,
                "count": 1,
                "selected": true
            }
        },
        {
            "FIELD": 456, //skuID
            "VALUE": {
                "timestamp": 1747036941,
                "count": 5,
                "selected": false
            }
        }
    ]
}

Redis 存储的好处就是响应更快，但是可靠性不如 MySQL，极端场景容易丢数据，但是购物车这个场景实际上可以容忍一定数据的丢失，问题不大。

不过 MySQL 支持事务，且结构化存储后，查询比较方便，一般而言推荐 MySQL 存储。

登录后合并策略

用户未登录时选择了很多东西，随后登录后需要将将临时购物车数据与服务端数据库中的购物车数据合并。

此时会遇到一些冲突数据：

• 商品重复：相同SKU数量累加（如临时车有2件，数据库有3件 → 合并为5件）。
• 库存不足：自动调整数量至最大可用库存，并弹窗提示用户

Redis 持久化丢数据

• AOF 写回策略设置 always 能一定保证数据不丢失吗？