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 /**
  19  * A simple base implementation of {@link TimeUuidState}, which maintains
  20  * different clock sequences for each thread.
  21  */
  22 public class ConcurrentTimeUuidState implements UuidFactory.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(TimeUuid.TIMESTAMP_ZERO, startInstant);
  50                 startTimeStamp = TimeUuid.durationToTimestamp(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(TimeUuid.TIMESTAMP_ZERO, Instant.now(clock));
 104                         return TimeUuid.durationToTimestamp(duration);
 105                 } else {
 106                         return startTimeStamp + nowVm();
 107                 }
 108         }
 109
 110         private long nowVm() {
 111                 return System.nanoTime() / 100;
 112         }
 113
 114         @Override
 115         public long getClockSequence() {
 116                 return currentHolder.get().clockSequence;
 117         }
 118
 119         @Override
 120         public long getLastTimestamp() {
 121                 return currentHolder.get().lastTimestamp;
 122         }
 123
 124         public void reset(long nodeIdBase) {
 125                 synchronized (clockSequenceProvider) {
 126                         this.nodeIdBase = nodeIdBase;
 127                         clockSequenceProvider.reset();
 128                         clockSequenceProvider.notifyAll();
 129                 }
 130         }
 131
 132         @Override
 133         public long getLeastSignificantBits() {
 134                 return currentHolder.get().leastSig;
 135         }
 136
 137         @Override
 138         public long getMostSignificantBits() {
 139                 long timestamp = useTimestamp();
 140                 long mostSig = UuidFactory.MOST_SIG_VERSION1 | ((timestamp & 0xFFFFFFFFL) << 32) // time_low
 141                                 | (((timestamp >> 32) & 0xFFFFL) << 16) // time_mid
 142                                 | ((timestamp >> 48) & 0x0FFFL);// time_hi_and_version
 143                 return mostSig;
 144         }
 145
 146         /*
 147          * INTERNAL CLASSSES
 148          */
 149
 150         private class Holder {
 151                 private long lastTimestamp;
 152                 private long clockSequence;
 153                 private long threadId;
 154
 155                 private long leastSig;
 156
 157                 @Override
 158                 public boolean equals(Object obj) {
 159                         boolean isItself = this == obj;
 160                         if (!isItself && clockSequence == ((Holder) obj).clockSequence)
 161                                 throw new IllegalStateException("There is another holder with the same clockSequence " + clockSequence);
 162                         return isItself;
 163                 }
 164
 165                 private void setClockSequence(long clockSequence) {
 166                         this.clockSequence = clockSequence;
 167 //                      if (nodeIdBase == null)
 168 //                              throw new IllegalStateException("Node id base is not initialised");
 169                         this.leastSig = nodeIdBase // already computed node base
 170                                         | (((clockSequence & 0x3F00) >> 8) << 56) // clk_seq_hi_res
 171                                         | ((clockSequence & 0xFF) << 48); // clk_seq_low
 172                 }
 173
 174                 @Override
 175                 public String toString() {
 176                         return "Holder " + clockSequence + ", threadId=" + threadId + ", lastTimestamp=" + lastTimestamp;
 177                 }
 178
 179         }
 180
 181         private static class ClockSequenceProvider {
 182                 private int rangeSize = 256;
 183                 private volatile int min;
 184                 private volatile int max;
 185                 private final AtomicLong counter = new AtomicLong(-1);
 186
 187                 private final SecureRandom secureRandom;
 188
 189                 private final Map<Holder, Long> activeHolders = Collections.synchronizedMap(new WeakHashMap<>());
 190
 191                 ClockSequenceProvider(SecureRandom secureRandom) {
 192                         this.secureRandom = secureRandom;
 193                         reset();
 194                 }
 195
 196                 synchronized void reset() {
 197                         int min = secureRandom.nextInt(ConcurrentTimeUuidState.MAX_CLOCKSEQUENCE - rangeSize);
 198                         int max = min + rangeSize;
 199                         if (min >= max)
 200                                 throw new IllegalArgumentException("Minimum " + min + " is bigger than maximum " + max);
 201                         if (min < 0 || min > MAX_CLOCKSEQUENCE)
 202                                 throw new IllegalArgumentException("Minimum " + min + " is not valid");
 203                         if (max < 0 || max > MAX_CLOCKSEQUENCE)
 204                                 throw new IllegalArgumentException("Maximum " + max + " is not valid");
 205                         this.min = min;
 206                         this.max = max;
 207
 208                         Set<Holder> active = activeHolders.keySet();
 209                         int activeCount = active.size();
 210                         if (activeCount > getRangeSize())
 211                                 throw new IllegalStateException(
 212                                                 "There are too many holders for range [" + min + "," + max + "] : " + activeCount);
 213                         // reset the counter
 214                         counter.set(min);
 215                         for (Holder holder : active) {
 216                                 // save old clocksequence?
 217                                 newClockSequence(holder);
 218                         }
 219                 }
 220
 221                 private synchronized int getRangeSize() {
 222                         return rangeSize;
 223                 }
 224
 225                 private synchronized void newClockSequence(Holder holder) {
 226                         // Too many holders, we will remove the oldes ones
 227                         while (activeHolders.size() > rangeSize) {
 228                                 long oldestTimeStamp = -1;
 229                                 Holder holderToRemove = null;
 230                                 holders: for (Holder h : activeHolders.keySet()) {
 231                                         if (h == holder)// skip the caller
 232                                                 continue holders;
 233
 234                                         if (oldestTimeStamp < 0) {
 235                                                 oldestTimeStamp = h.lastTimestamp;
 236                                                 holderToRemove = h;
 237                                         }
 238                                         if (h.lastTimestamp <= oldestTimeStamp) {
 239                                                 oldestTimeStamp = h.lastTimestamp;
 240                                                 holderToRemove = h;
 241                                         }
 242
 243                                 }
 244                                 assert holderToRemove != null;
 245                                 long oldClockSequence = holderToRemove.clockSequence;
 246                                 holderToRemove.clockSequence = -1;
 247                                 activeHolders.remove(holderToRemove);
 248                                 if (logger.isLoggable(WARNING))
 249                                         logger.log(WARNING, "Removed " + holderToRemove + ", oldClockSequence=" + oldClockSequence);
 250                         }
 251
 252                         long newClockSequence = -1;
 253                         int tryCount = 0;// an explicit exit condition
 254                         do {
 255                                 tryCount++;
 256                                 if (tryCount >= rangeSize)
 257                                         throw new IllegalStateException("No more clock sequence available");
 258
 259                                 newClockSequence = counter.incrementAndGet();
 260                                 assert newClockSequence >= 0 : "Clock sequence cannot be negative";
 261                                 if (newClockSequence > max) {
 262                                         // reset counter
 263                                         newClockSequence = min;
 264                                         counter.set(newClockSequence);
 265                                 }
 266                         } while (activeHolders.containsValue(newClockSequence));
 267                         // TODO use an iterator to check the values
 268                         holder.setClockSequence(newClockSequence);
 269                         activeHolders.put(holder, newClockSequence);
 270                         if (logger.isLoggable(DEBUG))
 271                                 logger.log(DEBUG,
 272                                                 "New clocksequence " + newClockSequence + " for thread " + Thread.currentThread().getId());
 273                 }
 274
 275         }
 276
 277 }