podfingerprint

README

podfingerprint: compute the fingerprint of a set of pods

This package computes the fingerprint of a set of kubernetes pods. For the purposes of this package, a Pod is only its namespace + name pair, used to identify it. A "fingerprint" is a compact unique representation of this set of pods. Any given unordered set of pods with the same elements will yield the same fingerprint, regardless of the order on which the pods are enumerated. The fingerprint is not actually unique because it is implemented using a hash function, but the collisions are expected to be extremely low. Note this package will NOT restrict itself to use only cryptographically secure hash functions, so you should NOT use the fingerprint in security-sensitive contexts.

LICENSE

apache v2

known issues and limitations

fingerprint v1: pod aliasing issue

the pod fingerprinting algorithm v1 uses the namespace+name pair to identify a pod. In case of high pod churn when burstable or guaranteed pods get deleted and recreated with non-identical pod specs (e.g. changing pod resources requests/limits), the fingerprint will clash. So, two different set of pods will yield the same fingerprint. Future versions of the fingerprint will address this issue.

mitigations

Kubernetes best practices suggest to always use controllers, not "naked" pods. Kubernetes controllers will generate create unique names for pods, hence in this scenario the name clash described above should occur very rarely.

more details

The v1 fingerprint algorithm uses the namespace+name pair to identify a pod because of a conscious design decision due to a survey of the data source available to the perspective consumers of this package. Considering that the source of truth for resource allocation is the kubelet, and preferring node-local APIs, the agents running on the node have only few data source options:

• the pods kubelet endpoint: reports the full pod spec, but does not report the resource allocation.
• the podresources kubelet endpoint: to learn about resource allocation, but does not report the pod UID, only the namespace+name pair. Designing the v1 algo, we decided to create an API which we can used with only the data provided by the podresources endpoint. This is meant to avoid the perspective consumers of the package to avoid the impose the requirement to join these two data sources, preventing races and complications.

Documentation

Overview

Package podfingerprint computes the fingerprint of a set of pods. "Pods" is meant in the kubernetes sense: https://kubernetes.io/docs/concepts/workloads/pods/ but for the purposes of this package, a Pod is identified by just its namespace + name pair. A "fingerprint" is a compact unique representation of this set of pods. Any given unordered set of pods with the same elements will yield the same fingerprint, regardless of the order on which the pods are enumerated. The fingerprint is not actually unique because it is implemented using a hash function, but the collisions are expected to be extremely low. Note this package will *NOT* restrict itself to use only cryptographically secure hash functions, so you should NOT use the fingerprint in security-sensitive contexts.

Index

• Constants
• Variables
• func CleanCompletionSink()
• func IsVersionCompatible(ver string) (bool, error)
• func MarkCompleted(st Status) error
• func SetCompletionSink(ch chan<- Status)
• type Fingerprint
  • func NewFingerprint(size int) *Fingerprint
  • func (fp *Fingerprint) Add(namespace, name string) error
  • func (fp *Fingerprint) AddPod(pod PodIdentifier) error
  • func (fp *Fingerprint) Check(sign string) error
  • func (fp *Fingerprint) Reset(size int)
  • func (fp *Fingerprint) Sign() string
  • func (fp *Fingerprint) Sum() []byte
• type NamespacedName
  • func (nn NamespacedName) GetName() string
  • func (nn NamespacedName) GetNamespace() string
  • func (nn NamespacedName) String() string
• type NullTracer
  • func (nt NullTracer) Add(namespace, name string)
  • func (nt NullTracer) Check(expected string)
  • func (nt NullTracer) Sign(computed string)
  • func (nt NullTracer) Start(numPods int)
• type PodIdentifier
• type Status
  • func MakeStatus(nodeName string) Status
  • func (st *Status) Add(namespace, name string)
  • func (st *Status) Check(expected string)
  • func (st Status) Clone() Status
  • func (st Status) Repr() string
  • func (st *Status) Sign(computed string)
  • func (st *Status) Start(numPods int)
