SchedulerCache是kubernetes scheduler中负责本地数据缓存的核心数据结构, 其实现了Cache接口,负责存储从apiserver获取的数据，提供给Scheduler调度器获取Node的信息，然后由调度算法的决策pod的最终node节点,其中Snapshot和节点打散算法非常值得借鉴

设计目标

数据感知

SchedulerCache的数据从apiserver通过网络感知,其数据的同步一致性主要是通过kubernetes中的Reflector组件来负责保证,SchedulerCache本身就是一个单纯数据的存储

Snapshot机制

当scheduler获取一个待调度的pod,则需要从Cache中获取当前集群中的快照数据(当前此时集群中node的统计信息), 用于后续调度流程中使用

节点打散

节点打散主要是指的调度器调度的时候，在满足调度需求的情况下，为了保证pod均匀分配到所有的node节点上，通常会按照逐个zone逐个node节点进行分配，从而让pod节点打散在整个集群中

过期删除

Scheduler进行完成调度流程的决策之后，为pod选择了一个node节点，此时还未进行后续的Bind操作，但实际上资源已经分配给该pod, 此时会先更新到本地缓存()，然后再等待apiserver进行数据的广播并且最终被kubelet来进行实际的调度

但如果因为某些原因导致pod后续的事件都没有被监听到，则需要将对应的pod资源进行删除，并删除对node资源的占用

cache内部pod状态机

在scheduler cache中pod会一个内部的状态机：initial、Assumed、Expired、Added、Delete,实际上所有的操作都是围绕着该状态机在进行，状态如下:
Initial: 初始化完成从apiserver监听到(也可能是监听到一个已经完成分配的pod)
Assumed: 在scheduler中完成分配最终完成bind操作的pod(未实际分配)
Added: 首先监听到事件可能是一个已经完成实际调度的pod(即从initial到Added),其次可能是经过调度决策后，被实际调度(从Assumed到Added),最后则是后续pod的更新(Update), Added语义上其实就是往Cache中添加一个Pod状态
Deleted: 某个pod被监听到删除事件，只有被Added过的数据才可以被Deleted
Expired: Assumed pod经过一段时间后没有感知到真正的分配事件被删除

源码实现

数据结构

type schedulerCache struct {
    stop   <-chan struct{}
    ttl    time.Duration
    period time.Duration

    // 保证数据的安全
    mu sync.RWMutex
    // 存储假定pod的信息集合,经过scheduler调度后假定pod被调度到某些节点,进行本地临时存储
    // 主要是为了进行node资源的占用，可以通过key在podStats查找到假定的pod信息
    assumedPods map[string]bool
    // pod的状态
    podStates map[string]*podState
    // 存储node的映射
    nodes     map[string]*nodeInfoListItem
    csiNodes  map[string]*storagev1beta1.CSINode
    // node信息的链表，按照最近更新时间来进行连接
    headNode *nodeInfoListItem
    // 存储node、zone的映射信息
    nodeTree *NodeTree
    // 镜像信息
    imageStates map[string]*imageState
}

Snapshot机制

数据结构

Snapshot数据结构主要负责存储当前集群中的node信息,并且通过Generation记录当前更新的最后一个周期

type Snapshot struct {
    NodeInfoMap map[string]*NodeInfo
    Generation  int64
}

Snapshot的创建与更新

创建主要位于kubernetes/pkg/scheduler/core/generic_scheduler.go，实际上就是创建一个空的snapshot对象

nodeInfoSnapshot:         framework.NodeInfoSnapshot(),

数据的更新则是通过snapshot方法来调用Cache的更新接口来进行更新

func (g *genericScheduler) snapshot() error {
    // Used for all fit and priority funcs.
    return g.cache.UpdateNodeInfoSnapshot(g.nodeInfoSnapshot)
}

借助headNode实现增量标记

