HiveD：意外朴素的算法
最近学 HiveD，第一感觉是：它的算法很朴素。
核心分配逻辑很像 buddy allocator：申请资源时找合适的 cell，找不到就从更大的 cell 拆；释放资源时，如果 buddy cell 都空了，就再合回去。
这套东西不难。HiveD 有意思的地方不在“分配算法多复杂”，而在它先把 GPU 集群里的资源重新抽象了一遍。
Note
普通 quota 问的是：用户有多少张 GPU？HiveD 更关心的是：用户拥有什么拓扑结构的 GPU？
这两个问题看起来只差几个字，但在多 GPU 训练里差很多。
只数 GPU 不够
一个作业申请 8 张 GPU，并不意味着随便给 8 张 GPU 就行。
同一台机器里的 8 张 GPU，和分散在 8 台机器上的 8 张 GPU，数量一样，训练性能可能完全不同。多卡训练要频繁同步梯度，GPU 之间是不是在同一个 node、同一个 PCIe switch、同一个 NUMA 域，都会影响通信效率。
所以 GPU 调度不能只看数量，还要看 affinity。
Note
HiveD 不是单纯讨论“怎么公平地分 GPU 数量”，而是在讨论“怎么在共享集群里保住 GPU 的拓扑结构”。如果集群只按数量做 quota，就容易出现一种尴尬情况：用户账面上还有 8 张 GPU，但空闲 GPU 已经被小作业切散了。数量上凑得够，拓扑上却凑不出一个完整的 8 卡节点。
HiveD 论文里把这类问题叫 sharing anomaly。共享之后，用户体验反而可能比一个小型私有集群还差。
VC：虚拟的是结构
HiveD 引入了 Virtual Private Cluster，也就是 VC。
VC 可以理解成一个逻辑上的私有 GPU 集群。用户并不是真的独占物理机器，但 HiveD 会尽量让用户看到一个结构稳定的资源池。
传统 quota 更像是在说：User A 有 32 张 GPU。
HiveD 更像是在说：User A 有一组带拓扑层级的 GPU cell。
这里的 cell 不是简单的一张 GPU，而是某个拓扑层级下的一组 GPU：
| Level | 大概含义 |
|---|---|
| GPU-level cell | 单张 GPU |
| PCIe-switch-level cell | 同一 PCIe switch 下的一组 GPU |
| NUMA-level cell | 同一 NUMA 域下的一组 GPU |
| Node-level cell | 同一台机器里的 GPU |
这样资源就不只是一个数字，而是带拓扑含义的资源块。
Important
HiveD 的关键不是把 GPU 重新编号，而是把 GPU affinity 放进资源模型本身。普通调度器看到的是“我要 8 张 GPU”。HiveD 想表达得更细：我要一个 node-level cell，或者一个 PCIe-switch-level cell，或者几个 GPU-level cell。
数量可能一样，但含义不一样。
high-level cell 不是无脑从最高层拆
HiveD 里有个说法容易误解：分配资源时尽量从 high-level cell 开始。
如果一个任务只申请 1 张 GPU，难道也要先拆一个完整 node 吗？
显然不是。
这里的 high-level 应该理解成：在满足任务 affinity 需求的前提下，选择合适层级的 cell。
单卡任务需要的是 GPU-level cell。
同一 PCIe switch 下的多卡任务，才需要 PCIe-switch-level cell。
同机 8 卡任务，才需要 node-level cell。
Warning
request 1 GPU 和 request 1 node-level cell 不是一回事。前者是一张卡，后者可能是一整台 8 卡机器。HiveD 想避免的是：不要把一个有拓扑需求的多卡作业，退化成“随便凑够 GPU 数量”。
Buddy Cell Allocation：朴素但够用
HiveD 的 buddy cell allocation 很直接：
申请资源时，先在目标层级找空闲 cell。
找不到，就向更高层级找一个更大的 cell，再 split 下来。
释放资源时，如果一组 buddy cell 都空闲，就 merge 回更高层级。
这和内存里的 buddy allocator 很像。
区别在于，内存 buddy 管的是连续地址空间；HiveD 管的是 GPU 拓扑 cell。它维护的不只是大小，还有 GPU 之间的亲和关系。
Note
HiveD 的算法朴素，但它作用的对象不朴素。它不是在一维资源数量上做 buddy，而是在 GPU 拓扑层级上做 buddy。所以 HiveD 的算法并不复杂。它真正有价值的地方是：把 GPU 资源从数量型 quota，变成了结构型 quota。
普通 quota 只能表达：你有多少 GPU？
HiveD 还能表达：你有哪些 GPU cell 结构？
这也是 VC 的意义。它不是简单给用户画一个逻辑边界，而是尽量保证用户拥有的资源结构不会被其他租户长期打散。
碎片还是会有
单卡任务会不会造成碎片？
会。
只要集群里有动态提交和释放，碎片就不可能完全消失。HiveD 也不是说自己能让碎片消失，而是让碎片有规则。
如果有低层级空闲 GPU，单卡任务就直接用 GPU-level cell。
如果没有，可能还是要从更高层级 cell 拆下来。
这确实会打碎一个原本完整的高层 cell。
但 buddy 的好处是：拆分和合并都有结构。等小作业释放后，如果 buddy cell 都空了，系统就有机会把它们重新 merge 回去，恢复成更高层级的拓扑块。
Tip
HiveD 不是“永远不产生碎片”，而是“碎了之后还有机会合回去”。小结
HiveD 可以压成一句话：
算法朴素，抽象关键。
Buddy cell allocation 本身不难，甚至很传统。但 HiveD 把它放到了 GPU 拓扑资源上，再和 VC 结合起来，就变成了一个很清晰的系统设计。
它解决的不是“这一次作业怎么放最优”，而是“多租户长期共享时，怎么不把用户的 GPU 拓扑资源打烂”。
这也是我觉得 HiveD 值得看的一点：系统设计里真正难的，很多时候不是想一个更聪明的策略，而是先把问题描述对。
