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 }