Function plan_graph_split

nodedb-cluster/src/shard_split.rs:112–201

Plan a graph-aware shard split. Uses BFS-based community detection to partition nodes into two groups that minimize cross-shard edges. Starting from a seed node, BFS assigns the first half of discovered nodes to group A, the rest to group B. This is a greedy heuristic — not optimal like METIS, but O(V+E) and practical for online splitting without blocking queries.

(
    source_vshard: u32,
    new_vshard: u32,
    target_node: u64,
    node_ids: &[String],
    edges: &[(String, String)],
)

/// This is a greedy heuristic — not optimal like METIS, but O(V+E) and
/// practical for online splitting without blocking queries.
pub fn plan_graph_split(
    source_vshard: u32,
    new_vshard: u32,
    target_node: u64,
    node_ids: &[String],
    edges: &[(String, String)],
) -> SplitPlan {
    if node_ids.is_empty() {
        return SplitPlan {
            source_vshard,
            new_vshard,
            target_node,
            documents_to_move: Vec::new(),
            strategy: SplitStrategy::GraphCommunity,
            estimated_bytes: 0,
        };
    }

    // Build adjacency list for BFS.
    let mut adj: HashMap<&str, Vec<&str>> = HashMap::new();
    for (src, dst) in edges {
        adj.entry(src.as_str()).or_default().push(dst.as_str());
        adj.entry(dst.as_str()).or_default().push(src.as_str());
    }

    // BFS from first node, assign first half to group A.
    let mut visited: Vec<String> = Vec::with_capacity(node_ids.len());
    let mut seen: HashSet<&str> = HashSet::new();
    let mut queue: std::collections::VecDeque<&str> = std::collections::VecDeque::new();

    // Start BFS from the node with the most edges (hub).
    let start = node_ids
        .iter()
        .max_by_key(|id| adj.get(id.as_str()).map(|v| v.len()).unwrap_or(0))
        .map(|s| s.as_str())
        .unwrap_or(node_ids[0].as_str());

    queue.push_back(start);
    seen.insert(start);

    while let Some(node) = queue.pop_front() {
        visited.push(node.to_string());
        if let Some(neighbors) = adj.get(node) {
            for &neighbor in neighbors {
                if seen.insert(neighbor) {
                    queue.push_back(neighbor);
                }
            }
        }
    }

    // Add any disconnected nodes not reached by BFS.
    for id in node_ids {
        if seen.insert(id.as_str()) {
            visited.push(id.clone());
        }
    }