storage: Keep leaseholders close to where their requests are coming from ("Leaseholders follow the sun")

[a-robinson]

This is a feature request explained by the last paragraph of the motivation section of the leaseholder rebalancing RFC. Excerpt copied below:

"""
The last goal is to place the leaseholder for a range near the gateway node that is accessing the range in order to minimize network RTT. As an obvious example: it is preferable for the leaseholder to be in the same datacenter as the gateway node. Note that there is usually more than one gateway node accessing a range and there will common workloads where the traffic from gateway nodes is not coming from a single locality making it impossible to satisfy this goal. In general, we'd like to minimize the aggregate RTT for accessing the range which makes the mixture of reads and writes important (reads only need a round-trip from the gateway to the leaseholder while writes need a round-trip to the leaseholder and from the leaseholder to a quorom of followers). Also, this goal is at odds with the second goal of distributing load throughout a cluster and we'll need to be careful with heuristics here. It may be beneficial to place the leaseholder in the same datacenter as the gateways accessing the range, but doing so can lower total throughput depending on the workload and if the latencies between datacenters are small.
"""

[a-robinson]

I've added tooling to allocsim to specify which localities the request load should be on and to print out the number of lease transfers per-node in addition to current number of leases held by each node. My goal has been to then try to optimize latency without hurting throughput while also keeping the rate of lease transfers to avoid thrashing.

I've focused the testing on 2 different latency configurations and 2 different workloads, comparing the results from before my changes to the results after my changes. All configurations have 3 nodes, each in a different locality, and 32 workers sending the cluster requests. All testing is just being done on my laptop.

Specifically, I'm using these 4 configurations:

1. 0ms of latency between each node, balanced load (11 worker on node 1 / 11 on node 2 / 10 on node 3)
2. 50ms of latency between each node, balanced load (11 / 11 / 10)
3. 0ms of latency between each node, 32 workers of load on node 2 (none on nodes 1 and 3)
4. 50ms of latency between each node, 32 workers of load on node 2 (none on nodes 1 and 3)

I'm getting good results on all cases after some tweaking of the heuristic, but I'm worried that the load generation mechanism may be influencing results a little too much. The 32 workers isn't maxing out my machine, so the limiting factor in how many requests go through the system is how long the client threads have to block on each request. This means that in case 2 (and even case 1 to a lesser extent), whichever node has the most leases will be able to serve requests the fastest, which means it'll serve the most requests, which means that it'll continue to hold all the leases. This behavior isn't truly wrong, but it feels like it's not testing the right thing. Thus, I want to do some testing with a fixed number of requests/node/sec to examine just the latency.

What suggestions do you have for what else should be tested? I've listed a few possibilities below, but it won't be feasible to try every exhaustive combination of configurations.

• Fixed number of requests/node/sec
• Different numbers of nodes per locality
• More localities
• Different latency numbers or worker distributions
• Request distributions that change over time

@petermattis @BramGruneir

[petermattis]

In scenario 1, I would expect the heuristic to evenly balance the leases amongst the nodes. Specifically, I would expect the new reactive lease balancing heuristic to not have any effect and the system to have the same behavior as it does now (before the new heuristic is added). Sounds like that isn't the case and I'm curious why. Can you expand on the details of the heuristic you're using?

[a-robinson]

The real explanation is in the third paragraph of my post above - "whichever node has the most leases will be able to serve requests the fastest, which means it'll serve the most requests, which means that it'll continue to hold all the leases. This behavior isn't truly wrong, but it feels like it's not testing the right thing. Thus, I want to do some testing with a fixed number of requests/node/sec to examine just the latency."

To expand on that a bit, this change doesn't just make leases respond to latency, but also to request load. A locality that's getting all the requests will still be favored for lease placement over other localities even when the latency between them is low, because the latency between them is always non-zero. The effect won't be as strong as when the latency is higher, but there's still an effect.

When I changed allocsim to round-robin its requests across all nodes evenly rather than allocate a number of workers to each node, this behavior went away and the leases went back to balancing evenly.

---

The heuristic I'm currently using is effectively:

1. If we don't have any or enough request count data for the range, fall back to the existing logic
2. Take the per-node data from the RPC heartbeats and merge it into per-locality latency averages
3. Calculate a "weight" for each replica based on where requests are coming from, the DiversityScore of how the request locality compares to each replica locality (so replicas with more similarity to the request locality get more "weight"), and the latency to the request locality. I believe this is currently isn't weighting the latency strongly enough and am going to play with it some more this morning.
4. Use the "weight" to adjust the rebalanceThreshold that affects what's considered overfull/underfull. Right now this is adjusting it as rebalanceThreshold := defaultRebalanceThreshold - math.Log(otherReplicaWeight / currentLeaseholderWeight), then using it similarly to how it's currently used to determine which stores are overfull/underfull with respect to that replica.
5. Pick the replica with the most extreme overfull/underfull numbers, whether that's the existing leaseholder or a remote leaseholder.

It could still use some tweaking to use latency a little more heavily and to more strongly prefer not transferring leases in the face of changing workloads. The allocsim workloads I've been using don't change over time, so aren't stressing the allocation stability in that sense.

[petermattis]

whichever node has the most leases will be able to serve requests the fastest, which means it'll serve the most requests, which means that it'll continue to hold all the leases

This might be an artifact of running multiple nodes on one machine. In a real cluster, a single machine would eventually hit a limit on the number of requests it could service and distributing leases to other nodes would improve overall performance (assuming the latencies to the other nodes are low enough).