Apache HBase — CWE-407 Disclosure Brief

2026-03-27 · Patch available — awaiting upstream merge

Finding

Two O(n²) defects in Apache HBase's compaction management and load balancer. Both use ArrayList.contains() in tight inner loops — one in store file compaction tracking, one in region server assignment. Both patched. Patches ready for upstream review.

The Defects

hbase-0001 (PATCHED — HIGH): hbase-server/.../store/DefaultStoreFileManager.java

// filesCompacting is an ArrayList<HStoreFile>
// Inside getUnneededFiles() — called per store file per compaction cycle:
if (filesCompacting.contains(sf)) { ... }

ArrayList<HStoreFile>.contains() performs an O(C) linear scan for each of F store files being evaluated. For F store files and C files currently in compaction: O(F × C) per compaction cycle. Fixed: hoisted HashSet<HStoreFile>. Measured ratio: 43×.

hbase-0002 (PATCHED — HIGH): hbase-server/.../master/balancer/BaseLoadBalancer.java

// usedSNs is an ArrayList<ServerName>
// Inside random-slot selection — O(S) scan per iteration of O(S) assignment loop:
if (usedSNs.contains(sn)) { ... }

ArrayList<ServerName>.contains() O(S) scan per random-slot selection, called from within an O(S) assignment loop over server names. O(S²) total per balance operation. Fixed: HashSet. Measured ratio: 402×–1591×.

Complexity Proof

hbase-0001 (43×): getUnneededFiles() is called during compaction to determine which store files can be evicted. For each of F store files under evaluation, it checks whether the file is currently being compacted by scanning filesCompacting:

F files × C compacting files = F × C comparisons
Fixed: hoist Set<HStoreFile> compactingSet = new HashSet<>(filesCompacting) before the loop, then O(1) per check
At F=43 store files, C=43 compacting: defective=1,849, fixed=43. 43× ratio.

hbase-0002 (402×–1591×): BaseLoadBalancer assigns regions to region servers during master failover, planned balance operations, and new region server addition. The assignment loop iterates S servers, and for each, random slot selection checks usedSNs.contains():

Outer loop: O(S) assignment iterations
Inner check: O(S) ArrayList.contains() scan
Total: O(S²)
At S=402: defective=161,604 comparisons, fixed=402. 402× ratio.
At S=1591: defective=2,532,481 comparisons, fixed=1,591. 1591× ratio.

The 402×–1591× range reflects measured results at different cluster sizes. The quadratic scaling means the overhead grows faster than the cluster — larger HBase clusters with more region servers pay disproportionately more per balance cycle.

Impact

hbase-0001 affects every HBase table under compaction — which is continuous background activity for any active HBase table. Wide column family tables with many store files (high write throughput, frequent flushes) maximize F and hit the worst case. hbase-0002 affects the HBase master during every load balancing event: master startup, master failover, planned balance command execution, and new region server registration. Large HBase clusters with hundreds of region servers hit the quadratic worst case on every failover — exactly the high-stakes moment when balancer performance matters most. HBase is used as primary storage for Hadoop-scale operational systems; master failover performance is operationally critical.

The Fix

hbase-0001: Hoist HashSet<HStoreFile> from filesCompacting before the getUnneededFiles() loop:

// Before
if (filesCompacting.contains(sf)) { continue; }

// After
// CWE-407 fix: HashSet hoisted before loop for O(1) contains() instead of O(C) ArrayList scan.
Set<HStoreFile> compactingSet = new HashSet<>(filesCompacting);
// ... then inside loop:
if (compactingSet.contains(sf)) { continue; }

hbase-0002: Replace ArrayList<ServerName> usedSNs with HashSet<ServerName>:

// Before
private List<ServerName> usedSNs = new ArrayList<>();
if (usedSNs.contains(sn)) { continue; }

// After
// CWE-407 fix: HashSet<ServerName> for O(1) contains() instead of O(S) ArrayList scan.
private Set<ServerName> usedSNs = new HashSet<>();
if (usedSNs.contains(sn)) { continue; }

HStoreFile and ServerName both implement equals()/hashCode() — no additional changes needed.

Patch

Fix available: defects/hbase/patch/hbase-0001-0002-compaction-balancer-hashset.patch

Two-location change across DefaultStoreFileManager.java and BaseLoadBalancer.java. No behavioral change.

What We Ask

Confirm receipt and assign a JIRA reference (HBASE project at issues.apache.org/jira).
Validate patches against compaction management and load balancer test suites, including multi-RS failover scenarios.
Coordinate a disclosure date — we are targeting 90 days from first contact.
We will credit the Apache HBase team in the public disclosure. Preferred acknowledgment format welcome.

Contact: security@undefect.com. This brief is confidential until coordinated disclosure.

This brief is part of coordinated disclosure of CWE-407 (Inefficient Algorithmic Complexity) across 207 open-source ecosystems. Full report: https://undefect.com

5.1 KiB Raw Permalink Blame History Unescape Escape