scheduler: ensure dup alloc names are fixed before plan submit. #18873

jrasell · 2023-10-26T10:54:46Z

This change fixes a bug within the generic scheduler which meant duplicate alloc indexes (names) could be submitted to the plan applier and written to state. The bug originates from the placements calculation notion that names of allocations being replaced are blindly copied to their replacement. This is not correct in all cases, particularly when dealing with canaries.

The fix updates the alloc name index tracker to include minor duplicate tracking. This can be used when computing placements to ensure duplicate are found, and a new name picked before the plan is submitted. The name index tracking is now passed from the reconciler to the generic scheduler via the results, so this does not have to be regenerated, or another data structure used.

closes #10727

Reviewer Notes

The new test TestServiceSched_JobModify_ProposedDuplicateAllocIndex mimics the reproduction behaviour and can be used to see how the code change has fixed the bug.

This reproduction can be used to test the code change in a manual way. The reproduction (in my testing) worked 100% of the time.

This change fixes a bug within the generic scheduler which meant duplicate alloc indexes (names) could be submitted to the plan applier and written to state. The bug originates from the placements calculation notion that names of allocations being replaced are blindly copied to their replacement. This is not correct in all cases, particularly when dealing with canaries. The fix updates the alloc name index tracker to include minor duplicate tracking. This can be used when computing placements to ensure duplicate are found, and a new name picked before the plan is submitted. The name index tracking is now passed from the reconciler to the generic scheduler via the results, so this does not have to be regenerated, or another data structure used.

nomad/structs/structs.go

tgross

Nice work on this @jrasell. The fix is tightly scoped and very clear, and the testing and extra commentary is really helpful.

scheduler/reconcile_util.go

scheduler/reconcile.go

scheduler/generic_sched_test.go

schmichael

Great work!

schmichael · 2023-10-26T17:23:17Z

scheduler/reconcile_util.go

+		allocIndex := a.Index()
+
+		if bitmap.Check(allocIndex) {
+			duplicates[allocIndex]++
+		} else {
+			bitmap.Set(allocIndex)
+		}


I think duplicates replaces bitmap entirely. bitmap is "a map of bools" when we need "a map of ints", hence the new duplicates mapping. However, I think ideally both bitmap and duplicates would be something like a slice of ints where the offset is the alloc index and the value is the number of duplicates: 0 indicating the index is unused, 1 indicating it is used, and >1 indicating it has duplicates. (this is all awkward to describe since both "alloc index" and "index of the slice" are two different concepts that could actually be same thing!)

That being said even if my suggestion works, it would be functionally identical to what you've implemented, so we should go with whatever the lowest-risk easiest-to-read implementation is. Since this is in the parallelized part of scheduling, and cpu time is usually plentiful on servers, I'm far more concerned with correctness than performance.

I agree that the name index tracking could be updated to include duplicates without using a bitmap, however, I think reworking this should be done within any follow-up. This change seems fairly low risk and targeted, whereas a larger rewrite would require substantial regression testing to be included. I'll raise an issue to discuss the idea of reworking the tracking, which I could noodle on casually.

lgfa29

Sharing some comments early in case I don't have a chance to come back for a deeper review later today, but great work!

lgfa29 · 2023-10-26T17:35:00Z

scheduler/generic_sched.go

+				// Pull the allocation name as a new variables, so we can alter
+				// this as needed without making changes to the original
+				// object.
+				newAllocName := missing.Name()


Maybe I'm misunderstanding it, but this comment seems a bit inaccurate. newAllocName doesn't seem to be modified, and even if it were strings are constants, so it shouldn't affect missing? 🤔

newAllocName is potentially modified on L654 if it is found to be a duplicate.

lgfa29 · 2023-10-26T17:41:19Z

scheduler/generic_sched.go

