守株阁

“微秒级”“简洁区块链”“异步BFT”不是三档性能套餐。NOPaxos把排序能力下沉到网络设备，以特殊网络原语缩短崩溃容错快路径；Streamlet用epoch、leader和公证链给出易讲清的拜占庭共识；HoneyBadgerBFT用随机化和密码学组件在异步网络中获得概率活性。它们改变的是系统模型，不能只按吞吐或延迟排成一条榜单。 分布式系统（E04）：Lambda 与 SkyPilot 的执行和调度边界 比较协议前先固定四个条件 至少要写清网络时序、故障类型、成员/身份和完成定义。一个协议的“快”可能依赖可编程交换机；另一个协议的“活”可能只承诺概率1最终完成；BFT证书还依赖认证密钥没有被正确节点滥用。 flowchart LR P[协议主张] --> N[网络模型] P --> F[故障模型] P --> I[身份/密码学] P --> C[完成与测量口径] N --> J[可比较结论] F --> J I --> J C --> J NOPaxos：网络排序换掉一部分协议工作 NOPaxos...

AWS Lambda和SkyPilot都能“把任务放到云上跑”，但它们调度的单位不同。Lambda围绕一次函数调用管理执行环境、扩缩容和事件重试；SkyPilot围绕带资源需求的批任务或服务，在多个云和区域间选择资源并管理集群生命周期。前者隐藏机器，后者显式优化机器放置。两者都不是共识协议，也都不会自动使外部副作用恰好一次。 分布式系统（E03）：IPFS、SUNDR 与 Bitcoin 的开放网络信任模型 四个问题决定执行形态 选择云执行方式前，需要把工作拆成四项：任务粒度、启动成本、失败后的重放边界、目标函数。短小无状态事件适合按调用扩展；需要GPU、长时训练、特定区域或跨云价格比较的作业更像资源放置问题。 flowchart TD J[工作负载] --> G{调度单位} G -->|单次事件/函数| L[Lambda式执行] G -->|任务+资源集合| S[SkyPilot式放置] L --> R[初始化、调用、重试] S --> P[选云、建集群、运行、恢复] R --> E[外部效果仍需幂...

内容寻址、fork consistency 和工作量证明都大量使用哈希，却在回答三个不同问题。IPFS先判断“拿到的字节是不是所请求的内容”；SUNDR判断“不可信服务器是否给不同客户端编造了无法再无痕合并的历史”；Bitcoin在开放成员网络里用累计工作竞争公共账本顺序。把它们统称为“去中心化保证”，会丢掉真正的信任边界。 分布式系统（E02）：GFS/HDFS 与 Bigtable/HBase 的存储架构 开放网络先问对手能做什么 E02里的NameNode、HMaster和存储节点处在一个明确管理域。开放网络则可能遇到陌生peer、恶意存储服务和Sybil身份。系统必须分别规定数据完整性、身份、发现、可用性、顺序和经济攻击成本。 flowchart TD Q[收到网络结果] --> I{要验证什么} I -->|字节是否匹配名字| C[内容寻址] I -->|服务器是否分叉历史| F[fork consistency] I -->|开放成员怎样竞争账本| W[工作量证明与链选择] C --&...

GFS 与 HDFS 面向大文件和顺序吞吐，Bigtable 与 HBase 面向按键查找的稀疏有序表。后两者把前者一类分布式文件系统当成持久层，却没有因此变成“文件系统加一层索引”。它们增加了 row range、写前日志、内存表、不可变文件和 Region 分配，故障恢复的单位也从块副本变成可服务的键范围。 本篇沿三条路径比较四个系统：控制面保存什么，用户数据经过哪里，节点失效后凭什么恢复。论文模型、当前产品文档与本地有限模型分别陈述。 分布式系统（E01）：CRDT、多主写入与收敛边界 共同骨架：元数据只负责找到数据 文件路径或 row key 先经过一个权威元数据视图，再落到保存字节的节点。元数据控制面决定命名、位置和归属；数据面承载大块内容。把两者拆开，才能让控制面保持较小状态，同时让客户端或服务节点直接传输大量数据。 flowchart LR C[客户端] --> M[元数据控制面] M -->|块位置或Region位置| C C --> D[数据节点] D --> P[复制文件块或写WAL/StoreFile] M -.不...

两个副本在断网时各自接受写入，恢复通信后还能自动合并，这是 CRDT 最吸引人的地方。它解决的却是一个比“数据库正确”更窄的问题：副本收到同一组更新后，能否得到等价状态。实时顺序、读新鲜度、跨对象唯一性和余额下界不会随“最终收敛”四个字自动出现。 本篇用状态型 PN-Counter 与 OR-Set 拆开两层判断。第一层检查乱序、重复状态传递后是否收敛；第二层检查合并结果是否仍满足应用不变量。实验会得到一个刻意刺眼的结果：两个副本逐字一致，用户名却同时属于两个用户。 分布式系统（35）：两次选择的负载均衡复现实验 系统模型决定“无冲突”的含义 设有两个正确副本 east 与 west。网络可以延迟、乱序、重复或暂时隔离消息；状态型实验假定反熵最终会把必要状态送达。副本不会伪造状态，replica id 稳定且不会被另一节点重用。一次本地更新先改变本地内存，没有磁盘持久化、进程崩溃或成员变更。 在这个模型里，“无需协调”表示本地更新不等待一个同步的全局排序点。副本仍要通信，永久丢失唯一更新也不会凭 merge 恢复。分区期间读到旧值也不违反收敛，因为副本尚未接收同一组更新。 flo...

“随机挑两台，选更空的一台”看起来只比随机分配多一次观察，却会显著降低最大负载。经典 Balanced Allocations 论文给出的结论更强：在明确的静态模型里，单选最大负载的量级约为 log n / log log n，固定 d>=2 次选择后降为 log log n / log d + O(1)，概率随规模增大趋近 1。 这项结论经常被压缩成“Power of Two Choices 总是更好”。本篇用独立研究项目检验这句话丢掉了哪些条件：先精确枚举小状态空间，再做固定种子的配对模拟，最后加入相关候选、整批陈旧快照和反向选择。结果同时包含支持主张的分布证据和推翻逐轨迹强断言的反例。 分布式系统（34）：复制 KV、分片迁移与故障恢复 研究问题先固定 实验只研究静态 balls-into-bins。m 个单位大小的 ball 依次到达，放入 n 个不会卸载的 bin。它可以代表一次性任务分配的抽象，却不包含服务完成、队列等待、节点权重或请求时延。 基线 one-choice 为每个 ball 均匀随机抽一个 bin。候选 two-choice 独立、有放回地抽两个 ...

前面的实验分别验证了复制、请求去重、分片和重配置。结课系统要回答更难的问题：这些机制放进同一个写入路径后，leader 停止、旧副本重启、迁移 worker 中途退出时，哪些状态必须一起恢复，哪些保证仍然缺失？ 本篇实现一个有界文件模型。它有两个三副本 KV 组、两分片和三份配置镜像，运行一条固定故障轨迹。模型刻意不复刻 Raft、真实网络与磁盘掉电；每项观察只证明源码中写出的有限状态转换。 分布式系统（33）：PBFT、恶意节点与信任边界 系统模型与不变量 键首字母小于 n 的属于 shard 0，其余属于 shard 1。初始配置是 shard 0 -> A@epoch1、shard 1 -> B@epoch1。A、B 各有三个副本，配置控制面也保存三份 JSON 镜像。 flowchart TB C[三份配置镜像<br/>owner + per-shard epoch] --> R[客户端路由] R -->|shard 0, epoch 1| A[A组三副本] R -->|shard 1, epoch 1| B[B组三副...

复制KV若只容忍崩溃，三副本取两票就能承受一台停机。节点一旦可以对不同接收者发送互相矛盾的消息，这个证明立即失效：两个两票集合可能只交在作恶节点上。PBFT（Practical Byzantine Fault Tolerance）增加的不只是一个副本，还包括认证消息、分阶段证书、换主证明和状态恢复规则。 分布式系统（32）：事件时间、水位线与状态恢复 同一份KV需求对应两种故障模型 需求固定为线性一致的 Put/Get、确定性状态机和最多一个故障。crash fault模型允许节点停止、重启或暂时不可达，但节点运行时仍遵守协议。三副本的两票集合至少交一个节点；交点不会为同一日志位置确认两个值，因此多数派交集有用。 Byzantine fault允许故障节点沉默、伪造自身状态、选择性转发、串谋，还能向不同接收者发送冲突消息。这样的行为称为equivocation。若沿用三副本两票阈值，故障节点B可以同时支持红值和蓝值： sequenceDiagram participant H1 as 正确副本 H1 participant B as 恶意副本 B participan...

流处理不能只问“数据到了没有”。一条记录有业务发生时间、进入系统时间和实际执行时间；乱序让三者分离，持续流又没有天然结尾。watermark负责声明事件时间推进到哪里，checkpoint负责保存恢复点，backpressure负责在下游变慢时限制上游。三个机制解决三个问题。 分布式系统（31）：Ray 的 Future、对象血缘与重试边界 事件时间把结果归到业务时间轴 processing time取算子处理记录时的墙钟，延迟低，却会被排队、重启和机器速度改变。event time取记录携带的业务时间戳；同一批输入重放时仍能落入同一窗口，更适合账单、监控和会话分析。 sequenceDiagram participant S as Source participant O as Operator S->>O: event(ts=2) S->>O: event(ts=8) S->>O: watermark(6) S->>O: event(ts=4, late) 事件时间没有免费确定性。系统不能知道网络里是否还...

Ray 把远程函数的返回值立即表示成 ObjectRef，它在概念上类似论文所称的 future。调用者可以继续把这个引用交给下游任务，不必先等待真实值，于是普通 Python 函数调用扩展成执行期间不断生长的分布式 DAG。代价也随之出现：引用、对象值、生产任务和外部副作用有不同的故障命运。 分布式系统（30）：Spark/RDD 的血缘、物化与故障重算 RDD 以数据集转换为中心；Ray 的基本节点更细，可以是一项任意远程任务及其 future。两者都能沿依赖重算，但 Ray 当前产品的对象 ownership、task retry 和 actor 规则不能直接从 RDD 类比推出。 ObjectRef 是未来值，不是结果副本 f.remote() 提交一个 task 并返回 ObjectRef。下游 task 接收引用时，Ray 记录依赖；参数值可用后，下游才具备运行条件。ray.get 把等待显式带回调用者。 flowchart LR A[f.remote → ObjectRef A] --> C[h.remote A B] B[g.remote ...