场景与算法设计面试

钝悟2026/9/17大约 71 分钟

场景与算法设计面试

功能场景

【中等】如何设计一个排行榜功能？⭐⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：15 min ｜ 🏷 标签：功能设计 / 缓存

💎 关键结论

首选 Redis zset（有序集合）：以用户为 member、排行指标为 score，天然有序。ZINCRBY 原子加分，ZREVRANGE 取 Top N，ZREVRANK 查个人名次，O(logN) 复杂度，实时且简单。

⚡记忆卡片

口诀：zset 装榜单，score 是分数，ZREVRANGE 取 Top N。
关键词：zset ／ ZINCRBY ／ ZREVRANK
链路：事件触发加分 → 自动排序 → 范围查询取名次

📖 核心知识

数据模型

ZADD rank:activity:{id} score memberId：member = 用户 ID，score = 排行指标（销售额、积分、点赞数）。
实时更新：业务事件发生时 ZINCRBY rank:activity:{id} increment memberId 原子累加。

核心查询

查询需求	命令	复杂度
Top N	`ZREVRANGE key 0 N-1 WITHSCORES`	O(logN + M)
个人名次	`ZREVRANK key memberId`	O(logN)
个人分数	`ZSCORE key memberId`	O(1)
周边排名	`ZREVRANGE key rank-5 rank+5`	O(logN + M)

设计要点

同分处理：zset 同分时按 member 字典序排列；如需时间优先，可把时间因子编入 score（如 score = 分值 × 10^10 - 时间戳）。
冷热分离：zset 只存 ID 与分数，用户详情在查出排名后按 ID 回查 DB/缓存，避免大 value。
持久化兜底：开启 Redis AOF，或定时把榜单快照落库，防止故障后榜单丢失。
容量参考：百万级成员的单个 zset，Top N 查询仍为毫秒级。

🔬 扩展知识

详情

【L3】多维度排行榜（分地区、分类目、分活动）：按维度拆分独立 zset rank:{维度}:{维度值}，查询时聚合，避免单一大 key。
【L3】海量榜单（亿级成员）：按分数区间分桶建两级索引，或改为离线定时批量计算快照 + 实时增量修正。
【L4】吞吐权衡：超高并发可改为 MQ 异步加分 + 定时刷入，用秒级实时性换吞吐。

📚 延伸阅读：Redis Sorted Set 官方文档

🔀 发散问题

Q：score 编大数会有精度问题吗？ → score 是 double 类型，超过 2^53 的整数会丢精度，复合分数要控制量级或降精度处理。
Q：如何防刷榜？ → 加分入口做限流与风控校验，并记录增量流水供对账；流量统计可参考本文档「如何实现接口每分钟调用统计功能？」。
Q：Redis 宕机榜单丢了怎么办？ → 用 DB 快照恢复 + 回放增量消息重建，切换思路见本文档「如何实现数据的不停服迁移？」。

【中等】如何设计一个点赞功能？⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：10 min ｜ 🏷 标签：功能设计 / 缓存

💎 关键结论

点赞本质是一个按时间排序的去重集合：用 Redis 抗流量（String 计数 + Set 记录点赞者），MQ 异步批量落库，可支撑十万级 QPS 的高并发，响应在 10ms 以内。

⚡记忆卡片

口诀：Redis 记点赞，MQ 削峰，批量入库。
关键词：INCR 计数／ Set 去重／ Write Behind
链路：点赞写 Redis → MQ 异步通知 → 批量聚合入库

📖 核心知识

点赞功能的核心操作是：

点赞
取消点赞
查看点赞列表

本质是一个按时间排序的去重集合。

实现思路

缓存抗流量：点赞信息先存储在 Redis。点赞数存储在 String 类型，采用 INCR 原子增减；点赞者维护在 Set 类型。响应时间在 10ms 以内。
异步削峰：点赞事件通过 MQ 异步通知，吞吐量可轻松抗住每秒 10 万级消息。
批量入库：消费者批量聚合一段时间窗口的点赞信息，如每 5 秒或每 1000 条点赞消息，触发批量入库。——Write Behind 缓存同步更新策略。

数据模型参考

数据	存储	操作
点赞数	Redis String `like:count:{目标ID}`	`INCR`／`DECR` 原子增减
点赞者	Redis Set `like:users:{目标ID}`	`SADD`／`SREM`／`SISMEMBER` 判断是否点过赞
点赞明细	MySQL（用户、目标、时间）唯一索引	异步批量落库

🔬 扩展知识

详情

【L3】点赞列表分页：Set 不支持按时间排序分页，列表展示需落 DB 或改用 zset（score = 时间戳）。
【L3】Redis 与 DB 一致性：Write Behind 窗口内宕机可能丢数据，以 MQ 持久化消息为落库凭据，消费失败重试保证最终一致。
【L4】亿级目标热点：计数 key 分桶聚合，热点 Set 按目标 ID 哈希拆分。

📚 延伸阅读：Redis INCR 命令

🔀 发散问题

Q：用户快速连点又取消怎么办？ → 以 Redis Set 的 SISMEMBER 判断当前态做切换，MQ 消息携带目标状态按序聚合，最终以 DB 为准。
Q：点赞数如何对账？ → 定时比对 Redis 计数与 DB 计数，不一致以 DB 为准修正 Redis；对账兜底思路可参考本文档「如何解决订单重复支付情况？」。

【中等】如何实现一个订单超时取消功能？⭐⭐⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：20 min ｜ 🏷 标签：功能设计 / 延迟任务

💎 关键结论

本质是延迟任务调度：下单发 30 分钟延迟消息为主，到期查状态，仍待支付则取消并释放资源；定时扫表兜底漏网单，两道防线都要求幂等。

⚡记忆卡片

口诀：延迟消息为主，扫表兜底，取消先查状态。
关键词：延迟消息／扫表兜底／幂等取消
链路：下单发延迟消息 → 到期查状态 → 取消 + 释放库存

📖 核心知识

本质是一个延迟任务调度问题：下单时记录“创建时间 + 超时时长”，到期后检查订单状态，若仍为待支付则取消并释放资源。

方案对比

方案	原理	精度	可靠性	适用场景
定时任务扫表	定时扫描“创建时间 + 30min < 当前时间”的订单	分钟级	高（DB 为准）	量小、精度要求低
JDK DelayQueue	内存延迟队列（最小堆）	高	差（宕机丢任务）	单机小工具，不适合生产
Redis ZSet	score = 到期时间戳，定时任务轮询取到期元素	秒级	中（需持久化保障）	中小量级自研延迟任务
延迟消息队列	RocketMQ 延迟级别 / RabbitMQ 死信+TTL	级别固定	高（消息持久化+重试）	主流生产方案
时间轮	环形数组 + 链表，O(1) 添加/取消	高	依赖宿主	组件内部实现（Netty/ Kafka）

推荐组合：延迟消息为主 + 定时扫表兜底

下单成功发一条 30 分钟延迟消息；到期消费时先查订单状态，已支付则忽略，未支付则取消。
定时任务（如每 5 分钟）扫描漏网的超时订单，防止消息丢失；两道防线都要求幂等。

时间轮原理（高频追问）

环形数组每个槽挂链表，指针每 tick（如 100ms）走一格执行当前槽任务；多层时间轮（秒/分/时）解决长延迟精度与内存的矛盾。
Netty HashedWheelTimer 是经典实现；Kafka 也用时间轮管理生产者/消费者超时。

取消动作的完整性：改状态（带状态机条件）→ 释放预占库存 → 退优惠券/积分 → 记录日志；取消操作需幂等（延迟消息与扫表可能重复触发）。

量化参考：日下单 100 万、超时率 30%，则每日 30 万条延迟消息，峰值每秒仅几十条，RocketMQ 轻松承载；扫表兜底按 create_time + status 联合索引扫描，单次百毫秒级。

🔬 扩展知识

详情

【L3】超时时长可配置（大促改为 15 分钟）：超时时长随下单时刻的活动规则快照进订单（而非读取时动态计算），延迟消息按下单时时长设置；配置变更只影响新订单，存量订单不受影响，避免规则漂移。
【L3】纯 Redis ZSet 自研延迟任务：score = 到期时间戳，轮询取到期元素，但 Redis 故障时任务丢失，只能做非关键场景。
【L4】JDK DelayQueue 是内存最小堆实现，宕机即丢任务，只适合单机小工具；生产必须选择有持久化的任务存储。

📚 延伸阅读：Netty HashedWheelTimer ／ RocketMQ 延迟消息

🏭 实战场景

详情

电商大促：峰值 5000 TPS 下单，订单超时取消时长 30 分钟，预计超时率 40%，要求取消精度分钟级、库存释放零遗漏。

分析要点：峰值 5000 TPS 下单对应 30 分钟后峰值约 2000/s 的取消任务，RocketMQ 延迟消息承载无压力；消费取消时批量处理（每次拉一批，按订单 ID 批量查状态 + 批量改状态），减少 DB 交互；扫表兜底每 5 分钟扫描 status=待支付 AND create_time < now-30min 的漏网单；取消与支付并发竞态用带状态条件的 UPDATE 解决，已支付单触发自动退款；全链路幂等键（订单 ID），消息重试与扫表重复触发均安全。

⚠️ 常见误区

详情

常见误区：

❌ “JDK DelayQueue 可以直接用于生产” → 内存队列宕机即丢任务，生产必须用延迟消息队列等持久化方案。
❌ “延迟消息和扫表有一个就够了” → 延迟消息精度高但依赖 MQ 可靠性，扫表简单但精度差且大表扫描有 DB 压力，双防线组合才是成本与可靠性的最佳平衡。
❌ “取消和支付的竞态靠时序保证” → 靠“操作前查状态 + 带条件更新”兜底：取消消费时以 DB 为准，已支付则忽略；支付回调发现已取消则触发自动退款。
❌ “延迟级别配了就等于实际触发时间” → 曾有线上事故：RocketMQ 延迟级别配错（30min 配成 1h），叠加扫表兜底间隔 10 分钟，导致超时订单最晚 70 分钟才取消，库存被无效占用引发超卖投诉——延迟任务上线必须验证实际触发时间。

