api/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.Objects;
  12 import java.util.Set;
  13 import java.util.WeakHashMap;
  14 import java.util.concurrent.atomic.AtomicInteger;
  15
  16 /**
  17  * A simple base implementation of {@link TimeUuidState}, which maintains
  18  * different clock sequences for each thread.
  19  */
  20 public class ConcurrentTimeUuidState implements TimeUuidState {
  21         private final static Logger logger = System.getLogger(ConcurrentTimeUuidState.class.getName());
  22
  23         /** The maximum possible value of the clocksequence. */
  24         private final static int MAX_CLOCKSEQUENCE = 16384;
  25
  26         private final ClockSequenceProvider clockSequenceProvider;
  27         private final ThreadLocal<ConcurrentTimeUuidState.Holder> currentHolder;
  28
  29         private final Instant startInstant;
  30         /** A start timestamp to which {@link System#nanoTime()}/100 can be added. */
  31         private final long startTimeStamp;
  32
  33         private final Clock clock;
  34         private final boolean useClockForMeasurement;
  35
  36         public ConcurrentTimeUuidState(SecureRandom secureRandom, Clock clock) {
  37                 useClockForMeasurement = clock != null;
  38                 this.clock = clock != null ? clock : Clock.systemUTC();
  39
  40                 Objects.requireNonNull(secureRandom);
  41
  42                 // compute the start reference
  43                 startInstant = Instant.now(this.clock);
  44                 long nowVm = nowVm();
  45                 Duration duration = Duration.between(TimeUuidState.GREGORIAN_START, startInstant);
  46                 startTimeStamp = durationToUuidTimestamp(duration) - nowVm;
  47
  48                 clockSequenceProvider = new ClockSequenceProvider(secureRandom);
  49
  50                 // initalise a state per thread
  51                 currentHolder = new ThreadLocal<>() {
  52
  53                         @Override
  54                         protected ConcurrentTimeUuidState.Holder initialValue() {
  55                                 ConcurrentTimeUuidState.Holder value = new ConcurrentTimeUuidState.Holder();
  56                                 value.threadId = Thread.currentThread().getId();
  57                                 value.lastTimestamp = startTimeStamp;
  58                                 clockSequenceProvider.newClockSequence(value);
  59                                 return value;
  60                         }
  61                 };
  62         }
  63
  64         /*
  65          * TIME OPERATIONS
  66          */
  67
  68         public long useTimestamp() {
  69                 Holder holder = currentHolder.get();
  70                 if (holder.clockSequence < 0) {
  71                         clockSequenceProvider.newClockSequence(holder);
  72                 }
  73
  74                 long previousTimestamp = holder.lastTimestamp;
  75                 long now = computeNow();
  76
  77                 // rare case where we are sooner
  78                 // (e.g. if system time has changed in between and we use the clock)
  79                 if (previousTimestamp > now) {
  80                         clockSequenceProvider.newClockSequence(holder);
  81                 }
  82
  83                 // very unlikely case where it took less than 100ns between both
  84                 if (previousTimestamp == now) {
  85                         try {
  86                                 Thread.sleep(0, 100);
  87                         } catch (InterruptedException e) {
  88                                 // silent
  89                         }
  90                         now = computeNow();
  91                         assert previousTimestamp != now;
  92                 }
  93                 holder.lastTimestamp = now;
  94                 return now;
  95         }
  96
  97         private long computeNow() {
  98                 if (useClockForMeasurement) {
  99                         Duration duration = Duration.between(TimeUuidState.GREGORIAN_START, Instant.now(clock));
 100                         return durationToUuidTimestamp(duration);
 101                 } else {
 102                         return startTimeStamp + nowVm();
 103                 }
 104         }
 105
 106         private long nowVm() {
 107                 return System.nanoTime() / 100;
 108         }
 109
 110         private long durationToUuidTimestamp(Duration duration) {
 111                 return (duration.getSeconds() * 10000000 + duration.getNano() / 100);
 112         }
 113
 114         @Override
 115         public long getClockSequence() {
 116                 return (long) currentHolder.get().clockSequence;
 117         }
 118
 119         private static class Holder {
 120                 private long lastTimestamp;
 121                 private int clockSequence;
 122                 private long threadId;
 123
 124                 @Override
 125                 public boolean equals(Object obj) {
 126                         boolean isItself = this == obj;
 127                         if (!isItself && clockSequence == ((Holder) obj).clockSequence)
 128                                 throw new IllegalStateException("There is another holder with the same clockSequence " + clockSequence);
 129                         return isItself;
 130                 }
 131
 132                 private synchronized void setClockSequence(int clockSequence) {
 133                         this.clockSequence = clockSequence;
 134                 }
 135
 136                 @Override
 137                 public String toString() {
 138                         return "Holder " + clockSequence + ", threadId=" + threadId + ", lastTimestamp=" + lastTimestamp;
 139                 }
 140
 141         }
 142
 143         private static class ClockSequenceProvider {
 144                 private int rangeSize = 256;
 145                 private volatile int min;
 146                 private volatile int max;
 147                 private final AtomicInteger counter = new AtomicInteger(-1);
 148
 149                 private final SecureRandom secureRandom;
 150
 151                 private final WeakHashMap<Holder, Integer> activeHolders = new WeakHashMap<>();
 152
 153                 ClockSequenceProvider(SecureRandom secureRandom) {
 154                         this.secureRandom = secureRandom;
 155                         reset();
 156                 }
 157
 158                 synchronized void reset() {
 159                         int min = secureRandom.nextInt(ConcurrentTimeUuidState.MAX_CLOCKSEQUENCE);
 160                         int max = min + rangeSize;
 161                         if (min >= max)
 162                                 throw new IllegalArgumentException("Minimum " + min + " is bigger than maximum " + max);
 163                         if (min < 0 || min > MAX_CLOCKSEQUENCE)
 164                                 throw new IllegalArgumentException("Minimum " + min + " is not valid");
 165                         if (max < 0 || max > MAX_CLOCKSEQUENCE)
 166                                 throw new IllegalArgumentException("Maximum " + max + " is not valid");
 167                         this.min = min;
 168                         this.max = max;
 169
 170                         Set<Holder> active = activeHolders.keySet();
 171                         int activeCount = active.size();
 172                         if (activeCount > getRangeSize())
 173                                 throw new IllegalStateException(
 174                                                 "There are too many holders for range [" + min + "," + max + "] : " + activeCount);
 175                         // reset the counter
 176                         counter.set(min);
 177                         for (Holder holder : active) {
 178                                 // save old clocksequence?
 179                                 newClockSequence(holder);
 180                         }
 181                 }
 182
 183                 private synchronized int getRangeSize() {
 184                         return rangeSize;
 185                 }
 186
 187                 private synchronized void newClockSequence(Holder holder) {
 188 //                      int activeCount = activeHolders.size();
 189                         while (activeHolders.size() > rangeSize) {
 190 //                              throw new IllegalStateException(
 191 //                                              "There are too many holders for range [" + min + "," + max + "] : " + activeCount);
 192                                 // remove oldest
 193                                 long oldestTimeStamp = -1;
 194                                 Holder holderToRemove = null;
 195                                 holders: for (Holder h : activeHolders.keySet()) {
 196                                         if (h == holder)// skip the caller
 197                                                 continue holders;
 198
 199                                         if (oldestTimeStamp < 0) {
 200                                                 oldestTimeStamp = h.lastTimestamp;
 201                                                 holderToRemove = h;
 202                                         }
 203                                         if (h.lastTimestamp <= oldestTimeStamp) {
 204                                                 oldestTimeStamp = h.lastTimestamp;
 205                                                 holderToRemove = h;
 206                                         }
 207
 208                                 }
 209                                 assert holderToRemove != null;
 210                                 long oldClockSequence = holderToRemove.clockSequence;
 211                                 holderToRemove.clockSequence = -1;
 212                                 activeHolders.remove(holderToRemove);
 213                                 if (logger.isLoggable(WARNING))
 214                                         logger.log(WARNING, "Removed " + holderToRemove + ", oldClockSequence=" + oldClockSequence);
 215                         }
 216
 217                         int newClockSequence = -1;
 218                         int tryCount = 0;// an explicit exit condition
 219                         do {
 220                                 tryCount++;
 221                                 if (tryCount >= rangeSize)
 222                                         throw new IllegalStateException("No more clock sequence available");
 223
 224                                 newClockSequence = counter.incrementAndGet();
 225                                 assert newClockSequence >= 0 : "Clock sequence cannot be negative";
 226                                 if (newClockSequence > max) {
 227                                         // reset counter
 228                                         newClockSequence = min;
 229                                         counter.set(newClockSequence);
 230                                 }
 231                         } while (activeHolders.containsValue(newClockSequence));
 232                         // TODO use an iterator to check the values
 233                         holder.setClockSequence(newClockSequence);
 234                         activeHolders.put(holder, newClockSequence);
 235                         if (logger.isLoggable(DEBUG))
 236                                 logger.log(DEBUG,
 237                                                 "New clocksequence " + newClockSequence + " for thread " + Thread.currentThread().getId());
 238                 }
 239
 240         }
 241
 242 }