Heracles: Improving Resource Efficiency at Scale

这是一篇非常经典的,混部领域解决延迟敏感问题的论文,作者当年还只是mit的一名博士生,在google实习,heracles 是这个学生毕业论文里的其中一部分

论文原址:https://dl.acm.org/doi/pdf/10.1145/2749469.2749475

这是一个实时的、自反馈的,大规模提升资源利用率的系统

1. 简介

为了解决LC服务和BE作业混部引起的LC服务SLO下降的问题,我们开发了Heracles,一个实时的控制器,能够动态使用硬件隔离机制和软隔离机制,保证共享资源的干扰问题

Heracles能够在保证LC服务足够SLO的情况下,最大限度的将空闲资源用来运行BE作业,同时,结合实时监控离线分析,自动检测干扰源,并在合适的时机,自动调整隔离机制防御干扰产生

在这里我们分两步走:

第一步,我们首先来研究一些经典案例,最终会抛出一个结论,那就是混部情况下【如无特殊说明,以下混部一律特指LC服务和BE作业】,干扰绝大部分情况下都是不均匀的、但是和负载有较强的相关性,所以,通过静态分区的方式来隔离共享资源是不够的

第二步,然后我们会解释为什么要设计Heracles,并且会证明

  1. 多种隔离机制的互相结合,是实现高利用率并且不打破LC服务SLO的关键所在
  2. 将干扰问题细分成几个独立的子问题,能够大大的降低动态控制的复杂性
  3. 为什么一个运行在所有机器上的、实时的监控程序是必须的

第三步,我们来评估一下Heracles在Google内部生产环境能产生多大的收益,测试表明,能够将机器利用率提高到90%左右

最后,我们通过硬件的一些机制来实现DRAM带宽的监控与隔离,进一步提高Heracles的精确性以及降低对离线分析的依赖


Reconciling High Server Utilization and Sub-millisecond Quality-of-Service

论文原址: http://csl.stanford.edu/~christos/publications/2014.mutilate.eurosys.pdf

In this paper, we analyze the challenges of maintaining high QoS for low-latency workloads when sharing servers with other workloads.

The additional workloads can interfere with resources such as processing cores, cache space, memory or I/O bandwidth

The goal of this work is to investigate if workload colocation and good quality-of-service for latency-critical services are fundamentally incompatible in modern systems, or if instead we can reconcile the two


机器学习中常用的概率分布

机器学习中常见的分布其实有:

  1. 伯努利分布
  2. 二项分布
  3. 泊松分布
  4. 正态分布(高斯分布)

这几种分布之间其实是可以严格推导的,伯努利分布 -> 二项分布 -> 泊松分布 -> 正态分布。此外,前三种分布都属于离散分布,正太分布是连续分布

1. 伯努利分布

伯努利分布是单次随机实验,只有A和B两种结果,例如0和1,或者成功和失败,是由瑞士科学家雅各布·伯努利(1654 – 1705)提出来的,是最简单的离散型概率分布

在现实生活中,有很多类似的场景。例如:抛硬币,要么正面(国徽)要么反面(面值);购买彩票,要么中奖要么没中奖;打篮球要么投中要么没投中。这些事件都可被称为伯努利试验

我们记伯努利分布成功的概率为 P, (0<=p<=1),则失败的概率为Q = 1-P

其概率质量函数为:P(x)=p^x(1-p)^{1-x}

其期望值为:E(x)=\sum xP(x)=0 * q + 1 * p = p

其方差为:Var(x)=E[(x-E(x))^2]=\sum (x-p)^2P(x)=pq


Intel Cache Allocation Technology: CPU LLC Isolation

1. LLC隔离的工具和原理

LLC是指Last Level cache,目前来说通常也就是L3 Cache,CAT是指Intel架构提供的一组工具&技术,用以支持LLC隔离。隔离的目的是针对Latency sensitive服务程序,提高QoS。可以考虑到两个LS敏感的程序跑在同一个机器上相互影响的程度还是比较大。

相关的一些资料如下:

其中的 17.16 PLATFORM SHARED RESOURCE CONTROL: CACHE ALLOCATION TECHNOLOGY

