balancer/weightedroundrobin: add load balancing policy (A58) #6241

dfawley · 2023-05-02T01:09:13Z

Implements https://github.com/grpc/proposal/blob/master/A58-client-side-weighted-round-robin-lb-policy.md

RELEASE NOTES:

balancer/weightedroundrobin: add new LB policy for balancing between backends based on their load reports

zasweq · 2023-05-02T16:42:30Z

I lgtmed the pr this is based off. Could you please rebase and fix vet?

zasweq · 2023-05-02T16:42:52Z

balancer/weightedroundrobin/config.go:38:6: exported type LBConfigForTesting should have comment or be unexported

zasweq

Did a first pass on the implementation focused on style/readability with a light correctness focus (but still tried to break correctness). Future passes I will go heavier on breaking correctness. I haven't looked at the tests yet.

balancer/weightedroundrobin/balancer.go

balancer/weightedroundrobin/config.go

balancer/weightedroundrobin/balancer.go

balancer/weightedroundrobin/scheduler.go

balancer/weightedroundrobin/balancer.go

dfawley

Updated based on additional comments, thanks!

balancer/weightedroundrobin/balancer.go

balancer/weightedroundrobin/config.go

balancer/weightedroundrobin/scheduler.go

zasweq

Took a first pass at tests. Sending them out now so you can see them, beginning implementation second pass now.

balancer/weightedroundrobin/balancer_test.go

zasweq · 2023-05-04T18:06:12Z

balancer/weightedroundrobin/balancer_test.go

+	// srv1 starts loaded and srv2 starts without load; ensure RPCs are routed
+	// disproportionately to srv2 (10:1).  Errors are set (but ignored
+	// initially) such that RPCs will be routed 50/50.
+	srv1.oobMetrics.SetQPS(10.0)
+	srv1.oobMetrics.SetCPUUtilization(1.0)
+	srv1.oobMetrics.SetEPS(0)
+	// srv1 weight before: 10.0 / 1.0 = 10.0
+	// srv1 weight after:  10.0 / 1.0 = 10.0
+
+	srv2.oobMetrics.SetQPS(10.0)
+	srv2.oobMetrics.SetCPUUtilization(.1)
+	srv2.oobMetrics.SetEPS(10.0)
+	// srv2 weight before: 10.0 / 0.1 = 100.0
+	// srv2 weight after:  10.0 / 1.0 = 10.0


I don't get this. Can you please specify where the errors are set, and why the RPCs once errors are set are routed 50/50 rather than 10/1.

Errors are set via SetEPS, and I explain here with "weight before/after" what the effective weights will be (10:1 before and 1:1 after). The comment above goes with these to explain this.

Can you specify what 0 and 10 mean wrt EPS and errors.

Done I think

balancer/weightedroundrobin/balancer_test.go

zasweq · 2023-05-04T18:09:06Z

balancer/weightedroundrobin/balancer_test.go

+	ctx, cancel := context.WithTimeout(context.Background(), defaultTestTimeout)
+	defer cancel()
+
+	var mu sync.Mutex
+	start := time.Now()
+	now := start
+	setNow := func(t time.Time) {
+		mu.Lock()
+		defer mu.Unlock()
+		now = t
+	}
+	iwrr.TimeNow = func() time.Time {
+		mu.Lock()
+		defer mu.Unlock()
+		return now
+	}
+	t.Cleanup(func() { iwrr.TimeNow = time.Now })
+
+	srv1 := startServer(t, reportBoth)
+	srv2 := startServer(t, reportBoth)
+
+	// srv1 starts loaded and srv2 starts without load; ensure RPCs are routed
+	// disproportionately to srv2 (10:1).  Because the OOB reporting interval
+	// is 1 minute but the weights expire in 1 second, routing will go to 50/50
+	// after the weights expire.
+	srv1.oobMetrics.SetQPS(10.0)
+	srv1.oobMetrics.SetCPUUtilization(1.0)
+
+	srv2.oobMetrics.SetQPS(10.0)
+	srv2.oobMetrics.SetCPUUtilization(.1)


