问题和回答记录

  1. 介绍分布式KV项目（答：Raft, ReadIndex, Pebble, Redis, Snapshot, StatefulSet, HeadlessService, Region分裂）

  2. 讲一下Raft过程（答：背诵）

  3. 故障恢复怎么做的（答：日志回放，重新选举，网络分区）

  4. Raft会出现多个Leader的情况吗（答：网络分区导致脑裂会出现）

  5. LSM Tree 写放大（答：Compaction，多次写入之后flush，然后合并SSTable，导致数据重复）

  6. 服务发现是怎么做的（答：StatefulSet保证DNS分配有序增长，Headless Service保证没有cluster IP，不走负载均衡，DNS查询返回所有Pod 的 IP列表，然后Golang层面AddNode，由Leader发起ConfChange，把新节点加入到集群）

  7. 这里具体是怎么配置（答：有点不清楚想问什么，yaml中配置，然后具体做是一个静态的表）

  8. 这里AddNode如果有很多个请求怎么办（答：串行，ProposeConfChange）

  9. 那如果ConfChange冲突怎么解决（答：不清楚怎么解决，就说应用层就已经限制串行了，必须commit+apply，不可能冲突）

  10. 极端环境下出现脑裂怎么解决（答：少于半数不可用，停止写入，保证一致性）

  11. 日志同步丢包怎么办（答：定期压缩快照，项目中有实现这一点，可以做断点续传）

  12. 会出现多个节点超过半数吗（答：不可能，Raft是多数投票一次性）

  13. k8s多个pod，怎么发现这个新的pod

  14. 秒杀系统讲一下

  15. 为什么用etcd来做，redlock是怎么做的（答：CP系统，redlock用setnx）

  16. redlock的问题在哪里（答：AP可能不一致，可能惊群）

  17. etcd怎么保证这个强一致性（答：lease租约，txn）

  18. 假设多个进程获取一个分布式锁，这个场景会发生什么

  19. 这里锁漂移是怎么发生的

  20. 假设一个进程拿到了锁，但是执行的任务很复杂，需要阻塞等待，超过了TTL，如何保证不会把别人的锁给释放掉，相当于这个锁已经被另外一个线程拿到了，但是原有的进程还是会触发一次释放

  21. 时间戳好像不能解决这个问题，还有没有什么办法（答：Redis存一个锁的key和一个进程的pid）

  22. Redis这个方案稍微有点复杂，能保证原子吗（答：用lua保证）

  23. 保证原子的情况下，有没有更简单的方案（答：compare and delete，不清楚具体怎么做）

  24. C++ 内存分区了解吗（答：代码段，数据段，堆，栈等）

  25. 什么时候这个变量是放到栈上，什么时候放到堆上（答：malloc，new，直接声明）

  26. malloc和new有什么区别（答：malloc返回void*，new加一个指针类型的强制转换）

  27. 除了这个类型转换还有什么（答：构造？）

  28. 虚函数是什么（答：类似接口，子类override）

  29. 构造函数能是虚函数吗（答：不能，构造之后才有虚函数表，构造函数为虚函数逻辑上矛盾）

  30. 虚函数表存在哪里

  31. 运行时多态是怎么实现的

  32. C++的unordered_map和map的底层

  33. C++的vector的底层

  34. Golang的map呢

  35. 链地址法和开放地址法

  36. SQL问题，Province，PlayerID，给出每个省份的Player数量（答：GroupBy，Count）

  37. Linux常用的命令（答：随便说，说不完）

  38. 怎么查看一个进程占用的内存 （答：ps或者htop）

  39. ps -ef能看到哪些内容（答：PID，父进程PID，虚拟内存占用，启动Command）

  40. 合并K个升序链表（答：分治）

  41. 时间复杂度呢（答：KNlogK，问有没有更快的方式，答：堆）

  42. 具体怎么做（答：每一次把头结点放进去，然后top取出之后把node.next放进堆）

  43. 实现具体代码（5min，main函数没写完，时间到了）

  44. 还漏了一个关于RPC的问题，这个分布式kv有用到RPC吗，如果我需要调用一个RPC服务，我需要传什么内容

答：需要传入服务地址，方法名，参数等内容。具体来说: - 服务地址：RPC 服务的 IP 和端口 - 方法名：要调用的具体方法名称 - 参数：调用方法所需的参数，如果使用 protobuf 或 JSON 等序列化格式，需要将参数序列化为字节流 - 返回值：RPC 调用完成后会返回结果，通常也是序列化后的字节流，需要反序列化为具体类型 - 错误处理：需要处理网络异常、超时等错误情况 - 认证信息：如果服务需要认证，可能还需要传入 token 或其他认证信息

