Function assign_hierarchical

pub fn assign_hierarchical<W, A, V, S>(
    workers: &BTreeMap<W, NonZeroUsize>,
    actors: &[A],
    virtual_nodes: &[V],
    salt: S,
    actor_capacity_mode: CapacityMode,
    balanced_by: BalancedBy,
) -> Result<BTreeMap<W, BTreeMap<A, Vec<V>>>>
where
    W: Ord + Hash + Eq + Clone + Debug,
    A: Ord + Hash + Eq + Copy + Clone + Debug,
    V: Hash + Eq + Copy + Clone + Debug,
    S: Hash + Copy,

Hierarchically distributes virtual nodes to actors in two weighted stages with deterministic tie-breaking.

This function first assigns each actor to a worker, then distributes all virtual nodes among those active workers, and finally partitions each worker’s vnodes among its actors in a simple round-robin fashion.

Type Parameters

• W: Worker identifier. Must implement Ord + Hash + Eq + Clone + Debug.
• A: Actor identifier. Must implement Ord + Hash + Eq + Copy + Clone + Debug.
• V: Virtual node type. Must implement Hash + Eq + Copy + Clone + Debug.
• S: Salt type for deterministic tie-breaking. Must implement Hash + Copy.

Parameters

• workers: A BTreeMap<W, NonZeroUsize> mapping each worker to its positive weight.
• actors: A slice of actors (&[A]) to place on workers.
• virtual_nodes: A slice of vnodes (&[V]) to distribute across actors.
• salt: A salt value to break ties in hashing, kept constant per invocation for reproducibility.
• actor_capacity_mode: A CapacityMode deciding how actors are packed onto workers:
  • Weighted: respect workers weights when placing actors.
  • Unbounded: ignore capacity limits when placing actors.
• balanced_by: A BalancedBy enum determining vnode distribution strategy:
  • RawWorkerWeights: prioritize original worker weights (with actor count as lower bound).
  • ActorCounts: prioritize equal vnode counts per actor (actor-oriented).

Returns

A BTreeMap<W, BTreeMap<A, Vec<V>>> mapping each worker to its map of actors and their assigned vnodes.

• Only workers with at least one actor appear in the result.
• Each actor receives at least one vnode (invariant).

Errors

• Returns an error if actors is empty or virtual_nodes is empty.
• Returns an error if actors.len() > virtual_nodes.len(), since each actor must receive at least one vnode.

Complexity

Runs in O((W + A + V) · log W + V · W) time:

• Actor → Worker assignment is O(A · W) via weighted rendezvous + O(W + A) map operations.
• VNode → Worker assignment is O(V · W) plus quota computation O(W log W).
• VNode → Actor partition is O(V).

Example

// Define two workers with numeric IDs and weights
let mut workers: BTreeMap<u8, NonZeroUsize> = BTreeMap::new();
workers.insert(1, NonZeroUsize::new(2).unwrap());
workers.insert(2, NonZeroUsize::new(3).unwrap());

// Actors also identified by numbers
let actors: Vec<u16> = vec![10, 20, 30];

// Virtual nodes are simple 0–8
let vnodes: Vec<u16> = (0..9).collect();

let assignment = assign_hierarchical(
    &workers,
    &actors,
    &vnodes,
    0u8,                          // salt
    CapacityMode::Weighted,       // actor -> worker mode
    BalancedBy::RawWorkerWeights, // vnode -> worker mode
)
.unwrap();

for (worker_id, actor_map) in assignment {
    println!("Worker {}:", worker_id);
    for (actor_id, vn_list) in actor_map {
        println!("  Actor {} -> {:?}", actor_id, vn_list);
    }
}

Algorithm

1. Actors → Workers

   • Use weighted or unbounded rendezvous hashing to assign each actor to exactly one worker, based on actor_capacity_mode and workers weights.
   • Build actor_to_worker: BTreeMap<W, Vec<A>>.

2. VNodes → Workers

   • If RawWorkerWeights: compute per-worker quotas with compute_worker_quotas, ensuring each active worker’s quota ≥ its actor count and quotas sum = total vnodes.
   • If ActorCounts: set each worker’s weight = its actor count.
   • Run assign_items_weighted_with_scale_fn on vnodes vs. the computed weights, yielding vnode_to_worker: BTreeMap<W, Vec<V>>.

3. VNodes → Actors

   • For each worker, take its vnode list and assign them to actors in simple round-robin: iterate vnodes in order, dispatching index % actor_list.len().
   • Collect into final BTreeMap<W, BTreeMap<A, Vec<V>>>.