不做大哥好多年 不做大哥好多年
首页
  • MySQL
  • Redis
  • Elasticsearch
  • Kafka
  • Etcd
  • MongoDB
  • TiDB
  • RabbitMQ
  • 01.Python
  • 02.GO
  • 03.Java
  • 04.业务问题
  • 05.关键技术
  • 06.项目常识
  • 10.计算机基础
  • Docker
  • K8S
  • 容器原理
  • Istio
  • 01.GO基础
  • 02.面向对象
  • 03.并发编程
  • 04.常用库
  • 05.数据库操作
  • 06.Beego框架
  • 07.Beego商城
  • 08.GIN框架
  • 09.GIN论坛
  • 10.微服务
  • 01.Python基础
  • 02.Python模块
  • 03.Django
  • 04.Flask
  • 05.SYL
  • 06.Celery
  • 10.微服务
  • 01.Java基础
  • 02.面向对象
  • 03.Java进阶
  • 04.Web基础
  • 05.Spring框架
  • 100.微服务
  • 数据结构
  • 算法基础
  • 算法题分类
  • 前置知识
  • PyTorch
  • Linux基础
  • Linux高级
  • Nginx
  • KeepAlive
  • ansible
  • zabbix
  • Shell
  • Linux内核

逍遥子

不做大哥好多年
首页
  • MySQL
  • Redis
  • Elasticsearch
  • Kafka
  • Etcd
  • MongoDB
  • TiDB
  • RabbitMQ
  • 01.Python
  • 02.GO
  • 03.Java
  • 04.业务问题
  • 05.关键技术
  • 06.项目常识
  • 10.计算机基础
  • Docker
  • K8S
  • 容器原理
  • Istio
  • 01.GO基础
  • 02.面向对象
  • 03.并发编程
  • 04.常用库
  • 05.数据库操作
  • 06.Beego框架
  • 07.Beego商城
  • 08.GIN框架
  • 09.GIN论坛
  • 10.微服务
  • 01.Python基础
  • 02.Python模块
  • 03.Django
  • 04.Flask
  • 05.SYL
  • 06.Celery
  • 10.微服务
  • 01.Java基础
  • 02.面向对象
  • 03.Java进阶
  • 04.Web基础
  • 05.Spring框架
  • 100.微服务
  • 数据结构
  • 算法基础
  • 算法题分类
  • 前置知识
  • PyTorch
  • Linux基础
  • Linux高级
  • Nginx
  • KeepAlive
  • ansible
  • zabbix
  • Shell
  • Linux内核
  • Python

  • GO

  • Java

  • 业务问题

  • 关键技术

  • 项目常识

    • 01.DDD领域驱动设计
    • 02.Redis_JWT_三方登录
    • 03.Restful风格
    • 04.三方支付
    • 21.后端场景题Part1
    • 22.后端场景题Part2
      • 02.场景题Part2
        • 1、微信发红包的api
        • 2、美团商家置顶和更新
        • 3、骑手并发抢单问题
        • 4、分布式定时任务调度器
        • 5、短链服务
        • 6、订单超时自动取消
        • 7、大文件上传
        • 8、快速得知IP是哪个组的
        • 9、分布式ID 不重复
        • 10、设计一个本地缓存
        • 11、电商购物车设计
        • 12、多目标调度优化
  • 计算机基础

  • 区块链

  • 常识
  • 项目常识
xiaonaiqiang
2024-12-19
目录

22.后端场景题Part2

# 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}
    
    1
    2
  • 分片上传参数

    • 任务 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 中
    • 对价格和库存的校验可以异步处理,仅在结算时进行强校验,减少购物车操作中的计算量

# 12、多目标调度优化

  • 面试官在考什么

    • 理解业务目标之间的冲突和约束

    • 具备策略设计思维:如何建模为评分函数、过滤器、权重机制

    • 能做工程落地:调度系统如何支撑策略的运行、高并发处理、热更新等

  • 场景建模:问题是多目标任务分配

    • 我们当时需要在 N 个任务、M 台车辆中做调度决策

    • 每个任务都有位置、优先级、时效性等信息,车辆也有当前状态

    • 比如

      • 电量是否充足?
      • 当前是否空闲?
      • 到达目标点的路径耗时?
    • 调度目标往往不止一个,比如要

      • 最小化路径耗时(响应快)

      • 最大化资源利用率(调度效率)

      • 保证车辆不会“调度即失败”(比如电量不够)

  • 策略抽象:打分模型 + 阶段性过滤

    • 们的策略是 将多目标转化为打分模型,每台车-任务组合都会计算一个分数

    • Score = α × 路径评分 + β × 状态评分 + γ × 负载评分

      • 路径评分:用高德/自建地图计算最短路径时间;
      • 状态评分:车辆当前状态是否合适(如电量 > 20%、不在维修);
      • 负载评分:该车辆最近任务数量、历史负载等。
    • 这样我们就能用一个统一评分方式排序任务分配。

  • 系统实现:评分器 + 匹配器 + 执行器

    • 调度系统中,我们做了模块划分

    • 候选生成器:从所有车辆中根据状态/距离过滤出可选车辆集合;

    • 评分器模块:根据策略规则进行打分(通过配置化的 JSON DSL,后期也支持外接算法模型);

    • 任务匹配器:基于得分结果做贪心分配或使用匈牙利算法;

    • 任务下发器:将调度结果通过消息队列发送到设备端;

  • 我的职责与技术点

    • 我主要负责的是调度引擎的整体框架设计和调度策略的配置化实现:

    • 使用 Go + Redis + gRPC 构建高并发调度服务;

    • 支持策略模块热更新 + 多目标策略打分;

    • 调度状态流转和失败兜底机制保障;

    • 高并发下调度性能压测和调优;

  • 与算法协同

    • 我们也与算法团队对接过模型打分器(如用强化学习/LightGBM)
    • 我们在工程上将评分器模块抽象成策略服务接口,可以无缝替换内部规则逻辑或外部模型评分
上次更新: 2025/2/19 16:42:39
21.后端场景题Part1
01.操作系统概述

← 21.后端场景题Part1 01.操作系统概述→

最近更新
01
06.Mage平台
05-30
02
16.区块链交易所
05-28
03
01.常识梳理
05-28
更多文章>
Theme by Vdoing | Copyright © 2019-2025 逍遥子 技术博客 京ICP备2021005373号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式