kszucs commented on code in PR #45360: URL: https://github.com/apache/arrow/pull/45360#discussion_r1992220062
########## cpp/src/parquet/chunker_internal.cc: ########## @@ -0,0 +1,319 @@ +// 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. + +#include "parquet/chunker_internal.h" + +#include <cmath> +#include <string> +#include <vector> +#include "arrow/array.h" +#include "arrow/util/logging.h" +#include "parquet/chunker_internal_generated.h" +#include "parquet/exception.h" +#include "parquet/level_conversion.h" + +namespace parquet::internal { + +/// Calculate the mask to use for the rolling hash, the mask is used to determine if a +/// new chunk should be created based on the rolling hash value. The mask is calculated +/// based on the min_size, max_size and norm_factor parameters. +/// +/// Assuming that the gear hash hash random values with a uniform distribution, then each +/// bit in the actual value of rolling_hash_ has even probability of being set so a mask +/// with the top N bits set has a probability of 1/2^N of matching the rolling hash. This +/// is the judgment criteria for the original gear hash based content-defined chunking. +/// The main drawback of this approach is the non-uniform distribution of the chunk sizes. +/// +/// Later on the FastCDC has improved the process by introducing: +/// - sub-minimum chunk cut-point skipping (not hashing the first `min_size` bytes) +/// - chunk size normalization (using two masks) +/// +/// This implementation uses cut-point skipping because it improves the overall +/// performance and a more accurate alternative to have less skewed chunk size +/// distribution. Instead of using two different masks (one with a lower and one with a +/// probability of matching and switching them based on the actual chunk size), we rather +/// use 8 different gear hash tables and require having 8 consecutive matches while +/// switching between the used hashtables. This approach is based on central limit theorem +/// and approximates normal distribution of the chunk sizes. +// +// @param min_size The minimum chunk size (default 256KiB) +// @param max_size The maximum chunk size (default 1MiB) +// @param norm_factor Normalization factor (default 0) +// @return The mask used to compare against the rolling hash +static uint64_t GetMask(int64_t min_size, int64_t max_size, uint8_t norm_factor) { + // calculate the average size of the chunks + int64_t avg_size = (min_size + max_size) / 2; + // since we are skipping the first `min_size` bytes for each chunk, we need to + // target a smaller chunk size to reach the average size after skipping the first + // `min_size` bytes + int64_t target_size = avg_size - min_size; + // assuming that the gear hash has a uniform distribution, we can calculate the mask + // by taking the log2 of the target size + size_t mask_bits = static_cast<size_t>(std::floor(std::log2(target_size))); Review Comment: Sure, updating. -- 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: github-unsubscr...@arrow.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org