面试问题和标准答案

1. 介绍一下你的分布式 KV 存储项目

回答

Raft 做一致性，ReadIndex 提供只读请求快速处理，Pebble 是底层 LSM 存储引擎，Redis 做热点缓存，Snapshot 支持快照压缩恢复，K8s 使用 StatefulSet 和 HeadlessService 实现服务发现，支持 Region 分裂扩展。

标准答案

本系统是基于 Raft 的多节点分布式 Key-Value 存储，支持强一致性、动态扩容、持久化与缓存协同等特性：

  • 一致性保证：使用 Raft 算法选主和同步日志。
  • 读优化：支持 ReadIndex 实现线性一致的只读查询。
  • 存储引擎：底层基于 Pebble（一个 RocksDB 的替代实现），实现 LSM Tree 存储。
  • 缓存加速：前置 Redis 缓存热点键值对。
  • 集群扩展：Region 分裂和动态迁移支持扩容。
  • Kubernetes 部署：使用 StatefulSet 保证节点 DNS 顺序，Headless Service 支持服务发现。

2. 请详细讲一下 Raft 协议的流程

回答

Raft 协议有三种角色，选举阶段 Candidate 拉票，成为 Leader 后发心跳维持领导地位，日志复制靠 AppendEntries，提交后同步到状态机。

标准答案

Raft 协议包含以下关键流程：

  • 角色：Follower、Candidate、Leader
  • 选举：Follower 超时转 Candidate，发起投票，获得多数变 Leader。
  • 心跳：Leader 周期性发心跳维持领导权。
  • 日志复制：Leader 追加日志，Follower 接收并存储。
  • 提交日志：当多数节点确认某日志后，Leader 提交日志，并通知 Follower 提交。
  • 故障恢复：新 Leader 会对未对齐日志的 Follower 进行回滚和补齐。

3. Raft 协议中的故障恢复是如何做的？

回答

通过重新选主、日志回放、快照压缩，网络分区后恢复通信可以自动同步。

标准答案

  • 选主机制保证出现故障时可以快速选出新 Leader（<1s）。
  • 落后节点通过 Raft 的日志或快照补齐。
  • 定期生成快照压缩日志，减小恢复代价。
  • 网络恢复后旧 Leader 会降级为 Follower。

4. Raft 是否可能出现多个 Leader？

回答

是的，在网络分区导致脑裂的时候可能多个节点都选举成功。

标准答案

在网络分区的情况下，不同分区可能都能获得超过半数选票，从而出现多个 Leader。但由于 Raft 中选票不能重复投，因此严格意义上同一任期只能有一个 Leader，多个 Leader 情况最终会被回收/降级。

5. 请解释一下 LSM Tree 的写放大问题

回答

每次写入都先写内存表，flush 成 SSTable 后还要 Compaction，多次合并导致多次写磁盘。

标准答案

LSM Tree 通过内存 MemTable 进行写缓冲，然后 flush 为 SSTable 文件。Compaction 是把多个 SSTable 文件合并成更大的一层，会引发多次写入相同 key，导致写放大。比如一个 key 写入一次，在 compaction 时可能会重写 3-5 次。

6. 在你们系统中，服务发现是怎么做的？

回答

StatefulSet 保证 Pod 命名有序，HeadlessService 返回所有 Pod IP，Leader 解析 IP 并通过 ConfChange 加入节点。

标准答案

使用 K8s 的 StatefulSet 和 Headless Service：

  • StatefulSet 确保 pod 命名顺序和稳定 DNS（如 kv-0.kv-headless.default.svc.cluster.local）。
  • Headless Service 不提供负载均衡，返回所有 pod 的真实 IP。
  • 业务层使用 DNS 查询 Pod 列表，由当前 Leader 发起 Raft 的 ConfChange 请求注册新节点。

7. StatefulSet 和 Headless Service 在你的项目中是怎么配置的？

回答

在 yaml 中静态写了副本数和服务，具体配置靠一个静态表。

标准答案

StatefulSet 指定 replicas，并挂载持久卷，确保数据不丢。Headless Service 配置中 clusterIP: None，返回所有 Pod IP。新节点上线通过解析 StatefulSet 命名规则自动识别。

8. 如果多个请求同时发起 AddNode，会出现什么问题？

回答

应用层串行控制，ConfChange 是串行的，必须 commit 才能继续。

标准答案