cpu cache隔离技术的原理基本上就是通过划分LLC,限制进程能使用的cache,前后隔离效果如下:

Cache Allocation Technology Allocates More Resource to High Priority Applications

0

1.1. Intel CAT技术

Intel CAT技术提供一系列工具:

  • 通过CPUID指令,查询当前cpu架构是否支持CAT技术,以及支持哪些资源类型(目前来看一般就是LLC),同时可以查询CLOS的数量以及CBM,CBM是指bitmask的长度
  • 提供一种机制,可以关联CLOSID和bitmask
  • 提供一个特殊的寄存器,存储CLOSID,硬件根据CLOSID决定当前使用哪些资源


dentry 缓存泄露追查

最近追查某线上服务发现一个问题:频繁的创建&删除目录或者文件,会消耗大量的物理内存。

原因是因为,目录或者文件删除后,dentry并没有立即释放,而是保存在了superblock上的lru链表上。通常只有内核认为内存紧张的时候才会回收此部分内存。

不过由于dentry结构非常小,这种case下内存增长是很慢。

// linux-2.6.32.68/fs/dcache.c
/*
 * dput - release a dentry
 * @dentry: dentry to release 
 *
 * Release a dentry. This will drop the usage count and if 
 * appropriate call the dentry unlink method as well as
 * removing it from the queues and releasing its resources. 
 * If the parent dentries were scheduled for release
 * they too may now get deleted.
 *
 * no dcache lock, please.
 */

void dput(struct dentry *dentry)
{
	if (!dentry)
		return;

repeat:
	if (atomic_read(&dentry->d_count) == 1)
		might_sleep();
	if (!atomic_dec_and_lock(&dentry->d_count, &dcache_lock))
		return;

	spin_lock(&dentry->d_lock);
	if (atomic_read(&dentry->d_count)) {
		spin_unlock(&dentry->d_lock);
		spin_unlock(&dcache_lock);
		return;
	}

	/*
	 * AV: ->d_delete() is _NOT_ allowed to block now.
	 */
	if (dentry->d_op && dentry->d_op->d_delete) {
		if (dentry->d_op->d_delete(dentry))
			goto unhash_it;
	}
	/* Unreachable? Get rid of it */
 	if (d_unhashed(dentry))
		goto kill_it;
  	if (list_empty(&dentry->d_lru)) {
  		dentry->d_flags |= DCACHE_REFERENCED;
                // 这里把dentry放到sb的lru链表里
		dentry_lru_add(dentry);
  	}
 	spin_unlock(&dentry->d_lock);
	spin_unlock(&dcache_lock);
	return;

unhash_it:
	__d_drop(dentry);
kill_it:
	/* if dentry was on the d_lru list delete it from there */
	dentry_lru_del(dentry);
	dentry = d_kill(dentry);
	if (dentry)
		goto repeat;
}

而内存回收有两种方式:

  1. 内核发现内存不足时主动处罚。例如分配不了内存时,达到某种指定的阈值时等等。
  2. 手动触发 sysctl vm.drop_caches。

这里只讨论第二种方法。内核在初始化的时候,注册了一个dcache_shrinker来释放dcache内存。shrink_dcache_memory的最主要的逻辑时prune_dcache()函数

static struct shrinker dcache_shrinker = {
	.shrink = shrink_dcache_memory,
	.seeks = DEFAULT_SEEKS,
};
static void __init dcache_init(void)
{
	int loop;
	/* 
	 * A constructor could be added for stable state like the lists,
	 * but it is probably not worth it because of the cache nature
	 * of the dcache. 
	 */
	dentry_cache = KMEM_CACHE(dentry,
		SLAB_RECLAIM_ACCOUNT|SLAB_PANIC|SLAB_MEM_SPREAD);
	// 注册钩子函数,当用户手动触发内存回收时,调用dcache_shrinker
	register_shrinker(&dcache_shrinker);
	/* ... */
}

cgroup 进程调度之 cfs 时间片限制

一些资料

  1. https://www.kernel.org/doc/Documentation/scheduler/sched-bwc.txt
  2. CPU bandwidth control for CFS