🔀 发散问题

Q：用户在第 29 分 59 秒支付成功，第 30 分钟取消任务触发怎么办？ → 取消消费时先查订单状态（以 DB 为准），已支付则忽略；支付回调发现已取消则自动退款，并发处理见本文档「如何设计一个取消订单功能？」。
Q：延迟消息丢失或 MQ 故障期间下的单怎么办？ → 扫表兜底按 create_time 扫描全部超时未支付单；两道防线都幂等，重复触发无副作用。
Q：取消为什么要联动库存？ → 取消必须同步释放预占库存，库存与订单的原子性见本文档「如何避免用户重复下单（多次下单为支持，占用库存）？」。

【中等】如何解决订单重复支付情况？⭐⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：15 min ｜ 🏷 标签：功能设计 / 支付

💎 关键结论

支付渠道（微信、支付宝）是第三方系统、数据不互通，无法阻止用户付款，只能做回调幂等处理：每次回调先查状态，判定重复支付则记录流水并原路退款，唯一索引防重，每日对账兜底。

⚡记忆卡片

口诀：重复支付即退款，幂等记录防重，对账兜底保安全。
关键词：回调幂等／原路退款／对账兜底
链路：回调查状态 → 判重记流水 → 自动退款 → 对账兜底

📖 核心知识

背景：比如用户用微信、支付宝支付，由于支付渠道是第三方系统，数据不互通，因此无法阻止用户付款。

解决核心思路：支付回调幂等性处理。

第一步、支付回调处理：

每次回调先检查订单当前状态。
若订单已支付（或已全额支付），则判定为重复支付。

第二步、重复支付处理：

记录重复支付流水。
立即发起退款（自动调用支付网关退款接口），将多付金额原路退回。
退款若失败，发起重试，重试超过一定次数，记录下来，通知运营转为人工处理。

第三步、幂等性：支付流水表建立唯一索引（如订单号+支付渠道+交易号），防止重复记录。

第四步、对账兜底：每日对账系统检查支付流水与订单状态，发现多付但未退款的，自动触发退款。

🔬 扩展知识

详情

【L3】对账实现：每日下载第三方账单，与本地流水逐笔比对（金额、状态、交易号），差异进入差错处理队列人工/自动跟进。
【L3】回调可靠性：第三方回调失败会按策略重试，我方回调接口必须幂等且快速返回，避免被对方判定超时而重复轰炸。
【L4】组合支付（余额 + 第三方）、部分退款场景需按支付流水拆分退款，对账粒度细化到流水级。

📚 延伸阅读：MySQL 唯一索引

🔀 发散问题

Q：退款接口一直失败怎么办？ → 重试 + 超限转人工，重试与降级策略参考本文档「调用第三方接口应注意哪些问题？」。
Q：如何防止伪造回调？ → 验签 + 比对金额，只处理签名合法且金额与订单一致的回调。
Q：和超时取消的竞态怎么处理？ → 订单已被超时取消但用户又付款，支付回调应触发自动退款，见本文档「如何实现一个订单超时取消功能？」。

【中等】如何实现一个分布式单例对象？⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：10 min ｜ 🏷 标签：功能设计 / 分布式锁

💎 关键结论

两层保证：进程内单例（每台机器只初始化一次）+ 进程间互斥（集群中只有一个实例真正工作，其余待命）。用分布式锁控制创建，并把对象状态存入外部存储供所有进程访问。

⚡记忆卡片

口诀：本地只初始化，全局抢锁，抢不到就待命。
关键词：分布式锁／外部存储／领导者选举
链路：本地单例 → 分布式锁控制创建 → 状态注册到外部存储

📖 核心知识

要让一个对象在分布式环境下全局唯一，需要满足两个条件：

进程内单例：在每台机器上，这个对象只初始化一次（本地单例）。
进程间互斥：在整个集群中，只允许一台机器的这个对象真正工作，其他机器的对象处于**“待命”或“禁用”**状态。

实现思路分为两步：

用分布式锁控制创建过程，保证同一时刻只有一个进程能创建。
把对象存到外部存储，让所有进程都能访问到。

落地要点

本地层：懒加载 + 双重检查（DCL）或静态内部类，保证每个进程只初始化一次。
集群层：用 Redis/ZooKeeper 分布式锁竞争“工作权”，未持锁者降级为待命，并周期性重新竞争。
共享状态：单例对象的可变状态（配置、计数、任务进度）放 Redis/DB，任何进程都能读取与接续。

🔬 扩展知识

详情

【L3】更标准的做法是领导者选举：ZooKeeper 临时节点 / etcd 租约竞选 leader，只有 leader 对外工作，会话失效自动重新选举，适合调度器、唯一消费者这类长期任职场景。
【L4】租约续期与脑裂：持锁者必须在租约到期前续期，续期失败要主动让位；写操作携带 fencing token，防止“僵尸节点”恢复后脏写。

📚 延伸阅读：ZooKeeper Recipes（Leader Election）

🔀 发散问题

Q：分布式锁和领导者选举有什么区别？ → 锁是短时操作互斥，用完即释放；选举是长期任职 + 租约续期，直到节点故障才重新选主。
Q：锁失效导致“双活”怎么办？ → 靠外部存储的唯一性约束或 fencing token 兜底，两层防护思路见本文档「如何避免用户重复下单（多次下单为支持，占用库存）？」。

【中等】如何实现接口每分钟调用统计功能？⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：15 min ｜ 🏷 标签：功能设计 / 统计

💎 关键结论

“记、存、看”三步：拦截器异步记录“接口 + 分钟桶”，用 Redis Hash 一分钟一个 Key 做 HINCRBY 原子计数，HGETALL 读取展示，写多读少性能极高。

⚡记忆卡片

口诀：Redis Hash 来计数，每分钟一个 Key，Field 是接口，Value 是次数。
关键词：HINCRBY ／分钟桶／ Grafana
链路：拦截记录 → MQ 异步 → Hash 计数 → 查询展示

📖 核心知识

整体思路分三步：记、存、看。

一、记（数据埋点）

拦截接口调用（拦截器、过滤器或 AOP），记录每次请求。

关键信息：
- 接口名：/api/user
- 时间桶：当前时间的分钟级窗口，例如 2026-02-26 14:00
操作：每一次请求，就给对应的“接口+分钟”计数器加 1。为了不影响正常请求业务，可以丢入一个 MQ 统一异步处理。

二、存（数据存储）

统计的核心是：写入极其频繁（每次请求都要写），读取相对低频（每分钟/每小时看一次）。

推荐方案：Redis Hash：

数据结构：用 Redis 的 Hash。
- Key：统计日期+分钟，如 stats:20260226:1400
- Field：接口名，如 /api/user
- Value：调用次数（整数）
操作：每次请求执行 HINCRBY stats:20260226:1400 /api/user 1
优点：
- 极高性能：内存操作，原子递增。
- 结构清晰：一个 Key 存一分钟的所有接口数据。
- 自动过期：可以给 Key 设置过期时间（比如保留 7 天），自动清理旧数据。

三、看（数据展示）

从存储中读取数据并展示出来。

查询实时分钟数据：直接 HGETALL stats:20260226:1400，拿到这一分钟所有接口的计数。
查询历史趋势：遍历多个分钟 Key，聚合出接口的调用趋势。
可视化：可以对接 Grafana，或自己写一个简单的接口返回 JSON 数据供前端图表展示。

🔬 扩展知识

详情

【L3】多粒度聚合：分钟级数据定时上卷为小时/天级，长期存储只保留低粒度，控制容量与 Key 数量。
【L3】大规模与告警：QPS 极高时先本地聚合再批量 HINCRBY；统计值写入后做阈值判断，流量突增/突降触发告警。
【L4】组件替换：需要长期保留与复杂查询时，可换时序数据库（Prometheus/InfluxDB）或 OLAP 引擎。

📚 延伸阅读：Redis Hash 官方文档

🔀 发散问题

Q：QPS 太高单个 Redis 顶不住怎么办？ → 客户端/接入层本地聚合后批量递增，或把统计 Key 分片到多个实例。
Q：想统计热点接口 Top N 怎么做？ → 每分钟桶再维护一个 zset（score = 次数）做排名，参考本文档「如何设计一个排行榜功能？」。
Q：给第三方接口做监控怎么扩展？ → 按依赖维度埋点并设 SLA 告警，参考本文档「调用第三方接口应注意哪些问题？」。

【中等】如何设计一个购物车功能？⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：15 min ｜ 🏷 标签：功能设计 / 电商

💎 关键结论

购物车设计 = Redis 存储 + 实时库存价格校验 + 合并结算 + 多端同步，核心是数据一致性和用户体验；购物车只存 skuId 与数量，价格库存查询时实时校验。

⚡记忆卡片

口诀：Hash 存购物车，价格库存实时校，登录合并，结算原子扣。
关键词：Hash 存储／实时校验／合并结算
链路：加购 → 校验与选中 → 合并结算 → 扣库存下单

📖 核心知识

数据存储

维度	关注点	解决方案
存储选型	高性能+持久化平衡	Redis（主）+ MySQL（备/历史）
数据结构	灵活查询	Hash 结构：`cart:user:{id}` → field=skuId, value=商品详情
过期策略	僵尸数据清理	7 天过期 + 定期清理未登录购物车

核心功能

功能	难点	解决
添加商品	重复 SKU 合并	存在则累加数量，不超过限购
数量更新	库存边界	实时校验库存上限、下限 1
实时价格	价格变动	查询时从商品服务拉取最新价
选中结算	批量操作	维护`selected`状态位，全选/反选

库存处理

预占库存：结算时 Redis 原子扣减（Lua 脚本）
释放库存：超时未支付/取消订单 → 回补
实时校验：添加/更新时查真实库存

多端同步

未登录 → LocalStorage
登录时 → 合并 LocalStorage 到 Redis
多端 → 同一 Redis，实时同步

异常场景

场景	问题	处理
库存不足	下单失败	标记失效，提示用户
价格变动	金额不符	重新计算，弹窗确认
商品下架	无法购买	自动移除，提示原因

🔬 扩展知识

详情

