# 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.

```java
// 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`:

```java
// 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:
1. During initial bulk assignment on cluster startup
2. For each region that needs reassignment when no preferred server is available
3. 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.