Analyze MapReduce Reducer Skew | System Design Practice | AlgoMaster.io

Analyze MapReduce Reducer Skewmedium

Analyze MapReduce Reducer Skew

medium

MapReduce sends every intermediate key to one reducer. A hot key can therefore overload one reducer even when the number of reducers is large.

Design ReducerLoadAnalyzer(int reducerCount) with:

int[] loads(String[] keys, int[] weights), returning total weight per reducer.
int hotReducer(String[] keys, int[] weights), returning the lowest-index reducer with maximum load.

Hash every key with unsigned 32-bit arithmetic:

Example 1:

Example 2:

Constraints

1 <= reducerCount <= 100
0 <= keys.length <= 10^4
keys.length == weights.length
Keys contain ASCII letters and digits.
0 <= weights[i] <= 10^6
Every reducer load fits in a signed 32-bit integer.

Hints

Loading...

Call	Returns
new ReducerLoadAnalyzer(2)	null
loads(["a","b","a","c"], [10,20,5,30])	[20,45]
hotReducer(["a","b","a","c"], [10,20,5,30])	1

b hashes to reducer 0. Both a records and c hash to reducer 1, producing loads 20 and 45.

Run checks these cases. Submit also runs a larger hidden set.