This whole codeblock is shared with test above (except reportBoth, which is fine since it's a no-op anyway if it just gets ignored). Refactor into helper?

I'd rather not have helpers that do too much.. The goal should be to have ~1 line for each type of operation. With too many helpers the code can end up harder to debug when there is a test error.

Line 514 - 547 are shared. Sorry, the comment didn't include the lines. I think due to the thirty lines of shared code repeated 3 times, you can pull into helper.

startServer and the setting of metrics are already factored out enough.

Setting the context can't be shared.

The bit that I'd be willing to rework is 517-530, but it seems fine to me this way.

balancer/weightedroundrobin/balancer_test.go

zasweq

Implementation looks solid. Some minor comments (alongside a test I want).

balancer/weightedroundrobin/internal/internal.go

zasweq · 2023-05-04T18:20:49Z

balancer/weightedroundrobin/scheduler.go

+}
+
+// A simple RR scheduler to use for fallback when all weights are zero or the
+// same or when only one subconn exists.


also mention if < 2 subconns have weights. (i.e. all weights are zero or only one subconn has weight, can perhaps replace the language of "all weights are zero" to both of these cases)

balancer/weightedroundrobin/scheduler.go

balancer/weightedroundrobin/balancer.go

zasweq · 2023-05-04T18:55:29Z

balancer/weightedroundrobin/balancer.go

+		// By default we set load reports to off, because they are not running
+		// upon initial weightedSubConn creation.


Is this the real root cause for this decision?

The reason this code is here is: 1. we need a non-nil oldCfg, and 2. we want the wsc to know there isn't a running OOB listener.

zasweq · 2023-05-04T18:56:52Z

balancer/weightedroundrobin/balancer.go

+		oldCfg = &lbConfig{EnableOOBLoadReport: false}
+	}
+	w.cfg = cfg
+	newPeriod := cfg.OOBReportingPeriod
+	if cfg.EnableOOBLoadReport == oldCfg.EnableOOBLoadReport &&
+		newPeriod == oldCfg.OOBReportingPeriod {
+		// Load reporting wasn't enabled before or after, or load reporting was
+		// enabled before and after, and had the same period.  (Note that with
+		// load reporting disabled, OOBReportingPeriod is always 0.)
+		return
+	}
+	// (Optionally stop and) start the listener to use the new config's
+	// settings for OOB reporting.
+	if w.stopORCAListener != nil {
+		w.stopORCAListener()
+	}
+	if !cfg.EnableOOBLoadReport {
+		w.stopORCAListener = nil
+		return
+	}


Is the first config update ok to be OOB? Then oldCfg would hit the nil check on 439, and this function work proceed as normal. It feels weird though that the default is off, but the first config has the bool set, so why not just use the bool in the first config since a config received is what triggers this call in the first place?

By default also means zero value I guess, and your code makes it work correctly.

oldCfg = the "current state of the wsc". But on the first call, there is no current state. Not really, anyway.

I have moved the initialization to happen at initialization time, which is better.

balancer/weightedroundrobin/balancer.go

dfawley

All comments addressed!

balancer/weightedroundrobin/balancer.go

balancer/weightedroundrobin/balancer_test.go

balancer/weightedroundrobin/internal/internal.go

balancer/weightedroundrobin/scheduler.go

dfawley · 2023-05-04T22:28:34Z

balancer/weightedroundrobin/scheduler.go

+}
+
+// A simple RR scheduler to use for fallback when all weights are zero or the
+// same or when only one subconn exists.


balancer/weightedroundrobin/balancer_test.go

zasweq

All comments minor. LGTM otherwise though.

balancer/weightedroundrobin/balancer.go

balancer/weightedroundrobin/balancer_test.go

balancer/weightedroundrobin/internal/internal.go

zasweq · 2023-05-05T20:23:18Z

balancer/weightedroundrobin/balancer.go

+	// and if the scheduler is replaced during this usage, we want to use the
+	// scheduler that was live when the pick started.


is replaced after reading and usage, continue to use the scheduler that was read. or something like that.

I can't see what's wrong with what I've written.

"We want to" is not strong enough language. I don't really care about this though minor nit.

balancer/weightedroundrobin/weightedroundrobin.go

balancer/weightedroundrobin/balancer_test.go

zasweq · 2023-05-05T20:29:28Z

balancer/weightedroundrobin/balancer_test.go