Raft 协议原生不支持并发配置变更。ConfChange 必须串行执行，Raft 状态机在未提交前拒绝接收第二个配置请求。应用层需要通过排队/分布式锁控制请求顺序。

9. 如果两个 ConfChange 冲突了该怎么办？

回答

应用层限制串行，系统里 commit + apply 完成前不会再发请求。

标准答案

Raft 协议不允许多个配置请求并发执行。如果出现冲突说明逻辑有问题，建议用 ConfChangeV2 或 Joint Consensus 实现原子变更多个节点配置。

10. 如果极端网络环境下发生脑裂，系统怎么处理？

回答

少于半数的 Leader 会自动降级，停止写入，避免不一致。

标准答案

Raft 要求超过半数节点才能 commit。出现脑裂时，孤立节点无法获得多数，只能保持只读状态或降级为 Follower。这样即使发生脑裂，也不会写入冲突数据。

11. 如果日志同步时发生丢包，系统怎么保证恢复？

回答

可以通过快照断点续传，Follower 接收失败后重新请求 Leader 日志。

标准答案

Raft 会记录每个 Follower 的日志索引，发生丢包或断连时，从上次日志索引恢复；如果日志太旧会发送 snapshot，snapshot 支持分段发送，支持断点续传。

12. Raft 中会不会出现多个节点都超过半数的情况？

回答

不可能，因为一个节点只能投一次票，两个多数集不可能同时存在。

标准答案

不会，数学上“多数派”集合不可能交叉，Raft 投票机制也保证一轮任期内每个节点只投一次票，不可能出现多个节点都获得多数。

13. 在 Kubernetes 中，如果多个 Pod 同时启动，你是如何发现并连接这些新 Pod 的？

回答

使用 Headless Service 和 StatefulSet，DNS 查询返回所有 Pod 的 IP 地址，Leader 解析并执行 AddNode 加入集群。

标准答案

Headless Service 配置 clusterIP: None，DNS 查询返回所有 Pod IP。StatefulSet 保证 Pod 命名稳定，例如 kv-0, kv-1。业务层 Leader 节点通过 DNS 解析所有节点地址，依次执行 Raft 的 ProposeConfChange 操作添加新节点。

14. 请介绍一下你们的秒杀系统设计

回答

Kafka 缓冲请求，Redis 做库存判断和排行榜，库存异步落库，etcd 做锁。

标准答案

  • 前端限流，预热缓存
  • 消息入 Kafka 实现削峰填谷
  • Redis 扣库存 + Lua 脚本保证原子
  • Etcd 实现分布式锁防止超卖
  • 异步落库防止阻塞
  • 排行榜用 Redis ZSet 结构实现，按 score 排名

15. 为什么你们使用 etcd 而不是 Redis 的 redlock？

回答

因为 etcd 是 CP 系统，保证一致性，而 redlock 是基于 setnx 的分布式锁，可能在网络分区下出现问题。

标准答案

etcd 基于 Raft 实现强一致性，即使在分区条件下仍然保证锁的正确性；而 redlock 属于最终一致性方案，网络延迟或 Redis 实例不同步可能导致多主。

16. Redis 的 redlock 有什么问题？

回答

网络延迟会导致锁漂移或惊群，多个客户端可能都认为自己获得了锁。

标准答案

  • 多实例的时间不同步可能导致误判锁过期
  • 客户端网络延迟会导致锁释放延迟或抢锁失败
  • Redis 故障重启导致锁状态丢失
  • 实际部署中不能严格保证分布式场景下的一致性

17. etcd 是如何保证强一致性的？

回答

使用租约机制（lease）保证锁的持有者是唯一的，事务（txn）机制保证操作原子性。

标准答案

etcd 基于 Raft 协议，每次写入都要过半节点确认。支持租约机制（lease）对 key 设置 TTL，结合事务（txn）机制可以实现 check-and-set 操作，防止竞争条件。

18. 如果多个进程同时尝试获取同一个分布式锁，这种场景下会发生什么？

回答

只有一个进程会抢到锁，其他会失败或等待重试。

标准答案

  • 如果用 etcd：只有第一个成功执行 txn 的客户端拿到锁，其它返回失败；支持监听事件实现 watch 重试。
  • 如果用 Redis：setnx 保证原子性，后续客户端只能等待锁释放或失败。

19. 锁漂移（Lock Drift）是如何发生的？

回答

客户端阻塞或系统时钟不同步，导致租约过期被他人抢占，但旧客户端还认为自己拥有锁。

标准答案

锁漂移常由以下情况导致：

  • TTL 过期后还未释放
  • 网络分区时锁状态不一致
  • 客户端执行任务卡住未续租
  • 时钟漂移或不同步，导致判断误差

