Sibuna 之书 1.0.0-beta.3 文档
语言: 简体中文
English简体中文한국어日本語EspañolDeutschहिन्दीالعربية
本页内容

第 I 部分:一次请求的成本

选择算法之前,先确定它要保护的资源。本章建立几个小模型,后面的每个设计决策都以它们为衡量标准:源站工作、谜题工作、会话分摊,以及不可信客户端能让服务器占用的内存。

准入是一个经济决策

假设源站为每个获准的请求执行一次数据库查询并渲染一个页面。令 \(c_o\) 表示这项工作,\(c_g\) 表示网关处理每个请求的工作,\(r\) 表示到达率。没有网关时,源站每秒必须承担 \(r c_o\) 个单位的工作。准入比例为 \(a\) 的网关把这一需求变为 \(r a c_o\),而自身消耗 \(r c_g\)。只有当节省下来的源站工作超过网关自身的成本以及它给合法访问者带来的成本时,网关才有用。

\[r c_g + r a c_o < r c_o \quad \Leftrightarrow \quad c_g < (1-a) c_o.\]

这是一个容量模型,不是测量结果。它省略了带宽、连接状态、存储和客户端延迟。它的价值在于每个缺失的项都清晰可见。缓存命中可能使 \(c_o\) 很小;代价高昂的查询可能使它很大。请求方与服务器之间不存在通用的成本比例。

工作量证明能证明什么

客户端谜题证明的是:某个人或程序找到了一个满足公开验证规则的输入。它不能证明对方是人、对方的身份或良好意图。请求方可以租用算力,在会话有效期内复用有效会话,或者把工作分散到多台机器上。谜题改变的是准入成本;获准的请求可以做什么,仍然由策略和检查决定。

基于地址的限制与之互补。它们约束单个地址,但一个共享地址可能代表很多人,一个请求方也可以使用很多地址。谜题和地址都不是可靠的身份判据。因此,Sibuna 把准入、检查和信誉作为彼此独立的决策。

把哈希搜索看作随机变量

对于理想的 256 位摘要,要求 \(b\) 个前导零比特,则每次独立尝试的成功概率为 \(p = 2^{-b}\)。令 \(K\) 表示直到首次成功(含)为止的尝试次数。于是

\[P(K=k) = (1-p)^{k-1} p, \quad P(K>k) = (1-p)^k, \quad E[K] = 1/p = 2^b.\]

期望可由尾部求和得到:

\[E[K] = \sum_{k=0}^{\infty} P(K>k) = \sum_{k=0}^{\infty} (1-p)^k = 1/p.\]

难度每增加一级,期望尝试次数翻倍。但这并不保证每道谜题的耗时都翻倍。有些谜题第一次尝试就成功;有些的耗时远超平均值。只测量一次求解的客户端,测到的主要是这种随机性。

一条曲线,在 x = 0 处从 1 开始下降,到 x = 4 时趋近于 0。x = 1 处的标记点表明,搜索仍在进行的概率为 e 的负 1 次方,约 0.368;x 约为 3.0 处的第二个点表明,95% 的搜索已经结束。
图 1 哈希搜索的生存概率:在大工作量近似 \(P(K > x/p) \approx e^{-x}\) 下,尝试次数达到期望次数的 \(x\) 倍之后,搜索仍在进行的概率。

会话分摊工作

假设一个会话在过期前允许 \(m\) 个请求,一道谜题的成本为 \(c_p\),验证成本为 \(c_v\),一次会话检查的成本为 \(c_s\)。忽略失败的尝试,网关分摊到每个请求的成本为 \(c_v/m + c_s\),而客户端的谜题成本为 \(c_p/m\)。延长会话有效期对真人和自动化客户端同样有利。选择有效期是一个策略决策,而不是密码学优化。

有界状态是第二种预算

把工作移出请求路径并不会让它消失。设事件以速率 \(\lambda\) 到达,存储线程以平均速率 \(\mu\) 持久化它们,队列可容纳 \(Q\) 条记录。当 \(\lambda > \mu\) 时,流体近似给出

\[t_{\mathrm{fill}} \approx \frac{Q}{\lambda - \mu}.\]

更大的队列换来的是时间,而不是吞吐量。批处理分摊了事务成本,但被保留的记录仍然需要内存,最终也需要处理。过载时,Sibuna 丢弃新的事件记录并对其计数,同时继续依据内存中的状态作出请求决策。运维人员既要监控 HTTP 成功率,也要监控丢失的证据。

我们将贯穿全书的不变量

  1. 不可信的请求不能创建无界的服务器状态。
  2. 有效的准入令牌不能绕过应用层的拒绝。
  3. 只要还有从缓冲区借出的切片,该缓冲区就保持存活。
  4. 持久化重试不能让一个事件或它对信誉的影响成倍增加。
  5. 已发布的策略快照在最后一个读者释放它之前保持不可变。

本书其余部分推导使这些陈述成立的机制,以及能够揭示违反情况的测试。只有在这些陈述保持成立时,快速路径才有用。