pigeon

README

Pigeon Agent: A policy based scheduler extender

The Pigeon scheduler extender agent optimizes particular policy objectives when scheduling a pod. The name pigeon is inspired from pigeon holing, where pigeons select holes in a pigeonhole structure in a collective and organized way, in analogy to bin-packing of pods on nodes in a cluster.

Description

The pigeon agent uses a library (libpigeon, written in C) to solve an optimization (minimization) problem with a given objective function. The priority function of the extender, called pigeon-holing, returns values inversly proportional to the values of the objective function. (Note that larger values of priority are more preferable.) Currently, we support the following policy objectives.

• Adaptive Bin Packing (A_BINPACK)

  A novel algorithm for bin packing called ABP has been introduced and detailed in reference 1. A brief presentation is provided here. The problem is that variability in pod sizes (in term of requested resources) dictates an optimal way for placing pods on nodes. The extreme cases are (1) equal sized pods and (2) a mixture of really small and really large pods. In the first case, it is better to spread the pods among the nodes, placing on the least allocated node. Whereas, in the second case, it is better to pack the pods on nodes, placing on the most allocated node, so as to be able to place large pods when they arrive. Given a spectrum of pod size variability, the following questions arise: How to define and measure variability in pod sizes? And, what is the scheme for placing the pods accordingly?

  The ABP algorithm learns the variability in pod sizes and adjusts the scheme for their placement in an adaptive way. Thus, selecting the A_BINPACK policy relieves us from deciding whether to spread, pack, or any other scheme in between. Further, the ABP algorithm deals with multiple resources (CPU, memory, GPU, ...) in a seamless way. ABP analyzes the correlation of sizes (requests) in multiple dimensions (resources). The objective function is the difference between the observed variability in pod sizes and the variability in node allocation in the cluster.

• Spreading (LOAD_BALANCE)

  The LOAD_BALANCE policy minimizes the variability in resource allocation in the nodes in the cluster. The objective function is the standard deviation of the allocation of the (configurable) prime resource (CPU, by default).

• Packing (CONSOLIDATE)

  The CONSOLIDATE policy does the opposite. The objective function is the negation of the standard deviation of the allocation of the (configurable) prime resource (CPU, by default).

Node allocation

The amount of resources allocated on a node is the aggregation of requested resources of all containers within all pods running on the node. The pigeon agent scheduler extender needs to obtain node allocation information before evaluating its priority function, in relation to scheduling a pod. Since node allocation information is not included in the arguments when the scheduler calls the extender, it will have to be obtained through other means. There are two common ways to obtain such information.

• Internal method: Using this method, the agent would use a Kubernetes client to query the API server for information about all nodes, all pods, all containers running in pods, and the amount of requested resources per container. This operation has to be performed before scheduling each pod.
• External method: A node annotator, external to the scheduler extender, uses a Kubernetes client as per the internal method, and periodically annotates the nodes with calculated node allocation information. The agent would then consult the node annotations when scheduling a pod.

Each mehod has its pros and cons. The internal method results in fresh data and does not require additional external components, but may cause an overhead due to potentially excessive access to the API server. And, the external method has an adjustable (through the choice of update frequency) and lower overhead, at the expense of potentially stale data.

We chose to implement the external method. A node allocation annotator, called k8s-assessor, is provided. The frequency of annotation is adjustable through an environment variable.

Configuration

A configuration file is provided to specify the following configuration variables.

• policyObjective: Current choices are A_BINPACK (default), LOAD_BALANCE, and CONSOLIDATE.
• policyResourceIndex: This is the index of the prime resource. The supported resources are (in order): CPU, memory, number of pods, GPU, and storage. Hence, the index of resources is 0, 1, ..., respectively. Not all resources have to be considered when placing pods. By default, the first two resources are considered. But, one may override this choice by setting an environment variable as described below. Currently, the choice of the number of resources, say n, dictates that resources with indices 0, 1, ..., n-1 are all considered. Extension to selective resources is straightforward.

In addition, the following environment variables may be used.

• POLICY_OBJECTIVE: Supported values are A_BINPACK, LOAD_BALANCE, and CONSOLIDATE. (Default A_BINPACK)
• NUM_RESOURCES: Supported values are in the range [1,5], as outlined above. (Default 2)

References

1. A. N. Tantawi and M. Steinder, "Autonomic Cloud Placement of Mixed Workload: An Adaptive Bin Packing Algorithm," 2019 IEEE International Conference on Autonomic Computing (ICAC), Umea, Sweden, 2019, pp. 187-193.

Documentation

Index

