1818package org .apache .spark .scheduler
1919
2020import java .io .{Externalizable , ObjectInput , ObjectOutput }
21+ import java .util .Arrays
2122
2223import scala .collection .mutable
2324
@@ -187,7 +188,9 @@ private[spark] class CompressedMapStatus(
187188 * @param numNonEmptyBlocks the number of non-empty blocks
188189 * @param emptyBlocks a bitmap tracking which blocks are empty
189190 * @param avgSize average size of the non-empty and non-huge blocks
190- * @param hugeBlockSizes sizes of huge blocks by their reduceId.
191+ * @param hugeBlockIds reduceIds of the accurately recorded blocks, in increasing order
192+ * @param hugeBlockSizes compressed sizes of the accurately recorded blocks, aligned with
193+ * hugeBlockIds
191194 * @param _mapTaskId unique task id for the task
192195 * @param _checksumVal checksum value for the task
193196 */
@@ -196,17 +199,22 @@ private[spark] class HighlyCompressedMapStatus private (
196199 private [this ] var numNonEmptyBlocks : Int ,
197200 private [this ] var emptyBlocks : RoaringBitmap ,
198201 private [this ] var avgSize : Long ,
199- private [this ] var hugeBlockSizes : scala.collection.Map [Int , Byte ],
202+ // The driver retains one map status per map task for the lifetime of the shuffle, so the
203+ // accurate sizes are held as two parallel primitive arrays rather than as a boxed
204+ // Map[Int, Byte], whose nodes, bucket array and boxed keys cost an order of magnitude more
205+ // heap per entry.
206+ private [this ] var hugeBlockIds : Array [Int ],
207+ private [this ] var hugeBlockSizes : Array [Byte ],
200208 private [this ] var _mapTaskId : Long ,
201209 private [this ] var _checksumVal : Long = 0 )
202210 extends MapStatus with Externalizable {
203211
204212 // loc could be null when the default constructor is called during deserialization
205- require(loc == null || avgSize > 0 || hugeBlockSizes.size > 0
213+ require(loc == null || avgSize > 0 || hugeBlockIds.length > 0
206214 || numNonEmptyBlocks == 0 || _mapTaskId > 0 ,
207215 " Average size can only be zero for map stages that produced no output" )
208216
209- protected def this () = this (null , - 1 , null , - 1 , null , - 1 , 0 ) // For deserialization only
217+ protected def this () = this (null , - 1 , null , - 1 , null , null , - 1 , 0 ) // For deserialization only
210218
211219 override def location : BlockManagerId = loc
212220
@@ -215,14 +223,12 @@ private[spark] class HighlyCompressedMapStatus private (
215223 }
216224
217225 override def getSizeForBlock (reduceId : Int ): Long = {
218- assert(hugeBlockSizes != null )
226+ assert(hugeBlockIds != null )
219227 if (emptyBlocks.contains(reduceId)) {
220228 0
221229 } else {
222- hugeBlockSizes.get(reduceId) match {
223- case Some (size) => MapStatus .decompressSize(size)
224- case None => avgSize
225- }
230+ val i = Arrays .binarySearch(hugeBlockIds, reduceId)
231+ if (i >= 0 ) MapStatus .decompressSize(hugeBlockSizes(i)) else avgSize
226232 }
227233 }
228234
@@ -234,10 +240,12 @@ private[spark] class HighlyCompressedMapStatus private (
234240 loc.writeExternal(out)
235241 emptyBlocks.serialize(out)
236242 out.writeLong(avgSize)
237- out.writeInt(hugeBlockSizes.size)
238- hugeBlockSizes.foreach { kv =>
239- out.writeInt(kv._1)
240- out.writeByte(kv._2)
243+ out.writeInt(hugeBlockIds.length)
244+ var i = 0
245+ while (i < hugeBlockIds.length) {
246+ out.writeInt(hugeBlockIds(i))
247+ out.writeByte(hugeBlockSizes(i))
248+ i += 1
241249 }
242250 out.writeLong(_mapTaskId)
243251 out.writeLong(_checksumVal)
@@ -250,13 +258,28 @@ private[spark] class HighlyCompressedMapStatus private (
250258 emptyBlocks.deserialize(in)
251259 avgSize = in.readLong()
252260 val count = in.readInt()
253- val hugeBlockSizesImpl = mutable.Map .empty[Int , Byte ]
254- (0 until count).foreach { _ =>
255- val block = in.readInt()
256- val size = in.readByte()
257- hugeBlockSizesImpl(block) = size
261+ val blockIds = new Array [Int ](count)
262+ val blockSizes = new Array [Byte ](count)
263+ var isSorted = true
264+ var i = 0
265+ while (i < count) {
266+ blockIds(i) = in.readInt()
267+ blockSizes(i) = in.readByte()
268+ if (i > 0 && blockIds(i) <= blockIds(i - 1 )) {
269+ isSorted = false
270+ }
271+ i += 1
272+ }
273+ if (isSorted) {
274+ hugeBlockIds = blockIds
275+ hugeBlockSizes = blockSizes
276+ } else {
277+ // writeExternal emits the entries in increasing reduceId order, but a status written by an
278+ // older version may be in any order, and getSizeForBlock binary searches the ids.
279+ val order = (0 until count).sortBy(blockIds).toArray
280+ hugeBlockIds = order.map(blockIds)
281+ hugeBlockSizes = order.map(blockSizes)
258282 }
259- hugeBlockSizes = hugeBlockSizesImpl
260283 _mapTaskId = in.readLong()
261284 _checksumVal = in.readLong()
262285 }
@@ -290,7 +313,9 @@ private[spark] object HighlyCompressedMapStatus {
290313 // only recorded while `numTiedSkewedBlocksToRecord` lasts, because there can be arbitrarily
291314 // many of them and recording them all would blow past SHUFFLE_MAX_ACCURATE_SKEWED_BLOCK_NUMBER.
292315 var skewCutoff = Long .MaxValue
316+ var numTiedSkewedBlocks = 0
293317 var numTiedSkewedBlocksToRecord = 0
318+ var tieRotationStart = 0
294319 val threshold =
295320 if (accurateBlockSkewedFactor > 0 ) {
296321 val maxAccurateSkewedBlockNumber =
@@ -318,13 +343,33 @@ private[spark] object HighlyCompressedMapStatus {
318343 numTiedSkewedBlocksToRecord = maxAccurateSkewedBlockNumber - numLargerSizes
319344 val skewSizeThreshold =
320345 Math .max(medianSize * accurateBlockSkewedFactor, skewCutoff.toDouble)
321- Math .min(shuffleAccurateBlockThreshold.toDouble, skewSizeThreshold)
346+ 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+ }
364+ skewThreshold
322365 } else {
323366 // Disable skew detection if accurateBlockSkewedFactor <= 0
324367 shuffleAccurateBlockThreshold.toDouble
325368 }
326369
327- val hugeBlockSizes = mutable.Map .empty[Int , Byte ]
370+ val hugeBlockIds = mutable.ArrayBuilder .make[Int ]
371+ val hugeBlockSizes = mutable.ArrayBuilder .make[Byte ]
372+ var numTiedSkewedBlocksSeen = 0
328373 while (i < totalNumBlocks) {
329374 val size = uncompressedSizes(i)
330375 if (size > 0 ) {
@@ -335,14 +380,20 @@ private[spark] object HighlyCompressedMapStatus {
335380 if (! isAccurate && size >= threshold) {
336381 if (size > skewCutoff) {
337382 isAccurate = true
338- } else if (numTiedSkewedBlocksToRecord > 0 ) {
339- // Ties are broken by block index so that the map status stays deterministic.
340- numTiedSkewedBlocksToRecord -= 1
341- 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
342392 }
343393 }
344394 if (isAccurate) {
345- hugeBlockSizes(i) = MapStatus .compressSize(size)
395+ hugeBlockIds += i
396+ hugeBlockSizes += MapStatus .compressSize(size)
346397 } else {
347398 totalSmallBlockSize += size
348399 numSmallBlocks += 1
@@ -360,6 +411,6 @@ private[spark] object HighlyCompressedMapStatus {
360411 emptyBlocks.trim()
361412 emptyBlocks.runOptimize()
362413 new HighlyCompressedMapStatus (loc, numNonEmptyBlocks, emptyBlocks, avgSize,
363- hugeBlockSizes, mapTaskId, checksumVal)
414+ hugeBlockIds.result(), hugeBlockSizes.result() , mapTaskId, checksumVal)
364415 }
365416}
0 commit comments