• type Tracer
• type TracingFingerprint
  • func NewTracingFingerprint(size int, tracer Tracer) *TracingFingerprint
  • func (tf *TracingFingerprint) Add(namespace, name string) error
  • func (tf *TracingFingerprint) AddPod(pod PodIdentifier) error
  • func (tf *TracingFingerprint) Check(sign string) error
  • func (tf *TracingFingerprint) Sign() string
  • func (tf *TracingFingerprint) Sum() []byte

Constants

const (
	// Prefix is the string common to all the fingerprints
	// A prefix is always 4 bytes long
	Prefix = "pfp0"
	// Version is the version of this fingerprint. You should
	// only compare compatible versions.
	// A Version is always 4 bytes long, in the form v\X\X\X
	Version = "v001"
	// Annotation is the recommended key to use to annotate objects
	// with the fingerprint.
	Annotation = "topology.node.k8s.io/fingerprint"
	// Attribute is the recommended attribute name to use in
	// NodeResourceTopology objects
	Attribute = "nodeTopologyPodsFingerprint"
	// AttributeMethod is the recommended attribute name to use
	// in NodeResourceTopology objects to declare how the
	// fingerprint was being computed
	AttributeMethod = "nodeTopologyPodsFingerprintMethod"
)

const (
	MethodAll                    = "all"                      // unrestricted. Just compute all the pods
	MethodWithExclusiveResources = "with-exclusive-resources" // only consider pods which require exclusive resources
)

Variables

var (
	ErrMalformed           = fmt.Errorf("malformed fingerprint")
	ErrIncompatibleVersion = fmt.Errorf("incompatible version")
	ErrSignatureMismatch   = fmt.Errorf("fingerprint mismatch")
)

Functions

func CleanCompletionSink

func CleanCompletionSink()

CleanCompletionSink should be used only in testing

func IsVersionCompatible

func IsVersionCompatible(ver string) (bool, error)

IsVersionCompatible check if this package is compatible with the provided fingerprint version. Returns bool if the fingerprint version and the package are compatible, false otherwise. Returns error if the fingerprint version cannot be safely decoded.

func MarkCompleted

func MarkCompleted(st Status) error

MarkCompleted sets a podfingerprint Status as completed. When a Status is completed, it means the Status and its fingerprint is considered sealed, so from now on only idempotent, non-state altering actions (like Repr(), Sign(), Check()) are expected to be performed. Applications which use the Tracing fingerprint can use this function to clearly signal this completion point and as another option to pass the Status to other subssystems.

func SetCompletionSink

func SetCompletionSink(ch chan<- Status)

SetCompletionSink sets the process-global completion destination

Types

type Fingerprint

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

Fingerprint represent the fingerprint of a set of pods

func NewFingerprint

func NewFingerprint(size int) *Fingerprint

NewFingerprint creates a empty Fingerprint. The size parameter is a hint for the expected size of the pod set. Use 0 if you don't know. Values of size < 0 are ignored.

func (*Fingerprint) Add

func (fp *Fingerprint) Add(namespace, name string) error

AddPod add a pod by its namespace/name pair to the pod set.

func (*Fingerprint) AddPod

func (fp *Fingerprint) AddPod(pod PodIdentifier) error

AddPod adds a pod to the pod set.

func (*Fingerprint) Check

func (fp *Fingerprint) Check(sign string) error

Check verifies if the provided fingerprint matches the current pod set. Returns nil if the verification holds, error otherwise, or if the fingerprint string is malformed.

func (*Fingerprint) Reset

func (fp *Fingerprint) Reset(size int)

Reset clears the internal state of the Fingerprint to empty (pristine) state. The size parameter is a hint for the expected size of the pod set. Use 0 if you don't know. Values of size < 0 are ignored. Explicit usage of this function is not recommended. Client code should not recycle Fingerprint objects, but rather discarded them after they are used - even though calling multiple times Sign() or Check() once reached steady state is perfectly fine.

func (*Fingerprint) Sign

func (fp *Fingerprint) Sign() string

Sign computes the pod set fingerprint as string. The string should be considered a opaque identifier and checked only for equality, or fed into Check

func (*Fingerprint) Sum

