上周有个朋友去面微软被问到了一道经典的智力题。那道题有名有姓叫 100 Prisoners in Solitary Cells在微软官方面试题列表里排得上前十。前面刚聊完 Paxos 和分布式共识面试官话锋一转说给你出道智力题。题目是这样的。100个囚徒关在100个单人牢房里互相之间不能通信。监狱里有一个特殊的房间里面只有一个灯泡一个开关。每天狱卒会随机选一个囚徒去这个房间。囚徒进去之后可以开灯也可以关灯也可以什么都不做。囚徒在被关进牢房之前可以聚在一起商量一次策略。之后再也不能见面不能传纸条不能敲墙什么都干不了。只有一种情况他们可以离开这个房间时做出一个声明所有100个囚徒都至少来过这个房间一次。如果声明正确所有人释放。如果错误所有人处死。问你能设计一个策略确保一定能安全释放他当场就说不可能。面试官笑了笑为什么不可能他说没有通信没有记忆随机选择你怎么可能知道谁去过谁没去过你被选100次也没法确定别人被选过。面试官说你再想想。灯泡是什么他愣住了。为什么这道题看起来不可能你先停下来想一想为什么他会觉得不可能。囚徒面临的核心困境是没有任何直接的通信渠道。不能说话不能写信不能碰面。你进了房间出来之后没有任何方式告诉别人我来过了。没有任何共享记忆。囚徒自己可以记住我来过几次但没法记住别人来过几次。选择是完全随机的。同一个囚徒可能被选1次也可能被选1000次。你不能用访问次数来推断是否所有人都来过。所以直觉告诉你这个问题无解。但面试官给了提示。灯泡是什么灯泡就是通信他后来跟我说面试官这句话点醒了他。灯泡不是一个装饰品。灯泡是一个共享的、持久化的、可读写的状态。它只有两个状态亮ON和灭OFF。但这两个状态就是1个 bit 的信息。1个 bit 听起来很少。但对于100个互不相通的囚徒来说这个 bit 就是他们之间唯一的通信桥梁。上一个囚徒离开房间时灯是亮的下一个进来的囚徒就能看到。上一个囚徒把灯关了下一个进来的也能看到。这不就是 Redis 吗Redis 就是一个所有服务共享的内存状态。服务 A 写入一个 key服务 B 读到这个 key两个服务就完成了一次通信。它们之间不需要直连不需要 RPC共享状态就是通信。灯泡就是一个只有1个 key、value 只有 0 或 1 的 Redis。现在问题变成了如何用1个 bit 的共享状态让100个互不相通的节点达成共识从最小的 case 开始好现在我们知道灯泡是通信渠道了。但1个 bit 怎么用老规矩从最简单的情况开始推。2个囚徒1个灯泡。囚徒 A 和囚徒 B。策略很简单指定 A 为计数者Counter。囚徒 B 的任务进房间时如果灯是灭的并且自己还没开过灯就把灯打开。开过一次之后以后再也不碰开关。囚徒 A 的任务进房间时如果灯是亮的就把灯关掉并且计数 1。执行过程B 进房间灯是灭的B 把灯打开。A 进房间灯是亮的A 把灯关掉计数 1。计数 1 2 - 1 1A 宣布所有人都来过了。完美。2个囚徒Counter 只需要等1个信号2个人减去 Counter 自己计数到1搞定。但等一下。如果顺序反过来呢A 先进房间灯是灭的A 什么都不做计数 0。B 进房间灯是灭的B 把灯打开。A 再进房间灯是亮的A 关灯计数 1。也没问题。只要 B 开过一次灯A 迟早会收到这个信号。3个囚徒1个灯泡。指定 A 为计数者。B 和 C 各自只需要开灯一次。但这里出现了一个关键问题。假设 B 进房间灯是灭的B 把灯打开。然后 C 进房间灯是亮的。C 怎么办C 还没开过灯但灯已经是亮的了。C 能不能把灯关掉再打开不能——因为如果 C 把灯关了A 进来看到灯是灭的就会以为还没人开过灯C 的信号就丢了。所以 C 什么都做不了。C 只能等下一次进来时灯碰巧是灭的才能开灯。这就是单 bit 缓冲区的局限缓冲区大小为1同一时间只能容纳1个信号。如果灯已经是亮的有1个待处理的信号后来的囚徒只能等。但没关系。因为B 开了灯。A 进来看到灯亮关灯计数 1。C 进来灯是灭的C 开灯。A 进来看到灯亮关灯计数 2。计数 2 3 - 1 2A 宣布所有人都来过了。3个囚徒2个信号计数到2搞定。协议的核心3条规则推到这里你大概已经看到规律了。我们把策略总结成3条规则规则1选出一个计数者。100个囚徒中指定1个人作为 Counter其余99个人是 Signaler。规则2Signaler 的行为——只开一次灯。每次 Signaler 进房间时如果灯是灭的OFF并且自己还没开过灯就把灯打开ON标记自己已发送信号。如果灯是亮的ON什么都不做。如果自己已经开过灯了以后再也不碰开关。规则3Counter 的行为——关灯 计数。每次 Counter 进房间时如果灯是亮的ON把灯关掉OFF计数 1。如果灯是灭的OFF什么都不做。当计数达到 99Counter 宣布所有人都来过了。就这么简单。3条规则一个1 bit 的Redis100个互不相通的囚徒共识达成。为什么只开一次灯是关键这个协议里最精妙的设计是 Signaler 只开一次灯。为什么不能开多次假设囚徒 B 每次进来都开灯。那么 Counter 怎么区分这是 B 第一次开的灯还是B 第10次开的灯没法区分。因为灯只有1个 bit它不携带谁开的和开了几次的信息。如果允许重复开灯信号就不可控了。Counter 永远不知道自己数到99的时候到底是99个不同的人开的灯还是同一个人开了99次。只开一次灯这条规则把一个不确定的、可能无限重复的信号变成了一个确定的、恰好发生1次的信号。用分布式系统的话说这是一个幂等操作Idempotent Operation。每个 Signaler 的操作是幂等的——不管你调用多少次效果只有1次。Counter 的计数才是精确的。这跟支付幂等性的设计一模一样。你设计一个支付接口同一个订单号不管被调用多少次只扣款一次。不是靠聪明的判断实现的是靠幂等设计保证的。幂等不是一种能力是一种约束。你主动约束自己只做一次系统才能正确计数。为什么需要一个 Counter你可能会想能不能不用 Counter每个人自己计数行不行不行。因为灯只有1个 bit。如果每个人都去碰开关这个 bit 就会变成一堆人的写入竞争——你刚关了他马上又开了另一个又关了……信息全乱了。1个 bit 的共享状态同一时间只能有1个写入者。这就是为什么必须指定一个 Counter。Counter 是唯一的消费者。Signaler 是生产者。灯泡是一个大小为1的缓冲队列。生产者Signaler往队列里放消息开灯消费者Counter从队列里取消息关灯 计数队列满了灯亮着的时候生产者等着队列空了灯灭着的时候消费者等着这就是经典的生产者-消费者模式Producer-Consumer Pattern。只不过这个队列的容量只有1。在真实的后端系统里Kafka 的消费者就是一个 CounterRedis 的 BLPOP 就是消费者从队列里取消息Raft 的 Leader 就是那个被指定的 Counter完整推演3个囚徒的完整流程为了让你完全理解我把3个囚徒的情况从头到尾推一遍包括所有可能的情况。假设灯初始状态为灭OFFA 是 CounterB 和 C 是 Signalers。理想情况访问者灯状态动作计数BOFF开灯第1次0AON关灯计数11COFF开灯第1次1AON关灯计数12--计数2(3-1)A宣布2如果 C 先于 B 进来呢访问者灯状态动作计数COFF开灯第1次0BON什么都不做灯已亮等待0AON关灯计数11BOFF开灯第1次1AON关灯计数12--计数2(3-1)A宣布2注意看第2行。B 进来时灯是亮的B 什么都做不了。但没关系——B 记住了我还没开过灯。等 A 把灯关了之后B 下次进来就能开了。如果 A 被连续选中很多次呢访问者灯状态动作计数AOFF什么都不做0AOFF什么都不做0AOFF什么都不做0BOFF开灯第1次0AON关灯计数11COFF开灯第1次1AON关灯,计数12--计数2(3-1)A宣布2A 连续进来3次灯是灭的什么也做不了。浪费了3次访问。但协议依然正确——只是慢了一点。这就是分布式系统里说的最终一致性Eventual Consistency不保证每一步都快但保证最终一定对。放大到100个囚徒逻辑完全一样。从3到100只是计数目标从2变成99。100个囚徒1个 Counter计数目标是 99。99个 Signalers每人只开灯一次。Counter 每次进房间发现灯亮关灯 计数 1。计数到 99宣布释放。为什么一定是 99 而不是 100因为 Counter 自己也是100人之一他不需要给自己发信号。他只需要确认其余99人都来过。99 个信号99 次关灯计数1 次宣布100 人释放。这套协议是绝对正确的。为什么因为每个 Signaler 只开灯一次。所以灯被打开的总次数恰好等于已经来过且已经发送过信号的 Signaler 数量。Counter 每次关灯就代表收到了1个新的信号。当计数到99意味着99个 Signaler 都至少来过一次。不存在误判的可能。没有可能来过和确定来过的模糊地带。99就是99一个不多一个不少。一个更尖锐的问题要等多久协议是正确的但代价呢100个囚徒每天选1个Counter 需要收集99个信号。每个信号的传递过程是Signaler 进房间发现灯灭开灯。Counter 进房间发现灯亮关灯计数1。问题在于Counter 被选中的概率只有 1/100。也就是说Counter 平均每100天才能进一次房间。99个信号每个信号平均要等100天让 Counter 来收集光 Counter 的等待时间就是 99 × 100 9900 天。再加上 Signaler 等待灯灭的时间早期还有很多人没发信号等待较短后期只剩少数人没发信号等待变长总体期望时间大约是100 × H₉₉ 100 × 99 ≈ 518 9900 ≈ 10418 天H₉₉ 是第99个调和数约等于5.18。总期望大约1万天接近30年。是的你没看错。用1个 bit 做通信100个囚徒要等30年才能释放。但这是期望值。运气好的话可能十几年运气差的话可能四五十年。关键是不管多久协议保证一定能释放。这就是1个 bit 的代价。你想要更快的共识那就得增加通信带宽。2个 bit速度提升一倍。100个 bit速度大幅提升。这就是为什么分布式系统需要网络——带宽越大共识越快。这道题到底在考什么到这里答案已经清楚了。但面试官真正想看的不是你能不能背出这个答案。这道题考的是三层能力第一层你能不能看出灯泡是通信。大部分人卡在这一层。觉得没有通信就是真的没有通信。但灯泡是一个持久化的共享状态它就是通信渠道。在工程世界里这对应的是你能不能看出共享数据库就是通信、共享文件系统就是通信、消息队列就是通信。很多开发者天天用 Redis、用 Kafka但没意识到这些工具的本质就是共享状态就是节点间的通信桥梁。第二层你能不能设计正确的协议。看出灯泡是通信还不够你还得设计一个不会出错的协议。只开一次灯这个约束是整个协议的正确性基石。在工程世界里这对应的是你能不能设计幂等接口。你的支付接口能不能保证同一订单不重复扣款你的消息消费者能不能保证不重复处理你的分布式锁能不能保证不重复获取第三层你能不能看到系统瓶颈。协议正确了但 Counter 是单点瓶颈。99个信号都要经过1个人收集时间复杂度是 O(n²)。在工程世界里这对应的是你能不能看到单 Leader 架构的吞吐瓶颈。Raft 的 Leader 承担所有写入当节点数量增加Leader 的压力线性增长。怎么破分片、多 Leader、无 Leader 架构Dynamo 风格……面试官用一道智力题把分布式共识的核心问题全考了。从囚徒到分布式系统硬核映射这道题的每一步都能在真实的分布式系统里找到对应1. 灯泡 共享存储灯泡是一个所有囚徒都能访问的、持久化的、1 bit 的共享状态。在工程世界里Redis 就是多服务共享的内存状态ZooKeeper 就是分布式协调的共享配置数据库就是多应用共享的持久化存储2. 指定 Counter 领导者选举Leader Election为什么必须指定一个 Counter因为1个 bit 的状态只能有1个写入者。多个写入者会互相覆盖。在工程世界里Raft 通过超时选举选出 LeaderPaxos 通过 Proposer 竞选选出唯一的提案者Kubernetes 通过 Lease 机制确保同一时刻只有一个活跃的控制器3. 只开一次灯 幂等操作Idempotency每个 Signaler 只开灯一次保证 Counter 的计数是精确的。在工程世界里支付接口用订单号做幂等键同一订单只扣款一次消息消费者用消息ID做去重同一消息只处理一次分布式锁用 lease token同一 token 只获取一次锁4. Counter 关灯计数 消费者消费消息Counter 是消费者灯泡是消息队列容量为1Signaler 是生产者。在工程世界里Kafka 消费者从分区拉取消息ack 后 offset 前移RabbitMQ 消费者 ack 后消息从队列删除这道题里Counter ack 的方式就是关灯5. 计数到99 两阶段提交的全部ACK2PCCounter 需要99个信号才能宣布这相当于2PC中协调者需要所有参与者都回复YES才能提交。在工程世界里2PC两阶段提交的协调者需要所有参与者ACK分布式事务的Saga模式需要所有补偿操作完成这道题要求100%确认不是多数派是全确认6. O(n²) 等待时间 单Leader吞吐瓶颈Counter 是唯一的消息消费者所有信号必须经过它。节点数增加等待时间平方级增长。在工程世界里Raft 单Leader的写入吞吐量受限于Leader的处理能力MySQL主从复制的写入瓶颈在主库解决方案分片、多副本并行、增加缓冲区大小一个容易忽略的细节灯的初始状态面试官可能会追问你一个问题如果灯的初始状态不确定呢可能亮也可能灭。这会引入一个微妙的问题如果灯初始就是亮的Counter 第一次进来关灯计数1但这个信号不是任何 Signaler 发的——计数虚高了1。解决方案有几种方案1Counter 第一次进房间时如果灯是亮的关掉但不计数。牺牲一次访问来消除初始状态的不确定性。方案2每个 Signaler 开灯两次。Counter 计数到 19899 × 2这样即使初始灯亮导致多计1次最终也能达到198。代价是等待时间翻倍。方案3在商量策略时约定假设灯初始为灭。如果实际不确定方案1最稳。这种细节在工程世界里叫做初始化问题。你的系统启动时共享状态的初始值是什么是0还是上次崩溃前的残留值这直接关系到系统的正确性。Redis 的 RDB/AOF 持久化、Raft 的日志持久化、ZooKeeper 的 snapshot都在解决这个问题怎么确保系统重启后的初始状态是确定的。面试时的回答策略如果你在面试中遇到这道题别急着说不可能。正确的回答路径是这样的第一步确认问题边界。囚徒之前能商量一次策略灯的初始状态是亮还是灭囚徒能不能记住自己的历史行为确认了边界你才知道协议设计的约束条件。第二步从最小 case 开始推。我先考虑2个囚徒的情况。1个 Counter1个 Signaler。Signaler 开灯一次Counter 关灯计数。从小 case 开始推面试官就知道你有工程师的思维——先写 base case再找规律。第三步提出完整协议。3条规则选1个 CounterSignaler 只开灯一次Counter 关灯计数到 n-1 时宣布。第四步分析正确性。为什么一定对因为每个 Signaler 只开灯一次所以 Counter 收到的信号数恰好等于已访问的 Signaler 数。不存在误判。第五步分析代价。时间复杂度 O(n²)因为 Counter 的访问概率是 1/n收集 n-1 个信号平均需要 n×(n-1) 次访问。瓶颈在于 Counter 是单点。第六步谈工程映射。这个模型对应分布式系统的共识协议灯泡是共享存储Counter 是 Leader幂等操作保证计数精确单Leader是吞吐瓶颈。这六步走下来面试官就知道你不只是知道答案而是真正理解了问题背后的系统设计思想。这道题最深的一层最后说一个我自己推完这道题之后的感受。这道题最反直觉的地方不是灯泡是通信——这个稍微想想就能理解。最反直觉的是囚徒不需要聪明。他们不需要推理、不需要猜测、不需要做任何复杂的判断。Signaler 只需要记住我开过灯没有Counter 只需要记住我数到几了。每个人只做一件极其简单的事。但就是这些不聪明的个体通过一个设计良好的协议达成了100%正确的共识。这就是分布式系统的核心思想协议设计大于个体智能。Paxos 看起来复杂但每个节点只需要做几件简单的事提案、承诺、接受。Raft 看起来精巧但每个节点只需要做三件事请求投票、追加日志、应用状态机。不是节点聪明是协议聪明。在工程世界里你设计一个微服务架构最重要的不是让每个服务变得多智能而是设计一套协议让一堆笨服务能正确协作消息队列保证 at-least-once 传递消费者负责幂等去重服务注册中心保证最终一致客户端负责重试和熔断分布式锁保证互斥业务层负责超时和续约你的系统有多可靠不取决于单个服务有多强取决于协议有多好。100个囚徒用1个灯泡达成了共识不是因为他们聪明是因为协议足够好。回到我那个朋友。他最后想出了灯泡是通信但没想出只开一次灯的幂等设计。面试官说思路对了让他回去再想想完整协议。他最后还是没拿到那个 offer。但他说出来之后跟我说了一句话我觉得特别到位以前我觉得分布式系统最难的是算法现在发现最难的是设计约束。不是你想做什么而是你约束自己不做什么。只开一次灯就是约束。不重复扣款就是约束。Leader 只有一个就是约束。约束不是限制约束是正确性的保证。