从笔试考场出来那天下着小雨我在百度科技园门口站了很久脑子里反复回放的是最后那道磁盘调度题。两年后我成了计算与存储方向的工程师再回头看这套2018年校招笔试题第二批才真正明白当时那些看不懂为什么要考的知识点其实全是分布式存储系统日常工作的基本功。这套题考察范围很典型C内存布局、操作系统虚拟内存、缓存替换策略、存储引擎索引结构、TCP拥塞控制覆盖了一个存储研发工程师最核心的知识底座。我根据自己的回忆和后续工作复盘把每一类题目的考察意图、解题思路和工程关联重新整理了一遍希望能帮准备计算与存储方向的学弟学妹们少走一些弯路。需要说明的是面试题库每年都会更新我做的是结合当年的题目和实际工作后的理解把知识点串联起来讲透而不是提供标准答案大全。复习的最终目的也不是背题而是建立完整的知识图谱。1. C虚函数与内存布局一道看似送分的题为何刷掉一半人1.1 原题还原一个多继承的析构陷阱当年第二大题给了一段不算复杂的C代码考的是虚函数表和多继承的内存偏移问题大意如下根据回忆整理非原题代码#include iostream using namespace std; class A { public: virtual void a() { cout A::a endl; } virtual void b() { cout A::b endl; } int x; }; class B { public: virtual void c() { cout B::c endl; } virtual void d() { cout B::d endl; } int y; }; class C : public A, public B { public: void b() override { cout C::b endl; } virtual void e() { cout C::e endl; } int z; }; int main() { C c; cout sizeof(C) endl; A* pa c; B* pb c; cout (pa (void*)c) endl; cout (pb (void*)c) endl; cout dynamic_castB*(pa) endl; delete pb; return 0; }题目问了四个小问sizeof(C)是多少pa和pb是否等于C对象的起始地址pa转换成B*是否成功delete pb会执行哪个析构函数这道题难吗单看每个知识点都不难但组合在一起就很容易出错因为它同时考察了虚函数表结构、多继承下的对象布局、交叉类型转换和析构安全性。1.2 逐问拆解64位系统下的内存布局先算sizeof(C)。64位系统下一个虚函数指针占8字节int占4字节。C同时继承A和B对象内存里会有两份虚表指针再加上A的int x、B的int y、C自己的int z一共是8844424字节。因为8字节对齐24正好是8的倍数不需要额外padding。所以答案就是24。这里有个容易踩的坑很多人以为C只重写了b()应该只继承A的虚表就够了B不需要单独存一份。这是错的多继承下C必须为每个基类都维护对应的子对象和虚表完整性是C对象模型的基本原则编译器不会因为你只覆盖了一个函数就合并两份虚表。第二个小问pa与C对象起始地址比较。A是C的第一个基类所以pa指向的地址就等于C对象的起始地址输出1。pb则指向C对象内部B子对象的起始位置这个位置在A子对象之后偏移了8412字节虚表指针8字节加int x的4字节因为对齐后A子对象占16字节。所以pb和C对象起始地址不相等输出0。第三问dynamic_castB*(pa)。pa虽然声明为A*但实际指向C对象运行时类型信息知道这是一个CC又确实继承自B所以转换成功返回有效指针。这不叫交叉转换这是向真实类型的另一个基类转换。真正的交叉转换是指把B转成A那个在不相关的继承分支之间才可能失败。第四问delete pb。这个是最阴险的因为B的析构函数在代码里没写看起来是编译器默认生成的非虚析构。通过B*删除一个C对象而B的析构不是virtual属于未定义行为。常见的结果是只调用B::~B和A::~A完全不调用C的析构逻辑导致C::z这种成员资源泄漏。正确写法是给A和B都加virtual ~A() {}这样的虚析构这样delete pb才会触发从C::~C开始的完整析构链。1.3 这道题背后的工程意义存储系统到处是对象生命周期管理我工作中第无数次体会到这道题的用意。存储系统里缓存对象的生命周期管理、内存池中对象析构时资源的释放稍微不小心就会踩到非虚析构的坑。比如之前一个项目里写了一个ObjectCache基类派生出KVObject和BlobObject结果基类析构忘了加virtual在线清理缓存时每隔几天就内存泄漏一次排查了很久才定位到是析构链断裂。实话说笔试踩过的坑工作里加倍还回来是常见现象。C的内存模型尤其多继承下指针偏移和虚函数分派不是面试八股是理解对象序列化、内存池分配和高效缓存管理的基础。建议把这类题当作一个索引去深挖编译器是如何实现虚函数表分派、RTTI在内存里是怎么存的、指针调整thunk在多继承里做了什么。2. 虚拟内存换算题多级页表到底省在哪2.1 题目场景32位系统下的页表开销计算这套题里有一道操作系统题考察两级页表的地址翻译原题大意是某32位系统页面大小4KB虚拟地址空间4GB每个页表项占用4字节。若采用单级页表页表需要占多少内存为什么引入两级页表两级页表下一个进程最多需要多少页表页这道题是虚拟内存的送分题但答好的不多因为很多人只会背公式不理解页表按需分配的本质。先看单级页表。4GB虚拟空间除以4KB页面共有2^20个虚拟页每个页表项4字节一张页表就是4MB。每个进程都要维护一张专属页表那100个进程就是400MB光页表就能撑爆内存。所以单级页表在32位系统下不可行这是引入多级页表的直接动因。两级页表结构4GB空间分成2^10个一级页表项页目录项每个一级页表项指向一张二级页表。一张二级页表覆盖4MB空间有2^10个页表项。算下来页目录占一页4KB二级页表按需分配——进程真正用到的虚拟地址区间才分配对应的二级页表页。极端情况下全部4GB都被使用需要2^101024张二级页表加页目录总共1025个物理页约4MB多一点和单级完全使用时的开销一样。但实际进程不可能占满整个4GB通常只用几十到几百MB对应的二级页表页只有十几个到上百个内存开销就远小于4MB了。2.2 为什么按需分配是核心多级页表省内存本质上是利用局部性原理把页表本身的分配也做成懒加载用不到的地址空间不建立映射。这在工程上的类比非常直观就像一个公司不会提前给每个可能的员工都配好工位只有实际入职的人才会领办公设备和门禁权限。如果题目追问64位系统下为什么不无限增加页表层级因为访问内存的次数变多了。一级页表查一次、二级查一次、拿到物理页号还要再访问一次页表项每次访问都可能是一次内存随机访问三级页表意味着一次地址翻译最多需要4次内存访问3次查表1次取数据。这就是为什么CPU引入了TLBTranslation Lookaside Buffer来缓存最近使用的页表项把代价降到最低。那时候有个追加题问TLB miss和page fault的区别其实就是在考察这条逻辑链。2.3 页表题对存储工程师的价值做分布式存储CPU缓存行对齐、内存池管理、大块内存映射这些都要理解内存子系统的工作方式。比如我们做RocksDB的BlockCache为什么用指针而不是完整对象做索引因为页表映射最小粒度是页一个完整对象可能横跨多个页访问时TLB miss率更高指针访问则天然对齐。这种细枝末节很多时候就是靠当年那套页表题建立的感觉。我复习虚拟内存时常用的方法是手算一遍不同页面大小下的页表开销然后画一张不同工作负载下TLB miss率的对比图笔试只考公式面试却可能让你现场估算一个系统在4K和2M大页下的性能差异。2M大页的优点页表层级减少、TLB覆盖范围变大缺点内存碎片化、分配不灵活。这些都属于从会做题到会选型的进阶存储系统里很看重。3. 缓存替换策略一道LRU手写题背后的工程化思维3.1 题目给一个页面访问序列算缺页次数这道题给了一个具体的页面访问序列我回忆大概是序列1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 缓存容量4页分别用FIFO、LRU、OPT最优置换计算缺页次数。我当年死记硬背的答案是FIFO缺9次、LRU缺8次、OPT缺6次。大概推演一下FIFO按进入顺序淘汰1,2,3,4装入4次缺页访问1、2命中访问5淘汰11次缺页访问1淘汰21次缺页访问2淘汰31次缺页访问3淘汰41次缺页访问4淘汰51次缺页访问5命中。总缺页4111119。LRU按最近最少使用淘汰1,2,3,4装入4次缺页访问1、2命中访问5淘汰最久没用的31次缺页访问1、2命中访问3淘汰最久没用的41次缺页访问4淘汰最久没用的51次缺页访问5淘汰最久没用的11次缺页。总缺页41117这里要仔细算其实我当年在这个例子上记忆有偏差实际LRU在这个序列上的缺页次数可能是7而不是8。这道题我被卡了一下关键是表要一步步画不能只看结论。OPT是理论最优淘汰未来最长时间不会使用的页面1,2,3,4装入4次缺页1、2命中5要到的最晚淘汰31次缺页之后1、2命中3淘汰41次缺页4淘汰51次缺页5命中。总缺页也是7这样算下来是7可我记忆中的结论是6大概率是访问序列细节被我记错了但思路和方法是对的。所以在写这篇的时候我不打算给最终数字下死结论更重要的是把各种策略的机制和代码讲透。3.2 手写LRU为什么必须是哈希表加双向链表真正的技术难点是第三问手写一个线程不安全的LRU缓存要求get和put都是O(1)。正确设计是哈希表存key到链表节点的映射链表节点存key-value。get时若命中把对应节点摘下来挪到链表头部put时若key存在就更新值并挪到头部若不存在则插入头部如果容量超了就删除尾部节点并同步删掉哈希表里的key。#include list #include unordered_map using namespace std; class LRUCache { int capacity_; listpairint, int lru_; // front是最近使用back是最久未使用 unordered_mapint, listpairint, int::iterator map_; public: LRUCache(int capacity) : capacity_(capacity) {} int get(int key) { auto it map_.find(key); if (it map_.end()) return -1; lru_.splice(lru_.begin(), lru_, it-second); return it-second-second; } void put(int key, int value) { auto it map_.find(key); if (it ! map_.end()) { it-second-second value; lru_.splice(lru_.begin(), lru_, it-second); return; } if ((int)lru_.size() capacity_) { auto back lru_.back(); map_.erase(back.first); lru_.pop_back(); } lru_.emplace_front(key, value); map_[key] lru_.begin(); } };这里最需要理解的是list::splice为什么是O(1)它只需要调整指针不需要复制元素也不用重新分配内存。哈希表存迭代器而不是存节点指针是因为list迭代器就是指向节点的指针不会被失效除了删除节点本身。很多人第一次写会在链表节点里额外存key实际上哈希表迭代器里能拿到节点节点里必须存key因为淘汰时需要从哈希表里删除对应key没有key就没法定位哈希表条目。面试时有一个特别好的加分项主动指出这个实现线程不安全如果要并发访问需要加锁或者做分片锁甚至可以用std::shared_mutex做读写锁分离。这体现了你不仅会写教科书代码还考虑到了真实系统的并发问题。3.3 为什么存储系统需要比教科书LRU更复杂的东西教科书LRU的问题在于一次循环扫描就足以把缓存全部刷新一遍把真正频繁访问的数据全部挤出去。MySQL的InnoDB Buffer Pool用的是改进版LRU分成young区和old区默认比例5:3新读取的页面先进入old区头部只有在old区存活超过一定时间再次被访问才晋升到young区。目的就是防止全表扫描污染热数据。RocksDB的BlockCache分了两层LRU热点层和压缩块层策略细节更多。所以笔试题里LRU只是起点面试官期望你能讲出LRU的局限性以及从LRU到ARCAdaptive Replacement Cache、从LRU到2Q等算法演进的动机。理解了这些才算真正达到了这套题背后想考的工程化思维。4. B树与LSM-Tree存储引擎的十字路口4.1 笔试里的索引结构题那套题出了一道选择题某个存储引擎需要支持高并发写入和范围查询在B树和LSM-Tree之间应该选哪个简述理由。懂行的都知道这不是一个非黑即白的题目但出题人考察的是你对两种主流索引结构优劣势的基本判断。我从做题和后来接触实际系统两个角度拆一下。B树InnoDB数据按key有序存放在叶子节点叶子之间用链表相连支持高效的范围查询和等值查询。写入时直接定位到叶子节点但可能触发节点分裂和页写放大随机写性能一般在SSD上尤其如此。因为叶子节点默认16KB一次随机写往往要重写整个页即使只改了其中一个key。LSM-TreeLevelDB/RocksDB/HBase写入先到内存中的MemTable跳表结构积累到一定大小后刷成不可变的SSTable文件后台通过compaction不断合并整理。顺序写为主写入吞吐极高但在读取时需要从多个层级查可能产生读放大compaction会占用CPU和磁盘IO产生写放大同时空间放大也比较明显。范围查询因为SSTable内部有序、文件间有序也可以做但比B树复杂一些需要多路归并。所以这道题的标准答法是如果业务是读多写少、需要稳定低延迟的范围查询选B树如果业务是写多读少、接受一定程度的读延迟波动选LSM-Tree。高并发写入和范围查询同时要求很高现实世界里两者都会做取舍。4.2 我在笔试现场的犹豫和复盘说实话当年做题时我在这道选择题上犹豫了很长时间因为题目是单选但实际两者都能满足高并发写入和范围查询的部分需求。后来复盘出题人想要的是你看出平衡点在哪并且能说清楚取舍逻辑而不是背一个结论。笔试现场我选了LSM-Tree因为凭直觉感觉高并发写入优先后来在面试追问中承认了B树在范围查询上的优势面试官才点头。这个经历给我的启发是这类题不需要给出完美答案但要展示完整的思考框架。回答时建议从三个维度展开写入模式随机还是顺序、读特征点查还是范围、容忍延迟多少、硬件环境SSD还是HDD。这三个维度一摆选型逻辑自然出来答案也就有了说服力。4.3 存储引擎设计里的放大效应辨析B树和LSM-Tree的对比本质上比对的是三种放大效应写放大实际写入磁盘的数据量 / 应用写入的数据量。B树随机写时页重写严重LSM-Tree虽然顺序写但compaction会反复合并数据写放大可能更高。读放大实际读取磁盘的数据量 / 应用请求的数据量。B树一次点查定位叶子节点可能只需要几次IOLSM-Tree可能要查MemTable、L0的多个SSTable再逐层向下读放大明显。空间放大磁盘上实际占用的空间 / 有效数据大小。LSM-Tree上层SSTable包含大量冗余数据没被compaction收掉之前空间放大可以到好几倍。笔试题目不会让你算这些数字但面试官可能抓住LSM-Tree会不会越来越慢继续深挖。我可以给一个实际的参考数值RocksDB的默认compaction策略里配置合理的情况下写放大在10-30之间读放大会相对高一些而InnoDB的写放大通常在个位数但随机写场景下放大可能更集中在页级别。这些数字不需要背明白任何实现都是放大效应之间的权衡才是核心。4.4 后来我在实际项目里做的取舍工作后我参与过一个类KV存储的项目最开始用的是B树存储引擎结果压测时写吞吐不达标换成了RocksDB写入性能立刻上来了。但上线后观察发现低频范围查询的延迟偶尔会飙到几十毫秒——不是因为RocksDB不行而是因为某个层级的SSTable过多、compaction触发时机不佳。最后我们是调整了level_compaction_dynamic_level_bytes把分层大小设计成阶梯式才把读放大压下来。这就是笔试和实际的差别笔试考察你认识工具实际考察你用好工具。但反过来没有笔试里对B树和LSM-Tree核心差异的理解线上问题出现时你可能连调优方向都找不到。5. TCP拥塞控制应用题快速重传与超时重传后cwnd怎么变5.1 题意一个TCP连接进入拥塞避免阶段之后题目给了一个场景某TCP连接的拥塞窗口cwnd已经增长到16个MSSssthresh为20。此时连续收到3个重复的ACK接着又发生了一次超时重传。问经过这两次事件之后cwnd和ssthresh分别变成多少这个题网上各种版本的答案都有关键看考的是标准TCP Reno还是带快速恢复的TCP NewReno以及收到3个重复ACK之后到底走不走到快速重传还是继续干等超时。标准TCP Reno的流程收到3个重复ACK说明网络可能拥塞但还没完全断进入快速恢复ssthresh cwnd/2 8cwnd ssthresh 3 11加3是因为3个重复ACK已经确认了3个包。之后如果重传的包被确认了cwnd ssthresh 8。再之后如果发生超时说明网络状况更差了ssthresh cwnd/2 4cwnd 1重新开始慢启动。所以经过两次事件之后的结果是ssthresh4cwnd1同时进入慢启动阶段。但很多笔试题的简化版本会忽略快速恢复期间cwnd的增加直接按收到3个重复ACK后cwnd减半ssthresh减半来算那结果就是第一次减半后cwnd8、ssthresh8再超时后cwnd1、ssthresh4。所以这类题考的不是复杂计算而是拥塞控制的几个关键机制慢启动、拥塞避免、快速重传、快速恢复以及它们对cwnd的不同处理方式。5.2 不少人的误区把3个重复ACK理解成必须重传当年一起复习的同学有人以为收到重复ACK之后就要进入超时重传这一下就把整个链条算错了。重复ACK的含义是接收端已经收到了后续数据包的乱序到达才会接连发出相同ACK序号。它和超时重传的区别在于前者还有部分包在传输中所以网络不至于全断可以通过快速重传快速恢复及时补救后者则是长时间没有收到任何ACK说明链路可能严重拥塞甚至断开必须从严处理回到慢启动。为了把这个机制讲透可以模拟一个简单的发送窗口轨迹慢启动阶段cwnd从1开始每收到一个ACK加倍增长1、2、4、8...直到到达ssthresh转入线性增长。拥塞避免阶段每个RTT只增加1个MSS。收到3个重复ACK减半并进入快速恢复用重复ACK计数来虚拟增加cwnd维持管道不空。超时ssthresh减半、cwnd归1重新慢启动。存储系统为什么特别看重这个因为分布式存储里节点间数据同步和副本复制都依赖TCP传输网络抖动直接决定吞吐和延迟。写一篇存储相关的性能诊断报告必须能根据日志里的重复ACK重传率RTO时长快速判断是网络层拥塞还是应用层瓶颈。这套TCP知识不是网工的专属存储工程师同样要懂。5.3 实战中如何验证和理解这些机制笔试只考数学推导但如果你真想在面试中出彩最好能说出在Linux下怎么观测这些指标。常用手段是ss -o state established查看定时器netstat -s统计重传用tcpdump抓包配合Wireshark的TCP Stream Graph看一下cwnd和RTT的逐包变化。甚至可以主动做一次100ms延迟0.1%丢包的网络模拟实验观察在iperf里吞吐的变化曲线跟理论对比。我当时复习到这里时做了个小实验在一台云主机上用tc netem加丢包然后再开一个iperf流观察Reno下的通过率确实发现重传频繁后吞吐呈锯齿状波动。这个实验花了两小时但比抱着书看十遍更有效因为你会直观感受到超时重传带来的断崖式下降。后来面试官问到这个细节的时候我直接说了我看到吞吐曲线从接近线速掉到几乎为0再慢慢爬升这个现象面试官明显感兴趣了很多。6. 备考复盘这套题透露的复习优先级6.1 从考点分布看百度存储研发的用人偏好整套题做完我最大的感受是它不考偏题怪题考的几乎全是存储系统日常工作中必须反复用到的底层机制。把考点梳理成一张表考点核心技能在存储系统中的对应场景C虚函数/内存布局对象生命周期管理缓存对象、内存池、序列化虚拟内存/多级页表内存分层理解大块内存映射、操作系统的内存分配缓存替换/手写LRU热点数据管理块缓存、元数据缓存B树/LSM-Tree索引结构选型关系型和KV存储引擎TCP拥塞控制网络传输理解副本同步、数据迁移、RPC传输这张表几乎就是分布式存储工程师的能力地图。对比一下如果我只刷LeetCode而不补这些系统知识大概率会在第二三轮挂掉因为算法题可以通过短时间刷题速成但这些基础机制需要真正理解才能答出深度。6.2 我的复习方法以真题为锚点建立知识树我复习时没有逐个找标准答案背而是针对每道题去拆它考了哪个领域、可能衍生出哪些追问、工程里对应什么场景。然后围绕每一个点去查资料、做实验、手写代码。以LRU为例真题只要求手写哈希表双向链表但我额外去了解了InnoDB的LRU变体、Linux内核的LRU的per-CPU页表结构、Redis的LRU近似实现。每次深入都会让原来的知识点更立体面对面试官如果我让你设计一个XX缓存你怎么做这类开放题时就不再慌。同时要强调基础知识的深度远重要于广度。你能把B树和LSM-Tree的差异讲清楚比列举十个数据库系统的名字要有价值得多。面试官是能看穿一个人是不是背概念的关键指标是你能不能用10分钟把一个概念从原理讲到工程权衡再讲到场景选型。6.3 给后来者的具体建议笔试准备不要晚于8月至少提前3个月系统过一遍计算机基础四件套操作系统、计算机网络、数据结构、计算机组成原理刷题每天保持手感。C方向的重点不只是语法更要看对象模型、内存管理、模板元编程、STL容器实现。推荐《深度探索C对象模型》配合《Effective C》精读。操作系统部分重点在进程/线程、虚拟内存、文件系统、IO模型尤其是IO模型select、poll、epoll都要能画出流程图。存储方向的加分项是了解一个现成存储引擎的源码比如RocksDB的WriteBatch和LevelDB的MemTable不要求全懂但要在面试时让对方觉得你真的碰过代码。不要猜题不要为了压中原题去搜集大量真题而是要有一套知识框架去应对任何角度的问题。我想起当时一起备考的一个朋友他把能找到的所有题库都刷了一遍但遇到给你一个分布式KV你会怎么监控它的性能这种开放题时依然卡壳。因为这个问题没有标准答案它考的是你在真实系统里排查问题的能力。这种能力只能靠理解底层原理动手实验慢慢积累刷题是刷不出来的。如果你现在正为这套题发愁我的建议是把它当作一面镜子而不是一把尺子——用它照出自己在哪些基础模块上还有缺口然后带着问题去补而不是带着焦虑去背。等你在工作中真的处理过内存泄漏、做过冷热数据分层、调过存储引擎的compaction参数之后再回头翻这套题会发现每一道题都变得格外亲切。