【L3】容量与淘汰：常见做法限制购物车条目上限（如约 100 件），超限按最久未使用淘汰；游客购物车与失效商品定期清理。
【L3】合并冲突策略：登录合并时同 SKU 数量累加并受库存与限购约束，价格与上下架状态以实时查询为准。
【L4】边界划分：购物车只负责“选购意向”，价格计算交给促销服务、库存扣减交给下单链路，避免购物车成为大杂烩服务。

📚 延伸阅读：Redis Hash 官方文档

🔀 发散问题

Q：价格要不要存进购物车？ → 不存，查询时实时拉取最新价，避免旧价格引发金额纠纷。
Q：结算后超时未支付怎么办？ → 释放预占库存并回补，参考本文档「如何实现一个订单超时取消功能？」。
Q：结算提交如何防重复下单？ → 幂等键 + 唯一索引兜底，见本文档「如何避免用户重复下单（多次下单为支持，占用库存）？」。

【中等】如何设计一个抢红包功能？⭐⭐⭐⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：15 min ｜ 🏷 标签：功能设计 / 电商

💎 关键结论

核心是“预生成金额 + 原子抢占”：用二倍均值法/线段分割法生成金额列表（以“分”为整数计算），存入 Redis 队列，LPOP 原子弹出保证不重不超，落库记账，过期剩余退回。

⚡记忆卡片

口诀：每次随机上限是剩余均值两倍，保证公平不超总；预切线段存队列，顺序取出无争议。
关键词：二倍均值法／线段分割法／ LPOP
链路：发红包预生成金额 → 原子弹出抢占 → 落库记账 → 过期退回

📖 核心知识

两种红包

类型	算法	要点
普通红包	总金额 / 个数	每人固定金额，简单。
随机红包	二倍均值法（实时）或线段分割法（预生成）	总额固定，每人 ≥ 0.01 元，随机公平。

随机红包核心算法

二倍均值法（实时计算）
- 公式：当前金额 = 随机 [0.01, 剩余金额/剩余人数 × 2 - 0.01]
- 特点：实时计算，期望公平，但最后一人金额波动大。
线段分割法（预生成）
- 原理：把总金额（分）看作线段，随机切 N-1 刀，按切点分段作为金额。
- 特点：提前生成金额列表存入队列，抢时顺序取，每人概率完全相同。

技术关键点

金额单位：用 “分”（整数），避免浮点误差。
并发控制：Redis LPOP 原子弹出预先生成的金额列表，或用 Lua 脚本保证一致性。
持久化：红包状态（已抢列表、剩余金额）需持久化到 DB/Redis，重启后恢复。
过期退回：未抢完的红包超时后，根据已抢记录计算剩余金额，原路退回。

🔬 扩展知识

详情

【L3】方差对比：二倍均值法最后一人拿剩余、方差大；线段分割法预生成全部金额，各份期望与方差更均匀，公平性敏感场景优先预生成。
【L3】高并发红包雨：用 Lua 脚本原子完成“判断剩余份数 + 弹出金额”，抢的结果异步落库，单 Redis 实例可支撑数万 QPS。
【L4】扩展玩法：群红包“手气王”统计可用 zset 实时聚合；企业红包需叠加审批与财务对账流程。

📚 延伸阅读：Redis LPOP 命令

🔀 发散问题

Q：最后一人金额波动大怎么办？ → 二倍均值法最后一人拿剩余，方差较大；改用线段分割法预生成可消除波动。
Q：0.1 元发 10 人可行吗？ → 不够每人 1 分，发红包时前置校验：总金额 ≥ 人数 × 最小单位（1 分）。
Q：系统重启怎么办？ → 持久化存储红包状态，重启后从存储恢复继续服务；预生成方案天然支持断点续抢。过期退回的延迟任务可参考本文档「如何实现一个订单超时取消功能？」。

【中等】如何设计一个取消订单功能？⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：10 min ｜ 🏷 标签：功能设计 / 电商

💎 关键结论

五步口诀“校验、改状态、释放库存、退券、退款”；取消与支付并发冲突用数据库行锁/乐观锁 + 状态机条件更新，两方只有一方能成功，对账补偿兜底防资损。

⚡记忆卡片

口诀：校验、改状态、释放库存、退券、退款。
关键词：状态机／条件更新／对账补偿
链路：校验状态 → 带条件改状态 → 释放库存退券 → （已支付）退款

📖 核心知识

基本流程

操作	说明
校验状态	只有待支付/已超时订单才可取消，已支付/已发货等不能取消
更新状态	将订单状态改为“已取消”
释放库存	恢复商品库存（若锁定过库存）
退还优惠券/积分	若有使用的优惠券需退回
触发退款	若已支付（仅当允许取消已支付订单时），走退款流程

并发冲突场景：取消与支付同时发生

用户点击“取消”的同时，支付回调也到达。
若不加控制，可能出现：
- 订单被取消后却支付成功（资金损失）
- 订单支付成功却被取消（体验问题）

核心目标：保证最终一致性，避免资损。

方案一、基于数据库行锁 + 状态机（推荐）

原理：在更新订单状态时，使用数据库行锁或乐观锁，保证状态变更的原子性。
实现：
- UPDATE orders SET status = 'CANCELED' WHERE id = ? AND status = 'PENDING'
- UPDATE orders SET status = 'PAID' WHERE id = ? AND status = 'PENDING'
- 两条更新语句同时执行时，只有一条能成功（因为 status = 'PENDING' 条件）。
优点：简单可靠，利用数据库 ACID。
缺点：依赖数据库，但订单系统通常足够。

方案二、分布式锁

原理：对订单 ID 加锁（如 Redis 锁），取消和支付先争抢锁，获得锁的一方执行，另一方等待或重试。
适用：跨多个服务或数据库，需要强一致性。

方案三、最终一致性 + 对账补偿

原理：允许短暂不一致，通过后续对账或消息补偿修复。
流程：
- 取消和支付都正常执行，但记录流水。
- 后台定时任务检查“已取消但已支付”的异常订单，自动退款。
优点：高并发下性能好。
缺点：需补偿逻辑，可能存在资损窗口。

最佳实践（推荐方案）

业务优化

在页面上可以限时订单取消计时为 10 分钟，但实际后端是延迟 11 分钟取消订单。这样就可以避免用户在取消订单限时最后一刻下定决心付款的情况。

数据库行锁/乐观锁 + 状态机 + 幂等 + 补偿

取消和支付都先检查订单状态（SELECT ... FOR UPDATE 或使用乐观锁）。
更新时带上原状态条件（status = 'PENDING'）。
若更新失败（影响行数为 0），说明状态已变更，根据新状态做不同处理：
- 若已被支付，取消操作失败，提示用户“订单已支付，不能取消”。
- 若已被取消，支付回调需拒绝或触发退款。
使用幂等设计：支付回调需幂等，避免重复处理。
兜底：对账系统定期扫描异常订单，自动修复（如已取消却支付成功则退款）。

🔀 发散问题

Q：用户已支付后才想取消怎么办？ → 转退款流程，退款重试与人工兜底见本文档「如何解决订单重复支付情况？」。
Q：系统自动超时取消怎么实现？ → 延迟任务触发取消，见本文档「如何实现一个订单超时取消功能？」。
Q：取消为什么要先查状态再更新？ → 防止与支付回调竞态造成资损，条件更新的幂等思想与本文档「如何避免用户重复下单（多次下单为支持，占用库存）？」一致。

【中等】如何避免用户重复下单（多次下单为支持，占用库存）？⭐⭐⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：20 min ｜ 🏷 标签：功能设计 / 幂等

💎 关键结论

幂等性设计：同一请求无论提交多少次，只创建一笔订单、只扣一次库存。客户端幂等键 + Redis 快速判断 + 分布式锁 + DB 唯一索引多层防护，重试链路必须透传幂等键。

⚡记忆卡片

口诀：幂等键先行，Redis 快判断，唯一索引兜底。
关键词：幂等键／分布式锁／唯一索引
链路：生成幂等键 → Redis 判断加锁 → 建单扣库存 → 唯一索引兜底

📖 核心知识

核心思想：同一请求无论提交多少次，只创建一笔订单，只扣一次库存（幂等性设计）。

三层防护

前端防重：按钮置灰 + Loading，防止用户双击或连续点击。
后端幂等：
- 幂等键：客户端生成唯一标识（如 UUID），在创建订单时传入。
- 处理流程：后端先查 Redis 该幂等键是否存在 → 存在则直接返回已创建订单，不再扣库存；不存在则加分布式锁，执行业务（创建订单、扣库存），完成后存入 Redis（带过期时间）。
数据库兜底：唯一约束——订单表为幂等键字段建立唯一索引，保证重复插入失败。

库存保护要点

库存扣减必须和订单创建在同一个事务中，保证原子性。
若幂等键已存在，直接返回已有订单，不再扣减库存。

🔬 扩展知识

详情

【L3】Redis 与 DB 状态不一致：Redis 写入成功但建单失败 → 幂等键要带短 TTL 或建单失败时主动清理，避免用户重试被误判为重复。
【L3】唯一索引冲突的语义：并发下后到的请求插入失败，应捕获异常后查询已存在订单返回（而不是报错），保证用户体验一致。
【L3】表单 Token 与幂等键的区别：表单 Token 是服务端预发一次性令牌，提交时校验并删除，防“同一页面重复提交”；幂等键是客户端生成、允许重复提交但返回同一结果，对网络超时重试更友好。现代 API 设计首选幂等键。
【L4】幂等键的传递：客户端重试（网络超时）必须携带同一幂等键；网关重试同理，防止重试风暴下创建多单。
【L4】失效场景：幂等键带短 TTL 时，Redis 过期后用户真重试可能重复建单，靠唯一索引兜底；幂等键若由服务端生成（如每次请求返回新 token），前端刷新/重进页面会重新获取，防重失效。

📚 延伸阅读：Stripe Idempotent Requests

🏭 实战场景

详情

弱网地区电商平台：移动端下单接口超时率 8%，用户习惯超时后立即重试，曾日均产生 3000 笔重复订单。

