Kubelet之Topology Manager分析

Topology Manager是kubelet的一个组件，在kubernetes 1.16加入，而kubernetes 1.18中该feature变为beta版。本篇文档将分析Topology Manager的具体工作原理。

1.为什么需要Topology Manager

现代计算机的CPU架构多采用NUMA（Non-Uniform Memory Access，非统一内存）架构。NUMA就是将cpu资源分开，以node 为单位进行分组，每个node都有着独有的cpu、memory等资源，当一个NUMA节点内的资源相交互时，性能将会有很大的提升；但是，如果是两个NUMA节点之间的资源交互将会变得很慢。

下面这幅图中有两个NUMA节点存在：

• NUMA0：由cpu0、cpu1、cpu2、cpu3以及gpu0、nic0和一块本地内存组成
• NUMA1：由cpu4、cpu5、cpu6、cpu7以及gpu1、nic1和一块本地内存组成

假设某个pod需要的资源清单如下：

• 4个CPU
• 200MB内存
• 1个GPU
• 1个NIC

我们知道，在kubelet中cpu和其他外围设备（比如GPU）的分配由不同的组件完成，cpu的分配由CPU Manager完成，外围设备由Device Manager完成。它们在给pod分配设备时，都是独立工作的，不会有一个全局观念，这会造成一个什么问题呢？在这个例子中，对于该pod而言比较好的资源组合有两个：

• 组合1：cpu0、cpu1、cpu2、cpu3、gpu0、nic0
• 组合2：cpu4、cpu5、cpu6、cpu7、gpu1、nic1

之所以称为比较好的组合，因为这些资源都在一个NUMA节点内。但是CPU Manager和Device Manager是独立工作的，它们不会感知对方给出的分配方案与自己给出的分配方案是不是最优的组合，于是就有可能出现下面这种组合：

• 组合3：cpu0、cpu1、cpu2、cpu3、gpu1、nic1

这个分配方案就不是我们想要的。Topology Manager就是为了解决这个问题而设计的，它的目标就是要找到我们例子中的组合1和组合2。

2.什么是TopologyHint

TopologyHint用中文描述为“拓扑提示”，在Topology Manager中，TopologyHint的定义如下：

type TopologyHint struct {
    NUMANodeAffinity bitmask.BitMask
    Preferred bool
}

其中NUMANodeAffinity是用bitmask表示的NUMA节点的组合。举个例子，假设有两个NUMA节点（编号分别为0和1），那么可能出现的组合为：[0]、[1]、[0,1]，用bitmask表示为：01，10，11（从右往左开始，组合中有哪一个NUMA节点，那一位就是1）。

Preferred代表这个NUMA节点组合对于某个pod而言是不是“优先考虑的”，某个TopologyHint对于pod而言是不是“优先考虑的”需要遵循如下的规则：在满足申请资源个数的前提下，选择的资源所涉及的NUMA节点个数最少，就是“优先考虑的”。怎么理解这句话？我们举个例子——假设现在有两个NUMA节点（编号为0和1），每个NUMA节点上都有两个cpu，如果某个pod需要请求两个cpu，那么TopologyHint有如下几个：

• {01: True}代表从NUMA0上分配两个cpu给pod，这两个cpu都在一个NUMA节点上，涉及的NUMA节点个数最少（为1），所以是“优先考虑的”。
• {10: True}代表从NUMA1上分配两个cpu给pod，这两个cpu也在一个NUMA节点上，涉及的NUMA节点个数也最少（为1），所以是“优先考虑的”。
• {11: False}代表从NUMA0和NUMA1上各取一个cpu，涉及的NUMA节点个数为2，所以不是“优先考虑的”。

那么，是不是所分配的资源必须在一个NUMA节点内，这个方案对于pod而言才是“优先考虑的”呢？——当然不是，比如现在有两个NUMA节点，每个NUMA节点都只有1块GPU，而某个pod申请了2个GPU，此时{11: True}这个TopologyHint就是“优先考虑的”，因为在满足申请资源个数的前提下，最少要涉及到2个NUMA节点。

3.Topology Manager的四种策略