+				// future version of Nomad.
+				if taskGroupNameIndex.IsDuplicate(allocIndex) {
+					oldAllocName := newAllocName
+					newAllocName = taskGroupNameIndex.Next(1)[0]


It's not immediately obvious to me how this could cause any problems, but given that we're trying to avoid duplicate names it could useful to further investigate if this bit of code could cause problems:

nomad/scheduler/reconcile_util.go

Lines 739 to 744 in fdde8a5

// We have exhausted the free set, now just pick overlapping indexes

var i uint

for i = 0; i < remainder; i++ {

next = append(next, structs.AllocName(a.job, a.taskGroup, i))

a.b.Set(i)

}

Maybe if, somehow, the count value differs between the time the allocNameIndex is created and the call to Next() (like in a job update? or a version revert?) we could maybe hit an overlap? 🤔

That's a good thread to pull on and something I will take a look at once this PR has been merged. This resolves a reproducible manifestation of the bug, so I would like to get that fixed given the time pressures before opening up new investigations.

lgfa29 · 2023-10-26T18:23:54Z

scheduler/reconcile.go

+	// Duplicate allocation indexes can be caused due to the way this piece of
+	// code works. The reproduction involved canaries, and performing both a


Just to make I understood, this hot path can return early with duplicate alloc names? Is there a way to avoid that so that callers don't have to handle them?

The comment has been clarified, hopefully that makes things clearer? I spent a while looking to see if I could fix the problem at the source, but I wasn't able to figure out a way.

tgross

LGTM!

This change fixes a bug within the generic scheduler which meant duplicate alloc indexes (names) could be submitted to the plan applier and written to state. The bug originates from the placements calculation notion that names of allocations being replaced are blindly copied to their replacement. This is not correct in all cases, particularly when dealing with canaries. The fix updates the alloc name index tracker to include minor duplicate tracking. This can be used when computing placements to ensure duplicate are found, and a new name picked before the plan is submitted. The name index tracking is now passed from the reconciler to the generic scheduler via the results, so this does not have to be regenerated, or another data structure used.

…) (#18891) This change fixes a bug within the generic scheduler which meant duplicate alloc indexes (names) could be submitted to the plan applier and written to state. The bug originates from the placements calculation notion that names of allocations being replaced are blindly copied to their replacement. This is not correct in all cases, particularly when dealing with canaries. The fix updates the alloc name index tracker to include minor duplicate tracking. This can be used when computing placements to ensure duplicate are found, and a new name picked before the plan is submitted. The name index tracking is now passed from the reconciler to the generic scheduler via the results, so this does not have to be regenerated, or another data structure used. Co-authored-by: James Rasell <jrasell@users.noreply.github.com>

This change fixes a bug within the generic scheduler which meant duplicate alloc indexes (names) could be submitted to the plan applier and written to state. The bug originates from the placements calculation notion that names of allocations being replaced are blindly copied to their replacement. This is not correct in all cases, particularly when dealing with canaries. The fix updates the alloc name index tracker to include minor duplicate tracking. This can be used when computing placements to ensure duplicate are found, and a new name picked before the plan is submitted. The name index tracking is now passed from the reconciler to the generic scheduler via the results, so this does not have to be regenerated, or another data structure used.

…icorp#18873) This change fixes a bug within the generic scheduler which meant duplicate alloc indexes (names) could be submitted to the plan applier and written to state. The bug originates from the placements calculation notion that names of allocations being replaced are blindly copied to their replacement. This is not correct in all cases, particularly when dealing with canaries. The fix updates the alloc name index tracker to include minor duplicate tracking. This can be used when computing placements to ensure duplicate are found, and a new name picked before the plan is submitted. The name index tracking is now passed from the reconciler to the generic scheduler via the results, so this does not have to be regenerated, or another data structure used.

jrasell self-assigned this Oct 26, 2023

changelog: add entry for #18873

9fb64df

vercel bot deployed to Preview – nomad-storybook-and-ui October 26, 2023 11:21 View deployment

jrasell requested review from tgross, lgfa29 and schmichael October 26, 2023 11:38

jrasell added backport/1.4.x backport to 1.4.x release line backport/1.5.x backport to 1.5.x release line backport/1.6.x backport to 1.6.x release line labels Oct 26, 2023

jrasell marked this pull request as ready for review October 26, 2023 11:42

Juanadelacuesta reviewed Oct 26, 2023

View reviewed changes

nomad/structs/structs.go Show resolved Hide resolved

tgross approved these changes Oct 26, 2023

View reviewed changes

scheduler/reconcile_util.go Outdated Show resolved Hide resolved

scheduler/reconcile_util.go Show resolved Hide resolved

scheduler/reconcile.go Outdated Show resolved Hide resolved

scheduler/generic_sched_test.go Show resolved Hide resolved

schmichael approved these changes Oct 26, 2023

View reviewed changes

lgfa29 reviewed Oct 26, 2023

View reviewed changes

review: updates based on feedback.

965e9a0

vercel bot deployed to Preview – nomad-storybook-and-ui October 27, 2023 07:37 View deployment

tgross approved these changes Oct 27, 2023

View reviewed changes

Merge branch 'main' into gh-10727-sched-fix-method

1240738

vercel bot deployed to Preview – nomad-storybook-and-ui October 27, 2023 12:33 View deployment

vercel bot deployed to Preview – nomad October 27, 2023 12:37 View deployment

jrasell merged commit 3c8eb54 into main Oct 27, 2023
26 checks passed

jrasell deleted the gh-10727-sched-fix-method branch October 27, 2023 13:16

jrasell added a commit that referenced this pull request Oct 31, 2023

changelog: fix entry wording for #18873

0814c48

jrasell added a commit that referenced this pull request Nov 1, 2023

changelog: fix entry wording for #18873 (#18927)

4a89a0a

nvanthao pushed a commit to nvanthao/nomad that referenced this pull request Mar 1, 2024

changelog: fix entry wording for hashicorp#18873 (hashicorp#18927)

21a65c9

nvanthao pushed a commit to nvanthao/nomad that referenced this pull request Mar 1, 2024

changelog: fix entry wording for hashicorp#18873 (hashicorp#18927)

7ed388e

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

scheduler: ensure dup alloc names are fixed before plan submit. #18873

scheduler: ensure dup alloc names are fixed before plan submit. #18873

jrasell commented Oct 26, 2023

tgross left a comment

schmichael left a comment

schmichael Oct 26, 2023

jrasell Oct 27, 2023

lgfa29 left a comment

lgfa29 Oct 26, 2023

jrasell Oct 27, 2023

lgfa29 Oct 26, 2023

jrasell Oct 27, 2023

lgfa29 Oct 26, 2023

jrasell Oct 27, 2023

tgross left a comment

	// We have exhausted the free set, now just pick overlapping indexes
	var i uint
	for i = 0; i < remainder; i++ {
	next = append(next, structs.AllocName(a.job, a.taskGroup, i))
	a.b.Set(i)
	}

		// Duplicate allocation indexes can be caused due to the way this piece of
		// code works. The reproduction involved canaries, and performing both a

scheduler: ensure dup alloc names are fixed before plan submit. #18873

scheduler: ensure dup alloc names are fixed before plan submit. #18873

Conversation

jrasell commented Oct 26, 2023

Reviewer Notes

tgross left a comment

Choose a reason for hiding this comment

schmichael left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

lgfa29 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

tgross left a comment

Choose a reason for hiding this comment