分析要点：客户端生成幂等键（进入下单页时生成一次，重试不变），服务端三层防护：Redis 幂等键快速判断（存在则直接返回已建订单）→ 分布式锁防并发穿透 → DB 幂等键唯一索引最后防线；网关重试必须透传幂等键，非幂等接口禁止自动重试；捕获唯一索引冲突后查已有订单返回（而非报错）；上线后监控重复订单数降为 0。

⚠️ 常见误区

详情

常见误区：

❌ “前端按钮置灰就能防重复下单” → 网络超时重试、网关自动重试都会绕过前端，必须靠后端幂等。
❌ “Redis 幂等键就够了” → Redis 提供快速判断但非绝对可靠（故障/过期后失效），DB 唯一索引才是最后防线，两层缺一不可。
❌ “网关自动重试能提升成功率，默认开启” → 曾有线上事故：网关对超时请求自动重试但未透传幂等键，弱网用户每单重试产生 2~3 笔重复订单，库存被无效占用——重试链路必须透传幂等键，网关重试仅限幂等接口。

🔀 发散问题

Q：幂等键存 Redis 多久合适？ → 覆盖用户重试窗口 + 业务时效：如 10~30 分钟；同时依赖 DB 唯一索引永久兜底（幂等键入订单表）。Redis 只加速判断，不承担唯一性责任。
Q：用户真的想下两单相同商品怎么办？ → 幂等键区分“重试”与“新意图”：同一幂等键重复提交返回同一订单，新下单生成新幂等键；还可叠加业务限频（同用户同 SKU 1 秒内只允许 1 单）防误操作。
Q：支付环节的重复问题怎么处理？ → 支付回调幂等 + 重复支付退款，见本文档「如何解决订单重复支付情况？」。

【中等】调用第三方接口应注意哪些问题？⭐⭐⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：20 min ｜ 🏷 标签：功能设计 / 外部集成

💎 关键结论

五类注意点：预防性设计（超时/重试/熔断/限流）、安全性、一致性（幂等/补偿）、资源隔离、可观测性；核心原则是不信任任何第三方，故障时必须有降级兜底。

⚡记忆卡片

口诀：超时限流再熔断，重试幂等带唯一键，线程隔离防雪崩。
关键词：超时重试／熔断降级／资源隔离
链路：超时控制 → 重试熔断 → 隔离降级 → 日志监控

📖 核心知识

要点

预防性设计：超时、重试、熔断、限流。
安全性：加密、认证、凭证管理、脱敏。
一致性：幂等、补偿、版本兼容。
资源隔离：线程池、连接池、信号量。
可观测性：日志、监控、链路追踪。

网络与超时控制

连接超时：设置合理的建立连接超时（如 3-5 秒），避免长时间等待。
读取超时：设置接口响应数据读取超时（如 10 秒），防止对方服务慢导致线程挂起。
DNS 解析超时：确保 DNS 查询不成为瓶颈，可考虑使用备用 DNS 或 IP 直连。

异常处理与重试

区分异常类型：网络抖动（可重试） vs 业务错误（不可重试，需人工介入）。
重试策略：指数退避 + 最大重试次数（如 3 次），避免加重对方负载。
幂等性保证：重试时需确保接口支持幂等，否则需业务层去重。

接口限流与熔断

限流：根据对方接口配额或自身系统能力，进行本地限流（如 Guava RateLimiter）或分布式限流。
熔断：引入熔断机制（如 Sentinel、Hystrix），当错误率达到阈值时快速失败，防止雪崩。
降级：定义降级逻辑（如返回缓存数据或默认值），保障核心业务。

数据安全与认证

传输加密：使用 HTTPS 确保数据传输安全，防止中间人攻击。
身份认证：妥善管理 API Key、Token 等凭证，避免硬编码（使用配置中心或密钥管理服务）。
敏感信息：请求/响应中若包含敏感数据，需进行脱敏或加密处理。

幂等性与数据一致性

请求幂等：对于可能重复提交的场景（如支付通知），需通过业务唯一键去重。
最终一致性：若第三方接口响应延迟或失败，需设计补偿机制（如定时对账、状态同步）。

接口版本管理与兼容性

版本控制：明确接口版本（如 URL 路径包含 v1），避免无通知升级导致兼容问题。
变更通知：关注第三方接口变更公告，提前适配。
灰度验证：新版本接口上线前，先在小流量验证。

资源隔离与线程池管理

线程池隔离：为第三方调用分配独立的线程池，避免占用核心业务线程资源。
信号量隔离：对于非阻塞调用，可使用信号量控制并发数。
连接池管理：合理配置 HTTP 连接池大小、空闲连接回收策略，避免资源泄漏。

量化参考：连接超时建议 1~3s（内网调用 1s 即可），读超时按对方 SLA 的 P99 × 2 设置；重试最多 1~2 次且带退避，重试风暴可使对方压力翻倍加剧故障。

🔬 扩展知识

详情

【L3】方案权衡：重试是把双刃剑——对非幂等接口自动重试会引发重复扣款/建单，重试策略必须区分幂等性；熔断阈值设太敏感会在抖动期误断，设太钝会在故障时拖死线程池——需按第三方历史 RT/错误率基线校准。
【L4】事故教训：对接物流接口未设读超时，对方故障时我方线程全部阻塞在等待，线程池耗尽拖垮自身下单链路——第三方调用的超时必须小于自身接口的超时，否则故障会传染。
【L4】场景实战：电商对接 3 家快递公司查件接口，各家 SLA 不同（RT P99 从 200ms 到 2s），高峰期我方查件 QPS 5000，要求对方故障时不影响下单主链路——查件调用独立线程池（舱壁模式），与下单链路线程资源完全隔离；超时按各家 SLA 分别配置（P99×2）；单家错误率超 30% 熔断，降级返回缓存的最后已知物流状态；物流状态改定时拉取 + 缓存，用户查看走缓存而非实时调对方；按对方配额限流，超额排队。核心原则：把第三方依赖从主链路移除，能异步就异步。

📚 延伸阅读：Sentinel（alibaba）／ Resilience4j

🔀 发散问题

Q：第三方接口无幂等支持，但我们必须重试怎么办？ → 业务层造幂等：每次请求携带我方唯一请求号，我方记录请求号与结果，重试前先查本地记录；资金类操作重试前必须查单确认状态。
Q：如何监控第三方接口的健康度？ → 按第三方维度埋点：成功率、RT P99、超时率，与其 SLA 对比告警；建立“依赖健康看板”，故障时快速判断是自己还是对方的问题；重要依赖定期做故障演练。
Q：对方接口升级不兼容怎么应对？ → 防腐层隔离对方模型（升级只改适配层），双版本双跑灰度切换；合同层要求变更提前通知；响应解析对未知字段宽容（反序列化不报错）。

数据场景

【中等】如何实现数据的不停服迁移？⭐⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：15 min ｜ 🏷 标签：功能设计 / 数据迁移

💎 关键结论

四阶段口诀“双写 → 迁移 → 灰度切读 → 降级切换”：新旧库双写，历史数据补录迁移，读流量 1%→100% 灰度放量，稳定后只写新库，全程业务无感知、可回滚。

⚡记忆卡片

口诀：读流量灰度切，逐步放量稳观察；双写降级只写新，观察备份再下线。
关键词：双写／补录迁移／灰度切换
链路：双写 → 历史迁移 + 增量补录 → 灰度切读 → 降级下线

📖 核心知识

核心思想
双写 + 数据同步 + 灰度切换
让新旧两套存储同时提供服务，逐步把流量切到新库，全程业务无感知。

第一阶段、准备与双写

新库上线，应用修改代码：所有写操作同时写入旧库和新库（双写）。
双写需保证最终一致性，可异步或同步（视业务容忍度）。
读操作仍从旧库读取，确保对业务无影响。

第二阶段、历史数据迁移

将旧库中的全量历史数据批量迁移到新库。
迁移过程中，增量数据仍在双写，需保证迁移与增量不冲突。
- 常见做法：记录迁移开始的时间戳或位点，迁移完成后，再补录期间产生的增量。
使用工具（如 DataX、Kettle）或自研脚本，分批迁移，避免影响线上。

第三阶段、灰度读切换

待历史数据迁移完成且双写稳定后，开始灰度切读流量。
逐步将读请求从旧库切到新库，比如 1%、10%、50%、100%。
每个灰度步骤观察业务指标（响应时间、错误率、数据一致性）。

第四阶段、双写降级与最终切换

当读流量全部切到新库且稳定运行后，可考虑将双写降级为只写新库。
此时旧库可作为备份，观察一段时间无异常后，正式下线旧库。
保留旧库一段时间（如一周），以备紧急回滚。

🔬 扩展知识

详情

【L3】补录冲突处理：迁移期间双写增量与历史数据冲突时，按“写入时间比较，新值覆盖旧值”，或以迁移起始位点为准迁移后重扫增量补录。
【L3】回滚预案：双写期间旧库数据完整，读切换异常可随时切回旧库；降级为单写是不可逆操作，必须经过足够观察期再执行。
【L4】异构迁移（MySQL→ES/MongoDB 等）：需额外处理字段映射、类型转换与唯一性校验，切换前做双读比对（影子比对）验证一致性。

📚 延伸阅读：DataX（alibaba）

🔀 发散问题

Q：迁移过程中如何保证增量不丢？ → 记录迁移开始时间戳/位点，迁移完成后补录增量，以位点为准而非人工把控。
Q：增量捕获不想侵入业务代码怎么办？ → 用 Binlog 捕获，参考本文档「如何设计数据同步方案（同步到数仓）？」。

【中等】如何在 10 亿个数据中找到最大的 1 万个？⭐⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：12 min ｜ 🏷 标签：场景设计 / 海量数据 TopK

💎 关键结论

维护一个容量为 1 万的最小堆：读入前 1 万条建堆，之后每条数据与堆顶比较，比堆顶大才替换堆顶并下沉调整。遍历一遍 10 亿数据后，堆中即最大的 1 万个。时间复杂度 O(n log K)，堆仅占约 40KB，适合数据无法全量装入内存的场景。

⚡记忆卡片

