# UNDF: UNDF-2026-000000099
# hadoop-0004: HDFS Balancer Dispatcher — srcBlocks ArrayList.contains() O(n²) in block receive loop

## Severity
HIGH — called on every block report during HDFS balancing; grows quadratically with blocks per source datanode

## File
`hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/balancer/Dispatcher.java`

## Lines
807 (`srcBlocks` field declaration), 910 (`!srcBlocks.contains(block)` inside per-block loop)

Also:
`hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/balancer/MovedBlocks.java`
Line 43 (`locations` field), 56 (`addLocation` does `locations.contains(loc)` inside a per-datanode loop)

## Pattern
CWE-407: O(n) ArrayList.contains() inside a loop.

### Dispatcher.java

```java
// DEFECTIVE (line 807)
private final List<DBlock> srcBlocks = new ArrayList<DBlock>();

// DEFECTIVE (line 910) — inside for (BlockWithLocations blkLocs : newBlksLocs.getBlocks())
if (!srcBlocks.contains(block) && isGoodBlockCandidate(block)) {
    srcBlocks.add(block);
}
```

`srcBlocks` is an `ArrayList`. Each call to `getReceivedBlocks()` iterates all blocks in
`newBlksLocs` and checks `srcBlocks.contains(block)` — O(S) where S = current size of srcBlocks.
For B blocks reported, total cost is O(B × S) = O(B²) as S grows toward B.

During HDFS balancing of a large cluster (millions of blocks per datanode), this becomes the
dominant inner-loop cost.

### MovedBlocks.java (same PR)

```java
// DEFECTIVE (line 43)
protected final List<L> locations = new ArrayList<L>(3);

// DEFECTIVE (line 56) — called inside the same block location update loop
public synchronized void addLocation(L loc) {
    if (!locations.contains(loc)) {   // O(L) per call
        locations.add(loc);
    }
}
```

`addLocation` is called for each datanode UUID in `blkLocs.getDatanodeUuids()` for each block.
With D datanodes/block and L existing locations per block: O(D × L). Across B blocks: O(B × D × L).

## Fix

**Dispatcher.java**: Replace `ArrayList<DBlock>` with `LinkedHashSet<DBlock>` (preserves
insertion order for deterministic iteration, O(1) contains):

```java
// FIXED
private final Set<DBlock> srcBlocks = new LinkedHashSet<DBlock>();
```

**MovedBlocks.java**: Replace `ArrayList<L>` with `LinkedHashSet<L>`:

```java
// FIXED
protected final Set<L> locations = new LinkedHashSet<L>(3);
```

## Complexity
- Before: O(B²) for block reporting during balance; O(B × D × L) for location updates
- After: O(B) for block reporting; O(B × D) for location updates

## Impact
HDFS Balancer is a background maintenance operation on large clusters. For a node with 100k
blocks, this defect makes block reporting O(10^10) rather than O(10^5). Real-world balancer
runs are visibly slow on large clusters; this is a documented operational pain point.
