xiangfu0 commented on code in PR #19795: URL: https://github.com/apache/pinot/pull/19795#discussion_r4227829254
########## compatibility-verifier/tdigest-compatibility/run.sh: ########## @@ -0,0 +1,38 @@ +#!/usr/bin/env bash +# +# 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. +# + +# Run after LegacyTDigestCompatibilityTest. Legacy jars are test-tool artifacts, not Pinot dependencies. +set -euo pipefail +TDIGEST_ROOT="$(cd "$(dirname "${BASH_SOURCE[0]}")/../.." && pwd)" +TDIGEST_FIXTURES="$TDIGEST_ROOT/pinot-segment-local/target/tdigest-compat-fixtures" +TDIGEST_WORK="$TDIGEST_ROOT/pinot-segment-local/target/tdigest-legacy-reader" +test -s "$TDIGEST_FIXTURES/manifest.tsv" +mkdir -p "$TDIGEST_WORK" +for TDIGEST_VERSION in 3.2 3.3; do + "$TDIGEST_ROOT/mvnw" -f "$TDIGEST_ROOT/pom.xml" -N -B -ntp \ Review Comment: Fixed in [d27edc192f](https://github.com/apache/pinot/commit/d27edc192f9440dd7bd2c15a56d44cb1e250a84f). Both standalone scripts preserve caller MAVEN_OPTS and append the workflow retry/TTL/keep-alive/pool properties. Pinned 3.2/3.3 jar copies are reused through the existing Maven cache, and the oracle reuses the same 3.3 copy; immutable baseline fetch has bounded retries. Seven shell harness cases verify cache hits, retry exhaustion and exact nonzero propagation from Maven/compile/reader failures; the actual 78-reader and 270-oracle gates pass. ########## pinot-segment-local/src/main/java/org/apache/pinot/segment/local/customobject/PercentileTDigestAccumulator.java: ########## @@ -0,0 +1,1687 @@ +/** + * 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.pinot.segment.local.customobject; + +import java.nio.ByteBuffer; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collection; +import java.util.List; +import org.apache.pinot.segment.local.utils.TDigestUtils; +import org.apache.pinot.segment.local.utils.TDigestUtils.SerializedTDigestMetadata; +import org.apache.pinot.segment.spi.customobject.TDigest; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + + +/// Accumulates raw values and serialized TDigests into primitive centroids using Pinot's K1 weight-limit rule. +/// +/// Raw values are sorted in small batches; serialized centroids retain their existing sorted order. Both are +/// linearly merged with accumulated centroids. K1 preserves Pinot's existing middle-quantile behavior, and the +/// legacy verbose and small encodings preserve stored data and mixed-version wire compatibility. +/// +/// Serialized state keeps its first digest pending and allocates centroid buffers only when another input must be +/// merged or the digest is queried. Raw-value buffers remain unallocated until a raw value is added. +/// +/// Historical corrupted payloads remain opaque and byte-exact, with NaN statistics. Their reported historical mass +/// may be invalid; they cannot be mutated or mixed with another distribution. Such an operation fails before +/// changing aggregate mass, because neither invented statistics nor synthetic NaN bytes are safe for old readers. +/// +/// Instances are externally serialized per aggregation or group key and are not safe for concurrent mutation. +public final class PercentileTDigestAccumulator extends TDigest { + private static final Logger LOGGER = LoggerFactory.getLogger(PercentileTDigestAccumulator.class); + private static final int MIN_RAW_BUFFER_SIZE = 256; + private static final int MAX_RAW_BUFFER_SIZE = 10_000; + private static final int MIN_COMPRESSION = 10; + private static final int TWO_LEVEL_COMPRESSION_MULTIPLIER = 2; + private static final int MIN_INCREMENTAL_COMPRESSION = 50; + + private final double _compression; + private final boolean _useTwoLevelRawCompression; + private final double _workingCompression; + private final double _publicMaxWeightScale; + private final double _workingMaxWeightScale; + private final int _centroidCapacity; + private final int _pendingCentroidCapacity; + private double[] _rawValues; + private double[] _centroidMeans; + private double[] _centroidWeights; + private double[] _outputMeans; + private double[] _outputWeights; + private double[] _incomingMeans; + private double[] _incomingWeights; + private double[] _sortedIncomingMeans; + private double[] _sortedIncomingWeights; + private SerializedTDigestInput _serializedTDigestInput; + private byte[] _pendingSerializedTDigest; + private byte[] _originalFractionalBytes; + private SerializedTDigestMetadata _pendingSerializedMetadata; + private boolean _legacyDegraded; + private byte[] _serializedBytesForWrite; + private boolean _hasFractionalWeights; + + private int _numRawValues; + private int _numCentroids; + private int _numIncomingCentroids; + private int _serializedMainCapacity; + private int _serializedBufferCapacity; + private int _mergeCount; + private boolean _publiclyCompressed; + private boolean _incomingCentroidsSorted = true; + private double _totalWeight; + private double _incomingWeight; + private double _min = Double.POSITIVE_INFINITY; + private double _max = Double.NEGATIVE_INFINITY; + + public PercentileTDigestAccumulator(int compression) { + this(positiveCompression(compression), true, true); + } + + public PercentileTDigestAccumulator(double compression) { + this(compression, true, true); + } + + private PercentileTDigestAccumulator(double compression, boolean allocateRawBuffer, boolean allocateMergeBuffers) { + this(compression, allocateRawBuffer, allocateMergeBuffers, false); + } + + private PercentileTDigestAccumulator(double compression, boolean allocateRawBuffer, boolean allocateMergeBuffers, + boolean useTwoLevelRawCompression) { + TDigestUtils.validateCompression(compression); + _useTwoLevelRawCompression = useTwoLevelRawCompression; + _compression = Math.max(MIN_COMPRESSION, compression); + _workingCompression = TWO_LEVEL_COMPRESSION_MULTIPLIER * _compression; + _publicMaxWeightScale = calculateK1MaxWeightScale(_compression); + _workingMaxWeightScale = calculateK1MaxWeightScale(_workingCompression); + long roundedCompression = (long) Math.ceil(_compression); + _centroidCapacity = TDigestUtils.getDefaultCentroidCapacity(_compression); + _pendingCentroidCapacity = getPendingCentroidCapacity(_centroidCapacity); + if (allocateRawBuffer) { + _rawValues = new double[getRawBufferSize(roundedCompression)]; + } + if (allocateMergeBuffers) { + int initialCapacity = Math.min(_centroidCapacity, MIN_RAW_BUFFER_SIZE); + _centroidMeans = new double[initialCapacity]; + _centroidWeights = new double[initialCapacity]; + _outputMeans = new double[initialCapacity]; + _outputWeights = new double[initialCapacity]; + } + } + + /// Creates a lazy digest with the legacy two-level compression used by Star-tree and general digest aggregation. + public static PercentileTDigestAccumulator forLegacyAggregation(double compression) { + return new PercentileTDigestAccumulator(compression, false, false, true); + } + + public static PercentileTDigestAccumulator forSerializedTDigest(byte[] bytes) { + return new PercentileTDigestAccumulator(readCompression(bytes), false, false); + } + + public static PercentileTDigestAccumulator forSerializedTDigest(SerializedTDigestInput input) { + return new PercentileTDigestAccumulator(input._compression, false, false); + } + + public static PercentileTDigestAccumulator forSerializedTDigestWithMergeBuffers(byte[] bytes) { + return new PercentileTDigestAccumulator(readCompression(bytes), false, true); + } + + public static PercentileTDigestAccumulator forSerializedTDigest(ByteBuffer input) { + SerializedTDigestInput serialized = new SerializedTDigestInput(); + serialized.reset(input); + PercentileTDigestAccumulator accumulator = forSerializedTDigest(serialized); + accumulator.addSerializedTDigest(serialized); + return accumulator; + } + + public static PercentileTDigestAccumulator forReduction(double compression) { + return new PercentileTDigestAccumulator(positiveCompression(compression), false, false); + } + + /// Copies primitive centroids without encoding and decoding them. Zero weights are ignored, and unordered + /// means are sorted when initializing a stored, already compressed distribution; caller arrays are not mutated. + /// Subsequent inputs use the normal buffered merge. Positive weights and consistent extrema are required. + public void addCentroids(double[] means, double[] weights, int count, double min, double max, + boolean alreadyCompressed) { + requireMutable(); + if (count < 0 || count > means.length || count > weights.length) { + throw new IllegalArgumentException("Invalid TDigest centroid count: " + count); + } + double totalWeight = 0.0; + int positiveCount = 0; + boolean sorted = true; + boolean fractionalWeights = false; + double previousMean = Double.NEGATIVE_INFINITY; + for (int i = 0; i < count; i++) { + double weight = weights[i]; + if (weight == 0.0) { + continue; + } + double mean = means[i]; + if (!(weight > 0.0) || !Double.isFinite(weight) || !(mean >= min && mean <= max)) { + throw new IllegalArgumentException("Invalid TDigest centroid"); + } + totalWeight += weight; + sorted &= mean >= previousMean; + previousMean = mean; + fractionalWeights |= weight != Math.rint(weight); + positiveCount++; + } + checkTotalWeight(getTotalWeight() + totalWeight); + if (positiveCount == 0) { + return; + } + materializePendingSerializedTDigest(); + _originalFractionalBytes = null; + _hasFractionalWeights |= fractionalWeights; + if (hasNoInputs() && alreadyCompressed) { + ensureCentroidCapacity(Math.addExact(positiveCount, 2)); + for (int i = 0; i < count; i++) { + if (weights[i] > 0.0) { + _centroidMeans[_numCentroids] = means[i]; + _centroidWeights[_numCentroids++] = weights[i]; + } + } + if (!sorted) { + it.unimi.dsi.fastutil.Arrays.mergeSort(0, _numCentroids, + (first, second) -> Double.compare(_centroidMeans[first], _centroidMeans[second]), + (first, second) -> { + double mean = _centroidMeans[first]; + _centroidMeans[first] = _centroidMeans[second]; + _centroidMeans[second] = mean; + double weight = _centroidWeights[first]; + _centroidWeights[first] = _centroidWeights[second]; + _centroidWeights[second] = weight; + }); + } + _totalWeight = totalWeight; + _min = min; + _max = max; + normalizeBoundaryCentroids(); + _publiclyCompressed = true; + } else { + for (int i = 0; i < count; i++) { + if (weights[i] > 0.0) { + bufferIncomingCentroid(means[i], weights[i]); + } + } + _min = Math.min(_min, min); + _max = Math.max(_max, max); + } + } + + public void add(double[] values, int from, int toExclusive) { + if (from >= toExclusive) { + return; + } + requireMutable(); + materializePendingSerializedTDigest(); + ensureRawBuffer(); + while (from < toExclusive) { + if (_numRawValues == _rawValues.length + || _numRawValues + _numIncomingCentroids == getPendingInputLimit()) { + flush(); + } + int numValues = Math.min(toExclusive - from, Math.min(_rawValues.length - _numRawValues, + getPendingInputLimit() - _numRawValues - _numIncomingCentroids)); + int rawOffset = _numRawValues; + for (int i = 0; i < numValues; i++) { + double value = values[from + i]; + if (Double.isNaN(value)) { + throw new IllegalArgumentException("Cannot add NaN to t-digest"); + } + _rawValues[rawOffset + i] = value; + } + _originalFractionalBytes = null; + from += numValues; + _numRawValues += numValues; + if (_numRawValues == _rawValues.length + || _numRawValues + _numIncomingCentroids == getPendingInputLimit()) { + flush(); + } + } + } + + @Override + public void add(double value) { + if (Double.isNaN(value)) { + throw new IllegalArgumentException("Cannot add NaN to t-digest"); + } + requireMutable(); + materializePendingSerializedTDigest(); + ensureRawBuffer(); + if (_numRawValues == _rawValues.length + || _numRawValues + _numIncomingCentroids == getPendingInputLimit()) { + flush(); + } + _originalFractionalBytes = null; + _rawValues[_numRawValues++] = value; + } + + @Override + public void add(double value, double weight) { + if (weight == 1) { + add(value); + return; + } + if (Double.isNaN(value)) { + throw new IllegalArgumentException("Cannot add NaN to t-digest"); + } + if (!(weight > 0.0) || !Double.isFinite(weight)) { + throw new IllegalArgumentException("TDigest weight must be positive: " + weight); + } + requireMutable(); + materializePendingSerializedTDigest(); + bufferIncomingCentroid(value, weight); + _originalFractionalBytes = null; + _hasFractionalWeights |= weight != Math.rint(weight); + _min = Math.min(_min, value); + _max = Math.max(_max, value); + } + + @Override + public void add(TDigest other) { + requireMutable(); + if (other instanceof PercentileTDigestAccumulator) { + addAccumulator((PercentileTDigestAccumulator) other); + return; + } + if (!other.hasValidStatistics()) { + materializePendingSerializedTDigest(); + SerializedTDigestInput input = getSerializedTDigestInput(); + input.reset(ByteBuffer.wrap(TDigestUtils.serialize(other)), false); + addSerializedTDigest(input); + return; + } + materializePendingSerializedTDigest(); + double otherWeight = other.getTotalWeight(); + checkTotalWeight(_totalWeight + _incomingWeight + _numRawValues + otherWeight); + for (Centroid centroid : other.centroids()) { + double weight = centroid.weight(); + if (weight == 0.0) { + continue; + } + if (!(weight > 0.0) || !Double.isFinite(weight) || Double.isNaN(centroid.mean())) { + throw new IllegalArgumentException("Invalid TDigest centroid"); + } + _hasFractionalWeights |= weight != Math.rint(weight); + bufferIncomingCentroid(centroid.mean(), weight); + _originalFractionalBytes = null; + } + if (otherWeight != 0.0) { + _min = Math.min(_min, other.getMin()); + _max = Math.max(_max, other.getMax()); + } + } + + @Override + public void add(List<? extends TDigest> others) { + for (TDigest other : others) { + add(other); + } + } + + private void addAccumulator(PercentileTDigestAccumulator other) { + if (other == this) { + compress(); + if (_numCentroids == 0) { + return; + } + // Snapshot only self-merges; fresh fractional mass need not be representable by a legacy wire payload. + addCentroids(Arrays.copyOf(_centroidMeans, _numCentroids), Arrays.copyOf(_centroidWeights, _numCentroids), + _numCentroids, _min, _max, false); + return; + } + if (other._originalFractionalBytes != null && _compression == other._compression && getTotalWeight() == 0.0) { + materializePendingSerializedTDigest(); + SerializedTDigestInput input = getSerializedTDigestInput(); + input.reset(other._originalFractionalBytes); + input._retainedBytes = other._originalFractionalBytes; + addSerializedTDigest(input); + return; + } + if (other._pendingSerializedTDigest != null) { + // Materialize before resetting the reusable reader: materialization uses that same reader. + materializePendingSerializedTDigest(); + SerializedTDigestInput input = getSerializedTDigestInput(); + input.reset(other._pendingSerializedTDigest, other._pendingSerializedMetadata); + input._retainedBytes = other._pendingSerializedTDigest; + addSerializedTDigest(input); + return; + } + if (other._legacyDegraded) { + addSerializedTDigest(other.serialize()); + return; + } + + // MergingDigest compressed merge sources in place. Aggregation owns these mutable inputs exclusively. + other.compress(); + materializePendingSerializedTDigest(); + checkTotalWeight(_totalWeight + _incomingWeight + _numRawValues + other._totalWeight); + _hasFractionalWeights |= other._hasFractionalWeights; + preserveSerializedCapacity(other._serializedMainCapacity, other._serializedBufferCapacity); + bufferIncomingCentroids(other._centroidMeans, other._centroidWeights, other._numCentroids); + if (other._totalWeight > 0.0) { + _originalFractionalBytes = null; + } + _min = Math.min(_min, other._min); + _max = Math.max(_max, other._max); + } + + public void addSerializedTDigest(byte[] bytes) { + requireMutable(); + materializePendingSerializedTDigest(); + SerializedTDigestInput input = getSerializedTDigestInput(); + input.reset(bytes); + addSerializedTDigest(input); + } + + private SerializedTDigestInput getSerializedTDigestInput() { + if (_serializedTDigestInput == null) { + _serializedTDigestInput = new SerializedTDigestInput(); + } + return _serializedTDigestInput; + } + + public void addSerializedTDigest(SerializedTDigestInput input) { + requireMutable(); + if (prepareSerializedTDigest(input)) { + mergeSerializedTDigest(input, false); + } + } + + public void addSerializedTDigestDirect(SerializedTDigestInput input) { + requireMutable(); + if (prepareSerializedTDigest(input)) { + mergeSerializedTDigest(input, true); + } + } + + private boolean prepareSerializedTDigest(SerializedTDigestInput input) { + if (_pendingSerializedTDigest == null && hasNoInputs()) { + input.inspectMetadata(); + _hasFractionalWeights |= input._metadata.fractionalWeights(); + _pendingSerializedTDigest = input.retainBytes(); + _pendingSerializedMetadata = input._metadata; + if (input.hasUnrepresentableBoundaryMass() && _compression == input._compression) { + // Alias the retained snapshot; historical fractional bytes remain byte-exact after read-only materialization. + _originalFractionalBytes = _pendingSerializedTDigest; + } + if (input._metadata.needsLegacyFallback()) { + markLegacyDegraded(input); + } + return false; + } + materializePendingSerializedTDigest(); + input.decode(); + if (input._metadata.needsLegacyFallback()) { + if (hasNoInputs()) { + _pendingSerializedTDigest = input.retainBytes(); + _pendingSerializedMetadata = input._metadata; + markLegacyDegraded(input); + return false; + } + throw corruptedMutation(); + } + checkTotalWeight(_totalWeight + _incomingWeight + _numRawValues + input._totalWeight); + if (input._totalWeight > 0.0) { + _originalFractionalBytes = null; + } + _hasFractionalWeights |= input._metadata.fractionalWeights(); + return true; + } + + private boolean hasNoInputs() { + return _numCentroids == 0 && _totalWeight == 0.0 && _numRawValues == 0 && _numIncomingCentroids == 0; + } + + private void mergeSerializedTDigest(SerializedTDigestInput input, boolean direct) { + if (input._totalWeight == 0.0) { + return; + } + preserveSerializedCapacity(input._mainCapacity, input._bufferCapacity); + if (hasNoInputs()) { + if (input._totalWeight != 0.0) { + ensureCentroidCapacity(input._numCentroids); + System.arraycopy(input._means, 0, _centroidMeans, 0, input._numCentroids); + System.arraycopy(input._weights, 0, _centroidWeights, 0, input._numCentroids); + _numCentroids = input._numCentroids; + _totalWeight = input._totalWeight; + _min = input._min; + _max = input._max; + // Stored centroids already went through the writer's public compression. Reading or repairing their + // endpoints needs another K1 pass only when the output compression differs from the stored compression. + _publiclyCompressed = _compression == input._compression; + } + return; + } + if (direct) { + flush(); + boolean runBackwards = (_mergeCount++ & 1) != 0; + if (!mergeSorted(input._means, input._weights, input._numCentroids, input._totalWeight, + getIncrementalCompression(), runBackwards)) { + return; + } + } else { + bufferIncomingCentroids(input._means, input._weights, input._numCentroids); + } + _min = Math.min(_min, input._min); + _max = Math.max(_max, input._max); + } + + @Override + public void compress() { + if (_legacyDegraded) { + return; + } + if (_pendingSerializedTDigest != null || _numRawValues > 0 || _numIncomingCentroids > 0 + || !_publiclyCompressed && _numCentroids > 0) { + _serializedBytesForWrite = null; + } + materializePendingSerializedTDigest(); + if (_numRawValues > 0 || _numIncomingCentroids > 0) { + // MergingDigest 3.3 combines pending values and existing centroids directly at public compression. Flushing at + // working compression first would add an extra lossy merge pass and materially increase reducer rank error. + flush(_compression); + _publiclyCompressed = true; + } else if (!_publiclyCompressed && _numCentroids > 0) { + recompressCentroids(_compression); + _publiclyCompressed = true; + } + } + + @Override + public long size() { + return (long) getTotalWeight(); + } + + @Override + public boolean hasValidStatistics() { + return !_legacyDegraded; + } + + @Override + public double getTotalWeight() { + return _pendingSerializedTDigest != null ? _pendingSerializedMetadata.totalWeight() + : _totalWeight + _incomingWeight + _numRawValues; + } + + /// Bounds serialized output centroids from buffered inputs, including up to two boundary splits before a merge + /// and two more before writing, without flushing or using the potentially huge input mass. + public long getCentroidCountUpperBound() { + return _pendingSerializedTDigest != null ? (long) _pendingSerializedMetadata.centroidCount() + 4L + : (long) _numCentroids + _numRawValues + _numIncomingCentroids + 4L; + } + + /// Whether fractional input weights invalidate the usual bound of one centroid per unit of mass. + public boolean hasFractionalWeights() { Review Comment: Fixed in [d27edc192f](https://github.com/apache/pinot/commit/d27edc192f9440dd7bd2c15a56d44cb1e250a84f). Removed the unused public hasFractionalWeights() accessor; its private serialization-bound heuristic remains internal. ########## pinot-segment-local/src/main/java/org/apache/pinot/segment/local/customobject/TDigest.java: ########## @@ -0,0 +1,142 @@ +/** + * 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.pinot.segment.spi.customobject; + +import java.nio.ByteBuffer; +import java.util.Collection; +import java.util.List; + +/// Mutable percentile digest contract for aggregation plugins and legacy t-digest byte encodings. +/// Implementations are not thread-safe; callers must serialize access to each aggregation state. +/// Historical corrupted payloads may be retained unchanged, but cannot be mutated or mixed with healthy state. Review Comment: Fixed in [d27edc192f](https://github.com/apache/pinot/commit/d27edc192f9440dd7bd2c15a56d44cb1e250a84f). Moved TDigest next to QuantileDigest in segment.local.customobject and updated all 31 consumer imports. No segment-spi code needs this type, and the consumers already depend on segment-local, so this avoids adding an unnecessary SPI contract. The shared native/wrapper base and legacy wire encoding remain intact; the migration notes show the new import and creation/add/serialization usage. -- 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] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