+	ctx, cancel := context.WithTimeout(context.Background(), defaultTestTimeout)
+	defer cancel()
+
+	var mu sync.Mutex
+	start := time.Now()
+	now := start
+	setNow := func(t time.Time) {
+		mu.Lock()
+		defer mu.Unlock()
+		now = t
+	}
+	iwrr.TimeNow = func() time.Time {
+		mu.Lock()
+		defer mu.Unlock()
+		return now
+	}
+	t.Cleanup(func() { iwrr.TimeNow = time.Now })
+
+	srv1 := startServer(t, reportBoth)
+	srv2 := startServer(t, reportBoth)
+
+	// srv1 starts loaded and srv2 starts without load; ensure RPCs are routed
+	// disproportionately to srv2 (10:1).  Because the OOB reporting interval
+	// is 1 minute but the weights expire in 1 second, routing will go to 50/50
+	// after the weights expire.
+	srv1.oobMetrics.SetQPS(10.0)
+	srv1.oobMetrics.SetCPUUtilization(1.0)
+
+	srv2.oobMetrics.SetQPS(10.0)
+	srv2.oobMetrics.SetCPUUtilization(.1)


Line 514 - 547 are shared. Sorry, the comment didn't include the lines. I think due to the thirty lines of shared code repeated 3 times, you can pull into helper.

zasweq · 2023-05-05T20:30:34Z

balancer/weightedroundrobin/balancer_test.go

+	// srv1 starts loaded and srv2 starts without load; ensure RPCs are routed
+	// disproportionately to srv2 (10:1).  Errors are set (but ignored
+	// initially) such that RPCs will be routed 50/50.
+	srv1.oobMetrics.SetQPS(10.0)
+	srv1.oobMetrics.SetCPUUtilization(1.0)
+	srv1.oobMetrics.SetEPS(0)
+	// srv1 weight before: 10.0 / 1.0 = 10.0
+	// srv1 weight after:  10.0 / 1.0 = 10.0
+
+	srv2.oobMetrics.SetQPS(10.0)
+	srv2.oobMetrics.SetCPUUtilization(.1)
+	srv2.oobMetrics.SetEPS(10.0)
+	// srv2 weight before: 10.0 / 0.1 = 100.0
+	// srv2 weight after:  10.0 / 1.0 = 10.0


Can you specify what 0 and 10 mean wrt EPS and errors.

zasweq

All comments minor. LGTM otherwise though.

balancer/weightedroundrobin/balancer.go

zasweq · 2023-05-05T20:34:59Z

balancer/weightedroundrobin/balancer.go

+	// or when registering a new listener, as those calls require the ORCA
+	// producer mu which is held when calling the listener, and the listener


why does holding the producer mu have anything to do with this mu? Are you saying that that's what guarantees mutual exclusion on accesses? I get the last bit about the listener callback also grabs mu so can't use this mu.

The ORCA producer holds a mutex when calling the listeners. If the listeners do something that requires that mutex (basically, register/unregister listeners), we get a deadlock. Transitively, if the listeners share a mutex with another part of the code that holds that mutex while registering/unregistering listeners, we get a deadlock.

I get that wrt deadlock scenarios. However, I'm asking why you mention the second producerMu. Is it to get around this deadlock that would happen if you grab the same mutex? (and can you clarify this in comment)

zasweq

LGTM.

dfawley · 2023-05-05T20:43:25Z

Flake in the first run is #6258. I'll run a few more times on GA and see if I can reproduce the failure with the scheduler pointer. I was never able to reproduce it locally, but found and fixed a handful of other things, so maybe it's gone now?

dfawley · 2023-05-05T21:26:16Z

Forced push to pull in 6258 as it was hitting that race a lot.

dfawley · 2023-05-05T21:40:02Z

Ohhhh... I think the problem with the bug I was seeing might be that an unsafe.Pointer is 64 bits, and the scheduler was not the first entry in the struct. I was only seeing problems on 386 and ARM, so I'm 99% sure that was it.. Debugging code removed & I think this is done! (hopefully??)

dfawley · 2023-05-05T21:51:26Z

That wasn't it, either.. But the other instrumentation I put in found it... The rrScheduler was being used and the cast to int from inc() was the problem.

Why does go use the signed int type for slice accesses and length?! Slices can't ever be negative...

dfawley added the Type: Feature label May 2, 2023

dfawley added this to the 1.56 Release milestone May 2, 2023