口诀：求 Top K 大，建最小堆；堆顶是门槛，够格才进门
关键词：最小堆／ O(n log K) ／ 40KB ／流式单遍
链路：读 1 万条建堆 → 逐条比堆顶 → 大则替换下沉 → 堆中即 Top K

📖 核心知识

1. 量化推导

数据量 n = 10 亿 = 10^9，目标 K = 1 万 = 10^4。
堆内存：1 万个 int ≈ 40KB，可忽略不计；堆无法容纳全量数据，天然适合磁盘 / 流式数据。
复杂度对比：
- 全排序后取前一万：O(n log n) ≈ 10^9 × 30 ≈ 300 亿次比较，且全量数据装不进内存；
- 最小堆：O(n log K) ≈ 10^9 × 13 ≈ 130 亿次比较，约为全排序的 43%。

2. 算法步骤

读入前 1 万条数据，构建最小堆（堆顶是这 1 万条中的最小值，即当前第 1 万大的候选门槛）；
循环读取剩余数据，每条与堆顶比较：
- 小于等于堆顶 → 直接丢弃（不可能进入前一万）；
- 大于堆顶 → 替换堆顶并执行下沉调整（sift-down），O(log K)；
读完全部数据后，堆中留存的即 TOP 10000。

3. 为什么是最小堆而不是最大堆

堆中存的是"当前 Top K 候选"，需要快速淘汰候选中的最小者——最小堆的堆顶恰好是候选最小值，一次 O(1) 比较即可决定是否入围。若建最大堆则需知道全量最大值，逻辑不成立。

🔬 扩展知识

详情

【L3】K 与 n 的相对大小决定算法选择：K 远小于 n 用堆；K 接近 n 时全排序或 QuickSelect 更优。QuickSelect 基于快排分区，平均 O(n) 可找到第 K 大，但要求数据可放入内存，且最坏 O(n²)（随机化pivot 规避）。
【L3】分布式版本：数据分布在多台机器时，每台机器本地求 Top K（各自最小堆），汇总 m × K 个候选到协调节点再求一次全局 Top K，两轮即可，网络传输量极小。
【L4】数据以流的形式持续到达时，最小堆方案依然成立（单遍、增量维护），这正是实时热点统计、监控 Top N 指标的基础结构。

🔀 发散问题

Q：如果数据是搜索日志关键词而不是数字，流程怎么变？ → 先哈希分桶统计词频，再对词频用最小堆取 Top，见「几亿条淘宝搜索日志取热度前十关键词」。
Q：如果问题从 TopK 变成海量去重，方案如何切换？ → 堆不再适用，整数域用 BitMap、允许误差用 BloomFilter，见「40 亿个 ID 去重」。

【中等】有几台机器存储着几亿的淘宝搜索日志，假设你只有一台 2g 的电脑，如何选出搜索热度最高的十个关键词？⭐⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：12 min ｜ 🏷 标签：场景设计 / 海量数据 TopK

💎 关键结论

核心思想是分而治之 + 哈希分桶 + 堆排序：先按哈希取模把几亿条日志打散成若干小桶（同词必进同桶），桶内用 HashMap 统计词频，最后用大小为 10 的最小堆对所有桶的词频结果做一次全局筛选，即得 Top 10 热词。

⚡记忆卡片

口诀：哈希取模分文件，同词同桶不乱窜；小文件全读入，哈希表里计次数；最小堆里比大小，遍历一遍取前十
关键词：哈希分桶／桶内计数／最小堆 Top10 ／ 2G 内存
链路：逐行哈希取模分桶 → 桶内 HashMap 计数 → 最小堆全局归并 → 输出 Top 10

📖 核心知识

1. 内存估算与分桶数选择

几亿条日志约 3GB 量级，2G 内存无法整体载入，且全量词频 HashMap 也放不下，必须分桶。
取 N = 200 个桶：每桶原始数据约 15MB；设每桶去重后约 150 万个不同词，Java HashMap 每条目约 50 字节，约 75MB——2G 内存完全容纳。
关键约束：相同关键词必须落入同一桶，否则词频会被拆散统计错误；哈希取模天然满足。

第一步：哈希分桶（分散数据）

逐行读取日志，对每个搜索词计算哈希值后取模 N（N = 200），追加写入对应临时文件（part_0.txt ~ part_199.txt）。
相同关键词一定进入同一临时文件，且每个文件大小可控（几十 MB 级）。

第二步：内存统计（桶内计数）

依次读取每个临时文件，用 HashMap 统计词频，生成结果文件（result_0.txt，每行 关键词次数）。
单桶可完全载入内存，处理完一个释放一个，内存峰值只与单桶相关。

第三步：堆排取 Top（全局筛选）

维护大小为 10 的最小堆（堆顶是当前第 10 大的词频），遍历所有结果文件的每一行：
- 次数 > 堆顶 → 弹出堆顶、插入该词；
- 否则跳过。
内存中始终只有 10 个元素的堆，一次遍历完成全局 Top 10。

第四步：输出结果

堆中剩下的 10 个词即为搜索热度最高的关键词。

🔬 扩展知识

详情

【L3】若某桶去重词数过多导致内存吃紧：可对该桶做二次哈希细分；或改用"桶内排序 + 归并计数"代替 HashMap——把桶内所有词排序后线性扫描计数，内存开销只剩外排缓冲。
【L3】多机版本即 MapReduce 模型：Map 端输出 (关键词, 1)，Reduce 端按键聚合计数，本质与单机分桶一致。
【L4】词频统计也可用 Trie 树压缩公共前缀降低内存，适合关键词前缀重合度高的场景；但实现复杂度高于 HashMap，一般面试给出即可。

🔀 发散问题

Q：如果数据量涨到内存连单桶都装不下怎么办？ → 增加分桶数（N 调大），或对单桶二次分治，原则是"分而治之"递归到底。
Q：Top10 的最小堆筛选和「10 亿数据找最大 1 万」是同一招吗？ → 是，都是"容量为 K 的最小堆"，只是 K 从 10000 变成 10，见本文档对应题目。

【中等】一张表里有三个字段（id，开始时间，结束时间），表中数据量为 5000W，如何统计流量最大的时候有多少条数据？⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：12 min ｜ 🏷 标签：场景设计 / 区间统计

💎 关键结论

用差分数组 + 扫描线：把每条记录的"开始"记为 +1、"结束"记为 -1，按时间排序后线性扫描做前缀累加，任意时刻的累加值即该时刻的并发条数，最大值即所求。时间复杂度 O(n log n)，远优于逐秒遍历或逐条比对。

⚡记忆卡片

口诀：起点 +1、终点 -1，排序扫描求前缀，峰值即答案
关键词：差分数组／扫描线／前缀和／ O(n log n)
链路：拆 +1/-1 事件 → 按时间排序 → 线性累加 → 取最大值

📖 核心知识

1. 量化推导

5000 万条记录 → 1 亿个事件点（每条拆成开始、结束两个）。
事件点用 long[1 亿] 存放约 800MB（每点 8 字节：时刻编码 + 增量位）；若内存紧张，可对事件点分批外排后再扫描。
复杂度：排序 O(n log n) ≈ 1 亿 × 27 ≈ 27 亿次比较；扫描 O(n)。若用"逐秒遍历每秒查覆盖数"的朴素方案是 O(时间跨度 × n)，完全不可行。

2. 方案一：时间跨度可控时用差分数组

若时间范围不大（如一天 86400 秒、一年约 3150 万秒），直接开 diff[] 数组：diff[start] += 1，diff[end+1] -= 1（闭区间约定），再对 diff 求前缀和，最大值即峰值流量。
数组方式无需排序，O(时间跨度 + n)。

3. 方案二：时间跨度大时用事件点排序

将每条 (开始时间, 结束时间) 拆为两个事件：(start, +1)、(end, -1)；
全部事件按时间排序（同一时刻 +1 事件排在 -1 之前）；
顺序扫描累加，维护最大值——累加值即"此刻有多少条数据在活跃"。

4. 边界约定

若"结束时间"表示该时刻仍在占用（闭区间），-1 事件应记在 end + 1；若表示该时刻已释放，直接记在 end。面试中先与面试官确认口径。

🔬 扩展知识

详情

【L3】同一秒既有开始又有结束时，排序必须让 +1 排在 -1 前，否则瞬时峰值会被低估；且要在"处理完该时刻全部 +1 后"再更新最大值。
【L3】本题是"区间最大重叠数"经典问题，同类应用：服务器并发连接峰值、带宽峰值统计、会议室最少数量（贪心解法）。
【L4】数据无法全量载入内存时，可对事件点做外排后再扫描，扫描阶段内存只需 O(1)。

🔀 发散问题

Q：如果只要峰值出现的时刻怎么办？ → 扫描时同时记录累加值首次达到最大值的时间点即可，算法不变。
Q：这类"扫描线 + 堆"的思路还能解什么？ → 与外排归并一样依赖堆做有序选择，见「500G 数据排序」中的多路归并。

【中等】有 40 亿个 ID，在 1G 内存中进行去重，如何实现？⭐⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：12 min ｜ 🏷 标签：场景设计 / 海量去重

💎 关键结论

用 BitMap（位图）：若 ID 是 32 位无符号整数，全值域 2^32 个 bit 仅需 512MB，1G 内存完全够用。每个 ID 映射为位图上的 1 个 bit，出现过置 1，扫描完成后位为 1 的位置即去重结果。时间 O(n)，空间仅 n/8 字节，精确无误差。

⚡记忆卡片

口诀：整数去重用位图，一个 bit 一个数，40 亿 ID 占 512M
关键词：BitMap ／ 2^32 bit=512MB ／ O(n) ／精确去重
链路：ID 定位 bit 位 → 置 1 标记 → 扫描位为 1 的位置 → 输出去重结果

📖 核心知识

1. 量化推导

前提：ID 为 32 位无符号整数，值域 0 ~ 2^32-1（约 42.9 亿），40 亿个 ID 落在该值域内。
位图空间：2^32 bit = 2^32 / 8 = 512MB，小于 1G 内存限制，方案可行。
对比 HashSet：40 亿条装箱 Integer + 哈希表开销约 40 亿 × 32 字节 ≈ 128GB，完全不可行；BitMap 将空间压缩了 2.5 亿倍。

