Skip to content

Commit 4196cb4

Browse files
committed
[SPARK-48290][CORE][FOLLOWUP] Record every block tied at the skew cutoff in a bitmap
Blocks tied at the skew cutoff were rationed to fit spark.shuffle.maxAccurateSkewedBlockNumber, and a rotation derived from the map task id spread which of them each map task recorded. A tie the rotation leaves out falls back to avgSize, which it raises in the process, so AQE's skew threshold rises along with the sizes it is compared against. With twice as many ties as the cap the coverage is already an even 50% under any schedule, and every tied reducer still reports below the threshold, so no window schedule fixes it. The tied blocks all share one size, so record their membership rather than their sizes: a run-optimized RoaringBitmap alongside the existing emptyBlocks one, plus the shared compressed cutoff size. Ties are excluded from the avgSize average, since they are recorded exactly. The rotation, the tie counting pass and the map task id derived offset are gone, and the id and size arrays still hold only the blocks strictly above the cutoff, which nthSmallest bounds. Statuses with no ties share one never-mutated empty bitmap. The rotation tests asserted coverage and per-reducer error against a fixed target, which cannot see the threshold move, so they are replaced by one that computes the AQE skew threshold from the map statuses themselves and requires every skewed reducer to clear it, over three tie group and map task count ratios. The retained-memory test built exactly spark.shuffle.minNumPartitionsToHighlyCompress blocks, so it measured a CompressedMapStatus and passed with the skew path never running; it now uses one more block and asserts the status type and that the sizes were recorded.
1 parent d3be2ba commit 4196cb4

2 files changed

Lines changed: 162 additions & 113 deletions

File tree

‎core/src/main/scala/org/apache/spark/scheduler/MapStatus.scala‎

Lines changed: 57 additions & 55 deletions
Original file line numberDiff line numberDiff line change
@@ -191,6 +191,8 @@ private[spark] class CompressedMapStatus(
191191
* @param hugeBlockIds reduceIds of the accurately recorded blocks, in increasing order
192192
* @param hugeBlockSizes compressed sizes of the accurately recorded blocks, aligned with
193193
* hugeBlockIds
194+
* @param skewedBlocks a bitmap tracking which blocks are exactly `skewedBlockSize` bytes
195+
* @param skewedBlockSize the compressed size shared by every block in `skewedBlocks`
194196
* @param _mapTaskId unique task id for the task
195197
* @param _checksumVal checksum value for the task
196198
*/
@@ -205,16 +207,22 @@ private[spark] class HighlyCompressedMapStatus private (
205207
// heap per entry.
206208
private[this] var hugeBlockIds: Array[Int],
207209
private[this] var hugeBlockSizes: Array[Byte],
210+
// Blocks tied at the skew cutoff all have the same size, so only their membership has to be
211+
// recorded. A bitmap costs a fraction of what an id per block would, which is what allows
212+
// every tied block to be recorded rather than a capped subset of them.
213+
private[this] var skewedBlocks: RoaringBitmap,
214+
private[this] var skewedBlockSize: Byte,
208215
private[this] var _mapTaskId: Long,
209216
private[this] var _checksumVal: Long = 0)
210217
extends MapStatus with Externalizable {
211218

212219
// loc could be null when the default constructor is called during deserialization
213-
require(loc == null || avgSize > 0 || hugeBlockIds.length > 0
220+
require(loc == null || avgSize > 0 || hugeBlockIds.length > 0 || !skewedBlocks.isEmpty
214221
|| numNonEmptyBlocks == 0 || _mapTaskId > 0,
215222
"Average size can only be zero for map stages that produced no output")
216223

217-
protected def this() = this(null, -1, null, -1, null, null, -1, 0) // For deserialization only
224+
// For deserialization only
225+
protected def this() = this(null, -1, null, -1, null, null, null, 0, -1, 0)
218226

219227
override def location: BlockManagerId = loc
220228

@@ -228,7 +236,13 @@ private[spark] class HighlyCompressedMapStatus private (
228236
0
229237
} else {
230238
val i = Arrays.binarySearch(hugeBlockIds, reduceId)
231-
if (i >= 0) MapStatus.decompressSize(hugeBlockSizes(i)) else avgSize
239+
if (i >= 0) {
240+
MapStatus.decompressSize(hugeBlockSizes(i))
241+
} else if (skewedBlocks.contains(reduceId)) {
242+
MapStatus.decompressSize(skewedBlockSize)
243+
} else {
244+
avgSize
245+
}
232246
}
233247
}
234248

@@ -247,6 +261,8 @@ private[spark] class HighlyCompressedMapStatus private (
247261
out.writeByte(hugeBlockSizes(i))
248262
i += 1
249263
}
264+
skewedBlocks.serialize(out)
265+
out.writeByte(skewedBlockSize)
250266
out.writeLong(_mapTaskId)
251267
out.writeLong(_checksumVal)
252268
}
@@ -280,12 +296,21 @@ private[spark] class HighlyCompressedMapStatus private (
280296
hugeBlockIds = order.map(blockIds)
281297
hugeBlockSizes = order.map(blockSizes)
282298
}
299+
val skewed = new RoaringBitmap()
300+
skewed.deserialize(in)
301+
skewedBlocks = if (skewed.isEmpty) HighlyCompressedMapStatus.noSkewedBlocks else skewed
302+
skewedBlockSize = in.readByte()
283303
_mapTaskId = in.readLong()
284304
_checksumVal = in.readLong()
285305
}
286306
}
287307