dfawley requested a review from zasweq May 2, 2023 01:09

dfawley assigned zasweq May 2, 2023

dfawley force-pushed the wrr branch from 7dfba4d to b97f8bb Compare May 2, 2023 22:05

dfawley changed the title ~~balancer/weightedroundrobin: add load balancing policy~~ balancer/weightedroundrobin: add load balancing policy (A58) May 2, 2023

dfawley force-pushed the wrr branch from b97f8bb to 7c79656 Compare May 2, 2023 22:18

zasweq requested changes May 3, 2023

View reviewed changes

zasweq reviewed May 3, 2023

View reviewed changes

balancer/weightedroundrobin/balancer.go Outdated Show resolved Hide resolved

zasweq assigned dfawley and unassigned zasweq May 3, 2023

dfawley assigned zasweq and unassigned dfawley May 3, 2023

dfawley commented May 3, 2023

View reviewed changes

balancer/weightedroundrobin/balancer.go Show resolved Hide resolved

balancer/weightedroundrobin/config.go Outdated Show resolved Hide resolved

balancer/weightedroundrobin/scheduler.go Show resolved Hide resolved

zasweq reviewed May 4, 2023

View reviewed changes

zasweq requested changes May 4, 2023

View reviewed changes

zasweq assigned dfawley and unassigned zasweq May 4, 2023

dfawley commented May 4, 2023

View reviewed changes

dfawley assigned zasweq and unassigned dfawley May 4, 2023

dfawley force-pushed the wrr branch from 0aa8699 to 9fde6b5 Compare May 5, 2023 16:38

zasweq reviewed May 5, 2023

View reviewed changes

balancer/weightedroundrobin/balancer.go Show resolved Hide resolved

zasweq reviewed May 5, 2023

View reviewed changes

zasweq approved these changes May 5, 2023

View reviewed changes

zasweq assigned dfawley May 5, 2023

zasweq removed their assignment May 5, 2023

dfawley added 9 commits May 5, 2023 14:25

balancer/weightedroundrobin: add load balancing policy

b648c10

fix random starting point and improve tests

2a52e41

review comments

f334858

review comments 2

b2d14c8

cleanup instead of defer to fix race detector

3a95a38

review comments 3

ecdda7f

debugging

df456e3

fix races

3d0e223

review comments

cac75d4

dfawley force-pushed the wrr branch from 235da86 to cac75d4 Compare May 5, 2023 21:25

dfawley added 2 commits May 5, 2023 14:35

more debugging

0386f4e

no debugging

3589e6e

found the bad cast

565032f

review comments

c9a55f0

dfawley merged commit 5c4bee5 into grpc:master May 8, 2023
11 checks passed

dfawley deleted the wrr branch May 8, 2023 17:01

atollena mentioned this pull request Jul 25, 2023

Rename weighted_round_robin_experimental into weighted_round_robin #6476

Closed

github-actions bot locked as resolved and limited conversation to collaborators Nov 5, 2023

		// By default we set load reports to off, because they are not running
		// upon initial weightedSubConn creation.

		// and if the scheduler is replaced during this usage, we want to use the
		// scheduler that was live when the pick started.

		// or when registering a new listener, as those calls require the ORCA
		// producer mu which is held when calling the listener, and the listener

balancer/weightedroundrobin: add load balancing policy (A58) #6241

balancer/weightedroundrobin: add load balancing policy (A58) #6241

Conversation

dfawley commented May 2, 2023 • edited

zasweq commented May 2, 2023

zasweq commented May 2, 2023

zasweq left a comment • edited

Choose a reason for hiding this comment

dfawley left a comment

Choose a reason for hiding this comment

zasweq 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

Choose a reason for hiding this comment

Choose a reason for hiding this comment

zasweq 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

Choose a reason for hiding this comment

dfawley left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

zasweq 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

zasweq left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

zasweq May 8, 2023 • edited

Choose a reason for hiding this comment

zasweq left a comment • edited

Choose a reason for hiding this comment

dfawley commented May 5, 2023

dfawley commented May 5, 2023

dfawley commented May 5, 2023

dfawley commented May 5, 2023

dfawley commented May 2, 2023 •

edited

zasweq left a comment •

edited

zasweq May 8, 2023 •

edited

zasweq left a comment •

edited