zhangyue19921010 commented on PR #13265:
URL: https://github.com/apache/hudi/pull/13265#issuecomment-2862819190
> what is the part the local partitioner missed so that data skew was
induced compared to the global partitioner proposed here?
# Analysis of Local Hash Algorithm Limitations
The Local Hash algorithm has two critical flaws:
1. **Uneven Distribution** causing long-tail effects, degrading resource
utilization and execution efficiency.
2. **Underutilized Parallelism** leading to idle Tasks (empty processing).
---
## Case 1: Data Skew
### Problem
When `bucketNum` and `parallelism` share a common factor `d > 1`, the
`curBucket` values for each partition are confined to a fixed subset of `d`
partition IDs. This results in **Uneven Distribution** and **Data Skew**.
### Example
- **Parameters**:
`parallelism = 6`, `bucketNum = 4` (common factor `d = 2`).
- **Partition A** (hash mod 6 = 2):
- `partitionIndex = 2 * 4 = 8`
- `globalIndex` for `curBucket = 0,1,2,3`: `8, 9, 10, 11`
- **Result**: Partition IDs `2, 3, 4, 5` (skewed to upper half).
- **Partition B** (hash mod 6 = 0):
- `curBucket` maps to Partition IDs `0, 1, 2, 3`.
- **Outcome**:
Partitions `0-3` handle most data, while `4-5` are underutilized.
---
## Case 2: Incomplete Coverage of Partition IDs
### Problem
A shared factor `d > 1` between `bucketNum` and `parallelism` restricts the
coverage of partition IDs to **`parallelism/d` unique values**. The modulo
operation cycles within a fixed subset of residues, leaving some partitions
unused.
### Example
- **Parameters**:
`parallelism = 6`, `bucketNum = 4` (common factor `d = 2`).
- **Partition** (hash mod 6 = 2):
- `partitionIndex = 2 * 4 = 8`
- `globalIndex` for `curBucket = 0,1,2,3`: `8, 9, 10, 11`
- **Modulo 6 Results**: `2, 3, 4, 5`
- **Consequence**:
Partition IDs `0` and `1` are **never assigned**, resulting in idle Tasks.
---
## Root Cause
The algorithm’s reliance on multiplicative offsets (partitionIndex = hash %
parallelism * bucketNum) and modulo arithmetic amplifies skew **when bucketNum
and parallelism share common factors**. This design flaw inherently limits the
effective parallelism and exacerbates resource imbalance.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