Topology Manager提供了四种策略供用户组合各个资源的TopologyHint。这四种策略是：

• none： 什么也不做，与没有开启Topology Manager的效果一样。
• best-effort:  允许Topology Manager通过组合各个资源提供的TopologyHint，而找到一个最优的TopologyHint，如果没有找到也没关系，节点也会接纳这个Pod。
• restricted： 允许Topology Manager通过组合各个资源提供的TopologyHint，而找到一个最优的TopologyHint，如果没有找到，那么节点会拒绝接纳这个Pod，如果Pod遭到节点拒绝，其状态将变为Terminated。
• single-numa-node： 允许Topology Manager通过组合各个资源提供的TopologyHint，而找到一个最优的TopologyHint，并且这个最优的TopologyHint所涉及的NUMA节点个数是1。如果没有找到，那么节点会拒绝接纳这个Pod，如果Pod遭到节点拒绝，其状态将变为Terminated。

至于Topology Manager是怎样组合各个资源提供的TopologyHint，并且找到一个最优的TopologyHint这个问题，我们会在后面详细阐述。

4.怎样开启Topology Manager

如果kubernetes版本为1.18及其以上的版本，直接在kubelet的启动项中添加：

--topology-manager-policy=
    [none | best-effort | restricted | single-numa-node]

如果kubernetes版本为1.16到1.18之间，还需要在kubelet启动项中添加：

--feature-gates="...,TopologyManager=<true|false>"

5.什么是HintProvider

在kubelet源码中，HintProvider的定义如下：

type HintProvider interface {
    // 根据container请求的资源数产生一组TopologyHint
    GetTopologyHints(*v1.Pod, *v1.Container) map[string][]TopologyHint
    // 根据container请求的资源数为container分配具体的资源
    Allocate(*v1.Pod, *v1.Container) error
}

其中GetTopologyHints这个函数用于为某个container产生某种或多种资源的TopologyHint数组。举个例子，假设有两个NUMA节点（编号为0和1），NUMA0上有cpu1和cpu2，NUMA1上有cpu3和cpu4，某个pod请求两个cpu。那么CPU Manager这个HintProvider会调用GetTopologyHints产生如下的TopologyHint：

• {01: True}代表从NUMA0取2个cpu，并且是“优先考虑的”。
• {10: True}代表从NUMA1取2个cpu，并且是“优先考虑的”。
• {11: False}代表从NUM0和NUMA1各取一个cpu，不是“优先考虑的”。

当前在kubelet中充当HintProvider的总共有两个组件：一个是CPU Manager，另外一个是Device Manager，这两个组件都实现了HintProvider这个接口的两个方法，后续会把HugePages组件加入进来。

另外需要注意的是：GetTopologyHints(*v1.Pod, *v1.Container) map[string][]TopologyHint函数的返回类型是map[string][]TopologyHint，为什么会是这种类型呢？这是为Device Manager设计的，因为Device Manager需要组合多种资源（比如GPU、NIC），每种资源都返回一组TopologyHint。

6.Topology Manager工作原理

下面这段伪代码说明了Topology Manager的主要工作原理：

for container := range append(InitContainers, Containers...) {
    // 遍历每一个HintProvider
    for provider := range HintProviders {
        // 对每一个HintProvider，调用GetTopologyHints获取一组或多组TopologyHint
        hints += provider.GetTopologyHints(container)
    }
    // 将所有的TopologyHint进行合并操作
    bestHint := policy.Merge(hints)
    // 通过合并找到最优的TopologyHint，然后代入每一个HintProvider的Allocate函数中
    // 为container分配资源
    for provider := range HintProviders {
        provider.Allocate(container, bestHint)
    }
}

用一幅图说明一下其原理：

• 遍历pod中的每一个容器
• 对于每一个容器，使用所有的HintProvider的GetTopologyHints方法产生TopologyHint
• 对这些TopologyHint做合并操作，寻求一个最优的TopologyHint
• 每个HintProvider通过最优的TopologyHint给容器分配相应的资源
• 根据设置的不同的策略，是否允许节点接纳这个pod

接下来对每个阶段进行详细说明。