288308
private[spark] object HighlyCompressedMapStatus {
309+
// Most shuffles record no skewed blocks at all, and the driver retains one map status per map
310+
// task, so those statuses share one empty bitmap rather than each allocating their own. It is
311+
// never mutated, which is what makes sharing it safe.
312+
private val noSkewedBlocks = new RoaringBitmap()
313+
289314
def apply(
290315
loc: BlockManagerId,
291316
uncompressedSizes: Array[Long],
@@ -309,13 +334,12 @@ private[spark] object HighlyCompressedMapStatus {
309334
Option(SparkEnv.get)
310335
.map(_.conf.get(config.SHUFFLE_ACCURATE_BLOCK_THRESHOLD))
311336
.getOrElse(config.SHUFFLE_ACCURATE_BLOCK_THRESHOLD.defaultValue.get)
312-
// Sizes at or above `threshold` are recorded accurately. Blocks of exactly `skewCutoff` are
313-
// only recorded while `numTiedSkewedBlocksToRecord` lasts, because there can be arbitrarily
314-
// many of them and recording them all would blow past SHUFFLE_MAX_ACCURATE_SKEWED_BLOCK_NUMBER.
337+
// Sizes at or above `threshold` are recorded accurately. At most
338+
// SHUFFLE_MAX_ACCURATE_SKEWED_BLOCK_NUMBER of them are strictly larger than `skewCutoff`, and
339+
// those are held as ids and sizes. There can be arbitrarily many blocks of exactly
340+
// `skewCutoff`, but they all share that one size, so only their membership is recorded.
315341
var skewCutoff = Long.MaxValue
316-
var numTiedSkewedBlocks = 0
317-
var numTiedSkewedBlocksToRecord = 0
318-
var tieRotationStart = 0
342+
var recordSkewedTies = false
319343
val threshold =
320344
if (accurateBlockSkewedFactor > 0) {
321345
val maxAccurateSkewedBlockNumber =
@@ -331,36 +355,15 @@ private[spark] object HighlyCompressedMapStatus {
331355
val medianSize: Long = Utils.medianInPlace(sizes)
332356
val firstAccurateIdx = totalNumBlocks - maxAccurateSkewedBlockNumber
333357
skewCutoff = Utils.nthSmallest(sizes, firstAccurateIdx)
334-
// At most `maxAccurateSkewedBlockNumber` sizes are strictly larger than `skewCutoff`, and
335-
// they all sit above `firstAccurateIdx` now, so counting them bounds how many blocks of
336-
// exactly `skewCutoff` may still be recorded.
337-
var numLargerSizes = 0
338-
var j = firstAccurateIdx
339-
while (j < totalNumBlocks) {
340-
if (sizes(j) > skewCutoff) numLargerSizes += 1
341-
j += 1
342-
}
343-
numTiedSkewedBlocksToRecord = maxAccurateSkewedBlockNumber - numLargerSizes
344358
val skewSizeThreshold =
345359
Math.max(medianSize * accurateBlockSkewedFactor, skewCutoff.toDouble)
346360
val skewThreshold = Math.min(shuffleAccurateBlockThreshold.toDouble, skewSizeThreshold)
347-
// Every map task of a shuffle sees the same block size distribution, so always recording
348-
// the lowest tied reduce ids would hide the reducers that lose the tie behind `avgSize` in
349-
// every map status, and MapOutputTracker sums those. Rotating the recorded window with the
350-
// map task id spreads the loss over all of the tied reducers instead. This costs one more
351-
// pass over the sizes, so it is only paid when blocks tied at the cutoff can be recorded
352-
// at all, which is not the case when the blocks above the cutoff already fill the budget
353-
// or when the skew threshold is above the cutoff.
354-
if (numTiedSkewedBlocksToRecord > 0 && skewThreshold <= skewCutoff.toDouble) {
355-
j = 0
356-
while (j < totalNumBlocks) {
357-
if (sizes(j) == skewCutoff && sizes(j) > 0) numTiedSkewedBlocks += 1
358-
j += 1
359-
}
360-
if (numTiedSkewedBlocks > 0) {
361-
tieRotationStart = Math.floorMod(mapTaskId, numTiedSkewedBlocks.toLong).toInt
362-
}
363-
}
361+
// Every map task of a shuffle sees the same block size distribution, so any rule that
362+
// records only some of the blocks tied at the cutoff hides the same reducers in every map
363+
// status, and MapOutputTracker sums those. The hidden ones fall back to `avgSize`, which
364+
// they raise in the process, so AQE's skew threshold moves up along with the sizes it is
365+
// compared against. Recording all of the ties is what keeps them visible.
366+
recordSkewedTies = skewCutoff > 0 && skewThreshold <= skewCutoff.toDouble
364367
skewThreshold
365368
} else {
366369
// Disable skew detection if accurateBlockSkewedFactor <= 0
@@ -369,31 +372,22 @@ private[spark] object HighlyCompressedMapStatus {
369372

370373
val hugeBlockIds = mutable.ArrayBuilder.make[Int]
371374
val hugeBlockSizes = mutable.ArrayBuilder.make[Byte]
372-
var numTiedSkewedBlocksSeen = 0
375+
val skewedBlocks = new RoaringBitmap()
373376
while (i < totalNumBlocks) {
374377
val size = uncompressedSizes(i)
375378
if (size > 0) {
376379
numNonEmptyBlocks += 1
377380
// Huge blocks are not included in the calculation for average size, thus size for smaller
378-
// blocks is more accurate.
379-
var isAccurate = size >= shuffleAccurateBlockThreshold
380-
if (!isAccurate && size >= threshold) {
381-
if (size > skewCutoff) {
382-
isAccurate = true
383-
} else if (numTiedSkewedBlocks > 0) {
384-
// `size` is exactly `skewCutoff` here, since `threshold >= skewCutoff` whenever a
385-
// block below `shuffleAccurateBlockThreshold` can reach this branch. The tied blocks
386-
// that this map task records are the `numTiedSkewedBlocksToRecord` ones starting at
387-
// `tieRotationStart`, wrapping around, which keeps the map status deterministic.
388-
val rank =
389-
Math.floorMod(numTiedSkewedBlocksSeen - tieRotationStart, numTiedSkewedBlocks)
390-
isAccurate = rank < numTiedSkewedBlocksToRecord
391-
numTiedSkewedBlocksSeen += 1
392-
}
393-
}
394-
if (isAccurate) {
381+
// blocks is more accurate. Blocks tied at the cutoff are excluded from it as well: they
382+
// are recorded accurately, so folding them into the average would both lose nothing and
383+
// inflate the size reported for the blocks that really are average.
384+
val isHuge = size >= shuffleAccurateBlockThreshold ||
385+
(size >= threshold && size > skewCutoff)
386+
if (isHuge) {
395387
hugeBlockIds += i
396388
hugeBlockSizes += MapStatus.compressSize(size)
389+
} else if (recordSkewedTies && size == skewCutoff) {
390+
skewedBlocks.add(i)
397391
} else {
398392
totalSmallBlockSize += size
399393
numSmallBlocks += 1
@@ -410,7 +404,15 @@ private[spark] object HighlyCompressedMapStatus {
410404
}
411405
emptyBlocks.trim()
412406
emptyBlocks.runOptimize()
407+
val hasSkewedBlocks = !skewedBlocks.isEmpty
408+
if (hasSkewedBlocks) {
409+
skewedBlocks.trim()
410+
skewedBlocks.runOptimize()
411+
}
413412
new HighlyCompressedMapStatus(loc, numNonEmptyBlocks, emptyBlocks, avgSize,
414-
hugeBlockIds.result(), hugeBlockSizes.result(), mapTaskId, checksumVal)
413+
hugeBlockIds.result(), hugeBlockSizes.result(),
414+
if (hasSkewedBlocks) skewedBlocks else noSkewedBlocks,
415+
if (hasSkewedBlocks) MapStatus.compressSize(skewCutoff) else 0.toByte,
416+
mapTaskId, checksumVal)
415417
}
416418
}

0 commit comments

Comments
 (0)