系统设计理解

2025-04-30 12:24:32 # 面试 #场景题

通用模板：

首先该处系统设计的架构：

明晰项目诉求：点赞系统即为存储每一个用户发布的帖子有哪些人点赞了，总的点赞数是多少；每一个用户具体点赞了哪些帖子，赞过的帖子总数是多少（其实这个逻辑友友们点开自己的牛客收藏和点赞其实就一目了然了）整体上是一个多对多的关系。

同时关注请求量，是否需要做高并发/高可用的扩展设计；

此外对实时性是否也要要求，追求强一致性还是最终一致性

确定业务逻辑：对于每个帖子，需要记录点赞的用户，点赞的总人数，取消点赞时点赞数要相应减1，用户查看自己发布的帖子需要显示总点赞数，以及展示一个点赞用户的列表（简单概括为增删改查）。同理，对于观看帖子的用户，需要记录用户点赞了哪些帖子，用户点赞帖子的总数，在我的 - 点赞页面需要展示出用户点赞过的帖子……

架构设计：存储（MySQL/Redis）+服务（是否需要拆分为多个服务）

前期并发量不大的情况下，可以将数据直接存储到MYSQL中，需要时前端将MysQL中的数据直接读取到内存中进行处理，但是当并发量上来之后，这样强依赖的同步调用会提升接口延迟。因此需要增加中间件，比如缓存redis。

当并发量再一次上升时，可以通过提升服务器硬件或者使用异步/并发/多协程的方式提升单服务器的并发量，但是当并发量再一次提升时，单台机器的性能的瓶颈导致无法处理过多的请求，因此可以通过源ip哈希+轮询算法实现的负载均衡的方式分布式部署多台服务器，进行分流（将目标请求资源，比如红包通过负载均衡放在一个SET中，每个SET中的数据库和其他服务器数据库都是独立的，然后再一次将红包通过哈希算法分配到当前SET的一个server中，server中有一个请求队列，用户有序、同步将每个请求拿出来消费共享资源，从而避免多个请求竞争资源问题。同时建立一个缓冲队列存放超出阈值的流量，超出阈值的流量待请求队列中的申请下降之后，再将缓存队列的请求转移至请求队列）。

当并发量再一次上升时，可能会遇到数据库读写锁竞争问题，采取主从复制，读写分离的方式解决。

最后，加入缓存层Redis后，那么面试官肯定会问到一个经典的问题，那就是：缓存和数据库的一致性是如何解决的，这里有多种解决方案，但常用的其实也就是两种：先更新数据库，再删除缓存（适用于读多写少且对一致性要求较高的场景，确保数据库写入成功，再删除缓存，避免因缓存未删除导致的脏读）；通过canle订阅binlog日志，再更新缓存，实现最终一致性。

引入Redis作为缓存后，所有的写请求还是会先写入到数据库，读请求会优先到达缓存层去检查数据，没有再去数据库内加载数据填充到缓存中。

先更新数据库，再删除缓存：

写操作流程：客户端发起写请求 → 更新数据库（INSERT/UPDATE/DELETE）→ 删除对应缓存键 → 返回成功

读操作流程：客户端发起读请求 → 检查缓存是否存在 → 存在则直接返回；不存在则查询数据库 → 将结果写入缓存 → 返回结果

通过canle订阅binlog日志，再更新缓存：

架构流程：MySQL主库写入数据 → Binlog记录变更 → Canal监听Binlog → 解析变更事件（如INSERT/UPDATE/DELETE）→ 发送到消息队列（如Kafka）→ 消费者获取事件并更新Redis缓存

需要注意的一些其余点：

无锁保证线程安全的同时提升并发性

零拷贝，减少CPU资源的损耗

池子化，复用连接，并通过心跳检测保证连接存活

异步/协程/并发，提高并发

分片（动态负载均衡，将目标请求资源，比如红包通过负载均衡放在一个集群中，每个SET中的数据库和其他服务器数据库都是独立的，然后再一次将红包通过哈希算法分配到当前SET的一个server中，server中有一个请求队列，用户有序、同步将每个请求拿出来消费共享资源，从而避免多个请求竞争资源问题。同时建立一个缓冲队列存放超出阈值的流量，超出阈值的流量待请求队列中的申请下降之后，再将缓存队列的请求转移至请求队列。）

队列，分类有缓冲队列（应对突发流量）、请求队列（排队用户请求，用于流量控制、同步控制等）、任务队列（异步执行任务，保证有序性）、消息队列（消息投递，有点对点和发布订阅模式，不同消息队列特性不同）。

1. 扫码登陆

扫码登录，其实涉及到三种角色，需要解决两个问题。

三种角色
- 扫码登录当中涉及到的三种角色：PC端、手机端、服务端。
两个问题
- 手机端如何完成认证
- PC端如何完成登录

扫码登录相比于传统的输入用户号密码登录，其实本质都是账号认证的过程，相信大家入门的第一个项目里一定会有登录这个功能。输入用户名和密码进行提交。服务端接收到用户名和密码，进行用户名和密码的匹配。如果匹配成功，则登录成功。

在用户名密码登陆中，PC端通过账号密码完成认证，服务端在登录完成后会生成一个 TOKEN，与当前登录的用户进行绑定。这个 TOKEN 可以存储在 redis 内，并设置在 redis 内的过期时间，这也是 TOKEN 的过期时间。最后将 TOKEN 返回给客户端。PC端再次请求服务端，需要携带token key，用于标识和证明自己登录的状态。

服务端响应的时候，需要对token key进行校验，通过则正常响应；校验不通过，认证失败；或者token过期，PC端需要再次登录认证，获取新的token key。以上就是整个登录认证的过程。

token主要是用于解决Session的弊端：在 Web 开发中，传统 Session 机制依赖服务器存储用户状态信息，存在分布式系统下的会话共享复杂、跨域请求受限、Cookie 易被窃取及服务器资源占用等弊端。而 Token 机制通过在用户登录后生成包含用户身份信息的令牌（如 JWT），由客户端在后续请求中携带，服务器只需验证令牌有效性即可识别用户。这种无状态设计无需服务器存储会话数据，天然支持分布式架构和跨域场景，且通过加密签名和过期时间设置提升了安全性，有效解决了 Session 在扩展性、跨域兼容性、资源占用及安全风险等方面的问题。

Session 是一种在服务器端记录用户状态的机制。当用户首次访问服务器时，服务器会为该用户创建一个唯一的 Session ID，并将其以 Cookie 的形式发送给客户端。客户端后续的每次请求都会携带这个 Session ID，服务器根据这个 ID 来识别用户，并获取该用户的相关会话数据。

在分布式系统中，由于 Session 数据通常存储在单个服务器上，当用户请求被分发到不同的服务器时，可能会出现无法获取到正确的 Session 数据的问题。为了解决这个问题，需要实现 Session 共享，这会增加系统的复杂性和成本。

如果 Cookie 被窃取，攻击者可以利用这个 Cookie 来冒充合法用户，从而获取用户的敏感信息。此外，由于 Session 数据存储在服务器端，服务器端的安全漏洞可能会导致 Session 数据泄露。

现在换成了扫码登录：

认证不是通过账号密码了，而是由手机端扫码来完成
PC端没法同步获取认证成功之后的凭据，必须用某种方式来让PC端获取认证的凭据。

之所以通过扫码登陆PC端没法同步获取认证成功之后的凭据是因为：在于其基于跨设备异步通信的技术架构与安全机制设计：PC 端、手机端和服务器三方交互时，设备间无法直接通信，需通过服务器中转认证状态，且 HTTP 协议的无状态性决定了 PC 端只能通过轮询或长轮询被动获取结果；同时，用户需在手机端主动确认认证操作，服务器需完成身份验证、临时凭证生成、设备绑定等复杂逻辑后才能发放最终凭据，这一过程涉及状态机严格控制和安全校验（如临时凭证时效性、防中间人攻击），无法在单次请求中同步完成，因此 PC 端必须通过异步方式等待服务器通知才能获取有效凭据。