cpu带宽控制的原理是在给定周期内(cpu.cfs_period_us)内限制进程组的运行时间(cpu.cfs_quota_us),这两个参数值通过cpu子系统来设置。

cfs_rq相关的两个成员是 runtime_remainingruntime_expires ,前者是当前进程组的剩余时间片,后者是时间片的到期时间。

内核的做法是:

  1. 每次进程切换的时候更新当前进程的运行时间,检查进程时钟带宽是否超过阈值。
  2. 通过一个定时器,每隔固定的cpu.cfs_period_us周期,更新进程组的时钟带宽


CPU 亲缘性实现原理

目前cpu亲缘性设置有两种方式:

  1. 通过sched_setaffinity()函数将进程绑定到某些cpu上运行
  2. 讲进程加入到cpuset控制组,通过修改cpuset.cpus参数来实现亲缘性设置

但是有一点需要注意的是,通过sched_setaffinity设置的cpu_mask不允许超出cpuset.cpus的范围,超出部分是无效的。

举例,进程A所在的cpuset控制组cpuset.cpus参数值是0,1,2,3,4,但是进程运行期间调用sched_setaffinity()修改cpu_mask为0,1,2,4,7。因为7并不在cpuset.cpus范围里,所以内核会把7忽略掉,最终进程只能在0,1,2,4这几个CPU上运行。


内核oom过程简单分析

以内核3.10.79为例。这里分析一下内核对于cgroup.memory进程组oom的过程,以及混部环境下需要什么样的oom策略。

触发时机

内核对于每个memory cgroup维护一个计数器,统计当前cgroup内已经使用了的内存。每当cgroup内进程创建页面时,页面大小所占用的内存就会通过res_counter_charge_locked()函数计入计数器里。而当内存占用超过memory.limit_in_bytes所设置的阈值时,charge失败,返回ENOMEN错误。

int res_counter_charge_locked(
struct res_counter *counter, unsigned long val, bool force)
{
        int ret = 0;
        if (counter->usage + val > counter->limit) {
                counter->failcnt++;
                ret = -ENOMEM;
                if (!force)
                        return ret;
        }
        counter->usage += val;
        if (counter->usage > counter->max_usage)
                counter->max_usage = counter->usage;
        return ret;
}

另外有一个问题需要注意的是,内存这个子系统是拓扑型控制的,不是平级控制的。下一级子系统的所有limit_in_bytes之和不能超过父亲的limit_in_bytes值,否则会设置失败。

所以内存计数的时候:

  1. 进程新创建的页面,会被反向递归计入到所有的父cgroup下面。
  2. memory子系统的根的计数一定是当前内核所有进程的内存使用之和。(注意,由于cgroup.memory对内存的统计和proc文件系统的统计方法不一致,所以这两个系统对于内存使用的值并不是完全对等的)

子cgroup也许内存配额有冗余,但父cgroup不一定会有冗余,所以在反向递归计数的时候,谁内存超过阈值了,就oom谁(选择这个cgroup下的某个进程kill掉,所以这里是有可能某个cgroup明明内存没有被超限但也会被莫名的干掉了)。


libprocess 并发编程

libprocess是mesos中非常重要的一个基础库,提供一些很方便的helper函数以及并发编程所需要的基本原语,例如下面我将重点讲的future/promise。

为了更好的解释future/promise是什么,我抽取了一段mesos中的代码作为例子:

Future<Socket> PollSocketImpl::accept()
{
  return io::poll(get(), io::READ)
    .then(lambda::bind(&internal::accept, get()));
}

这个函数的基本作用是:使用io::poll()注册io::READ事件,并且当事件ready的时候,调用internal::accept()。

显然,这是一个异步的accept()方法。


Borg: google 集群管理操作系统

1. Introduction

google服务器集群的管理系统,类似于百度的Matrix,阿里的fuxi,腾讯的台风平台等等,还有开源的mesos

Borg provides three main benefits: it

  1. hides the details of resource management and failure handling so its users can focus on application development instead;
  2. operates with very high reliability and availability, and supports applications that do the same; and
  3. lets us run workloads across tens of thousands of machines effectively.