1 package org
.argeo
.api
.uuid
;
3 import static java
.lang
.System
.Logger
.Level
.DEBUG
;
4 import static java
.lang
.System
.Logger
.Level
.WARNING
;
6 import java
.lang
.System
.Logger
;
7 import java
.security
.SecureRandom
;
8 import java
.time
.Clock
;
9 import java
.time
.Duration
;
10 import java
.time
.Instant
;
11 import java
.util
.Collections
;
13 import java
.util
.Objects
;
15 import java
.util
.WeakHashMap
;
16 import java
.util
.concurrent
.atomic
.AtomicLong
;
18 import org
.argeo
.api
.uuid
.UuidFactory
.TimeUuidState
;
21 * A simple base implementation of {@link TimeUuidState}, which maintains
22 * different clock sequences for each thread, based on a specified range. This
23 * range is defined as clock_seq_hi (cf. RFC4122) and only clock_seq_low is
24 * dynamically allocated. It means that there can be at most 256 parallel clock
25 * sequences. If that limit is reached, the clock sequence which has not be used
26 * for the most time is reallocated to the new thread. It is assumed that the
27 * context where time uUIDs will be generated will often be using thread pools
28 * (e.g. {@link ForkJoinPool#commonPool(), http server, database access, etc.)
29 * and that such reallocation won't have to happen too often.
31 public class ConcurrentTimeUuidState
implements UuidFactory
.TimeUuidState
{
32 private final static Logger logger
= System
.getLogger(ConcurrentTimeUuidState
.class.getName());
34 /** The maximum possible value of the clocksequence. */
35 private final static int MAX_CLOCKSEQUENCE
= 0x3F00;
37 private final ClockSequenceProvider clockSequenceProvider
;
38 private final ThreadLocal
<ConcurrentTimeUuidState
.Holder
> currentHolder
;
40 private final Instant startInstant
;
41 /** A start timestamp to which {@link System#nanoTime()}/100 can be added. */
42 private final long startTimeStamp
;
44 private final Clock clock
;
45 private final boolean useClockForMeasurement
;
47 private long nodeIdBase
;
49 public ConcurrentTimeUuidState(SecureRandom secureRandom
, Clock clock
) {
50 useClockForMeasurement
= clock
!= null;
51 this.clock
= clock
!= null ? clock
: Clock
.systemUTC();
53 Objects
.requireNonNull(secureRandom
);
55 // compute the start reference
56 startInstant
= Instant
.now(this.clock
);
58 Duration duration
= Duration
.between(TimeUuid
.TIMESTAMP_ZERO
, startInstant
);
59 startTimeStamp
= TimeUuid
.durationToTimestamp(duration
) - nowVm
;
61 clockSequenceProvider
= new ClockSequenceProvider(secureRandom
);
63 // initalise a state per thread
64 currentHolder
= new ThreadLocal
<>() {
67 protected ConcurrentTimeUuidState
.Holder
initialValue() {
68 ConcurrentTimeUuidState
.Holder value
= new ConcurrentTimeUuidState
.Holder();
69 value
.threadId
= Thread
.currentThread().getId();
70 value
.lastTimestamp
= 0;
71 clockSequenceProvider
.newClockSequence(value
);
81 public long useTimestamp() {
82 Holder holder
= currentHolder
.get();
83 if (holder
.clockSequence
< 0) {
84 clockSequenceProvider
.newClockSequence(holder
);
87 long previousTimestamp
= holder
.lastTimestamp
;
88 long now
= computeNow();
90 // rare case where we are sooner
91 // (e.g. if system time has changed in between and we use the clock)
92 if (previousTimestamp
> now
) {
93 clockSequenceProvider
.newClockSequence(holder
);
96 // very unlikely case where it took less than 100ns between both
97 if (previousTimestamp
== now
) {
100 } catch (InterruptedException e
) {
104 assert previousTimestamp
!= now
;
106 holder
.lastTimestamp
= now
;
110 private long computeNow() {
111 if (useClockForMeasurement
) {
112 Duration duration
= Duration
.between(TimeUuid
.TIMESTAMP_ZERO
, Instant
.now(clock
));
113 return TimeUuid
.durationToTimestamp(duration
);
115 return startTimeStamp
+ nowVm();
119 private long nowVm() {
120 return System
.nanoTime() / 100;
124 public long getClockSequence() {
125 return currentHolder
.get().clockSequence
;
129 public long getLastTimestamp() {
130 return currentHolder
.get().lastTimestamp
;
133 protected void reset(long nodeIdBase
, long range
) {
134 synchronized (clockSequenceProvider
) {
135 this.nodeIdBase
= nodeIdBase
;
136 clockSequenceProvider
.reset(range
);
137 clockSequenceProvider
.notifyAll();
142 public long getLeastSignificantBits() {
143 return currentHolder
.get().leastSig
;
147 public long getMostSignificantBits() {
148 long timestamp
= useTimestamp();
149 long mostSig
= UuidFactory
.MOST_SIG_VERSION1
| ((timestamp
& 0xFFFFFFFFL
) << 32) // time_low
150 | (((timestamp
>> 32) & 0xFFFFL
) << 16) // time_mid
151 | ((timestamp
>> 48) & 0x0FFFL
);// time_hi_and_version
158 private class Holder
{
159 private long lastTimestamp
;
160 private long clockSequence
;
161 private long threadId
;
163 private long leastSig
;
166 public boolean equals(Object obj
) {
167 boolean isItself
= this == obj
;
168 if (!isItself
&& clockSequence
== ((Holder
) obj
).clockSequence
)
169 throw new IllegalStateException("There is another holder with the same clockSequence " + clockSequence
);
173 private void setClockSequence(long clockSequence
) {
174 this.clockSequence
= clockSequence
;
175 this.leastSig
= nodeIdBase
// already computed node base
176 | (((clockSequence
& 0x3F00) >> 8) << 56) // clk_seq_hi_res
177 | ((clockSequence
& 0xFF) << 48); // clk_seq_low
181 public String
toString() {
182 return "Holder " + clockSequence
+ ", threadId=" + threadId
+ ", lastTimestamp=" + lastTimestamp
;
187 private static class ClockSequenceProvider
{
188 /** Set to an illegal value. */
189 private long range
= MAX_CLOCKSEQUENCE
;// this is actually clk_seq_hi
190 // private int rangeSize = 256;
191 private volatile long min
;
192 private volatile long max
;
193 private final AtomicLong counter
= new AtomicLong(-1);
195 private final SecureRandom secureRandom
;
197 private final Map
<Holder
, Long
> activeHolders
= Collections
.synchronizedMap(new WeakHashMap
<>());
199 ClockSequenceProvider(SecureRandom secureRandom
) {
200 this.secureRandom
= secureRandom
;
204 synchronized void reset(long range
) {
205 // long min = secureRandom.nextInt(ConcurrentTimeUuidState.MAX_CLOCKSEQUENCE -
207 // long max = min + rangeSize;
211 if (range
> MAX_CLOCKSEQUENCE
)
212 throw new IllegalArgumentException("Range " + Long
.toHexString(range
) + " is too big");
213 long previousRange
= this.range
;
214 this.range
= range
& 0x3F00;
215 if (this.range
!= range
) {
216 this.range
= previousRange
;
217 throw new IllegalArgumentException(
218 "Range is not properly formatted: " + range
+ " (0x" + Long
.toHexString(range
) + ")");
223 } else {// full range
226 max
= MAX_CLOCKSEQUENCE
;
228 assert min
== (int) min
;
229 assert max
== (int) max
;
231 // TODO rather use assertions
233 throw new IllegalArgumentException("Minimum " + min
+ " is bigger than maximum " + max
);
234 if (min
< 0 || min
> MAX_CLOCKSEQUENCE
)
235 throw new IllegalArgumentException("Minimum " + min
+ " is not valid");
236 if (max
< 0 || max
> MAX_CLOCKSEQUENCE
)
237 throw new IllegalArgumentException("Maximum " + max
+ " is not valid");
241 Set
<Holder
> active
= activeHolders
.keySet();
242 int activeCount
= active
.size();
243 if (activeCount
> getRangeSize())
244 throw new IllegalStateException(
245 "There are too many holders for range [" + min
+ "," + max
+ "] : " + activeCount
);
247 // reset the counter with a random value in range
248 long firstCount
= min
+ secureRandom
.nextInt(getRangeSize());
249 counter
.set(firstCount
);
252 for (Holder holder
: active
) {
253 // save old clocksequence?
254 newClockSequence(holder
);
258 private synchronized void newClockSequence(Holder holder
) {
259 // Too many holders, we will remove the oldes ones
260 while (activeHolders
.size() > getRangeSize()) {
261 long oldestTimeStamp
= -1;
262 Holder holderToRemove
= null;
263 holders
: for (Holder h
: activeHolders
.keySet()) {
264 if (h
== holder
)// skip the caller
267 if (oldestTimeStamp
< 0) {
268 oldestTimeStamp
= h
.lastTimestamp
;
271 if (h
.lastTimestamp
<= oldestTimeStamp
) {
272 oldestTimeStamp
= h
.lastTimestamp
;
277 assert holderToRemove
!= null;
278 long oldClockSequence
= holderToRemove
.clockSequence
;
279 holderToRemove
.clockSequence
= -1;
280 activeHolders
.remove(holderToRemove
);
281 if (logger
.isLoggable(WARNING
))
282 logger
.log(WARNING
, "Removed " + holderToRemove
+ ", oldClockSequence=" + oldClockSequence
);
285 long newClockSequence
= -1;
286 int tryCount
= 0;// an explicit exit condition
289 if (tryCount
>= getRangeSize())
290 throw new IllegalStateException("No more clock sequence available");
292 newClockSequence
= counter
.incrementAndGet();
293 assert newClockSequence
>= 0 : "Clock sequence cannot be negative";
294 if (newClockSequence
> max
) {
296 newClockSequence
= min
;
297 counter
.set(newClockSequence
);
299 } while (activeHolders
.containsValue(newClockSequence
));
300 // TODO use an iterator to check the values
301 holder
.setClockSequence(newClockSequence
);
302 activeHolders
.put(holder
, newClockSequence
);
303 if (logger
.isLoggable(DEBUG
)) {
304 String clockDesc
= range
>= 0 ? Long
.toHexString(newClockSequence
& 0x00FF)
305 : Long
.toHexString(newClockSequence
| 0x8000);
306 String rangeDesc
= Long
.toHexString(min
| 0x8000) + "-" + Long
.toHexString(max
| 0x8000);
307 logger
.log(DEBUG
, "New clocksequence " + clockDesc
+ " for thread " + Thread
.currentThread().getId()
308 + " (in range " + rangeDesc
+ ")");
312 private synchronized int getRangeSize() {
313 return (int) (max
- min
);