Rebalance Shards

You have N nodes holding shards with varying sizes. The current node loads are provided, along with the list of shards and their assigned node.

Rebalance by repeatedly moving shards from the most-loaded node to the least-loaded node until the load difference is within delta:

Algorithm (repeat):

1. Find node hi with max load (tie -> lowest index).
2. Find node lo with min load (tie -> lowest index).
3. If load[hi] - load[lo] <= delta, stop.
4. Move the largest shard on node hi (tie -> lowest shard ID) to node lo.
5. Update loads and continue.

Stop early if a move would not reduce the max-min load gap (to avoid oscillation).

Return the list of moves in order.

Types

type Shard struct {
    ID   int
    Size int
    Node int
}

type Move struct {
    ShardID int
    From    int
    To      int
}

Function signature

func RebalanceShards(loads []int, shards []Shard, delta int) []Move

Example

loads  = [10, 3]
shards = [{ID:1, Size:4, Node:0}, {ID:2, Size:6, Node:0}, {ID:3, Size:3, Node:1}]
delta  = 2

Move shard 2 (size 6) from 0 -> 1
Result moves: [{ShardID:2, From:0, To:1}]

Constraints

• 1 <= len(loads) <= 1000
• 0 <= len(shards) <= 10000
• 0 <= delta <= 1_000_000

Notes

• If a node has no shards, it cannot be the source of a move.