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.atomic.AtomicLong;
  13
  14 import org.argeo.api.uuid.UuidFactory.TimeUuidState;
  15
  16 /**
  17  * A simple base implementation of {@link TimeUuidState}, which maintains
  18  * different clock sequences for each thread, based on a specified range. This
  19  * range is defined as clock_seq_hi (cf. RFC4122) and only clock_seq_low is
  20  * dynamically allocated. It means that there can be at most 256 parallel clock
  21  * sequences. If that limit is reached, the clock sequence which has not be used
  22  * for the most time is reallocated to the new thread. It is assumed that the
  23  * context where time uUIDs will be generated will often be using thread pools
  24  * (e.g. {@link ForkJoinPool#commonPool(), http server, database access, etc.)
  25  * and that such reallocation won't have to happen too often.
  26  */
  27 public class ConcurrentTimeUuidState implements UuidFactory.TimeUuidState {
  28 //      private final static Logger logger = System.getLogger(ConcurrentTimeUuidState.class.getName());
  29
  30         /** The maximum possible value of the clocksequence. */
  31         private final static int MAX_CLOCKSEQUENCE = 0x3F00;
  32
  33         private final ClockSequenceProvider clockSequenceProvider;
  34         private final ThreadLocal<ConcurrentTimeUuidState.Holder> currentHolder;
  35
  36         private final Instant startInstant;
  37         /** A start timestamp to which {@link System#nanoTime()}/100 can be added. */
  38         private final long startTimeStamp;
  39
  40         private final Clock clock;
  41         private final boolean useClockForMeasurement;
  42
  43         private long nodeIdBase;
  44
  45         public ConcurrentTimeUuidState(SecureRandom secureRandom, Clock clock) {
  46                 useClockForMeasurement = clock != null;
  47                 this.clock = clock != null ? clock : Clock.systemUTC();
  48
  49                 Objects.requireNonNull(secureRandom);
  50
  51                 // compute the start reference
  52                 startInstant = Instant.now(this.clock);
  53                 long nowVm = nowVm();
  54                 Duration duration = Duration.between(TimeUuid.TIMESTAMP_ZERO, startInstant);
  55                 startTimeStamp = TimeUuid.durationToTimestamp(duration) - nowVm;
  56
  57                 clockSequenceProvider = new ClockSequenceProvider(secureRandom);
  58
  59                 // initalise a state per thread
  60                 currentHolder = new ThreadLocal<>() {
  61
  62                         @Override
  63                         protected ConcurrentTimeUuidState.Holder initialValue() {
  64                                 ConcurrentTimeUuidState.Holder value = new ConcurrentTimeUuidState.Holder();
  65                                 value.threadId = Thread.currentThread().getId();
  66                                 value.lastTimestamp = 0;
  67                                 clockSequenceProvider.newClockSequence(value);
  68                                 return value;
  69                         }
  70                 };
  71         }
  72
  73         /*
  74          * TIME OPERATIONS
  75          */
  76
  77         public long useTimestamp() {
  78                 Holder holder = currentHolder.get();
  79                 if (holder.clockSequence < 0) {
  80                         clockSequenceProvider.newClockSequence(holder);
  81                 }
  82
  83                 long previousTimestamp = holder.lastTimestamp;
  84                 long now = computeNow();
  85
  86                 // rare case where we are sooner
  87                 // (e.g. if system time has changed in between and we use the clock)
  88                 if (previousTimestamp > now) {
  89                         clockSequenceProvider.newClockSequence(holder);
  90                 }
  91
  92                 // very unlikely case where it took less than 100ns between both
  93                 if (previousTimestamp == now) {
  94                         try {
  95                                 Thread.sleep(0, 100);
  96                         } catch (InterruptedException e) {
  97                                 // silent
  98                         }
  99                         now = computeNow();
 100                         assert previousTimestamp != now;
 101                 }
 102                 holder.lastTimestamp = now;
 103                 return now;
 104         }
 105
 106         private long computeNow() {
 107                 if (useClockForMeasurement) {
 108                         Duration duration = Duration.between(TimeUuid.TIMESTAMP_ZERO, Instant.now(clock));
 109                         return TimeUuid.durationToTimestamp(duration);
 110                 } else {
 111                         return startTimeStamp + nowVm();
 112                 }
 113         }
 114
 115         private long nowVm() {
 116                 return System.nanoTime() / 100;
 117         }
 118
 119         @Override
 120         public long getClockSequence() {
 121                 return currentHolder.get().clockSequence;
 122         }
 123
 124         @Override
 125         public long getLastTimestamp() {
 126                 return currentHolder.get().lastTimestamp;
 127         }
 128
 129         protected void reset(long nodeIdBase, long range) {
 130                 synchronized (clockSequenceProvider) {
 131                         this.nodeIdBase = nodeIdBase;
 132                         clockSequenceProvider.reset(range);
 133                         clockSequenceProvider.notifyAll();
 134                 }
 135         }
 136
 137         @Override
 138         public long getLeastSignificantBits() {
 139                 return currentHolder.get().leastSig;
 140         }
 141
 142         @Override
 143         public long getMostSignificantBits() {
 144                 long timestamp = useTimestamp();
 145                 long mostSig = UuidFactory.MOST_SIG_VERSION1 | ((timestamp & 0xFFFFFFFFL) << 32) // time_low
 146                                 | (((timestamp >> 32) & 0xFFFFL) << 16) // time_mid
 147                                 | ((timestamp >> 48) & 0x0FFFL);// time_hi_and_version
 148                 return mostSig;
 149         }
 150
 151         /*
 152          * INTERNAL CLASSSES
 153          */
 154         private class Holder {
 155                 private long lastTimestamp;
 156                 private long clockSequence;
 157                 private long threadId;
 158
 159                 private long leastSig;
 160
 161                 @Override
 162                 public boolean equals(Object obj) {
 163                         boolean isItself = this == obj;
 164                         if (!isItself && clockSequence == ((Holder) obj).clockSequence)
 165                                 throw new IllegalStateException("There is another holder with the same clockSequence " + clockSequence);
 166                         return isItself;
 167                 }
 168
 169                 private void setClockSequence(long clockSequence) {
 170                         this.clockSequence = clockSequence;
 171                         this.leastSig = nodeIdBase // already computed node base
 172                                         | (((clockSequence & 0x3F00) >> 8) << 56) // clk_seq_hi_res
 173                                         | ((clockSequence & 0xFF) << 48); // clk_seq_low
 174                 }
 175
 176                 @Override
 177                 public String toString() {
 178                         return "Holder " + clockSequence + ", threadId=" + threadId + ", lastTimestamp=" + lastTimestamp;
 179                 }
 180
 181         }
 182
 183         private static class ClockSequenceProvider {
 184                 /** Set to an illegal value. */
 185                 private long range = MAX_CLOCKSEQUENCE;// this is actually clk_seq_hi
 186 //              private int rangeSize = 256;
 187                 private volatile long min;
 188                 private volatile long max;
 189                 private final AtomicLong counter = new AtomicLong(-1);
 190
 191                 private final SecureRandom secureRandom;
 192
 193                 private final Map<Holder, Long> activeHolders = Collections.synchronizedMap(new WeakHashMap<>());
 194
 195                 ClockSequenceProvider(SecureRandom secureRandom) {
 196                         this.secureRandom = secureRandom;
 197 //                      reset(range);
 198                 }
 199
 200                 synchronized void reset(long range) {
 201                         // long min = secureRandom.nextInt(ConcurrentTimeUuidState.MAX_CLOCKSEQUENCE -
 202                         // rangeSize);
 203                         // long max = min + rangeSize;
 204
 205                         long min, max;
 206                         if (range >= 0) {
 207                                 if (range > MAX_CLOCKSEQUENCE)
 208                                         throw new IllegalArgumentException("Range " + Long.toHexString(range) + " is too big");
 209                                 long previousRange = this.range;
 210                                 this.range = range & 0x3F00;
 211                                 if (this.range != range) {
 212                                         this.range = previousRange;
 213                                         throw new IllegalArgumentException(
 214                                                         "Range is not properly formatted: " + range + " (0x" + Long.toHexString(range) + ")");
 215                                 }
 216
 217                                 min = this.range;
 218                                 max = min | 0xFF;
 219                         } else {// full range
 220                                 this.range = range;
 221                                 min = 0;
 222                                 max = MAX_CLOCKSEQUENCE;
 223                         }
 224                         assert min == (int) min;
 225                         assert max == (int) max;
 226
 227                         // TODO rather use assertions
 228                         if (min >= max)
 229                                 throw new IllegalArgumentException("Minimum " + min + " is bigger than maximum " + max);
 230                         if (min < 0 || min > MAX_CLOCKSEQUENCE)
 231                                 throw new IllegalArgumentException("Minimum " + min + " is not valid");
 232                         if (max < 0 || max > MAX_CLOCKSEQUENCE)
 233                                 throw new IllegalArgumentException("Maximum " + max + " is not valid");
 234                         this.min = min;
 235                         this.max = max;
 236
 237                         Set<Holder> active = activeHolders.keySet();
 238                         int activeCount = active.size();
 239                         if (activeCount > getRangeSize())
 240                                 throw new IllegalStateException(
 241                                                 "There are too many holders for range [" + min + "," + max + "] : " + activeCount);
 242
 243                         // reset the counter with a random value in range
 244                         long firstCount = min + secureRandom.nextInt(getRangeSize());
 245                         counter.set(firstCount);
 246
 247                         // reset holders
 248                         for (Holder holder : active) {
 249                                 // save old clocksequence?
 250                                 newClockSequence(holder);
 251                         }
 252                 }
 253
 254                 private synchronized void newClockSequence(Holder holder) {
 255                         // Too many holders, we will remove the oldes ones
 256                         while (activeHolders.size() > getRangeSize()) {
 257                                 long oldestTimeStamp = -1;
 258                                 Holder holderToRemove = null;
 259                                 holders: for (Holder h : activeHolders.keySet()) {
 260                                         if (h == holder)// skip the caller
 261                                                 continue holders;
 262
 263                                         if (oldestTimeStamp < 0) {
 264                                                 oldestTimeStamp = h.lastTimestamp;
 265                                                 holderToRemove = h;
 266                                         }
 267                                         if (h.lastTimestamp <= oldestTimeStamp) {
 268                                                 oldestTimeStamp = h.lastTimestamp;
 269                                                 holderToRemove = h;
 270                                         }
 271
 272                                 }
 273                                 assert holderToRemove != null;
 274 //                              long oldClockSequence = holderToRemove.clockSequence;
 275                                 holderToRemove.clockSequence = -1;
 276                                 activeHolders.remove(holderToRemove);
 277 //                              if (logger.isLoggable(WARNING))
 278 //                                      logger.log(WARNING, "Removed " + holderToRemove + ", oldClockSequence=" + oldClockSequence);
 279                         }
 280
 281                         long newClockSequence = -1;
 282                         int tryCount = 0;// an explicit exit condition
 283                         do {
 284                                 tryCount++;
 285                                 if (tryCount >= getRangeSize())
 286                                         throw new IllegalStateException("No more clock sequence available");
 287
 288                                 newClockSequence = counter.incrementAndGet();
 289                                 assert newClockSequence >= 0 : "Clock sequence cannot be negative";
 290                                 if (newClockSequence > max) {
 291                                         // reset counter
 292                                         newClockSequence = min;
 293                                         counter.set(newClockSequence);
 294                                 }
 295                         } while (activeHolders.containsValue(newClockSequence));
 296                         // TODO use an iterator to check the values
 297                         holder.setClockSequence(newClockSequence);
 298                         activeHolders.put(holder, newClockSequence);
 299 //                      if (logger.isLoggable(DEBUG)) {
 300 //                              String clockDesc = range >= 0 ? Long.toHexString(newClockSequence & 0x00FF)
 301 //                                              : Long.toHexString(newClockSequence | 0x8000);
 302 //                              String rangeDesc = Long.toHexString(min | 0x8000) + "-" + Long.toHexString(max | 0x8000);
 303 //                              logger.log(DEBUG, "New clocksequence " + clockDesc + " for thread " + Thread.currentThread().getId()
 304 //                                              + " (in range " + rangeDesc + ")");
 305 //                      }
 306                 }
 307
 308                 private synchronized int getRangeSize() {
 309                         return (int) (max - min);
 310                 }
 311
 312         }
 313
 314 }