Network toplogy aware scheduling support in Volcano scheduler: Populate hyperNode tree in cache #3881 #3922

penggu · 2024-12-24T15:32:12Z

add event handler for adding/deleting/updating HyperNode in scheduler cache.

volcano-sh-bot · 2024-12-24T15:32:16Z

Welcome @penggu!

It looks like this is your first PR to volcano-sh/volcano.

Thank you, and welcome to Volcano. 😃

volcano-sh-bot · 2024-12-24T15:32:19Z

[APPROVALNOTIFIER] This PR is NOT APPROVED

This pull-request has been approved by:
To complete the pull request process, please assign wpeng102
You can assign the PR to them by writing /assign @wpeng102 in a comment when ready.

The full list of commands accepted by this bot can be found here.

Details

Needs approval from an approver in each of these files:

OWNERS

Approvers can indicate their approval by writing /approve in a comment
Approvers can cancel approval by writing /approve cancel in a comment

pkg/scheduler/cache/cache.go

JesseStutler · 2024-12-25T09:04:44Z

pkg/scheduler/cache/cache.go

+	hnfb.nodes[hn.Name] = hntn
+
+	tierStr := hn.Spec.Tier
+	tier, err := strconv.Atoi(tierStr)


Currently, in api definition, the tier is a type of string, what if the user wants to specify tier name other than numbers? Is there any purpose in defining the type of tier as string before?

I think Tier should be an int. If a "tier name" is needed, then a mapping from a "tier name" string to its "tier number" int is needed.

JesseStutler · 2024-12-25T09:15:39Z

pkg/scheduler/cache/cache.go

