Repository: armadaproject/armada
Pull request #3512 (2024-04-12 12:21:05)

Scheduler: make taints and labels on Node immutable, intern their strings


Patch:
diff --git a/internal/scheduler/internaltypes/node.go b/internal/scheduler/internaltypes/node.go
index f71a8aa4..b7c516db 100644
--- a/internal/scheduler/internaltypes/node.go
+++ b/internal/scheduler/internaltypes/node.go
@@ -5,6 +5,8 @@ import (
 	v1 "k8s.io/api/core/v1"
 
 	armadamaps "github.com/armadaproject/armada/internal/common/maps"
+	"github.com/armadaproject/armada/internal/scheduler/kubernetesobjects/label"
+	koTaint "github.com/armadaproject/armada/internal/scheduler/kubernetesobjects/taint"
 	"github.com/armadaproject/armada/internal/scheduler/schedulerobjects"
 )
 
@@ -22,8 +24,8 @@ type Node struct {
 
 	// We need to store taints and labels separately from the node type: the latter only includes
 	// indexed taints and labels, but we need all of them when checking pod requirements.
-	Taints []v1.Taint
-	Labels map[string]string
+	taints []v1.Taint
+	labels map[string]string
 
 	TotalResources schedulerobjects.ResourceList
 
@@ -57,8 +59,8 @@ func CreateNode(
 		index:                 index,
 		executor:              executor,
 		name:                  name,
-		Taints:                taints,
-		Labels:                labels,
+		taints:                koTaint.DeepCopyTaints(taints),
+		labels:                deepCopyLabels(labels),
 		TotalResources:        totalResources,
 		AllocatableByPriority: allocatableByPriority,
 		AllocatedByQueue:      allocatedByQueue,
@@ -88,6 +90,35 @@ func (node *Node) GetNodeTypeId() uint64 {
 	return node.nodeTypeId
 }
 
+func (node *Node) GetLabels() map[string]string {
+	return deepCopyLabels(node.labels)
+}
+
+func (node *Node) GetLabelValue(key string) (string, bool) {
+	val, ok := node.labels[key]
+	return val, ok
+}
+
+func (node *Node) GetTaints() []v1.Taint {
+	return koTaint.DeepCopyTaints(node.taints)
+}
+
+func (node *Node) FindMatchingUntoleratedTaint(tolerations ...[]v1.Toleration) (v1.Taint, bool) {
+	return koTaint.FindMatchingUntoleratedTaint(node.taints, tolerations...)
+}
+
+func (node *Node) MatchNodeSelectorTerms(nodeSelector *v1.NodeSelector) (bool, error) {
+	return label.MatchNodeSelectorTerms(node.labels, nodeSelector)
+}
+
+func (node *Node) GetTolerationsForTaints() []v1.Toleration {
+	var tolerations []v1.Toleration
+	for _, taint := range node.taints {
+		tolerations = append(tolerations, v1.Toleration{Key: taint.Key, Value: taint.Value, Effect: taint.Effect})
+	}
+	return tolerations
+}
+
 // UnsafeCopy returns a pointer to a new value of type Node; it is unsafe because it only makes
 // shallow copies of fields that are not mutated by methods of NodeDb.
 func (node *Node) UnsafeCopy() *Node {
@@ -97,9 +128,8 @@ func (node *Node) UnsafeCopy() *Node {
 		executor:   node.executor,
 		name:       node.name,
 		nodeTypeId: node.nodeTypeId,
-
-		Taints: node.Taints,
-		Labels: node.Labels,
+		taints:     node.taints,
+		labels:     node.labels,
 
 		TotalResources: node.TotalResources,
 
@@ -111,3 +141,11 @@ func (node *Node) UnsafeCopy() *Node {
 		EvictedJobRunIds:      maps.Clone(node.EvictedJobRunIds),
 	}
 }
+
+func deepCopyLabels(labels map[string]string) map[string]string {
+	result := make(map[string]string, len(labels))
+	for k, v := range labels {
+		result[k] = v
+	}
+	return result
+}
diff --git a/internal/scheduler/jobdb/jobdb.go b/internal/scheduler/jobdb/jobdb.go
index 47e04527..ee066dcc 100644
--- a/internal/scheduler/jobdb/jobdb.go
+++ b/internal/scheduler/jobdb/jobdb.go
@@ -56,12 +56,12 @@ func (_ RealUUIDProvider) New() uuid.UUID {
 	return uuid.New()
 }
 
-func NewJobDb(priorityClasses map[string]types.PriorityClass, defaultPriorityClassName string, stringInternerCacheSize uint32) *JobDb {
+func NewJobDb(priorityClasses map[string]types.PriorityClass, defaultPriorityClassName string, stringInterner *stringinterner.StringInterner) *JobDb {
 	return NewJobDbWithSchedulingKeyGenerator(
 		priorityClasses,
 		defaultPriorityClassName,
 		schedulerobjects.NewSchedulingKeyGenerator(),
-		stringInternerCacheSize,
+		stringInterner,
 	)
 }
 
@@ -69,7 +69,7 @@ func NewJobDbWithSchedulingKeyGenerator(
 	priorityClasses map[string]types.PriorityClass,
 	defaultPriorityClassName string,
 	skg *schedulerobjects.SchedulingKeyGenerator,
-	stringInternerCacheSize uint32,
+	stringInterner *stringinterner.StringInterner,
 ) *JobDb {
 	defaultPriorityClass, ok := priorityClasses[defaultPriorityClassName]
 	if !ok {
@@ -84,7 +84,7 @@ func NewJobDbWithSchedulingKeyGenerator(
 		priorityClasses:        priorityClasses,
 		defaultPriorityClass:   defaultPriorityClass,
 		schedulingKeyGenerator: skg,
-		stringInterner:         stringinterner.New(stringInternerCacheSize),
+		stringInterner:         stringInterner,
 		clock:                  clock.RealClock{},
 		uuidProvider:           RealUUIDProvider{},
 	}
diff --git a/internal/scheduler/kubernetesobjects/label/label.go b/internal/scheduler/kubernetesobjects/label/label.go
new file mode 100644
index 00000000..f5de1b4b
--- /dev/null
+++ b/internal/scheduler/kubernetesobjects/label/label.go
@@ -0,0 +1,18 @@
+package label
+
+import (
+	v1 "k8s.io/api/core/v1"
+	metav1 "k8s.io/apimachinery/pkg/apis/meta/v1"
+	"k8s.io/component-helpers/scheduling/corev1"
+)
+
+func MatchNodeSelectorTerms(nodeLabels map[string]string, nodeSelector *v1.NodeSelector) (bool, error) {
+	return corev1.MatchNodeSelectorTerms(
+		&v1.Node{
+			ObjectMeta: metav1.ObjectMeta{
+				Labels: nodeLabels,
+			},
+		},
+		nodeSelector,
+	)
+}
diff --git a/internal/scheduler/kubernetesobjects/taint/taint.go b/internal/scheduler/kubernetesobjects/taint/taint.go
new file mode 100644
index 00000000..f7ba4abc
--- /dev/null
+++ b/internal/scheduler/kubernetesobjects/taint/taint.go
@@ -0,0 +1,58 @@
+package taint
+
+import (
+	v1 "k8s.io/api/core/v1"
+	metav1 "k8s.io/apimachinery/pkg/apis/meta/v1"
+	"k8s.io/component-helpers/scheduling/corev1"
+)
+
+func DeepCopyTaints(taints []v1.Taint) []v1.Taint {
+	return DeepCopyTaintsInternStrings(taints, func(s string) string { return s })
+}
+
+func DeepCopyTaint(taint *v1.Taint) v1.Taint {
+	return DeepCopyTaintInternStrings(taint, func(s string) string { return s })
+}
+
+func DeepCopyTaintsInternStrings(taints []v1.Taint, stringInterner func(string) string) []v1.Taint {
+	result := make([]v1.Taint, len(taints))
+	for i, taint := range taints {
+		result[i] = DeepCopyTaintInternStrings(&taint, stringInterner)
+	}
+	return result
+}
+
+func DeepCopyTaintInternStrings(taint *v1.Taint, stringInterner func(string) string) v1.Taint {
+	var pTimedAdded *metav1.Time = nil
+	if taint.TimeAdded != nil {
+		timedAdded := *taint.TimeAdded
+		pTimedAdded = &timedAdded
+	}
+
+	return v1.Taint{
+		Key:       stringInterner(taint.Key),
+		Value:     stringInterner(taint.Value),
+		Effect:    v1.TaintEffect(stringInterner(string(taint.Effect))),
+		TimeAdded: pTimedAdded,
+	}
+}
+
+// findMatchingUntoleratedTaint checks if the given tolerations tolerates
+// all the taints, and returns the first taint without a toleration.
+// Returns true if there is an untolerated taint.
+// Returns false if all taints are tolerated.
+func FindMatchingUntoleratedTaint(taints []v1.Taint, tolerations ...[]v1.Toleration) (v1.Taint, bool) {
+	for _, taint := range taints {
+		taintTolerated := false
+		for _, ts := range tolerations {
+			taintTolerated = taintTolerated || corev1.TolerationsTolerateTaint(ts, &taint)
+			if taintTolerated {
+				break
+			}
+		}
+		if !taintTolerated {
+			return DeepCopyTaint(&taint), true
+		}
+	}
+	return v1.Taint{}, false
+}
diff --git a/internal/scheduler/nodedb/nodedb.go b/internal/scheduler/nodedb/nodedb.go
index 8efacea9..a02dacf6 100644
--- a/internal/scheduler/nodedb/nodedb.go
+++ b/internal/scheduler/nodedb/nodedb.go
@@ -11,12 +11,12 @@ import (
 	"github.com/hashicorp/go-memdb"
 	"github.com/pkg/errors"
 	"golang.org/x/exp/maps"
-	"golang.org/x/exp/slices"
 	v1 "k8s.io/api/core/v1"
 	"k8s.io/apimachinery/pkg/api/resource"
 
 	"github.com/armadaproject/armada/internal/armada/configuration"
 	"github.com/armadaproject/armada/internal/common/armadaerrors"
+	"github.com/armadaproject/armada/internal/common/stringinterner"
 	"github.com/armadaproject/armada/internal/common/types"
 	"github.com/armadaproject/armada/internal/common/util"
 	schedulerconfig "github.com/armadaproject/armada/internal/scheduler/configuration"
@@ -24,6 +24,7 @@ import (
 	"github.com/armadaproject/armada/internal/scheduler/interfaces"
 	"github.com/armadaproject/armada/internal/scheduler/internaltypes"
 	"github.com/armadaproject/armada/internal/scheduler/jobdb"
+	koTaint "github.com/armadaproject/armada/internal/scheduler/kubernetesobjects/taint"
 	"github.com/armadaproject/armada/internal/scheduler/schedulerobjects"
 	"github.com/armadaproject/armada/pkg/api"
 )
@@ -41,13 +42,10 @@ var empty struct{}
 func (nodeDb *NodeDb) create(node *schedulerobjects.Node) (*internaltypes.Node, error) {
 	taints := node.GetTaints()
 	if node.Unschedulable {
-		taints = append(slices.Clone(taints), UnschedulableTaint())
+		taints = append(koTaint.DeepCopyTaintsInternStrings(taints, nodeDb.stringInterner.Intern), UnschedulableTaint())
 	}
 
-	labels := maps.Clone(node.GetLabels())
-	if labels == nil {
-		labels = make(map[string]string)
-	}
+	labels := nodeDb.copyMapWithIntern(node.GetLabels())
 	labels[schedulerconfig.NodeIdLabel] = node.Id
 
 	totalResources := node.TotalResources
@@ -115,6 +113,14 @@ func (nodeDb *NodeDb) create(node *schedulerobjects.Node) (*internaltypes.Node,
 		nil), nil
 }
 
+func (nodeDb *NodeDb) copyMapWithIntern(labels map[string]string) map[string]string {
+	result := make(map[string]string, len(labels))
+	for k, v := range labels {
+		result[nodeDb.stringInterner.Intern(k)] = nodeDb.stringInterner.Intern(v)
+	}
+	return result
+}
+
 func (nodeDb *NodeDb) CreateAndInsertWithApiJobsWithTxn(txn *memdb.Txn, jobs []*api.Job, node *schedulerobjects.Node) error {
 	entry, err := nodeDb.create(node)
 	if err != nil {
@@ -253,6 +259,8 @@ type NodeDb struct {
 	// delete entries from scheduledAtPriorityByJobId in general) and every
 	// scheduling round uses a fresh NodeDb.
 	scheduledAtPriorityByJobId map[string]int32
+
+	stringInterner *stringinterner.StringInterner
 }
 
 func NewNodeDb(
@@ -262,6 +270,7 @@ func NewNodeDb(
 	indexedTaints []string,
 	indexedNodeLabels []string,
 	wellKnownNodeTypes []configuration.WellKnownNodeType,
+	stringInterner *stringinterner.StringInterner,
 ) (*NodeDb, error) {
 	nodeDbPriorities := []int32{evictedPriority}
 	nodeDbPriorities = append(nodeDbPriorities, types.AllowedPriorities(priorityClasses)...)
@@ -322,6 +331,7 @@ func NewNodeDb(
 		podRequirementsNotMetReasonStringCache: make(map[uint64]string, 128),
 
 		scheduledAtPriorityByJobId: make(map[string]int32),
+		stringInterner:             stringInterner,
 	}
 
 	for _, wellKnownNodeType := range wellKnownNodeTypes {
@@ -793,7 +803,7 @@ func (nodeDb *NodeDb) selectNodeForPodWithItAtPriority(
 		if onlyCheckDynamicRequirements {
 			matches, score, reason = DynamicJobRequirementsMet(node.AllocatableByPriority[priority], jctx)
 		} else {
-			matches, score, reason, err = JobRequirementsMet(node.Taints, node.Labels, node.TotalResources, node.AllocatableByPriority[priority], jctx)
+			matches, score, reason, err = jobRequirementsMet(node, priority, jctx)
 		}
 		if err != nil {
 			return nil, err
@@ -866,14 +876,12 @@ func (nodeDb *NodeDb) selectNodeForJobWithFairPreemption(txn *memdb.Txn, jctx *s
 		if priority > maxPriority {
 			maxPriority = priority
 		}
-		matches, _, reason, err := JobRequirementsMet(
-			node.Taints,
-			node.Labels,
-			node.TotalResources,
+		matches, _, reason, err := jobRequirementsMet(
+			node,
 			// At this point, we've unbound the jobs running on the node.
 			// Hence, we should check if the job is schedulable at evictedPriority,
 			// since that indicates the job can be scheduled without causing further preemptions.
-			node.AllocatableByPriority[evictedPriority],
+			evictedPriority,
 			jctx,
 		)
 		if err != nil {
diff --git a/internal/scheduler/nodedb/nodematching.go b/internal/scheduler/nodedb/nodematching.go
index 7936d33f..963c20ef 100644
--- a/internal/scheduler/nodedb/nodematching.go
+++ b/internal/scheduler/nodedb/nodematching.go
@@ -6,10 +6,10 @@ import (
 	"github.com/segmentio/fasthash/fnv1a"
 	v1 "k8s.io/api/core/v1"
 	"k8s.io/apimachinery/pkg/api/resource"
-	metav1 "k8s.io/apimachinery/pkg/apis/meta/v1"
-	"k8s.io/component-helpers/scheduling/corev1"
 
 	schedulercontext "github.com/armadaproject/armada/internal/scheduler/context"
+	"github.com/armadaproject/armada/internal/scheduler/internaltypes"
+	koTaint "github.com/armadaproject/armada/internal/scheduler/kubernetesobjects/taint"
 	"github.com/armadaproject/armada/internal/scheduler/schedulerobjects"
 )
 
@@ -136,26 +136,32 @@ func NodeTypeJobRequirementsMet(nodeType *schedulerobjects.NodeType, jctx *sched
 		return matches, reason
 	}
 
-	matches, reason = NodeSelectorRequirementsMet(nodeType.GetLabels(), nodeType.GetUnsetIndexedLabels(), jctx.AdditionalNodeSelectors)
+	nodeTypeLabels := nodeType.GetLabels()
+	nodeTypeLabelGetter := func(key string) (string, bool) {
+		val, ok := nodeTypeLabels[key]
+		return val, ok
+	}
+
+	matches, reason = NodeSelectorRequirementsMet(nodeTypeLabelGetter, nodeType.GetUnsetIndexedLabels(), jctx.AdditionalNodeSelectors)
 	if !matches {
 		return matches, reason
 	}
 
-	return NodeSelectorRequirementsMet(nodeType.GetLabels(), nodeType.GetUnsetIndexedLabels(), jctx.PodRequirements.GetNodeSelector())
+	return NodeSelectorRequirementsMet(nodeTypeLabelGetter, nodeType.GetUnsetIndexedLabels(), jctx.PodRequirements.GetNodeSelector())
 }
 
-// JobRequirementsMet determines whether a job can be scheduled onto this node.
+// jobRequirementsMet determines whether a job can be scheduled onto this node.
 // If the pod can be scheduled, the returned score indicates how well the node fits:
 // - 0: Pod can be scheduled by preempting running pods.
 // - 1: Pod can be scheduled without preempting any running pods.
 // If the requirements are not met, it returns the reason why.
 // If the requirements can't be parsed, an error is returned.
-func JobRequirementsMet(taints []v1.Taint, labels map[string]string, totalResources schedulerobjects.ResourceList, allocatableResources schedulerobjects.ResourceList, jctx *schedulercontext.JobSchedulingContext) (bool, int, PodRequirementsNotMetReason, error) {
-	matches, reason, err := StaticJobRequirementsMet(taints, labels, totalResources, jctx)
+func jobRequirementsMet(node *internaltypes.Node, priority int32, jctx *schedulercontext.JobSchedulingContext) (bool, int, PodRequirementsNotMetReason, error) {
+	matches, reason, err := StaticJobRequirementsMet(node, jctx)
 	if !matches || err != nil {
 		return matches, 0, reason, err
 	}
-	matches, score, reason := DynamicJobRequirementsMet(allocatableResources, jctx)
+	matches, score, reason := DynamicJobRequirementsMet(node.AllocatableByPriority[priority], jctx)
 	if !matches {
 		return matches, 0, reason, nil
 	}
@@ -164,28 +170,28 @@ func JobRequirementsMet(taints []v1.Taint, labels map[string]string, totalResour
 
 // StaticJobRequirementsMet checks if a job can be scheduled onto this node,
 // accounting for taints, node selectors, node affinity, and total resources available on the node.
-func StaticJobRequirementsMet(taints []v1.Taint, labels map[string]string, totalResources schedulerobjects.ResourceList, jctx *schedulercontext.JobSchedulingContext) (bool, PodRequirementsNotMetReason, error) {
-	matches, reason := TolerationRequirementsMet(taints, jctx.AdditionalTolerations, jctx.PodRequirements.GetTolerations())
+func StaticJobRequirementsMet(node *internaltypes.Node, jctx *schedulercontext.JobSchedulingContext) (bool, PodRequirementsNotMetReason, error) {
+	matches, reason := NodeTolerationRequirementsMet(node, jctx.AdditionalTolerations, jctx.PodRequirements.GetTolerations())
 	if !matches {
 		return matches, reason, nil
 	}
 
-	matches, reason = NodeSelectorRequirementsMet(labels, nil, jctx.AdditionalNodeSelectors)
+	matches, reason = NodeSelectorRequirementsMet(node.GetLabelValue, nil, jctx.AdditionalNodeSelectors)
 	if !matches {
 		return matches, reason, nil
 	}
 
-	matches, reason = NodeSelectorRequirementsMet(labels, nil, jctx.PodRequirements.GetNodeSelector())
+	matches, reason = NodeSelectorRequirementsMet(node.GetLabelValue, nil, jctx.PodRequirements.GetNodeSelector())
 	if !matches {
 		return matches, reason, nil
 	}
 
-	matches, reason, err := NodeAffinityRequirementsMet(labels, jctx.PodRequirements.GetAffinityNodeSelector())
+	matches, reason, err := NodeAffinityRequirementsMet(node, jctx.PodRequirements.GetAffinityNodeSelector())
 	if !matches || err != nil {
 		return matches, reason, err
 	}
 
-	matches, reason = ResourceRequirementsMet(totalResources, jctx.PodRequirements.ResourceRequirements.Requests)
+	matches, reason = ResourceRequirementsMet(node.TotalResources, jctx.PodRequirements.ResourceRequirements.Requests)
 	if !matches {
 		return matches, reason, nil
 	}
@@ -201,37 +207,25 @@ func DynamicJobRequirementsMet(allocatableResources schedulerobjects.ResourceLis
 }
 
 func TolerationRequirementsMet(taints []v1.Taint, tolerations ...[]v1.Toleration) (bool, PodRequirementsNotMetReason) {
-	untoleratedTaint, hasUntoleratedTaint := findMatchingUntoleratedTaint(taints, tolerations...)
+	untoleratedTaint, hasUntoleratedTaint := koTaint.FindMatchingUntoleratedTaint(taints, tolerations...)
 	if hasUntoleratedTaint {
 		return false, &UntoleratedTaint{Taint: untoleratedTaint}
 	}
 	return true, nil
 }
 
-// findMatchingUntoleratedTaint checks if the given tolerations tolerates
-// all the taints, and returns the first taint without a toleration.
-// Returns true if there is an untolerated taint.
-// Returns false if all taints are tolerated.
-func findMatchingUntoleratedTaint(taints []v1.Taint, tolerations ...[]v1.Toleration) (v1.Taint, bool) {
-	for _, taint := range taints {
-		taintTolerated := false
-		for _, ts := range tolerations {
-			taintTolerated = taintTolerated || corev1.TolerationsTolerateTaint(ts, &taint)
-			if taintTolerated {
-				break
-			}
-		}
-		if !taintTolerated {
-			return taint, true
-		}
+func NodeTolerationRequirementsMet(node *internaltypes.Node, tolerations ...[]v1.Toleration) (bool, PodRequirementsNotMetReason) {
+	untoleratedTaint, hasUntoleratedTaint := node.FindMatchingUntoleratedTaint(tolerations...)
+	if hasUntoleratedTaint {
+		return false, &UntoleratedTaint{Taint: untoleratedTaint}
 	}
-	return v1.Taint{}, false
+	return true, nil
 }
 
-func NodeSelectorRequirementsMet(nodeLabels, unsetIndexedLabels, nodeSelector map[string]string) (bool, PodRequirementsNotMetReason) {
+func NodeSelectorRequirementsMet(nodeLabelGetter func(string) (string, bool), unsetIndexedLabels, nodeSelector map[string]string) (bool, PodRequirementsNotMetReason) {
 	for label, podValue := range nodeSelector {
 		// If the label value differs between nodeLabels and the pod, always return false.
-		if nodeValue, ok := nodeLabels[label]; ok {
+		if nodeValue, ok := nodeLabelGetter(label); ok {
 			if nodeValue != podValue {
 				return false, &UnmatchedLabel{
 					Label:     label,
@@ -255,16 +249,9 @@ func NodeSelectorRequirementsMet(nodeLabels, unsetIndexedLabels, nodeSelector ma
 	return true, nil
 }
 
-func NodeAffinityRequirementsMet(nodeLabels map[string]string, nodeSelector *v1.NodeSelector) (bool, PodRequirementsNotMetReason, error) {
+func NodeAffinityRequirementsMet(node *internaltypes.Node, nodeSelector *v1.NodeSelector) (bool, PodRequirementsNotMetReason, error) {
 	if nodeSelector != nil {
-		matchesNodeSelector, err := corev1.MatchNodeSelectorTerms(
-			&v1.Node{
-				ObjectMeta: metav1.ObjectMeta{
-					Labels: nodeLabels,
-				},
-			},
-			nodeSelector,
-		)
+		matchesNodeSelector, err := node.MatchNodeSelectorTerms(nodeSelector)
 		if err != nil {
 			return false, nil, err
 		}
diff --git a/internal/scheduler/pool_assigner.go b/internal/scheduler/pool_assigner.go
index 83e6f60a..556d6eea 100644
--- a/internal/scheduler/pool_assigner.go
+++ b/internal/scheduler/pool_assigner.go
@@ -10,6 +10,7 @@ import (
 
 	"github.com/armadaproject/armada/internal/armada/configuration"
 	"github.com/armadaproject/armada/internal/common/armadacontext"
+	"github.com/armadaproject/armada/internal/common/stringinterner"
 	"github.com/armadaproject/armada/internal/common/types"
 	"github.com/armadaproject/armada/internal/scheduler/constraints"
 	schedulercontext "github.com/armadaproject/armada/internal/scheduler/context"
@@ -160,6 +161,7 @@ func (p *DefaultPoolAssigner) constructNodeDb(nodes []*schedulerobjects.Node) (*
 		p.indexedTaints,
 		p.indexedNodeLabels,
 		p.wellKnownNodeTypes,
+		stringinterner.New(1024),
 	)
 	if err != nil {
 		return nil, err
diff --git a/internal/scheduler/preempting_queue_scheduler.go b/internal/scheduler/preempting_queue_scheduler.go
index 8261e13f..a1c4f886 100644
--- a/internal/scheduler/preempting_queue_scheduler.go
+++ b/internal/scheduler/preempting_queue_scheduler.go
@@ -9,7 +9,6 @@ import (
 	"github.com/pkg/errors"
 	"golang.org/x/exp/maps"
 	"golang.org/x/exp/slices"
-	v1 "k8s.io/api/core/v1"
 	"k8s.io/apimachinery/pkg/api/resource"
 
 	"github.com/armadaproject/armada/internal/common/armadacontext"
@@ -865,9 +864,7 @@ func (evi *Evictor) Evict(ctx *armadacontext.Context, nodeDbTxn *memdb.Txn) (*Ev
 			jctx.IsEvicted = true
 			jctx.AddNodeSelector(schedulerconfig.NodeIdLabel, node.GetId())
 			evictedJctxsByJobId[job.GetId()] = jctx
-			for _, taint := range node.Taints {
-				jctx.AdditionalTolerations = append(jctx.AdditionalTolerations, v1.Toleration{Key: taint.Key, Value: taint.Value, Effect: taint.Effect})
-			}
+			jctx.AdditionalTolerations = append(jctx.AdditionalTolerations, node.GetTolerationsForTaints()...)
 
 			nodeIdByJobId[job.GetId()] = node.GetId()
 		}
diff --git a/internal/scheduler/schedulerapp.go b/internal/scheduler/schedulerapp.go
index 2f601abb..600a5465 100644
--- a/internal/scheduler/schedulerapp.go
+++ b/internal/scheduler/schedulerapp.go
@@ -31,6 +31,7 @@ import (
 	"github.com/armadaproject/armada/internal/common/profiling"
 	"github.com/armadaproject/armada/internal/common/pulsarutils"
 	"github.com/armadaproject/armada/internal/common/serve"
+	"github.com/armadaproject/armada/internal/common/stringinterner"
 	"github.com/armadaproject/armada/internal/common/types"
 	schedulerconfig "github.com/armadaproject/armada/internal/scheduler/configuration"
 	"github.com/armadaproject/armada/internal/scheduler/database"
@@ -240,6 +241,7 @@ func Run(config schedulerconfig.Configuration) error {
 		return errors.WithStack(err)
 	}
 
+	stringInterner := stringinterner.New(config.InternedStringsCacheSize)
 	schedulingAlgo, err := NewFairSchedulingAlgo(
 		config.Scheduling,
 		config.MaxSchedulingDuration,
@@ -248,6 +250,7 @@ func Run(config schedulerconfig.Configuration) error {
 		schedulingContextRepository,
 		nodeQuarantiner,
 		queueQuarantiner,
+		stringInterner,
 	)
 	if err != nil {
 		return errors.WithMessage(err, "error creating scheduling algo")
@@ -255,7 +258,7 @@ func Run(config schedulerconfig.Configuration) error {
 	jobDb := jobdb.NewJobDb(
 		config.Scheduling.PriorityClasses,
 		config.Scheduling.DefaultPriorityClassName,
-		config.InternedStringsCacheSize,
+		stringInterner,
 	)
 	schedulingRoundMetrics := NewSchedulerMetrics(config.Metrics.Metrics)
 	if err := prometheus.Register(schedulingRoundMetrics); err != nil {
diff --git a/internal/scheduler/scheduling_algo.go b/internal/scheduler/scheduling_algo.go
index 77719461..dce7a873 100644
--- a/internal/scheduler/scheduling_algo.go
+++ b/internal/scheduler/scheduling_algo.go
@@ -19,6 +19,7 @@ import (
 	"github.com/armadaproject/armada/internal/common/armadacontext"
 	"github.com/armadaproject/armada/internal/common/logging"
 	armadaslices "github.com/armadaproject/armada/internal/common/slices"
+	"github.com/armadaproject/armada/internal/common/stringinterner"
 	"github.com/armadaproject/armada/internal/common/util"
 	schedulerconstraints "github.com/armadaproject/armada/internal/scheduler/constraints"
 	schedulercontext "github.com/armadaproject/armada/internal/scheduler/context"
@@ -63,8 +64,9 @@ type FairSchedulingAlgo struct {
 	// Function that is called every time an executor is scheduled. Useful for testing.
 	onExecutorScheduled func(executor *schedulerobjects.Executor)
 	// rand and clock injected here for repeatable testing.
-	rand  *rand.Rand
-	clock clock.Clock
+	rand           *rand.Rand
+	clock          clock.Clock
+	stringInterner *stringinterner.StringInterner
 }
 
 func NewFairSchedulingAlgo(
@@ -75,6 +77,7 @@ func NewFairSchedulingAlgo(
 	schedulingContextRepository *reports.SchedulingContextRepository,
 	nodeQuarantiner *quarantine.NodeQuarantiner,
 	queueQuarantiner *quarantine.QueueQuarantiner,
+	stringInterner *stringinterner.StringInterner,
 ) (*FairSchedulingAlgo, error) {
 	if _, ok := config.PriorityClasses[config.DefaultPriorityClassName]; !ok {
 		return nil, errors.Errorf(
@@ -95,6 +98,7 @@ func NewFairSchedulingAlgo(
 		onExecutorScheduled:         func(executor *schedulerobjects.Executor) {},
 		rand:                        util.NewThreadsafeRand(time.Now().UnixNano()),
 		clock:                       clock.RealClock{},
+		stringInterner:              stringInterner,
 	}, nil
 }
 
@@ -352,6 +356,7 @@ func (l *FairSchedulingAlgo) scheduleOnExecutors(
 		l.schedulingConfig.IndexedTaints,
 		l.schedulingConfig.IndexedNodeLabels,
 		l.schedulingConfig.WellKnownNodeTypes,
+		l.stringInterner,
 	)
 	if err != nil {
 		return nil, nil, err
diff --git a/internal/scheduler/simulator/simulator.go b/internal/scheduler/simulator/simulator.go
index 134ad0e4..39b468e0 100644
--- a/internal/scheduler/simulator/simulator.go
+++ b/internal/scheduler/simulator/simulator.go
@@ -19,6 +19,7 @@ import (
 	"github.com/armadaproject/armada/internal/common/armadacontext"
 	"github.com/armadaproject/armada/internal/common/logging"
 	armadaslices "github.com/armadaproject/armada/internal/common/slices"
+	"github.com/armadaproject/armada/internal/common/stringinterner"
 	"github.com/armadaproject/armada/internal/common/types"
 	"github.com/armadaproject/armada/internal/common/util"
 	"github.com/armadaproject/armada/internal/scheduler"
@@ -101,7 +102,7 @@ func NewSimulator(clusterSpec *ClusterSpec, workloadSpec *WorkloadSpec, scheduli
 	jobDb := jobdb.NewJobDb(
 		schedulingConfig.PriorityClasses,
 		schedulingConfig.DefaultPriorityClassName,
-		1024,
+		stringinterner.New(1024),
 	)
 	randomSeed := workloadSpec.RandomSeed
 	if randomSeed == 0 {
@@ -229,6 +230,7 @@ func (s *Simulator) setupClusters() error {
 				s.schedulingConfig.IndexedTaints,
 				s.schedulingConfig.IndexedNodeLabels,
 				s.schedulingConfig.WellKnownNodeTypes,
+				stringinterner.New(1024),
 			)
 			if err != nil {
 				return err
diff --git a/internal/scheduler/submitcheck.go b/internal/scheduler/submitcheck.go
index 9b7e2bd5..d8a6a52b 100644
--- a/internal/scheduler/submitcheck.go
+++ b/internal/scheduler/submitcheck.go
@@ -6,6 +6,8 @@ import (
 	"sync"
 	"time"
 
+	"github.com/armadaproject/armada/internal/common/stringinterner"
+
 	lru "github.com/hashicorp/golang-lru"
 	"github.com/pkg/errors"
 	"golang.org/x/exp/maps"
@@ -282,6 +284,7 @@ func (srv *SubmitChecker) constructNodeDb(nodes []*schedulerobjects.Node) (*node
 		srv.indexedTaints,
 		srv.indexedNodeLabels,
 		srv.wellKnownNodeTypes,
+		stringinterner.New(512),
 	)
 	if err != nil {
 		return nil, err


Test patch:
diff --git a/internal/scheduler/gang_scheduler_test.go b/internal/scheduler/gang_scheduler_test.go
index 8d02a070..e72453ec 100644
--- a/internal/scheduler/gang_scheduler_test.go
+++ b/internal/scheduler/gang_scheduler_test.go
@@ -14,6 +14,7 @@ import (
 	"github.com/armadaproject/armada/internal/armada/configuration"
 	"github.com/armadaproject/armada/internal/common/armadacontext"
 	armadaslices "github.com/armadaproject/armada/internal/common/slices"
+	"github.com/armadaproject/armada/internal/common/stringinterner"
 	"github.com/armadaproject/armada/internal/common/types"
 	"github.com/armadaproject/armada/internal/common/util"
 	schedulerconstraints "github.com/armadaproject/armada/internal/scheduler/constraints"
@@ -578,6 +579,7 @@ func TestGangScheduler(t *testing.T) {
 				tc.SchedulingConfig.IndexedTaints,
 				tc.SchedulingConfig.IndexedNodeLabels,
 				tc.SchedulingConfig.WellKnownNodeTypes,
+				stringinterner.New(1024),
 			)
 			require.NoError(t, err)
 			txn := nodeDb.Txn(true)
diff --git a/internal/scheduler/internaltypes/node_test.go b/internal/scheduler/internaltypes/node_test.go
index dcfd1415..f58eedfb 100644
--- a/internal/scheduler/internaltypes/node_test.go
+++ b/internal/scheduler/internaltypes/node_test.go
@@ -98,14 +98,25 @@ func TestNode(t *testing.T) {
 	assert.Equal(t, index, node.GetIndex())
 	assert.Equal(t, executor, node.GetExecutor())
 	assert.Equal(t, name, node.GetName())
-	assert.Equal(t, taints, node.Taints)
-	assert.Equal(t, labels, node.Labels)
+	assert.Equal(t, taints, node.GetTaints())
+	assert.Equal(t, labels, node.GetLabels())
 	assert.Equal(t, totalResources, node.TotalResources)
 	assert.Equal(t, allocatableByPriority, node.AllocatableByPriority)
 	assert.Equal(t, allocatedByQueue, node.AllocatedByQueue)
 	assert.Equal(t, allocatedByJobId, node.AllocatedByJobId)
 	assert.Equal(t, keys, node.Keys)
 
+	val, ok := node.GetLabelValue("key")
+	assert.True(t, ok)
+	assert.Equal(t, "value", val)
+
+	val, ok = node.GetLabelValue("missing")
+	assert.False(t, ok)
+	assert.Empty(t, val)
+
+	tolerations := node.GetTolerationsForTaints()
+	assert.Equal(t, []v1.Toleration{{Key: "foo", Value: "bar"}}, tolerations)
+
 	nodeCopy := node.UnsafeCopy()
 	node.Keys = nil // UnsafeCopy() sets Keys to nil
 	assert.Equal(t, node, nodeCopy)
diff --git a/internal/scheduler/jobdb/comparison_test.go b/internal/scheduler/jobdb/comparison_test.go
index 84735444..5ebcf816 100644
--- a/internal/scheduler/jobdb/comparison_test.go
+++ b/internal/scheduler/jobdb/comparison_test.go
@@ -5,6 +5,7 @@ import (
 
 	"github.com/stretchr/testify/assert"
 
+	"github.com/armadaproject/armada/internal/common/stringinterner"
 	"github.com/armadaproject/armada/internal/common/types"
 )
 
@@ -51,7 +52,7 @@ func TestJobPriorityComparer(t *testing.T) {
 		},
 		"Running jobs come before queued jobs": {
 			a:        &Job{id: "a", priority: 1},
-			b:        (&Job{id: "b", priority: 2, jobDb: NewJobDb(map[string]types.PriorityClass{"foo": {}}, "foo", 1)}).WithNewRun("", "", "", 0),
+			b:        (&Job{id: "b", priority: 2, jobDb: NewJobDb(map[string]types.PriorityClass{"foo": {}}, "foo", stringinterner.New(1))}).WithNewRun("", "", "", 0),
 			expected: 1,
 		},
 		"Running jobs are ordered third by runtime": {
diff --git a/internal/scheduler/jobdb/job_run_test.go b/internal/scheduler/jobdb/job_run_test.go
index 66159b7f..e3cec287 100644
--- a/internal/scheduler/jobdb/job_run_test.go
+++ b/internal/scheduler/jobdb/job_run_test.go
@@ -6,6 +6,7 @@ import (
 	"github.com/google/uuid"
 	"github.com/stretchr/testify/assert"
 
+	"github.com/armadaproject/armada/internal/common/stringinterner"
 	"github.com/armadaproject/armada/internal/common/types"
 	"github.com/armadaproject/armada/internal/scheduler/schedulerobjects"
 )
@@ -32,7 +33,7 @@ var (
 		TestPriorityClasses,
 		TestDefaultPriorityClass,
 		SchedulingKeyGenerator,
-		1024,
+		stringinterner.New(1024),
 	)
 	scheduledAtPriority = int32(5)
 )
diff --git a/internal/scheduler/jobdb/jobdb_test.go b/internal/scheduler/jobdb/jobdb_test.go
index eda76e4e..d0fb9756 100644
--- a/internal/scheduler/jobdb/jobdb_test.go
+++ b/internal/scheduler/jobdb/jobdb_test.go
@@ -14,6 +14,7 @@ import (
 	metav1 "k8s.io/apimachinery/pkg/apis/meta/v1"
 	"k8s.io/utils/pointer"
 
+	"github.com/armadaproject/armada/internal/common/stringinterner"
 	"github.com/armadaproject/armada/internal/common/types"
 	"github.com/armadaproject/armada/internal/common/util"
 	"github.com/armadaproject/armada/internal/scheduler/interfaces"
@@ -27,7 +28,7 @@ func NewTestJobDb() *JobDb {
 			"bar": {},
 		},
 		"foo",
-		1024,
+		stringinterner.New(1024),
 	)
 }
 
diff --git a/internal/scheduler/kubernetesobjects/label/label_test.go b/internal/scheduler/kubernetesobjects/label/label_test.go
new file mode 100644
index 00000000..3e513660
--- /dev/null
+++ b/internal/scheduler/kubernetesobjects/label/label_test.go
@@ -0,0 +1,30 @@
+package label
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+	v1 "k8s.io/api/core/v1"
+)
+
+func TestMatchNodeSelectorTermsMatch(t *testing.T) {
+	result, err := MatchNodeSelectorTerms(map[string]string{"key": "val"}, testNodeSelector())
+	assert.True(t, result)
+	assert.Nil(t, err)
+}
+
+func TestMatchNodeSelectorTermsNoMatch(t *testing.T) {
+	result, err := MatchNodeSelectorTerms(map[string]string{"key": "missing-val"}, testNodeSelector())
+	assert.False(t, result)
+	assert.Nil(t, err)
+}
+
+func testNodeSelector() *v1.NodeSelector {
+	return &v1.NodeSelector{
+		NodeSelectorTerms: []v1.NodeSelectorTerm{
+			{
+				MatchExpressions: []v1.NodeSelectorRequirement{{Key: "key", Operator: v1.NodeSelectorOpIn, Values: []string{"val"}}},
+			},
+		},
+	}
+}
diff --git a/internal/scheduler/kubernetesobjects/taint/taint_test.go b/internal/scheduler/kubernetesobjects/taint/taint_test.go
new file mode 100644
index 00000000..3655f038
--- /dev/null
+++ b/internal/scheduler/kubernetesobjects/taint/taint_test.go
@@ -0,0 +1,46 @@
+package taint
+
+import (
+	"testing"
+	"time"
+
+	"github.com/stretchr/testify/assert"
+	v1 "k8s.io/api/core/v1"
+	metav1 "k8s.io/apimachinery/pkg/apis/meta/v1"
+)
+
+var testTaints = []v1.Taint{
+	{Key: "key1", Value: "val", Effect: v1.TaintEffectNoSchedule, TimeAdded: nil},
+	{Key: "key2", Value: "val", Effect: v1.TaintEffectNoExecute, TimeAdded: &metav1.Time{time.Now()}},
+}
+
+func TestDeepCopy(t *testing.T) {
+	assert.Equal(t, testTaints[0], DeepCopyTaint(&testTaints[0]))
+	assert.Equal(t, testTaints, DeepCopyTaints(testTaints))
+}
+
+func TestDeepCopyInternStrings(t *testing.T) {
+	seen := map[string]bool{}
+	addToSeen := func(s string) string { seen[s] = true; return s }
+	assert.Equal(t, testTaints[0], DeepCopyTaintInternStrings(&testTaints[0], addToSeen))
+	assert.Equal(t, testTaints, DeepCopyTaintsInternStrings(testTaints, addToSeen))
+	assert.Equal(t, map[string]bool{"NoExecute": true, "NoSchedule": true, "key1": true, "key2": true, "val": true}, seen)
+}
+
+func TestFindMatchingUntoleratedTaint_AllTolerated(t *testing.T) {
+	firstTaintFound, found := FindMatchingUntoleratedTaint(testTaints, []v1.Toleration{
+		{Key: "key1", Value: "val", Effect: v1.TaintEffectNoSchedule, Operator: v1.TolerationOpEqual},
+		{Key: "key2", Value: "val", Effect: v1.TaintEffectNoExecute, Operator: v1.TolerationOpEqual},
+	})
+	assert.Empty(t, firstTaintFound.Key)
+	assert.Empty(t, firstTaintFound.Value)
+	assert.False(t, found)
+}
+
+func TestFindMatchingUntoleratedTaint_OneTolerated(t *testing.T) {
+	firstTaintFound, found := FindMatchingUntoleratedTaint(testTaints, []v1.Toleration{
+		{Key: "key1", Value: "val", Effect: v1.TaintEffectNoSchedule, Operator: v1.TolerationOpEqual},
+	})
+	assert.Equal(t, testTaints[1], firstTaintFound)
+	assert.True(t, found)
+}
diff --git a/internal/scheduler/nodedb/nodedb_test.go b/internal/scheduler/nodedb/nodedb_test.go
index 989e14d5..a66eda3b 100644
--- a/internal/scheduler/nodedb/nodedb_test.go
+++ b/internal/scheduler/nodedb/nodedb_test.go
@@ -12,6 +12,7 @@ import (
 
 	"github.com/armadaproject/armada/internal/armada/configuration"
 	armadamaps "github.com/armadaproject/armada/internal/common/maps"
+	"github.com/armadaproject/armada/internal/common/stringinterner"
 	"github.com/armadaproject/armada/internal/common/types"
 	"github.com/armadaproject/armada/internal/common/util"
 	schedulerconfig "github.com/armadaproject/armada/internal/scheduler/configuration"
@@ -590,6 +591,7 @@ func TestAwayNodeTypes(t *testing.T) {
 				},
 			},
 		},
+		stringinterner.New(1024),
 	)
 	require.NoError(t, err)
 
@@ -640,6 +642,7 @@ func benchmarkUpsert(nodes []*schedulerobjects.Node, b *testing.B) {
 		testfixtures.TestIndexedTaints,
 		testfixtures.TestIndexedNodeLabels,
 		testfixtures.TestWellKnownNodeTypes,
+		stringinterner.New(1024),
 	)
 	require.NoError(b, err)
 	txn := nodeDb.Txn(true)
@@ -679,6 +682,7 @@ func benchmarkScheduleMany(b *testing.B, nodes []*schedulerobjects.Node, jobs []
 		testfixtures.TestIndexedTaints,
 		testfixtures.TestIndexedNodeLabels,
 		testfixtures.TestWellKnownNodeTypes,
+		stringinterner.New(1024),
 	)
 	require.NoError(b, err)
 	txn := nodeDb.Txn(true)
@@ -804,6 +808,7 @@ func newNodeDbWithNodes(nodes []*schedulerobjects.Node) (*NodeDb, error) {
 		testfixtures.TestIndexedTaints,
 		testfixtures.TestIndexedNodeLabels,
 		testfixtures.TestWellKnownNodeTypes,
+		stringinterner.New(1024),
 	)
 	if err != nil {
 		return nil, err
diff --git a/internal/scheduler/nodedb/nodeiteration_test.go b/internal/scheduler/nodedb/nodeiteration_test.go
index 699628fc..2700fff0 100644
--- a/internal/scheduler/nodedb/nodeiteration_test.go
+++ b/internal/scheduler/nodedb/nodeiteration_test.go
@@ -926,8 +926,8 @@ func testWithNodeTypeId(node *internaltypes.Node, nodeTypeId uint64) *internalty
 		node.GetIndex(),
 		node.GetExecutor(),
 		node.GetName(),
-		node.Taints,
-		node.Labels,
+		node.GetTaints(),
+		node.GetLabels(),
 		node.TotalResources,
 		node.AllocatableByPriority,
 		node.AllocatedByQueue,
diff --git a/internal/scheduler/nodedb/nodematching_test.go b/internal/scheduler/nodedb/nodematching_test.go
index d2ef5f35..82569e04 100644
--- a/internal/scheduler/nodedb/nodematching_test.go
+++ b/internal/scheduler/nodedb/nodematching_test.go
@@ -8,17 +8,18 @@ import (
 	"k8s.io/apimachinery/pkg/api/resource"
 
 	schedulercontext "github.com/armadaproject/armada/internal/scheduler/context"
+	"github.com/armadaproject/armada/internal/scheduler/internaltypes"
 	"github.com/armadaproject/armada/internal/scheduler/schedulerobjects"
 )
 
 func TestNodeSchedulingRequirementsMet(t *testing.T) {
 	tests := map[string]struct {
-		node          *schedulerobjects.Node
+		node          *internaltypes.Node
 		req           *schedulerobjects.PodRequirements
 		expectSuccess bool
 	}{
 		"nil taints and labels": {
-			node: &schedulerobjects.Node{},
+			node: makeTestNodeTaintsLabels(nil, nil),
 			req: &schedulerobjects.PodRequirements{
 				Tolerations: []v1.Toleration{{Key: "foo", Value: "foo"}},
 				Affinity: &v1.Affinity{
@@ -42,10 +43,7 @@ func TestNodeSchedulingRequirementsMet(t *testing.T) {
 			expectSuccess: false,
 		},
 		"no taints or labels": {
-			node: &schedulerobjects.Node{
-				Taints: make([]v1.Taint, 0),
-				Labels: make(map[string]string),
-			},
+			node: makeTestNodeTaintsLabels(make([]v1.Taint, 0), make(map[string]string)),
 			req: &schedulerobjects.PodRequirements{
 				Tolerations: []v1.Toleration{{Key: "foo", Value: "foo"}},
 				Affinity: &v1.Affinity{
@@ -69,28 +67,28 @@ func TestNodeSchedulingRequirementsMet(t *testing.T) {
 			expectSuccess: false,
 		},
 		"tolerated taints": {
-			node: &schedulerobjects.Node{
-				Taints: []v1.Taint{{Key: "foo", Value: "foo", Effect: v1.TaintEffectNoSchedule}},
-				Labels: nil,
-			},
+			node: makeTestNodeTaintsLabels(
+				[]v1.Taint{{Key: "foo", Value: "foo", Effect: v1.TaintEffectNoSchedule}},
+				nil,
+			),
 			req: &schedulerobjects.PodRequirements{
 				Tolerations: []v1.Toleration{{Key: "foo", Value: "foo"}},
 			},
 			expectSuccess: true,
 		},
 		"untolerated taints": {
-			node: &schedulerobjects.Node{
-				Taints: []v1.Taint{{Key: "foo", Value: "foo", Effect: v1.TaintEffectNoSchedule}},
-				Labels: nil,
-			},
+			node: makeTestNodeTaintsLabels(
+				[]v1.Taint{{Key: "foo", Value: "foo", Effect: v1.TaintEffectNoSchedule}},
+				nil,
+			),
 			req:           &schedulerobjects.PodRequirements{},
 			expectSuccess: false,
 		},
 		"matched node affinity": {
-			node: &schedulerobjects.Node{
-				Taints: nil,
-				Labels: map[string]string{"bar": "bar"},
-			},
+			node: makeTestNodeTaintsLabels(
+				nil,
+				map[string]string{"bar": "bar"},
+			),
 			req: &schedulerobjects.PodRequirements{
 				Affinity: &v1.Affinity{
 					NodeAffinity: &v1.NodeAffinity{
@@ -113,7 +111,7 @@ func TestNodeSchedulingRequirementsMet(t *testing.T) {
 			expectSuccess: true,
 		},
 		"unmatched node affinity": {
-			node: &schedulerobjects.Node{},
+			node: makeTestNodeTaintsLabels(nil, nil),
 			req: &schedulerobjects.PodRequirements{
 				Affinity: &v1.Affinity{
 					NodeAffinity: &v1.NodeAffinity{
@@ -136,10 +134,10 @@ func TestNodeSchedulingRequirementsMet(t *testing.T) {
 			expectSuccess: false,
 		},
 		"tolerated taints and matched node affinity": {
-			node: &schedulerobjects.Node{
-				Taints: []v1.Taint{{Key: "foo", Value: "foo", Effect: v1.TaintEffectNoSchedule}},
-				Labels: map[string]string{"bar": "bar"},
-			},
+			node: makeTestNodeTaintsLabels(
+				[]v1.Taint{{Key: "foo", Value: "foo", Effect: v1.TaintEffectNoSchedule}},
+				map[string]string{"bar": "bar"},
+			),
 			req: &schedulerobjects.PodRequirements{
 				Tolerations: []v1.Toleration{{Key: "foo", Value: "foo"}},
 				Affinity: &v1.Affinity{
@@ -163,10 +161,10 @@ func TestNodeSchedulingRequirementsMet(t *testing.T) {
 			expectSuccess: true,
 		},
 		"untolerated taints and matched node affinity": {
-			node: &schedulerobjects.Node{
-				Taints: []v1.Taint{{Key: "foo", Value: "foo", Effect: v1.TaintEffectNoSchedule}},
-				Labels: map[string]string{"bar": "bar"},
-			},
+			node: makeTestNodeTaintsLabels(
+				[]v1.Taint{{Key: "foo", Value: "foo", Effect: v1.TaintEffectNoSchedule}},
+				map[string]string{"bar": "bar"},
+			),
 			req: &schedulerobjects.PodRequirements{
 				Affinity: &v1.Affinity{
 					NodeAffinity: &v1.NodeAffinity{
@@ -189,10 +187,10 @@ func TestNodeSchedulingRequirementsMet(t *testing.T) {
 			expectSuccess: false,
 		},
 		"tolerated taints and unmatched node affinity": {
-			node: &schedulerobjects.Node{
-				Taints: []v1.Taint{{Key: "foo", Value: "foo", Effect: v1.TaintEffectNoSchedule}},
-				Labels: nil,
-			},
+			node: makeTestNodeTaintsLabels(
+				[]v1.Taint{{Key: "foo", Value: "foo", Effect: v1.TaintEffectNoSchedule}},
+				nil,
+			),
 			req: &schedulerobjects.PodRequirements{
 				Tolerations: []v1.Toleration{{Key: "foo", Value: "foo"}},
 				Affinity: &v1.Affinity{
@@ -216,27 +214,27 @@ func TestNodeSchedulingRequirementsMet(t *testing.T) {
 			expectSuccess: false,
 		},
 		"matched node selector": {
-			node: &schedulerobjects.Node{
-				Taints: nil,
-				Labels: map[string]string{"bar": "bar"},
-			},
+			node: makeTestNodeTaintsLabels(
+				nil,
+				map[string]string{"bar": "bar"},
+			),
 			req: &schedulerobjects.PodRequirements{
 				NodeSelector: map[string]string{"bar": "bar"},
 			},
 			expectSuccess: true,
 		},
 		"unmatched node selector": {
-			node: &schedulerobjects.Node{},
+			node: makeTestNodeTaintsLabels(nil, nil),
 			req: &schedulerobjects.PodRequirements{
 				NodeSelector: map[string]string{"bar": "bar"},
 			},
 			expectSuccess: false,
 		},
 		"tolerated taints and matched node selector": {
-			node: &schedulerobjects.Node{
-				Taints: []v1.Taint{{Key: "foo", Value: "foo", Effect: v1.TaintEffectNoSchedule}},
-				Labels: map[string]string{"bar": "bar"},
-			},
+			node: makeTestNodeTaintsLabels(
+				[]v1.Taint{{Key: "foo", Value: "foo", Effect: v1.TaintEffectNoSchedule}},
+				map[string]string{"bar": "bar"},
+			),
 			req: &schedulerobjects.PodRequirements{
 				Tolerations:  []v1.Toleration{{Key: "foo", Value: "foo"}},
 				NodeSelector: map[string]string{"bar": "bar"},
@@ -244,20 +242,20 @@ func TestNodeSchedulingRequirementsMet(t *testing.T) {
 			expectSuccess: true,
 		},
 		"untolerated taints and matched node selector": {
-			node: &schedulerobjects.Node{
-				Taints: []v1.Taint{{Key: "foo", Value: "foo", Effect: v1.TaintEffectNoSchedule}},
-				Labels: map[string]string{"bar": "bar"},
-			},
+			node: makeTestNodeTaintsLabels(
+				[]v1.Taint{{Key: "foo", Value: "foo", Effect: v1.TaintEffectNoSchedule}},
+				map[string]string{"bar": "bar"},
+			),
 			req: &schedulerobjects.PodRequirements{
 				NodeSelector: map[string]string{"bar": "bar"},
 			},
 			expectSuccess: false,
 		},
 		"tolerated taints and unmatched node selector": {
-			node: &schedulerobjects.Node{
-				Taints: []v1.Taint{{Key: "foo", Value: "foo", Effect: v1.TaintEffectNoSchedule}},
-				Labels: nil,
-			},
+			node: makeTestNodeTaintsLabels(
+				[]v1.Taint{{Key: "foo", Value: "foo", Effect: v1.TaintEffectNoSchedule}},
+				nil,
+			),
 			req: &schedulerobjects.PodRequirements{
 				Tolerations:  []v1.Toleration{{Key: "foo", Value: "foo"}},
 				NodeSelector: map[string]string{"bar": "bar"},
@@ -265,20 +263,20 @@ func TestNodeSchedulingRequirementsMet(t *testing.T) {
 			expectSuccess: false,
 		},
 		"sufficient cpu": {
-			node: &schedulerobjects.Node{
-				AllocatableByPriorityAndResource: schedulerobjects.AllocatableByPriorityAndResourceType{
+			node: makeTestNodeResources(
+				schedulerobjects.AllocatableByPriorityAndResourceType{
 					0: schedulerobjects.ResourceList{
 						Resources: map[string]resource.Quantity{
 							"cpu": resource.MustParse("1"),
 						},
 					},
 				},
-				TotalResources: schedulerobjects.ResourceList{
+				schedulerobjects.ResourceList{
 					Resources: map[string]resource.Quantity{
 						"cpu": resource.MustParse("1"),
 					},
 				},
-			},
+			),
 			req: &schedulerobjects.PodRequirements{
 				ResourceRequirements: v1.ResourceRequirements{
 					Requests: v1.ResourceList{
@@ -290,20 +288,20 @@ func TestNodeSchedulingRequirementsMet(t *testing.T) {
 			expectSuccess: true,
 		},
 		"insufficient cpu": {
-			node: &schedulerobjects.Node{
-				AllocatableByPriorityAndResource: schedulerobjects.AllocatableByPriorityAndResourceType{
+			node: makeTestNodeResources(
+				schedulerobjects.AllocatableByPriorityAndResourceType{
 					0: schedulerobjects.ResourceList{
 						Resources: map[string]resource.Quantity{
 							"cpu": resource.MustParse("0"),
 						},
 					},
 				},
-				TotalResources: schedulerobjects.ResourceList{
+				schedulerobjects.ResourceList{
 					Resources: map[string]resource.Quantity{
 						"cpu": resource.MustParse("0"),
 					},
 				},
-			},
+			),
 			req: &schedulerobjects.PodRequirements{
 				ResourceRequirements: v1.ResourceRequirements{
 					Requests: v1.ResourceList{
@@ -315,8 +313,8 @@ func TestNodeSchedulingRequirementsMet(t *testing.T) {
 			expectSuccess: false,
 		},
 		"sufficient cpu at priority": {
-			node: &schedulerobjects.Node{
-				AllocatableByPriorityAndResource: schedulerobjects.AllocatableByPriorityAndResourceType{
+			node: makeTestNodeResources(
+				schedulerobjects.AllocatableByPriorityAndResourceType{
 					0: schedulerobjects.ResourceList{
 						Resources: map[string]resource.Quantity{
 							"cpu": resource.MustParse("0"),
@@ -328,12 +326,12 @@ func TestNodeSchedulingRequirementsMet(t *testing.T) {
 						},
 					},
 				},
-				TotalResources: schedulerobjects.ResourceList{
+				schedulerobjects.ResourceList{
 					Resources: map[string]resource.Quantity{
 						"cpu": resource.MustParse("1"),
 					},
 				},
-			},
+			),
 			req: &schedulerobjects.PodRequirements{
 				ResourceRequirements: v1.ResourceRequirements{
 					Requests: v1.ResourceList{
@@ -345,8 +343,8 @@ func TestNodeSchedulingRequirementsMet(t *testing.T) {
 			expectSuccess: true,
 		},
 		"insufficient cpu at priority": {
-			node: &schedulerobjects.Node{
-				AllocatableByPriorityAndResource: schedulerobjects.AllocatableByPriorityAndResourceType{
+			node: makeTestNodeResources(
+				schedulerobjects.AllocatableByPriorityAndResourceType{
 					0: schedulerobjects.ResourceList{
 						Resources: map[string]resource.Quantity{
 							"cpu": resource.MustParse("0"),
@@ -358,12 +356,12 @@ func TestNodeSchedulingRequirementsMet(t *testing.T) {
 						},
 					},
 				},
-				TotalResources: schedulerobjects.ResourceList{
+				schedulerobjects.ResourceList{
 					Resources: map[string]resource.Quantity{
 						"cpu": resource.MustParse("1"),
 					},
 				},
-			},
+			),
 			req: &schedulerobjects.PodRequirements{
 				ResourceRequirements: v1.ResourceRequirements{
 					Requests: v1.ResourceList{
@@ -377,11 +375,9 @@ func TestNodeSchedulingRequirementsMet(t *testing.T) {
 	}
 	for name, tc := range tests {
 		t.Run(name, func(t *testing.T) {
-			matches, _, reason, err := JobRequirementsMet(
-				tc.node.Taints,
-				tc.node.Labels,
-				tc.node.TotalResources,
-				tc.node.AllocatableByPriorityAndResource[tc.req.Priority],
+			matches, _, reason, err := jobRequirementsMet(
+				tc.node,
+				tc.req.Priority,
 				// TODO(albin): Define a jctx in the test case instead.
 				&schedulercontext.JobSchedulingContext{
 					PodRequirements: tc.req,
@@ -638,3 +634,39 @@ func BenchmarkInsufficientResourcesSum64(b *testing.B) {
 
 func TestResourceRequirementsMet(t *testing.T) {
 }
+
+func makeTestNodeTaintsLabels(taints []v1.Taint, labels map[string]string) *internaltypes.Node {
+	return internaltypes.CreateNode(
+		"id",
+		1,
+		1,
+		"executor",
+		"name",
+		taints,
+		labels,
+		schedulerobjects.ResourceList{},
+		schedulerobjects.AllocatableByPriorityAndResourceType{},
+		map[string]schedulerobjects.ResourceList{},
+		map[string]schedulerobjects.ResourceList{},
+		map[string]bool{},
+		[][]byte{},
+	)
+}
+
+func makeTestNodeResources(allocatableByPriority schedulerobjects.AllocatableByPriorityAndResourceType, totalResources schedulerobjects.ResourceList) *internaltypes.Node {
+	return internaltypes.CreateNode(
+		"id",
+		1,
+		1,
+		"executor",
+		"name",
+		[]v1.Taint{},
+		map[string]string{},
+		totalResources,
+		allocatableByPriority,
+		map[string]schedulerobjects.ResourceList{},
+		map[string]schedulerobjects.ResourceList{},
+		map[string]bool{},
+		[][]byte{},
+	)
+}
diff --git a/internal/scheduler/preempting_queue_scheduler_test.go b/internal/scheduler/preempting_queue_scheduler_test.go
index c2992142..69ce43cc 100644
--- a/internal/scheduler/preempting_queue_scheduler_test.go
+++ b/internal/scheduler/preempting_queue_scheduler_test.go
@@ -19,11 +19,13 @@ import (
 	"github.com/armadaproject/armada/internal/common/logging"
 	armadamaps "github.com/armadaproject/armada/internal/common/maps"
 	armadaslices "github.com/armadaproject/armada/internal/common/slices"
+	"github.com/armadaproject/armada/internal/common/stringinterner"
 	"github.com/armadaproject/armada/internal/common/types"
 	"github.com/armadaproject/armada/internal/common/util"
 	schedulerconstraints "github.com/armadaproject/armada/internal/scheduler/constraints"
 	schedulercontext "github.com/armadaproject/armada/internal/scheduler/context"
 	"github.com/armadaproject/armada/internal/scheduler/fairness"
+	"github.com/armadaproject/armada/internal/scheduler/internaltypes"
 	"github.com/armadaproject/armada/internal/scheduler/jobdb"
 	"github.com/armadaproject/armada/internal/scheduler/nodedb"
 	"github.com/armadaproject/armada/internal/scheduler/schedulerobjects"
@@ -40,14 +42,16 @@ func TestEvictOversubscribed(t *testing.T) {
 		testfixtures.N1Cpu4GiJobs("A", config.DefaultPriorityClassName, 20)...,
 	)
 
+	stringInterner := stringinterner.New(1024)
+
 	node := testfixtures.Test32CpuNode(priorities)
-	nodeDb, err := NewNodeDb(config)
+	nodeDb, err := NewNodeDb(config, stringInterner)
 	require.NoError(t, err)
 	nodeDbTxn := nodeDb.Txn(true)
 	err = nodeDb.CreateAndInsertWithJobDbJobsWithTxn(nodeDbTxn, jobs, node)
 	require.NoError(t, err)
 
-	jobDb := jobdb.NewJobDb(config.PriorityClasses, config.DefaultPriorityClassName, 1024)
+	jobDb := jobdb.NewJobDb(config.PriorityClasses, config.DefaultPriorityClassName, stringInterner)
 	jobDbTxn := jobDb.WriteTxn()
 	err = jobDbTxn.Upsert(jobs)
 	require.NoError(t, err)
@@ -1747,7 +1751,7 @@ func TestPreemptingQueueScheduler(t *testing.T) {
 	}
 	for name, tc := range tests {
 		t.Run(name, func(t *testing.T) {
-			nodeDb, err := NewNodeDb(tc.SchedulingConfig)
+			nodeDb, err := NewNodeDb(tc.SchedulingConfig, stringinterner.New(1024))
 			require.NoError(t, err)
 			nodeDbTxn := nodeDb.Txn(true)
 			for _, node := range tc.Nodes {
@@ -1758,7 +1762,7 @@ func TestPreemptingQueueScheduler(t *testing.T) {
 
 			priorities := types.AllowedPriorities(tc.SchedulingConfig.PriorityClasses)
 
-			jobDb := jobdb.NewJobDb(tc.SchedulingConfig.PriorityClasses, tc.SchedulingConfig.DefaultPriorityClassName, 1024)
+			jobDb := jobdb.NewJobDb(tc.SchedulingConfig.PriorityClasses, tc.SchedulingConfig.DefaultPriorityClassName, stringinterner.New(1024))
 			jobDbTxn := jobDb.WriteTxn()
 
 			// Accounting across scheduling rounds.
@@ -1829,8 +1833,8 @@ func TestPreemptingQueueScheduler(t *testing.T) {
 				for _, j := range round.NodeIndicesToCordon {
 					node, err := nodeDb.GetNode(tc.Nodes[j].Id)
 					require.NoError(t, err)
-					node = node.UnsafeCopy()
-					node.Taints = append(slices.Clone(node.Taints), nodedb.UnschedulableTaint())
+					taints := append(slices.Clone(node.GetTaints()), nodedb.UnschedulableTaint())
+					node = testNodeWithTaints(node, taints)
 					err = nodeDb.Upsert(node)
 					require.NoError(t, err)
 				}
@@ -1943,7 +1947,7 @@ func TestPreemptingQueueScheduler(t *testing.T) {
 					assert.NotEmpty(t, node)
 
 					// Check that the job can actually go onto this node.
-					matches, reason, err := nodedb.StaticJobRequirementsMet(node.Taints, node.Labels, node.TotalResources, jctx)
+					matches, reason, err := nodedb.StaticJobRequirementsMet(node, jctx)
 					require.NoError(t, err)
 					assert.Empty(t, reason)
 					assert.True(t, matches)
@@ -2172,7 +2176,7 @@ func BenchmarkPreemptingQueueScheduler(b *testing.B) {
 				priorityFactorByQueue[queue] = float64(rand.Intn(tc.MaxPriorityFactor-tc.MinPriorityFactor+1) + tc.MinPriorityFactor)
 			}
 
-			nodeDb, err := NewNodeDb(tc.SchedulingConfig)
+			nodeDb, err := NewNodeDb(tc.SchedulingConfig, stringinterner.New(1024))
 			require.NoError(b, err)
 			txn := nodeDb.Txn(true)
 			for _, node := range tc.Nodes {
@@ -2181,7 +2185,7 @@ func BenchmarkPreemptingQueueScheduler(b *testing.B) {
 			}
 			txn.Commit()
 
-			jobDb := jobdb.NewJobDb(tc.SchedulingConfig.PriorityClasses, tc.SchedulingConfig.DefaultPriorityClassName, 1024)
+			jobDb := jobdb.NewJobDb(tc.SchedulingConfig.PriorityClasses, tc.SchedulingConfig.DefaultPriorityClassName, stringinterner.New(1024))
 			jobDbTxn := jobDb.WriteTxn()
 			var queuedJobs []*jobdb.Job
 			for _, jobs := range jobsByQueue {
@@ -2265,7 +2269,7 @@ func BenchmarkPreemptingQueueScheduler(b *testing.B) {
 				nodeId := result.NodeIdByJobId[job.GetId()]
 				jobsByNodeId[nodeId] = append(jobsByNodeId[nodeId], job)
 			}
-			nodeDb, err = NewNodeDb(tc.SchedulingConfig)
+			nodeDb, err = NewNodeDb(tc.SchedulingConfig, stringinterner.New(1024))
 			require.NoError(b, err)
 			txn = nodeDb.Txn(true)
 			for _, node := range tc.Nodes {
@@ -2314,3 +2318,21 @@ func BenchmarkPreemptingQueueScheduler(b *testing.B) {
 		})
 	}
 }
+
+func testNodeWithTaints(node *internaltypes.Node, taints []v1.Taint) *internaltypes.Node {
+	return internaltypes.CreateNode(
+		node.GetId(),
+		node.GetNodeTypeId(),
+		node.GetIndex(),
+		node.GetExecutor(),
+		node.GetName(),
+		taints,
+		node.GetLabels(),
+		node.TotalResources,
+		node.AllocatableByPriority,
+		node.AllocatedByQueue,
+		node.AllocatedByJobId,
+		node.EvictedJobRunIds,
+		node.Keys,
+	)
+}
diff --git a/internal/scheduler/queue_scheduler_test.go b/internal/scheduler/queue_scheduler_test.go
index 9eed4775..472b0b78 100644
--- a/internal/scheduler/queue_scheduler_test.go
+++ b/internal/scheduler/queue_scheduler_test.go
@@ -18,6 +18,7 @@ import (
 	"github.com/armadaproject/armada/internal/armada/configuration"
 	"github.com/armadaproject/armada/internal/common/armadacontext"
 	armadaslices "github.com/armadaproject/armada/internal/common/slices"
+	"github.com/armadaproject/armada/internal/common/stringinterner"
 	"github.com/armadaproject/armada/internal/common/util"
 	schedulerconstraints "github.com/armadaproject/armada/internal/scheduler/constraints"
 	schedulercontext "github.com/armadaproject/armada/internal/scheduler/context"
@@ -516,7 +517,7 @@ func TestQueueScheduler(t *testing.T) {
 	}
 	for name, tc := range tests {
 		t.Run(name, func(t *testing.T) {
-			nodeDb, err := NewNodeDb(tc.SchedulingConfig)
+			nodeDb, err := NewNodeDb(tc.SchedulingConfig, stringinterner.New(1024))
 			require.NoError(t, err)
 			txn := nodeDb.Txn(true)
 			for _, node := range tc.Nodes {
@@ -696,7 +697,7 @@ func TestQueueScheduler(t *testing.T) {
 				assert.NotEmpty(t, node)
 
 				// Check that the job can actually go onto this node.
-				matches, reason, err := nodedb.StaticJobRequirementsMet(node.Taints, node.Labels, node.TotalResources, jctx)
+				matches, reason, err := nodedb.StaticJobRequirementsMet(node, jctx)
 				require.NoError(t, err)
 				assert.Empty(t, reason)
 				assert.True(t, matches)
@@ -728,7 +729,7 @@ func TestQueueScheduler(t *testing.T) {
 	}
 }
 
-func NewNodeDb(config configuration.SchedulingConfig) (*nodedb.NodeDb, error) {
+func NewNodeDb(config configuration.SchedulingConfig, stringInterner *stringinterner.StringInterner) (*nodedb.NodeDb, error) {
 	nodeDb, err := nodedb.NewNodeDb(
 		config.PriorityClasses,
 		config.MaxExtraNodesToConsider,
@@ -736,6 +737,7 @@ func NewNodeDb(config configuration.SchedulingConfig) (*nodedb.NodeDb, error) {
 		config.IndexedTaints,
 		config.IndexedNodeLabels,
 		config.WellKnownNodeTypes,
+		stringInterner,
 	)
 	if err != nil {
 		return nil, err
diff --git a/internal/scheduler/scheduling_algo_test.go b/internal/scheduler/scheduling_algo_test.go
index 0df311e3..21edcae4 100644
--- a/internal/scheduler/scheduling_algo_test.go
+++ b/internal/scheduler/scheduling_algo_test.go
@@ -17,6 +17,7 @@ import (
 	"github.com/armadaproject/armada/internal/armada/configuration"
 	"github.com/armadaproject/armada/internal/common/armadacontext"
 	armadaslices "github.com/armadaproject/armada/internal/common/slices"
+	"github.com/armadaproject/armada/internal/common/stringinterner"
 	"github.com/armadaproject/armada/internal/scheduler/jobdb"
 	schedulermocks "github.com/armadaproject/armada/internal/scheduler/mocks"
 	"github.com/armadaproject/armada/internal/scheduler/nodedb"
@@ -392,6 +393,7 @@ func TestSchedule(t *testing.T) {
 				schedulingContextRepo,
 				nil,
 				nil,
+				stringinterner.New(1024),
 			)
 			require.NoError(t, err)
 
@@ -544,6 +546,7 @@ func BenchmarkNodeDbConstruction(b *testing.B) {
 			b.ResetTimer()
 			for n := 0; n < b.N; n++ {
 				b.StopTimer()
+				stringInterner := stringinterner.New(1024)
 				algo, err := NewFairSchedulingAlgo(
 					schedulingConfig,
 					time.Second*5,
@@ -552,6 +555,7 @@ func BenchmarkNodeDbConstruction(b *testing.B) {
 					nil,
 					nil,
 					nil,
+					stringInterner,
 				)
 				require.NoError(b, err)
 				b.StartTimer()
@@ -563,6 +567,7 @@ func BenchmarkNodeDbConstruction(b *testing.B) {
 					schedulingConfig.IndexedTaints,
 					schedulingConfig.IndexedNodeLabels,
 					schedulingConfig.WellKnownNodeTypes,
+					stringInterner,
 				)
 				require.NoError(b, err)
 				err = algo.addExecutorToNodeDb(nodeDb, jobs, nodes)
diff --git a/internal/scheduler/testfixtures/testfixtures.go b/internal/scheduler/testfixtures/testfixtures.go
index 31350e88..62f96465 100644
--- a/internal/scheduler/testfixtures/testfixtures.go
+++ b/internal/scheduler/testfixtures/testfixtures.go
@@ -19,6 +19,7 @@ import (
 	"k8s.io/apimachinery/pkg/api/resource"
 
 	"github.com/armadaproject/armada/internal/armada/configuration"
+	"github.com/armadaproject/armada/internal/common/stringinterner"
 	"github.com/armadaproject/armada/internal/common/types"
 	"github.com/armadaproject/armada/internal/common/util"
 	schedulerconfiguration "github.com/armadaproject/armada/internal/scheduler/configuration"
@@ -98,7 +99,7 @@ func NewJobDb() *jobdb.JobDb {
 		TestPriorityClasses,
 		TestDefaultPriorityClass,
 		SchedulingKeyGenerator,
-		1024,
+		stringinterner.New(1024),
 	)
 	// Mock out the clock and uuid provider to ensure consistent ids and timestamps are generated.
 	jobDb.SetClock(NewMockPassiveClock())