现在换成了扫码登录，换汤不换药，还是需要让 PC 端获取到认证的 ID。

1.1 二维码生成

扫码登录在PC端生成的二维码，里面不光可以存储数字，还可以存储任何的字符，以二维码的形式展示出来。手机扫码的过程，就是解码的过程。划重点！！理解了手机扫码是解码的过程，那这道题就理解了一大半了

PC 端显示的二维码，其实就是PC端向服务端发起请求后，服务端返回的内容。那这个返回内容是什么呢？可以看做是一个唯一请求ID，能够唯一地代表当前的请求，同时这个唯一的ID 是有状态的，表示这个当前二维码是未扫描还是扫描成功，PC端根据服务端返回的唯一请求ID生成一个二维码。

同时这个唯一请求ID是有过期时间的。这个二维码过了一段时间，我们不扫描，网页会显示已失效，请刷新。在设计上呢可以将唯一请求ID，作为 KEY 存储到 REDIS 内并设置一个失效时间。

综上，这个唯一请求ID最后有三个状态，一个是未扫描，扫描成功还有已失效。已失效就提示它再次进行刷新。

1.2 手机扫码

要进行手机扫码，前提条件是手机的 APP 必须是登录状态的，这个非常重要，也就是手机端已经进行了用户名和密码的登录认证过程。手机端一定会存储登录认证后的 TOKEN。手机扫码识别 PC 端的二维码后会解析出二维码携带的唯一请求ID。也就是PC端向服务端发起请求后，服务端返回的唯一请求ID，手机会显示确认登录的按钮，按下按钮，手机端会将唯一请求ID 和手机认证的 TOKEN 一同发送到服务端进行认证。

1.3 服务端验证

服务端首先会验证手机端的 TOKEN 是否有效，如果有效会验证唯一请求 ID 的状态，如果唯一请求ID 不存在了说明就已经失效了，Redis过期删除。如果唯一请求 ID 存在且当前状态是未扫码的，也就是说 REDIS 存在唯一请求 ID的KEY。此时就会生成一个 PC 端的 TOKEN，与唯一请求 ID进行关联，设置 REDIS 的唯一请求 ID对应的 VALUE 为 PC端登录的 TOKEN。此时 PC 的唯一登录 ID 就产生了，其他情况都是验证失败。

到这里我们简单总结一下：PC端发起登录请求，服务端返回唯一请求ID，PC端根据请求ID生成二维码，处于登录态的手机已获得手机端的登录token，扫码解析出唯一请求ID后，将唯一请求ID和token一同发给服务端，服务端验证唯一请求ID和token后，生成PC端的登录唯一ID。

1.4 PC端获得TOKEN

PC 端在生成完这个二维码之后会启动一个异步请求，向服务端去查询唯一 ID 的状态。

如果是未扫描，REDIS 内存在唯一请求ID的 KEY，而且 VALUE 是空的，说明这个二维码是有效的。
如果服务端的 REDIS 内已经没有唯一请求ID的 KEY 了，那说明就已经失效，提示二维码已经失效。
如果 REDIS 内有唯一请求ID且有对应的 VALUE，则返回扫描成功和关联的 TOKEN，同时 PC 端就会显示登录成功。

补充：PC 端通过什么方式来查询唯一请求 ID 的状态？

轮询，PC 通过轮询的方式一次次的向服务端发送请求查询二维码的状态。（非阻塞）
长轮询，长轮询是指客户端主动给服务端发送二维码状态的查询请求。服务端接收到请求之后会按照情况进行阻塞直至二维码的信息状态更新或者超时。当客户端接收到返回的结果后，若二维码仍未扫描则会继续发送查询的请求，直至状态变化。（阻塞）
WEB SOCKET ，WEB SOCKET 是指前端或者客户端在生成二维码后会与后端建立连接。一旦后端发现二维码状态发生变化，可以直接通过建立主动推送二维码的状态给前端。

1.5 总结

以轮询的方式来获取二维码的状态为例。

1）PC 端展示登录页面，会请求服务端获取唯一请求 ID，然后服务端会生成相应的唯一请求ID，并设置唯一请求 ID 的过期时间和状态，返回唯一请求 ID 给 PC 端。

2）PC 端获取到唯一请求 ID 后生成相应的二维码，PC 端通过轮询的方式请求服务端通过唯一请求 ID 获取二维码的状态。

3）手机端扫描二维码获取唯一请求 ID，将手机端的 TOKEN 和唯一请求 ID 发送给服务端确认登录。

4）服务端验证手机端 TOKEN。然后根据手机端 TOKEN 和唯一请求 ID 生成 PC 端的 TOKEN（该TOKEN和唯一请求ID绑定）。此时 PC 端通过轮循的方式请求服务端，就会获得到这个唯一请求 ID 对应的二维码的状态。如果是成功了，服务端就会返回 PC 端的 TOKEN，显示登录成功。

2. 排行榜怎么设计

可以考虑采用reids的zset结构，它结合了哈希表和跳跃表的特性，每个成员都关联着一个分数（score），Redis 会根据分数对成员进行排序。

将每个用户的得分作为zset中元素的score，将用户ID作为元素的value。使用zset提供的排序功能，可以按照分数从高到低排序。但在分数相同的情况下，redis按照默认的排序规则会按照value值排序，但如果希望按时间进行排序，也就是分数相同的情况下先上榜的排在前面。

在这种情况下，可以将分数score设置为一个浮点数，其中整数部分为得分，小数部分为时间戳。

即：score = 分数 + 1 - 时间戳/1e13

此时在分数相同的情况下，时间早的时间戳小，除以一个很大的数后得到的数字就小，被1减去以后得到的差就会大，也就实现了

分数相同的情况下先上榜的排在前面。

zset的特性：

成员唯一性：和 Set 一样，ZSet 中的每个成员都是唯一的，不会有重复元素。
分数关联：ZSet 中的每个成员都关联着一个分数（score），这个分数是一个浮点数。Redis 正是依据这个分数对成员进行排序，从而实现集合的有序性。
有序排列：成员按照分数从小到大的顺序排列。若多个成员有相同的分数，它们会按照字典序排列。

3. 系统设计的思路⭐

（1）明晰项目诉求：在这里就是设计出一个根据积分或点赞等数据进行排序。同时关注请求量，是否需要做高并发/高可用的扩展设计；此外对实时性是否也要要求，追求强一致性还是最终一致性

（2）确定业务逻辑：新用户上榜后排行榜要产生变化；用户积分发生变化后调整排名

（3）架构设计：存储（MySQL/Redis）+服务（是否需要拆分为多个服务）

大体上排行榜由两部分组成，排序结构和信息汇总结构。也就是我们在排行榜上看到的根据点赞数排出前一百，而信息汇总则是我们点击某一个用户头像可以看到其具体的用户信息。

系统设计初期，前端同步调用排行榜系统，对于并发量不大的情况，可以直接使用MySQL作为存储，直接操作数据库io即可，这里数据库的极限在5000/s。也可以先把全量数据从数据库里取出来后在内存中进行排序（前提是数据量不大的情况下）

但随着并发量和用户量上升，这种强依赖的同步调用会增加接口延迟。

这时可以增加中间层，也就是应对接口性能提不上去的三板斧之一（缓存，消息队列，分库分表）。如使用Rocket MQ或Kafka等消息队列（MQ）。流量大时可对排行榜系统起到削峰作用，还可批量插入数据库减少IO次数，提高插入效率。不过，使用MQ后要做好幂等处理（八股提问，MQ的消息幂等有哪些方式可以实现）。

当流量和并发量持续上升，数据库读写锁竞争加剧，可采用主从分离等方式均摊读压力，当然也可以直接考虑使用Redis作为排行榜。利用Redis的sortset类型排序（这里需要掌握zset，相关的八股文也要熟悉，可能会被问到），如排行评论数可使用ZINCRBY命令更新，查询用ZREVRANGE命令获取前N名排名和分数。

