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> + */ [email protected] [email protected] +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> + */ [email protected] [email protected] +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. + */ [email protected] [email protected] +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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
