UNDF: UNDF-2026-000000103

hbase-0002: BaseLoadBalancer.randomAssignment — usedSNs ArrayList.contains() O(n²) in assignment loop

Severity

HIGH — called for every region assignment and on every random assignment fallback during region open; O(S²) where S = number of servers; materializes on large clusters during rolling restart or mass region reassignment.

File

hbase-balancer/src/main/java/org/apache/hadoop/hbase/master/balancer/BaseLoadBalancer.java

Lines

465 (usedSNs declaration), 470 and 478 (usedSNs.contains() inside do-while and for loops)

Pattern

CWE-407: O(n) ArrayList.contains() inside two nested loops.

// DEFECTIVE (line 465)
List<ServerName> usedSNs = new ArrayList<>(servers.size());

// DEFECTIVE (line 467-473) — do-while loop, up to numServers * 4 iterations
do {
    int i = rand.nextInt(numServers);
    sn = servers.get(i);
    if (!usedSNs.contains(sn)) {   // O(usedSNs.size()) per iteration
        usedSNs.add(sn);
    }
} while (cluster.wouldLowerAvailability(regionInfo, sn) && iterations++ < maxIterations);

// DEFECTIVE (line 477-486) — fallback for loop over all servers
if (iterations >= maxIterations) {
    for (ServerName unusedServer : servers) {
        if (!usedSNs.contains(unusedServer)) {   // O(usedSNs.size()) per server

usedSNs is an ArrayList. In the do-while loop, contains is called up to numServers * 4 times, each O(usedSNs.size()). In the fallback for-loop, contains is called for each server — O(S) iterations, each O(S) = O(S²) total.

For a cluster with S=500 servers (typical large HBase), the fallback path costs O(250,000) operations rather than O(500).

Fix

Replace ArrayList with LinkedHashSet:

// FIXED
Set<ServerName> usedSNs = new LinkedHashSet<>(servers.size());

contains() and add() both become O(1). No behavior change — the usedSNs collection is only tested for membership, never indexed.

Complexity

Before: O(S²) worst-case per assignment (fallback path) + O(S) per do-while amortized
After: O(S) worst-case per assignment

Impact

randomAssignment() is called:

During initial bulk assignment on cluster startup
For each region that needs reassignment when no preferred server is available
During rolling restart — every region gets reassigned

On a 500-server cluster with 200k regions, the fallback path triggered by wouldLowerAvailability can make the balancer loop take minutes instead of seconds.

2.4 KiB Raw Permalink Blame History