架构上可以由Redis作为消费者，它订阅MQ消息，消费时做幂等判断（确保同一条消息不会被重复处理），用Lua脚本保证操作原子性。（这段话可以作为经典话术使用）

4. 高并发如何设计⭐

高并发意味着大流量，需要运用技术手段抵抗流量的冲击，这些手段好比操作流量，能让流量更平稳地被系统所处理，带给用户更好的体验。我们需要解决多个进程或线程同时（或者说在同一段时间内）访问同一资源产生的并发问题。

我们常见的高并发场景有：淘宝的双11、春运时的抢票、微博大V的热点新闻等。除了这些典型事情，每秒几十万请求的秒杀系统、每天千万级的订单系统、每天亿级日活的信息流系统等，都可以归为高并发。

4.1 解决方法

1）纵向扩展

它的目标是提升单机的处理能力，方案又包括：

1、提升单机的硬件性能：通过增加内存、 CPU核数、存储容量、或者将磁盘升级成SSD 等堆硬件的方式来提升。

2、提升单机的软件性能：使用缓存减少IO次数，使用并发或者异步/协程的方式增加吞吐量。

2）横向扩展

横向扩展随之会发生两个主要问题：

问题1;用户访问IP多了，怎么解决？

问题2：数据库出现瓶颈怎么办？

针对问题一：因为单机性能总会存在极限，所以最终还需要引入横向扩展，通过集群部署以进一步提高并发处理能力，重要部分是负载均衡。

负载均衡的主要作用是：

流量分发：将客户端请求均匀分配到集群中的多个节点，避免单个节点过载，充分利用所有节点的资源。（示例：当 10 万并发请求到达集群时，负载均衡器将请求分配到 100 个节点，每个节点处理 1000 并发，远低于单机极限）
高可用性：监控节点健康状态，自动屏蔽故障节点，将请求路由到正常节点，避免单点故障影响整体服务。
性能优化：根据节点当前负载（如 CPU 利用率、内存占用、连接数）动态调整分发策略，实现资源的最优利用

负载均衡算法：

轮询（Round Robin）：按顺序依次分配请求，适用于节点性能一致的场景。
最少连接（Least Connections）：将请求分配给当前连接数最少的节点，适应负载不均的情况。
源 IP 哈希（Source IP Hashing）：通过客户端 IP 地址的哈希值固定路由到某节点，实现会话亲和性（如保持用户登录状态），该方法在面对大流量访问时很有用，可以将属性相同的连接归到一个服务器上的，这样属性不同的连接之间互不影响。
加权策略：根据节点性能配置权重（如高配节点权重设为 2，低配设为 1），按比例分配流量。

针对问题二：数据库出现瓶颈怎么办？比如数据库读写锁竞争严重

解决方案有：MySql主从复制与读写分离

写请求走主库：所有写操作（INSERT/UPDATE/DELETE）直接发送到主库，确保数据唯一性和完整性。

读请求走从库：读操作（SELECT）分发到一个或多个从库，利用从库的计算和 IO 资源分担压力。

通过 “主库写、从库读” 的分工，将读压力分散到多个节点，提升系统并发能力和可用性。但需注意从库延迟、数据一致性和主库自身的写瓶颈问题，适用于读多写少的业务场景。一般来说都是通过主从复制（Master-Slave）的方式来同步数据，再通过读写分离（MySQL-Proxy）来提升数据库的并发负载能力这样的方案来进行部署与实施的。

5. 点赞系统设计⭐

在这种情况下应该如何设计点赞系统？那么关于系统设计题，我在上篇文章里已经提到了一些通用的方法论，感兴趣的小伙伴可以去看一看，当然我这里也贴心的贴在这里，帮助大家更好的理解。

（1）明晰项目诉求：点赞系统即为存储每一个用户发布的帖子有哪些人点赞了，总的点赞数是多少；每一个用户具体点赞了哪些帖子，赞过的帖子总数是多少，整体上是一个多对多的关系。

同时关注请求量，是否需要做高并发/高可用的扩展设计；

此外对实时性是否也要要求，追求强一致性还是最终一致性

（2）确定业务逻辑：对于每个帖子，需要记录点赞的用户，点赞的总人数，取消点赞时点赞数要相应减1，用户查看自己发布的帖子需要显示总点赞数，以及展示一个点赞用户的列表（简单概括为增删改查）。同理，对于观看帖子的用户，需要记录用户点赞了哪些帖子，用户点赞帖子的总数，在我的 - 点赞页面需要展示出用户点赞过的帖子……

（3）架构设计：存储（MySQL/Redis）+服务（是否需要拆分为多个服务）

友友们会发现，整体的业务逻辑并不是很复杂，但是因为这是面试题，面试官就会问你在高并发的情况下你设计的系统会有什么问题。这其实也是我回答场景题的惯用套路，根据请求量一步一步迭代自己的设计，我们在实际生产过程中也同样是这样一个步骤，先思考最简单的实，然后一步一步迭代，直到可以抗住高并发，实现高可用（满足面试官的要求）

业务逻辑梳理清楚了，接下来我们就来到存储与服务设计了，因为点赞信息是比较重要的，所以这里还是考虑使用MySQL做持久化存储。（做过黑马点评的友友可能直接就会想到Redis做存储，利用incrby 自增命令快速实现点赞功能，这当然是可以的，但是从系统设计和信息丢失的角度来看，先从MySQL入手可以保证数据的安全性，也更能体现面试者的系统设计能力，逐步优化的一个思想）

5.1 数据库

数据表设计

1、点赞记录表

1）type，也就是业务类型，你是为视频点赞还是为评论点赞，还是为其他业务类型点赞

2）作者ID

3）作品ID

4）userID:点赞人ID

5）点赞时间

6）点赞动作（1 like/ 2 unlike）

2、点赞计数表

1）type，也就是业务类型，你是为视频点赞还是为评论点赞，还是为其他业务类型点赞

2）作者ID

3）作品ID

4）点赞数量

5）取消点赞数量

点赞的业务逻辑

前端用户发起点赞请求到达后端服务。后端服务会判断表内是否有之前的点赞记录，因为前端用户可能会重复的去点击点赞按钮。
- 如果没有记录就插入点赞记录，之后点赞计数表加一
- 如果表内有了用户对作品的点赞记录，就去比较点赞的时间
  - 如果时间小于表内记录的时间，说明当前的请求是之前的请求，丢掉就可以了
  - 如果是大于表内的记录的点赞时间，就继续判断状态
- 如果已经是点赞状态了，说明就是重复的点赞请求，就丢掉就可以了
- 如果是取消点赞的状态，就更新记录为点赞状态即可，同时可以增加点赞计数表的数量加一整个点赞的逻辑就处理完了。

取消点赞的业务逻辑

当前端用户取消点赞，后端服务检查计数表内是否有对应用户对该作品的记录。
- 如果没有，说明之前没有点赞过，直接丢到返回前端即可。
- 如果有记录，继续判断时间，如果时间小于数据库内记录时间，说明是之前的请求，直接丢掉就可以了。
  - 如果是大于表内记录时间，说明就继续判断记录的点赞状态。
    - 如果表内是取消点赞的状态，说明是重复请求了，直接丢到就可以了。
    - 如果表内是点赞状态，更改为取消状态，之后点赞数减一即可。

5.2 并发

点赞过程中的并发问题

1）重复插入问题：在并发情况下，可能会有多个点赞请求同时到达后端，并且都检查到数据库中没有该用户对该作品的点赞记录，然后都执行插入操作，导致重复插入点赞记录。

2）计数不准确问题：当多个点赞请求并发执行时，可能会出现点赞计数表加一的操作不是原子性的情况。例如，两个并发请求同时读取了点赞计数表中的值为 10，然后各自执行加一操作并更新回数据库，最终结果可能是 11 而不是正确的 12。

取消点赞过程中的并发问题

