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())) {