Skip to content

Commit d3be2ba

Browse files
committed
[SPARK-48290][CORE][FOLLOWUP] Rotate cutoff ties per map task and store the accurate sizes compactly
Every map task of a shuffle sees the same block size distribution, so breaking the ties at the skew cutoff by block index recorded the same reduce ids in every map status, and a reducer that lost the tie was represented by avgSize in all of them. MapOutputTracker sums those, so a genuinely skewed reducer could stay invisible to adaptive query execution. The window of tied blocks a map task records now rotates with its map task id, so a tied reducer loses on one map task out of the number of tied blocks rather than on all of them. The map status stays deterministic, avgSize is unchanged, and the per map task cap still holds. Counting the tied blocks costs one more pass over the sizes, so it is only paid when a tied block can be recorded at all. HighlyCompressedMapStatus held the accurate sizes in a mutable.Map[Int, Byte], one of which the driver retains per map task for the lifetime of the shuffle. They are now two parallel primitive arrays sorted by reduce id, which getSizeForBlock binary searches. Measured on a MapOutputTrackerMaster holding a 10000 map task stage of 2001 reducers with 101 blocks tied at the cutoff, the retained map statuses go from 6004 to 668 bytes per map task, or from 57 MiB to 6 MiB for the stage. Reading a block size also gets cheaper, from 6.5 to 3.9 nanoseconds at 50000 partitions, since the reduce id is no longer boxed on every lookup. The benchmark reports both, alongside the build cost.
1 parent db74b8e commit d3be2ba

4 files changed

Lines changed: 328 additions & 50 deletions

File tree

‎core/benchmarks/HighlyCompressedMapStatusBenchmark-jdk21-results.txt‎

Lines changed: 39 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -6,22 +6,22 @@ OpenJDK 64-Bit Server VM 21.0.10 on Mac OS X 26.5.2
66
Apple M4
77
2048 shuffle partitions: Best Time(ms) Avg Time(ms) Stdev(ms) Rate(M/s) Per Row(ns) Relative
88
------------------------------------------------------------------------------------------------------------------------
9-
skewed block sizes not recorded 0 0 0 0.2 6458.0 1.0X
10-
skewed block sizes recorded accurately 0 0 0 0.1 17250.0 0.4X
9+
skewed block sizes not recorded 0 0 0 0.1 7166.0 1.0X
10+
skewed block sizes recorded accurately 0 0 0 0.1 18042.0 0.4X
1111

1212
OpenJDK 64-Bit Server VM 21.0.10 on Mac OS X 26.5.2
1313
Apple M4
1414
10000 shuffle partitions: Best Time(ms) Avg Time(ms) Stdev(ms) Rate(M/s) Per Row(ns) Relative
1515
------------------------------------------------------------------------------------------------------------------------
16-
skewed block sizes not recorded 0 0 0 0.1 13834.0 1.0X
17-
skewed block sizes recorded accurately 0 0 0 0.0 56250.0 0.2X
16+
skewed block sizes not recorded 0 0 0 0.1 14792.0 1.0X
17+
skewed block sizes recorded accurately 0 0 0 0.0 55917.0 0.3X
1818

1919
OpenJDK 64-Bit Server VM 21.0.10 on Mac OS X 26.5.2
2020
Apple M4
2121
50000 shuffle partitions: Best Time(ms) Avg Time(ms) Stdev(ms) Rate(M/s) Per Row(ns) Relative
2222
------------------------------------------------------------------------------------------------------------------------
23-
skewed block sizes not recorded 0 0 0 0.0 35959.0 1.0X
24-
skewed block sizes recorded accurately 0 0 0 0.0 309750.0 0.1X
23+
skewed block sizes not recorded 0 0 0 0.0 53250.0 1.0X
24+
skewed block sizes recorded accurately 0 0 0 0.0 375959.0 0.1X
2525

2626

2727
================================================================================================
@@ -32,21 +32,48 @@ OpenJDK 64-Bit Server VM 21.0.10 on Mac OS X 26.5.2
3232
Apple M4
3333
2048 shuffle partitions: Best Time(ms) Avg Time(ms) Stdev(ms) Rate(M/s) Per Row(ns) Relative
3434
------------------------------------------------------------------------------------------------------------------------
35-
skewed block sizes not recorded 0 0 0 0.2 6416.0 1.0X
36-
skewed block sizes recorded accurately 0 0 0 0.0 23583.0 0.3X
35+
skewed block sizes not recorded 0 0 0 0.1 7375.0 1.0X
36+
skewed block sizes recorded accurately 0 0 0 0.0 25209.0 0.3X
3737

3838
OpenJDK 64-Bit Server VM 21.0.10 on Mac OS X 26.5.2
3939
Apple M4
4040
10000 shuffle partitions: Best Time(ms) Avg Time(ms) Stdev(ms) Rate(M/s) Per Row(ns) Relative
4141
------------------------------------------------------------------------------------------------------------------------
42-
skewed block sizes not recorded 0 0 0 0.1 14666.0 1.0X
43-
skewed block sizes recorded accurately 0 0 0 0.0 99458.0 0.1X
42+
skewed block sizes not recorded 0 0 0 0.0 20166.0 1.0X
43+
skewed block sizes recorded accurately 0 0 0 0.0 105375.0 0.2X
4444

4545
OpenJDK 64-Bit Server VM 21.0.10 on Mac OS X 26.5.2
4646
Apple M4
4747
50000 shuffle partitions: Best Time(ms) Avg Time(ms) Stdev(ms) Rate(M/s) Per Row(ns) Relative
4848
------------------------------------------------------------------------------------------------------------------------
49-
skewed block sizes not recorded 0 0 0 0.0 54583.0 1.0X
50-
skewed block sizes recorded accurately 1 1 0 0.0 530209.0 0.1X
49+
skewed block sizes not recorded 0 0 0 0.0 85708.0 1.0X
50+
skewed block sizes recorded accurately 1 1 0 0.0 579709.0 0.1X
51+
52+
53+
================================================================================================
54+
Read block sizes out of HighlyCompressedMapStatus
55+
================================================================================================
56+
57+
OpenJDK 64-Bit Server VM 21.0.10 on Mac OS X 26.5.2
58+
Apple M4
59+
2048 shuffle partitions: Best Time(ms) Avg Time(ms) Stdev(ms) Rate(M/s) Per Row(ns) Relative
60+
--------------------------------------------------------------------------------------------------------------------------
61+
sum every block size over the map statuses 1 1 0 210.7 4.7 1.0X
62+
63+
OpenJDK 64-Bit Server VM 21.0.10 on Mac OS X 26.5.2
64+
Apple M4
65+
50000 shuffle partitions: Best Time(ms) Avg Time(ms) Stdev(ms) Rate(M/s) Per Row(ns) Relative
66+
--------------------------------------------------------------------------------------------------------------------------
67+
sum every block size over the map statuses 19 20 0 256.5 3.9 1.0X
68+
69+
70+
================================================================================================
71+
Driver heap retained by MapOutputTracker
72+
================================================================================================
73+
74+
2001 partitions, 10000 map tasks retained MiB bytes per task serialized KiB
75+
------------------------------------------------------------------------------------------
76+
skewed block sizes not recorded 1 164 13
77+
skewed block sizes recorded accurately 6 668 27
5178

5279

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

Lines changed: 78 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,7 @@
1818
package org.apache.spark.scheduler
1919

2020
import java.io.{Externalizable, ObjectInput, ObjectOutput}
21+
import java.util.Arrays
2122

2223
import 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

Comments
 (0)