音视频 AI Agent 一面:一致性哈希、gRPC 与 B+ 树三层能存多少行
- 轮次
- 一面
- 时间
- 2026-11
- 来源
- 牛客网
《面试题目》
- 自我介绍。
- 介绍一段实习经历。
- 你那里缓存的是全量数据吗?预热的是周活用户吗?周活是多少?
- 这段实习里有没有遇到什么问题?
- 讲讲你的开源经历,用画板画一下架构。
- 一致性哈希是怎么实现的?权重怎么配置?
- 再讲一个开源的需求,用画板画出链路。
- HTTP、HTTPS、gRPC 有什么区别?gRPC 的底层是 HTTP/2 吗?
- Netty 的实现原理是什么?
- Java 的并发模型是怎样的?
- Go、Java、C++ 在并发层面有哪些共性和不同?
- 你平时用 Go 并发,举一个工作中的场景。
- Go 有哪些锁?API 是什么?在画板上写一下。
- 你说熟悉 MySQL,具体熟悉哪几方面:ACID、事务、索引?
- 索引有几种?
- 使用索引时,有遇到过什么问题吗?
- 给定一个表结构(一个主键索引、一个联合索引),问里面的索引结构是怎样的。
- 画一下主键索引的数据结构。
- B 树和 B+ 树有什么区别?
- B+ 树三层最多能存多少数据?具体怎么计算?
- 算法:给一个数组,求中位数,说说思路。
- 用快排求中位数,时间复杂度是多少?
- 快排有什么缺点?大量重复元素会导致性能下降,分析一下。
《参考解析》
缓存与预热这道追问在验证「你是不是真做过」:被问「缓存的是全量还是热点」,要能说清数据规模与选型依据——全量缓存适合数据量小、读多写少、变更可接受的场景(实现简单、命中率高),热点缓存适合数据量大、长尾访问多的场景(内存可控但要处理穿透与击穿)。「预热周活用户」要能给出具体口径:周活是按登录去重还是按活跃行为去重、量级多少、预热在什么时间点触发、预热失败怎么降级到回源、命中率与回源 QPS 的对比。数字答不上来会被认为只是跟着做、没掌握全貌。
一致性哈希与权重:普通取模在节点增减时几乎全部 key 都要迁移;一致性哈希把节点与 key 都映射到 0~2³²−1 的环上,key 顺时针找第一个节点,增删节点只影响相邻区间。节点少时分布不均,用虚拟节点把每个物理节点映射成几百个位置摊平负载;权重则给高配机器更多虚拟节点(或按权重划分环上的区间)。帖主提到的「加权随机 + 虚拟节点降低方差」是这个思路的工程版本:虚拟节点数量越多,各节点分到的 key 比例越接近权重,方差越小,但内存与查找开销也上升(环可以用有序数组加二分,或跳表)。再补一句更彻底的方案——Jump Consistent Hash 或 Rendezvous Hashing,前者无需存储环、扩缩容时迁移量最小,后者实现简单且天然支持权重。
HTTP、HTTPS、gRPC 与 Netty:HTTP 是明文的应用层协议,HTTPS 在其下加 TLS(握手、证书校验、对称加密),解决窃听与篡改;HTTP/1.1 有队头阻塞、头部冗余,HTTP/2 引入二进制分帧、多路复用、HPACK 头部压缩、流控与服务端推送。gRPC 建立在 HTTP/2 之上,用 protobuf 做序列化,支持四种调用形态(一元、服务端流、客户端流、双向流),带 deadline、metadata 与状态码,天然适合内部服务间调用;它的性能优势来自二进制编码与多路复用,而不是某种私有传输协议。Netty 的核心是主从 Reactor:boss 组处理 accept、worker 组处理读写,每个 Channel 绑定一个 EventLoop(单线程执行,避免锁),事件沿 ChannelPipeline 里的 Handler 链传播;ByteBuf 用池化与引用计数减少分配,CompositeByteBuf 与 FileRegion 实现零拷贝,写缓冲的水位线(WRITE_BUFFER_WATER_MARK)提供背压。
三种语言的并发模型:Java 是共享内存模型,线程映射到内核线程(Loom 的虚拟线程改变了这一点),用 synchronized、volatile、AQS 系的 ReentrantLock、CountDownLatch、并发容器与线程池,JMM 规定 happens-before;Go 是 CSP 模型,goroutine 由运行时调度(GMP,M 绑内核线程、P 是逻辑处理器、G 是协程),用 channel 通信、select 多路复用,锁有 sync.Mutex、RWMutex、atomic、Once、WaitGroup、Map、Cond,还有 context 做取消与超时;C++ 最接近硬件,std::thread 直接映射系统线程,靠 atomic、mutex、条件变量与内存序(memory_order)自己保证正确性,没有运行时调度器。共性是要处理竞态、可见性、死锁与背压;差异是调度在用户态还是内核态、错误处理是返回错误还是异常、以及能否轻易开出十万级并发。
MySQL 索引与 B+ 树:按数据结构分 B+ 树索引(InnoDB 默认,聚簇索引与二级索引)、哈希索引(Memory 引擎、自适应哈希)、全文索引、以及基于 R-Tree 的空间索引。InnoDB 的主键索引是聚簇索引,叶子节点直接存整行;二级索引的叶子存主键值,查非索引列要回表。联合索引遵循最左前缀,能覆盖查询时走覆盖索引不回表,MySQL 5.6 之后还有索引下推(ICP)把过滤条件下推到存储引擎层。用索引常见的问题:索引失效(对列做函数运算、隐式类型转换、前导模糊 %x、OR 混用非索引列)、区分度低的列建索引收益小、索引太多拖慢写入并占空间、长字段建索引要用前缀索引、以及范围查询之后的列无法继续用索引排序。
B 树与 B+ 树的区别,以及三层能存多少:B 树的非叶子节点也存数据,一个节点能放的索引项更少,且范围查询要在树里来回跳;B+ 树的非叶子只存键与子指针,数据全在叶子,叶子之间用双向链表相连,所以层数更少、范围扫描是顺序 IO、每次查询路径长度稳定。三层能存多少行完全取决于假设:页大小 16KB、主键为 8 字节 bigint、页内指针 6 字节,则每个非叶子页可放约 16KB / 14B ≈ 1170 个索引项;叶子页存行,若每行 1KB 则一页 16 行,三层即 1170 × 1170 × 16 ≈ 2190 万行;若行更小(如 200B,一页 80 行),能到一亿行以上。所以标准答案是「给出公式与假设,再给量级」,而不是背一个固定数字。
求中位数与快排的退化:排序后取中间是 O(n log n);Quickselect 只递归包含中位数的那一侧,平均 O(n)、最坏 O(n²)(每次 pivot 都取到极值),随机化 pivot 或 median-of-medians 可以把最坏压到 O(n)。工程上直接用 std::nth_element(内省选择,退化时切堆排序)或 Python 的 statistics.median。数据量大到放不进内存时用双堆(大顶堆存较小一半、小顶堆存较大一半)流式维护,或用分桶按值域二分。快排的缺点正是这道追问要的:不稳定、最坏 O(n²)、递归深度 O(log n) 到 O(n)(可用尾递归优化或显式栈)、以及对已排序数组不友好。大量重复元素时,两路划分(Lomuto)会把等于 pivot 的元素全分到一侧,每次只缩小一个元素,退化成 O(n²);解法是三路划分(小于、等于、大于),等于区一次成型,全相同元素时一轮就结束——这也解释了为什么标准库的 sort 用内省排序而不是朴素快排。