02.场景题Part2

1、微信发红包的api

• 采用随机分配算法（如二倍均值法），保证红包随机性，同时精确到分，分配逻辑满足总金额和总数量的约束
  • 每次抢红包，金额在 [1, 2 * 平均值] 范围内随机
  • 剩余金额减少，重复上述逻辑直到分配完所有红包
• 高并发抢红包处理：
  • 使用 Redis 存储红包数据，并通过分布式锁机制防止并发问题
  • 用户抢红包时从 Redis 列表中弹出金额，减少数据库操作
• 通过Redis + MySQL 双写机制，并引入事务和防重复领取逻辑，确保分布式系统下的数据一致性
• 通过队列削峰、异步操作和分布式部署，解决高并发场景的性能问题

2、美团商家置顶和更新

• 美团首页每天会从10000个商家里面推荐50个商家置顶，每个商家有一个权值，你如何来推荐？第二天怎么更新推荐的家？

• 推荐策略（第一天）
  • 用户评价：商家的评分和评价数
  • 历史转化率：点击转化率、订单量等
  • 曝光机会：前期曝光少的商家可能需要一定的扶持
  • 地域与时间相关性：例如与用户当前位置、时段相关的商家
  • 使用加权排序：w1 * UserRating + w2 * ConversionRate …
• 更新推荐（第二天）
  • 根据前一天的推荐结果反馈更新权值，例如点击率、转化率等
  • 对长期推荐的商家进行时间衰减，降低其权值，保证新商家有更多机会
  • 使用策略，90% 权值推荐，10% 随机探索

3、骑手并发抢单问题

• 如果一个外卖配送单子要发布，现在有200个骑手都想要接这一单，如何保证只有一个骑手接到单子？

• 分布式锁

  • 基于唯一标识 order_id，生成分布式锁
  • 第一个成功获取锁的骑手分配到单子，锁释放后其他骑手返回失败
  • 为每个订单设置最大抢单时间，超时未分配则重新分配
  • 在 Redis 中设置锁的过期时间，防止死锁

• 队列流量削峰

  • 订单取消支付冲突处理骑手点击抢单后，请求被投递到 RabbitMQ 或 Kafka 消息队列
  • 将抢单结果异步返回给骑手

• 据一致性保障

  • 数据库与 Redis 之间采用事务或双写机制，保证分布式环境下数据一致性

4、分布式定时任务调度器

• 1）定时任务

  • 使用分布式锁（如 ETCD 的租约机制）确保每个任务只能被一个节点触发

  • 任务唯一性标识可以使用 任务ID+时间撮

  • 调用 Grant 创建一个租约，并设定超时时间，分布式锁以租约的 ID 为标识绑定，锁的有效期与租约一致

  • 使用 ETCD 的 KeepAlive 方法，自动发送心跳包续约

  • 如果节点发生故障（如宕机），租约会自动过期，锁将释放，其他节点可以重新抢锁

• 2）周期性任务

  • 问题：如果节点启动时间不同，可能会导致某个任务在不同节点先后被触发
  • 确保所有节点基于相同的触发时间点计算任务周期
    • 每个任务的触发时间为 T0 + N * Period，其中 N 是自然数，Period 是任务周期
    • 每个节点计算当前时间对应的最近触发点，并等待该时间触发任务
  • 使用 ETCD 分布式锁，确保同一任务在一个周期内只由一个节点执行
  • 通过租约续约和自动抢占机制，解决节点故障时的任务调度问题
  • 确保任务逻辑具备幂等性，防止重复执行的副作用

5、短链服务

• 微博或者短信都有单条发送字数的限制，如果需要分享一个长网址，很容易越出限制
• 短链服务可以将长网址变成短网址，方便传播

• 使用哈希算法（如 MD5 或 SHA256）对长链接进行哈希处理，生成固定长度的哈希值

• 提取哈希值的前若干位（如 6-8 位）并使用 Base62 编码，生成短链接 ID

  • 一个 8 位的 Base62 短链可以表示 (62^8 = 218\万亿) 个不同的短链（实际就是62进制数）

• 冲突解决

  • 使用数据库（如 Redis、MySQL）存储短链和长链的映射关系

  • 在插入前检查生成的短链是否已存在，若存在则标记为冲突

  • 如果出现冲突，加入自增数字重新计算Base62

• 短链还原

  • 查询存储系统，通过短链 ID 查找对应的长链，返回原始长链供客户端使用

• 安全性：在生成短链时加入加密签名，防止篡改

  • 短链的结构可以包含签名例如：https://short.link/{shortID}.{signature}

  • shortID 是短链接的主要部分（如 Base62 编码后的结果）

  • signature 是根据 shortID 和密钥生成的加密校验值

6、订单超时自动取消

• 方案1：定时轮训 Redis ZSET 有序集合
  • 将任务的执行时间作为分数，将任务的唯一标识（如任务ID）作为集合中的元素
  • 优缺点
    • 优点：是查询效率高
    • 缺点：是依赖定时任务执行频率
• 方案2：Redis key过期监听
  • 当设置一个key的过期时间时，可以设置一个回调函数
  • 当key过期时，Redis会自动调用这个回调函数
  • 优缺点
    • 优点：实时性好，资源消耗少，支持高并发
    • 缺点：对Redis服务的依赖性强

