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