20. 假设某个进程拿到了锁，但执行任务时间太长超过 TTL，锁被别人拿走，这时原进程仍尝试释放锁，会发生什么？

回答

会误删别人的锁，导致数据不一致。

标准答案

必须为锁记录唯一 ID，例如客户端 UUID，在释放时通过 compare-and-delete 或 Lua 脚本确保只有锁 owner 才能释放锁，否则可能误删有效锁。

21. 使用时间戳来判断锁是否有效是否安全？还有没有其他方法？

回答

时间戳不安全，推荐使用唯一 ID（如 pid、UUID）结合 CAS 比较释放。

标准答案

时间戳方案易受网络抖动/时钟不同步影响。更稳妥方式是将锁的 value 设置为唯一进程标识，释放时必须进行 ID 对比，或使用原子脚本控制。

22. Redis 实现 compare-and-delete 方案能保证原子性吗？

回答

可以，用 Lua 脚本执行 get + check + del 保证原子。

标准答案

是的。Redis 的 EVAL 执行 Lua 脚本是单线程的，天然原子。可写脚本判断 key 的值是否匹配当前客户端 ID，然后删除，实现 compare-and-delete。

23. 有没有更简单的方法保证 compare-and-delete 的原子性？

回答

可以用 Redis 的 Lua 脚本或特殊命令，但不太清楚具体怎么做。

标准答案

使用 Lua 脚本如：

1
2
3
4
5
if redis.call("get", KEYS[1]) == ARGV[1] then
    return redis.call("del", KEYS[1])
else
    return 0
end

即可保证 get 与 del 的原子性。

24. C++ 中了解内存分区结构吗？

回答

分为代码段、数据段、堆、栈等区域。

标准答案

C++ 程序运行时内存分为：

  • 代码段：存放程序指令（只读）
  • 数据段：全局变量和静态变量
  • 堆：动态分配内存（new/malloc）
  • 栈：函数局部变量、参数

25. 什么时候变量是放在栈上？什么时候放在堆上？

回答

局部变量默认在栈上，new 或 malloc 分配的是堆。

标准答案

  • 栈：函数内声明变量、参数默认在栈上
  • 堆：new/malloc 动态分配内存，需要手动释放（delete/free）

26. malloc 和 new 有什么区别？

回答

malloc 返回 void*，要强转，new 返回对应类型指针。

标准答案

  • malloc 是 C 风格，返回 void*，不调用构造函数
  • new 是 C++，返回具体类型指针，并调用构造函数
  • 对象释放时，free 不调用析构函数，而 delete 会调用析构函数

27. 除了类型转换，new 和 malloc 还有什么不同？

回答

new 会调用构造函数，malloc 不会。

标准答案

new 是 C++ 的操作符，构造对象，自动类型安全；malloc 仅分配内存。new 和 delete 是成对使用，支持重载和异常处理。

28. 什么是虚函数？

回答

类似接口，子类 override 虚函数，运行时多态。

标准答案

虚函数是用 virtual 修饰的成员函数，支持运行时多态，基类指针调用子类方法依赖 vtable（虚函数表）实现动态绑定。

29. 构造函数能是虚函数吗？

回答

不能，构造过程中还没有虚函数表。

标准答案

不能。构造函数在对象创建时调用，而虚函数表尚未初始化，逻辑上无法使用虚函数。

30. 虚函数表（vtable）存在哪里？

回答

每个对象有一个隐藏的 vptr 指针，指向类的 vtable。

标准答案

vtable 是类级别的静态表，包含函数指针。每个含虚函数的对象会有一个隐藏指针（vptr）指向该类的 vtable。

31. C++ 的运行时多态是如何实现的？

回答

通过 vtable 和 vptr。

标准答案

当类含虚函数时，编译器为其生成 vtable 表，对象中包含 vptr 指针指向 vtable。调用虚函数时通过 vptr 查表，实现动态绑定。

32. C++ 中 map 和 unordered_map 的底层实现分别是什么？

回答

map 是红黑树，有序；unordered_map 是哈希表，无序。

标准答案

  • map：基于红黑树（平衡二叉搜索树），插入/查找/删除复杂度 O(logN)。
  • unordered_map：基于哈希表，使用链地址法解决冲突，平均复杂度 O(1)。

33. C++ 中 vector 的底层实现原理是什么？

回答

是一个动态数组，支持自动扩容。

标准答案

vector 使用连续内存存储元素，自动扩容时按 1.5~2 倍扩容，旧数据搬迁到新地址。支持随机访问但插入删除中间元素代价较高。

