You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@hbase.apache.org by "jinhyukify (via GitHub)" <gi...@apache.org> on 2026/02/11 18:15:00 UTC

[PR] HBASE-29889 Add XXH3 Hash Support to Bloom Filter [hbase]

jinhyukify opened a new pull request, #7740:
URL: https://github.com/apache/hbase/pull/7740

   **Jira** https://issues.apache.org/jira/browse/HBASE-29889
   
   This PR adds **XXH3** as a new Bloom filter hash type. XXH3 is designed for modern CPU architectures and shows clearly better performance than the existing Jenkins/Murmur/Murmur3 hashes used today.
   
   Benchmark results and brief implementation notes can be found here:
   https://docs.google.com/document/d/1LycZZMKFrrxYytEnzVj-EjQB4PbmmTgprhMOpDRPqYM/edit?tab=t.0


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@hbase.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] HBASE-29889 Add XXH3 Hash Support to Bloom Filter [hbase]

Posted by "jinhyukify (via GitHub)" <gi...@apache.org>.
jinhyukify commented on code in PR #7740:
URL: https://github.com/apache/hbase/pull/7740#discussion_r2794774536


##########
hbase-common/src/main/java/org/apache/hadoop/hbase/util/XXH3.java:
##########
@@ -0,0 +1,557 @@
+/*
+ * 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.hadoop.hbase.util;
+
+import static java.lang.Integer.toUnsignedLong;
+
+import org.apache.yetus.audience.InterfaceAudience;
+import org.apache.yetus.audience.InterfaceStability;
+
+/**
+ * XXH3 64-bit hash implementation.
+ * <p>
+ * Optimized for modern CPU architectures, providing high throughput, strong dispersion, and minimal
+ * memory usage. Designed for low-latency, zero-allocation hashing in most cases.
+ * <p>
+ * Note, however, that when the input exceeds 240 bytes and a non-default seed (anything other than
+ * {@code 0}) is used, a derived secret must be generated internally, which results in a temporary
+ * byte-array allocation.
+ * @see <a href=
+ *      "https://github.com/Cyan4973/xxHash/blob/dev/doc/xxhash_spec.md#xxh3-algorithm-overview">XXH3
+ *      Algorithm</a>
+ */
+@InterfaceAudience.Private
+@InterfaceStability.Unstable
+public class XXH3 extends Hash implements Hash64 {
+  private static final XXH3 _instance = new XXH3();
+  private static final long MASK32 = 0xFFFFFFFFL;
+  private static final long PRIME32_1 = 0x9E3779B1L;
+  private static final long PRIME32_2 = 0x85EBCA77L;
+  private static final long PRIME32_3 = 0xC2B2AE3DL;
+  private static final long PRIME64_1 = 0x9E3779B185EBCA87L;
+  private static final long PRIME64_2 = 0xC2B2AE3D27D4EB4FL;
+  private static final long PRIME64_3 = 0x165667B19E3779F9L;
+  private static final long PRIME64_4 = 0x85EBCA77C2B2AE63L;
+  private static final long PRIME64_5 = 0x27D4EB2F165667C5L;
+  private static final long PRIME_MX1 = 0x165667919E3779F9L;
+  private static final long PRIME_MX2 = 0x9FB21C651E98DF25L;
+
+  private static final byte[] DEFAULT_SECRET = { (byte) 0xb8, (byte) 0xfe, (byte) 0x6c, (byte) 0x39,
+    (byte) 0x23, (byte) 0xa4, (byte) 0x4b, (byte) 0xbe, (byte) 0x7c, (byte) 0x01, (byte) 0x81,
+    (byte) 0x2c, (byte) 0xf7, (byte) 0x21, (byte) 0xad, (byte) 0x1c, (byte) 0xde, (byte) 0xd4,
+    (byte) 0x6d, (byte) 0xe9, (byte) 0x83, (byte) 0x90, (byte) 0x97, (byte) 0xdb, (byte) 0x72,
+    (byte) 0x40, (byte) 0xa4, (byte) 0xa4, (byte) 0xb7, (byte) 0xb3, (byte) 0x67, (byte) 0x1f,
+    (byte) 0xcb, (byte) 0x79, (byte) 0xe6, (byte) 0x4e, (byte) 0xcc, (byte) 0xc0, (byte) 0xe5,
+    (byte) 0x78, (byte) 0x82, (byte) 0x5a, (byte) 0xd0, (byte) 0x7d, (byte) 0xcc, (byte) 0xff,
+    (byte) 0x72, (byte) 0x21, (byte) 0xb8, (byte) 0x08, (byte) 0x46, (byte) 0x74, (byte) 0xf7,
+    (byte) 0x43, (byte) 0x24, (byte) 0x8e, (byte) 0xe0, (byte) 0x35, (byte) 0x90, (byte) 0xe6,
+    (byte) 0x81, (byte) 0x3a, (byte) 0x26, (byte) 0x4c, (byte) 0x3c, (byte) 0x28, (byte) 0x52,
+    (byte) 0xbb, (byte) 0x91, (byte) 0xc3, (byte) 0x00, (byte) 0xcb, (byte) 0x88, (byte) 0xd0,
+    (byte) 0x65, (byte) 0x8b, (byte) 0x1b, (byte) 0x53, (byte) 0x2e, (byte) 0xa3, (byte) 0x71,
+    (byte) 0x64, (byte) 0x48, (byte) 0x97, (byte) 0xa2, (byte) 0x0d, (byte) 0xf9, (byte) 0x4e,
+    (byte) 0x38, (byte) 0x19, (byte) 0xef, (byte) 0x46, (byte) 0xa9, (byte) 0xde, (byte) 0xac,
+    (byte) 0xd8, (byte) 0xa8, (byte) 0xfa, (byte) 0x76, (byte) 0x3f, (byte) 0xe3, (byte) 0x9c,
+    (byte) 0x34, (byte) 0x3f, (byte) 0xf9, (byte) 0xdc, (byte) 0xbb, (byte) 0xc7, (byte) 0xc7,
+    (byte) 0x0b, (byte) 0x4f, (byte) 0x1d, (byte) 0x8a, (byte) 0x51, (byte) 0xe0, (byte) 0x4b,
+    (byte) 0xcd, (byte) 0xb4, (byte) 0x59, (byte) 0x31, (byte) 0xc8, (byte) 0x9f, (byte) 0x7e,
+    (byte) 0xc9, (byte) 0xd9, (byte) 0x78, (byte) 0x73, (byte) 0x64, (byte) 0xea, (byte) 0xc5,
+    (byte) 0xac, (byte) 0x83, (byte) 0x34, (byte) 0xd3, (byte) 0xeb, (byte) 0xc3, (byte) 0xc5,
+    (byte) 0x81, (byte) 0xa0, (byte) 0xff, (byte) 0xfa, (byte) 0x13, (byte) 0x63, (byte) 0xeb,
+    (byte) 0x17, (byte) 0x0d, (byte) 0xdd, (byte) 0x51, (byte) 0xb7, (byte) 0xf0, (byte) 0xda,
+    (byte) 0x49, (byte) 0xd3, (byte) 0x16, (byte) 0x55, (byte) 0x26, (byte) 0x29, (byte) 0xd4,
+    (byte) 0x68, (byte) 0x9e, (byte) 0x2b, (byte) 0x16, (byte) 0xbe, (byte) 0x58, (byte) 0x7d,
+    (byte) 0x47, (byte) 0xa1, (byte) 0xfc, (byte) 0x8f, (byte) 0xf8, (byte) 0xb8, (byte) 0xd1,
+    (byte) 0x7a, (byte) 0xd0, (byte) 0x31, (byte) 0xce, (byte) 0x45, (byte) 0xcb, (byte) 0x3a,
+    (byte) 0x8f, (byte) 0x95, (byte) 0x16, (byte) 0x04, (byte) 0x28, (byte) 0xaf, (byte) 0xd7,
+    (byte) 0xfb, (byte) 0xca, (byte) 0xbb, (byte) 0x4b, (byte) 0x40, (byte) 0x7e, };
+
+  // Pre-converted longs from DefaultSecret to avoid reconstruction at runtime

Review Comment:
   This matches the little-endian value we get from reading the default secret bytes as-is.
   Pre-computing it as a long like this gave a small performance bump when I tested.



##########
hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterUtil.java:
##########
@@ -278,4 +279,31 @@ public static byte[] getBloomFilterParam(BloomType bloomFilterType, Configuratio
     }
     return bloomParam;
   }