• Constants
• func PriorityFunc(pod v1.Pod, nodes []v1.Node) (*schedulerapi.HostPriorityList, error)
• type Agent
  • func NewAgent() *Agent
  • func (a *Agent) ComputeRank(pod *v1.Pod) (*map[string]int, error)
  • func (a *Agent) UpdateState(nodes *[]v1.Node) bool
• type Client
  • func NewClient(configFile string) *Client
  • func (client *Client) Destroy()
  • func (client *Client) GetNumResources() int
  • func (client *Client) GetPodRanks(pr *PodRequest) map[string]float64
  • func (client *Client) StateUpdateNode(node *Node) (bool, error)
  • func (client *Client) StateUpdatePod(podState *PodState) error
  • func (client *Client) StateUpdatePrint()
  • func (client *Client) StateUpdateStart() bool
  • func (client *Client) StateUpdateStop()
• type Node
  • func MakeNodeTemplate(node *v1.Node, numResources int) *Node
• type PodRequest
  • func CreatePodModel(pod *v1.Pod, numResources int) *PodRequest
• type PodState

Constants

const (
	// RequestedCPUKey : key for the requested CPU
	RequestedCPUKey = "requested-cpu"
	// RequestedMemoryKey : key for the requested memory
	RequestedMemoryKey = "requested-memory"
	// RequestedPodKey : key for the requested pods
	RequestedPodKey = "requested-pods"
	// RequestedGPUKey : key for the requested GPU
	RequestedGPUKey = "requested-gpu"
	// RequestedStorageKey : key for the requested storage
	RequestedStorageKey = "requested-ephemeral-storage"
)

*

• Key labels

const (
	// DefaultNumResources :
	DefaultNumResources = 2
)

*

• Environment variables and their default values

const (
	// PriorityPigeonName : name of pigeon priority function
	PriorityPigeonName = "pigeon-holing"
)

*

• Names of predicates and priority functions

Functions

func PriorityFunc

func PriorityFunc(pod v1.Pod, nodes []v1.Node) (*schedulerapi.HostPriorityList, error)

PriorityFunc : compute pigeon priority function

Types

type Agent

type Agent struct {
	// contains filtered or unexported fields
}

Agent :

var (
	// PigeonAgent :
	PigeonAgent *Agent
)

func NewAgent

func NewAgent() *Agent

NewAgent creates a pigeon agent

func (*Agent) ComputeRank

func (a *Agent) ComputeRank(pod *v1.Pod) (*map[string]int, error)

ComputeRank :

func (*Agent) UpdateState

func (a *Agent) UpdateState(nodes *[]v1.Node) bool

UpdateState :

type Client

type Client struct {
	// contains filtered or unexported fields
}

Client : client to pigeon

func NewClient

func NewClient(configFile string) *Client

NewClient : create an instance of a pigeon client

func (*Client) Destroy

func (client *Client) Destroy()

Destroy : destroy the scheduler

func (*Client) GetNumResources

func (client *Client) GetNumResources() int

GetNumResources : get the number of resource types considered

func (*Client) GetPodRanks

func (client *Client) GetPodRanks(pr *PodRequest) map[string]float64

GetPodRanks :

func (*Client) StateUpdateNode

func (client *Client) StateUpdateNode(node *Node) (bool, error)

StateUpdateNode : Update the state of a node

func (*Client) StateUpdatePod

func (client *Client) StateUpdatePod(podState *PodState) error

StateUpdatePod : Update the state of a pod

func (*Client) StateUpdatePrint

func (client *Client) StateUpdatePrint()

StateUpdatePrint : print the state updater

func (*Client) StateUpdateStart

func (client *Client) StateUpdateStart() bool

StateUpdateStart : start an update session for a given generation

func (*Client) StateUpdateStop

func (client *Client) StateUpdateStop()

StateUpdateStop : stop the update session and print report

type Node

type Node struct {
	/* unique ID */
	ID string

	/* resources */
	ResourceCapacity []int64
	ResourceOverflow []bool
	ResourceUsage    []int64
}

Node : node characteristics

func MakeNodeTemplate

func MakeNodeTemplate(node *v1.Node, numResources int) *Node

MakeNodeTemplate : make a node info template for a node

type PodRequest

type PodRequest struct {
	/* unique ID */
	ID string

	/* resource demand */
	ResourceDemand []int64
}

PodRequest : attributes of a pod placement request

func CreatePodModel

func CreatePodModel(pod *v1.Pod, numResources int) *PodRequest

CreatePodModel : create a pod request

type PodState

type PodState struct {
	/* pod unique ID */
	ID string

	/* node unique ID */
	NodeID string

	/* resource demand */
	ResourceDemand []int64

	/* running state of pod */
	IsRunning bool
}

PodState : the observed state of a pod