1）重复减一问题：类似于点赞过程中的计数不准确问题，当多个取消点赞请求并发执行时，如果点赞数减一的操作不是原子性的，可能会导致点赞数被多减。例如，当前点赞数为 5，两个并发的取消点赞请求同时读取点赞数并执行减一操作，最终结果可能是 4 而不是正确的 3。

2）状态更新不一致问题：在并发环境下，可能会出现两个请求同时判断点赞状态为点赞，然后一个请求先将其更新为取消状态并减一，另一个请求再更新时可能会出现错误的结果。

可以采用数据库事务来确保操作的原子性和一致性，或者使用分布式锁来保证同一时间只有一个请求能执行点赞或取消点赞的操作。同时，在数据库设计上，可以考虑使用乐观锁或悲观锁机制来防止数据冲突。

5.3 引入redis缓存

当流量大起来以后，此时数据库的读写锁的竞争就会加剧。考虑加入缓存层Redis。

既然引入了缓存，那么面试官肯定会问到一个经典的问题，那就是：缓存和数据库的一致性是如何解决的，这里有多种解决方案，但常用的其实也就是两种：先更新数据库，再删除缓存（适用于读多写少且对一致性要求较高的场景，确保数据库写入成功，再删除缓存，避免因缓存未删除导致的脏读）；通过canle订阅binlog日志，再更新缓存，实现最终一致性。

引入Redis作为缓存后，所有的写请求还是会先写入到数据库，读请求会优先到达缓存层去检查数据，没有再去数据库内加载数据填充到缓存中。

先更新数据库，再删除缓存：

写操作流程：客户端发起写请求 → 更新数据库（INSERT/UPDATE/DELETE）→ 删除对应缓存键 → 返回成功

读操作流程：客户端发起读请求 → 检查缓存是否存在 → 存在则直接返回；不存在则查询数据库 → 将结果写入缓存 → 返回结果

通过canle订阅binlog日志，再更新缓存：

架构流程：MySQL主库写入数据 → Binlog记录变更 → Canal监听Binlog → 解析变更事件（如INSERT/UPDATE/DELETE）→ 发送到消息队列（如Kafka）→ 消费者获取事件并更新Redis缓存

5.4 业务逻辑

查询点赞数：先是去Redis查看某个作品的点赞数，如果存在直接返回给客户端，如果不存在则查询数据库计数表内的数据。然后存储到Redis内，最后返回给客户端数量即可。

点赞列表查询：首先还是会去Redis内查询点赞列表，如果不存在，去mysql里查询，将数据写回到Redis的zset内即可。这里依然要注意zset长度，最后会返回给客户端就可以了。如果存在就进行zset分页（类似于MySQL的分页查询，不用直接返回所有的数据，而是根据分数，这里是时间戳，查询所需要的页面数据即可）。如果页面超过了zset分页范围，超出的部分就会去数据库内查询，拼接结果返回客户端即可。如果未超过zset长度限制，直接返回当前页的数据给前端就可以了。

对于写请求，前端用户发起点赞请求，设计到缓存的更新。这里建议采用canal监听mysql的binlog。根据binlog数据变化，更新缓存内的数据。

涉及到两个操作。一个是更新点赞记录，一个是更新点赞数量，由于点赞记录用的是zset处理，并且是有长度限制的。如果超过长度限制，要删除掉多余的元素。整个操作不是原子的，所以用lua脚本来保证整个过程的原子性。

没有采用直接删除缓存类的数据因为点赞是一个很频繁的动作，如果频繁的删除数据，其实会频繁的去数据库加载数据，缓存的命中率其实就会很低，实际上并没有给数据库降低压力。

5.5 总计

先考虑流量不大的情况，设计出初步的业务逻辑，当流量大起来以后，考虑使用Redis作为缓存，这里考虑缓存和数据库的一致性问题；如果Redis也扛不住了，那就再加上消息队列，进行流量削峰，同时通过异步调用提高客户端的响应速度；最后考虑到数据量庞大的问题，采用分库分表来解决存储和读写效率问题。

系统设计初期，前端同步调用排行榜系统，对于并发量不大的情况，可以直接使用MySQL作为存储，直接操作数据库io即可，这里数据库的极限在5000/s。也可以先把全量数据从数据库里取出来后在内存中进行排序（前提是数据量不大的情况下）但随着并发量和用户量上升，这种强依赖的同步调用会增加接口延迟。

当流量和并发量持续上升，数据库读写锁竞争加剧，可采用主从分离等方式均摊读压力，当然也可以直接考虑引入Redis。

6. 后台服务架构高性能设计

无锁化：多线程处理共享资源不当会导致锁竞争，影响性能。无锁化有串行无锁和结构无锁两种实现。串行无锁如 Redis、Nginx 采用的单线程模型，主从 Reactor 职责链模型让连接读写在同一线程执行，无需同步；结构无锁利用硬件支持的原子操作（如 CAS）实现无锁数据结构，如无锁链表，性能比有锁链表更高。
零拷贝：数据在内核缓冲区和应用程序缓冲区传输时，普通读写存在多次数据拷贝。内存映射让用户空间和内核空间共享内核缓冲区，减少数据拷贝次数；零拷贝技术（如 Linux 的 sendfile）避免 CPU 将数据从一块存储拷贝到另一块存储，提高数据传输效率，RocketMQ、Kafka 等都应用了相关技术。
序列化：数据传输和存储时需序列化与反序列化。序列化技术分为内置类型、文本类型、二进制类型。衡量其性能的指标包括序列化后的字节大小、速度、CPU 和内存消耗，Protobuf、FlatBuffer 等二进制类型在性能上表现突出。选型时要考虑性能、易用性、通用性、兼容性和扩展性。
池子化：通过创建池子提高对象复用，减少重复创建、销毁的开销。常用的池化技术有内存池（解决频繁内存分配释放带来的性能和碎片问题，有 ptmalloc、tcmalloc、jemalloc 等实现）、线程池（限制线程数量并重复使用）、连接池（如数据库、Redis 连接池，需考虑初始化、连接数目等问题）、对象池（缓存对象，避免大量创建，如 Redis 整数对象池）。
并发化：请求并发指将无依赖关系的子任务并发处理，减少总耗时，还可对同种请求批量合并，减少 RPC 调用次数；冗余请求指同时发送多个同样请求，用响应快的结果，适用于初始化或请求少的场景，如企鹅电竞跑马模块。
异步化：处理耗时任务时，同步等待会降低系统吞吐量。调用异步化有 Callback、Future、CPS 等方式，解决代码分散和维护问题；流程异步化将非关键依赖异步处理，如企鹅电竞开播服务，写完存储即响应，后置同步操作异步执行。
缓存：缓存是原始数据的复制集，用空间换时间解决高并发读。适合使用缓存的场景包括数据基本不变、读密集型、计算代价大、千人一面等；不适合写多读少、对数据一致性要求严格的场景。缓存分类有进程级、集中式、分布式、多级缓存。常用模式有 Cache-Aside 和 Cache-As-SoR。回收策略基于时间、空间、容量、引用等。还需应对缓存穿透、雪崩、热点等问题，并有动静分离、慎用大对象等实践经验。
分片：将较大部分分成多个较小部分，包括数据分片和任务分片。数据分片策略有区间、随机、组合分片，还有二级索引（本地索引和全局索引）、路由策略（客户端、代理层、集群路由）、动态平衡（固定分区、动态分区），分库分表有垂直切分和水平切分。任务分片将任务分成子任务并行处理，如 Map/Reduce。
存储：不同业务场景下存储读写有不同方法论。读写分离适用于读多写少业务，主节点写、从节点读，需处理数据复制延迟问题；动静分离分离经常更新和更新频率低的数据；冷热分离将热数据放高性能设备，冷数据下沉；重写轻读将计算逻辑从读转移到写；数据异构按不同维度建立索引关系加速查询。
队列：在系统应用中有广泛场景。可用于异步处理、流量削峰、系统解耦、数据同步、柔性事务等。分类有缓冲队列（应对突发流量）、请求队列（排队用户请求，用于流量控制等）、任务队列（异步执行任务）、消息队列（消息投递，有点对点和发布订阅模式，不同消息队列特性不同）。

