This is an automated email from the ASF dual-hosted git repository.
LuciferYang pushed a commit to branch branch-4.0
in repository https://gitbox.apache.org/repos/asf/spark.git
The following commit(s) were added to refs/heads/branch-4.0 by this push:
new df84b51480ab [SPARK-57662][CORE] Use unsigned byte comparison for
KVStore iterator keys
df84b51480ab is described below
commit df84b51480abc5e06ff9908c6b7368fc956f2225
Author: YangJie <[email protected]>
AuthorDate: Thu Jun 25 14:43:09 2026 +0800
[SPARK-57662][CORE] Use unsigned byte comparison for KVStore iterator keys
### What changes were proposed in this pull request?
`LevelDBIterator` and `RocksDBIterator` each have a static `compare(byte[],
byte[])` used to order keys during iteration, and it compared bytes with `a[i]
- b[i]`. That had two problems. The `diff += ...` accumulation was dead: the
loop returns on the first non-zero byte, so it was really just `=`. More
importantly, the signed byte subtraction disagrees with how LevelDB and RocksDB
order keys, which is unsigned bytewise (their default comparators use
`memcmp`). For any key byte `>= 0x [...]
### Why are the changes needed?
The comparator should agree with the ordering the underlying store uses.
With signed bytes it did not, so for non-ASCII keys the iterator could compare
a key against its bounds incorrectly. ASCII keys are unaffected, which is why
this never surfaced in practice, but the comparator was still wrong. The method
is called at four iterator sites that use only the sign and two type-info sites
that use `!= 0`, all of which stay correct under the change.
### Does this PR introduce _any_ user-facing change?
No. It only corrects key ordering that was previously wrong, and only for
keys containing bytes `>= 0x80`.
### How was this patch tested?
Added `DBIteratorCompareSuite`, which calls both static comparators
directly (no database, so it runs on every platform) and checks equal arrays,
prefix and length ordering, and the unsigned cases such as `0x80 > 0x7f` and
`0xff > 0x00`. Reverting either method to `Arrays.compare` (the signed variant)
fails the suite, so it is a real regression guard. The full kvstore test suite
passes locally, with the LevelDB suites skipped on Apple Silicon and covered by
CI, and checkstyle reports [...]
### Was this patch authored or co-authored using generative AI tooling?
No
Closes #56740 from LuciferYang/SPARK-kvstore-iterator-compare.
Authored-by: YangJie <[email protected]>
Signed-off-by: yangjie01 <[email protected]>
(cherry picked from commit e19d4e65f0b8f4cf462cd0ce271a0289d18cd0aa)
Signed-off-by: yangjie01 <[email protected]>
---
.../apache/spark/util/kvstore/LevelDBIterator.java | 14 ++---
.../apache/spark/util/kvstore/RocksDBIterator.java | 13 +---
.../spark/util/kvstore/DBIteratorCompareSuite.java | 72 ++++++++++++++++++++++
3 files changed, 79 insertions(+), 20 deletions(-)
diff --git
a/common/kvstore/src/main/java/org/apache/spark/util/kvstore/LevelDBIterator.java
b/common/kvstore/src/main/java/org/apache/spark/util/kvstore/LevelDBIterator.java
index 29ed37ffa44e..bdfd75d6d199 100644
---
a/common/kvstore/src/main/java/org/apache/spark/util/kvstore/LevelDBIterator.java
+++
b/common/kvstore/src/main/java/org/apache/spark/util/kvstore/LevelDBIterator.java
@@ -20,6 +20,7 @@ package org.apache.spark.util.kvstore;
import java.io.IOException;
import java.lang.ref.Cleaner;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
@@ -290,17 +291,10 @@ class LevelDBIterator<T> implements KVStoreIterator<T> {
key[key.length - 1] == LevelDBTypeInfo.END_MARKER[0]);
}
+ @VisibleForTesting
static int compare(byte[] a, byte[] b) {
- int diff = 0;
- int minLen = Math.min(a.length, b.length);
- for (int i = 0; i < minLen; i++) {
- diff += (a[i] - b[i]);
- if (diff != 0) {
- return diff;
- }
- }
-
- return a.length - b.length;
+ // Unsigned bytewise comparison, matching LevelDB's key ordering.
+ return Arrays.compareUnsigned(a, b);
}
static class ResourceCleaner implements Runnable {
diff --git
a/common/kvstore/src/main/java/org/apache/spark/util/kvstore/RocksDBIterator.java
b/common/kvstore/src/main/java/org/apache/spark/util/kvstore/RocksDBIterator.java
index e350ddc2d445..a60f537c4cd4 100644
---
a/common/kvstore/src/main/java/org/apache/spark/util/kvstore/RocksDBIterator.java
+++
b/common/kvstore/src/main/java/org/apache/spark/util/kvstore/RocksDBIterator.java
@@ -278,17 +278,10 @@ class RocksDBIterator<T> implements KVStoreIterator<T> {
key[key.length - 1] == RocksDBTypeInfo.END_MARKER[0]);
}
+ @VisibleForTesting
static int compare(byte[] a, byte[] b) {
- int diff = 0;
- int minLen = Math.min(a.length, b.length);
- for (int i = 0; i < minLen; i++) {
- diff += (a[i] - b[i]);
- if (diff != 0) {
- return diff;
- }
- }
-
- return a.length - b.length;
+ // Unsigned bytewise comparison, matching RocksDB's key ordering.
+ return Arrays.compareUnsigned(a, b);
}
static class ResourceCleaner implements Runnable {
diff --git
a/common/kvstore/src/test/java/org/apache/spark/util/kvstore/DBIteratorCompareSuite.java
b/common/kvstore/src/test/java/org/apache/spark/util/kvstore/DBIteratorCompareSuite.java
new file mode 100644
index 000000000000..b399d250bff2
--- /dev/null
+++
b/common/kvstore/src/test/java/org/apache/spark/util/kvstore/DBIteratorCompareSuite.java
@@ -0,0 +1,72 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.util.kvstore;
+
+import org.junit.jupiter.api.Test;
+import static org.junit.jupiter.api.Assertions.*;
+
+/**
+ * Unit tests for the static byte-array comparator that LevelDBIterator and
RocksDBIterator
+ * each define (the two backends are kept independent, so the method is
duplicated). The
+ * comparator is pure and needs no database, so these tests run on every
platform.
+ */
+public class DBIteratorCompareSuite {
+
+ @FunctionalInterface
+ private interface ByteArrayComparator {
+ int compare(byte[] a, byte[] b);
+ }
+
+ @Test
+ public void testLevelDBIteratorCompare() {
+ checkUnsignedByteOrdering(LevelDBIterator::compare);
+ }
+
+ @Test
+ public void testRocksDBIteratorCompare() {
+ checkUnsignedByteOrdering(RocksDBIterator::compare);
+ }
+
+ private static void checkUnsignedByteOrdering(ByteArrayComparator cmp) {
+ // Equal arrays compare equal.
+ assertEquals(0, cmp.compare(new byte[] { 1, 2, 3 }, new byte[] { 1, 2, 3
}));
+
+ // Empty arrays compare equal, and an empty array sorts before any
non-empty one.
+ assertEquals(0, cmp.compare(new byte[] {}, new byte[] {}));
+ assertTrue(cmp.compare(new byte[] {}, new byte[] { 1 }) < 0);
+ assertTrue(cmp.compare(new byte[] { 1 }, new byte[] {}) > 0);
+
+ // A prefix sorts before the longer array that extends it.
+ assertTrue(cmp.compare(new byte[] { 1, 2 }, new byte[] { 1, 2, 3 }) < 0);
+ assertTrue(cmp.compare(new byte[] { 1, 2, 3 }, new byte[] { 1, 2 }) > 0);
+
+ // Bytes must be ordered as unsigned, matching the underlying key
ordering: 0x80 (128) is
+ // greater than 0x7f (127). A signed comparison would wrongly treat 0x80
as -128.
+ byte[] highBit = new byte[] { (byte) 0x80 };
+ byte[] lowBit = new byte[] { 0x7f };
+ assertTrue(cmp.compare(highBit, lowBit) > 0);
+ assertTrue(cmp.compare(lowBit, highBit) < 0);
+
+ // 0xff (255) is the largest byte value when unsigned, so it sorts after
0x00.
+ assertTrue(cmp.compare(new byte[] { (byte) 0xff }, new byte[] { 0x00 }) >
0);
+
+ // The first differing byte decides the order, regardless of later bytes.
+ assertTrue(cmp.compare(new byte[] { 0x01, (byte) 0xff }, new byte[] {
0x02, 0x00 }) < 0);
+ }
+
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
