rebalance moves tenants from the most-loaded to the least-loaded shard while the spread exceeds the threshold and a strictly improving move exists.
(in PlacementInput, k int, assign map[string]string, load []int, members [][]TenantInfo)
| 115 | // rebalance moves tenants from the most-loaded to the least-loaded shard while |
| 116 | // the spread exceeds the threshold and a strictly improving move exists. |
| 117 | func rebalance(in PlacementInput, k int, assign map[string]string, load []int, members [][]TenantInfo) { |
| 118 | if k < 2 || in.RebalanceThreshold <= 0 { |
| 119 | return |
| 120 | } |
| 121 | total := 0 |
| 122 | for _, l := range load { |
| 123 | total += l |
| 124 | } |
| 125 | if total == 0 { |
| 126 | return |
| 127 | } |
| 128 | avg := float64(total) / float64(k) |
| 129 | |
| 130 | for iter := 0; iter < len(in.Tenants); iter++ { |
| 131 | maxIdx, minIdx := argmaxLoad(load), argminLoad(load) |
| 132 | spread := load[maxIdx] - load[minIdx] |
| 133 | if float64(spread)/avg <= in.RebalanceThreshold { |
| 134 | return |
| 135 | } |
| 136 | |
| 137 | // Pick the move that most reduces the spread between the two shards; |
| 138 | // among equal reductions prefer the smaller tenant (cheaper handoff). |
| 139 | best := -1 |
| 140 | bestSpread, bestWeight := spread, 0 |
| 141 | for i, t := range members[maxIdx] { |
| 142 | if t.Deleting || t.Weight == 0 { |
| 143 | continue |
| 144 | } |
| 145 | // Honor only pins ComputePlacement itself honors: a pin to a |
| 146 | // non-existent shard is ignored at placement time, so it must not |
| 147 | // make the tenant sticky here either. |
| 148 | if pin, pinned := in.Pinned[t.Namespace]; pinned { |
| 149 | if idx, ok := ParseShardIndex(pin); ok && idx < k { |
| 150 | continue |
| 151 | } |
| 152 | } |
| 153 | if in.CanRebalance != nil && !in.CanRebalance(t.Namespace) { |
| 154 | continue |
| 155 | } |
| 156 | newSpread := abs((load[maxIdx] - t.Weight) - (load[minIdx] + t.Weight)) |
| 157 | if newSpread < bestSpread || (newSpread == bestSpread && best >= 0 && t.Weight < bestWeight) { |
| 158 | best, bestSpread, bestWeight = i, newSpread, t.Weight |
| 159 | } |
| 160 | } |
| 161 | if best < 0 || bestSpread >= spread { |
| 162 | return |
| 163 | } |
| 164 | |
| 165 | t := members[maxIdx][best] |
| 166 | members[maxIdx] = append(members[maxIdx][:best:best], members[maxIdx][best+1:]...) |
| 167 | members[minIdx] = append(members[minIdx], t) |
| 168 | load[maxIdx] -= t.Weight |
| 169 | load[minIdx] += t.Weight |
| 170 | assign[t.Namespace] = ShardName(minIdx) |
| 171 | } |
| 172 | } |
| 173 | |
| 174 | // argminLoad returns the least-loaded shard index, tie-break lowest index. |
no test coverage detected