7. 微信红包（秒杀系统）⭐⭐⭐

微信红包（尤其是发在微信群里的红包，即群红包）业务形态上很类似网上的普通商品“秒杀”活动。

用户在微信群里发一个红包，等同于是普通商品“秒杀”活动的商品上架；微信群里的所有用户抢红包的动作，等同于“秒杀”活动中的查询库存；用户抢到红包后拆红包的动作，则对应“秒杀”活动中用户的“秒杀”动作。

不过除了上面的相同点之外，微信红包在业务形态上与普通商品“秒杀”活动相比，还具备自身的特点：

首先，微信红包业务比普通商品“秒杀”有更海量的并发要求。

微信红包用户在微信群里发一个红包，等同于在网上发布一次商品“秒杀”活动。假设同一时间有 10 万个群里的用户同时在发红包，那就相当于同一时间有 10 万个“秒杀”活动发布出去。10 万个微信群里的用户同时抢红包，将产生海量的并发请求。

其次，微信红包业务要求更严格的安全级别。

微信红包业务本质上是资金交易。微信红包是微信支付的一个商户，提供资金流转服务。

用户发红包时，相当于在微信红包这个商户上使用微信支付购买一笔“钱”，并且收货地址是微信群。当用户支付成功后，红包“发货”到微信群里，群里的用户拆开红包后，微信红包提供了将“钱”转入折红包用户微信零钱的服务。

资金交易业务比普通商品“秒杀”活动有更高的安全级别要求。普通的商品“秒杀”商品由商户提供，库存是商户预设的，“秒杀”时可以允许存在“超卖”（即实际被抢的商品数量比计划的库存多）、“少卖”（即实际被抢的商户数量比计划的库存少）的情况。但是对于微信红包，用户发 100 元的红包绝对不可以被拆出 101 元；用户发 100 元只被领取 99 元时，剩下的 1 元在 24 小时过期后要精确地退还给发红包用户，不能多也不能少。

7.1 系统设计

明诉项目需求，多个用户群发布红包时能保证多个用户群里的用户能分到随机的预定的金钱（固定红包或者随机红包），红包的金额总和前后不能发生变化
- 同时考虑如何提升系统的并发量
- 此外对实时性是否有要求，要结果一致性还是全局一致性
确定业务逻辑，一个秒杀活动对应数据库中的一条库记录。当用户进行商品“秒杀”时，系统的主要逻辑在于数据库中库存的操作上。一般来说，对数据库的操作流程有以下三步：a. 锁库存 b. 插入“秒杀”记录 c. 更新库存。（下文继续讲）
架构设计：存储+多个服务（下文继续讲）

7.1 业务逻辑

一个“秒杀”活动，对应数据库中的一条库存记录。当用户进行商品“秒杀”时，系统的主要逻辑在于数据库中库存的操作上。一般来说，对数据库的操作流程有以下三步：

a. 锁库存

b. 插入“秒杀”记录

c. 更新库存

“秒杀”系统的设计难点就在这个事务操作上。商品库存在数据库中记为一行，大量用户同时“秒杀”同一商品时，第一个到达数据库的请求锁住了这行库存记录。在第一个事务完成提交之前这个锁一直被第一个请求占用，后面的所有请求需要排队等待。同时参与“秒杀”的用户越多，并发进数据库的请求越多，请求排队越严重。因此，并发请求抢锁，是典型的商品“秒杀”系统的设计难点。

微信红包业务相比普通商品“秒杀”活动，具有海量并发、高安全级别要求的特点。在微信红包系统的设计上，除了并发请求抢锁之外，还有以下两个突出难点：

首先，事务级操作量极大。上文介绍微信红包业务特点时提到，普遍情况下同时会有数以万计的微信群在发红包。这个业务特点映射到微信红包系统设计上，就是有数以万计的“并发请求抢锁”同时在进行。这使得 DB 的压力比普通单个商品“库存”被锁要大很多倍。

其次，事务性要求严格。微信红包系统本质上是一个资金交易系统，相比普通商品“秒杀”系统有更高的事务级别要求。

方案一，使用内存操作替代实时的 DB 事务操作。

先在内存里 “假装扣库存”：用内存缓存（比如 Redis）代替数据库，先在内存中记录 “库存扣减” 的操作（比如把库存从 1000 减到 999）。
马上告诉用户 “成功了”：内存操作速度极快（比数据库快 100 倍以上），可以立即给用户返回 “秒杀成功” 的结果。
稍后再把操作 “同步到数据库”：通过异步任务（比如后台线程或消息队列），慢慢把内存中的库存变化写入数据库，实现持久化存储。

这个方案的优点是用内存操作替代磁盘操作，提高了并发性能。

但是缺点也很明显，在内存操作成功但数据库持久化失败，或者内存 Cache 故障的情况下，数据库持久化会丢数据，不适合微信红包这种资金交易系统。

内存操作成功，数据库写入失败：
- 比如，内存里库存扣减了，但在异步写入数据库时，突然遇到数据库故障、网络中断，导致最终数据没保存到数据库。此时，内存中的数据是 “假的”，数据库里的库存还是原来的数值，造成 数据不一致。
内存缓存本身故障：
- 内存是 “易失性存储”，一旦服务器断电、重启，内存中的数据会直接丢失。如果还没来得及同步到数据库，就会导致库存记录完全消失（比如内存里扣了 100 库存，但数据库没记录，最终库存少了 100）。

举例：微信红包是资金交易，每一分钱都必须准确记录。如果用这个方案，可能出现 “用户看到红包扣了，但实际没到账” 或者 “红包金额丢失” 的情况，这是绝对不能接受的。

方案二，使用乐观锁替代悲观锁。

所谓悲观锁，是关系数据库管理系统里的一种并发控制的方法。它可以阻止一个事务以影响其他用户的方式来修改数据。如果一个事务执行的操作对某行数据应用了锁，那只有当这个事务把锁释放，其他事务才能够执行与该锁冲突的操作。对应于上文分析中的“并发请求抢锁”行为。

所谓乐观锁，它假设多用户并发的事务在处理时不会彼此互相影响，各事务能够在不产生锁的情况下处理各自影响的那部分数据。在提交数据更新之前，每个事务会先检查在该事务读取数据后，有没有其他事务又修改了该数据。如果其他事务有更新的话，正在提交的事务会进行回滚。

商品“秒杀”系统中，乐观锁的具体应用方法，是在 DB 的“库存”记录中维护一个版本号。在更新“库存”的操作进行前，先去 DB 获取当前版本号。在更新库存的事务提交时，检查该版本号是否已被其他事务修改。如果版本没被修改，则提交事务，且版本号加 1；如果版本号已经被其他事务修改，则回滚事务，并给上层报错。

这个方案解决了“并发请求抢锁”的问题，可以提高 DB 的并发处理能力。

但是如果应用于微信红包系统，则会存在下面三个问题：

如果拆红包采用乐观锁，那么在并发抢到相同版本号的拆红包请求中，只有一个能拆红包成功，其他的请求将事务回滚并返回失败，给用户报错，用户体验完全不可接受。
如果采用乐观锁，将会导致第一时间同时拆红包的用户有一部分直接返回失败，反而那些“手慢”的用户，有可能因为并发减小后拆红包成功，这会带来用户体验上的负面影响。
如果采用乐观锁的方式，会带来大数量的无效更新请求、事务回滚，给 DB 造成不必要的额外压力。

基于以上原因，微信红包系统不能采用乐观锁的方式解决并发抢锁问题。

7.2 解决高并发问题

1.系统垂直 SET 化，分而治之（采用负载均衡的源ip哈希方法）

每个红包生成唯一 ID（如1001_20240510_abc），系统按 ID 尾号取模（如ID % 100），将所有与该红包相关的操作（发红包、抢红包、查询等）固定路由到某个 SET（这个操作和均衡负载的源 IP 哈希作用相同）。

