OwnedObjectSizeEstimator.java
// 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.doris.datasource.metacache;
import org.apache.doris.analysis.LiteralExpr;
import org.apache.doris.analysis.MaxLiteral;
import org.apache.doris.catalog.ListPartitionItem;
import org.apache.doris.catalog.PartitionKey;
import org.apache.doris.catalog.RangePartitionItem;
import org.apache.doris.catalog.ScalarType;
import org.apache.doris.catalog.Type;
import org.apache.doris.nereids.trees.expressions.literal.Literal;
import java.lang.reflect.Array;
import java.lang.reflect.Field;
import java.lang.reflect.Modifier;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.nio.ByteBuffer;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collection;
import java.util.Deque;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.Set;
import java.util.concurrent.TimeUnit;
/**
* Full, identity-deduplicated traversal for owned Doris cache value graphs.
*
* <p>JDK containers use public collection APIs and explicit layout formulas, so
* this walker never needs module opens. An inaccessible non-JDK owned field makes
* the result incomplete instead of silently contributing zero. Unknown mutable ArrayLists
* are rejected because their retained capacity is not exposed by a public API. The dedicated
* Hive partition adapters conservatively model lists created by the connector's known path;
* cache publishers freeze all other owned lists before estimation.
*/
public final class OwnedObjectSizeEstimator {
private static final long LEGACY_LITERAL_HEADROOM_BYTES = 1024L;
private static final long NEREIDS_LITERAL_HEADROOM_BYTES = 2048L;
// These are hard safety ceilings, not sampling limits. Production-sized Hive partition graphs
// are still traversed exactly; an object is rejected if exact traversal cannot finish safely.
static final int DEFAULT_MAX_OBJECTS = 5_000_000;
static final int DEFAULT_MAX_DEPTH = 128;
static final long DEFAULT_TIMEOUT_NANOS = TimeUnit.SECONDS.toNanos(5);
private static final int DEADLINE_CHECK_INTERVAL = 256;
private static final Set<String> SUPPORTED_LEGACY_LITERAL_TYPES = new HashSet<>(Arrays.asList(
"org.apache.doris.analysis.BoolLiteral",
"org.apache.doris.analysis.DateLiteral",
"org.apache.doris.analysis.DecimalLiteral",
"org.apache.doris.analysis.FloatLiteral",
"org.apache.doris.analysis.IPv4Literal",
"org.apache.doris.analysis.IPv6Literal",
"org.apache.doris.analysis.IntLiteral",
"org.apache.doris.analysis.JsonLiteral",
"org.apache.doris.analysis.LargeIntLiteral",
"org.apache.doris.analysis.MaxLiteral",
"org.apache.doris.analysis.NullLiteral",
"org.apache.doris.analysis.StringLiteral",
"org.apache.doris.analysis.TimeV2Literal",
"org.apache.doris.analysis.VarBinaryLiteral"));
private static final Set<String> SUPPORTED_NEREIDS_LITERAL_TYPES = new HashSet<>(Arrays.asList(
"org.apache.doris.nereids.trees.expressions.literal.BigIntLiteral",
"org.apache.doris.nereids.trees.expressions.literal.BooleanLiteral",
"org.apache.doris.nereids.trees.expressions.literal.CharLiteral",
"org.apache.doris.nereids.trees.expressions.literal.DateLiteral",
"org.apache.doris.nereids.trees.expressions.literal.DateTimeLiteral",
"org.apache.doris.nereids.trees.expressions.literal.DateTimeV2Literal",
"org.apache.doris.nereids.trees.expressions.literal.DateV2Literal",
"org.apache.doris.nereids.trees.expressions.literal.DecimalLiteral",
"org.apache.doris.nereids.trees.expressions.literal.DecimalV3Literal",
"org.apache.doris.nereids.trees.expressions.literal.DoubleLiteral",
"org.apache.doris.nereids.trees.expressions.literal.FloatLiteral",
"org.apache.doris.nereids.trees.expressions.literal.IPv4Literal",
"org.apache.doris.nereids.trees.expressions.literal.IPv6Literal",
"org.apache.doris.nereids.trees.expressions.literal.IntegerLiteral",
"org.apache.doris.nereids.trees.expressions.literal.JsonLiteral",
"org.apache.doris.nereids.trees.expressions.literal.LargeIntLiteral",
"org.apache.doris.nereids.trees.expressions.literal.MaxLiteral",
"org.apache.doris.nereids.trees.expressions.literal.NullLiteral",
"org.apache.doris.nereids.trees.expressions.literal.SmallIntLiteral",
"org.apache.doris.nereids.trees.expressions.literal.StringLiteral",
"org.apache.doris.nereids.trees.expressions.literal.TimeV2Literal",
"org.apache.doris.nereids.trees.expressions.literal.TimestampTzLiteral",
"org.apache.doris.nereids.trees.expressions.literal.TinyIntLiteral",
"org.apache.doris.nereids.trees.expressions.literal.VarBinaryLiteral",
"org.apache.doris.nereids.trees.expressions.literal.VarcharLiteral"));
private static final Set<String> SHARED_BOUNDARY_TYPE_NAMES = new LinkedHashSet<>();
static {
SHARED_BOUNDARY_TYPE_NAMES.add("java.util.concurrent.Executor");
SHARED_BOUNDARY_TYPE_NAMES.add("java.util.concurrent.ExecutorService");
SHARED_BOUNDARY_TYPE_NAMES.add("javax.sql.DataSource");
SHARED_BOUNDARY_TYPE_NAMES.add("org.apache.doris.common.security.authentication.HadoopAuthenticator");
SHARED_BOUNDARY_TYPE_NAMES.add("org.apache.doris.datasource.CatalogIf");
SHARED_BOUNDARY_TYPE_NAMES.add("org.apache.hadoop.conf.Configuration");
SHARED_BOUNDARY_TYPE_NAMES.add("org.apache.hadoop.fs.FileSystem");
SHARED_BOUNDARY_TYPE_NAMES.add("org.apache.hadoop.hive.metastore.IMetaStoreClient");
SHARED_BOUNDARY_TYPE_NAMES.add("org.apache.iceberg.catalog.Catalog");
SHARED_BOUNDARY_TYPE_NAMES.add("org.apache.iceberg.io.FileIO");
SHARED_BOUNDARY_TYPE_NAMES.add("org.apache.iceberg.Table");
SHARED_BOUNDARY_TYPE_NAMES.add("org.apache.paimon.catalog.Catalog");
SHARED_BOUNDARY_TYPE_NAMES.add("org.apache.paimon.fs.FileIO");
SHARED_BOUNDARY_TYPE_NAMES.add("org.apache.paimon.table.Table");
}
private static final ClassValue<Boolean> SHARED_BOUNDARY_TYPES = new ClassValue<Boolean>() {
@Override
protected Boolean computeValue(Class<?> type) {
return isNamedBoundaryType(type);
}
};
private static final ClassValue<ClassPlan> CLASS_PLANS = new ClassValue<ClassPlan>() {
@Override
protected ClassPlan computeValue(Class<?> type) {
List<Field> referenceFields = new ArrayList<>();
for (Class<?> current = type; current != null; current = current.getSuperclass()) {
for (Field field : current.getDeclaredFields()) {
if (Modifier.isStatic(field.getModifiers()) || field.getType().isPrimitive()) {
continue;
}
try {
if (!field.isAccessible()) {
field.setAccessible(true);
}
referenceFields.add(field);
} catch (RuntimeException e) {
return ClassPlan.inaccessible(current.getName() + "." + field.getName());
}
}
}
return ClassPlan.accessible(referenceFields.toArray(new Field[0]));
}
};
private OwnedObjectSizeEstimator() {
}
public static MetaCacheSizeEstimate estimate(Object... roots) {
return estimateWithLimits(DEFAULT_MAX_OBJECTS, DEFAULT_MAX_DEPTH, DEFAULT_TIMEOUT_NANOS, roots);
}
static MetaCacheSizeEstimate estimateWithLimitsForTest(
int maxObjects, int maxDepth, long timeoutNanos, Object... roots) {
return estimateWithLimits(maxObjects, maxDepth, timeoutNanos, roots);
}
private static MetaCacheSizeEstimate estimateWithLimits(
int maxObjects, int maxDepth, long timeoutNanos, Object... roots) {
if (maxObjects <= 0 || maxDepth < 0 || timeoutNanos <= 0) {
throw new IllegalArgumentException("estimator limits must be positive");
}
if (!JvmSizeUtils.isVmLayoutKnown()) {
return MetaCacheSizeEstimate.incomplete("unsupported_jvm_layout");
}
State state = new State(maxObjects, maxDepth, timeoutNanos);
for (Object root : roots) {
state.enqueue(root, 0);
}
return state.run();
}
private static final class State {
private final IdentityHashMap<Object, Boolean> visited = new IdentityHashMap<>();
private final Deque<PendingObject> pending = new ArrayDeque<>();
private final int maxObjects;
private final int maxDepth;
private final long deadlineNanos;
private long bytes;
private long operations;
private String incompleteReason;
private int currentDepth;
private State(int maxObjects, int maxDepth, long timeoutNanos) {
this.maxObjects = maxObjects;
this.maxDepth = maxDepth;
long now = System.nanoTime();
this.deadlineNanos = timeoutNanos >= Long.MAX_VALUE - now ? Long.MAX_VALUE : now + timeoutNanos;
}
private void enqueue(Object value) {
enqueue(value, currentDepth + 1);
}
private void enqueue(Object value, int depth) {
if (value == null || incompleteReason != null) {
return;
}
if (++operations % DEADLINE_CHECK_INTERVAL == 0 && System.nanoTime() - deadlineNanos >= 0) {
incompleteReason = "time_budget_exceeded";
return;
}
if (visited.containsKey(value)) {
return;
}
if (depth > maxDepth) {
incompleteReason = "depth_budget_exceeded:" + maxDepth;
return;
}
if (visited.size() >= maxObjects) {
incompleteReason = "object_budget_exceeded:" + maxObjects;
return;
}
visited.put(value, Boolean.TRUE);
pending.addLast(new PendingObject(value, depth));
}
private MetaCacheSizeEstimate run() {
while (!pending.isEmpty() && incompleteReason == null) {
if (++operations % DEADLINE_CHECK_INTERVAL == 0 && System.nanoTime() - deadlineNanos >= 0) {
incompleteReason = "time_budget_exceeded";
break;
}
PendingObject next = pending.removeLast();
currentDepth = next.depth;
measure(next.value);
}
return incompleteReason == null
? MetaCacheSizeEstimate.complete(bytes)
: MetaCacheSizeEstimate.incomplete(incompleteReason);
}
private void measure(Object value) {
Class<?> type = value.getClass();
if (value instanceof String) {
if (((String) value).length() > maxObjects) {
incompleteReason = "single_object_budget_exceeded:string";
return;
}
add(JvmSizeUtils.sizeOfString((String) value));
return;
}
if (type.isArray()) {
measureArray(value, type.getComponentType());
return;
}
if (value instanceof PartitionKey) {
measurePartitionKey((PartitionKey) value);
return;
}
if (value instanceof ListPartitionItem) {
measureListPartitionItem((ListPartitionItem) value);
return;
}
if (value instanceof RangePartitionItem) {
measureRangePartitionItem((RangePartitionItem) value);
return;
}
if (value instanceof LiteralExpr) {
measureLegacyLiteral((LiteralExpr) value);
return;
}
if (value instanceof Literal) {
measureNereidsLiteral((Literal) value);
return;
}
if (value instanceof Type) {
add(JvmSizeUtils.shallowSizeOf(type));
if (type == ScalarType.class) {
// PrimitiveType is an enum/shared boundary. These three optional strings are
// the only owned references retained by ScalarType instances.
ScalarType scalarType = (ScalarType) value;
enqueue(scalarType.getScalarPrecisionStr());
enqueue(scalarType.getScalarScaleStr());
enqueue(scalarType.getLenStr());
} else {
// Complex Type subclasses own nested Type graphs whose sharing semantics are
// not established by this Phase-1 adapter.
incompleteReason = "unsupported_type:" + type.getName();
}
return;
}
if (isSharedBoundary(value, type)) {
return;
}
if (value instanceof Map) {
measureMap((Map<?, ?>) value);
return;
}
if (value instanceof Collection) {
measureCollection((Collection<?>) value);
return;
}
if (value instanceof Optional) {
add(JvmSizeUtils.shallowSizeOf(type));
enqueue(((Optional<?>) value).orElse(null));
return;
}
if (value instanceof BigInteger) {
if (type != BigInteger.class) {
incompleteReason = "unsupported_value_type:" + type.getName();
return;
}
add(JvmSizeUtils.shallowSizeOf(type));
add(JvmSizeUtils.sizeOfPrimitiveArray(
Math.max(1, (((BigInteger) value).abs().bitLength() + 31) / 32), Integer.BYTES));
return;
}
if (value instanceof BigDecimal) {
if (type != BigDecimal.class) {
incompleteReason = "unsupported_value_type:" + type.getName();
return;
}
add(JvmSizeUtils.shallowSizeOf(type));
enqueue(((BigDecimal) value).unscaledValue());
return;
}
if (value instanceof ByteBuffer) {
add(JvmSizeUtils.shallowSizeOf(type));
ByteBuffer buffer = (ByteBuffer) value;
if (buffer.hasArray()) {
enqueue(buffer.array());
} else {
incompleteReason = "inaccessible_owned_buffer:" + type.getName();
}
return;
}
if (value instanceof BitSet) {
if (type != BitSet.class) {
incompleteReason = "unsupported_value_type:" + type.getName();
return;
}
add(JvmSizeUtils.shallowSizeOf(type));
// BitSet.size() exposes the retained long[] capacity without reflective access.
add(JvmSizeUtils.sizeOfPrimitiveArray(((BitSet) value).size() / Long.SIZE, Long.BYTES));
return;
}
if (isLeaf(type)) {
add(JvmSizeUtils.shallowSizeOf(type));
return;
}
if (type.getName().startsWith("java.")) {
// Known JDK containers and values have explicit adapters above. Silently treating
// a new reference-bearing JDK type as shallow would underestimate retained bytes.
incompleteReason = "unsupported_jdk_type:" + type.getName();
return;
}
add(JvmSizeUtils.shallowSizeOf(type));
ClassPlan plan = CLASS_PLANS.get(type);
if (plan.inaccessibleField != null) {
incompleteReason = "inaccessible_owned_field:" + plan.inaccessibleField;
return;
}
for (Field field : plan.referenceFields) {
try {
enqueue(field.get(value));
if (incompleteReason != null) {
return;
}
} catch (IllegalAccessException | RuntimeException e) {
incompleteReason = "inaccessible_owned_field:"
+ field.getDeclaringClass().getName() + "." + field.getName();
return;
}
}
}
private void measureArray(Object value, Class<?> componentType) {
int length = Array.getLength(value);
if (length > maxObjects) {
incompleteReason = "single_object_budget_exceeded:array";
return;
}
if (componentType.isPrimitive()) {
add(JvmSizeUtils.sizeOfPrimitiveArray(length, primitiveBytes(componentType)));
return;
}
add(JvmSizeUtils.sizeOfObjectArray(length));
for (int i = 0; i < length; i++) {
enqueue(Array.get(value, i));
if (incompleteReason != null) {
return;
}
}
}
private void measurePartitionKey(PartitionKey partitionKey) {
add(JvmSizeUtils.shallowSizeOf(partitionKey.getClass()));
measureConnectorArrayList(partitionKey.getKeys());
measureConnectorArrayList(partitionKey.getOriginHiveKeys());
measureConnectorArrayList(partitionKey.getTypes());
}
private void measureListPartitionItem(ListPartitionItem item) {
add(JvmSizeUtils.shallowSizeOf(item.getClass()));
measureConnectorArrayList(item.getItems());
}
private void measureRangePartitionItem(RangePartitionItem item) {
add(JvmSizeUtils.shallowSizeOf(item.getClass()));
com.google.common.collect.Range<PartitionKey> range = item.getItems();
add(JvmSizeUtils.shallowSizeOf(range.getClass()));
add(128L); // lower/upper Cut wrappers and bound enums
if (range.hasLowerBound()) {
enqueue(range.lowerEndpoint());
}
if (range.hasUpperBound()) {
enqueue(range.upperEndpoint());
}
}
private void measureLegacyLiteral(LiteralExpr literal) {
String className = literal.getClass().getName();
if (!SUPPORTED_LEGACY_LITERAL_TYPES.contains(className)) {
incompleteReason = "unsupported_partition_literal:" + className;
return;
}
add(JvmSizeUtils.shallowSizeOf(literal.getClass()));
add(JvmSizeUtils.sizeOfString(literal.getStringValue()));
// Partition literals are scalar leaves. This allowance covers Expr's memoized
// suppliers/optionals and subtype-local scalar wrappers without changing Expr itself.
add(LEGACY_LITERAL_HEADROOM_BYTES);
}
private void measureNereidsLiteral(Literal literal) {
String className = literal.getClass().getName();
if (!SUPPORTED_NEREIDS_LITERAL_TYPES.contains(className)) {
incompleteReason = "unsupported_partition_literal:" + className;
return;
}
add(JvmSizeUtils.shallowSizeOf(literal.getClass()));
Object scalarValue = literal.getValue();
if (scalarValue instanceof String) {
enqueue(scalarValue);
} else if (scalarValue instanceof BigDecimal || scalarValue instanceof BigInteger
|| scalarValue instanceof ByteBuffer || scalarValue instanceof byte[]) {
enqueue(scalarValue);
} else if (scalarValue != null) {
add(JvmSizeUtils.shallowSizeOf(scalarValue.getClass()));
}
add(JvmSizeUtils.sizeOfString(literal.toString()));
// Expression caches (SQL text, input slots, hash and DateV2's legacy literal) are
// deliberately left encapsulated. Reserve their maximum small scalar graph here.
add(NEREIDS_LITERAL_HEADROOM_BYTES);
}
private void measureConnectorArrayList(List<?> values) {
if (values == null) {
return;
}
if (values.size() > maxObjects) {
incompleteReason = "single_object_budget_exceeded:collection";
return;
}
add(JvmSizeUtils.shallowSizeOf(values.getClass()));
add(JvmSizeUtils.sizeOfObjectArray(defaultArrayListCapacity(values.size())));
for (Object value : values) {
enqueue(value);
if (incompleteReason != null) {
return;
}
}
}
private static int defaultArrayListCapacity(int size) {
if (size <= 0) {
return 0;
}
long capacity = 10L;
while (capacity < size) {
capacity = capacity + (capacity >> 1);
if (capacity >= Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
}
return (int) capacity;
}
private void measureMap(Map<?, ?> map) {
if (map.size() > maxObjects) {
incompleteReason = "single_object_budget_exceeded:map";
return;
}
Class<?> type = map.getClass();
String typeName = type.getName();
add(JvmSizeUtils.shallowSizeOf(type));
if (type == KnownCapacityHashMap.class) {
KnownCapacityHashMap<?, ?> knownCapacityMap = (KnownCapacityHashMap<?, ?>) map;
add(JvmSizeUtils.sizeOfKnownCapacityHashMapStorage(
map.size(), knownCapacityMap.getRetainedTableCapacity()));
add(knownCapacityMap.getRetainedViewBytes());
} else if (typeName.equals("com.google.common.collect.RegularImmutableBiMap")
|| typeName.equals("com.google.common.collect.SingletonImmutableBiMap")) {
// This two-index model is conservative for ImmutableBiMap's compact alternating
// key/value array and inverse view. Mutable HashBiMap is intentionally rejected:
// its retained array capacities are not exposed by a public API.
add(JvmSizeUtils.sizeOfHashBiMapStorage(map.size()));
} else if (!typeName.equals("java.util.Collections$EmptyMap")
&& !typeName.equals("java.util.Collections$SingletonMap")) {
incompleteReason = "unsupported_map_type:" + typeName;
return;
}
for (Map.Entry<?, ?> entry : map.entrySet()) {
enqueue(entry.getKey());
enqueue(entry.getValue());
if (incompleteReason != null) {
return;
}
}
}
private void measureCollection(Collection<?> collection) {
if (collection.size() > maxObjects) {
incompleteReason = "single_object_budget_exceeded:collection";
return;
}
Class<?> type = collection.getClass();
String typeName = type.getName();
add(JvmSizeUtils.shallowSizeOf(type));
if (type == KnownNullableImmutableList.class) {
add(JvmSizeUtils.sizeOfObjectArray(collection.size()));
} else if (type == ArrayList.class) {
incompleteReason = "mutable_array_list_capacity_unknown";
return;
} else if (typeName.equals("java.util.Arrays$ArrayList")
|| typeName.equals("com.google.common.collect.RegularImmutableList")) {
add(JvmSizeUtils.sizeOfObjectArray(collection.size()));
} else if (typeName.equals("com.google.common.collect.RegularImmutableSet")) {
// Guava retains an exact elements array and an open-addressed hash table. Model the
// latter conservatively at two slots per element; singleton/empty variants have
// their own runtime classes handled below.
add(JvmSizeUtils.sizeOfObjectArray(collection.size()));
add(JvmSizeUtils.sizeOfObjectArray(collection.size() > Integer.MAX_VALUE / 2
? Integer.MAX_VALUE : collection.size() * 2));
} else if (!typeName.equals("java.util.Collections$EmptyList")
&& !typeName.equals("java.util.Collections$SingletonList")
&& !typeName.equals("java.util.Collections$EmptySet")
&& !typeName.equals("java.util.Collections$SingletonSet")
&& !typeName.equals("com.google.common.collect.SingletonImmutableList")) {
incompleteReason = "unsupported_collection_type:" + typeName;
return;
}
for (Object element : collection) {
enqueue(element);
if (incompleteReason != null) {
return;
}
}
}
private void add(long value) {
bytes = JvmSizeUtils.saturatedAdd(bytes, value);
}
private static boolean isSharedBoundary(Object value, Class<?> type) {
String name = type.getName();
return value == MaxLiteral.MAX_VALUE
|| value instanceof Class
|| value instanceof ClassLoader
|| value instanceof Thread
|| type.isEnum()
|| name.startsWith("org.apache.logging.")
|| SHARED_BOUNDARY_TYPES.get(type);
}
private static boolean isLeaf(Class<?> type) {
return type == Boolean.class || type == Byte.class || type == Character.class
|| type == Short.class || type == Integer.class || type == Long.class
|| type == Float.class || type == Double.class;
}
private static int primitiveBytes(Class<?> type) {
if (type == boolean.class || type == byte.class) {
return 1;
}
if (type == char.class || type == short.class) {
return 2;
}
if (type == int.class || type == float.class) {
return 4;
}
return 8;
}
}
private static boolean isNamedBoundaryType(Class<?> type) {
if (type == null) {
return false;
}
if (SHARED_BOUNDARY_TYPE_NAMES.contains(type.getName())) {
return true;
}
for (Class<?> interfaceType : type.getInterfaces()) {
if (isNamedBoundaryType(interfaceType)) {
return true;
}
}
return isNamedBoundaryType(type.getSuperclass());
}
private static final class PendingObject {
private final Object value;
private final int depth;
private PendingObject(Object value, int depth) {
this.value = value;
this.depth = depth;
}
}
private static final class ClassPlan {
private final Field[] referenceFields;
private final String inaccessibleField;
private ClassPlan(Field[] referenceFields, String inaccessibleField) {
this.referenceFields = referenceFields;
this.inaccessibleField = inaccessibleField;
}
private static ClassPlan accessible(Field[] referenceFields) {
return new ClassPlan(referenceFields, null);
}
private static ClassPlan inaccessible(String field) {
return new ClassPlan(new Field[0], field);
}
}
}