org.argeo.api.uuid/src/org/argeo/api/uuid/ConcurrentTimeUuidState.java

   1 package org.argeo.api.uuid;
   2
   3 import static java.lang.System.Logger.Level.DEBUG;
   4 import static java.lang.System.Logger.Level.WARNING;
   5
   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;
  12 import java.util.Map;
  13 import java.util.Objects;
  14 import java.util.Set;
  15 import java.util.WeakHashMap;
  16 import java.util.concurrent.atomic.AtomicLong;
  17
  18 import org.argeo.api.uuid.UuidFactory.TimeUuidState;
  19
  20 /**
  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.
  30  */
  31 public class ConcurrentTimeUuidState implements UuidFactory.TimeUuidState {
  32         private final static Logger logger = System.getLogger(ConcurrentTimeUuidState.class.getName());
  33
  34         /** The maximum possible value of the clocksequence. */
  35         private final static int MAX_CLOCKSEQUENCE = 0x3F00;
  36
  37         private final ClockSequenceProvider clockSequenceProvider;
  38         private final ThreadLocal<ConcurrentTimeUuidState.Holder> currentHolder;
  39
  40         private final Instant startInstant;
  41         /** A start timestamp to which {@link System#nanoTime()}/100 can be added. */
  42         private final long startTimeStamp;
  43
  44         private final Clock clock;
  45         private final boolean useClockForMeasurement;
  46
  47         private long nodeIdBase;
  48
  49         public ConcurrentTimeUuidState(SecureRandom secureRandom, Clock clock) {
  50                 useClockForMeasurement = clock != null;
  51                 this.clock = clock != null ? clock : Clock.systemUTC();
  52
  53                 Objects.requireNonNull(secureRandom);
  54
  55                 // compute the start reference
  56                 startInstant = Instant.now(this.clock);
  57                 long nowVm = nowVm();
  58                 Duration duration = Duration.between(TimeUuid.TIMESTAMP_ZERO, startInstant);
  59                 startTimeStamp = TimeUuid.durationToTimestamp(duration) - nowVm;
  60
  61                 clockSequenceProvider = new ClockSequenceProvider(secureRandom);
  62
  63                 // initalise a state per thread
  64                 currentHolder = new ThreadLocal<>() {
  65
  66                         @Override
  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);
  72                                 return value;
  73                         }
  74                 };
  75         }
  76
  77         /*
  78          * TIME OPERATIONS
  79          */
  80
  81         public long useTimestamp() {
  82                 Holder holder = currentHolder.get();
  83                 if (holder.clockSequence < 0) {
  84                         clockSequenceProvider.newClockSequence(holder);
  85                 }
  86
  87                 long previousTimestamp = holder.lastTimestamp;
  88                 long now = computeNow();
  89
  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);
  94                 }
  95
  96                 // very unlikely case where it took less than 100ns between both
  97                 if (previousTimestamp == now) {
  98                         try {
  99                                 Thread.sleep(0, 100);
 100                         } catch (InterruptedException e) {
 101                                 // silent
 102                         }
 103                         now = computeNow();
 104                         assert previousTimestamp != now;
 105                 }
 106                 holder.lastTimestamp = now;
 107                 return now;
 108         }
 109
 110         private long computeNow() {
 111                 if (useClockForMeasurement) {
 112                         Duration duration = Duration.between(TimeUuid.TIMESTAMP_ZERO, Instant.now(clock));
 113                         return TimeUuid.durationToTimestamp(duration);
 114                 } else {
 115                         return startTimeStamp + nowVm();
 116                 }
 117         }
 118
 119         private long nowVm() {
 120                 return System.nanoTime() / 100;
 121         }
 122
 123         @Override
 124         public long getClockSequence() {
 125                 return currentHolder.get().clockSequence;
 126         }
 127
 128         @Override
 129         public long getLastTimestamp() {
 130                 return currentHolder.get().lastTimestamp;
 131         }
 132
 133         protected void reset(long nodeIdBase, long range) {
 134                 synchronized (clockSequenceProvider) {
 135                         this.nodeIdBase = nodeIdBase;
 136                         clockSequenceProvider.reset(range);
 137                         clockSequenceProvider.notifyAll();
 138                 }
 139         }
 140
 141         @Override
 142         public long getLeastSignificantBits() {
 143                 return currentHolder.get().leastSig;
 144         }
 145
 146         @Override
 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
 152                 return mostSig;
 153         }
 154
 155         /*
 156          * INTERNAL CLASSSES
 157          */
 158         private class Holder {
 159                 private long lastTimestamp;
 160                 private long clockSequence;
 161                 private long threadId;
 162
 163                 private long leastSig;
 164
 165                 @Override
 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);
 170                         return isItself;
 171                 }
 172
 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
 178                 }
 179
 180                 @Override
 181                 public String toString() {
 182                         return "Holder " + clockSequence + ", threadId=" + threadId + ", lastTimestamp=" + lastTimestamp;
 183                 }
 184
 185         }
 186
 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);
 194
 195                 private final SecureRandom secureRandom;
 196
 197                 private final Map<Holder, Long> activeHolders = Collections.synchronizedMap(new WeakHashMap<>());
 198
 199                 ClockSequenceProvider(SecureRandom secureRandom) {
 200                         this.secureRandom = secureRandom;
 201 //                      reset(range);
 202                 }
 203
 204                 synchronized void reset(long range) {
 205                         // long min = secureRandom.nextInt(ConcurrentTimeUuidState.MAX_CLOCKSEQUENCE -
 206                         // rangeSize);
 207                         // long max = min + rangeSize;
 208
 209                         long min, max;
 210                         if (range >= 0) {
 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) + ")");
 219                                 }
 220
 221                                 min = this.range;
 222                                 max = min | 0xFF;
 223                         } else {// full range
 224                                 this.range = range;
 225                                 min = 0;
 226                                 max = MAX_CLOCKSEQUENCE;
 227                         }
 228                         assert min == (int) min;
 229                         assert max == (int) max;
 230
 231                         // TODO rather use assertions
 232                         if (min >= max)
 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");
 238                         this.min = min;
 239                         this.max = max;
 240
 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);
 246
 247                         // reset the counter with a random value in range
 248                         long firstCount = min + secureRandom.nextInt(getRangeSize());
 249                         counter.set(firstCount);
 250
 251                         // reset holders
 252                         for (Holder holder : active) {
 253                                 // save old clocksequence?
 254                                 newClockSequence(holder);
 255                         }
 256                 }
 257
 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
 265                                                 continue holders;
 266
 267                                         if (oldestTimeStamp < 0) {
 268                                                 oldestTimeStamp = h.lastTimestamp;
 269                                                 holderToRemove = h;
 270                                         }
 271                                         if (h.lastTimestamp <= oldestTimeStamp) {
 272                                                 oldestTimeStamp = h.lastTimestamp;
 273                                                 holderToRemove = h;
 274                                         }
 275
 276                                 }
 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);
 283                         }
 284
 285                         long newClockSequence = -1;
 286                         int tryCount = 0;// an explicit exit condition
 287                         do {
 288                                 tryCount++;
 289                                 if (tryCount >= getRangeSize())
 290                                         throw new IllegalStateException("No more clock sequence available");
 291
 292                                 newClockSequence = counter.incrementAndGet();
 293                                 assert newClockSequence >= 0 : "Clock sequence cannot be negative";
 294                                 if (newClockSequence > max) {
 295                                         // reset counter
 296                                         newClockSequence = min;
 297                                         counter.set(newClockSequence);
 298                                 }
 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 + ")");
 309                         }
 310                 }
 311
 312                 private synchronized int getRangeSize() {
 313                         return (int) (max - min);
 314                 }
 315
 316         }
 317
 318 }