+				nodeName := member.Selector.ExactMatch.Name
+				hntn.NodeMatchers.Insert(NewExactMatcher(nodeName))
+				workerNode := sc.Nodes[nodeName]
+				if workerNode == nil {


There is a scenario that if the HyperNode is created first and then handles the event of the HyperNode, the Node has not been created yet and is not in the cache. If we directly return here and there is no change of the HyperNode, there will no longer be new events related to the HyperNode. You can look at the logic in vc-controller. The event of resource change and the worker responsible for processing collaborate through the workqueue. If the event processing fails, the worker can throw it back to the workqueue, and then process it from the workqueue later. So we may need to add worker and workqueue here, and re-enqueue the event if it fails

Thanks for bring up this scenario. I am aware of it. My hope is that the event handler for Node need to update the HyperNode (I did not implement that logic in the current PR. I was planning to add it later).

Your proposed solution (using workqueue) should work for Exact match. I wonder how does it work for Regex match. In case of Regex match, when will we know for sure that no future child node will appear -- hence we stop throwing it back to the workqueue?

I think a better solution is to update HyperNodeTree when AddNode and DeleteNode, so that it doesn't matter if Node is not created yet, both ExactMatch and RegexMatch can be included. Our original intention of designing RegexMatch is actually to serve Node.

JesseStutler · 2024-12-25T09:30:58Z

pkg/scheduler/cache/cache.go

+			case networktopov1alpha1.ExactMatchMemberSelectorType:
+				memberName := member.Selector.ExactMatch.Name
+				hntn.MemberMatchers.Insert(NewExactMatcher(memberName))
+				member := sc.hypernodeForestbuilder.nodes[memberName]


The same problem, the HyperNode events here are out of order, and the Member may not have been recorded in the builder. Then if the HyperNode does not change, there won't be more events coming

JesseStutler · 2024-12-25T09:52:59Z

pkg/scheduler/cache/cache.go

+				if member != nil {
+					insertHyperNodeMember(hntn, hnfb, memberName, member, sc)
+					if hntn.Parent != nil {
+						sc.HyperNodes[hntn.Parent.Name].Union(sc.HyperNodes[memberName])


Also has the same problem here, Union is cloned and the return value is not processed, and I didn't get the point here, what is the purpose here?

Also has the same problem here, Union is cloned and the return value is not processed, and I didn't get the point here, what is the purpose here?

All members of a HyperNode should also be members of its parent

JesseStutler · 2024-12-25T09:53:11Z

pkg/scheduler/cache/cache.go

+					}
+				}
+				if hntn.Parent != nil {
+					sc.HyperNodes[hntn.Parent.Name].Union(sc.HyperNodes[hntn.Name])


Also has the same problem here

Also has the same problem here

Same answer: All members of a HyperNode should also be members of its parent

JesseStutler · 2024-12-25T09:59:12Z

pkg/scheduler/cache/cache.go

+	if hnfb.roots.Has(hn.Name) {
+		hnfb.roots.Delete(hn.Name)
+	}
+


Missed update sc.HyperNodeListByTier and sc.HyperNodes

JesseStutler · 2024-12-25T09:59:57Z

pkg/scheduler/cache/cache.go

+	CSINodesStatus         map[string]*schedulingapi.CSINodeStatusInfo
+	HyperNodeListByTier    map[int]sets.Set[string]    // Maps tier to a set of hypernode names
+	HyperNodes             map[string]sets.Set[string] // Maps hypernode name to a set of node names
+	HyperNodeTreeRoots     HyperNodeSet


I see that HyperNodeTreeRoots is not used. Is it still needed?

Good catch. It has been replaced by hypernodeForestbuilder.roots

JesseStutler · 2024-12-25T10:05:08Z

pkg/scheduler/cache/event_handlers.go

+
+// UpdateHyperNodeV1alpha1 update hypernode in scheduler cache
+func (sc *SchedulerCache) UpdateHyperNodeV1alpha1(oldObj, newObj interface{}) {
+	sc.DeleteHyperNodeV1alpha1(oldObj)


Can we directly implement the logic of update member and update hypernode here?

Direct implementation involves

Finding diff between the old and new CRD

Update the forest based on the updated fields, and all the parent/child relationship based on ExactMatch and RegexMatch needs to be updated.

Because of the complicated logic involved in Step2, especially RegexMatch for both its children and its parents, that piece of code will be very complicated, and it will be a lot of duplicated logic from exiting AddHyperNodeV1alpha1() and DeleteHyperNodeV1alpha1().

i think the current implementation is easier to understand and to maintain. Please let me know if you think otherwise.

I think it's great

JesseStutler · 2024-12-25T10:09:07Z

Please rebase onto the new codes: #3874, and squash your commit into one, so I can review clearly

Monokaix · 2024-12-27T03:28:26Z

pkg/scheduler/cache/cache.go

+}
+
+// insertHyperNodeMember inserts a member into a hypernode and updates the forest
+func insertHyperNodeMember(hntn *HyperNodeTreeNode, hnfb *HyperNodeForestBuilder, memberName string, memberNode *HyperNodeTreeNode, sc *SchedulerCache) {


There is no distinction between the nodes in the leaf nodes and the hyperNodes of non-leaf nodes. What we expect is that the key stored in HyperNodes is the hyperNode, and the value is a list of all leaf nodes under the hyperNode.

Monokaix · 2024-12-27T03:34:30Z

pkg/scheduler/cache/cache.go

+			case networktopov1alpha1.ExactMatchMemberSelectorType:
+				nodeName := member.Selector.ExactMatch.Name
+				hntn.NodeMatchers.Insert(NewExactMatcher(nodeName))
+				workerNode := sc.Nodes[nodeName]


sc.Nodes should be accessed with lock.

Monokaix · 2024-12-27T03:36:36Z

pkg/scheduler/cache/cache.go

+	Parent         *HyperNodeTreeNode
+	Members        sets.Set[*HyperNodeTreeNode]
+	MemberMatchers sets.Set[*MemberMatcher]
+	Nodes          sets.Set[*schedulingapi.NodeInfo]


We just need nodeName instead of NodeInfo.

Monokaix · 2024-12-27T06:24:51Z

pkg/scheduler/cache/cache.go

+	HyperNodeListByTier    map[int]sets.Set[string]    // Maps tier to a set of hypernode names
+	HyperNodes             map[string]sets.Set[string] // Maps hypernode name to a set of node names
+	HyperNodeTreeRoots     HyperNodeSet
+	hypernodeForestbuilder *HyperNodeForestBuilder


Should also be locked.

Monokaix · 2024-12-27T06:34:09Z

We should also expose a method like LCA(Lowest Common Ancestor) for HyperNodeTreeRoots, which will be used by score logic.

Monokaix · 2024-12-27T06:42:10Z

pkg/scheduler/cache/cache.go

+	klog.V(4).Infof("Adding hypernode %s to the forest, in %d tier", hn.Name, tier)
+
+	// Iterate over members and add them to the forest
+	for _, member := range hn.Spec.Members {


This can be wrapped as a func, it' the logic to build a hyperNodeTreeNode, and the last thing to do is update the sc.HyperNodeListByTier and sc.HyperNodes.
And can we just use one var to express the tree?

Monokaix · 2024-12-27T06:45:57Z

pkg/scheduler/cache/cache.go

+	Parent         *HyperNodeTreeNode
+	Members        sets.Set[*HyperNodeTreeNode]
+	MemberMatchers sets.Set[*MemberMatcher]
+	Nodes          sets.Set[*schedulingapi.NodeInfo]


And seems nowhere to assign leaf nodes to sc.HyperNodes.

JesseStutler · 2024-12-27T09:19:48Z

pkg/scheduler/cache/cache.go

+	for _, parentNode := range sc.hypernodeForestbuilder.nodes {
+		for m := range parentNode.MemberMatchers {
+			if m.Exact != "" && m.Exact == hn.Name {
+				insertHyperNodeMember(parentNode, hnfb, hn.Name, hntn, sc)


insertHyperNodeMember should be used as a method of *HyperNodeForestBuilder instead of passing it in through parameters.

SchedulerCache should also be used as an attribute of HyperNodeForestBuilder. The function parameters must be consistent with the function name and responsibilities.

Don't memerNode already contain a name attribute? No need to pass again

Monokaix · 2025-01-06T10:48:18Z

pkg/scheduler/cache/cache.go

 		})
 	}
+
+	// TODO (penggu): create informat for HyperNode(v1alpha1) information


TODO still need?

JesseStutler · 2025-01-07T09:02:20Z

pkg/scheduler/cache/cache.go

+	Tier           int
+	Parent         *HyperNodeTreeNode
+	Members        sets.Set[*HyperNodeTreeNode]
+	MemberMatchers sets.Set[*MemberMatcher]


Can we group together Members/NodeMatchers and MemberMatchers/NodeMatchers? Too many unused fields

Add AddFunc for HyperNode informer support to SchedulerCache Network topology implements of scheduler Signed-off-by: Monokaix <[email protected]> Add plugin for networkTopology and score logic Signed-off-by: Monokaix <[email protected]> WIP1 HyperNode handling in scheduler cache Change HyperNodesListByTier to a map of set (instead of string) Refactor event handling for HyperNode cache Remove unused updateHyperNodeListByTier function Add child member handling for HyperNodes based on parent matchers Move add and delete HyperNode functions to event_handlers.go Refactor HyperNode handling: unify member updates

volcano-sh-bot · 2025-01-14T01:58:34Z

@penggu: PR needs rebase.

Details

Instructions for interacting with me using PR comments are available here. If you have questions or suggestions related to my behavior, please file an issue against the kubernetes/test-infra repository.

Monokaix · 2025-01-15T07:08:50Z

This pr has some code conflict to resolve and update, and #3964 will work based on this: )

penggu · 2025-01-16T17:27:12Z

This feature has been merged via PR #3964. So it is no longer needed. OK to close this PR now.

volcano-sh-bot requested review from k82cn, merryzhou and shinytang6 December 24, 2024 15:32

volcano-sh-bot added the size/XXL Denotes a PR that changes 1000+ lines, ignoring generated files. label Dec 24, 2024

JesseStutler reviewed Dec 25, 2024

View reviewed changes

volcano-sh-bot added the needs-rebase Indicates a PR cannot be merged because it has merge conflicts with HEAD. label Dec 26, 2024

Monokaix reviewed Dec 27, 2024

View reviewed changes

JesseStutler reviewed Dec 27, 2024

View reviewed changes

penggu force-pushed the network-topo-peng branch from aec453f to 5e3e22e Compare January 6, 2025 05:04

Monokaix reviewed Jan 6, 2025

View reviewed changes

pkg/scheduler/cache/cache.go

})

}

// TODO (penggu): create informat for HyperNode(v1alpha1) information

Copy link

Member

Monokaix Jan 6, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

TODO still need?

JesseStutler reviewed Jan 7, 2025

View reviewed changes

volcano-sh-bot added size/L Denotes a PR that changes 100-499 lines, ignoring generated files. and removed needs-rebase Indicates a PR cannot be merged because it has merge conflicts with HEAD. size/XXL Denotes a PR that changes 1000+ lines, ignoring generated files. labels Jan 7, 2025

penggu force-pushed the network-topo-peng branch from d453afd to 4d68f2c Compare January 7, 2025 21:10

Update dependency for volcano.sh/apis to a newer version

cb436ea

Monokaix mentioned this pull request Jan 11, 2025

Update: Populate hyperNode info #3964

Merged

volcano-sh-bot added the needs-rebase Indicates a PR cannot be merged because it has merge conflicts with HEAD. label Jan 14, 2025

fix compiling errors

4c4c8c0

penggu closed this Jan 16, 2025

Network toplogy aware scheduling support in Volcano scheduler: Populate hyperNode tree in cache #3881 #3922

Network toplogy aware scheduling support in Volcano scheduler: Populate hyperNode tree in cache #3881 #3922

Uh oh!

Conversation

penggu commented Dec 24, 2024

Uh oh!

volcano-sh-bot commented Dec 24, 2024

Uh oh!

volcano-sh-bot commented Dec 24, 2024

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

JesseStutler commented Dec 25, 2024

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Monokaix commented Dec 27, 2024

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

volcano-sh-bot commented Jan 14, 2025

Uh oh!

Monokaix commented Jan 15, 2025

Uh oh!

penggu commented Jan 16, 2025

Uh oh!

Reviewers

Assignees