k8s调度流程梳理：为创建的 pod 找到合适的 node

backoff机制是并发编程中常见的一种机制，即如果任务反复执行依旧失败，则会按次增长等待调度时间，降低重试效率，从而避免反复失败浪费调度资源

// cmd/kube-scheduler/app/server.go
func runCommand(cmd *cobra.Command, opts *options.Options, registryOptions ...Option) error {
    ...
    ...
    cc, sched, err := Setup(ctx, opts, registryOptions...) // 初始化 scheduler
	if err != nil {
		return err
	}

     return Run(ctx, cc, sched) // 开始调度
}

func (sched *Scheduler) scheduleOne(ctx context.Context) {
    // 从 activeQ 中 pop 出 一个 pod
    // 到底是pop 最新 pod，还是最老pod呢？
    podInfo := sched.NextPod()
    ...
    // 根据 pod.Spec.SchedulerName 拿到对应的调度框架实例(这里是 default-scheduler)
    fwk, err := sched.frameworkForPod(pod)
    ...
    ...
    // filter 和 score 后 返回最优节点
    scheduleResult, err := sched.Algorithm.Schedule(schedulingCycleCtx, sched.Extenders, fwk, state, pod)
    if err != nil {
        var nominatingInfo *framework.NominatingInfo
	reason := v1.PodReasonUnschedulable
        if fitError, ok := err.(*framework.FitError); ok {  // 调度失败
            if !fwk.HasPostFilterPlugins() { // 默认调度框架是会有 postFilterPlugins的
	        klog.V(3).InfoS("No PostFilter plugins are registered, so no preemption will be performed")
	    } else {
                // 这里面会执行抢占逻辑，什么是抢占呢?
                // 相当于给 pod "开后门"， 即如果 pod 的优先值比较高，删除一个比他优先级低的 pod(victim)。
                // 然后返回 pod 抢占到的节点
                result, status := fwk.RunPostFilterPlugins(ctx, state, pod, fitError.Diagnosis.NodeToStatusMap)
		...
                ...
                // 构建提名信息	
		if result != nil {
		    nominatingInfo = result.NominatingInfo
		}
                ...
                ...
                // 这里面就是执行调度失败的逻辑， 会把 抢占者pod 加入到 unschedulableQ 队列中, 重新调度
                sched.recordSchedulingFailure(fwk, podInfo, err, reason, nominatingInfo)
                return
            }
        }
    }
    ...
    .
    // 这就是我们说的 乐观假设，通过本地化数据模拟调度成功。最终结果就是 pod.Spec.NodeName = SuggestedHost
    // 经过 filter 和 score 就开始模拟调度了
    err = sched.assume(assumedPod, scheduleResult.SuggestedHost)
    if err != nil {
        ...
        // 这里就没有抢占，重新调度。
        // 看到 "clearNominatedNode"没， 直接删除提名信息
        sched.recordSchedulingFailure(fwk, assumedPodInfo, err, SchedulerError, clearNominatedNode)
	return
    }
    
    // 即有时候会为 pod 预留一些资源比如 pvc(在 PreFilter 中也只会调用VolumeBinding，这时候就预留了pvc与 pv 的绑定逻辑, 放在上下文 CycleState 中的) 
    // default-scheduler 底层 只有一个 VolumeBinding 插件。所以这里也是操作本地缓存将 pvc 与 pv 的绑定。
    if sts := fwk.RunReservePluginsReserve(schedulingCycleCtx, state, assumedPod, scheduleResult.SuggestedHost); !sts.IsSuccess() {
       ...
       ...
       sched.recordSchedulingFailure(fwk, assumedPodInfo, sts.AsError(), SchedulerError, clearNominatedNode)
       return
    }

    // 这里会遇到"检查点" Permit。
    // 有点尴尬的是 default-scheduler 里面没有实现 Permit插件。 所以可以不用管这块逻辑 所以注释掉
    // runPermitStatus := fwk.RunPermitPlugins(schedulingCycleCtx, state, assumedPod, scheduleResult.SuggestedHost)

   // 最后就是通过异步协程的方式，向 apiserver 发送 pod 与 node 的绑定请求
   go func() {
       // 遇到绑定周期的 PreBind。
       // 你看源码会发现跟调度周期中"检查点" Reserve 配置的插件是一样的，都是调用 VolumeBinding 插件实例。
       // 就是做的 pvc 与 pv 的绑定
       preBindStatus := fwk.RunPreBindPlugins(bindingCycleCtx, state, assumedPod, scheduleResult.SuggestedHost)
       ...
       ...
       // 遇到 Bind "检查点"。
       // 其实底层非常简单，就是给 apiserver 发送 v1.Binding 资源类型来完成真正的绑定。
       sched.bind(bindingCycleCtx, fwk, assumedPod, scheduleResult.SuggestedHost, state)
       ...
       ...
       // 最后会"检查点" PostBind。
       // 但default-scheduler 里面也没有实现 PostBind插件。 所以也可以不用管这块逻辑
       // fwk.RunPostBindPlugins(bindingCycleCtx, state, assumedPod, scheduleResult.SuggestedHost)
   }()
}