2. 实现步骤

初始化：申请 512MB 的 byte[]（2^29 个字节），全部置 0；
标记：逐个读入 ID，定位并置位：
- byteIndex = id / 8，bitIndex = id % 8；
- arr[byteIndex] |= (1 << bitIndex)；
输出：扫描位图，所有为 1 的位对应的 ID 即去重后的集合；重复 ID 不会改变已置 1 的位，天然幂等。

3. 适用条件与局限

只适合整数且值域已知的场景；若 ID 是 64 位 long，全值域位图需 2^64 bit = 2EB，不可能实现；
若只关心"是否存在"且允许少量误判，可用 BloomFilter（空间远小于位图）；若要查"缺失的数"，位图同样适用（扫 0 位）。

🔬 扩展知识

详情

【L3】Java 中可直接用 java.util.BitSet，内部即 long 数组 + 位运算，自动扩容；set/get/clear 均为 O(1)。
【L3】ID 值域大但实际出现稀疏时，RoaringBitmap 将 32 位值域按高 16 位分桶、桶内按基数自适应选择数组/位图/区间容器，稀疏场景比稠密位图省几个数量级内存，广泛用于 OLAP 引擎。
【L4】分布式去重：按 ID 哈希分片到多台机器，各节点维护子位图 / HashSet 本地去重，最后汇总——本质仍是"分而治之"，与搜索日志分桶同构。
【L4】BloomFilter 的误判率公式 (1 - e^(-kn/m))^k：给定 n 与可接受误判率 p，可反推所需位数 m 与哈希函数个数 k，这是它优于位图的定量依据。

🔀 发散问题

Q：如果 ID 是字符串而不是整数怎么办？ → 位图失效，改用哈希分桶后桶内 HashSet 去重，见「几亿条淘宝搜索日志」的分桶思想。
Q：去重之外还要排序输出怎么办？ → 位图按下标顺序扫描天然有序；数据量大时结合外排，见「500G 数据排序」。

【中等】如果有 500G 数据需要排序，但是只有 4G 内存，如何实现？⭐⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：12 min ｜ 🏷 标签：场景设计 / 外排序

💎 关键结论

用外部排序：分块内排 + 多路归并。先把 500G 切成约 3.5G 的小块逐块内存排序写回磁盘，再用最小堆对约 143 路有序文件做 K 路归并，配合输入/输出缓冲区流式读写。全程磁盘 I/O 两读一写，归并比较复杂度 O(n log K)，K 为归并路数。

⚡记忆卡片

口诀：切块内排，多路归并，堆选最小，缓冲读写
关键词：外排分治／ 3.5G 块 ×143 路／最小堆归并／缓冲区
链路：分块载入内存排序 → 写回有序临时文件 → 最小堆 K 路归并 → 输出最终结果

📖 核心知识

1. 量化推导

500G / 3.5G ≈ 143 块；留约 0.5G 给归并阶段的缓冲区与堆。
归并路数 K = 143：若同时打开 143 路，每路输入缓冲 2MB 仅需约 286MB，可行；每元素比较次数 log₂143 ≈ 7.2 次。
若内存更小导致路数过大（如上万路），文件句柄与堆开销不可接受，改用多阶段归并：先 16 路归并成中间文件，再归并一轮。

第一步：分块排序

将 500G 数据分成若干小块，每块小于 4G（如 3.5G），保证能载入内存；
每块在内存中内部排序（如快速排序），写回磁盘成为有序的临时文件。

第二步：多路归并

同时打开所有有序临时文件，每个文件分配一个输入缓冲区（几十 MB 级）；
用最小堆从各路缓冲区队首中选出全局最小值，写入输出缓冲区；某路缓冲区读空则从对应文件续读，输出缓冲区满则刷盘；
堆维护 K 个元素，每次取最小后下沉调整 O(log K)。

第三步：清理

归并完成、结果校验后删除临时文件。

关键优化点

缓冲区分配：输入缓冲越大越少 I/O 次数，但要给堆和输出缓冲留余地；
堆优化：最小堆比逐路两两比较减少比较次数；
并行 I/O：异步预读下一批、多线程重叠计算与 I/O；
压缩：临时文件压缩存储，降低磁盘占用与 I/O 量。

🔬 扩展知识

详情

【L3】初始归并段可用**置换-选择排序（replacement selection）**生成平均长度约 2 倍内存的有序段，减少归并轮数；若数据"近乎有序"效果更显著。
【L3】工程实例：MySQL 的 sort_buffer_size 不足时即走磁盘归并排序（filesort），Hadoop MapReduce 的 Shuffle 阶段本质也是外排归并。
【L4】只需全局有序前 N 条时，不必完整归并：对有序块建堆做"多路归并取 TopN"，提前终止，与本文 TopK 题同构。

🔀 发散问题

Q：归并阶段只想取前 1 万条怎么办？ → K 路归并 + 提前终止即可，取够 N 条即停，见「10 亿数据找最大 1 万」。
Q：排序前需要先对 40 亿 ID 去重怎么办？ → 先 BitMap 去重再外排，两阶段串联，见「40 亿个 ID 去重」。

【中等】如何导入百万数据量级的 Excel 到数据库？⭐⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：12 min ｜ 🏷 标签：场景设计 / 批量导入

💎 关键结论

核心是流式读取 + 分批处理 + 批量插入 + 异步化：用 EasyExcel 等流式库逐行读避免 OOM，逐行校验转换，每 1000 条一批走 JDBC batch 插入并小事务提交，整个过程异步执行、进度可查、错误行可回溯可续传。

⚡记忆卡片

口诀：流式读、逐行校、千条一批批量插，异步任务加反馈
关键词：EasyExcel 流式读／ 1000 条/批／ rewriteBatchedStatements ／断点续传
链路：流式读取 → 逐行校验转换 → 分批批量插入 → 异步进度反馈 → 错误记录与续传

📖 核心知识

第一步：流式读取 Excel

痛点：一次性读入百万行必 OOM；POI 的 UserModel（XSSF）会把全表对象化驻留内存。
方案：使用流式读取库，逐行回调处理：
- EasyExcel：基于 SAX 事件模型解析，内存占用与行数无关，是读大文件的主流选择；
- POI 原生读大文件同样用 SAX 事件 API（XSSFReader + SheetHandler）。
- ⚠️ 注意：POI 的 SXSSFWorkbook 是流式写入（导出方向）的 API，不能用于流式读取，容易混淆。

第二步：数据校验与转换

逐行校验格式与合法性（必填、类型、长度、枚举），转换为数据库实体；校验失败的行收集进错误集，不阻断主流程。

第三步：分批缓存与批量插入

批大小：每 1000 条攒一批，达到后执行批量插入；
批量插入：JDBC addBatch() + executeBatch() 或 MyBatis batch 模式；MySQL 需开启 rewriteBatchedStatements=true，才能把多条 INSERT 重写为一条多值 INSERT，吞吐提升可达一个数量级；
事务控制：一批一事务提交，避免长事务占用 undo/redo、加剧锁竞争。

第四步：异步化与进度反馈

前端提交后立即返回任务 ID，后端异步处理；定期更新已处理行数，前端轮询展示进度。

第五步：错误处理与补偿

校验/插入失败的行记录到错误表或错误文件，提供下载；
断点续传：记录已成功行数/游标，中断后从断点继续。

性能优化要点

连接池：按批处理并发度配置合适连接数；
索引策略：导入前禁用非必要二级索引，导入后重建（批量写入时索引维护是主要开销之一）；
极限吞吐：MySQL 可用 LOAD DATA INFILE，绕过 SQL 解析层，比 INSERT 快数倍；
内存控制：流式读 + 分批处理，内存占用恒定在几十 MB 级。

🔬 扩展知识

详情

【L3】量化：百万行 × 每行 1KB ≈ 1GB 原始数据，XSSF 全量对象化后内存膨胀数倍必 OOM；EasyExcel SAX 模式常驻内存仅几十 MB。
【L3】超大文件可分片并行导入：按 Sheet 或行区间切分，多线程各持连接并发批插；注意目标表主键/唯一键冲突与锁竞争。
【L4】任务可靠性：导入任务表记录状态机（待处理/处理中/成功/失败），失败自动重试；结合分片游标实现幂等续传，避免重复插入。

🔀 发散问题

Q：反过来，导出 Excel 很慢怎么优化？ → 同样是"查询 + 组装 + 写文件"三段瓶颈，见本文档「Excel 导出场景很慢，如何优化？」。
Q：导入的数据量涨到 500G 级别怎么办？ → 退化为外排分治思想，见「500G 数据排序」。

【中等】Excel 导出场景很慢，如何优化？⭐⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：12 min ｜ 🏷 标签：场景设计 / 批量导出

💎 关键结论

导出慢先定位瓶颈，一般就三段：数据库查询慢、业务组装慢、文件写入慢。分别用游标分页替换深翻页、批量 RPC 替换循环单次调用、EasyExcel 流式写替换全量内存组装，三段同时优化才能根治。

⚡记忆卡片

口诀：查询用游标，组装走批量，写文件流式，超大分片打包
关键词：游标分页／批量 RPC ／ EasyExcel 流式写／分片 ZIP
链路：定位三段瓶颈 → 游标分页取数 → 批量组装 → 流式写文件 → 超大分片并行

📖 核心知识

Excel 导出慢一般有三种情况：

数据库查询慢
业务逻辑处理慢
Excel 文件写入慢

数据库查询优化

痛点：LIMIT offset, size 分页在 offset 很大时性能极差，需扫描并丢弃大量前缀行；导出百万行时 offset 线性增长，总耗时接近 O(n²)。
方案：游标分页（基于主键 ID）
- 记录上一批最后一条的 ID，下次查询从该 ID 之后开始；
- SQL 示例：SELECT * FROM orders WHERE status = 1 AND id > ? ORDER BY id ASC LIMIT 1000。
前提：ID 字段有索引，且必须带 ORDER BY id ASC，让 MySQL 走索引顺序扫描。
优势：每批只扫描固定行数，性能稳定，深翻页场景速度提升可达数百倍。

业务逻辑优化