6.1 CPU Manager的GetTopologyHints实现

前面说过，目前可作为HintProvider的组件有两个：CPU Manager和Device Manager。那么这两个组件是如何为给定的pod产生一组（或多组）TopologyHint的呢？本节首先分析CPU Manager。

CPU Manager的GetTopologyHints方法主要是调用了其policy的GetTopologyHints方法。而CPU Manager的static policy对该方法的实现如下：

func (p *staticPolicy) GetTopologyHints(s state.State, pod *v1.Pod, container *v1.Container) map[string][]topologymanager.TopologyHint {
  // 省略其他非关键性代码
  ......
  // 产生TopologyHint的主要逻辑由这个函数完成
	cpuHints := p.generateCPUTopologyHints(available, reusable, requested)
  // 可以看到，只返回了一种资源的TopologyHint，那就是cpu
	return map[string][]topologymanager.TopologyHint{
		string(v1.ResourceCPU): cpuHints,
	}
}

主要的逻辑都是由generateCPUTopologyHints这个函数完成，generateCPUTopologyHints内容如下：

func (p *staticPolicy) generateCPUTopologyHints(availableCPUs cpuset.CPUSet, reusableCPUs cpuset.CPUSet, request int) []topologymanager.TopologyHint {
  // 在满足容器申请资源数的前提下，TopologyHint涉及到的最少的NUMA节点个数
  // 初始值为k8s节点上所有NUMA节点的个数。
	minAffinitySize := p.topology.CPUDetails.NUMANodes().Size()
	// 在满足容器申请资源数的前提下，TopologyHint涉及到的最少的Socket个数
  // 初始值为k8s节点上所有Socket的个数。
	minSocketsOnMinAffinity := p.topology.CPUDetails.Sockets().Size()

	// 用于保存所有TopologyHint
	hints := []topologymanager.TopologyHint{}
  // bitmask.IterateBitMasks这个函数用于将k8s节点上所有的NUMA节点求组合，然后通过回调函数处理这个组合。
  // 例如某个k8s节点上有3个NUMA节点（编号为0，1，2），那么所有组合有
  // [[0],[1],[2],[0,1],[0,2],[1,2],[0,1,2]]
	bitmask.IterateBitMasks(p.topology.CPUDetails.NUMANodes().ToSlice(), func(mask bitmask.BitMask) {
    // 取出NUMA节点组合（以bitmask形式表示）中所涉及到的cpu
		cpusInMask := p.topology.CPUDetails.CPUsInNUMANodes(mask.GetBits()...).Size()
    // 取出NUMA节点组合（以bitmask形式表示）中所涉及到的Socket
		socketsInMask := p.topology.CPUDetails.SocketsInNUMANodes(mask.GetBits()...).Size()
    // 如果NUMA节点组合中所涉及到的cpu个数比请求的cpu数大，并且这个组合所涉及的NUMA节点个数
    // 是目前为止所有组合中最小的，那么就更新它。
		if cpusInMask >= request && mask.Count() < minAffinitySize {
			minAffinitySize = mask.Count()
			if socketsInMask < minSocketsOnMinAffinity {
				minSocketsOnMinAffinity = socketsInMask
			}
		}

	  // 下面这两个for循环用户统计当前k8s节点可用的cpu中，有哪些是属于当前正在处理的NUMA节点组合
		numMatching := 0
		for _, c := range reusableCPUs.ToSlice() {
			// Disregard this mask if its NUMANode isn't part of it.
			if !mask.IsSet(p.topology.CPUDetails[c].NUMANodeID) {
				return
			}
			numMatching++
		}
		for _, c := range availableCPUs.ToSlice() {
			if mask.IsSet(p.topology.CPUDetails[c].NUMANodeID) {
				numMatching++
			}
		}

		// 如果当前组合中可用的cpu数比请求的cpu小，那么就直接返回
		if numMatching < request {
			return
		}
    // 否则就创建一个TopologyHint，并把它加入到hints这个slice中
		hints = append(hints, topologymanager.TopologyHint{
			NUMANodeAffinity: mask,
			Preferred:        false,
		})
	})

  // 这一步表示拿到所有的TopologyHint后，开始对哪些TopologyHint标注“Preferred = true”
  // 这些TopologyHint会被标注为“Preferred = true”：
  // (1)涉及到的NUMA节点个数最少
  // (2)涉及到的socket个数最少
	for i := range hints {
		if hints[i].NUMANodeAffinity.Count() == minAffinitySize {
			nodes := hints[i].NUMANodeAffinity.GetBits()
			numSockets := p.topology.CPUDetails.SocketsInNUMANodes(nodes...).Size()
			if numSockets == minSocketsOnMinAffinity {
				hints[i].Preferred = true
			}
		}
	}

	return hints
}