// pkg/scheduler/apis/config/v1beta2/default_plugins.go
func getDefaultPlugins() *v1beta2.Plugins {
	plugins := &v1beta2.Plugins{
		QueueSort: v1beta2.PluginSet{
			Enabled: []v1beta2.Plugin{
				{Name: names.PrioritySort},
			},
		},
		PreFilter: v1beta2.PluginSet{
			Enabled: []v1beta2.Plugin{
				{Name: names.NodeResourcesFit},
				{Name: names.NodePorts},
				{Name: names.VolumeRestrictions},
				{Name: names.PodTopologySpread},
				{Name: names.InterPodAffinity},
				{Name: names.VolumeBinding},
				{Name: names.NodeAffinity},
			},
		},
		Filter: v1beta2.PluginSet{
			Enabled: []v1beta2.Plugin{
				{Name: names.NodeUnschedulable},
				{Name: names.NodeName},
				{Name: names.TaintToleration},
				{Name: names.NodeAffinity},
				{Name: names.NodePorts},
				{Name: names.NodeResourcesFit},
				{Name: names.VolumeRestrictions},
				{Name: names.EBSLimits},
				{Name: names.GCEPDLimits},
				{Name: names.NodeVolumeLimits},
				{Name: names.AzureDiskLimits},
				{Name: names.VolumeBinding},
				{Name: names.VolumeZone},
				{Name: names.PodTopologySpread},
				{Name: names.InterPodAffinity},
			},
		},
		PostFilter: v1beta2.PluginSet{
			Enabled: []v1beta2.Plugin{
				{Name: names.DefaultPreemption},
			},
		},
		PreScore: v1beta2.PluginSet{
			Enabled: []v1beta2.Plugin{
				{Name: names.InterPodAffinity},
				{Name: names.PodTopologySpread},
				{Name: names.TaintToleration},
				{Name: names.NodeAffinity},
			},
		},
		Score: v1beta2.PluginSet{
			Enabled: []v1beta2.Plugin{
				{Name: names.NodeResourcesBalancedAllocation, Weight: pointer.Int32Ptr(1)},
				{Name: names.ImageLocality, Weight: pointer.Int32Ptr(1)},
				{Name: names.InterPodAffinity, Weight: pointer.Int32Ptr(1)},
				{Name: names.NodeResourcesFit, Weight: pointer.Int32Ptr(1)},
				{Name: names.NodeAffinity, Weight: pointer.Int32Ptr(1)},
				// Weight is doubled because:
				// - This is a score coming from user preference.
				// - It makes its signal comparable to NodeResourcesFit.LeastAllocated.
				{Name: names.PodTopologySpread, Weight: pointer.Int32Ptr(2)},
				{Name: names.TaintToleration, Weight: pointer.Int32Ptr(1)},
			},
		},
		Reserve: v1beta2.PluginSet{
			Enabled: []v1beta2.Plugin{
				{Name: names.VolumeBinding},
			},
		},
		PreBind: v1beta2.PluginSet{
			Enabled: []v1beta2.Plugin{
				{Name: names.VolumeBinding},
			},
		},
		Bind: v1beta2.PluginSet{
			Enabled: []v1beta2.Plugin{
				{Name: names.DefaultBinder},
			},
		},
	}
	applyFeatureGates(plugins)

	return plugins
}