7、大文件上传

• 在上传大文件前，前端需与后端交互，获取一个唯一的任务 ID，用于标识该文件上传任务

• # 前端请求示例 {"fileName":"bigfile.zip","fileSize":5242880000,"fileHash":"md5-of-file"}
  # 后端响应    {"taskId":"123e4567-e89b-12d3-a456-426614174000","chunkSize":5242880}
  

• 分片上传参数

  • 任务 ID（taskId）：标识文件所属的上传任务
  • 分片序号（chunkIndex）：分片的顺序编号（从 0 开始）
  • 分片哈希值（chunkHash）：可选，校验分片数据完整性
  • 总分片数（totalChunks）：便于服务端校验是否全部接收完成
  • 文件大小和文件名：必要时附加，用于后端验证和存储

• 后端将分片按序号合并为完整文件（taskId）

• 断点续传

  • 上传之前，前端计算整个文件的 MD5 值，用于标识该文件的唯一性
  • 如果文件分片上传过（即后端已记录该 MD5 值的任务），后端返回已上传分片列表，前端跳过这些分片

• 方案二：也可以在后端生成OSS预签名，前端自己上传到OSS然后将上传路径和任务对应关系发送给后端，后端合并

8、快速得知IP是哪个组的

• 给每个组分配不同的IP段，怎么设计一种结构使的快速得知IP是哪个组的

• 方法1：前缀树（Trie）

  • 将IP地址按位拆分，以前缀树的形式存储每个IP段

  • 每个叶子节点存储对应的组ID

  • 优势：

    • 前缀树适合处理范围查询，可以高效匹配IP段
    • 查找时间复杂度为 O(k)，其中 k 是IP地址的位数（IPv4为32）

• 方法2：区间映射（Range Mapping）+ 二分查找

  • 将所有IP段按照起始地址排序，存储为有序数组，并存储组ID
  • 查询时使用二分查找快速定位IP段
  • 优势：
    • 实现简单，插入与删除成本较低，查询时间复杂度为 O(log⁡n)，其中 n 是IP段数量

• 方法3：哈希表（针对无重叠的IP段）

  • 将每个IP段直接映射为一个哈希表的键，键值对为IP段与组ID

  • 适用于IP段范围少且固定的场景

9、分布式ID 不重复

• 雪花算法，它是Twitter开源的由64位整数组成分布式ID，性能较⾼，并且在单机上递增

• 1.第一位 占1 bit，其值始终是0，没有实际作用

• 2.时间戳 占41 bit，单位为毫秒，总共可以容纳约69年的时间

• 3.工作机器id 占10 bit，其中高位5bit是数据中心ID，低位5bit是工作节点ID最多可以容纳1024个节点

• 4.序列号 占12 bit，用来记录同毫秒内产⽣的不同id

  • 每个节点每毫秒0开始不断累加，最多可以累加到4095，同一毫秒一共可以产生4096个ID
  • 同一毫秒的ID数量 = 1024 X 4096 = 4194304

• 故障处理：

  • 时钟回拨 (服务器上的时间突然倒退到之前的时间)

    • 直接抛出异常、阻塞等待时间同步、或将机器下线避免冲突

  • 机器 ID 冲突：通过中心化服务（如 Zookeeper 或 ETCD）动态分配唯一机器 ID

10、设计一个本地缓存

• 使用 字典 + 双向链表 实现本地缓存 LRU（最近最少未使用）

• 字典： 查找、插入和删除操作的时间复杂度均为 O(1)

  • key（缓存键），value（双向链表节点指针）

• 双向链表：用于维护访问顺序

  • 双向链表中的每个节点存储一个缓存项，包含键和值
  • 最近使用的缓存项放在链表的头部，最久未使用的缓存项放在链表的尾部
  • 当有新的缓存项加入或访问某个缓存项时，将其移到链表头部
  • 如果缓存容量已满，需要移除尾部节点（最久未使用的项），并同时更新哈希表

• 缓存策略：LRU（最近最少使用）、LFU（最不经常使用）

• 缓存容量：确定缓存的最大容量

• 缓存淘汰机制：当缓存容量达到上限时，需要决定淘汰哪些缓存项

• 缓存过期机制：设置缓存项的过期时间

• 并发访问控制：考虑多线程或多进程同时访问缓存的情况

11、电商购物车设计

• 实时性和一致性
  • 购物车中信息可能与下单时实际状态不一致，需要实时校验和更新
  • 使用 Redis 缓存商品详情、库存、价格等热点数据，减少数据库压
  • 用户提交订单时，通过库存服务和价格服务进行最终校验，确保数据的准确性
• 未登录与已登录用户数据同步
  • 未登录状态下，使用 LocalStorage 或 Cookie 临时保存购物车数据
  • 登录后，服务器合并本地和远端数据，按修改时间优先级或数量累计策略处理冲突
• 复杂业务规则的高效处理
  • 满减、优惠券、会员价等规则复杂多变，需要在用户操作时动态校验
  • 对固定促销规则的商品进行预计算，并将结果缓存到 Redis 中
  • 对价格和库存的校验可以异步处理，仅在结算时进行强校验，减少购物车操作中的计算量