View Javadoc
1   /*
2    * Logback: the reliable, generic, fast and flexible logging framework.
3    * Copyright (C) 1999-2026, QOS.ch. All rights reserved.
4    *
5    * This program and the accompanying materials are dual-licensed under
6    * either the terms of the Eclipse Public License v2.0 as published by
7    * the Eclipse Foundation
8    *
9    *   or (per the licensee's choosing)
10   *
11   * under the terms of the GNU Lesser General Public License version 2.1
12   * as published by the Free Software Foundation.
13   */
14  package ch.qos.logback.core.kryo;
15  
16  import java.util.LinkedHashMap;
17  import java.util.Map;
18  
19  import static ch.qos.logback.core.kryo.KryoCoreConstants.UNREGISTERED_ID;
20  import static ch.qos.logback.core.kryo.KryoCoreConstants.cappedSerializerCapacity;
21  
22  /**
23   * A {@link BidirectionalObjectToIdMap} that only assigns stable ids to values after they have
24   * been seen often enough on the write path.
25   *
26   * <h2>Motivation</h2>
27   * <p>A plain {@link BidirectionalObjectToIdMapDefault} caches every distinct value on first
28   * sight. For high-cardinality fields (log messages, MDC values, exception text) that creates a
29   * large cache of one-off entries and little compression benefit: the stream still pays for a
30   * {@code NEW_ENTRY} header plus a full payload, and the map fills with values that never recur.
31   *
32   * <p>This implementation <em>gates</em> registration by frequency. A value is not entered into
33   * the id map until it has been written more than {@link #MIN_HITS} times. Until then, writers
34   * emit a full payload under a sentinel id ({@link KryoCoreConstants#UNREGISTERED_ID}); only
35   * on later occurrences is a real id assigned so subsequent writes can emit a compact
36   * {@code CACHED_ENTRY} reference.
37   *
38   * <h2>Write-path protocol</h2>
39   * <p>Used by {@link SerializerBase#write} as follows:
40   * <ol>
41   *   <li>{@link #getIdByValue(Object)} — if a real id exists, emit {@code CACHED_ENTRY} + id
42   *       (no payload).</li>
43   *   <li>Otherwise {@link #insertNewEntryOnWrite(Object)}:
44   *     <ul>
45   *       <li>Increments the per-value access count.</li>
46   *       <li>If {@code count <= MIN_HITS}: returns {@link KryoCoreConstants#UNREGISTERED_ID}
47   *           ({@code -1}) and does <strong>not</strong> store the value in the id map.</li>
48   *       <li>If {@code count > MIN_HITS}: assigns the next id, stores the mapping, returns that
49   *           id.</li>
50   *     </ul>
51   *   </li>
52   *   <li>In both unregistered and newly registered cases, {@code SerializerBase} still writes
53   *       {@code NEW_ENTRY} + the returned id + the full payload via {@code writeNewEntry}.</li>
54   * </ol>
55   *
56   * <p>Thus the first sighting of a value always carries a full payload with id {@code -1}. The
57   * second sighting (with default {@code MIN_HITS = 1}) carries a full payload again, but with a
58   * real id that is stored for later {@code CACHED_ENTRY} hits.
59   *
60   * <h2>Read-path protocol</h2>
61   * <p>{@link SerializerBase#read} reads the entry flag and id, then:
62   * <ul>
63   *   <li>For {@code NEW_ENTRY}: deserializes the payload; if the id is not
64   *       {@link KryoCoreConstants#UNREGISTERED_ID}, registers it via
65   *       {@link #insertNewEntryOnRead(int, Object)}; unregistered ids are not stored.</li>
66   *   <li>For {@code CACHED_ENTRY}: looks up the value with {@link #getValueById(int)} (must already
67   *       have been registered by a prior {@code NEW_ENTRY} with a real id).</li>
68   * </ul>
69   *
70   * <p>Read-side registration is not frequency-gated: the stream is authoritative. Gating applies
71   * only when assigning ids on write.
72   *
73   * <h2>State</h2>
74   * <ul>
75   *   <li><strong>Id map</strong> — a {@link BidirectionalObjectToIdMapDefault} of capacity
76   *       {@code capacity}, access-order LRU eviction when full.</li>
77   *   <li><strong>Access counts</strong> — a separate access-order {@link LinkedHashMap} used only
78   *       on the write path to decide when a value graduates to a real id. Initial capacity
79   *       {@link #ACCESS_COUNT_CACHE_SIZE}.</li>
80   *   <li><strong>Ids</strong> — assigned by the underlying map when a value passes the
81   *       frequency gate; evicted ids are reused.</li>
82   * </ul>
83   *
84   * <h2>Thread safety</h2>
85   * <p>{@link #recordAccess(Object)} is synchronized. Other methods are not; a given map instance
86   * is intended for single-threaded use by one serializer (typical Kryo usage).
87   *
88   * @param <V> value type (must have correct {@code equals}/{@code hashCode} for map keys)
89   * @see BidirectionalObjectToIdMapDefault
90   * @see SerializerBase.BiMapType#FREQUENCY_GATED
91   * @see KryoCoreConstants#UNREGISTERED_ID
92   */
93  public class FrequencyGatedBidirectionalObjectToIdMap<V> implements BidirectionalObjectToIdMap<V> {
94  
95      final int capacity;
96  
97      /**
98       * Minimum number of write-path sightings before a value is assigned a stable id.
99       * 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 }