func (sched *Scheduler) scheduleOne(ctx context.Context) {
...
...
    // 执行完filter 和 score 逻辑
    scheduleResult, err := sched.Algorithm.Schedule(schedulingCycleCtx, sched.Extenders, fwk, state, pod)
    if err != nil {
        // 提名信息
        var nominatingInfo *framework.NominatingInfo
	reason := v1.PodReasonUnschedulable
	if fitError, ok := err.(*framework.FitError); ok {
            ...
            result, status := fwk.RunPostFilterPlugins(ctx, state, pod, fitError.Diagnosis.NodeToStatusMap)
            if result != nil {
	        nominatingInfo = result.NominatingInfo
	    }
        }
    ...
    ...
    // 调度失败方法
    sched.recordSchedulingFailure(fwk, podInfo, err, reason, nominatingInfo)
    return
    }

....
}

func (ev *Evaluator) Preempt(ctx context.Context, pod *v1.Pod, m framework.NodeToStatusMap) (*framework.PostFilterResult, *framework.Status) {
...
...
   // 1. 验证是否需要发生抢占，如果有 pod 已经处于删除中，就可以不用发生抢占
    if !ev.PodEligibleToPreemptOthers(pod, m[pod.Status.NominatedNodeName]) {
        return nil, framework.NewStatus(framework.Unschedulable)
    } 
   
    // 2. 找到所有可以抢占的 node 以及他上面的可以被抢占的pod(我们统一将这类 pod 称为 victim)
    candidates, nodeToStatusMap, err := ev.findCandidates(ctx, pod, m)
    if err != nil && len(candidates) == 0 {
       return nil, framework.AsStatus(err)
    }
   
    // 3. 通过 extenders 在过滤一次
    candidates, status := ev.callExtenders(pod, candidates)

    // 4. 找到最合适的
    bestCandidate := ev.SelectCandidate(candidates)
    if bestCandidate == nil || len(bestCandidate.Name()) == 0 {
        return nil, framework.NewStatus(framework.Unschedulable)
    }

    // 5. 删除 victim, 再清除节点上比抢占 pod 优先级低的pod的提名(pod.Status.NominatedNodeName = "")
    if status := ev.prepareCandidate(bestCandidate, pod, ev.PluginName); !status.IsSuccess() {
        return nil, status
    }
}

func (sched *Scheduler) recordSchedulingFailure(fwk framework.Framework, podInfo *framework.QueuedPodInfo, err error, reason string, nominatingInfo *framework.NominatingInfo) {
    // 通过这里将被抢占的 pod 添加到 unschedulableQ 中。(不要被他 Error 迷惑了， 以为是个错误日志 -_-!!!)
    sched.Error(podInfo, err)

    if sched.SchedulingQueue != nil {
        // 增加提名信息
        sched.SchedulingQueue.AddNominatedPod(podInfo.PodInfo, nominatingInfo)
    } 
    ...
    ...
    // 更新 pod status 中的提名: pod.Status.NominatedNodeName = nominatingInfo.NominatedNodeName
    if err := updatePod(sched.client, pod, &v1.PodCondition{
          Type:    v1.PodScheduled,
	  Status:  v1.ConditionFalse,
	  Reason:  reason,
	  Message: err.Error(),
	}, nominatingInfo); err != nil {
          klog.ErrorS(err, "Error updating pod", "pod", klog.KObj(pod))
    }
}