痛点：循环中逐条调用 RPC / 缓存，网络 IO 次数爆炸，耗时剧增。
方案：批量查询
- 先从列表提取所有查询条件（如用户 ID），一次性批量调用 batchGetUserByIds；
- 再用结果 Map 回填数据，将 N 次 RPC 降为 1 次。
优势：大幅减少网络交互，显著提升接口响应速度。

Excel 生成优化

痛点：POI 的 XSSF 等传统方式将全量数据组装到内存，大数据量导出易 OOM。
方案：EasyExcel 流式写入 + 分批查询
- 流式写入：边查边写，每批刷入磁盘，内存占用稳定在 100-200MB；
- 分批查询：结合游标分页，每次查 1000 行，避免全量加载。
进阶：超大数据量可多线程分片导出，按地区/时间分片并发生成多个 Sheet 或文件，最后打包 ZIP。
优势：避免 OOM，支持超大数据量导出，内存占用可控。

🔬 扩展知识

详情

【L3】量化：百万行导出若用 LIMIT offset 翻页，第 100 万页需扫描丢弃约 100 万行，总扫描量 ≈ n²/(2×批大小)；游标分页恒为 n，差距随数据量平方放大。
【L3】EasyExcel 写大文件时的内存模型：SXSSF 类流式写会保留窗口内行、其余刷临时文件，单 Sheet 行数上限 104 万（xlsx 规范），超限需拆多 Sheet 或多文件。
【L4】异步导出 + 文件中心：大导出任务异步化，结果文件上传 OSS，完成后站内信/邮件通知下载，彻底避免接口超时与并发导出拖垮应用内存。

🔀 发散问题

Q：导入和导出能复用同一套分批框架吗？ → 能：流式 IO + 分批处理 + 异步任务是同一套骨架，见「导入百万 Excel 到数据库」。
Q：导出数据源查询本身就很慢，除了分页还能怎么办？ → 可改从从库/数仓读、或预先跑批落中间表，导出只扫中间表，思路与消息推送的人群圈选分片一致。

【中等】假设生产者-消费者模型中有 200 万个生产者，只有 1 个消费者，如何实现？⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：12 min ｜ 🏷 标签：场景设计 / 并发模型

💎 关键结论

关键在于消除写端锁竞争 + 撑高单消费者吞吐：生产侧用 Disruptor 式无锁环形队列（CAS 抢序号写入，缓存行填充防伪共享）；消费侧批量拉取 + 线程池并行业务处理；再配背压机制防堆积。同时要想清：200 万生产者不是 200 万线程，需用 NIO/Reactor 收敛为少量 IO 线程。

⚡记忆卡片

口诀：写端无锁 CAS，读端批量拉取，满了背压，连接靠 Reactor
关键词：Disruptor ／ RingBuffer ／批量消费／背压／ Reactor
链路：NIO 收敛连接 → CAS 抢序号写 RingBuffer → 消费者批量拉取 → 线程池处理 → 背压保护

📖 核心知识

核心挑战

200 万并发写：直接竞争同一个队列会导致严重锁冲突、CPU 飙升；
单消费者：消费速度可能成为瓶颈，需最大化消费者效率；
内存压力：海量数据堆积可能撑爆内存。

设计目标：高吞吐、低延迟、背压保护、数据不丢失（按需）。

生产者优化：无锁环形队列

问题：200 万生产者直接写同一队列，竞争激烈；
方案：采用无锁环形队列 + 多生产者序号分配，典型实现是 Disruptor：
- 预先分配固定大小的环形缓冲区（RingBuffer）；
- 每个生产者通过 CAS 竞争获取下一个可写入的序号，然后写入数据；
- 消费者通过序号屏障读取；
优点：无锁、预分配内存、缓存行填充避免伪共享，性能极高。

消费者优化：批量 + 异步

问题：单消费者处理速度必须跟上写入速度；
方案：批量拉取，每次从环形缓冲区拉一批数据（如 1000 条），减少调用次数；收到一批后提交线程池并行处理业务（如需保序则按序号分段提交）。

背压机制

问题：生产速度超过消费速度，数据堆积；
方案：RingBuffer 满时生产者按策略处理——阻塞、自旋或抛异常；堆积超阈值则降级（丢弃非关键数据、记日志）；实时监控缓冲区使用率，触发扩容或限流。

生产者线程管理

问题：200 万个生产者若是独立线程，系统无法支撑（线程栈内存 + 调度开销）；
方案：用 NIO/Reactor 模型（如 Netty）处理海量连接，由少量 IO 线程承接 200 万连接的事件并作为生产者写队列；若生产者是业务线程，用线程池限制并发，由有限线程代表 200 万任务写入。

🔬 扩展知识

详情

【L3】Disruptor 高性能的根源：环形数组预分配避免 GC；序号 CAS 无锁；缓存行填充（padding）防伪共享；消费侧序号屏障避免逐条通知。
【L3】量化：若单条处理 1ms，单消费者串行吞吐上限约 1000 条/秒；批量拉取 + 8 线程池可提升至数千条/秒——先算消费上限再决定批量与线程数。
【L4】若业务允许拆分，可将"1 个消费者"改为按 key 哈希分组的多消费者分区消费（MQ 分区思想），本题的约束下则需在单消费者内做并行。

🔀 发散问题

Q：如果消费端也要削峰怎么办？ → 引入 MQ 缓冲，生产-消费两端解耦，见「消息推送系统」的削峰设计。
Q：队列堆积导致内存爆了怎么办？ → 背压 + 降级丢弃，与推送系统的频控/限流思想同构。

【中等】如何对 500 万会员提前 7 天进行过期提醒？⭐⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：12 min ｜ 🏷 标签：场景设计 / 定时任务

💎 关键结论

核心思路：定时任务 + 索引优化 + 异步通知。在 expire_date 上建索引，每天定时扫描"7 天后到期"的会员（范围查询命中索引），对命中者异步发送提醒并记录已提醒状态防重复。关键是把"扫全表"变成"扫一天的到期量"。

⚡记忆卡片

口诀：索引建在到期日，定时只扫那一天，异步发提醒，发过打标记
关键词：expire_date 索引／滚动扫描／异步通知／防重标记
链路：定时任务触发 → 索引范围查当日到期 → 异步发送提醒 → 标记已提醒

📖 核心知识

1. 量化推导

500 万会员，若到期日分布均匀，单天到期量 ≈ 500 万 / 365 ≈ 1.4 万人；任务每天只需处理这个量级，而非 500 万。
expire_date 建索引后，查询 WHERE expire_date = 当前日+7 是范围扫描，只读命中行；若无索引则全表扫 500 万行。

2. 方案设计

在会员表的 expire_date 字段上建立索引；
设置定时任务（如每天凌晨），滚动翻页扫描索引，筛选 7 天后过期的数据；翻页用主键游标而非 LIMIT offset，避免深翻页；
对命中会员发送提醒（短信/推送/站内信），走异步队列 + 批量发送，不阻塞扫描主流程；
在记录表中标记状态为已提醒（或用"提醒记录表 + 唯一索引"），任务重跑不重复发。

3. 健壮性要点

任务失败可重跑，幂等靠已提醒标记/唯一索引保障；
发送失败进重试队列；监控当日提醒量，骤降告警（防索引失效/任务未调度）。

🔬 扩展知识

详情

【L3】若到期分布极不均匀（如促销日集中到期），单日量可能几十万，扫描分批 + MQ 削峰是必要组合，与推送系统同构。
【L3】更精确的定时可用延时消息（Redis ZSet score=提醒时间戳、RocketMQ 延时消息）代替轮询；但 500 万量级一次性写入延时队列成本高，"日级扫描 + 异步发送"更稳。
【L4】提醒渠道抽象为通道层（短信/推送/邮件），按用户偏好与免打扰时段过滤，避免骚扰——与推送系统的频控设计一致。

🔀 发散问题

Q：如果提醒渠道扩容成多渠道、千万级用户怎么办？ → 直接演进为消息推送系统，见「如何设计一个消息推送系统」。
Q：扫描翻页为什么不能用 LIMIT offset？ → 深翻页扫描丢弃行，性能 O(n²)，应改主键游标，见「Excel 导出优化」的同类优化。

地理搜索

【中等】如何快速找到附近距离用户最近的 N 家商户？⭐⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：15 min ｜ 🏷 标签：功能设计 / LBS

💎 关键结论

通法都是“空间索引粗筛 + 精确距离重排取 Top N”：小规模高并发用 Redis GEO 一条命令直取；海量持久化用 GeoHash 前缀匹配 + 邻域扩展，或 ES geo_distance，按数据量与查询形态选型。

⚡记忆卡片

口诀：GeoHash 编经纬，前缀匹配找附近，邻域扩展防边界，精确计算再排序。
关键词：GeoHash ／ Redis GEO ／ geo_distance
链路：经纬度编码 → 区域粗筛 → 精确距离排序 → 取 Top N

📖 核心知识

方案一、GeoHash + MySQL（通用、易实现）

原理：将二维经纬度编码为一维字符串，前缀相同的区域相邻。
步骤：
1. 商户入库时，根据经纬度计算 GeoHash 值（如 6-8 位），存入数据库并建索引。
2. 查询时，计算用户位置的 GeoHash，取前缀匹配（如前 6 位），查询该区域及周围 8 个邻域的商户。
3. 对查询结果计算精确距离，排序取前 N 个。
优点：实现简单，支持分库分表，精度可控。
缺点：边界问题需扩展邻域，精确距离计算需回表。

方案二、Redis GEO（高性能、简单）

原理：Redis 3.2+ 内置 GEO 类型，基于有序集合（ZSet）存储经纬度，提供地理距离计算。
步骤：
1. 用 GEOADD 将商户 ID 和经纬度加入 Redis。
2. 用 GEORADIUS 或 GEORADIUSBYMEMBER 查询用户附近 N 个商户，直接返回距离排序结果。
优点：性能极高（内存操作），API 简单，支持距离排序和返回距离。
缺点：数据需全量驻留内存，容量受限于内存；适合商户数量可容纳的场景。

方案三、Elasticsearch Geo Distance（搜索型、可扩展）

