守株阁

一个容量已满的数组追加元素时，可能需要复制全部旧元素。这次操作的线性成本，与一长段追加操作具有线性总成本可以同时成立。摊还分析说明每段合法序列的总账，不要求用户随机操作，也不把昂贵调用的延迟抹掉。 第 02 篇通过求和分析递归，本篇把相同方法用于数据结构的时间序列。讨论对象是抽象动态数组：当前元素数 n、容量 C、操作序列长度 q，C 初始为 1，始终为 2 的幂。只支持末尾追加与删除；中间插删需要移动元素，不属于本篇常数摊还结论。 满时加倍的总复制成本 追加前若 n=C，就分配容量 2C 的存储，复制 n 个已有元素，然后写入新元素。一次普通追加计 1 次写入，一次扩容追加计 n+1 次。这里按存活元素复制收费，未计清零新容量的工作；若分配还需 Θ(C)\Theta(C)Θ(C) 初始化，常数会变化，总阶的论证仍需把它纳入。 从空数组开始连续追加 q 次，复制发生在容量 1、2、4、8 等时刻。设最后一次复制的旧容量为 2t<q2^t<q2t<q，总复制数为： 1+2+⋯+2t=2t+1−1<2q.1+2+\cdots+2^t=2^{t+1}-1&l...

递归程序每层写着两次调用，不意味着总成本就是“层数乘以 n”。子问题有多大、每层共有多少节点、局部工作是否包含复制，都要从实际代码得到。第 01 篇的树聚合已经给出一个反例：左右子树可以很不均衡，遍历时间仍为线性，栈深却可能为线性。 本篇只讨论确定性的最坏成本与比较模型下界。输入规模 n 为元素数，单次比较和引用移动视为单位成本；目标是推导随 n 增长的工作量，不估算墙上时间。下文递推式是被声明的成本模型，不能自动代替任意同名算法的真实实现。 均衡递归的每层账目 对二路均衡归并，设 n 为 2 的幂，边界 T(1)=c0T(1)=c_0T(1)=c0​，每个内部节点的拆分和合并总工作为 cn，c 为正的固定常数： T(n)=2T(n/2)+cn.T(n)=2T(n/2)+cn. T(n)=2T(n/2)+cn. 第 j 层有 2j2^j2j 个子问题，每个大小为 n/2jn/2^jn/2j，所以该层局部工作是 cn。内部层共有 log⁡2n\log_2 nlog2​n 层，叶子 n 个，总成本为 cnlog⁡2n+c0ncn\log_2 n+c_0ncnlog2​n+c0​n，...

二分查找在长度为 1 的数组上出错，通常不是“特殊情况太多”，而是区间含义没有统一。若把循环中的每个变量解释成一个持续成立的命题，空数组、重复值和目标缺失就能进入同一个证明。 第 00 篇定义了输入输出契约。本篇把契约连接到代码：先证明允许重复值的左边界二分，再用结构归纳证明树上聚合。输入均为有限数据，操作期间不被其他线程修改。一般性证明写在正文；有限检查由 examples/advanced-algorithms/check_foundations.py 运行。 二分查找返回的是边界 给定非降序整数数组 A，长度为 n，以及整数 x，返回最小下标 p，使得 A[p] 不小于 x。没有这样的元素时返回 n。等价地，输出要满足： 0≤p≤n,∀i<p, A[i]<x,∀i≥p, A[i]≥x.0\le p\le n,\qquad \forall i<p,\ A[i]<x,\qquad \forall i\ge p,\ A[i]\ge x. 0≤p≤n,∀i<p, A[i]<x,∀i≥p, A[i]≥x. 最后一个量词仅针对数组合法下标。数组为空...

