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 = TimeUuid.toMostSignificantBits(timestamp);
 147                 return mostSig;
 148         }
 149
 150         /*
 151          * INTERNAL CLASSSES
 152          */
 153         private class Holder {
 154                 private long lastTimestamp;
 155                 private long clockSequence;
 156                 private long threadId;
 157
 158                 private long leastSig;
 159
 160                 @Override
 161                 public boolean equals(Object obj) {
 162                         boolean isItself = this == obj;
 163                         if (!isItself && clockSequence == ((Holder) obj).clockSequence)
 164                                 throw new IllegalStateException("There is another holder with the same clockSequence " + clockSequence);
 165                         return isItself;
 166                 }
 167
 168                 private void setClockSequence(long clockSequence) {
 169                         this.clockSequence = clockSequence;
 170                         this.leastSig = nodeIdBase // already computed node base
 171                                         | (((clockSequence & 0x3F00) >> 8) << 56) // clk_seq_hi_res
 172                                         | ((clockSequence & 0xFF) << 48); // clk_seq_low
 173                 }
 174
 175                 @Override
 176                 public String toString() {
 177                         return "Holder " + clockSequence + ", threadId=" + threadId + ", lastTimestamp=" + lastTimestamp;
 178                 }
 179
 180         }
 181
 182         private static class ClockSequenceProvider {
 183                 /** Set to an illegal value. */
 184                 private long range = MAX_CLOCKSEQUENCE;// this is actually clk_seq_hi
 185 //              private int rangeSize = 256;
 186                 private volatile long min;
 187                 private volatile long max;
 188                 private final AtomicLong counter = new AtomicLong(-1);
 189
 190                 private final SecureRandom secureRandom;
 191
 192                 private final Map<Holder, Long> activeHolders = Collections.synchronizedMap(new WeakHashMap<>());
 193
 194                 ClockSequenceProvider(SecureRandom secureRandom) {
 195                         this.secureRandom = secureRandom;
 196 //                      reset(range);
 197                 }
 198
 199                 synchronized void reset(long range) {
 200                         // long min = secureRandom.nextInt(ConcurrentTimeUuidState.MAX_CLOCKSEQUENCE -
 201                         // rangeSize);
 202                         // long max = min + rangeSize;
 203
 204                         long min, max;
 205                         if (range >= 0) {
 206                                 if (range > MAX_CLOCKSEQUENCE)
 207                                         throw new IllegalArgumentException("Range " + Long.toHexString(range) + " is too big");
 208                                 long previousRange = this.range;
 209                                 this.range = range & 0x3F00;
 210                                 if (this.range != range) {
 211                                         this.range = previousRange;
 212                                         throw new IllegalArgumentException(
 213                                                         "Range is not properly formatted: " + range + " (0x" + Long.toHexString(range) + ")");
 214                                 }
 215
 216                                 min = this.range;
 217                                 max = min | 0xFF;
 218                         } else {// full range
 219                                 this.range = range;
 220                                 min = 0;
 221                                 max = MAX_CLOCKSEQUENCE;
 222                         }
 223                         assert min == (int) min;
 224                         assert max == (int) max;
 225
 226                         // TODO rather use assertions
 227                         if (min >= max)
 228                                 throw new IllegalArgumentException("Minimum " + min + " is bigger than maximum " + max);
 229                         if (min < 0 || min > MAX_CLOCKSEQUENCE)
 230                                 throw new IllegalArgumentException("Minimum " + min + " is not valid");
 231                         if (max < 0 || max > MAX_CLOCKSEQUENCE)
 232                                 throw new IllegalArgumentException("Maximum " + max + " is not valid");
 233                         this.min = min;
 234                         this.max = max;
 235
 236                         Set<Holder> active = activeHolders.keySet();
 237                         int activeCount = active.size();
 238                         if (activeCount > getRangeSize())
 239                                 throw new IllegalStateException(
 240                                                 "There are too many holders for range [" + min + "," + max + "] : " + activeCount);
 241
 242                         // reset the counter with a random value in range
 243                         long firstCount = min + secureRandom.nextInt(getRangeSize());
 244                         counter.set(firstCount);
 245
 246                         // reset holders
 247                         for (Holder holder : active) {
 248                                 // save old clocksequence?
 249                                 newClockSequence(holder);
 250                         }
 251                 }
 252
 253                 private synchronized void newClockSequence(Holder holder) {
 254                         // Too many holders, we will remove the oldes ones
 255                         while (activeHolders.size() > getRangeSize()) {
 256                                 long oldestTimeStamp = -1;
 257                                 Holder holderToRemove = null;
 258                                 holders: for (Holder h : activeHolders.keySet()) {
 259                                         if (h == holder)// skip the caller
 260                                                 continue holders;
 261
 262                                         if (oldestTimeStamp < 0) {
 263                                                 oldestTimeStamp = h.lastTimestamp;
 264                                                 holderToRemove = h;
 265                                         }
 266                                         if (h.lastTimestamp <= oldestTimeStamp) {
 267                                                 oldestTimeStamp = h.lastTimestamp;
 268                                                 holderToRemove = h;
 269                                         }
 270
 271                                 }
 272                                 assert holderToRemove != null;
 273 //                              long oldClockSequence = holderToRemove.clockSequence;
 274                                 holderToRemove.clockSequence = -1;
 275                                 activeHolders.remove(holderToRemove);
 276 //                              if (logger.isLoggable(WARNING))
 277 //                                      logger.log(WARNING, "Removed " + holderToRemove + ", oldClockSequence=" + oldClockSequence);
 278                         }
 279
 280                         long newClockSequence = -1;
 281                         int tryCount = 0;// an explicit exit condition
 282                         do {
 283                                 tryCount++;
 284                                 if (tryCount >= getRangeSize())
 285                                         throw new IllegalStateException("No more clock sequence available");
 286
 287                                 newClockSequence = counter.incrementAndGet();
 288                                 assert newClockSequence >= 0 : "Clock sequence cannot be negative";
 289                                 if (newClockSequence > max) {
 290                                         // reset counter
 291                                         newClockSequence = min;
 292                                         counter.set(newClockSequence);
 293                                 }
 294                         } while (activeHolders.containsValue(newClockSequence));
 295                         // TODO use an iterator to check the values
 296                         holder.setClockSequence(newClockSequence);
 297                         activeHolders.put(holder, newClockSequence);
 298 //                      if (logger.isLoggable(DEBUG)) {
 299 //                              String clockDesc = range >= 0 ? Long.toHexString(newClockSequence & 0x00FF)
 300 //                                              : Long.toHexString(newClockSequence | 0x8000);
 301 //                              String rangeDesc = Long.toHexString(min | 0x8000) + "-" + Long.toHexString(max | 0x8000);
 302 //                              logger.log(DEBUG, "New clocksequence " + clockDesc + " for thread " + Thread.currentThread().getId()
 303 //                                              + " (in range " + rangeDesc + ")");
 304 //                      }
 305                 }
 306
 307                 private synchronized int getRangeSize() {
 308                         return (int) (max - min);
 309                 }
 310
 311         }
 312
 313 }