34. Golang 的 map 是怎么实现的？

回答

基于哈希表实现。

标准答案

Go map 使用开放寻址 + 桶（bucket）+ 哈希冲突解决机制，每个桶包含多个 key-value，冲突时通过扩容或链式 bucket 链接。

35. 链地址法和开放地址法分别是什么？

回答

链地址法使用链表处理哈希冲突，开放地址法则查找下一个空位。

标准答案

  • 链地址法：每个桶是一个链表，冲突元素挂在链上（如 C++ unordered_map）
  • 开放地址法：发生冲突时继续探测下一个可用位置（如 Go 的 map）

继续整理第 36 至 43 题，保持题干完整，不合并问题：

36. 有一张表记录了玩家的所属省份和 PlayerID，请写一条 SQL 查询语句，统计每个省份的玩家数量

回答

1
SELECT Province, COUNT(PlayerID) FROM table GROUP BY Province;

标准答案

1
2
3
SELECT Province, COUNT(DISTINCT PlayerID) AS PlayerCount
FROM PlayerTable
GROUP BY Province;

说明：使用 DISTINCT 防止重复计数，GROUP BY 进行分组聚合。

37. Linux 中常用的命令有哪些？

回答

太多了，比如 ls, cd, grep, ps, top, htop, df, du, chmod, chown, kill 等。

标准答案

常见 Linux 命令分类举例：

  • 文件操作：ls, cd, cp, mv, rm, touch, mkdir
  • 系统信息：top, htop, uptime, free, vmstat
  • 进程管理：ps, kill, killall, nice, renice
  • 网络：ping, netstat, ss, curl, wget, scp, ssh
  • 磁盘与权限：df, du, chmod, chown, mount

38. 如何查看一个进程占用的内存情况？

回答

可以用 ps aux 查看 RSS/VSZ，或者使用 htop 查看实时内存占用。

标准答案

  • ps -eo pid,comm,%mem,rss,vsz 查看各进程内存
  • top 或 htop 动态查看内存占用
  • /proc/<pid>/status 查看 VmRSS、VmSize
  • smem -r -k 更详细的工具（需安装）

39. ps -ef 输出中包含哪些信息？

回答

PID，父进程 PID（PPID），虚拟内存占用（VSZ），启动命令（CMD）等。

标准答案

ps -ef 显示如下字段：

  • UID：用户 ID
  • PID：进程 ID
  • PPID：父进程 ID
  • C：CPU 占用率
  • STIME：启动时间
  • TTY：终端
  • TIME：累计 CPU 时间
  • CMD：启动命令行

40. 请你实现一个算法，合并 K 个升序链表

回答

可以使用分治或者最小堆，先两两合并或者用优先队列维护每个链表头节点。

标准答案

两种方式：

  1. 分治：递归两两合并，时间复杂度 O(NlogK)
  2. 最小堆（优先队列）：每次从堆中取最小节点并推入其 next 节点，时间复杂度 O(NlogK)

41. 合并 K 个升序链表的时间复杂度是多少？有没有更快的方式？

回答

堆方式是 O(N log K)，比直接遍历所有元素合并 O(KN) 要快。

标准答案

  • 分治合并：O(N log K)，N 为总节点数，K 为链表数
  • 优先队列（堆）：O(N log K) 无法比 O(N log K) 更快，因为每个元素都必须访问一次，logK 是堆的插入/删除复杂度下界。

42. 使用堆实现合并 K 个升序链表，具体步骤是什么？

回答

  1. 把每个链表头结点放入堆；
  2. 每次取堆顶最小节点加入结果链表；
  3. 如果该节点有 next，推入堆中；
  4. 重复直到堆为空。

标准答案

堆中保存所有链表头节点，流程如下：

1
2
3
4
5
6
7
8
auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
for (auto node : lists) if (node) pq.push(node);
while (!pq.empty()) {
    auto minNode = pq.top(); pq.pop();
    tail->next = minNode;
    if (minNode->next) pq.push(minNode->next);
}

43. 请你实现合并 K 个升序链表的完整代码（5 分钟内）

回答

代码部分写完了合并逻辑，但 main 函数没有来得及写。

标准答案（C++ 示例）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);

    for (auto node : lists) {
        if (node) pq.push(node);
    }

    ListNode dummy(0), *tail = &dummy;
    while (!pq.empty()) {
        ListNode* node = pq.top(); pq.pop();
        tail->next = node;
        tail = tail->next;
        if (node->next) pq.push(node->next);
    }

    return dummy.next;
}