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

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