From 38414ed12442720c522f5cb6d89fbdb3010bf2f4 Mon Sep 17 00:00:00 2001 From: Mathieu Baudier Date: Mon, 24 Jan 2022 09:27:01 +0100 Subject: [PATCH] Make time based UUID generation more robust. --- .../api/uuid/ConcurrentTimeUuidState.java | 194 +++++++++++++----- .../src/org/argeo/api/uuid/TimeUuidState.java | 22 -- 2 files changed, 148 insertions(+), 68 deletions(-) diff --git a/org.argeo.api.uuid/src/org/argeo/api/uuid/ConcurrentTimeUuidState.java b/org.argeo.api.uuid/src/org/argeo/api/uuid/ConcurrentTimeUuidState.java index 9a414e8fa..7d5e6013b 100644 --- a/org.argeo.api.uuid/src/org/argeo/api/uuid/ConcurrentTimeUuidState.java +++ b/org.argeo.api.uuid/src/org/argeo/api/uuid/ConcurrentTimeUuidState.java @@ -1,28 +1,30 @@ package org.argeo.api.uuid; +import static java.lang.System.Logger.Level.DEBUG; +import static java.lang.System.Logger.Level.WARNING; + +import java.lang.System.Logger; import java.security.SecureRandom; import java.time.Clock; import java.time.Duration; import java.time.Instant; import java.util.Objects; +import java.util.Set; +import java.util.WeakHashMap; +import java.util.concurrent.atomic.AtomicInteger; /** * A simple base implementation of {@link TimeUuidState}, which maintains * different clock sequences for each thread. */ public class ConcurrentTimeUuidState implements TimeUuidState { -// public final static ThreadLocal isTimeUuidThread = new ThreadLocal<>() { -// -// @Override -// protected Boolean initialValue() { -// return false; -// } -// }; + private final static Logger logger = System.getLogger(ConcurrentTimeUuidState.class.getName()); /** The maximum possible value of the clocksequence. */ private final static int MAX_CLOCKSEQUENCE = 16384; - private final ThreadLocal holder; + private final ClockSequenceProvider clockSequenceProvider; + private final ThreadLocal currentHolder; private final Instant startInstant; /** A start timestamp to which {@link System#nanoTime()}/100 can be added. */ @@ -31,14 +33,11 @@ public class ConcurrentTimeUuidState implements TimeUuidState { private final Clock clock; private final boolean useClockForMeasurement; - private final SecureRandom secureRandom; - public ConcurrentTimeUuidState(SecureRandom secureRandom, Clock clock) { useClockForMeasurement = clock != null; this.clock = clock != null ? clock : Clock.systemUTC(); Objects.requireNonNull(secureRandom); - this.secureRandom = secureRandom; // compute the start reference startInstant = Instant.now(this.clock); @@ -46,15 +45,17 @@ public class ConcurrentTimeUuidState implements TimeUuidState { Duration duration = Duration.between(TimeUuidState.GREGORIAN_START, startInstant); startTimeStamp = durationToUuidTimestamp(duration) - nowVm; + clockSequenceProvider = new ClockSequenceProvider(secureRandom); + // initalise a state per thread - holder = new ThreadLocal<>() { + currentHolder = new ThreadLocal<>() { @Override - protected Holder initialValue() { - Holder value = new Holder(); + protected ConcurrentTimeUuidState.Holder initialValue() { + ConcurrentTimeUuidState.Holder value = new ConcurrentTimeUuidState.Holder(); + value.threadId = Thread.currentThread().getId(); value.lastTimestamp = startTimeStamp; - value.clockSequence = newClockSequence(); -// isTimeUuidThread.set(true); + clockSequenceProvider.newClockSequence(value); return value; } }; @@ -65,22 +66,18 @@ public class ConcurrentTimeUuidState implements TimeUuidState { */ public long useTimestamp() { + Holder holder = currentHolder.get(); + if (holder.clockSequence < 0) { + clockSequenceProvider.newClockSequence(holder); + } - long previousTimestamp = holder.get().lastTimestamp; + long previousTimestamp = holder.lastTimestamp; long now = computeNow(); // rare case where we are sooner // (e.g. if system time has changed in between and we use the clock) if (previousTimestamp > now) { - long newClockSequence = newClockSequence(); - for (int i = 0; i < 64; i++) { - if (newClockSequence != holder.get().clockSequence) - break; - newClockSequence = newClockSequence(); - } - if (newClockSequence != holder.get().clockSequence) - throw new IllegalStateException("Cannot change clock sequence"); - holder.get().clockSequence = newClockSequence; + clockSequenceProvider.newClockSequence(holder); } // very unlikely case where it took less than 100ns between both @@ -93,11 +90,11 @@ public class ConcurrentTimeUuidState implements TimeUuidState { now = computeNow(); assert previousTimestamp != now; } - holder.get().lastTimestamp = now; + holder.lastTimestamp = now; return now; } - protected long computeNow() { + private long computeNow() { if (useClockForMeasurement) { Duration duration = Duration.between(TimeUuidState.GREGORIAN_START, Instant.now(clock)); return durationToUuidTimestamp(duration); @@ -110,31 +107,136 @@ public class ConcurrentTimeUuidState implements TimeUuidState { return System.nanoTime() / 100; } - protected long durationToUuidTimestamp(Duration duration) { + private long durationToUuidTimestamp(Duration duration) { return (duration.getSeconds() * 10000000 + duration.getNano() / 100); } - /* - * STATE OPERATIONS - */ + @Override + public long getClockSequence() { + return (long) currentHolder.get().clockSequence; + } + + private static class Holder { + private long lastTimestamp; + private int clockSequence; + private long threadId; + + @Override + public boolean equals(Object obj) { + boolean isItself = this == obj; + if (!isItself && clockSequence == ((Holder) obj).clockSequence) + throw new IllegalStateException("There is another holder with the same clockSequence " + clockSequence); + return isItself; + } + + private synchronized void setClockSequence(int clockSequence) { + this.clockSequence = clockSequence; + } + + @Override + public String toString() { + return "Holder " + clockSequence + ", threadId=" + threadId + ", lastTimestamp=" + lastTimestamp; + } - protected long newClockSequence() { - return secureRandom.nextInt(ConcurrentTimeUuidState.MAX_CLOCKSEQUENCE); } - /* - * ACCESSORS - */ + private static class ClockSequenceProvider { + private int rangeSize = 256; + private volatile int min; + private volatile int max; + private final AtomicInteger counter = new AtomicInteger(-1); -// @Override -// public byte[] getNodeId() { -// byte[] arr = new byte[6]; -// System.arraycopy(holder.get().nodeId, 0, arr, 0, 6); -// return arr; -// } + private final SecureRandom secureRandom; + + private final WeakHashMap activeHolders = new WeakHashMap<>(); + + ClockSequenceProvider(SecureRandom secureRandom) { + this.secureRandom = secureRandom; + reset(); + } + + synchronized void reset() { + int min = secureRandom.nextInt(ConcurrentTimeUuidState.MAX_CLOCKSEQUENCE); + int max = min + rangeSize; + if (min >= max) + throw new IllegalArgumentException("Minimum " + min + " is bigger than maximum " + max); + if (min < 0 || min > MAX_CLOCKSEQUENCE) + throw new IllegalArgumentException("Minimum " + min + " is not valid"); + if (max < 0 || max > MAX_CLOCKSEQUENCE) + throw new IllegalArgumentException("Maximum " + max + " is not valid"); + this.min = min; + this.max = max; + + Set active = activeHolders.keySet(); + int activeCount = active.size(); + if (activeCount > getRangeSize()) + throw new IllegalStateException( + "There are too many holders for range [" + min + "," + max + "] : " + activeCount); + // reset the counter + counter.set(min); + for (Holder holder : active) { + // save old clocksequence? + newClockSequence(holder); + } + } + + private synchronized int getRangeSize() { + return rangeSize; + } + + private synchronized void newClockSequence(Holder holder) { +// int activeCount = activeHolders.size(); + while (activeHolders.size() > rangeSize) { +// throw new IllegalStateException( +// "There are too many holders for range [" + min + "," + max + "] : " + activeCount); + // remove oldest + long oldestTimeStamp = -1; + Holder holderToRemove = null; + holders: for (Holder h : activeHolders.keySet()) { + if (h == holder)// skip the caller + continue holders; + + if (oldestTimeStamp < 0) { + oldestTimeStamp = h.lastTimestamp; + holderToRemove = h; + } + if (h.lastTimestamp <= oldestTimeStamp) { + oldestTimeStamp = h.lastTimestamp; + holderToRemove = h; + } + + } + assert holderToRemove != null; + long oldClockSequence = holderToRemove.clockSequence; + holderToRemove.clockSequence = -1; + activeHolders.remove(holderToRemove); + if (logger.isLoggable(WARNING)) + logger.log(WARNING, "Removed " + holderToRemove + ", oldClockSequence=" + oldClockSequence); + } + + int newClockSequence = -1; + int tryCount = 0;// an explicit exit condition + do { + tryCount++; + if (tryCount >= rangeSize) + throw new IllegalStateException("No more clock sequence available"); + + newClockSequence = counter.incrementAndGet(); + assert newClockSequence >= 0 : "Clock sequence cannot be negative"; + if (newClockSequence > max) { + // reset counter + newClockSequence = min; + counter.set(newClockSequence); + } + } while (activeHolders.containsValue(newClockSequence)); + // TODO use an iterator to check the values + holder.setClockSequence(newClockSequence); + activeHolders.put(holder, newClockSequence); + if (logger.isLoggable(DEBUG)) + logger.log(DEBUG, + "New clocksequence " + newClockSequence + " for thread " + Thread.currentThread().getId()); + } - @Override - public long getClockSequence() { - return holder.get().clockSequence; } + } diff --git a/org.argeo.api.uuid/src/org/argeo/api/uuid/TimeUuidState.java b/org.argeo.api.uuid/src/org/argeo/api/uuid/TimeUuidState.java index 4c9eec5a6..b926ccb36 100644 --- a/org.argeo.api.uuid/src/org/argeo/api/uuid/TimeUuidState.java +++ b/org.argeo.api.uuid/src/org/argeo/api/uuid/TimeUuidState.java @@ -22,26 +22,4 @@ public interface TimeUuidState { static boolean isNoMacAddressNodeId(byte[] nodeId) { return (nodeId[0] & 1) != 0; } - - static class Holder { - long lastTimestamp; - long clockSequence; - - public long getLastTimestamp() { - return lastTimestamp; - } - - public void setLastTimestamp(long lastTimestamp) { - this.lastTimestamp = lastTimestamp; - } - - public long getClockSequence() { - return clockSequence; - } - - public void setClockSequence(long clockSequence) { - this.clockSequence = clockSequence; - } - - } } -- 2.30.2