每个 SET 包含独立的逻辑服务器（Server）和数据库（DB），不同 SET 之间完全隔离：

发红包时，SET1 的 Server 处理ID=1001的红包，SET2 的 Server 处理ID=1002的红包，互不干扰。
即使 SET1 的 DB 出现故障，也不会影响 SET2 的红包操作，实现故障隔离。

假设总共有 100 个 SET，每个 SET 只处理 1% 的红包请求，原本 10 万并发的洪流被拆成 100 股 1000 并发的小流，每个 SET 的 DB 压力大幅降低。

这个方案解决了同时存在海量事务级操作的问题，将海量化为小量。

2. 逻辑 Server 层将请求排队，解决 DB 并发问题。

解决数据库 “并发抢锁” 问题，确保同一红包的操作按顺序执行，避免多个请求同时修改同一笔红包数据。

实现逻辑（分三步）：

同一红包 “绑定” 到同一台 Server
- 在 SET 内部，进一步按红包 ID 哈希（如hash(ID) % 5）将请求分配到 SET 内的某一台 Server（假设 SET 有 5 台 Server）。
- 效果：同一个红包的所有请求（比如 100 人抢同一个红包）都会被 “钉” 到同一台 Server 上，不会分散到 SET 内的其他 Server。
单机请求排队：FIFO 队列保证串行处理
- 每台 Server 内部有一个 “请求队列”，按接收顺序（FIFO）排队处理同一红包的请求。
- 例如：用户 A、B、C 同时抢红包，请求按到达顺序进入队列，Server 按 A→B→C 的顺序处理，确保每次只有一个请求操作 DB。
- 关键：即使 Server 有多个 CPU 核心，也强制同一红包的请求串行执行（通过线程同步机制），避免并发修改 DB 中的红包数据。
Memcached 限流：防止队列 “堵车”
- 在 Server 同机部署 Memcached（内存缓存），利用其CAS原子操作（类似 “计数器”）控制同时进入 DB 的请求数。
- 例如：设定同一红包最多允许 2 个请求同时操作 DB，超过阈值的请求直接返回 “系统繁忙”，避免 DB 瞬间被大量请求压垮。
- 作用：当 DB 负载过高时，Memcached 作为 “阀门” 自动限流，防止队列堆积导致服务降级，保障核心流程（如拆红包）的稳定性。

8. 设计一个rpc框架⭐

rpc原理很简单，相当于远程调用一个函数，整个过程对服务调用方来说就是透明的，这个过程可以像调用本地服务一样简单高效，不需要关心服务是如何调用的等一系列问题。

8.1 如何设计⭐⭐

首先服务调用，那肯定是需要和服务提供方进行通信的，如何通信也有着不同的选择方式，像HTTP协议抑或是TCP协议，这就是通信方式的选择。

其次就是调用信息的编码协议，我们可以直接用JSON来承载我们的调用信息，当然JSON所占用的字节数比较多，效率也就比较低下，这时候我们就可以选择效率更高的序列化编码协议，像谷歌的Protobuf这种二进制编码协议，效率更高

那么到了这里其实我们已经可以完成客户端对服务端的RPC调用了，但往更深了想，我们客户端调用服务，那么就必须在本地维护我们的服务提供方的信息，从而完成我们服务的调用，那么维护的这个信息是和客户端耦合的，其次信息的更新也是不方便的，所以基于此，我们往往就是将服务提供方的信息放在另外一个**注册中心，在注册中心维护着服务提供方的各种详细信息，包括像服务提供地址，暴露的服务和方法等，客户端和服务端只需要知道注册中心即可，这就是我们的服务发现**

其次，当我们的流量很大的时候，一个服务提供方肯定是不够能力处理流量很大的时候的请求的，我们的服务提供方就需要扩容，我们RPC调用的过程对客户端来说就是透明的，那么这就涉及到我们的负载均衡了，通过一定的负载均衡算法将客户端的请求打在不同的机器上面，服务提供方只需要给客户端返回处理消息即可

那么到这个时候，我们整个RPC调用的逻辑就清晰了，客户端通过注册中心拿到服务提供方的信息来进行远程调用，但是最后处理请求的时候也有可能会出问题，这就涉及到我们的服务治理了，RPC调用应该是高可用的，有时候由于不可抗力因素，导致客户端调用的那个服务提供方出现宕机，那么这个调用就说明失败了，我们需要及时返回调用失败信息，这就涉及我们的超时控制，其次就是要将这个服务提供方从注册中心中剔除掉，防止我们下次调用还打在这个服务提供方上

那么到这里就很清晰明了了，简单的RPC框架设计无非就是以下几部分的考量

传输协议（TCP/HTTP）->编码协议（json/protobuf）->服务注册与发现（zookeepr）->服务治理（负载均衡）

8.2 服务发现设计

客户端部分我们集成了服务发现接口，可以根据不同的需要整合不同的服务发现策略
- 服务发现模块是嵌在客户端里面的，包含了服务注册中心的地址，并维护一个超时时间，默认每次从本地拿服务列表，如超时则直接从注册中心获取
- 客户端维护一个已建立连接的client列表，复用连接以减少资源消耗
- 维护一个负载均衡策略标识位，实际负载均衡算法由服务发现模块实现
- 获取的服务提供方列表缓存到本地用于后续调用
服务端部分我们通过注册中心维护一个服务提供方列表，将其地址与上次更新时间记录下来，每次处理客户端或者服务端请求的时候更新列表
- 注册中心和客户端，服务端之间的通信是通过http协议交流的，主要是将服务器列表放入请求头里
- 心跳连接的设计主要就是每个服务端起一个协程，起一个打点器定时发送http请求给注册中心，从而更新服务端列表中的时间，心跳连接循环时间要小于超时时间避免误判服务器失活
- 维护一个互斥锁防止并发更新服务器注册列表出现问题

我们可以使用zookeeper充当一个配置中心的作用

zookeeper上面我们标识了每个类的方法所对应的分布式节点地址，当我们其他服务器想要RPC的时候，就去 zookeeper 上面查询对应要调用的服务在哪个节点上。

这里就相当于，我其他服务器来 zookeeper 查询User::is_exist ，然后会得到127.0.0.1：8001 这个值，这个值就是你布置这个功能的一个RPC节点的网络标识符，然后向这个节点去发送参数并且等待这个节点的相应。

8.3 其他设计

1）心跳连接：

心跳连接状态的维护，主要是在注册中心维护一个服务提供方列表，里面记录了服务提供方的地址和上次连接至注册中心的时间，同时在注册中心维护一个超时时间，每次进行心跳连接或者是获取服务实例列表的时候都会对其进行更新，将已超时服务实例剔除列表，整个过程通过维护一个打点器，定时向注册中心发送一个http的post请求，注册中心维护对http请求的响应，包括：返回活跃实例，更新服务实例列表（更新时间或添加实例）

2）超时控制：

在整个远程调用的过程中，客户端和服务端都会出现调用超时，也分为不同的情况 客户端主要体现在

建立连接的超时，长时间无法建立 TCP 连接
读写报文造成的超时，连接已建立，但发送请求或读取响应时数据传输卡住（如网络波动导致报文丢失）。
等待服务端响应造成的超时（如服务端挂了），服务端已接收请求并处理，但因业务逻辑复杂或故障，迟迟不返回结果

服务端主要体现在

读写报文超时
处理服务调用造成的超时（服务调用超时）

此项目在主要在三个地方添加了超时处理机制，考虑到编码一般不会出现问题

