DONAR 2010 — 把 DNS 全球调度写成一道可解的优化题

是什么

DONAR 是一篇把”全球用户该去访问哪个数据中心”这件事写成数学约束优化题、并用分布式算法解出来的论文。日常类比：一家连锁奶茶店在 50 个城市有门店，订单从 App 进来，总部要决定每单派到哪家店。规则不是”谁近派谁”这么简单——还要看每家店当天的产能上限、要不要把新店多压点单做培训、要不要把订单按比例分给两家做 A/B。DONAR 就是给这种”派单大脑”写的通用引擎。

放到云/CDN 场景，输入是：

• 全球若干个数据中心，每个有副本
• 客户端从世界各地发起 DNS 查询
• 服务方一份策略：延迟权重多少、每个副本最大承受多少 QPS、几个副本之间按什么比例分

输出是：每个客户端该被解析到哪个数据中心 IP。DONAR 跑在多个分布式节点上，节点之间只交换”对偶变量”（一种聚合统计量）就能联合解一个逼近集中式最优的方案。

为什么重要

不理解这篇，下面这些事都没法解释：

• 为什么 akamai-2002 时代 CDN 调度是黑盒、而 2010 年后学术界突然能讲清楚 DNS 全球负载均衡的数学
• 为什么”策略与机制分离”成了现代 GSLB（Global Server Load Balancing）控制平面的默认范式
• 为什么 Cloudflare / Fastly / Azure Traffic Manager 这些商用 GSLB 让你填的字段长得几乎一样：延迟 + 负载上限 + 权重
• 为什么”DNS-based 全球调度”虽然被 anycast 部分替代，至今仍在所有大厂的边缘网络里

核心要点

一句话：把”用户该访问哪个数据中心”从经验法则变成可求解的优化问题，让控制平面有数学保证。

DONAR 把服务器选择拆成 三层抽象：

第一层：策略 DSL（服务方说想要什么）

服务方不写”if 用户在亚洲就走东京”。它声明三件事：

1. 一个延迟权重 α —— 多在乎用户体验
2. 每个副本一个负载上限 —— 这台机器最多接多少
3. 副本之间一个分流比例 —— 比如新版本只接 5% 流量做灰度

这套规则像保险条款：你描述偏好，DONAR 替你算执行方案。

第二层：约束优化（数学引擎）

把上面规则翻成线性规划：

• 决策变量 x[i, j]：把客户端群体 i 的多少比例映射到副本 j
• 目标：最小化总延迟 Σ α · latency(i, j) · x[i, j]
• 约束：每个 j 的总流量 ≤ 负载上限；按比例约束 x[i, j] 满足分流权重

这是一个标准的凸优化问题。如果只有一个 DONAR 节点，直接调求解器就能算。

第三层：分布式求解（不让一个节点累死）

实际部署要扛全球流量，DONAR 节点本身也是分布式的。论文用拉格朗日对偶分解：

• 每个 DONAR 节点只看自己附近的客户端，本地解一个小问题
• 节点之间周期性交换”对偶变量”——你可以理解为一种虚拟价格：某个副本越紧张，它的”价格”越高，邻居节点看到价格高就不再往那个副本派单
• 几轮迭代后全网收敛到接近集中式的最优解

只交换价格、不交换原始客户端列表，通信量下降 1-2 个数量级。

第四层：与传统做法对比

维度	写死规则的 DNS（传统）	DONAR
策略表达	if/else 配置文件	凸优化的目标函数 + 约束
节点协调	各算各的，可能给同一客户端不同答案	对偶变量同步
改一行的影响	需要全网推配置	自动收敛
数学保证	无	接近集中式最优解

实践案例

案例 1：DONAR 怎么决定一个 DNS 查询

用户在巴黎访问 service.example.com。流程：

1. 巴黎运营商的递归 DNS 把请求发给 DONAR 的 anycast 入口
2. 离巴黎最近的 DONAR 节点接到查询，查本地 mapping 表：“这个客户端群体应该解析到法兰克福副本”
3. 返回法兰克福 IP，TTL 30 秒
4. 同一时刻 DONAR 节点之间在后台交换对偶价格——如果法兰克福副本快爆了，下一轮巴黎客户端会被切到伦敦

整个过程对用户透明，只感觉到”打开服务很快”。

案例 2：策略改一行，效果立刻不同

服务方原本写：

