You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@fluss.apache.org by ya...@apache.org on 2026/10/21 02:32:11 UTC
(fluss) branch main updated: [kv] Bound prefix lookups with an exclusive upper limit (#4744)
This is an automated email from the ASF dual-hosted git repository.
platinumhamburg pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/fluss.git
The following commit(s) were added to refs/heads/main by this push:
new 233092a88 [kv] Bound prefix lookups with an exclusive upper limit (#4744)
233092a88 is described below
commit 233092a884eefefc6e45229a5c92df63d17355f0
Author: Yang Wang <oc...@alibaba-inc.com>
AuthorDate: Wed Oct 21 10:32:05 2026 +0800
[kv] Bound prefix lookups with an exclusive upper limit (#4744)
* [kv] Bound prefix lookups with an exclusive upper limit
* [kv] Remove unused byte prefix comparison
---
.../java/org/apache/fluss/utils/BytesUtils.java | 99 -------------------
.../apache/fluss/server/kv/rocksdb/RocksDBKv.java | 40 +++++---
.../fluss/server/kv/rocksdb/RocksDBKvTest.java | 110 +++++++++++++++++++++
3 files changed, 139 insertions(+), 110 deletions(-)
diff --git a/fluss-common/src/main/java/org/apache/fluss/utils/BytesUtils.java b/fluss-common/src/main/java/org/apache/fluss/utils/BytesUtils.java
index 63ce0ec0c..e39d9a633 100644
--- a/fluss-common/src/main/java/org/apache/fluss/utils/BytesUtils.java
+++ b/fluss-common/src/main/java/org/apache/fluss/utils/BytesUtils.java
@@ -18,11 +18,8 @@
package org.apache.fluss.utils;
import org.apache.fluss.annotation.Internal;
-import org.apache.fluss.utils.crc.Java;
-import java.lang.reflect.Method;
import java.nio.ByteBuffer;
-import java.util.Arrays;
/** Utils for bytes. */
@Internal
@@ -62,100 +59,4 @@ public final class BytesUtils {
}
return dest;
}
-
- /**
- * Check if the given first byte array ({@code prefix}) is a prefix of the second byte array
- * ({@code bytes}).
- *
- * @param prefix the prefix byte array
- * @param bytes the byte array to check if it has the prefix
- * @return true if the given bytes has the given prefix, false otherwise.
- */
- public static boolean prefixEquals(byte[] prefix, byte[] bytes) {
- return BEST_EQUAL_COMPARER.prefixEquals(prefix, bytes);
- }
-
- // -------------------------------------------------------------------------------------------
-
- private static final BytesPrefixComparer BEST_EQUAL_COMPARER;
-
- static {
- if (Java.IS_JAVA9_COMPATIBLE) {
- BEST_EQUAL_COMPARER = new Java9BytesPrefixComparer();
- } else {
- BEST_EQUAL_COMPARER = new PureJavaBytesPrefixComparer();
- }
- }
-
- /** Compare two byte arrays for equality. */
- private interface BytesPrefixComparer {
-
- /**
- * Check if the given first byte array ({@code prefix}) is a prefix of the second byte array
- * ({@code bytes}).
- *
- * @param prefix The prefix byte array
- * @param bytes The byte array to check if it has the prefix
- * @return true if the given bytes has the given prefix, false otherwise
- */
- boolean prefixEquals(byte[] prefix, byte[] bytes);
- }
-
- private static final class Java9BytesPrefixComparer implements BytesPrefixComparer {
- private static final Method EQUALS_METHOD;
-
- static {
- try {
- EQUALS_METHOD =
- Class.forName(Arrays.class.getName())
- .getMethod(
- "equals",
- byte[].class,
- int.class,
- int.class,
- byte[].class,
- int.class,
- int.class);
- } catch (Exception e) {
- throw new RuntimeException("Failed to load Arrays.equals method", e);
- }
- }
-
- @Override
- public boolean prefixEquals(byte[] prefix, byte[] bytes) {
- if (prefix.length > bytes.length) {
- return false;
- }
- try {
- int fromIndex = 0; // inclusive
- int toIndex = prefix.length; // exclusive
- return (boolean)
- EQUALS_METHOD.invoke(
- null, prefix, fromIndex, toIndex, bytes, fromIndex, toIndex);
- } catch (Throwable e) {
- // should never happen
- throw new RuntimeException(e);
- }
- }
- }
-
- /**
- * A pure Java implementation of the {@link BytesPrefixComparer} that does not rely on Java 9
- * APIs and compares bytes one by one which is slower.
- */
- private static final class PureJavaBytesPrefixComparer implements BytesPrefixComparer {
-
- @Override
- public boolean prefixEquals(byte[] prefix, byte[] bytes) {
- if (prefix.length > bytes.length) {
- return false;
- }
- for (int i = 0; i < prefix.length; i++) {
- if (prefix[i] != bytes[i]) {
- return false;
- }
- }
- return true;
- }
- }
}
diff --git a/fluss-server/src/main/java/org/apache/fluss/server/kv/rocksdb/RocksDBKv.java b/fluss-server/src/main/java/org/apache/fluss/server/kv/rocksdb/RocksDBKv.java
index 106daf57b..9fbac8541 100644
--- a/fluss-server/src/main/java/org/apache/fluss/server/kv/rocksdb/RocksDBKv.java
+++ b/fluss-server/src/main/java/org/apache/fluss/server/kv/rocksdb/RocksDBKv.java
@@ -24,7 +24,6 @@ import org.apache.fluss.metrics.Histogram;
import org.apache.fluss.rocksdb.RocksDBOperationUtils;
import org.apache.fluss.server.kv.KvCloseMode;
import org.apache.fluss.server.utils.ResourceGuard;
-import org.apache.fluss.utils.BytesUtils;
import org.apache.fluss.utils.IOUtils;
import io.github.fluss_contrib.rocksdb.Cache;
@@ -35,6 +34,7 @@ import io.github.fluss_contrib.rocksdb.ReadOptions;
import io.github.fluss_contrib.rocksdb.RocksDB;
import io.github.fluss_contrib.rocksdb.RocksDBException;
import io.github.fluss_contrib.rocksdb.RocksIterator;
+import io.github.fluss_contrib.rocksdb.Slice;
import io.github.fluss_contrib.rocksdb.Statistics;
import io.github.fluss_contrib.rocksdb.WriteOptions;
import org.slf4j.Logger;
@@ -44,6 +44,7 @@ import javax.annotation.Nullable;
import java.io.IOException;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.List;
import java.util.Objects;
import java.util.concurrent.TimeUnit;
@@ -211,17 +212,20 @@ public class RocksDBKv implements AutoCloseable {
public List<byte[]> prefixLookup(byte[] prefixKey) {
List<byte[]> pkList = new ArrayList<>();
- ReadOptions readOptions = new ReadOptions();
- RocksIterator iterator = db.newIterator(defaultColumnFamilyHandle, readOptions);
- try {
- iterator.seek(prefixKey);
- while (iterator.isValid() && BytesUtils.prefixEquals(prefixKey, iterator.key())) {
- pkList.add(iterator.value());
- iterator.next();
+ byte[] upperBound = prefixUpperBound(prefixKey);
+ // The bound must outlive both the read options and the iterator that reference it.
+ try (Slice upperBoundSlice = upperBound == null ? null : new Slice(upperBound);
+ ReadOptions readOptions = new ReadOptions().setTotalOrderSeek(true)) {
+ if (upperBoundSlice != null) {
+ readOptions.setIterateUpperBound(upperBoundSlice);
+ }
+ try (RocksIterator iterator = db.newIterator(defaultColumnFamilyHandle, readOptions)) {
+ iterator.seek(prefixKey);
+ while (iterator.isValid()) {
+ pkList.add(iterator.value());
+ iterator.next();
+ }
}
- } finally {
- readOptions.close();
- iterator.close();
}
return pkList;
@@ -482,4 +486,18 @@ public class RocksDBKv implements AutoCloseable {
long offset = Math.min(l0Files - flussL0SlowdownTrigger, (long) window - 1);
return (float) offset / window;
}
+
+ /** Returns the exclusive bytewise bound, or null if the prefix has no finite upper bound. */
+ @Nullable
+ private static byte[] prefixUpperBound(byte[] prefix) {
+ for (int i = prefix.length - 1; i >= 0; i--) {
+ if ((prefix[i] & 0xff) != 0xff) {
+ byte[] upperBound = Arrays.copyOf(prefix, i + 1);
+ upperBound[i]++;
+ return upperBound;
+ }
+ }
+ // Empty and all-0xff prefixes match every key at or after the seek position.
+ return null;
+ }
}
diff --git a/fluss-server/src/test/java/org/apache/fluss/server/kv/rocksdb/RocksDBKvTest.java b/fluss-server/src/test/java/org/apache/fluss/server/kv/rocksdb/RocksDBKvTest.java
index a0035d557..a82ea1f65 100644
--- a/fluss-server/src/test/java/org/apache/fluss/server/kv/rocksdb/RocksDBKvTest.java
+++ b/fluss-server/src/test/java/org/apache/fluss/server/kv/rocksdb/RocksDBKvTest.java
@@ -21,13 +21,20 @@ import org.apache.fluss.config.Configuration;
import org.apache.fluss.exception.FlussRuntimeException;
import org.apache.fluss.metrics.SimpleCounter;
import org.apache.fluss.metrics.util.TestHistogram;
+import org.apache.fluss.row.BinaryString;
+import org.apache.fluss.row.GenericRow;
+import org.apache.fluss.row.encode.CompactedKeyEncoder;
import org.apache.fluss.server.kv.KvCloseMode;
+import org.apache.fluss.types.DataTypes;
+import org.apache.fluss.types.RowType;
import io.github.fluss_contrib.rocksdb.ColumnFamilyOptions;
import io.github.fluss_contrib.rocksdb.FlushOptions;
import io.github.fluss_contrib.rocksdb.RocksDBException;
import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.io.TempDir;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.ValueSource;
import java.io.File;
import java.nio.file.Path;
@@ -68,6 +75,109 @@ class RocksDBKvTest {
}
}
+ @ParameterizedTest
+ @ValueSource(booleans = {false, true})
+ void testPrefixLookupByteBoundaries(boolean flush, @TempDir Path tempDir) throws Exception {
+ // Already in unsigned bytewise order, including exact prefixes and their upper bounds.
+ byte[][] keys = {
+ {},
+ {0},
+ {0, 0},
+ {0, (byte) 0xff},
+ {1},
+ {1, 0},
+ {1, (byte) 0xfe},
+ {1, (byte) 0xff},
+ {1, (byte) 0xff, 0},
+ {1, (byte) 0xff, (byte) 0xff},
+ {2},
+ {0x7f},
+ {0x7f, (byte) 0xff},
+ {(byte) 0x80},
+ {(byte) 0x80, 0},
+ {(byte) 0xfe},
+ {(byte) 0xff},
+ {(byte) 0xff, 0},
+ {(byte) 0xff, (byte) 0xff},
+ {(byte) 0xff, (byte) 0xff, (byte) 0xff}
+ };
+ byte[][] prefixes = {
+ {},
+ {0},
+ {0, (byte) 0xff},
+ {1},
+ {1, (byte) 0xff},
+ {1, (byte) 0xff, (byte) 0xff},
+ {1, (byte) 0xff, (byte) 0xff, 0},
+ {2},
+ {3},
+ {0x7f},
+ {0x7f, (byte) 0xff},
+ {(byte) 0x80},
+ {(byte) 0xff},
+ {(byte) 0xff, (byte) 0xff},
+ {(byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff}
+ };
+ try (RocksDBKv kv = buildRocksDBKv(tempDir.toFile())) {
+ for (byte[] key : keys) {
+ kv.put(key, key);
+ }
+ if (flush) {
+ try (FlushOptions options = new FlushOptions().setWaitForFlush(true)) {
+ kv.db.flush(options);
+ }
+ }
+ for (byte[] prefix : prefixes) {
+ byte[][] expected =
+ Arrays.stream(keys)
+ .filter(
+ key ->
+ key.length >= prefix.length
+ && Arrays.equals(
+ Arrays.copyOf(key, prefix.length),
+ prefix))
+ .toArray(byte[][]::new);
+ assertThat(kv.prefixLookup(prefix))
+ .as("prefix %s (flushed=%s)", Arrays.toString(prefix), flush)
+ .containsExactly(expected);
+ }
+ }
+ }
+
+ @Test
+ void testPrefixLookupWithEncodedKeysAndMixedSstAndMemtable(@TempDir Path tempDir)
+ throws Exception {
+ RowType keyType = RowType.of(DataTypes.STRING(), DataTypes.INT());
+ CompactedKeyEncoder keyEncoder = new CompactedKeyEncoder(keyType);
+ CompactedKeyEncoder prefixEncoder = new CompactedKeyEncoder(keyType, new int[] {0});
+ byte[] prefix = prefixEncoder.encodeKey(GenericRow.of(BinaryString.fromString("ab"), 0));
+ byte[] key1 = keyEncoder.encodeKey(GenericRow.of(BinaryString.fromString("ab"), 1));
+ byte[] key2 = keyEncoder.encodeKey(GenericRow.of(BinaryString.fromString("ab"), 2));
+ byte[] key3 = keyEncoder.encodeKey(GenericRow.of(BinaryString.fromString("ab"), 3));
+ byte[] key4 = keyEncoder.encodeKey(GenericRow.of(BinaryString.fromString("ab"), 4));
+ byte[] other = keyEncoder.encodeKey(GenericRow.of(BinaryString.fromString("ac"), 1));
+ try (RocksDBKv kv = buildRocksDBKv(tempDir.toFile())) {
+ kv.put(key1, new byte[] {1});
+ kv.put(key2, new byte[] {2});
+ kv.put(key3, new byte[] {3});
+ kv.put(other, new byte[] {9});
+ try (FlushOptions options = new FlushOptions().setWaitForFlush(true)) {
+ kv.db.flush(options);
+ kv.put(key1, new byte[] {5});
+ kv.delete(key2);
+ kv.put(key4, new byte[] {4});
+ assertThat(kv.prefixLookup(prefix))
+ .containsExactly(new byte[] {5}, new byte[] {3}, new byte[] {4});
+ kv.db.flush(options);
+ assertThat(kv.prefixLookup(prefix))
+ .containsExactly(new byte[] {5}, new byte[] {3}, new byte[] {4});
+ kv.db.compactRange();
+ assertThat(kv.prefixLookup(prefix))
+ .containsExactly(new byte[] {5}, new byte[] {3}, new byte[] {4});
+ }
+ }
+ }
+
@Test
void testLiveSstFilesSize(@TempDir Path tempDir) throws Exception {
try (RocksDBKv rocksDBKv = buildRocksDBKv(tempDir.toFile())) {