客户端建立连接时，若不控制连接时间，客户端可能无限阻塞，导致线程 / 连接池被占满
- 客户端发起连接请求，同时启动一个定时器（如设置超时时间为 2 秒），通过 select 同时监听 “连接成功事件” 和 “定时器超时事件”，若 2 秒内连接成功，返回连接实例；若超时，直接返回 “连接超时” 错误，避免继续等待。
客户端调用服务超时，服务端处理缓慢或故障时，客户端若一直等待会导致请求堆积，甚至引发级联超时。
- 客户端发起调用时，生成一个子 context，设置超时时间（如 3 秒），将 context 传递给远程调用函数，函数内部通过监听 context.Done() 通道检测超时，若 3 秒内服务端未返回响应，context 自动取消，调用流程终止，返回超时错误。（context 能跨函数传递，统一控制整个调用链的超时，避免单个慢调用拖垮整个客户端）
服务端处理服务超时，服务端处理业务逻辑时可能因耗时操作（如数据库查询、第三方接口调用）阻塞，占用线程资源。
- 和客户端连接超时控制类似，服务端接收到请求后，启动一个定时器（如设置处理超时时间为 2 秒），通过 select 同时监听 “业务处理完成通道” 和 “超时信号通道”，若 2 秒内处理完成，正常返回响应；若超时，直接终止处理逻辑，返回 “处理超时” 错误，并释放线程资源。

3）路由和负载均衡（考虑到负载均衡就要考虑是否要分片）

4）集群容错（处理集群裂脑和惊群现象），考虑到分布式部署就必须得考虑集群容错

3）零拷贝

4）池化，rpc连接池，复用连接

6）队列

7）无锁

8）异步（服务端业务处理逻辑加入异步处理机制。在RPC 框架提供一种回调方式，让业务逻辑可以异步处理，处理完之后调用 RPC 框架的回调接口）

9. 分布式缓存

设计一个分布式缓存系统，需要考虑资源控制、淘汰策略、并发、分布式节点通信等各个方面的问题。

1）缓存功能以及缓存淘汰策略

常见的缓存淘汰策略有三种：

先进先出
LFU
LRU

我们选择LRU算法来淘汰数据，具体实现简述：

1、创建一个结构体 Cache

包含缓存最大长度、缓存当前长度、双向链表、map、以及回调函数

2、实现结构体方法：LRU的实现方法

到此我们已经实现了一个带有LRU淘汰算法的缓存系统了。

但是目前的缓存并不支持并发访问，所以我们需要封装这个分布式缓存，使其具有高并发性能。

2）高并发

首先，通过负载均衡方法将申请进行分流，每个节点管理的申请各自独立；

其次，每个节点再单独设立一个处理队列，该队列通过自旋锁封装（因为是短时间任务），每个队列中的申请按顺序依次将数据存储到该节点对应的缓存中；

最后，创建一个连接池，避免因为频繁进行连接申请/消耗而造成资源开销。

3）分布式通信

分布式通信将上面的设计整体串起来：

传输协议（TCP/HTTP）->编码协议（json/protobuf）->服务注册与发现（zookeepr）->服务治理（负载均衡）

4）其他

超时控制、心跳机制、连接池、分片、集群容错、零拷贝、池化、异步、队列、无锁

10. 40亿QQ号, 1G内存，怎么去重？

10.1 数据规模分析

数据量：题目中的40亿个QQ号意味着你需要处理的数据集非常庞大。如果每个QQ号以整数形式存储（比如32位整数），每个QQ号占用4字节空间。
总内存需求：如果直接将这40亿个QQ号存入内存中，所需空间为：

$$
40亿*4字节=160亿字节=16GB
$$

这个规模远超1GB内存的限制，因此直接在内存中存储所有QQ号是不可能的。

10.2 解法

10.2.1 使用位图进行数据去重

什么是位图

BitMap，顾名思义，就是用“位”来存储数据的技术。我们平时可能听过“字节”、“兆字节”这些词，但BitMap更小巧精悍，直接用最小的数据单位——“位”——来操作。在计算机里，1个字节（Byte）等于8位（bit），也就是说，一个字节能记录8个信息点。这个小小的技巧让BitMap在处理海量数据的时候非常高效。

BitMap在计算机里是用“位”来表示某个数据是否存在。打个比方，如果你有40亿个QQ号，你不需要为每个QQ号都分配一个独立的空间（比如字符串），而是通过一个位图，按顺序标记“这个号有没有出现过”。它的核心优势就是省内存，因为一个bit只占用一个二进制位，这对海量数据来说节省了很多空间。

如何使用位图去重

假设你现在有40亿个QQ号需要去重。如果每个QQ号都是一个32位的整数，那如果直接存储这些QQ号，将占用16GB内存（40亿个QQ号 × 每个号4字节）。但我们假设QQ号的最大范围也就是从1到40亿，意味着我们最多需要存储40亿个数的“有”或“没有”状态，用BitMap刚好可以应对。

步骤如下：

初始化位图
- 我们需要一个大小足够的位图来记录这40亿个QQ号。既然1个bit能表示一个QQ号有没有出现，那40亿个QQ号就需要40亿个bit。这样一个位图大概需要500MB的内存（40亿bit / 8 = 500MB），这和我们要处理的1GB内存限制相符。
读取QQ号并标记位图
- 可以想象一下这个位图是一张巨大的“表”，上面有40亿个小格子，每个小格子代表一个QQ号的位置，初始时每个格子都是“0”，表示这个号码还没出现。当我们逐个读取QQ号时，假设读到第一个QQ号是12345678，那我们就把位图中的第12345678个位置标记为“1”，表示这个QQ号出现了。重复的号码再次被读取时，它对应的位已经是“1”了，所以我们就知道这个QQ号已经存在，不会重复处理。
扫码位图得到去重结果
- 当所有QQ号都处理完之后，去重的过程就完成了。接下来，我们只需要遍历这个位图，找到所有标记为“1”的位，就可以得到所有去重后的QQ号。

位图的优劣

优势
- 节省内存，只需用一个bit代表一个QQ号，这样原本需要16GB的内存，而BitMap只用了500MB左右，就完成了同样的任务。
- 时间复杂度低，通过位运算（移位、掩码，比如直接和掩码进行或操作定位目标）可直接定位目标位，标记存在性（置 1）或查询（读位）的时间复杂度均为 **O(1)**，不随数据量增长而变化。
劣势
- 位图存在最大值限制，BitMap的大小必须提前确定。如果我们处理的QQ号超过了原先设置的最大值（比如说你预期最多处理40亿个号码，但突然遇到了超过40亿的QQ号），那么位图就“装不下”了，需要重新扩展空间，而这个操作可能会非常繁琐和耗时。
- 存储稀疏数据时，内存利用率不高，甚至可能导致使用位图的内存比直接遍历QQ号用的内存还要多
- 适用条件有限，只能用来处理“整数”类的数据（因为需要通过与、或、与或操作定位目标位置），如果我们处理的不是QQ号，而是其他需要更复杂数据结构的内容，比如字符串（例如邮箱地址），BitMap就不适用了，若强行使用，需先将非整数数据哈希映射为整数，但哈希可能导致冲突（不同数据映射到同一索引），破坏准确性。

10.2.2 布隆过滤器

什么是布隆过滤器

布隆过滤器，听起来像是一种很高深的技术，其实它的原理非常简单，主要用来快速判断某个元素是不是已经存在过。

它特别适合处理海量数据，但不同于普通的集合或者列表，布隆过滤器的最大特点是节省空间，也就是说，在存储大量数据时，它几乎不怎么占用内存。

假设你是公司的HR，负责一个超大的应聘者名单。名单上有上百万个名字，你每天都要检查一个名字是否已经在这个名单里。正常情况下，你需要一个非常庞大的数据库或者Excel表格，才能够存储这些名字，并进行查找，但布隆过滤器的好处是，它通过“牺牲一点点准确性”来换取极大的存储空间和速度优势。

也就是说，它能够快速告诉你：“这个名字可能已经在名单里了”，但有一点点可能性它会误判。

实现原理

布隆过滤器的核心原理就是使用多个哈希函数。

每次我们插入一个元素（比如一个QQ号或一个名字），布隆过滤器会通过几个哈希函数，生成几个不同的位置，把这些位置的“位”（bit）设置为1。之后，当你需要检查某个元素是否已经存在时，它会用同样的哈希函数去检查对应位置的位是否都已经是1。如果都是1，那么它会告诉你：“这个元素可能存在过”。如果有任何一个位是0，它就可以非常肯定地告诉你：“这个元素绝对没出现过”。