总结一下这个函数：

• 创建一个存放TopologyHint的数组，名称为hints。
• 根据k8s节点上所有的NUMA节点ID求所有的NUMA节点组合。
• 找出这些组合中涉及NUMA节点个数的最小值，将这个值设置为minAffinitySize。
• 找出这些组合中涉及到Socket个数的最小值，将这个值设置为minSocketsOnMinAffinity。
• 对每个组合，检查当前k8s节点上可用的cpu与该组合所涉及的cpu的交集的个数是否大于容器申请的cpu数，如果比容器申请的cpu数小，那么就不创建TopologyHint，否则就创建一个TopologyHint，并放入hints中。
• 检查hints中所有的TopologyHint，如果该TopologyHint涉及到的NUMA节点数与minAffinitySize值相同，并且该TopologyHint所涉及到的Socket数与minSocketsOnMinAffinity相同，那么将该TopologyHint的Preferred设置为true。

以一张图来说明一下整个流程，图中有3个NUMA节点，每个节点有2个cpu，假设某个pod请求2个cpu以及已知当前k8s节点上空闲的cpu，寻找TopologyHint过程如图：

6.2 Device Manager的GetTopologyHints实现

DeviceManager的GetTopologyHint函数实现与CPU Manager的GetTopologyHint函数实现基本一致，该函数主要调用generateDeviceTopologyHints这个函数，generateDeviceTopologyHints函数内容如下：

func (m *ManagerImpl) generateDeviceTopologyHints(resource string, available sets.String, reusable sets.String, request int) []topologymanager.TopologyHint {
	// 初始化minAffinitySize为k8s节点中NUMA节点个数
	minAffinitySize := len(m.numaNodes)

	// 获取所有NUMA节点组合
	hints := []topologymanager.TopologyHint{}
	bitmask.IterateBitMasks(m.numaNodes, func(mask bitmask.BitMask) {
        // 对每一个NUMA组合做如下处理
		// First, update minAffinitySize for the current request size.
        // devicesInMask用于统计该NUMA组合涉及到device个数
		devicesInMask := 0
        // 获取某种资源下的所有设备（比如获取gpu资源的所有GPU卡），并检查该device是否在当前NUMA组合中
        // 如果在，devicesInMask值加1
		for _, device := range m.allDevices[resource] {
			if mask.AnySet(m.getNUMANodeIds(device.Topology)) {
				devicesInMask++
			}
		}
        // 如果当前NUMA组合涉及到的device数量比request当，并且当前NUMA组合中包含的NUMA个数
        // 比minAffinitySize还小，那么更新minAffinitySize的值。
		if devicesInMask >= request && mask.Count() < minAffinitySize {
			minAffinitySize = mask.Count()
		}

		// numMatching用于获取当前NUMA组合中空闲的device数
		numMatching := 0
		for d := range reusable {
			// Skip the device if it doesn't specify any topology info.
			if m.allDevices[resource][d].Topology == nil {
				continue
			}
			// Otherwise disregard this mask if its NUMANode isn't part of it.
            // 如果reusable中的device的NUMA节点ID不在当前这个NUMA组合中，那么直接返回
            // 不对这个NUMA组合创建TopologyHint，这样做的原因是保证reusable中的device
            // 优先被使用完
			if !mask.AnySet(m.getNUMANodeIds(m.allDevices[resource][d].Topology)) {
				return
			}
			numMatching++
		}

		// Finally, check to see if enough available devices remain on the
		// current NUMA node combination to satisfy the device request.
		for d := range available {
			if mask.AnySet(m.getNUMANodeIds(m.allDevices[resource][d].Topology)) {
				numMatching++
			}
		}

		// 如果当前NUMA组合中可用的device比请求的device数还少，那么直接返回
		if numMatching < request {
			return
		}
        // 创建TopologyHint
		hints = append(hints, topologymanager.TopologyHint{
			NUMANodeAffinity: mask,
			Preferred:        false,
		})
	})
    // 如果某个TopologyHint所涉及的NUMA数最少，那么将该TopologyHint的Preferred设置为true
	for i := range hints {
		if hints[i].NUMANodeAffinity.Count() == minAffinitySize {
			hints[i].Preferred = true
		}
	}

	return hints
}