客户端发出 Put(x, 1)，等待超时。服务端究竟有没有修改 x？只凭这条错误，无法判定。请求可能没到，也可能已经执行，只是回复没有回来。工程上需要重试、查询或人工核对，理论上需要先写清楚：哪些事件发生了，谁能观察到这些事件，协议允许哪些执行。 分布式系统的学习从这个区别开始。运行在不同进程里的代码通过消息合作，每个进程只掌握局部状态；一项业务动作可以跨越多个故障边界。正确性不能只根据正常路径上的最终输出判断。 这是系列的入口篇。验收目标是根据三个节点和客户端的时间线，区分确定发生、仍有可能和无法判定的结果；配套 Go 程序重放有限故障组合，不实现共识协议。 从课程结构到实验路径 MIT 6.5840 Spring 2026把 RPC、存储和复制实验逐步连起来；Stanford CS244B Spring 2024更突出原论文讨论与研究。两份课表覆盖事务、分布式计算和信任模型，学习范围远大于 Paxos、Raft、ZooKeeper 与 etcd。 系列按先修关系重新排列：先获得分析请求、状态和故障的语言，再实现任务调度、KV、复制与分片，随后讨论协调服务、事务、缓存、计算系统...

“分数发生变化后，立即显示新的名次”还不是一个足以实现和分析的需求。相同分数是否并列，删除之后名次是否连续，查询不存在的记录应返回什么，都能改变程序的合法输出。先固定这些选择，才能讨论哈希表、数组和有序树各自承担的工作。 本系列从一个本地动态榜单开始。它没有网络请求、权限和并发更新，全部操作顺序执行。首篇只建立操作契约与朴素参照；后续结构必须回答相同的问题，才能比较成本。MIT 的算法导论讲义把问题表述为输入与允许输出之间的关系，这也是这里区分“需求”和“某一种程序”的依据。MIT 6.006 Lecture 1 同分记录怎样排序 每条记录包含整数标识 id 和整数分数 score。标识从 0 开始，由插入操作单调分配，删除后不复用。分数可为负数，同分合法。排序键统一写为 (-score, id)，按字典序升序比较，因此高分靠前，同分时较早分配的 ID 靠前。 ID 分数 排序键 名次 0 80 (-80, 0) 2 1 95 (-95, 1) 1 2 80 (-80, 2) 3 把 ID 2 更新为 100，顺序就成为 2, 1, 0。再把 ID ...

第二次 TLS 连接显示 Reused，是否意味着没有握手？客户端指定了早期数据文件，是否意味着服务器已经接受它？恢复成功、早期数据被接受、应用处理完成，是三个需要分别观察的结果。 第 24 篇建立了证书与服务身份验证。本篇保留专用测试 CA，在新建连接之间传递会话材料，比较完整握手、普通恢复和带早期数据的恢复。实验只运行本机 OpenSSL，不访问真实业务接口。 恢复的是安全上下文，不是旧 socket RFC 8446 §2.2允许从先前连接建立恢复所用的预共享密钥关系。后续连接可以提出相应 PSK 身份，服务器接受后，新连接的安全上下文与先前认证建立的上下文相联系。 客户端仍然新建连接、发送 ClientHello 并处理服务器响应。它不是继续使用旧 TCP 序号空间，也不是把旧的加密字节直接接到新连接上。普通恢复不能只凭“第二次访问”或“耗时较小”判断，必须检查实现实际选择了何种握手路径。 PSK 可以结合新的临时密钥交换，也可以按协议允许的其他模式使用。是否包含新的共享秘密会影响前向保密性质，不能把所有恢复统称为“安全属性与完整证书握手完全一致”。本篇只报告所选实现的结...

TCP 已经连通，收到的证书也能解析，为什么 TLS 仍可能拒绝连接？证书内容可读、签名可验证、签发者可信、服务名字匹配，是不同条件。只证明其中一个，不能替代其他条件。 前置是第 16 篇连接状态。本篇把连接地址与预期服务身份分开，用专用测试 CA 验证三个场景：正常连接、主机名不匹配、不信任签发者。实验不向系统安装 CA，不访问公共 HTTPS 网站；会话恢复与早期数据留到第 25 篇。 先确定要连接谁，再检查它提供的身份 假设应用要连接 server.lab.test，测试中它的传输地址固定为 127.0.0.1。IP 地址告诉 socket 连接到哪里，预期名字告诉证书验证要匹配谁。连接到回环地址不要求证书必须含该 IP，前提是应用的参考身份确实是配置好的 DNS 名，并按该名字验证。 RFC 9525 §6.1要求客户端独立构造可接受的参考身份，不能拿服务端刚给出的证书名字作为预期值，再宣布它与自己匹配。否则任意证书都可能通过这项检查。 服务端证书的 subjectAltName（SAN）可以包含 DNS 名或 IP 地址。DNS 身份与 dNSName 匹配，直接 IP...

