@@ -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
288308private [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