1 package org
.argeo
.api
.uuid
;
3 import java
.security
.SecureRandom
;
4 import java
.time
.Clock
;
5 import java
.time
.Duration
;
6 import java
.time
.Instant
;
7 import java
.util
.Collections
;
9 import java
.util
.Objects
;
11 import java
.util
.WeakHashMap
;
12 import java
.util
.concurrent
.ForkJoinPool
;
13 import java
.util
.concurrent
.atomic
.AtomicLong
;
15 import org
.argeo
.api
.uuid
.UuidFactory
.TimeUuidState
;
18 * A simple base implementation of {@link TimeUuidState}, which maintains
19 * different clock sequences for each thread, based on a specified range. This
20 * range is defined as clock_seq_hi (cf. RFC4122) and only clock_seq_low is
21 * dynamically allocated. It means that there can be at most 256 parallel clock
22 * sequences. If that limit is reached, the clock sequence which has not be used
23 * for the most time is reallocated to the new thread. It is assumed that the
24 * context where time uUIDs will be generated will often be using thread pools
25 * (e.g. {@link ForkJoinPool#commonPool()}, http server, database access, etc.)
26 * and that such reallocation won't have to happen too often.
28 public class ConcurrentTimeUuidState
implements UuidFactory
.TimeUuidState
{
29 // private final static Logger logger = System.getLogger(ConcurrentTimeUuidState.class.getName());
31 /** The maximum possible value of the clocksequence. */
32 private final static int MAX_CLOCKSEQUENCE
= 0x3F00;
34 private final ClockSequenceProvider clockSequenceProvider
;
35 private final ThreadLocal
<ConcurrentTimeUuidState
.Holder
> currentHolder
;
37 private final Instant startInstant
;
38 /** A start timestamp to which {@link System#nanoTime()}/100 can be added. */
39 private final long startTimeStamp
;
41 private final Clock clock
;
42 private final boolean useClockForMeasurement
;
44 private long nodeIdBase
;
46 public ConcurrentTimeUuidState(SecureRandom secureRandom
, Clock clock
) {
47 useClockForMeasurement
= clock
!= null;
48 this.clock
= clock
!= null ? clock
: Clock
.systemUTC();
50 Objects
.requireNonNull(secureRandom
);
52 // compute the start reference
53 startInstant
= Instant
.now(this.clock
);
55 Duration duration
= Duration
.between(TimeUuid
.TIMESTAMP_ZERO
, startInstant
);
56 startTimeStamp
= TimeUuid
.durationToTimestamp(duration
) - nowVm
;
58 clockSequenceProvider
= new ClockSequenceProvider(secureRandom
);
60 // initalise a state per thread
61 currentHolder
= new ThreadLocal
<>() {
64 protected ConcurrentTimeUuidState
.Holder
initialValue() {
65 ConcurrentTimeUuidState
.Holder value
= new ConcurrentTimeUuidState
.Holder();
66 value
.threadId
= Thread
.currentThread().getId();
67 value
.lastTimestamp
= 0;
68 clockSequenceProvider
.newClockSequence(value
);
78 public long useTimestamp() {
79 Holder holder
= currentHolder
.get();
80 if (holder
.clockSequence
< 0) {
81 clockSequenceProvider
.newClockSequence(holder
);
84 long previousTimestamp
= holder
.lastTimestamp
;
85 long now
= computeNow();
87 // rare case where we are sooner
88 // (e.g. if system time has changed in between and we use the clock)
89 if (previousTimestamp
> now
) {
90 clockSequenceProvider
.newClockSequence(holder
);
93 // very unlikely case where it took less than 100ns between both
94 if (previousTimestamp
== now
) {
97 } catch (InterruptedException e
) {
101 assert previousTimestamp
!= now
;
103 holder
.lastTimestamp
= now
;
107 private long computeNow() {
108 if (useClockForMeasurement
) {
109 Duration duration
= Duration
.between(TimeUuid
.TIMESTAMP_ZERO
, Instant
.now(clock
));
110 return TimeUuid
.durationToTimestamp(duration
);
112 return startTimeStamp
+ nowVm();
116 private long nowVm() {
117 return System
.nanoTime() / 100;
121 public long getClockSequence() {
122 return currentHolder
.get().clockSequence
;
126 public long getLastTimestamp() {
127 return currentHolder
.get().lastTimestamp
;
130 protected void reset(long nodeIdBase
, long range
) {
131 synchronized (clockSequenceProvider
) {
132 this.nodeIdBase
= nodeIdBase
;
133 clockSequenceProvider
.reset(range
);
134 clockSequenceProvider
.notifyAll();
139 public long getLeastSignificantBits() {
140 return currentHolder
.get().leastSig
;
144 public long getMostSignificantBits() {
145 long timestamp
= useTimestamp();
146 long mostSig
= UuidFactory
.MOST_SIG_VERSION1
| ((timestamp
& 0xFFFFFFFFL
) << 32) // time_low
147 | (((timestamp
>> 32) & 0xFFFFL
) << 16) // time_mid
148 | ((timestamp
>> 48) & 0x0FFFL
);// time_hi_and_version
155 private class Holder
{
156 private long lastTimestamp
;
157 private long clockSequence
;
158 private long threadId
;
160 private long leastSig
;
163 public boolean equals(Object obj
) {
164 boolean isItself
= this == obj
;
165 if (!isItself
&& clockSequence
== ((Holder
) obj
).clockSequence
)
166 throw new IllegalStateException("There is another holder with the same clockSequence " + clockSequence
);
170 private void setClockSequence(long clockSequence
) {
171 this.clockSequence
= clockSequence
;
172 this.leastSig
= nodeIdBase
// already computed node base
173 | (((clockSequence
& 0x3F00) >> 8) << 56) // clk_seq_hi_res
174 | ((clockSequence
& 0xFF) << 48); // clk_seq_low
178 public String
toString() {
179 return "Holder " + clockSequence
+ ", threadId=" + threadId
+ ", lastTimestamp=" + lastTimestamp
;
184 private static class ClockSequenceProvider
{
185 /** Set to an illegal value. */
186 private long range
= MAX_CLOCKSEQUENCE
;// this is actually clk_seq_hi
187 // private int rangeSize = 256;
188 private volatile long min
;
189 private volatile long max
;
190 private final AtomicLong counter
= new AtomicLong(-1);
192 private final SecureRandom secureRandom
;
194 private final Map
<Holder
, Long
> activeHolders
= Collections
.synchronizedMap(new WeakHashMap
<>());
196 ClockSequenceProvider(SecureRandom secureRandom
) {
197 this.secureRandom
= secureRandom
;
201 synchronized void reset(long range
) {
202 // long min = secureRandom.nextInt(ConcurrentTimeUuidState.MAX_CLOCKSEQUENCE -
204 // long max = min + rangeSize;
208 if (range
> MAX_CLOCKSEQUENCE
)
209 throw new IllegalArgumentException("Range " + Long
.toHexString(range
) + " is too big");
210 long previousRange
= this.range
;
211 this.range
= range
& 0x3F00;
212 if (this.range
!= range
) {
213 this.range
= previousRange
;
214 throw new IllegalArgumentException(
215 "Range is not properly formatted: " + range
+ " (0x" + Long
.toHexString(range
) + ")");
220 } else {// full range
223 max
= MAX_CLOCKSEQUENCE
;
225 assert min
== (int) min
;
226 assert max
== (int) max
;
228 // TODO rather use assertions
230 throw new IllegalArgumentException("Minimum " + min
+ " is bigger than maximum " + max
);
231 if (min
< 0 || min
> MAX_CLOCKSEQUENCE
)
232 throw new IllegalArgumentException("Minimum " + min
+ " is not valid");
233 if (max
< 0 || max
> MAX_CLOCKSEQUENCE
)
234 throw new IllegalArgumentException("Maximum " + max
+ " is not valid");
238 Set
<Holder
> active
= activeHolders
.keySet();
239 int activeCount
= active
.size();
240 if (activeCount
> getRangeSize())
241 throw new IllegalStateException(
242 "There are too many holders for range [" + min
+ "," + max
+ "] : " + activeCount
);
244 // reset the counter with a random value in range
245 long firstCount
= min
+ secureRandom
.nextInt(getRangeSize());
246 counter
.set(firstCount
);
249 for (Holder holder
: active
) {
250 // save old clocksequence?
251 newClockSequence(holder
);
255 private synchronized void newClockSequence(Holder holder
) {
256 // Too many holders, we will remove the oldes ones
257 while (activeHolders
.size() > getRangeSize()) {
258 long oldestTimeStamp
= -1;
259 Holder holderToRemove
= null;
260 holders
: for (Holder h
: activeHolders
.keySet()) {
261 if (h
== holder
)// skip the caller
264 if (oldestTimeStamp
< 0) {
265 oldestTimeStamp
= h
.lastTimestamp
;
268 if (h
.lastTimestamp
<= oldestTimeStamp
) {
269 oldestTimeStamp
= h
.lastTimestamp
;
274 assert holderToRemove
!= null;
275 // long oldClockSequence = holderToRemove.clockSequence;
276 holderToRemove
.clockSequence
= -1;
277 activeHolders
.remove(holderToRemove
);
278 // if (logger.isLoggable(WARNING))
279 // logger.log(WARNING, "Removed " + holderToRemove + ", oldClockSequence=" + oldClockSequence);
282 long newClockSequence
= -1;
283 int tryCount
= 0;// an explicit exit condition
286 if (tryCount
>= getRangeSize())
287 throw new IllegalStateException("No more clock sequence available");
289 newClockSequence
= counter
.incrementAndGet();
290 assert newClockSequence
>= 0 : "Clock sequence cannot be negative";
291 if (newClockSequence
> max
) {
293 newClockSequence
= min
;
294 counter
.set(newClockSequence
);
296 } while (activeHolders
.containsValue(newClockSequence
));
297 // TODO use an iterator to check the values
298 holder
.setClockSequence(newClockSequence
);
299 activeHolders
.put(holder
, newClockSequence
);
300 // if (logger.isLoggable(DEBUG)) {
301 // String clockDesc = range >= 0 ? Long.toHexString(newClockSequence & 0x00FF)
302 // : Long.toHexString(newClockSequence | 0x8000);
303 // String rangeDesc = Long.toHexString(min | 0x8000) + "-" + Long.toHexString(max | 0x8000);
304 // logger.log(DEBUG, "New clocksequence " + clockDesc + " for thread " + Thread.currentThread().getId()
305 // + " (in range " + rangeDesc + ")");
309 private synchronized int getRangeSize() {
310 return (int) (max
- min
);