随着集群中node和pod的数量的增加，如果每次都全量获取snapshot则会严重影响调度器的调度效率，在Cache中通过一个双向链表和node的递增计数(etcd实现)来实现增量更新

func (cache *schedulerCache) UpdateNodeInfoSnapshot(nodeSnapshot *schedulernodeinfo.Snapshot) error {
    cache.mu.Lock()
    defer cache.mu.Unlock()
    balancedVolumesEnabled := utilfeature.DefaultFeatureGate.Enabled(features.BalanceAttachedNodeVolumes)

    // 获取当前snapshot的Genration
    snapshotGeneration := nodeSnapshot.Generation

    // 遍历双向链表，更新snapshot信息
    for node := cache.headNode; node != nil; node = node.next {
        if node.info.GetGeneration() <= snapshotGeneration {
            //所有node信息都更新完毕
            break
        }
        if balancedVolumesEnabled && node.info.TransientInfo != nil {
            // Transient scheduler info is reset here.
            node.info.TransientInfo.ResetTransientSchedulerInfo()
        }
        if np := node.info.Node(); np != nil {
            nodeSnapshot.NodeInfoMap[np.Name] = node.info.Clone()
        }
    }
    // 更新snapshot的genration
    if cache.headNode != nil {
        nodeSnapshot.Generation = cache.headNode.info.GetGeneration()
    }

    // 如果snapshot里面包含过期的pod信息则进行清理工作
    if len(nodeSnapshot.NodeInfoMap) > len(cache.nodes) {
        for name := range nodeSnapshot.NodeInfoMap {
            if _, ok := cache.nodes[name]; !ok {
                delete(nodeSnapshot.NodeInfoMap, name)
            }
        }
    }
    return nil
}

nodeTree

nodeTree主要负责节点的打散，用于让pod均匀分配在多个zone中的node节点上

2.3.1 数据结构

type NodeTree struct {
    tree      map[string]*nodeArray // 存储zone和zone下面的node信息
    zones     []string              // 存储zones
    zoneIndex int
    numNodes  int
    mu        sync.RWMutex
}

其中zones和zoneIndex主要用于后面的节点打散算法使用，实现按zone逐个分配

nodeArray

nodeArray负责存储一个zone下面的所有node节点，并且通过lastIndex记录当前zone分配的节点索引

type nodeArray struct {
    nodes     []string
    lastIndex int
}

添加node

添加node其实很简单，只需要获取对应node的zone信息，然后加入对应zone的nodeArray中

func (nt *NodeTree) addNode(n *v1.Node) {
    // 获取zone
    zone := utilnode.GetZoneKey(n)
    if na, ok := nt.tree[zone]; ok {
        for _, nodeName := range na.nodes {
            if nodeName == n.Name {
                klog.Warningf("node %q already exist in the NodeTree", n.Name)
                return
            }
        }
        // 吧节点加入到zone中
        na.nodes = append(na.nodes, n.Name)
    } else {
        // 新加入zone
        nt.zones = append(nt.zones, zone)
        nt.tree[zone] = &nodeArray{nodes: []string{n.Name}, lastIndex: 0}
    }
    klog.V(2).Infof("Added node %q in group %q to NodeTree", n.Name, zone)
    nt.numNodes++
}

数据打散算法

数据打散算法很简单，首先我们存储了zone和nodeArray的信息，然后我们只需要通过两个索引zoneIndex和nodeIndex就可以实现节点的打散操作， 只有当当前集群中所有zone里面的所有节点都进行一轮分配后，然后重建分配索引

