001/*
002 * Logback: the reliable, generic, fast and flexible logging framework.
003 * Copyright (C) 1999-2026, QOS.ch. All rights reserved.
004 *
005 * This program and the accompanying materials are dual-licensed under
006 * either the terms of the Eclipse Public License v2.0 as published by
007 * the Eclipse Foundation
008 *
009 *   or (per the licensee's choosing)
010 *
011 * under the terms of the GNU Lesser General Public License version 2.1
012 * as published by the Free Software Foundation.
013 */
014package ch.qos.logback.core.kryo;
015
016import java.util.LinkedHashMap;
017import java.util.Map;
018
019import static ch.qos.logback.core.kryo.KryoCoreConstants.UNREGISTERED_ID;
020import static ch.qos.logback.core.kryo.KryoCoreConstants.cappedSerializerCapacity;
021
022/**
023 * A {@link BidirectionalObjectToIdMap} that only assigns stable ids to values after they have
024 * been seen often enough on the write path.
025 *
026 * <h2>Motivation</h2>
027 * <p>A plain {@link BidirectionalObjectToIdMapDefault} caches every distinct value on first
028 * sight. For high-cardinality fields (log messages, MDC values, exception text) that creates a
029 * large cache of one-off entries and little compression benefit: the stream still pays for a
030 * {@code NEW_ENTRY} header plus a full payload, and the map fills with values that never recur.
031 *
032 * <p>This implementation <em>gates</em> registration by frequency. A value is not entered into
033 * the id map until it has been written more than {@link #MIN_HITS} times. Until then, writers
034 * emit a full payload under a sentinel id ({@link KryoCoreConstants#UNREGISTERED_ID}); only
035 * on later occurrences is a real id assigned so subsequent writes can emit a compact
036 * {@code CACHED_ENTRY} reference.
037 *
038 * <h2>Write-path protocol</h2>
039 * <p>Used by {@link SerializerBase#write} as follows:
040 * <ol>
041 *   <li>{@link #getIdByValue(Object)} — if a real id exists, emit {@code CACHED_ENTRY} + id
042 *       (no payload).</li>
043 *   <li>Otherwise {@link #insertNewEntryOnWrite(Object)}:
044 *     <ul>
045 *       <li>Increments the per-value access count.</li>
046 *       <li>If {@code count <= MIN_HITS}: returns {@link KryoCoreConstants#UNREGISTERED_ID}
047 *           ({@code -1}) and does <strong>not</strong> store the value in the id map.</li>
048 *       <li>If {@code count > MIN_HITS}: assigns the next id, stores the mapping, returns that
049 *           id.</li>
050 *     </ul>
051 *   </li>
052 *   <li>In both unregistered and newly registered cases, {@code SerializerBase} still writes
053 *       {@code NEW_ENTRY} + the returned id + the full payload via {@code writeNewEntry}.</li>
054 * </ol>
055 *
056 * <p>Thus the first sighting of a value always carries a full payload with id {@code -1}. The
057 * second sighting (with default {@code MIN_HITS = 1}) carries a full payload again, but with a
058 * real id that is stored for later {@code CACHED_ENTRY} hits.
059 *
060 * <h2>Read-path protocol</h2>
061 * <p>{@link SerializerBase#read} reads the entry flag and id, then:
062 * <ul>
063 *   <li>For {@code NEW_ENTRY}: deserializes the payload; if the id is not
064 *       {@link KryoCoreConstants#UNREGISTERED_ID}, registers it via
065 *       {@link #insertNewEntryOnRead(int, Object)}; unregistered ids are not stored.</li>
066 *   <li>For {@code CACHED_ENTRY}: looks up the value with {@link #getValueById(int)} (must already
067 *       have been registered by a prior {@code NEW_ENTRY} with a real id).</li>
068 * </ul>
069 *
070 * <p>Read-side registration is not frequency-gated: the stream is authoritative. Gating applies
071 * only when assigning ids on write.
072 *
073 * <h2>State</h2>
074 * <ul>
075 *   <li><strong>Id map</strong> — a {@link BidirectionalObjectToIdMapDefault} of capacity
076 *       {@code capacity}, access-order LRU eviction when full.</li>
077 *   <li><strong>Access counts</strong> — a separate access-order {@link LinkedHashMap} used only
078 *       on the write path to decide when a value graduates to a real id. Initial capacity
079 *       {@link #ACCESS_COUNT_CACHE_SIZE}.</li>
080 *   <li><strong>Ids</strong> — assigned by the underlying map when a value passes the
081 *       frequency gate; evicted ids are reused.</li>
082 * </ul>
083 *
084 * <h2>Thread safety</h2>
085 * <p>{@link #recordAccess(Object)} is synchronized. Other methods are not; a given map instance
086 * is intended for single-threaded use by one serializer (typical Kryo usage).
087 *
088 * @param <V> value type (must have correct {@code equals}/{@code hashCode} for map keys)
089 * @see BidirectionalObjectToIdMapDefault
090 * @see SerializerBase.BiMapType#FREQUENCY_GATED
091 * @see KryoCoreConstants#UNREGISTERED_ID
092 */
093public class FrequencyGatedBidirectionalObjectToIdMap<V> implements BidirectionalObjectToIdMap<V> {
094
095    final int capacity;
096
097    /**
098     * Minimum number of write-path sightings before a value is assigned a stable id.
099     * With the default of {@code 1}, the second write of the same value receives a real id.
100     */
101    static int MIN_HITS = 1;
102
103    /** Initial capacity of the write-side access-count map. */
104    static final int ACCESS_COUNT_CACHE_SIZE = 512;
105
106    private final BidirectionalObjectToIdMapDefault<V> bidirectionalObjectToIdMap;
107    private final Map<V, Integer> accessCount;
108
109    /**
110     * @param capacity maximum number of value↔id mappings retained in the underlying id map
111     *                 (access-order LRU eviction via {@link BidirectionalObjectToIdMapDefault})
112     */
113    public FrequencyGatedBidirectionalObjectToIdMap(int capacity) {
114        this.capacity = cappedSerializerCapacity(capacity);
115        bidirectionalObjectToIdMap = new BidirectionalObjectToIdMapDefault<>(this.capacity);
116        accessCount = new LinkedHashMap<>(ACCESS_COUNT_CACHE_SIZE, 0.75f, true);
117    }
118
119    /**
120     * Records one write-path access for {@code val} and returns the new count.
121     *
122     * @param val value being written (may be used as a map key)
123     * @return access count for {@code val} after this call (at least 1)
124     */
125    public synchronized int recordAccess(V val) {
126        return accessCount.merge(val, 1, Integer::sum);
127    }
128
129    /**
130     * Returns the stable id for {@code value} if it has already passed the frequency gate and is
131     * still in the id map; otherwise {@code null}.
132     */
133    @Override
134    public Integer getIdByValue(V value) {
135            return bidirectionalObjectToIdMap.getIdByValue(value);
136    }
137
138    /**
139     * Called on the write path when {@link #getIdByValue(Object)} returned {@code null}.
140     *
141     * <p>Increments the access count for {@code value}. If the count is still
142     * {@code <= MIN_HITS}, returns {@link KryoCoreConstants#UNREGISTERED_ID} without storing
143     * a mapping. Once the count exceeds {@link #MIN_HITS}, assigns the next id, stores the
144     * mapping, and returns that id.
145     *
146     * <p>In both cases the caller is expected to write a full payload (the id alone is not
147     * enough for the reader until a real id has been seen).
148     *
149     * @param value value being serialized
150     * @return a newly assigned positive id, or {@link KryoCoreConstants#UNREGISTERED_ID}
151     *         if the value has not yet graduated
152     */
153    @Override
154    public Integer insertNewEntryOnWrite(V value) {
155        int count = recordAccess(value);
156        if (count > MIN_HITS) {
157            return bidirectionalObjectToIdMap.insertNewEntryOnWrite(value);
158        }
159        return UNREGISTERED_ID;
160    }
161
162    /**
163     * Registers a mapping on the read path when a {@code NEW_ENTRY} carries a real id.
164     * Not frequency-gated; delegates to the underlying id map.
165     *
166     * @param id    id from the stream (must not be {@link KryoCoreConstants#UNREGISTERED_ID}
167     *              when called from {@link SerializerBase#read})
168     * @param value deserialized value
169     * @return previous value for {@code id}, or {@code null} if none
170     */
171    @Override
172    public V insertNewEntryOnRead(int id, V value) {
173        return bidirectionalObjectToIdMap.insertNewEntryOnRead(id, value);
174    }
175
176    /**
177     * Looks up a value by id on the read path for {@code CACHED_ENTRY} records.
178     *
179     * @return the value, or {@code null} if the id is unknown or was LRU-evicted
180     */
181    @Override
182    public V getValueById(int id) {
183        return bidirectionalObjectToIdMap.getValueById(id);
184    }
185
186    /** Underlying value↔id map (real ids only). */
187    public BidirectionalObjectToIdMapDefault<V> getBidirectionalObjectToIdMap() {
188        return bidirectionalObjectToIdMap;
189    }
190
191    /**
192     * Write-side access counts used for frequency gating.
193     * Not used for id assignment after a value has graduated.
194     */
195    public Map<V, Integer> getAccessCountMap() {
196        return accessCount;
197    }
198}