func (fp *Fingerprint) Sum() []byte

Sum computes the fingerprint of the *current* pod set as slice of bytes. It is legal to keep adding pods after calling Sum, but the fingerprint of the set will change. The output of Sum is guaranteed to be stable if the content of the pod set is stable.

type NamespacedName

type NamespacedName struct {
	Namespace string
	Name      string
}

NamespacedName is a Namespace/Name pair

func (NamespacedName) GetName

func (nn NamespacedName) GetName() string

func (NamespacedName) GetNamespace

func (nn NamespacedName) GetNamespace() string

func (NamespacedName) String

func (nn NamespacedName) String() string

type NullTracer

type NullTracer struct{}

NullTracer implements the Tracer interface and does nothing

func (NullTracer) Add

func (nt NullTracer) Add(namespace, name string)

func (NullTracer) Check

func (nt NullTracer) Check(expected string)

func (NullTracer) Sign

func (nt NullTracer) Sign(computed string)

func (NullTracer) Start

func (nt NullTracer) Start(numPods int)

type PodIdentifier

type PodIdentifier interface {
	GetNamespace() string
	GetName() string
}

PodIdentifier represent the minimal interface this package needs to identify a Pod

type Status

type Status struct {
	FingerprintExpected string           `json:"fingerprintExpected,omitempty"`
	FingerprintComputed string           `json:"fingerprintComputed,omitempty"`
	Pods                []NamespacedName `json:"pods,omitempty"`
	NodeName            string           `json:"nodeName,omitempty"`
}

Status represents the working status of a Fingerprint

func MakeStatus

func MakeStatus(nodeName string) Status

func (*Status) Add

func (st *Status) Add(namespace, name string)

func (*Status) Check

func (st *Status) Check(expected string)

func (Status) Clone

func (st Status) Clone() Status

func (Status) Repr

func (st Status) Repr() string

Repr represents the Status as compact yet human-friendly string

func (*Status) Sign

func (st *Status) Sign(computed string)

func (*Status) Start

func (st *Status) Start(numPods int)

type Tracer

type Tracer interface {
	// Start is called when the Fingerprint is initialized
	Start(numPods int)
	// Add is called when a new pod data is fed to the fingerprint,
	// respecting the invocation order (no reordering done)
	Add(namespace, name string)
	// Sign is called when the fingerprint is asked for the signature
	Sign(computed string)
	// Check is called when the fingerprint is asked to check
	Check(expected string)
}

Tracer tracks the actions needed to compute a fingerprint

type TracingFingerprint

type TracingFingerprint struct {
	Fingerprint
	// contains filtered or unexported fields
}

func NewTracingFingerprint

func NewTracingFingerprint(size int, tracer Tracer) *TracingFingerprint

NewTracingFingerprint creates a empty Fingerprint. The size parameter is a hint for the expected size of the pod set. Use 0 if you don't know. Values of size < 0 are ignored. The tracer parameter attach a tracer to this fingerprint. Client code can peek inside the fingerprint parameters, for debug purposes.

func (*TracingFingerprint) Add

func (tf *TracingFingerprint) Add(namespace, name string) error

AddPod add a pod by its namespace/name pair to the pod set.

func (*TracingFingerprint) AddPod

func (tf *TracingFingerprint) AddPod(pod PodIdentifier) error

AddPod adds a pod to the pod set.

func (*TracingFingerprint) Check

func (tf *TracingFingerprint) Check(sign string) error

Check verifies if the provided fingerprint matches the current pod set. Returns nil if the verification holds, error otherwise, or if the fingerprint string is malformed.

func (*TracingFingerprint) Sign

func (tf *TracingFingerprint) Sign() string

Sign computes the pod set fingerprint as string. The string should be considered a opaque identifier and checked only for equality, or fed into Check

func (*TracingFingerprint) Sum

func (tf *TracingFingerprint) Sum() []byte

Sum computes the fingerprint of the *current* pod set as slice of bytes. It is legal to keep adding pods after calling Sum, but the fingerprint of the set will change. The output of Sum is guaranteed to be stable if the content of the pod set is stable.