同一个 URL 连续返回 200，能否证明每次都访问了源站？过期后收到 304，是否意味着正文为空？把响应状态、正文来源和缓存决策混在一起，会同时误判这两个问题。缓存可以直接生成带正文的 200，也可以在上游验证成功后继续使用已有正文。 第 22 篇解决消息边界。本篇在两个回环 HTTP 服务之间加入受限教学缓存，分别记录客户端、缓存与源站的交换，研究新鲜度、验证器和表示变体。实验不使用浏览器缓存或公共 CDN。 同一资源可以有不同表示 URL 标识目标资源，不保证每次选中的表示逐字节相同。请求头、协商条件以及资源随时间的变化都可能影响结果。例如同一路径按 Accept-Language 返回中文或英文；只按路径保存一份正文，会让后来的另一种语言请求取得错误变体。 缓存保存的对象也不仅是正文。后续复用至少需要关联请求条件、响应字段、验证器和时间信息。丢失 Vary 信息会混用变体；丢失 Date 与 Age 会误算有效期；收到 304 后丢失旧正文则无法构造完整响应。 这里分开回答两个问题：当前请求能匹配哪份已存响应，以及这份响应能否直接复用。变体匹配正确，不等于新鲜；时间尚新鲜...

一个 TCP 连接依次返回两份 HTTP 响应，客户端怎样确定第一份到哪里结束？等待 socket 关闭会阻止连接复用；把一次 recv() 当作一份响应，又会受实际读取分块影响。正确的边界来自 HTTP 消息规则，还依赖对应请求的方法与响应状态。 前置是第 02 篇字节流分帧和第 16 篇连接生命周期。本篇用标准库回环服务发送固定长度与分块响应，检查解析器实际消费的字节。缓存验证留到第 23 篇，TLS 身份验证留到第 24 篇。 方法说明操作，长度规则划分消息 请求行中的方法和目标指出请求的操作，后续字段提供 Host 等上下文。响应状态说明处理结果；这些语义不能由连接成功或收到了若干字节代替。例如收到完整错误响应，表示消息传输与解析可以成功，业务请求仍可能失败。 RFC 9110 §9.2分别定义安全方法与幂等方法。安全指方法的请求语义本质上只读，不承诺服务器完全不写日志。幂等比较重复相同请求对服务器的预期效果，不要求每次响应状态、时间或正文完全相同。因而“第一次响应丢了”并不自动授权重试任意操作。 HTTP/1.1 消息具有起始行、字段、空行，以及按规则存在的消息体。头部...

权威服务器上的地址已经改了，客户端为什么还会得到旧地址？一个刚创建的名字，为什么仍被回答为不存在？这两种现象都可能来自缓存，但需要不同的记录和返回码来证明，不能统一归结为“DNS 尚未传播完”。 前置是第 13 篇 UDP 与第 16 篇连接状态。本篇用独立 Unbound 进程查询自建权威服务，比较权威数据、递归缓存和客户端实际结果。实验不修改操作系统 DNS 配置，也不请求公共域名。 查询的是某个名字的某类数据 DNS 不是只保存“域名到一个 IP”的表。一次问题包含名字、类型和类；例如 www.lab.test. IN A 与同名的 AAAA 是两个问题。A 提供 IPv4 地址，RFC 3596 §2定义的 AAAA 提供 IPv6 地址，NS 描述名称服务器，SOA 携带一个区的管理信息。一个名字可以有多种记录，同一类型也可能有多条记录。 名字末尾的点表示从根开始的完整名称。www.lab.test. 的标签按层次组织，但每一级标签不必对应独立服务器或独立管理区。区（zone）是权威管理与数据提供的边界；委派把一部分名字空间交给下一级，父区保留通向下一级的指引。RFC ...