func (nt *NodeTree) Next() string {
    nt.mu.Lock()
    defer nt.mu.Unlock()
    if len(nt.zones) == 0 {
        return ""
    }
    // 记录分配完所有node的zone的计数，用于进行状态重置
    // 比如有3个zone: 则当numExhaustedZones=3的时候，就会重新从头开始进行分配
    numExhaustedZones := 0
    for {
        if nt.zoneIndex >= len(nt.zones) {
            nt.zoneIndex = 0
        }
        // 按照zone索引来进行逐个zone分配
        zone := nt.zones[nt.zoneIndex]
        nt.zoneIndex++
        // 返回当前zone下面的next节点,如果exhausted为True则表明当前zone所有的节点，在这一轮调度中都已经分配了一次
        // 就需要从下个zone继续获取节点
        nodeName, exhausted := nt.tree[zone].next()
        if exhausted {
            numExhaustedZones++
            // 所有的zone下面的node都被分配了一次，这里进行重置，从头开始继续分配
            if numExhaustedZones >= len(nt.zones) { // all zones are exhausted. we should reset.
                nt.resetExhausted()
            }
        } else {
            return nodeName
        }
    }
}

重建索引

重建索引则是将所有nodeArray的索引和当前zoneIndex进行归零

func (nt *NodeTree) resetExhausted() {// 重置索引
    for _, na := range nt.tree {
        na.lastIndex = 0
    }
    nt.zoneIndex = 0
}

数据过期清理

数据存储

Cache要定时将之前在经过本地scheduler分配完成后的假设的pod的信息进行清理，如果这些pod在给定时间内仍然没有感知到对应的pod真正的添加事件则就这些pod删除

assumedPods map[string]bool

后台定时任务

默认每30s进行清理一次

func (cache *schedulerCache) run() {
    go wait.Until(cache.cleanupExpiredAssumedPods, cache.period, cache.stop)
}

清理逻辑

清理逻辑主要是针对那些已经完成绑定的pod来进行，如果一个pod完成了在scheduler里面的所有操作后，会有一个过期时间，当前是30s,如果超过该时间即deadline小于当前的时间就删除该pod

// cleanupAssumedPods exists for making test deterministic by taking time as input argument.
func (cache *schedulerCache) cleanupAssumedPods(now time.Time) {
    cache.mu.Lock()
    defer cache.mu.Unlock()

    // The size of assumedPods should be small
    for key := range cache.assumedPods {
        ps, ok := cache.podStates[key]
        if !ok {
            panic("Key found in assumed set but not in podStates. Potentially a logical error.")
        }
        // 未完成绑定的pod不会被进行清理
        if !ps.bindingFinished {
            klog.V(3).Infof("Couldn't expire cache for pod %v/%v. Binding is still in progress.",
                ps.pod.Namespace, ps.pod.Name)
            continue
        }
        // 在完成bind之后会设定一个过期时间，目前是30s,如果deadline即bind时间+30s小于当前时间就过期删除
        if now.After(*ps.deadline) {
            klog.Warningf("Pod %s/%s expired", ps.pod.Namespace, ps.pod.Name)
            if err := cache.expirePod(key, ps); err != nil {
                klog.Errorf("ExpirePod failed for %s: %v", key, err)
            }
        }
    }
}

清理pod

清理pod主要分为如下几个部分：
1.对应pod假定分配node的信息
2.清理映射的podState信息

func (cache *schedulerCache) expirePod(key string, ps *podState) error {
    if err := cache.removePod(ps.pod); err != nil {
        return err
    }
    delete(cache.assumedPods, key)
    delete(cache.podStates, key)
    return nil
}

设计总结

核心数据结构数据流如上所示，其核心是通过nodes、headNode实现一个Snapshot为调度器提供当前系统资源的快照，并通过nodeTree进行node节点的打散，最后内部通过一个pod的状态机来进行系统内部的pod资源状态的转换,并通过后台的定时任务来保证经过经过Reflector获取的数据的最终一致性(删除那些经过bind的但是却没被实际调度或者事件丢失的pod), 借助这些其实一个最基础的工业级调度器的本地cache功能就实现了

微信号：baxiaoshi2020
关注公告号阅读更多源码分析文章
更多文章关注 www.sreguide.com
本文由博客一文多发平台 OpenWrite 发布