稍微总结一下：

• 创建一个存放TopologyHint的数组，名称为hints。
• 根据k8s节点上所有的NUMA节点ID求所有的NUMA节点组合。
• 找出这些组合中涉及NUMA节点个数的最小值，将这个值设置为minAffinitySize。
• 对每个组合，检查当前k8s节点上某种资源（比如GPU）可用的设备数与该组合所涉及的该资源的设备数的交集的个数是否大于容器申请的设备数，如果比容器申请的设备数小，那么就不创建TopologyHint，否则就创建一个TopologyHint，并放入hints中。
• 检查hints中所有的TopologyHint，如果该TopologyHint涉及到的NUMA节点数与minAffinitySize值相同，那么将该TopologyHint的Preferred设置为true。

6.3 TopologyHint的merge操作

前面已经说到了CPU Manager和Device Manager会产生多组TopologyHint。那么如何合并这些TopologyHint，找到最优的那个TopologyHint呢？来看看是怎样实现的。

以下面这幅图做说明，在这幅图中总共有3个NUMA节点，对于某个容器而言，CPU Manager找出了CPU资源的一组TopologyHint，Device Manager找出了GPU和NIC的TopologyHint。整个merge流程如下：

• 从每一组资源类型中拿出一个TopologyHint组合成一个新的TopologyHint组合。
• 在这个新的TopologyHint组合内，寻找它们公共的NUMA节点。并且只有当这个组合内所有的TopologyHint的Preferred域都为true时，合并后的TopologyHint的Preferred域才为True。
• 从合并后的TopologyHint中寻找最优的TopologyHint（即TopologyHint的Preferred域为True）。

前面提到过Topology Manager的四种策略，现在重点说一下四种策略中的后面三种：

• best-effort:  结合上图来说，如果没有找到最优的TopologyHint（即图中的TH6），k8s节点也会接纳这个Pod。
• restricted： 结合上图来说，如果没有找到最优的TopologyHint（即图中的TH6），那么节点会拒绝接纳这个Pod，如果Pod遭到节点拒绝，其状态将变为Terminated。
• single-numa-node： 结合上图来说，如果没有找到最优的TopologyHint（即图中的TH6，并且NUMA节点个数为1），那么节点会拒绝接纳这个Pod，如果Pod遭到节点拒绝，其状态将变为Terminated。

另外需要说明的是，在为容器分配相应的资源时，CPU Manager和Device Manager会优先考虑在最优的TopologyHint所涉及的NUMA节点上为容器分配资源，如果这些NUMA节点上的资源不够，还会从其他NUMA节点上为容器分配。

6.4 何时会进行分配操作

也就是说这些HintProvider何时会执行其Allocate函数为容器分配资源？在Topology Manager中有一个Admit函数，会遍历所有的HintProvider，执行HintProvider的Allocate函数。而Topology Manager的Admit函数会在kubelet判断一个pod是否被节点接纳的时候执行（kubelet调用所有的PodAdmitHandler，只要有一个PodAdmitHandler给出拒绝意见，那么节点将不会接纳该pod），因为Topology Manager也是一个PodAdmitHandler。

7.参考文档

https://kubernetes.io/blog/2020/04/01/kubernetes-1-18-feature-topoloy-manager-beta/

https://github.com/kubernetes/enhancements/pull/1121