Heracles是Stanford的研究者在Google的支持下输出的研究成果，是一个算法框架的名字，论文发表于ISCA’15上，是对borg论文的一个有价值的补充。一般而言，在看完Borg论文以后，也建议阅读一下这篇文章，了解一下在一个集群操作系统上进行大混布，需要考虑的单机隔离问题。

论文解决的问题背景为：在绝大多数的互联网公司中，存在一些被称为LC(Latency-critical, borg中叫latency-sensitive)的任务。这些任务一般是面向终端用户的、对于请求的延时要求很高。比如WebSearch、Redis等这种，需要在几十、几百毫秒内返回。另一种在这篇文章里面被称为BE作业，一般是那些离线计算任务，必要时可以被kill、并由上层计算框架挪到另外一台机器上去执行。在各种类型业务的混布环境下，由于一台机器上部署的进程众多，就会导致LC应用的延时(latency)受到较大影响。而调度系统为了确保LC服务的质量，就会采取比较保守的策略，降低了集群资源利用率。

在论文中，作者首先花很大的篇幅分析了造成这个现象的原因：进程对共享资源的争抢。在当前的计算机体系结构下，这些共享资源包括：

• CPU cores: 在当前的Intel CPU架构下，一个CPU芯片上有两个物理封装(socket)，在一个物理封装下有多个物理核，然后在打开超线程的情况下，一个物理核下面又会有多个逻辑核。CPU Cache出现在不同的级别上，L1/L2是设置在具体的物理核上的，即每个物理核有一组独立的L1/L2 Cache，L3(LLC, Last-level cache)是在socket层面上、被同一socket下的多个物理核共享的。这种结构使得当一个进程被kernel从一个cpu core挪动到另一个core下、或者同一个物理核下的多个超线程(Hyper thread)切换执行的时候，对应的cache和register会被淘汰，出现比较大的性能损耗。因此，调度上会更加希望将LC进程尽可能的绑定在某几个固定的物理核上执行（可以用cgroups的cpuset子系统设定）、且避免BE作业跑到LC作业绑定的core上执行，以尽量消除影响。

• DRAM bandwidth: 当LLC miss的时候，就会发生内存的读写操作。内存的访问是有带宽限制的，这就导致LC任务可能因为带宽不足而提高了访存延时。

• Network traffic: 和DRAM带宽一样，网络带宽也有类似的问题。但这个问题在同一个idc下的通讯中，可能不是瓶颈。

  idc内的一个最底层的交换机下往往连着几十台机器，目前的网卡基本是千兆网卡，然后交换机和更高一层的交换机/路由器的带宽可能只有几个G。比如，1个机架有50台机器，挂在一个64口交换机下，每台机器有1Gb的带宽，但这个交换机和上层只有5Gb的通讯带宽，那么这里就存在1Gb*50 : 5Gb=10:1的收敛比。在现实世界中，往往单机网络带宽还没被打满，就会先被交换机的出口带宽给弄残了。

• Power: CPU加电问题。CPU有供电保护，当一些物理核高速运转的时候，可能出于确保CPU安全的考虑，会降低一些物理核的工作频率。这种调整是硬件层面的，并不知道此时对应核上的进程是啥，可能导致LC业务受损。

在分析了上述共享资源项以后，文章的后面几个部分就非常自然了。首先，作者找了一些LC程序A、以及一组对上述资源中的某个纬度使用非常猛烈的『干扰程序』，让他们在一起运行，量化影响。在测试中，作者们先通过压力测试得到A程序的极限负载(不打破程序SLA的最大负载)，并以此为基准测试在干扰程序影响下，A在x%的极限负载下、长尾请求部分的变化程度。作者将测试的数据绘制成了一张数据表格、可以理解成给A打上”标签”，是A程序的一个”特征”。这张表格建议读论文的时候，建议仔细看看，里面的数据挺有意思的，能分析出许多内容。

而后论文具体介绍了Heracles的算法，这个算法的基本思路包括两个：将共享资源的控制分成几个独立的controller，上面的策略主要是计算如何调整提供给BE的资源量，比如增加或者减少几个cpu物理核的绑定；第二个思路是这个调整是渐进的、多纬度轮询尝试的，即controller每个周期都只在某个单一纬度上尝试调整一点点，然后观察LC任务的SLA情况，如果SLA变化太大，就立即调整回来一些。这个调整过程有点类似『梯度下降法』，即沿着『导数』方向探寻在不打破LC任务SLA的条件下、能分配给BE作业的最佳量。在后面作者贴出来的测试场景下，Heracles表现惊艳，能够把机器的利用率提高到90%左右，同时能够确保上面运行的LC任务的SLA质量。

个人以为，这篇文章的主要参考意义在于他比较系统的分析了LC任务影响的核心要素有哪些(cache, DRAM bandwidth, etc)，并且系统性的进行了数据的分析。对典型负载的数据测试分析，是这篇文章比较出彩的地方，建议细读。后面的Heracles算法，其实只要看透了前面的部分，其设计就是非常自然、直接的，可以较快带过。