之所以可能，是因为可能会发生哈希冲突，不同的原值被映射到了同一块地方。

工作过程

添加数据

当你往布隆过滤器里添加一个新元素时，比如一个QQ号，布隆过滤器会通过多个哈希函数生成几个位置。假设有三个哈希函数，分别生成了位置1001、4567和7890。
布隆过滤器就会在这三个位置上把对应的“位”设为1。
重复这个过程，对于每一个新的元素，它都会通过哈希函数找到多个位置，并把这些位置的位都设置为1。

查询数据

当你查询某个QQ号是否存在时，布隆过滤器会用相同的哈希函数生成位置，比如你查询的QQ号生成了位置1001、4567和7890。
然后，布隆过滤器检查这几个位置的位是否都是1。如果都是1，那么它会告诉你：“这个QQ号可能已经存在”。如果有任何一个位是0，它会告诉你：“这个QQ号肯定不存在”。

注意，这里有个“可能”的说法。因为布隆过滤器有一定的误判率——它可能会错误地告诉你某个元素存在，但它不会错判不存在的情况。换句话说，布隆过滤器可以提供“假阳性”，但绝对不会给出“假阴性”。

布隆过滤器的应用场景

数据库缓存：每次用户查询商品时，你得先去数据库查一遍。如果商品不存在，那你就白费力气了。这时候可以使用布隆过滤器先判断商品是否存在

垃圾邮箱过滤：布隆过滤器可以通过多个哈希函数快速检测出已知的垃圾邮件模式，而不必遍历列表，从而提高处理效率。

布隆过滤器和位图的区别

选择布隆过滤器：

数据量非常大（数百万甚至数亿条）；
允许少量误判（假阳性）；
内存有限且需要高效存储；
数据类型多样，可能是字符串、URL等非整数型数据；
数据规模不固定，或者数据分布比较稀疏。

选择位图（BitMap）：

数据为整数型，且取值范围明确；
数据量大且分布较为密集；
不能容忍任何误判（需要100%准确性）；
内存空间充足，可以根据数据范围分配足够的位图大小。

11. 概率问题

问题：一辆出租车在雨夜肇事，现场有一个目击证人说，看见该车是蓝色。已知：1、该目击证人识别蓝色和绿色出租车的准确率是80%；2、该地的出租车85%是绿色的，15%是蓝色的。请问：那辆肇事出租车是蓝色的概率有多大？

条件概率：
$$
P(B|A)=P(AB)/P(A)
$$

$$
P(AB)=P(B|A)*P(A)
$$

$$
P(A_1A_2…A_n)=P(A_1)P(A_2|A_1)P(A_3|A_1A_2)…P(A_n|A_1A_2…A_n-1)
$$

贝叶斯公式：
$$
P(A|B) = P(B) * P(B|A) / P(A)
$$

P(A)是 A 的先验概率，之所以称为“先验”是因为它不考虑任何 B 方面的因素。

P(A|B)是已知 B 发生后 A 的条件概率，也由于得自 B 的取值而被称作 A 的后验概率。

P(B|A)是已知 A 发生后 B 的条件概率，也由于得自 A 的取值而被称作 B 的后验概率。

P(B)是 B 的先验概率，也作标淮化常量（normalizing constant）。

全概率公式：
$$
P(B)=P(A_1)P(B|A_1)+P(A_2)P(B|A_2)+P(A_3)P(B|A_3)
$$

这里有两个概念：
1、已知蓝色的车，目击证人识别出蓝色的车的概率80%；

2、已知目击证人识别出蓝色的车，这辆车确实是蓝色的概率有多少。

这是两个不同的概率问题。

1、比较单纯，因为给定了车，车的颜色就是固定的，100%是蓝色的，只有目击证人的识别是存在不确定性的。

2、比较复杂，因为目击证人识别出蓝色的车，这个前提存在结构，因为人是会出错的，或者说不确定性前置了，不确定性隐含在了已知条件里面。也就是说，存在下面两种情况，都可能出现“目击证人识别出蓝色的车”

1）蓝色的车被识别为蓝色的车-识别正确

2）绿色的车被识别为蓝色的车-识别错误

在这个问题里面，因为绿色的车占比太大了，所以，虽然目击证人识别错误（将绿车识别为蓝车）的可能性并不高，但是，其错误对识别结果的影响是不可忽略的。

1. 定义事件与概率

事件 A：肇事车辆是蓝色（先验概率）P(A)=15%=0.15，P(¬A)=85%=0.85（肇事车辆是绿色）
事件 B：目击者认定肇事车辆是蓝色
- 目击者正确识别蓝色的概率：P(B∣A)=80%=0.8
- 目击者错误识别绿色为蓝色的概率：P(B∣¬A)=20%=0.2

2. 应用贝叶斯定理

目标是计算在目击者指认蓝色的条件下，实际为蓝色的概率，即 P(A∣B)。
根据贝叶斯公式：P(A∣B)=P(B)P(B∣A)⋅P(A)
其中，P(B) 是目击者指认蓝色的全概率，包括两种情况：

实际是蓝色且正确识别：P(B∣A)⋅P(A)
实际是绿色但错误识别为蓝色：P(B∣¬A)⋅P(¬A)

因此：P(B)=P(B∣A)⋅P(A)+P(B∣¬A)⋅P(¬A)

3. 代入数值计算

计算分母 P(B)：P(B)=0.8×0.15+0.2×0.85=0.12+0.17=0.29
计算分子 P(B∣A)⋅P(A)：0.8×0.15=0.12
代入贝叶斯公式：12/29=0.41

首先我用常识而不是数学公式来解释楼主的问题：我对蓝色判断的正确率已经是80%了为什么还要做上述计算呢？这本质上是似然函数和先验分布的关系。我举例说明：假如某人是大幂幂极端狂热的粉丝，尤其对她的腿有超强的识别度。在网上找图片通过腿来识别该女星是否为大幂幂的正确率为高达80%。有一天他在自家村口通过背影看到一位长腿美女，并根据自己多年看腿的经验得出此人就是大幂幂的结论。那么请问，这个美女是杨幂的概率是多少呢，80%吗？当然是不对的。为什么呢？因为杨幂此时此刻根本不会出现在他们村子里啊！所以该美女就是大幂幂的概率其实是0*80%=0。但我换个条件，假如我告诉你已知大幂幂此时出现在这个村子里的概率是50%，那他猜对的概率是多少呢？那就应该是50%*80%=40%。通过该例子我想说明，单纯地对事物可能性的判断并不直接等于实际的情况，因为还要考虑你是否是处在一个满足条件的样本池（大幂幂此时在不在村里）里进行猜测的。

接下来说说理论的东西。在上述例子中，那个看腿的正确率80%被称作似然函数（之所以叫函数是因为往往含有参数），而大幂幂出现在村里的概率则是先验概率，即无任何其他信息时看到她的概率。两个相乘，则是“在这个先验概率的条件下，通过80%正确率的观察的方法”得出的正确的可能性。也就是说似然函数其实是一个条件概率，必需要满足一定条件才可以用。而这个条件就是先验概率。即P(腿且在村里) = P(腿/在村里)*P(在村里)

再回到原题。题主给出的计算方法就是贝叶斯公式，这里不再赘述。但想强调一下，原本15%的蓝色概率怎么就跑到41.38%了呢？因为贝叶斯已经研究决定了。先验分布在经过一次观察到蓝车的样本调整后，产生了比较大的改变，尽管还是不如绿车概率大，但已经比原先大很多了。而在计算中分子上的0.8要乘以0.15也和前述原因相同，因为样本池里只有15%的蓝车，而80%的正确率也只是针对全部是蓝车来说的一个条件概率罢了。而贝叶斯公式正是考虑了两者并将他们乘起来了。希望说清楚了。

2025-04-30 12:24:32 # 面试 #场景题