原理：ES 内置地理点类型和地理距离查询，利用倒排索引和空间索引。
步骤：
1. 定义字段类型为 geo_point，索引商户经纬度。
2. 使用 geo_distance 查询，按距离排序，取前 N 个。
优点：支持海量数据，可与全文搜索结合，分布式天然扩展。
缺点：需部署 ES 集群，运维成本较高。

方案四、空间索引（PostGIS / MySQL Spatial）（数据库原生）

原理：关系数据库的空间扩展，使用 R-Tree 索引加速几何计算。
步骤：
1. 创建 GEOMETRY 列存储点坐标，建立空间索引。
2. 使用 ST_Distance 和 ST_Within 等函数查询最近点。
优点：数据库原生支持，无需额外组件，数据一致性好。
缺点：某些数据库实现（如 MySQL）的空间索引性能可能不如 GeoHash 或 Redis；PostGIS 性能优异但需 PostgreSQL。

方案选型建议

场景	推荐方案	理由
商户数百万以内，并发高	Redis GEO	简单、快、内存可控
商户数千万以上，需持久化	GeoHash + MySQL / MongoDB	成本低，可水平扩展
需要复杂查询（文本+地理）	Elasticsearch	功能全面，扩展性强
已有 PostgreSQL	PostGIS	原生支持，性能优异

优化技巧

多级索引：先用行政区划（城市、区县）粗筛，再用 GeoHash 细查。
缓存热点：热门区域的查询结果可缓存，减少重复计算。
动态网格：根据商户密度动态调整网格大小，平衡精度和性能。
异步更新：商户位置变化不频繁，可异步更新索引。

🔬 扩展知识

详情

【L3】GeoHash 边界问题：地图上相邻的两点可能 GeoHash 前缀完全不同，查询必须扩展周围 8 个邻域；位数越少网格越粗、候选越多，精度与性能需权衡。
【L3】Redis GEO 容量：GEO 本质是 zset，百万级商户占用百 MB 级内存，但需全量驻留内存，容量超限必须转 GeoHash + DB/ES。
【L4】组合过滤：实际业务常叠加“距离 + 评分/销量/配送范围”复合排序，ES 比 Redis GEO 更适合。

📚 延伸阅读：GeoHash - Wikipedia ／ ES Geo queries

🔀 发散问题

Q：商户位置动态变化（如骑手）怎么办？ → 异步更新索引（MQ 消费后更新 GEO/GeoHash），位置变更低频可接受最终一致。
Q：全国商户量太大如何分片？ → 按城市或 GeoHash 前缀分片，查询先定位分片再检索。
Q：热门区域查询结果怎么缓存？ → 热点区域结果短 TTL 缓存 + 定时刷新，缓存抗流量思路参考本文档「如何设计一个点赞功能？」。

【中等】如何实现 Nearby 搜索（附近的人/商户）？⭐⭐⭐⭐

🎯 目标等级：L3 ｜ ⏱ 建议用时：15 min ｜ 🏷 标签：搜索 / 地理

💎 关键结论

Nearby 搜索的核心是地理索引。三种方案：① GeoHash（将经纬度编码为字符串，前缀越相同越近）；② 四叉树（递归四分空间）；③ S2 Geometry（Google 出品，球面投影）。Redis GEO 命令底层用 GeoHash + Sorted Set。

⚡记忆卡片

口诀：经纬度编码串，前缀同则近
关键词：GeoHash ／四叉树／ S2 Geometry ／ Redis GEO
链路：经纬度 → GeoHash 编码 → 前缀匹配邻近区域 → 精确距离过滤 → 排序返回

📖 核心知识

GeoHash 原理：经纬度分别二分编码交织；精度与长度成正比（6 位≈1.2km，8 位≈38m）。
查询流程：计算目标点 GeoHash 前缀 → 取周围 8 个区域前缀 → 查索引获取候选 → 精确 Haversine 距离过滤。
Redis GEO：GEOADD/GEOSEARCH/GEOPOS 命令；底层 GeoHash 整数编码存入 ZSet。
大规模优化：按区域分片；热点区域（市中心）加缓存；动态调整 GeoHash 精度。

搜索算法

【中等】如何实现分面搜索（Faceted Search）？⭐⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：15 min ｜ 🏷 标签：搜索 / 电商

💎 关键结论

分面搜索 = 搜索 + 多维聚合。用户搜索后，左侧展示各维度（品牌/价格/颜色/评分）的可选值及计数；用户勾选后作为 Filter 缩小结果集。Elasticsearch 的 Aggregation 天然支持。

⚡记忆卡片

口诀：搜索出结果，聚合列维度，勾选再缩小
关键词：Facet ／聚合／ Filter 组合／ Elasticsearch Aggregation
链路：关键词搜索 → 返回结果+各维度聚合计数 → 用户勾选 Facet → 追加 Filter → 重新搜索

📖 核心知识

实现原理：每次搜索同时对预定义字段做 terms aggregation，统计每个值的文档数。
性能优化：Facet 字段用 doc_values（列式存储）加速聚合；高基数字段（如 SKU）慎用。
交互设计：多选（OR/AND 可配置）；层级 Facet（类目树）；价格区间 Facet（range aggregation）。
缓存策略：相同查询+筛选条件的聚合结果缓存；增量更新时失效相关缓存。

【中等】如何实现拼写检查与模糊搜索？⭐⭐⭐

🎯 目标等级：L3 ｜ ⏱ 建议用时：15 min ｜ 🏷 标签：搜索 / 容错

💎 关键结论

拼写检查的核心是编辑距离 + 候选生成。两种方案：① 基于词典：对查询词计算编辑距离 ≤k 的所有变体，检查是否在词典中；② 基于 n-gram：将词拆成 bigram/trigram，建索引，查询时匹配相似 n-gram 集合。Elasticsearch 用第二种。

⚡记忆卡片

口诀：编辑距离找近词，n-gram 拆片段
关键词：编辑距离／ n-gram ／ BK-Tree ／ Did-you-mean
链路：查询词 → 生成候选（编辑距离/n-gram） → 按频率排序 → 返回 "您是不是要找"

📖 核心知识

编辑距离：Levenshtein 距离（插入/删除/替换/转置）；Damerau-Levenshtein 支持相邻字符转置。
BK-Tree：一种度量树，按编辑距离组织词典，查询效率远优于暴力遍历。
n-gram 方案：将 "apple" 拆成 [ap, pp, pl, le]；查询 "aple" 拆成 [ap, pl, le]；Jaccard 相似度匹配。
模糊搜索：Elasticsearch 的 fuzzy query（基于编辑距离）和 match query 的 fuzziness 参数。

安全算法

【中等】加密后的数据怎么支持模糊搜索？⭐⭐

🎯 目标等级：L2 ｜ ⏱ 建议用时：15 min ｜ 🏷 标签：安全设计 / 加密检索

💎 关键结论

密文天然不支持模糊搜索，必须借助辅助结构。最常用分词加密：数据分词后确定性加密建索引，搜索词同样处理去匹配；迫不得已用数据库解密搜索（性能极差慎用）；专业方案交给 ES 这类外置搜索引擎。安全性和可搜索性不可兼得，按敏感度取舍。

⚡记忆卡片

口诀：数据分词存密文，搜索分词去匹配，索引加速效果好
关键词：分词加密／确定性加密／解密搜索／外置搜索引擎
链路：明文分词 → 确定性加密 → 辅助字段建索引 → 搜索词同样处理 → 密文匹配

📖 核心知识

方案一：分词加密（最常用）

要点：数据分词存密文，搜索分词去匹配，索引加速效果好。

原理：
1. 对原始数据进行分词（如手机号 13812345678 拆成 138, 1381, 13812... 或固定长度组合）。
2. 对每个分词进行确定性加密（每次加密结果相同，如 AES 确定模式）。
3. 将分词密文存入辅助字段，建立索引。
4. 搜索时，对搜索词做相同分词和加密，用加密后的分词去索引中匹配。
优点：
- 支持模糊搜索：通过匹配部分词实现模糊效果。
- 性能较好：使用索引精确匹配。
缺点：
- 安全性略降：确定性加密和分词暴露了部分信息（攻击者可统计频率）。
- 存储增加：需额外字段。

方案二：数据库解密搜索（迫不得已）

要点：解密再查询，简单但巨慢，慎用。
原理：
1. 在数据库层面使用可解密的函数（如 MySQL 的 AES_DECRYPT）。
2. SELECT * FROM user WHERE AES_DECRYPT(encrypted_phone, key) LIKE '%138%'。
优点：实现简单，不改变现有逻辑。
缺点：
- 性能极差：无法使用索引，全表扫描解密。
- 密钥暴露风险：密钥需传递给数据库，易泄露。

方案三：外置搜索引擎（专业方案）

要点：专业的事交给 ES，加密索引两不误。
原理：
1. 将明文数据发送给专业搜索引擎（如 Elasticsearch），利用其内置的加密功能或插件（如 ES 的 Encrypted 字段）。
2. ES 对数据加密索引，搜索时同样加密查询词进行匹配。
优点：功能强大（支持复杂搜索、分词、排序）；安全可控（专业的加密方案）。
缺点：引入新组件，增加架构复杂度；成本较高。

🔬 扩展知识

详情

【L3】只需精确查找（如手机号等值查询）时可用 HMAC 盲索引：对明文算带密钥的 HMAC 存为索引列，等值查询走索引，安全性优于确定性加密，但不支持模糊。
【L4】可搜索加密（Searchable Encryption）是学术界的通用方案，用加密陷门实现密文检索，但实现复杂、性能代价大，生产中极少直接使用。
【L4】确定性加密相同明文产生相同密文，可被频率分析攻击，只适合敏感度可接受部分泄露模式的场景（如手机号后四位），高敏字段慎用。

🔀 发散问题

Q：敏感数据的整体保护框架是什么？ → 模糊搜索只是加密后的检索难题之一，见「接口中的敏感数据（如身份证号、手机号）应该如何保护？」。
Q：如果只是想展示打码而不是加密呢？ → 见「数据脱敏有哪些方案？静态脱敏与动态脱敏如何选型？」。