α = 1.0     # 完全在乎延迟
load_cap = 10000 QPS   # 每个副本上限
weights = [50, 50]     # 两个副本均分

改成 weights = [10, 90]——DONAR 重新求解，10 秒内全球流量切换到 9:1。这种”声明一行、全球生效”的能力是 DNS-based GSLB 的杀手锏。

案例 3：与 anycast 的分工

Anycast 负责”路由层选最近”，但路由层不知道副本的负载和分流策略。DONAR 跑在 anycast 节点之上，负责”应用层选最优”。两层组合：

• 路由层：让用户找到最近的 DONAR 节点
• 应用层：DONAR 节点选最合适的服务副本

踩过的坑

1. DNS 缓存让反应慢：TTL 内的决策无法立刻生效。论文承认这个 limitation——TTL 设短增加查询量，设长延迟反应。这个矛盾至今没完美解决。

2. 客户端聚合粒度难选：太粗（按 /8 网段聚合）会失去精度，太细（按 /24）通信开销爆炸。DONAR 选了基于 ISP+地理的混合聚合，工程上够用但不漂亮。

3. 服务方不知道想要什么权衡：α 该设多少？很多业务方根本不知道延迟和成本怎么换算。论文没解决这个 product-level 问题，把它留给上层。

4. 对偶分解需要凸性：一旦策略包含”如果延迟 > 100ms 就走备份”这种非凸/离散规则，标准对偶分解不收敛。需要扩展或退化到启发式。

适用 vs 不适用场景

适用：

• 多数据中心 / 多副本的云服务调度
• 想把延迟、负载、分流比例统一在一个框架下求解
• 控制平面与数据平面分离的现代 GSLB 设计
• CDN 调度算法的学术参考起点

不适用：

• 单数据中心 / L4 负载均衡（用 LVS / ipvs 就够）
• 需要毫秒级反应的场景（DNS TTL 是天花板）
• 策略本质是离散规则（用规则引擎 + 路由表更直接）
• 极小规模服务（直接 hard-code 比上 DONAR 简单）

历史小故事（可跳过）

• 2002 年：akamai-2002 公开讲清楚商用 CDN 的两级 DNS 调度，但策略是黑盒。
• 2006 年：OASIS（Freedman, NSDI 2006）作为开源 anycast 选择系统出现，是 DONAR 的直接前身。Freedman 也是 DONAR 作者之一。
• 2010 年：Princeton 的 Wendell + Rexford 团队发表 DONAR，首次把 DNS 调度写成约束优化并给出分布式求解。Rexford 此前在 AT&T 做 BGP 流量工程，把”流量工程视角”搬到了 DNS 层。
• 2010 年代后：商用 GSLB（Azure Traffic Manager 2014、Cloudflare Load Balancer 2016）的控制面思路与 DONAR 高度同构——虽然不一定直接抄代码，但抽象层级一致。

学到什么

1. 把工程问题写成优化问题，会逼出”策略 vs 机制”的清晰分离——这是现代基础设施控制平面的通用打法
2. 分布式优化的核心是只交换聚合量——拉格朗日对偶分解让节点本地决策、邻居交换价格
3. DNS 是 1980 年代的老协议，但承载现代云调度的能力被一篇 SIGCOMM 论文重新激活
4. Anycast + 应用层 GSLB 是互补的两层，不是替代关系
5. 声明式接口比命令式接口更好横向扩展：服务方说”我想要什么”，引擎决定”怎么做”，规模翻倍时引擎升级即可，调用方不动

延伸阅读

• 论文 PDF：DONAR SIGCOMM 2010（14 页，第 3 节是优化建模，最数学但也最值得读）
• 视频：Jennifer Rexford SIGCOMM 演讲合集（看她讲流量工程的连贯思路）
• 商用对照：Cloudflare Load Balancer 文档（DONAR 抽象在产品里的样子）
• akamai-2002 —— 工程上的前辈，DONAR 是它的形式化版本

关联

• akamai-2002 —— DONAR 把 Akamai 的黑盒调度讲成了可求解的优化题
• consistent-hashing-1997 —— CDN 一致性映射的另一支路线，DONAR 是约束优化路线
• fielding-rest-2000 —— REST 把 Web 设计哲学讲成约束推导，DONAR 把调度讲成约束求解，思路同源
• turing-1936 —— 可计算性给”问题能否被求解”画了边界，DONAR 把工程问题压进可计算的凸优化里