This is an automated email from the ASF dual-hosted git repository.
adoroszlai pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/ozone.git
The following commit(s) were added to refs/heads/master by this push:
new 84da9cee920 HDDS-13319. Simplify KeyPrefixFilter (#8692)
84da9cee920 is described below
commit 84da9cee92070cce3bcbce85f88a9d2d7c52ec63
Author: Tsz-Wo Nicholas Sze <[email protected]>
AuthorDate: Wed Jun 25 08:05:41 2025 -0700
HDDS-13319. Simplify KeyPrefixFilter (#8692)
---
.../hadoop/hdds/utils/MetadataKeyFilters.java | 123 +++++----------------
1 file changed, 27 insertions(+), 96 deletions(-)
diff --git
a/hadoop-hdds/framework/src/main/java/org/apache/hadoop/hdds/utils/MetadataKeyFilters.java
b/hadoop-hdds/framework/src/main/java/org/apache/hadoop/hdds/utils/MetadataKeyFilters.java
index a36b38989fd..d385a6d3c53 100644
---
a/hadoop-hdds/framework/src/main/java/org/apache/hadoop/hdds/utils/MetadataKeyFilters.java
+++
b/hadoop-hdds/framework/src/main/java/org/apache/hadoop/hdds/utils/MetadataKeyFilters.java
@@ -17,12 +17,7 @@
package org.apache.hadoop.hdds.utils;
-import com.google.common.base.Preconditions;
-import com.google.common.base.Strings;
-import java.util.ArrayList;
-import java.util.List;
import org.apache.hadoop.hdds.StringUtils;
-import org.apache.hadoop.ozone.OzoneConsts;
/**
* An utility class to filter levelDB keys.
@@ -30,12 +25,6 @@
public final class MetadataKeyFilters {
private MetadataKeyFilters() { }
- @Deprecated
- public static KeyPrefixFilter getDeletingKeyFilter() {
- return new MetadataKeyFilters.KeyPrefixFilter()
- .addFilter(OzoneConsts.DELETING_KEY_PREFIX);
- }
-
/**
* @return A {@link KeyPrefixFilter} that ignores all keys beginning with
* #. This uses the convention that key prefixes are surrounded by
@@ -43,123 +32,52 @@ public static KeyPrefixFilter getDeletingKeyFilter() {
* added in the future.
*/
public static KeyPrefixFilter getUnprefixedKeyFilter() {
- return new MetadataKeyFilters.KeyPrefixFilter()
- .addFilter("#", true);
+ return KeyPrefixFilter.newFilter("#", true);
}
/**
- * Interface for RocksDB key filters.
+ * Filter key by a byte[] prefix.
*/
- public interface MetadataKeyFilter {
- /**
- * Filter levelDB key with a certain condition.
- *
- * @param currentKey current key.
- * @return true if a certain condition satisfied, return false otherwise.
- */
- boolean filterKey(byte[] currentKey);
-
- default int getKeysScannedNum() {
- return 0;
- }
-
- default int getKeysHintedNum() {
- return 0;
- }
- }
+ public static final class KeyPrefixFilter {
+ private static final KeyPrefixFilter NULL_FILTER = new
KeyPrefixFilter(null, true);
- /**
- * Utility class to filter key by a string prefix. This filter
- * assumes keys can be parsed to a string.
- */
- public static final class KeyPrefixFilter implements MetadataKeyFilter {
- private List<String> positivePrefixList = new ArrayList<>();
- private List<String> negativePrefixList = new ArrayList<>();
+ private final byte[] prefix;
+ private final boolean isPositive;
private int keysScanned = 0;
private int keysHinted = 0;
- private KeyPrefixFilter() { }
-
- public KeyPrefixFilter addFilter(String keyPrefix) {
- addFilter(keyPrefix, false);
- return this;
+ private KeyPrefixFilter(byte[] prefix, boolean isPositive) {
+ this.prefix = prefix;
+ this.isPositive = isPositive;
}
- public KeyPrefixFilter addFilter(String keyPrefix, boolean negative) {
- Preconditions.checkArgument(!Strings.isNullOrEmpty(keyPrefix),
- "KeyPrefix is null or empty: %s", keyPrefix);
- // keyPrefix which needs to be added should not be prefix of any opposing
- // filter already present. If keyPrefix is a negative filter it should
not
- // be a prefix of any positive filter. Nor should any opposing filter be
- // a prefix of keyPrefix.
- // For example if b0 is accepted b can not be rejected and
- // if b is accepted b0 can not be rejected. If these scenarios need to be
- // handled we need to add priorities.
- if (negative) {
- Preconditions.checkArgument(positivePrefixList.stream().noneMatch(
- prefix -> prefix.startsWith(keyPrefix) || keyPrefix
- .startsWith(prefix)),
- "KeyPrefix: " + keyPrefix + " already accepted.");
- this.negativePrefixList.add(keyPrefix);
- } else {
- Preconditions.checkArgument(negativePrefixList.stream().noneMatch(
- prefix -> prefix.startsWith(keyPrefix) || keyPrefix
- .startsWith(prefix)),
- "KeyPrefix: " + keyPrefix + " already rejected.");
- this.positivePrefixList.add(keyPrefix);
- }
- return this;
- }
-
- @Override
+ /** @return true if the given should be returned. */
public boolean filterKey(byte[] currentKey) {
keysScanned++;
if (currentKey == null) {
return false;
}
- boolean accept;
-
// There are no filters present
- if (positivePrefixList.isEmpty() && negativePrefixList.isEmpty()) {
+ if (prefix == null) {
return true;
}
-
- accept = !positivePrefixList.isEmpty() && positivePrefixList.stream()
- .anyMatch(prefix -> {
- byte[] prefixBytes = StringUtils.string2Bytes(prefix);
- return prefixMatch(prefixBytes, currentKey);
- });
- if (accept) {
+ // Use == since true iff (positive && matched) || (!positive && !matched)
+ if (isPositive == prefixMatch(prefix, currentKey)) {
keysHinted++;
return true;
}
-
- accept = !negativePrefixList.isEmpty() && negativePrefixList.stream()
- .allMatch(prefix -> {
- byte[] prefixBytes = StringUtils.string2Bytes(prefix);
- return !prefixMatch(prefixBytes, currentKey);
- });
- if (accept) {
- keysHinted++;
- return true;
- }
-
return false;
}
- @Override
public int getKeysScannedNum() {
return keysScanned;
}
- @Override
public int getKeysHintedNum() {
return keysHinted;
}
private static boolean prefixMatch(byte[] prefix, byte[] key) {
- Preconditions.checkNotNull(prefix);
- Preconditions.checkNotNull(key);
if (key.length < prefix.length) {
return false;
}
@@ -171,12 +89,25 @@ private static boolean prefixMatch(byte[] prefix, byte[]
key) {
return true;
}
+ /** The same as newFilter(prefix, false). */
public static KeyPrefixFilter newFilter(String prefix) {
return newFilter(prefix, false);
}
+ /** @return a positive/negative filter for the given prefix. */
public static KeyPrefixFilter newFilter(String prefix, boolean negative) {
- return new KeyPrefixFilter().addFilter(prefix, negative);
+ if (prefix == null) {
+ if (negative) {
+ throw new IllegalArgumentException("The prefix of a negative filter
cannot be null");
+ }
+ return NULL_FILTER;
+ }
+
+ // TODO: HDDS-13329: Two exising bugs in the code:
+ // Bug 1: StringUtils.string2Bytes may silently replace
unsupported characters with '?'.
+ // Bug 2: The encoding of StringUtils.string2Bytes can be
different from the Codec of key.
+ // It should use the same Codec as the key in order to fix them.
+ return new KeyPrefixFilter(StringUtils.string2Bytes(prefix), !negative);
}
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
