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 /**
  19  * A simple base implementation of {@link TimeUuidState}, which maintains
  20  * different clock sequences for each thread.
  21  */
  22 public class ConcurrentTimeUuidState implements TimeUuidState {
  23         private final static Logger logger = System.getLogger(ConcurrentTimeUuidState.class.getName());
  24
  25         /** The maximum possible value of the clocksequence. */
  26         private final static int MAX_CLOCKSEQUENCE = 16384;
  27
  28         private final ClockSequenceProvider clockSequenceProvider;
  29         private final ThreadLocal<ConcurrentTimeUuidState.Holder> currentHolder;
  30
  31         private final Instant startInstant;
  32         /** A start timestamp to which {@link System#nanoTime()}/100 can be added. */
  33         private final long startTimeStamp;
  34
  35         private final Clock clock;
  36         private final boolean useClockForMeasurement;
  37
  38         private long nodeIdBase;
  39
  40         public ConcurrentTimeUuidState(SecureRandom secureRandom, Clock clock) {
  41                 useClockForMeasurement = clock != null;
  42                 this.clock = clock != null ? clock : Clock.systemUTC();
  43
  44                 Objects.requireNonNull(secureRandom);
  45
  46                 // compute the start reference
  47                 startInstant = Instant.now(this.clock);
  48                 long nowVm = nowVm();
  49                 Duration duration = Duration.between(TimeUuidState.GREGORIAN_START, startInstant);
  50                 startTimeStamp = durationToUuidTimestamp(duration) - nowVm;
  51
  52                 clockSequenceProvider = new ClockSequenceProvider(secureRandom);
  53
  54                 // initalise a state per thread
  55                 currentHolder = new ThreadLocal<>() {
  56
  57                         @Override
  58                         protected ConcurrentTimeUuidState.Holder initialValue() {
  59                                 ConcurrentTimeUuidState.Holder value = new ConcurrentTimeUuidState.Holder();
  60                                 value.threadId = Thread.currentThread().getId();
  61                                 value.lastTimestamp = 0;
  62                                 clockSequenceProvider.newClockSequence(value);
  63                                 return value;
  64                         }
  65                 };
  66         }
  67
  68         /*
  69          * TIME OPERATIONS
  70          */
  71
  72         public long useTimestamp() {
  73                 Holder holder = currentHolder.get();
  74                 if (holder.clockSequence < 0) {
  75                         clockSequenceProvider.newClockSequence(holder);
  76                 }
  77
  78                 long previousTimestamp = holder.lastTimestamp;
  79                 long now = computeNow();
  80
  81                 // rare case where we are sooner
  82                 // (e.g. if system time has changed in between and we use the clock)
  83                 if (previousTimestamp > now) {
  84                         clockSequenceProvider.newClockSequence(holder);
  85                 }
  86
  87                 // very unlikely case where it took less than 100ns between both
  88                 if (previousTimestamp == now) {
  89                         try {
  90                                 Thread.sleep(0, 100);
  91                         } catch (InterruptedException e) {
  92                                 // silent
  93                         }
  94                         now = computeNow();
  95                         assert previousTimestamp != now;
  96                 }
  97                 holder.lastTimestamp = now;
  98                 return now;
  99         }
 100
 101         private long computeNow() {
 102                 if (useClockForMeasurement) {
 103                         Duration duration = Duration.between(TimeUuidState.GREGORIAN_START, Instant.now(clock));
 104                         return durationToUuidTimestamp(duration);
 105                 } else {
 106                         return startTimeStamp + nowVm();
 107                 }
 108         }
 109
 110         private long nowVm() {
 111                 return System.nanoTime() / 100;
 112         }
 113
 114         private long durationToUuidTimestamp(Duration duration) {
 115                 return (duration.getSeconds() * 10000000 + duration.getNano() / 100);
 116         }
 117
 118         @Override
 119         public long getClockSequence() {
 120                 return currentHolder.get().clockSequence;
 121         }
 122
 123         @Override
 124         public long getLastTimestamp() {
 125                 return currentHolder.get().lastTimestamp;
 126         }
 127
 128         public void reset(long nodeIdBase) {
 129                 synchronized (clockSequenceProvider) {
 130                         this.nodeIdBase = nodeIdBase;
 131                         clockSequenceProvider.reset();
 132                         clockSequenceProvider.notifyAll();
 133                 }
 134         }
 135
 136         @Override
 137         public long getLeastSignificantBits() {
 138                 return currentHolder.get().leastSig;
 139         }
 140
 141         @Override
 142         public long getMostSignificantBits() {
 143                 long timestamp = useTimestamp();
 144                 long mostSig = MOST_SIG_VERSION1 // base for version 1 UUID
 145                                 | ((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
 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 //                      if (nodeIdBase == null)
 173 //                              throw new IllegalStateException("Node id base is not initialised");
 174                         this.leastSig = nodeIdBase // already computed node base
 175                                         | (((clockSequence & 0x3F00) >> 8) << 56) // clk_seq_hi_res
 176                                         | ((clockSequence & 0xFF) << 48); // clk_seq_low
 177                 }
 178
 179                 @Override
 180                 public String toString() {
 181                         return "Holder " + clockSequence + ", threadId=" + threadId + ", lastTimestamp=" + lastTimestamp;
 182                 }
 183
 184         }
 185
 186         private static class ClockSequenceProvider {
 187                 private int rangeSize = 256;
 188                 private volatile int min;
 189                 private volatile int 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();
 199                 }
 200
 201                 synchronized void reset() {
 202                         int min = secureRandom.nextInt(ConcurrentTimeUuidState.MAX_CLOCKSEQUENCE - rangeSize);
 203                         int max = min + rangeSize;
 204                         if (min >= max)
 205                                 throw new IllegalArgumentException("Minimum " + min + " is bigger than maximum " + max);
 206                         if (min < 0 || min > MAX_CLOCKSEQUENCE)
 207                                 throw new IllegalArgumentException("Minimum " + min + " is not valid");
 208                         if (max < 0 || max > MAX_CLOCKSEQUENCE)
 209                                 throw new IllegalArgumentException("Maximum " + max + " is not valid");
 210                         this.min = min;
 211                         this.max = max;
 212
 213                         Set<Holder> active = activeHolders.keySet();
 214                         int activeCount = active.size();
 215                         if (activeCount > getRangeSize())
 216                                 throw new IllegalStateException(
 217                                                 "There are too many holders for range [" + min + "," + max + "] : " + activeCount);
 218                         // reset the counter
 219                         counter.set(min);
 220                         for (Holder holder : active) {
 221                                 // save old clocksequence?
 222                                 newClockSequence(holder);
 223                         }
 224                 }
 225
 226                 private synchronized int getRangeSize() {
 227                         return rangeSize;
 228                 }
 229
 230                 private synchronized void newClockSequence(Holder holder) {
 231                         // Too many holders, we will remove the oldes ones
 232                         while (activeHolders.size() > rangeSize) {
 233                                 long oldestTimeStamp = -1;
 234                                 Holder holderToRemove = null;
 235                                 holders: for (Holder h : activeHolders.keySet()) {
 236                                         if (h == holder)// skip the caller
 237                                                 continue holders;
 238
 239                                         if (oldestTimeStamp < 0) {
 240                                                 oldestTimeStamp = h.lastTimestamp;
 241                                                 holderToRemove = h;
 242                                         }
 243                                         if (h.lastTimestamp <= oldestTimeStamp) {
 244                                                 oldestTimeStamp = h.lastTimestamp;
 245                                                 holderToRemove = h;
 246                                         }
 247
 248                                 }
 249                                 assert holderToRemove != null;
 250                                 long oldClockSequence = holderToRemove.clockSequence;
 251                                 holderToRemove.clockSequence = -1;
 252                                 activeHolders.remove(holderToRemove);
 253                                 if (logger.isLoggable(WARNING))
 254                                         logger.log(WARNING, "Removed " + holderToRemove + ", oldClockSequence=" + oldClockSequence);
 255                         }
 256
 257                         long newClockSequence = -1;
 258                         int tryCount = 0;// an explicit exit condition
 259                         do {
 260                                 tryCount++;
 261                                 if (tryCount >= rangeSize)
 262                                         throw new IllegalStateException("No more clock sequence available");
 263
 264                                 newClockSequence = counter.incrementAndGet();
 265                                 assert newClockSequence >= 0 : "Clock sequence cannot be negative";
 266                                 if (newClockSequence > max) {
 267                                         // reset counter
 268                                         newClockSequence = min;
 269                                         counter.set(newClockSequence);
 270                                 }
 271                         } while (activeHolders.containsValue(newClockSequence));
 272                         // TODO use an iterator to check the values
 273                         holder.setClockSequence(newClockSequence);
 274                         activeHolders.put(holder, newClockSequence);
 275                         if (logger.isLoggable(DEBUG))
 276                                 logger.log(DEBUG,
 277                                                 "New clocksequence " + newClockSequence + " for thread " + Thread.currentThread().getId());
 278                 }
 279
 280         }
 281
 282 }