+
+  /**
+   * Generate the two hash values needed for Bloom filter index generation. Bloom filters require a
+   * (hash1, hash2) pair to derive multiple probe locations.
+   * <ul>
+   * <li>If the hash implementation provides a 64-bit hash, we split the 64-bit value into two
+   * 32-bit hashes to avoid extra hashing cost.</li>
+   * <li>Otherwise, fall back to classic double hashing by rehashing with hash1 as the seed.</li>
+   * </ul>
+   * @param hash the hash function
+   * @param key  the hash key
+   * @return a pair of hash values (hash1, hash2)
+   */
+  public static Pair<Integer, Integer> getHashPair(Hash hash, HashKey<?> key) {
+    if (hash instanceof Hash64) {
+      long hash64 = ((Hash64) hash).hash64(key);
+      // Use lower 32 bits as first hash, upper 32 bits as second hash.
+      int hash1 = (int) hash64;
+      int hash2 = (int) (hash64 >>> 32);

Review Comment:
   A well-designed hash function should behave reliably even if we take either half of its 64-bit output as a 32-bit value. XXH3 is no exception.
   I'm adding the XXH3 author’s comment here for reference.
   https://github.com/Cyan4973/xxHash/issues/453#issuecomment-696838445



##########
hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/CompoundBloomFilter.java:
##########
@@ -217,6 +218,9 @@ public String toString() {
     sb.append(BloomFilterUtil.STATS_RECORD_SEP + ((comparator != null)
       ? "Comparator: " + comparator.getClass().getSimpleName()
       : "Comparator: " + Bytes.BYTES_RAWCOMPARATOR.getClass().getSimpleName()));
+    sb.append(BloomFilterUtil.STATS_RECORD_SEP + "Hash type: " + hashType)
+      .append(" (" + Optional.ofNullable(Hash.getInstance(hashType))
+        .map(i -> i.getClass().getSimpleName()).orElse("UNKNOWN") + ")");

Review Comment:
   I'd like to show the Bloom filter hash type in HFilePrettyPrinter.



##########
hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterUtil.java:
##########
@@ -278,4 +279,31 @@ public static byte[] getBloomFilterParam(BloomType bloomFilterType, Configuratio
     }
     return bloomParam;
   }
+
+  /**
+   * Generate the two hash values needed for Bloom filter index generation. Bloom filters require a
+   * (hash1, hash2) pair to derive multiple probe locations.
+   * <ul>
+   * <li>If the hash implementation provides a 64-bit hash, we split the 64-bit value into two
+   * 32-bit hashes to avoid extra hashing cost.</li>
+   * <li>Otherwise, fall back to classic double hashing by rehashing with hash1 as the seed.</li>
+   * </ul>
+   * @param hash the hash function
+   * @param key  the hash key
+   * @return a pair of hash values (hash1, hash2)
+   */
+  public static Pair<Integer, Integer> getHashPair(Hash hash, HashKey<?> key) {

Review Comment:
   This part gave me a bit of trouble.
   I put quite a lot of work into making the XXH3 implementation zero-heap, but ironically ended up adding a small object allocation in the hash calculation path.
   
   The main reason was that the Bloom filter hash-location logic was split across two different classes, so I consolidated it into one place. This contains path is pretty hot, so I hesitated a bit, but given recent GC algorithm performance it might be acceptable.
   
   Still, I'd love to hear your thoughts on this trade-off.



##########
hbase-common/src/main/java/org/apache/hadoop/hbase/util/XXH3.java:
##########
@@ -0,0 +1,557 @@
+/*
+ * 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.hadoop.hbase.util;
+
+import static java.lang.Integer.toUnsignedLong;
+
+import org.apache.yetus.audience.InterfaceAudience;
+import org.apache.yetus.audience.InterfaceStability;
+
+/**
+ * XXH3 64-bit hash implementation.
+ * <p>
+ * Optimized for modern CPU architectures, providing high throughput, strong dispersion, and minimal
+ * memory usage. Designed for low-latency, zero-allocation hashing in most cases.
+ * <p>
+ * Note, however, that when the input exceeds 240 bytes and a non-default seed (anything other than
+ * {@code 0}) is used, a derived secret must be generated internally, which results in a temporary
+ * byte-array allocation.
+ * @see <a href=
+ *      "https://github.com/Cyan4973/xxHash/blob/dev/doc/xxhash_spec.md#xxh3-algorithm-overview">XXH3
+ *      Algorithm</a>
+ */
+@InterfaceAudience.Private
+@InterfaceStability.Unstable
+public class XXH3 extends Hash implements Hash64 {
+  private static final XXH3 _instance = new XXH3();
+  private static final long MASK32 = 0xFFFFFFFFL;
+  private static final long PRIME32_1 = 0x9E3779B1L;
+  private static final long PRIME32_2 = 0x85EBCA77L;
+  private static final long PRIME32_3 = 0xC2B2AE3DL;
+  private static final long PRIME64_1 = 0x9E3779B185EBCA87L;
+  private static final long PRIME64_2 = 0xC2B2AE3D27D4EB4FL;
+  private static final long PRIME64_3 = 0x165667B19E3779F9L;
+  private static final long PRIME64_4 = 0x85EBCA77C2B2AE63L;
+  private static final long PRIME64_5 = 0x27D4EB2F165667C5L;
+  private static final long PRIME_MX1 = 0x165667919E3779F9L;
+  private static final long PRIME_MX2 = 0x9FB21C651E98DF25L;
+
+  private static final byte[] DEFAULT_SECRET = { (byte) 0xb8, (byte) 0xfe, (byte) 0x6c, (byte) 0x39,
+    (byte) 0x23, (byte) 0xa4, (byte) 0x4b, (byte) 0xbe, (byte) 0x7c, (byte) 0x01, (byte) 0x81,
+    (byte) 0x2c, (byte) 0xf7, (byte) 0x21, (byte) 0xad, (byte) 0x1c, (byte) 0xde, (byte) 0xd4,
+    (byte) 0x6d, (byte) 0xe9, (byte) 0x83, (byte) 0x90, (byte) 0x97, (byte) 0xdb, (byte) 0x72,
+    (byte) 0x40, (byte) 0xa4, (byte) 0xa4, (byte) 0xb7, (byte) 0xb3, (byte) 0x67, (byte) 0x1f,
+    (byte) 0xcb, (byte) 0x79, (byte) 0xe6, (byte) 0x4e, (byte) 0xcc, (byte) 0xc0, (byte) 0xe5,
+    (byte) 0x78, (byte) 0x82, (byte) 0x5a, (byte) 0xd0, (byte) 0x7d, (byte) 0xcc, (byte) 0xff,
+    (byte) 0x72, (byte) 0x21, (byte) 0xb8, (byte) 0x08, (byte) 0x46, (byte) 0x74, (byte) 0xf7,
+    (byte) 0x43, (byte) 0x24, (byte) 0x8e, (byte) 0xe0, (byte) 0x35, (byte) 0x90, (byte) 0xe6,
+    (byte) 0x81, (byte) 0x3a, (byte) 0x26, (byte) 0x4c, (byte) 0x3c, (byte) 0x28, (byte) 0x52,
+    (byte) 0xbb, (byte) 0x91, (byte) 0xc3, (byte) 0x00, (byte) 0xcb, (byte) 0x88, (byte) 0xd0,
+    (byte) 0x65, (byte) 0x8b, (byte) 0x1b, (byte) 0x53, (byte) 0x2e, (byte) 0xa3, (byte) 0x71,
+    (byte) 0x64, (byte) 0x48, (byte) 0x97, (byte) 0xa2, (byte) 0x0d, (byte) 0xf9, (byte) 0x4e,
+    (byte) 0x38, (byte) 0x19, (byte) 0xef, (byte) 0x46, (byte) 0xa9, (byte) 0xde, (byte) 0xac,
+    (byte) 0xd8, (byte) 0xa8, (byte) 0xfa, (byte) 0x76, (byte) 0x3f, (byte) 0xe3, (byte) 0x9c,
+    (byte) 0x34, (byte) 0x3f, (byte) 0xf9, (byte) 0xdc, (byte) 0xbb, (byte) 0xc7, (byte) 0xc7,
+    (byte) 0x0b, (byte) 0x4f, (byte) 0x1d, (byte) 0x8a, (byte) 0x51, (byte) 0xe0, (byte) 0x4b,
+    (byte) 0xcd, (byte) 0xb4, (byte) 0x59, (byte) 0x31, (byte) 0xc8, (byte) 0x9f, (byte) 0x7e,
+    (byte) 0xc9, (byte) 0xd9, (byte) 0x78, (byte) 0x73, (byte) 0x64, (byte) 0xea, (byte) 0xc5,
+    (byte) 0xac, (byte) 0x83, (byte) 0x34, (byte) 0xd3, (byte) 0xeb, (byte) 0xc3, (byte) 0xc5,
+    (byte) 0x81, (byte) 0xa0, (byte) 0xff, (byte) 0xfa, (byte) 0x13, (byte) 0x63, (byte) 0xeb,
+    (byte) 0x17, (byte) 0x0d, (byte) 0xdd, (byte) 0x51, (byte) 0xb7, (byte) 0xf0, (byte) 0xda,
+    (byte) 0x49, (byte) 0xd3, (byte) 0x16, (byte) 0x55, (byte) 0x26, (byte) 0x29, (byte) 0xd4,
+    (byte) 0x68, (byte) 0x9e, (byte) 0x2b, (byte) 0x16, (byte) 0xbe, (byte) 0x58, (byte) 0x7d,
+    (byte) 0x47, (byte) 0xa1, (byte) 0xfc, (byte) 0x8f, (byte) 0xf8, (byte) 0xb8, (byte) 0xd1,
+    (byte) 0x7a, (byte) 0xd0, (byte) 0x31, (byte) 0xce, (byte) 0x45, (byte) 0xcb, (byte) 0x3a,
+    (byte) 0x8f, (byte) 0x95, (byte) 0x16, (byte) 0x04, (byte) 0x28, (byte) 0xaf, (byte) 0xd7,
+    (byte) 0xfb, (byte) 0xca, (byte) 0xbb, (byte) 0x4b, (byte) 0x40, (byte) 0x7e, };
+
+  // Pre-converted longs from DefaultSecret to avoid reconstruction at runtime

Review Comment:
   This loads an additional set of 37 long values as static fields.
   There’s some overhead from keeping these statically initialized values around, but the performance gains make it worthwhile.



##########
hbase-common/src/main/java/org/apache/hadoop/hbase/util/Hash64.java:
##########
@@ -0,0 +1,45 @@
+/*
+ * 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.hadoop.hbase.util;
+
+import org.apache.yetus.audience.InterfaceAudience;
+import org.apache.yetus.audience.InterfaceStability;
+
+/**
+ * Interface for computing 64-bit hash values.
+ */
+@InterfaceAudience.Private
+@InterfaceStability.Stable
+public interface Hash64 {
+  /**
+   * Computes a 64-bit hash from the given {@code HashKey} using a seed of 0.
+   * @param hashKey the input key providing byte access
+   * @return the computed 64-bit hash value
+   */
+  default <T> long hash64(HashKey<T> hashKey) {
+    return hash64(hashKey, 0L);
+  }
+
+  /**
+   * Computes a 64-bit hash from the given {@code HashKey} and seed.
+   * @param hashKey the input key providing byte access
+   * @param seed    the 64-bit seed value
+   * @return the computed 64-bit hash value
+   */
+  <T> long hash64(HashKey<T> hashKey, long seed);

Review Comment:
   The goal here is to take a single 64-bit hash result and split it into two 32-bit hashes to compute the Bloom hash locations.
   
   ```
   -------------- 64-bit hash output --------------
   |                    64 bits                   |
   ------------------------------------------------
   |              lower 32 bits (hash1)           |
   |              upper 32 bits (hash2)           |
   ------------------------------------------------
   ```
   
   Since XXH3 already performs much better than the existing hashes and we no longer need to run the hash function twice, this approach gives us an additional performance win on top of the baseline speedup.



##########
hbase-common/src/main/java/org/apache/hadoop/hbase/util/RowColBloomHashKey.java:
##########
@@ -80,9 +87,146 @@ public byte get(int offset) {
 
   @Override
   public int length() {
-    // For ROW_COL blooms we use bytes
-    // <RK length> (2 bytes) , <RK>, 0 (one byte CF length), <CQ>, <TS> (8 btes), <TYPE> ( 1 byte)
-    return KeyValue.ROW_LENGTH_SIZE + this.t.getRowLength() + KeyValue.FAMILY_LENGTH_SIZE
-      + this.t.getQualifierLength() + KeyValue.TIMESTAMP_TYPE_SIZE;
+    return totalLength;
+  }
+
+  @Override
+  public int getIntLE(int offset) {
+    // Handle fast path that can return the row key as int directly
+    // Compute rowkey section range.
+    final int rowEnd = KeyValue.ROW_LENGTH_SIZE + rowLength;
+    if (offset >= KeyValue.ROW_LENGTH_SIZE && offset + Bytes.SIZEOF_INT <= rowEnd) {
+      return LittleEndianBytes.getRowAsInt(t, offset - KeyValue.ROW_LENGTH_SIZE);
+    }
+
+    // Compute qualifier section range.
+    final int qualStart = rowEnd + KeyValue.FAMILY_LENGTH_SIZE;
+    final int qualEnd = qualStart + qualLength;
+    if (offset >= qualStart && offset + Bytes.SIZEOF_INT <= qualEnd) {
+      return LittleEndianBytes.getQualifierAsInt(t, offset - qualStart);
+    }
+
+    // Compute timestamp section range.
+    final int tsEnd = qualEnd + KeyValue.TIMESTAMP_SIZE;
+    if (offset >= qualEnd && offset + Bytes.SIZEOF_INT <= tsEnd) {
+      return LittleEndianBytes.toInt(LATEST_TS, offset - qualEnd);
+    }
+
+    return (int) assembleCrossingLE(offset, Bytes.SIZEOF_INT);
+  }
+
+  @Override
+  public long getLongLE(int offset) {
+    // Handle fast path that can return the row key as long directly
+    // Compute rowkey section range.
+    final int rowEnd = KeyValue.ROW_LENGTH_SIZE + rowLength;
+    if (offset >= KeyValue.ROW_LENGTH_SIZE && offset + Bytes.SIZEOF_LONG <= rowEnd) {
+      return LittleEndianBytes.getRowAsLong(t, offset - KeyValue.ROW_LENGTH_SIZE);
+    }
+
+    // Compute qualifier section range.
+    final int qualStart = rowEnd + KeyValue.FAMILY_LENGTH_SIZE;
+    final int qualEnd = qualStart + qualLength;
+    if (offset >= qualStart && offset + Bytes.SIZEOF_LONG <= qualEnd) {
+      return LittleEndianBytes.getQualifierAsLong(t, offset - qualStart);
+    }
+
+    // Compute timestamp section range.
+    if (offset == qualEnd) {
+      return LATEST_TS_LE;
+    }
+
+    // Optimization: when the offset points to the last 8 bytes,
+    // we can return the precomputed trailing long value directly.
+    if (offset + Bytes.SIZEOF_LONG == totalLength) {
+      return LAST_8_BYTES;

Review Comment:
   This approach gave better performance in the 9–16 byte hash path.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@hbase.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] HBASE-29889 Add XXH3 Hash Support to Bloom Filter [hbase]

Posted by "jinhyukify (via GitHub)" <gi...@apache.org>.
jinhyukify commented on PR #7740:
URL: https://github.com/apache/hbase/pull/7740#issuecomment-3935626270

   Hello! Here is the additional context I’d like to share after re-running the benchmarks:
   
   Although I initially thought the JDK version might limit us, I realized that starting from HBase 3+ we are already on JDK 17, so Java version compatibility is no longer an issue. This made me revisit the option of adopting hash4j, since its performance with byte-array inputs is indeed excellent.
   
   However, the new results were quite unexpected.
   
   I provide input through our `HashKey` interface, which exposes data 1 byte at a time for streaming access, and in this PR I also added optimized 4-byte and 8-byte read operations on top of it. With hash4j, this means we must use its [HashFunnel](https://github.com/dynatrace-oss/hash4j/blob/main/src/main/java/com/dynatrace/hash4j/hashing/HashFunnel.java) interface instead of passing a raw byte array. While the byte-array path is very fast, the streaming path in hash4j turned out to be extremely slower. Profiling showed that the internal handling of streamed input is not very efficient, and this leads to a substantial performance drop.
   
   <img width="872" height="1091" alt="스크린샷 2026-02-21 오전 12 09 51" src="https://github.com/user-attachments/assets/0407cb2c-445b-4e08-83d0-9b4dde7692f6" />
   
   - Tested in here: https://github.com/jinhyukify/xxh3-benchmark/tree/hash4j
   - You can check the benchmark results
   
   Given this, I don’t think we can adopt hash4j unless we change our hashing API to return a raw byte array, which I personally want to avoid because it would introduce unnecessary allocations and GC pressure.
   
   For this reason, I opened a separate PR that implements XXH3 using Zero-Allocation-Hashing library.
   https://github.com/apache/hbase/pull/7772
   
   If maintaining our own implementation is a concern (XXH3 is indeed non-trivial), ZAH is an alternative. However, it is still roughly 2× slower than the implementation in this PR.
   
   Happy to discuss further if you have any thoughts or preferences!
   
   ---
   
   **Summary**
   
   - I evaluated both **Zero-Allocation-Hashing** and **hash4j**. While **hash4j** shows excellent performance with raw byte-array inputs, its streaming path (which we must use due to the HashKey interface) is significantly slower and therefore not feasible for our use case.
   - I also opened a PR with a ZAH-based implementation, but it performs roughly 2× slower than this PR, especially for small and medium input sizes.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@hbase.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] HBASE-29889 Add XXH3 Hash Support to Bloom Filter [hbase]

Posted by "Apache9 (via GitHub)" <gi...@apache.org>.
Apache9 commented on PR #7740:
URL: https://github.com/apache/hbase/pull/7740#issuecomment-3901234331

   We need to implement this algorithm by ourselves? No existing libraries available?


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@hbase.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] HBASE-29889 Add XXH3 Hash Support to Bloom Filter [hbase]

Posted by "Apache9 (via GitHub)" <gi...@apache.org>.
Apache9 commented on PR #7740:
URL: https://github.com/apache/hbase/pull/7740#issuecomment-3901241325

   Like this one?
   
   https://github.com/OpenHFT/Zero-Allocation-Hashing


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@hbase.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] HBASE-29889 Add XXH3 Hash Support to Bloom Filter [hbase]

Posted by "oertl (via GitHub)" <gi...@apache.org>.
oertl commented on PR #7740:
URL: https://github.com/apache/hbase/pull/7740#issuecomment-3935910947

   Hi! I am a developer of hash4j. Have you tried implementing the `ByteAccess` interface for `HashKey`? With that, you could hash directly using https://github.com/dynatrace-oss/hash4j/blob/206f723b423ccdb22c90ad9c09c3efc043331760/src/main/java/com/dynatrace/hash4j/hashing/Hasher64.java#L92


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@hbase.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] HBASE-29889 Add XXH3 Hash Support to Bloom Filter [hbase]

Posted by "jinhyukify (via GitHub)" <gi...@apache.org>.
jinhyukify commented on PR #7740:
URL: https://github.com/apache/hbase/pull/7740#issuecomment-3936513037

   @oertl Hello. First of all, thank you for developing such a great library!
   
   I tried switching the integration to use the `ByteAccess` interface as you suggested, and the performance results were much better than the streaming approach with `HashFunnel`. The numbers were very close to what I expected based on the byte array benchmarks.
   
   <img width="876" height="1091" alt="스크린샷 2026-02-21 오전 3 34 02" src="https://github.com/user-attachments/assets/35c793bf-1c06-49b9-92a7-a13da621ba5c" />
   
   - Test code: https://github.com/jinhyukify/xxh3-benchmark/blob/hash4j/src/main/java/hash/HashKeyByteAccess.java
   
   
   Thanks again for the help!


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@hbase.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] HBASE-29889 Add XXH3 Hash Support to Bloom Filter [hbase]

Posted by "jinhyukify (via GitHub)" <gi...@apache.org>.
jinhyukify commented on PR #7740:
URL: https://github.com/apache/hbase/pull/7740#issuecomment-3901438289

   @Apache9 Thank you for reviewing this first. 😄 
   
   I first evaluated [Zero-Allocation-Hashing](https://github.com/OpenHFT/Zero-Allocation-Hashing) and [hash4j](https://github.com/dynatrace-oss/hash4j).
   The performance results were as follows:
   <img width="812" height="1000" alt="스크린샷 2026-02-14 오후 5 31 03" src="https://github.com/user-attachments/assets/2f3a2c79-23a9-416d-abc6-72c4a77c19e2" />
   
   There are several reasons why I decided not to adopt these libraries.
   
   ### Zero-Allocation-Hashing (ZAH)
   HBase provides fallback logic for `Unsafe` access and therefore does not strictly depend on `Unsafe`. However, Zero-Allocation-Hashing relies on Unsafe when reading the secret.
   https://github.com/OpenHFT/Zero-Allocation-Hashing/blob/ea/src/main/java/net/openhft/hashing/XXH3.java#L17
   
   And this implementation showed slightly better performance. I believe this comes from an optimization where I pre-decode the input bytes into long values (precomputed long loads)
   
   ### Hash4j
   hash4j shows better performance starting from medium input lengths, but it only supports JDK 11 and above. The observed performance difference appears to come from intrinsic optimizations of functions that were introduced in Java 9 and later.
   https://github.com/dynatrace-oss/hash4j/blob/main/src/main/java/com/dynatrace/hash4j/internal/UnsignedMultiplyUtil.java#L36
   
   In my personal view, hash function implementations typically do not require continuous maintenance. Therefore, maintaining our own implementation should not be considered a significant drawback. WDYT?


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@hbase.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] HBASE-29889 Add XXH3 Hash Support to Bloom Filter [hbase]

Posted by "jinhyukify (via GitHub)" <gi...@apache.org>.
jinhyukify commented on code in PR #7740:
URL: https://github.com/apache/hbase/pull/7740#discussion_r2833831089


##########
hbase-common/src/main/java/org/apache/hadoop/hbase/util/XXH3.java:
##########
@@ -0,0 +1,579 @@
+/*
+ * 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.hadoop.hbase.util;
+
+import static java.lang.Integer.toUnsignedLong;
+
+import org.apache.yetus.audience.InterfaceAudience;
+import org.apache.yetus.audience.InterfaceStability;
+
+/**
+ * XXH3 64-bit hash implementation.
+ * <p>
+ * Optimized for modern CPU architectures, providing high throughput, strong dispersion, and minimal
+ * memory usage. Designed for low-latency, zero-allocation hashing in most cases.
+ * <p>
+ * Note, however, that when the input exceeds 240 bytes and a non-default seed (anything other than
+ * {@code 0}) is used, a derived secret must be generated internally, which results in a temporary
+ * byte-array allocation.
+ * @see <a href=
+ *      "https://github.com/Cyan4973/xxHash/blob/dev/doc/xxhash_spec.md#xxh3-algorithm-overview">XXH3
+ *      Algorithm</a>
+ */
+@InterfaceAudience.Private
+@InterfaceStability.Unstable
+public class XXH3 extends Hash implements Hash64 {
+  private static final XXH3 _instance = new XXH3();
+  private static final long MASK32 = 0xFFFFFFFFL;
+  private static final long PRIME32_1 = 0x9E3779B1L;
+  private static final long PRIME32_2 = 0x85EBCA77L;
+  private static final long PRIME32_3 = 0xC2B2AE3DL;
+  private static final long PRIME64_1 = 0x9E3779B185EBCA87L;
+  private static final long PRIME64_2 = 0xC2B2AE3D27D4EB4FL;
+  private static final long PRIME64_3 = 0x165667B19E3779F9L;
+  private static final long PRIME64_4 = 0x85EBCA77C2B2AE63L;
+  private static final long PRIME64_5 = 0x27D4EB2F165667C5L;
+  private static final long PRIME_MX1 = 0x165667919E3779F9L;
+  private static final long PRIME_MX2 = 0x9FB21C651E98DF25L;
+
+  private static final byte[] DEFAULT_SECRET = { (byte) 0xb8, (byte) 0xfe, (byte) 0x6c, (byte) 0x39,
+    (byte) 0x23, (byte) 0xa4, (byte) 0x4b, (byte) 0xbe, (byte) 0x7c, (byte) 0x01, (byte) 0x81,
+    (byte) 0x2c, (byte) 0xf7, (byte) 0x21, (byte) 0xad, (byte) 0x1c, (byte) 0xde, (byte) 0xd4,
+    (byte) 0x6d, (byte) 0xe9, (byte) 0x83, (byte) 0x90, (byte) 0x97, (byte) 0xdb, (byte) 0x72,
+    (byte) 0x40, (byte) 0xa4, (byte) 0xa4, (byte) 0xb7, (byte) 0xb3, (byte) 0x67, (byte) 0x1f,
+    (byte) 0xcb, (byte) 0x79, (byte) 0xe6, (byte) 0x4e, (byte) 0xcc, (byte) 0xc0, (byte) 0xe5,
+    (byte) 0x78, (byte) 0x82, (byte) 0x5a, (byte) 0xd0, (byte) 0x7d, (byte) 0xcc, (byte) 0xff,
+    (byte) 0x72, (byte) 0x21, (byte) 0xb8, (byte) 0x08, (byte) 0x46, (byte) 0x74, (byte) 0xf7,
+    (byte) 0x43, (byte) 0x24, (byte) 0x8e, (byte) 0xe0, (byte) 0x35, (byte) 0x90, (byte) 0xe6,
+    (byte) 0x81, (byte) 0x3a, (byte) 0x26, (byte) 0x4c, (byte) 0x3c, (byte) 0x28, (byte) 0x52,
+    (byte) 0xbb, (byte) 0x91, (byte) 0xc3, (byte) 0x00, (byte) 0xcb, (byte) 0x88, (byte) 0xd0,
+    (byte) 0x65, (byte) 0x8b, (byte) 0x1b, (byte) 0x53, (byte) 0x2e, (byte) 0xa3, (byte) 0x71,
+    (byte) 0x64, (byte) 0x48, (byte) 0x97, (byte) 0xa2, (byte) 0x0d, (byte) 0xf9, (byte) 0x4e,
+    (byte) 0x38, (byte) 0x19, (byte) 0xef, (byte) 0x46, (byte) 0xa9, (byte) 0xde, (byte) 0xac,
+    (byte) 0xd8, (byte) 0xa8, (byte) 0xfa, (byte) 0x76, (byte) 0x3f, (byte) 0xe3, (byte) 0x9c,
+    (byte) 0x34, (byte) 0x3f, (byte) 0xf9, (byte) 0xdc, (byte) 0xbb, (byte) 0xc7, (byte) 0xc7,
+    (byte) 0x0b, (byte) 0x4f, (byte) 0x1d, (byte) 0x8a, (byte) 0x51, (byte) 0xe0, (byte) 0x4b,
+    (byte) 0xcd, (byte) 0xb4, (byte) 0x59, (byte) 0x31, (byte) 0xc8, (byte) 0x9f, (byte) 0x7e,
+    (byte) 0xc9, (byte) 0xd9, (byte) 0x78, (byte) 0x73, (byte) 0x64, (byte) 0xea, (byte) 0xc5,
+    (byte) 0xac, (byte) 0x83, (byte) 0x34, (byte) 0xd3, (byte) 0xeb, (byte) 0xc3, (byte) 0xc5,
+    (byte) 0x81, (byte) 0xa0, (byte) 0xff, (byte) 0xfa, (byte) 0x13, (byte) 0x63, (byte) 0xeb,
+    (byte) 0x17, (byte) 0x0d, (byte) 0xdd, (byte) 0x51, (byte) 0xb7, (byte) 0xf0, (byte) 0xda,
+    (byte) 0x49, (byte) 0xd3, (byte) 0x16, (byte) 0x55, (byte) 0x26, (byte) 0x29, (byte) 0xd4,
+    (byte) 0x68, (byte) 0x9e, (byte) 0x2b, (byte) 0x16, (byte) 0xbe, (byte) 0x58, (byte) 0x7d,
+    (byte) 0x47, (byte) 0xa1, (byte) 0xfc, (byte) 0x8f, (byte) 0xf8, (byte) 0xb8, (byte) 0xd1,
+    (byte) 0x7a, (byte) 0xd0, (byte) 0x31, (byte) 0xce, (byte) 0x45, (byte) 0xcb, (byte) 0x3a,
+    (byte) 0x8f, (byte) 0x95, (byte) 0x16, (byte) 0x04, (byte) 0x28, (byte) 0xaf, (byte) 0xd7,
+    (byte) 0xfb, (byte) 0xca, (byte) 0xbb, (byte) 0x4b, (byte) 0x40, (byte) 0x7e, };
+
+  // Pre-converted longs from DefaultSecret to avoid reconstruction at runtime
+  private static final long DEFAULT_SECRET_LONG_0 = 0xBE4BA423396CFEB8L;
+  private static final long DEFAULT_SECRET_LONG_1 = 0x1CAD21F72C81017CL;
+  private static final long DEFAULT_SECRET_LONG_2 = 0xDB979083E96DD4DEL;
+  private static final long DEFAULT_SECRET_LONG_3 = 0x1F67B3B7A4A44072L;
+  private static final long DEFAULT_SECRET_LONG_4 = 0x78E5C0CC4EE679CBL;
+  private static final long DEFAULT_SECRET_LONG_5 = 0x2172FFCC7DD05A82L;
+  private static final long DEFAULT_SECRET_LONG_6 = 0x8E2443F7744608B8L;
+  private static final long DEFAULT_SECRET_LONG_7 = 0x4C263A81E69035E0L;
+  private static final long DEFAULT_SECRET_LONG_8 = 0xCB00C391BB52283CL;
+  private static final long DEFAULT_SECRET_LONG_9 = 0xA32E531B8B65D088L;
+  private static final long DEFAULT_SECRET_LONG_10 = 0x4EF90DA297486471L;
+  private static final long DEFAULT_SECRET_LONG_11 = 0xD8ACDEA946EF1938L;
+  private static final long DEFAULT_SECRET_LONG_12 = 0x3F349CE33F76FAA8L;
+  private static final long DEFAULT_SECRET_LONG_13 = 0x1D4F0BC7C7BBDCF9L;
+  private static final long DEFAULT_SECRET_LONG_14 = 0x3159B4CD4BE0518AL;
+  private static final long DEFAULT_SECRET_LONG_15 = 0x647378D9C97E9FC8L;
+
+  // Pre-converted longs from DefaultSecret (3-byte offset) to avoid reconstruction at runtime.
+  private static final long DEFAULT_SECRET_3_LONG_0 = 0x81017CBE4BA42339L;
+  private static final long DEFAULT_SECRET_3_LONG_1 = 0x6DD4DE1CAD21F72CL;
+  private static final long DEFAULT_SECRET_3_LONG_2 = 0xA44072DB979083E9L;
+  private static final long DEFAULT_SECRET_3_LONG_3 = 0xE679CB1F67B3B7A4L;
+  private static final long DEFAULT_SECRET_3_LONG_4 = 0xD05A8278E5C0CC4EL;
+  private static final long DEFAULT_SECRET_3_LONG_5 = 0x4608B82172FFCC7DL;
+  private static final long DEFAULT_SECRET_3_LONG_6 = 0x9035E08E2443F774L;
+  private static final long DEFAULT_SECRET_3_LONG_7 = 0x52283C4C263A81E6L;
+  private static final long DEFAULT_SECRET_3_LONG_8 = 0x65D088CB00C391BBL;
+  private static final long DEFAULT_SECRET_3_LONG_9 = 0x486471A32E531B8BL;
+  private static final long DEFAULT_SECRET_3_LONG_10 = 0xEF19384EF90DA297L;
+  private static final long DEFAULT_SECRET_3_LONG_11 = 0x76FAA8D8ACDEA946L;
+  private static final long DEFAULT_SECRET_3_LONG_12 = 0xBBDCF93F349CE33FL;
+  private static final long DEFAULT_SECRET_3_LONG_13 = 0xE0518A1D4F0BC7C7L;
+
+  private static final long DEFAULT_SECRET_LONG_119 = 0x7378D9C97E9FC831L;
+  private static final long DEFAULT_SECRET_LONG_127 = 0xEBD33483ACC5EA64L;
+
+  private static final long DEFAULT_SECRET_BITFLIP_0 =
+    ((DEFAULT_SECRET_LONG_0 >>> 32) ^ (DEFAULT_SECRET_LONG_0 & MASK32));
+  private static final long DEFAULT_SECRET_BITFLIP_1 =
+    (DEFAULT_SECRET_LONG_1 ^ DEFAULT_SECRET_LONG_2);
+  private static final long DEFAULT_SECRET_BITFLIP_2 =
+    (DEFAULT_SECRET_LONG_3 ^ DEFAULT_SECRET_LONG_4);
+  private static final long DEFAULT_SECRET_BITFLIP_3 =
+    (DEFAULT_SECRET_LONG_5 ^ DEFAULT_SECRET_LONG_6);
+  private static final long DEFAULT_SECRET_BITFLIP_4 =
+    (DEFAULT_SECRET_LONG_7 ^ DEFAULT_SECRET_LONG_8);
+
+  public static Hash getInstance() {
+    return _instance;
+  }
+
+  @Override
+  public <T> long hash64(HashKey<T> hashKey, long seed) {
+    int length = hashKey.length();
+    long result64;
+
+    if (length <= 16) {
+      result64 = hashSmall(hashKey, length, seed);
+    } else if (length <= 240) {
+      result64 = hashMedium(hashKey, length, seed);
+    } else {
+      result64 = hashLarge(hashKey, length, seed);
+    }
+
+    return result64;
+  }
+
+  @Override
+  public <T> int hash(HashKey<T> hashKey, int seed) {
+    long result64 = hash64(hashKey, (long) seed);
+    return toLow32Int(result64);
+  }
+
+  private byte[] initSecret(long seed) {
+    if (seed == 0L) {
+      return DEFAULT_SECRET;
+    } else {
+      // For non-default seeds, derived secret generation requires a new byte array.
+      byte[] derivedSecret = new byte[192];
+      for (int i = 0; i < 12; i++) {
+        putLong64LE(derivedSecret, i * 16, readLong64LE(DEFAULT_SECRET, i * 16) + seed);
+        putLong64LE(derivedSecret, i * 16 + 8, readLong64LE(DEFAULT_SECRET, i * 16 + 8) - seed);
+      }
+      return derivedSecret;
+    }
+  }
+
+  private static int toLow32Int(long value) {
+    // Grab only the lower 32 bits.
+    return (int) value;
+  }
+
+  private static long avalanche(long hash) {
+    hash ^= hash >>> 37;
+    hash *= PRIME_MX1;
+    hash ^= hash >>> 32;
+    return hash;
+  }
+
+  private static long avalancheXXH64(long hash) {
+    hash ^= hash >>> 33;
+    hash *= PRIME64_2;
+    hash ^= hash >>> 29;
+    hash *= PRIME64_3;
+    hash ^= hash >>> 32;
+    return hash;
+  }
+
+  private static long rrmxmx(long hash, int inputLength) {
+    hash ^= Long.rotateLeft(hash, 49) ^ Long.rotateLeft(hash, 24);
+    hash *= PRIME_MX2;
+    hash ^= (hash >>> 35) + inputLength;
+    hash *= PRIME_MX2;
+    hash ^= hash >>> 28;
+    return hash;
+  }
+
+  private static long mul128AndFold64(long x, long y) {
+    // Consider switching to Math.unsignedMultiplyHigh(x, y) when we can drop Java 8.

Review Comment:
   Replaced this to use `Math.multiplyHigh`(>= jdk 9) in HBase3+



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@hbase.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] HBASE-29889 Add XXH3 Hash Support to Bloom Filter [hbase]

Posted by "jinhyukify (via GitHub)" <gi...@apache.org>.
jinhyukify commented on PR #7740:
URL: https://github.com/apache/hbase/pull/7740#issuecomment-3938418885

   I’ve opened a PR that implements XXH3 using hash4j.
   https://github.com/apache/hbase/pull/7782
   
   If we plan to introduce XXH3 to HBase 2.x as well, we might need a different approach because of the JDK version constraints.
   Please have a look when you have time and share your thoughts. 😄 


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@hbase.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] HBASE-29889 Add XXH3 Hash Support to Bloom Filter [hbase]

Posted by "jinhyukify (via GitHub)" <gi...@apache.org>.
jinhyukify commented on PR #7740:
URL: https://github.com/apache/hbase/pull/7740#issuecomment-4052158574

   I applied the same optimization to the existing hash implementations to read 4 bytes at once instead of assembling integers byte-by-byte.
   This optimization also brings noticeable performance improvements. The benchmark results are summarized below.
   For easier comparison, I also attached graphs in the Jira comment. Please take a look. 🙇‍♂️ 
   
   | Length | Jenkins | **Jenkins After** | Δ% | Murmur | **Murmur After** | Δ% | Murmur3 | **Murmur3 After** | Δ% |
   |---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|
   | 3 | 377M | **381M** | +1.2% | 598M | **599M** | +0.3% | 622M | **619M** | -0.5% |
   | 8 | 323M | **330M** | +2.2% | 315M | **417M** | +32.5% | 275M | **384M** | +39.6% |
   | 16 | 147M | **204M** | +39.0% | 246M | **339M** | +37.7% | 207M | **282M** | +35.8% |
   | 32 | 100M | **139M** | +38.5% | 145M | **208M** | +43.3% | 128M | **176M** | +37.2% |
   | 64 | 51M | **70M** | +38.2% | 85M | **113M** | +32.4% | 70M | **89M** | +28.0% |
   | 128 | 26M | **33M** | +27.7% | 44M | **56M** | +28.4% | 36M | **42M** | +15.9% |
   | 240 | 13M | **17M** | +33.6% | 23M | **29M** | +23.8% | 18M | **19M** | +8.0% |
   | 256 | 12M | **16M** | +31.4% | 22M | **27M** | +22.0% | 15M | **18M** | +23.6% |
   | 512 | 6M | **8M** | +26.5% | 10M | **12M** | +14.9% | 7M | **7M** | +2.0% |
   | 1024 | 3M | **4M** | +26.8% | 5M | **5M** | +10.5% | 3M | **4M** | +6.0% |
   | 2048 | 1M | **2M** | +27.3% | 2M | **2M** | +6.3% | 2M | **2M** | +5.5% |
   | 4096 | 709K | **934K** | +31.8% | 1M | **1M** | +10.1% | 802K | **833K** | +3.8% |
   | 16384 | 185K | **232K** | +25.6% | 254K | **262K** | +3.0% | 199K | **197K** | -0.8% |


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@hbase.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] HBASE-29889 Add XXH3 Hash Support to Bloom Filter [hbase]

Posted by "jinhyukify (via GitHub)" <gi...@apache.org>.
jinhyukify commented on code in PR #7740:
URL: https://github.com/apache/hbase/pull/7740#discussion_r2803820955


##########
hbase-common/src/main/java/org/apache/hadoop/hbase/util/XXH3.java:
##########
@@ -0,0 +1,579 @@
+/*
+ * 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.hadoop.hbase.util;
+
+import static java.lang.Integer.toUnsignedLong;
+
+import org.apache.yetus.audience.InterfaceAudience;
+import org.apache.yetus.audience.InterfaceStability;
+
+/**
+ * XXH3 64-bit hash implementation.
+ * <p>
+ * Optimized for modern CPU architectures, providing high throughput, strong dispersion, and minimal
+ * memory usage. Designed for low-latency, zero-allocation hashing in most cases.
+ * <p>
+ * Note, however, that when the input exceeds 240 bytes and a non-default seed (anything other than
+ * {@code 0}) is used, a derived secret must be generated internally, which results in a temporary
+ * byte-array allocation.
+ * @see <a href=
+ *      "https://github.com/Cyan4973/xxHash/blob/dev/doc/xxhash_spec.md#xxh3-algorithm-overview">XXH3
+ *      Algorithm</a>
+ */
+@InterfaceAudience.Private
+@InterfaceStability.Unstable
+public class XXH3 extends Hash implements Hash64 {
+  private static final XXH3 _instance = new XXH3();
+  private static final long MASK32 = 0xFFFFFFFFL;
+  private static final long PRIME32_1 = 0x9E3779B1L;
+  private static final long PRIME32_2 = 0x85EBCA77L;
+  private static final long PRIME32_3 = 0xC2B2AE3DL;
+  private static final long PRIME64_1 = 0x9E3779B185EBCA87L;
+  private static final long PRIME64_2 = 0xC2B2AE3D27D4EB4FL;
+  private static final long PRIME64_3 = 0x165667B19E3779F9L;
+  private static final long PRIME64_4 = 0x85EBCA77C2B2AE63L;
+  private static final long PRIME64_5 = 0x27D4EB2F165667C5L;
+  private static final long PRIME_MX1 = 0x165667919E3779F9L;
+  private static final long PRIME_MX2 = 0x9FB21C651E98DF25L;
+
+  private static final byte[] DEFAULT_SECRET = { (byte) 0xb8, (byte) 0xfe, (byte) 0x6c, (byte) 0x39,
+    (byte) 0x23, (byte) 0xa4, (byte) 0x4b, (byte) 0xbe, (byte) 0x7c, (byte) 0x01, (byte) 0x81,
+    (byte) 0x2c, (byte) 0xf7, (byte) 0x21, (byte) 0xad, (byte) 0x1c, (byte) 0xde, (byte) 0xd4,
+    (byte) 0x6d, (byte) 0xe9, (byte) 0x83, (byte) 0x90, (byte) 0x97, (byte) 0xdb, (byte) 0x72,
+    (byte) 0x40, (byte) 0xa4, (byte) 0xa4, (byte) 0xb7, (byte) 0xb3, (byte) 0x67, (byte) 0x1f,
+    (byte) 0xcb, (byte) 0x79, (byte) 0xe6, (byte) 0x4e, (byte) 0xcc, (byte) 0xc0, (byte) 0xe5,
+    (byte) 0x78, (byte) 0x82, (byte) 0x5a, (byte) 0xd0, (byte) 0x7d, (byte) 0xcc, (byte) 0xff,
+    (byte) 0x72, (byte) 0x21, (byte) 0xb8, (byte) 0x08, (byte) 0x46, (byte) 0x74, (byte) 0xf7,
+    (byte) 0x43, (byte) 0x24, (byte) 0x8e, (byte) 0xe0, (byte) 0x35, (byte) 0x90, (byte) 0xe6,
+    (byte) 0x81, (byte) 0x3a, (byte) 0x26, (byte) 0x4c, (byte) 0x3c, (byte) 0x28, (byte) 0x52,
+    (byte) 0xbb, (byte) 0x91, (byte) 0xc3, (byte) 0x00, (byte) 0xcb, (byte) 0x88, (byte) 0xd0,
+    (byte) 0x65, (byte) 0x8b, (byte) 0x1b, (byte) 0x53, (byte) 0x2e, (byte) 0xa3, (byte) 0x71,
+    (byte) 0x64, (byte) 0x48, (byte) 0x97, (byte) 0xa2, (byte) 0x0d, (byte) 0xf9, (byte) 0x4e,
+    (byte) 0x38, (byte) 0x19, (byte) 0xef, (byte) 0x46, (byte) 0xa9, (byte) 0xde, (byte) 0xac,
+    (byte) 0xd8, (byte) 0xa8, (byte) 0xfa, (byte) 0x76, (byte) 0x3f, (byte) 0xe3, (byte) 0x9c,
+    (byte) 0x34, (byte) 0x3f, (byte) 0xf9, (byte) 0xdc, (byte) 0xbb, (byte) 0xc7, (byte) 0xc7,
+    (byte) 0x0b, (byte) 0x4f, (byte) 0x1d, (byte) 0x8a, (byte) 0x51, (byte) 0xe0, (byte) 0x4b,
+    (byte) 0xcd, (byte) 0xb4, (byte) 0x59, (byte) 0x31, (byte) 0xc8, (byte) 0x9f, (byte) 0x7e,
+    (byte) 0xc9, (byte) 0xd9, (byte) 0x78, (byte) 0x73, (byte) 0x64, (byte) 0xea, (byte) 0xc5,
+    (byte) 0xac, (byte) 0x83, (byte) 0x34, (byte) 0xd3, (byte) 0xeb, (byte) 0xc3, (byte) 0xc5,
+    (byte) 0x81, (byte) 0xa0, (byte) 0xff, (byte) 0xfa, (byte) 0x13, (byte) 0x63, (byte) 0xeb,
+    (byte) 0x17, (byte) 0x0d, (byte) 0xdd, (byte) 0x51, (byte) 0xb7, (byte) 0xf0, (byte) 0xda,
+    (byte) 0x49, (byte) 0xd3, (byte) 0x16, (byte) 0x55, (byte) 0x26, (byte) 0x29, (byte) 0xd4,
+    (byte) 0x68, (byte) 0x9e, (byte) 0x2b, (byte) 0x16, (byte) 0xbe, (byte) 0x58, (byte) 0x7d,
+    (byte) 0x47, (byte) 0xa1, (byte) 0xfc, (byte) 0x8f, (byte) 0xf8, (byte) 0xb8, (byte) 0xd1,
+    (byte) 0x7a, (byte) 0xd0, (byte) 0x31, (byte) 0xce, (byte) 0x45, (byte) 0xcb, (byte) 0x3a,
+    (byte) 0x8f, (byte) 0x95, (byte) 0x16, (byte) 0x04, (byte) 0x28, (byte) 0xaf, (byte) 0xd7,
+    (byte) 0xfb, (byte) 0xca, (byte) 0xbb, (byte) 0x4b, (byte) 0x40, (byte) 0x7e, };
+
+  // Pre-converted longs from DefaultSecret to avoid reconstruction at runtime
+  private static final long DEFAULT_SECRET_LONG_0 = 0xBE4BA423396CFEB8L;
+  private static final long DEFAULT_SECRET_LONG_1 = 0x1CAD21F72C81017CL;
+  private static final long DEFAULT_SECRET_LONG_2 = 0xDB979083E96DD4DEL;
+  private static final long DEFAULT_SECRET_LONG_3 = 0x1F67B3B7A4A44072L;
+  private static final long DEFAULT_SECRET_LONG_4 = 0x78E5C0CC4EE679CBL;
+  private static final long DEFAULT_SECRET_LONG_5 = 0x2172FFCC7DD05A82L;
+  private static final long DEFAULT_SECRET_LONG_6 = 0x8E2443F7744608B8L;
+  private static final long DEFAULT_SECRET_LONG_7 = 0x4C263A81E69035E0L;
+  private static final long DEFAULT_SECRET_LONG_8 = 0xCB00C391BB52283CL;
+  private static final long DEFAULT_SECRET_LONG_9 = 0xA32E531B8B65D088L;
+  private static final long DEFAULT_SECRET_LONG_10 = 0x4EF90DA297486471L;
+  private static final long DEFAULT_SECRET_LONG_11 = 0xD8ACDEA946EF1938L;
+  private static final long DEFAULT_SECRET_LONG_12 = 0x3F349CE33F76FAA8L;
+  private static final long DEFAULT_SECRET_LONG_13 = 0x1D4F0BC7C7BBDCF9L;
+  private static final long DEFAULT_SECRET_LONG_14 = 0x3159B4CD4BE0518AL;
+  private static final long DEFAULT_SECRET_LONG_15 = 0x647378D9C97E9FC8L;
+
+  // Pre-converted longs from DefaultSecret (3-byte offset) to avoid reconstruction at runtime.
+  private static final long DEFAULT_SECRET_3_LONG_0 = 0x81017CBE4BA42339L;
+  private static final long DEFAULT_SECRET_3_LONG_1 = 0x6DD4DE1CAD21F72CL;
+  private static final long DEFAULT_SECRET_3_LONG_2 = 0xA44072DB979083E9L;
+  private static final long DEFAULT_SECRET_3_LONG_3 = 0xE679CB1F67B3B7A4L;
+  private static final long DEFAULT_SECRET_3_LONG_4 = 0xD05A8278E5C0CC4EL;
+  private static final long DEFAULT_SECRET_3_LONG_5 = 0x4608B82172FFCC7DL;
+  private static final long DEFAULT_SECRET_3_LONG_6 = 0x9035E08E2443F774L;
+  private static final long DEFAULT_SECRET_3_LONG_7 = 0x52283C4C263A81E6L;
+  private static final long DEFAULT_SECRET_3_LONG_8 = 0x65D088CB00C391BBL;
+  private static final long DEFAULT_SECRET_3_LONG_9 = 0x486471A32E531B8BL;
+  private static final long DEFAULT_SECRET_3_LONG_10 = 0xEF19384EF90DA297L;
+  private static final long DEFAULT_SECRET_3_LONG_11 = 0x76FAA8D8ACDEA946L;
+  private static final long DEFAULT_SECRET_3_LONG_12 = 0xBBDCF93F349CE33FL;
+  private static final long DEFAULT_SECRET_3_LONG_13 = 0xE0518A1D4F0BC7C7L;
+
+  private static final long DEFAULT_SECRET_LONG_119 = 0x7378D9C97E9FC831L;
+  private static final long DEFAULT_SECRET_LONG_127 = 0xEBD33483ACC5EA64L;
+
+  private static final long DEFAULT_SECRET_BITFLIP_0 =
+    ((DEFAULT_SECRET_LONG_0 >>> 32) ^ (DEFAULT_SECRET_LONG_0 & MASK32));
+  private static final long DEFAULT_SECRET_BITFLIP_1 =
+    (DEFAULT_SECRET_LONG_1 ^ DEFAULT_SECRET_LONG_2);
+  private static final long DEFAULT_SECRET_BITFLIP_2 =
+    (DEFAULT_SECRET_LONG_3 ^ DEFAULT_SECRET_LONG_4);
+  private static final long DEFAULT_SECRET_BITFLIP_3 =
+    (DEFAULT_SECRET_LONG_5 ^ DEFAULT_SECRET_LONG_6);
+  private static final long DEFAULT_SECRET_BITFLIP_4 =
+    (DEFAULT_SECRET_LONG_7 ^ DEFAULT_SECRET_LONG_8);
+
+  public static Hash getInstance() {
+    return _instance;
+  }
+
+  @Override
+  public <T> long hash64(HashKey<T> hashKey, long seed) {
+    int length = hashKey.length();
+    long result64;
+
+    if (length <= 16) {
+      result64 = hashSmall(hashKey, length, seed);
+    } else if (length <= 240) {
+      result64 = hashMedium(hashKey, length, seed);
+    } else {
+      result64 = hashLarge(hashKey, length, seed);
+    }
+
+    return result64;
+  }
+
+  @Override
+  public <T> int hash(HashKey<T> hashKey, int seed) {
+    long result64 = hash64(hashKey, (long) seed);
+    return toLow32Int(result64);
+  }
+
+  private byte[] initSecret(long seed) {
+    if (seed == 0L) {
+      return DEFAULT_SECRET;
+    } else {
+      // For non-default seeds, derived secret generation requires a new byte array.
+      byte[] derivedSecret = new byte[192];
+      for (int i = 0; i < 12; i++) {
+        putLong64LE(derivedSecret, i * 16, readLong64LE(DEFAULT_SECRET, i * 16) + seed);
+        putLong64LE(derivedSecret, i * 16 + 8, readLong64LE(DEFAULT_SECRET, i * 16 + 8) - seed);
+      }
+      return derivedSecret;
+    }
+  }
+
+  private static int toLow32Int(long value) {
+    // Grab only the lower 32 bits.
+    return (int) value;
+  }
+
+  private static long avalanche(long hash) {
+    hash ^= hash >>> 37;
+    hash *= PRIME_MX1;
+    hash ^= hash >>> 32;
+    return hash;
+  }
+
+  private static long avalancheXXH64(long hash) {
+    hash ^= hash >>> 33;
+    hash *= PRIME64_2;
+    hash ^= hash >>> 29;
+    hash *= PRIME64_3;
+    hash ^= hash >>> 32;
+    return hash;
+  }
+
+  private static long rrmxmx(long hash, int inputLength) {
+    hash ^= Long.rotateLeft(hash, 49) ^ Long.rotateLeft(hash, 24);
+    hash *= PRIME_MX2;
+    hash ^= (hash >>> 35) + inputLength;
+    hash *= PRIME_MX2;
+    hash ^= hash >>> 28;
+    return hash;
+  }
+
+  private static long mul128AndFold64(long x, long y) {
+    // Consider switching to Math.unsignedMultiplyHigh(x, y) when we can drop Java 8.

Review Comment:
   https://github.com/openjdk/jdk/blob/jdk-21%2B35/src/java.base/share/classes/java/lang/Math.java#L1399-L1414
   Using `Math.multiplyHigh`(>= jdk 9) or `Math.unsignedMultiplyHigh` (>= jdk 18) showed better benchmark performance because the JIT compiler replaces them with optimized CPU instructions (intrinsics).



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@hbase.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] HBASE-29889 Add XXH3 Hash Support to Bloom Filter [hbase]

Posted by "jinhyukify (via GitHub)" <gi...@apache.org>.
jinhyukify commented on code in PR #7740:
URL: https://github.com/apache/hbase/pull/7740#discussion_r2796378497


##########
hbase-common/src/main/java/org/apache/hadoop/hbase/util/XXH3.java:
##########
@@ -0,0 +1,557 @@
+/*
+ * 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.hadoop.hbase.util;
+
+import static java.lang.Integer.toUnsignedLong;
+
+import org.apache.yetus.audience.InterfaceAudience;
+import org.apache.yetus.audience.InterfaceStability;
+
+/**
+ * XXH3 64-bit hash implementation.
+ * <p>
+ * Optimized for modern CPU architectures, providing high throughput, strong dispersion, and minimal
+ * memory usage. Designed for low-latency, zero-allocation hashing in most cases.
+ * <p>
+ * Note, however, that when the input exceeds 240 bytes and a non-default seed (anything other than
+ * {@code 0}) is used, a derived secret must be generated internally, which results in a temporary
+ * byte-array allocation.
+ * @see <a href=
+ *      "https://github.com/Cyan4973/xxHash/blob/dev/doc/xxhash_spec.md#xxh3-algorithm-overview">XXH3
+ *      Algorithm</a>
+ */
+@InterfaceAudience.Private
+@InterfaceStability.Unstable
+public class XXH3 extends Hash implements Hash64 {

Review Comment:
   I mostly followed the algorithm as described here
   [xxh3-algorithm-overview](https://github.com/Cyan4973/xxHash/blob/dev/doc/xxhash_spec.md#xxh3-algorithm-overview)
   
   Also referenced the original implementation.
   https://xxhash.com/doc/v0.8.2/xxhash_8h_source.html



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@hbase.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org