From e846ef84146b66ae543c29c5f17b2991ff0f5973 Mon Sep 17 00:00:00 2001 From: Mathieu Baudier Date: Mon, 24 Jan 2022 11:07:50 +0100 Subject: [PATCH] Improve time based UUID speed and configuration. --- .../api/uuid/AbstractAsyncUuidFactory.java | 64 ++++++----- .../argeo/api/uuid/AbstractUuidFactory.java | 13 ++- .../org/argeo/api/uuid/AsyncUuidFactory.java | 9 -- .../api/uuid/ConcurrentTimeUuidState.java | 66 ++++++++--- .../argeo/api/uuid/ConcurrentUuidFactory.java | 64 +++++++++++ .../argeo/api/uuid/MacAddressUuidFactory.java | 15 +++ .../org/argeo/api/uuid/NodeIdSupplier.java | 20 ++++ .../org/argeo/api/uuid/SimpleUuidFactory.java | 106 ------------------ .../src/org/argeo/api/uuid/TimeUuidState.java | 8 +- .../src/org/argeo/api/uuid/UuidFactory.java | 4 - 10 files changed, 204 insertions(+), 165 deletions(-) create mode 100644 org.argeo.api.uuid/src/org/argeo/api/uuid/ConcurrentUuidFactory.java create mode 100644 org.argeo.api.uuid/src/org/argeo/api/uuid/MacAddressUuidFactory.java create mode 100644 org.argeo.api.uuid/src/org/argeo/api/uuid/NodeIdSupplier.java delete mode 100644 org.argeo.api.uuid/src/org/argeo/api/uuid/SimpleUuidFactory.java diff --git a/org.argeo.api.uuid/src/org/argeo/api/uuid/AbstractAsyncUuidFactory.java b/org.argeo.api.uuid/src/org/argeo/api/uuid/AbstractAsyncUuidFactory.java index 2cdb59f77..f57462388 100644 --- a/org.argeo.api.uuid/src/org/argeo/api/uuid/AbstractAsyncUuidFactory.java +++ b/org.argeo.api.uuid/src/org/argeo/api/uuid/AbstractAsyncUuidFactory.java @@ -20,7 +20,9 @@ import java.util.concurrent.ThreadLocalRandom; */ public abstract class AbstractAsyncUuidFactory extends AbstractUuidFactory implements AsyncUuidFactory { private SecureRandom secureRandom; - protected TimeUuidState timeUuidState; + protected ConcurrentTimeUuidState timeUuidState; + + private NodeIdSupplier nodeIdSupplier; public AbstractAsyncUuidFactory() { secureRandom = newSecureRandom(); @@ -30,11 +32,22 @@ public abstract class AbstractAsyncUuidFactory extends AbstractUuidFactory imple * ABSTRACT METHODS */ - protected abstract UUID newTimeUUID(); + protected abstract SecureRandom newSecureRandom(); - protected abstract UUID newTimeUUIDwithMacAddress(); + /* + * STATE + */ + public void reset() { + if (nodeIdSupplier == null) + throw new IllegalStateException("No node id supplier available"); + long nodeIdBase = nodeIdSupplier.get(); + timeUuidState.reset(nodeIdBase); + } - protected abstract SecureRandom newSecureRandom(); + public void setNodeIdSupplier(NodeIdSupplier nodeIdSupplier) { + this.nodeIdSupplier = nodeIdSupplier; + reset(); + } /* * SYNC OPERATIONS @@ -47,6 +60,22 @@ public abstract class AbstractAsyncUuidFactory extends AbstractUuidFactory imple return newRandomUUID(ThreadLocalRandom.current()); } + protected UUID newTimeUUID() { + if (nodeIdSupplier == null) + throw new IllegalStateException("No node id supplier available"); + UUID uuid = new UUID(timeUuidState.getMostSignificantBits(), timeUuidState.getLeastSignificantBits()); + long clockSequence = timeUuidState.getClockSequence(); + long timestamp = timeUuidState.getLastTimestamp(); + // assert uuid.node() == longFromBytes(node); + assert uuid.timestamp() == timestamp; + assert uuid.clockSequence() == clockSequence + : "uuid.clockSequence()=" + uuid.clockSequence() + " clockSequence=" + clockSequence; + assert uuid.version() == 1; + assert uuid.variant() == 2; + + return uuid; + } + /* * ASYNC OPERATIONS (heavy) */ @@ -74,11 +103,6 @@ public abstract class AbstractAsyncUuidFactory extends AbstractUuidFactory imple return request(futureTimeUUID()); } - @Override - public CompletionStage requestTimeUUIDwithMacAddress() { - return request(futureTimeUUIDwithMacAddress()); - } - /* * ASYNC OPERATIONS (light) */ @@ -105,26 +129,4 @@ public abstract class AbstractAsyncUuidFactory extends AbstractUuidFactory imple public ForkJoinTask futureTimeUUID() { return submit(this::newTimeUUID); } - - @Override - public ForkJoinTask futureTimeUUIDwithMacAddress() { - return submit(this::newTimeUUIDwithMacAddress); - } - -// @Override -// public UUID timeUUID() { -// if (ConcurrentTimeUuidState.isTimeUuidThread.get()) -// return newTimeUUID(); -// else -// return futureTimeUUID().join(); -// } -// -// @Override -// public UUID timeUUIDwithMacAddress() { -// if (ConcurrentTimeUuidState.isTimeUuidThread.get()) -// return newTimeUUIDwithMacAddress(); -// else -// return futureTimeUUIDwithMacAddress().join(); -// } - } diff --git a/org.argeo.api.uuid/src/org/argeo/api/uuid/AbstractUuidFactory.java b/org.argeo.api.uuid/src/org/argeo/api/uuid/AbstractUuidFactory.java index ba2196add..9d829987b 100644 --- a/org.argeo.api.uuid/src/org/argeo/api/uuid/AbstractUuidFactory.java +++ b/org.argeo.api.uuid/src/org/argeo/api/uuid/AbstractUuidFactory.java @@ -272,7 +272,7 @@ public abstract class AbstractUuidFactory implements UuidFactory { return new String(hexChars); } - protected byte[] toNodeId(byte[] source, int offset) { + protected byte[] toNodeIdBytes(byte[] source, int offset) { if (source == null) return null; if (offset < 0 || offset + 6 > source.length) @@ -282,6 +282,17 @@ public abstract class AbstractUuidFactory implements UuidFactory { return nodeId; } +// protected long toNodeIdBase(byte[] node) { +// assert node.length == 6; +// return LEAST_SIG_RFC4122_VARIANT // base for Leach–Salz UUID +// | (node[0] & 0xFFL) // +// | ((node[1] & 0xFFL) << 8) // +// | ((node[2] & 0xFFL) << 16) // +// | ((node[3] & 0xFFL) << 24) // +// | ((node[4] & 0xFFL) << 32) // +// | ((node[5] & 0xFFL) << 40); // +// } + /* * STATIC UTILITIES */ diff --git a/org.argeo.api.uuid/src/org/argeo/api/uuid/AsyncUuidFactory.java b/org.argeo.api.uuid/src/org/argeo/api/uuid/AsyncUuidFactory.java index dd40f81e9..bd92f561e 100644 --- a/org.argeo.api.uuid/src/org/argeo/api/uuid/AsyncUuidFactory.java +++ b/org.argeo.api.uuid/src/org/argeo/api/uuid/AsyncUuidFactory.java @@ -11,12 +11,8 @@ public interface AsyncUuidFactory extends UuidFactory { */ CompletionStage requestTimeUUID(); - CompletionStage requestTimeUUIDwithMacAddress(); - ForkJoinTask futureTimeUUID(); - ForkJoinTask futureTimeUUIDwithMacAddress(); - /* * NAME BASED (version 3 and 5) */ @@ -48,11 +44,6 @@ public interface AsyncUuidFactory extends UuidFactory { return futureTimeUUID().invoke(); } - @Override - default UUID timeUUIDwithMacAddress() { - return futureTimeUUIDwithMacAddress().invoke(); - } - @Override default UUID nameUUIDv5(UUID namespace, byte[] data) { return futureNameUUIDv5(namespace, data).invoke(); 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 1529a3a5d..61f5b8304 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 @@ -8,10 +8,12 @@ import java.security.SecureRandom; import java.time.Clock; import java.time.Duration; import java.time.Instant; +import java.util.Collections; +import java.util.Map; import java.util.Objects; import java.util.Set; import java.util.WeakHashMap; -import java.util.concurrent.atomic.AtomicInteger; +import java.util.concurrent.atomic.AtomicLong; /** * A simple base implementation of {@link TimeUuidState}, which maintains @@ -33,6 +35,8 @@ public class ConcurrentTimeUuidState implements TimeUuidState { private final Clock clock; private final boolean useClockForMeasurement; + private long nodeIdBase; + public ConcurrentTimeUuidState(SecureRandom secureRandom, Clock clock) { useClockForMeasurement = clock != null; this.clock = clock != null ? clock : Clock.systemUTC(); @@ -54,7 +58,7 @@ public class ConcurrentTimeUuidState implements TimeUuidState { protected ConcurrentTimeUuidState.Holder initialValue() { ConcurrentTimeUuidState.Holder value = new ConcurrentTimeUuidState.Holder(); value.threadId = Thread.currentThread().getId(); - value.lastTimestamp = startTimeStamp; + value.lastTimestamp = 0; clockSequenceProvider.newClockSequence(value); return value; } @@ -113,14 +117,48 @@ public class ConcurrentTimeUuidState implements TimeUuidState { @Override public long getClockSequence() { - return (long) currentHolder.get().clockSequence; + return currentHolder.get().clockSequence; } - private static class Holder { + @Override + public long getLastTimestamp() { + return currentHolder.get().lastTimestamp; + } + + public void reset(long nodeIdBase) { + synchronized (clockSequenceProvider) { + this.nodeIdBase = nodeIdBase; + clockSequenceProvider.reset(); + clockSequenceProvider.notifyAll(); + } + } + + @Override + public long getLeastSignificantBits() { + return currentHolder.get().leastSig; + } + + @Override + public long getMostSignificantBits() { + long timestamp = useTimestamp(); + long mostSig = MOST_SIG_VERSION1 // base for version 1 UUID + | ((timestamp & 0xFFFFFFFFL) << 32) // time_low + | (((timestamp >> 32) & 0xFFFFL) << 16) // time_mid + | ((timestamp >> 48) & 0x0FFFL);// time_hi_and_version + return mostSig; + } + + /* + * INTERNAL CLASSSES + */ + + private class Holder { private long lastTimestamp; - private int clockSequence; + private long clockSequence; private long threadId; + private long leastSig; + @Override public boolean equals(Object obj) { boolean isItself = this == obj; @@ -129,8 +167,13 @@ public class ConcurrentTimeUuidState implements TimeUuidState { return isItself; } - private synchronized void setClockSequence(int clockSequence) { + private void setClockSequence(long clockSequence) { this.clockSequence = clockSequence; +// if (nodeIdBase == null) +// throw new IllegalStateException("Node id base is not initialised"); + this.leastSig = nodeIdBase // already computed node base + | (((clockSequence & 0x3F00) >> 8) << 56) // clk_seq_hi_res + | ((clockSequence & 0xFF) << 48); // clk_seq_low } @Override @@ -144,11 +187,11 @@ public class ConcurrentTimeUuidState implements TimeUuidState { private int rangeSize = 256; private volatile int min; private volatile int max; - private final AtomicInteger counter = new AtomicInteger(-1); + private final AtomicLong counter = new AtomicLong(-1); private final SecureRandom secureRandom; - private final WeakHashMap activeHolders = new WeakHashMap<>(); + private final Map activeHolders = Collections.synchronizedMap(new WeakHashMap<>()); ClockSequenceProvider(SecureRandom secureRandom) { this.secureRandom = secureRandom; @@ -185,11 +228,8 @@ public class ConcurrentTimeUuidState implements TimeUuidState { } private synchronized void newClockSequence(Holder holder) { -// int activeCount = activeHolders.size(); + // Too many holders, we will remove the oldes ones 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()) { @@ -214,7 +254,7 @@ public class ConcurrentTimeUuidState implements TimeUuidState { logger.log(WARNING, "Removed " + holderToRemove + ", oldClockSequence=" + oldClockSequence); } - int newClockSequence = -1; + long newClockSequence = -1; int tryCount = 0;// an explicit exit condition do { tryCount++; diff --git a/org.argeo.api.uuid/src/org/argeo/api/uuid/ConcurrentUuidFactory.java b/org.argeo.api.uuid/src/org/argeo/api/uuid/ConcurrentUuidFactory.java new file mode 100644 index 000000000..05b2f05c6 --- /dev/null +++ b/org.argeo.api.uuid/src/org/argeo/api/uuid/ConcurrentUuidFactory.java @@ -0,0 +1,64 @@ +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.DrbgParameters; +import java.security.NoSuchAlgorithmException; +import java.security.SecureRandom; +import java.util.Objects; + +/** + * A configurable implementation of an {@link AsyncUuidFactory}, which can be + * used as a base class for more optimised implementations. + * + * @see https://datatracker.ietf.org/doc/html/rfc4122 + */ +public class ConcurrentUuidFactory extends AbstractAsyncUuidFactory { + private final static Logger logger = System.getLogger(ConcurrentUuidFactory.class.getName()); + +// private byte[] defaultNodeId; + + private Long nodeIdBase; + + public ConcurrentUuidFactory(byte[] nodeId, int offset) { + Objects.requireNonNull(nodeId); + if (offset + 6 > nodeId.length) + throw new IllegalArgumentException("Offset too big: " + offset); + byte[] defaultNodeId = toNodeIdBytes(nodeId, offset); + nodeIdBase = NodeIdSupplier.toNodeIdBase(defaultNodeId); + setNodeIdSupplier(() -> nodeIdBase); + } + + protected ConcurrentUuidFactory() { + + } + + @Override + protected SecureRandom newSecureRandom() { + SecureRandom secureRandom; + try { + secureRandom = SecureRandom.getInstance("DRBG", + DrbgParameters.instantiation(256, DrbgParameters.Capability.PR_AND_RESEED, "UUID".getBytes())); + } catch (NoSuchAlgorithmException e) { + try { + logger.log(DEBUG, "DRBG secure random not found, using strong"); + secureRandom = SecureRandom.getInstanceStrong(); + } catch (NoSuchAlgorithmException e1) { + logger.log(WARNING, "No strong secure random was found, using default"); + secureRandom = new SecureRandom(); + } + } + return secureRandom; + } + + /* + * TIME-BASED (version 1) + */ +// +// @Override +// public UUID newTimeUUID() { +// return newTimeUUID(timeUuidState.useTimestamp(), timeUuidState.getClockSequence(), defaultNodeId, 0); +// } +} diff --git a/org.argeo.api.uuid/src/org/argeo/api/uuid/MacAddressUuidFactory.java b/org.argeo.api.uuid/src/org/argeo/api/uuid/MacAddressUuidFactory.java new file mode 100644 index 000000000..d1ce6ded8 --- /dev/null +++ b/org.argeo.api.uuid/src/org/argeo/api/uuid/MacAddressUuidFactory.java @@ -0,0 +1,15 @@ +package org.argeo.api.uuid; + +public class MacAddressUuidFactory extends ConcurrentUuidFactory { + public final static UuidFactory DEFAULT = new MacAddressUuidFactory(); + + public MacAddressUuidFactory() { + setNodeIdSupplier(() -> { + byte[] hardwareAddress = getHardwareAddress(); + byte[] macAddressNodeId = toNodeIdBytes(hardwareAddress, 0); + long nodeIdBase = NodeIdSupplier.toNodeIdBase(macAddressNodeId); + return nodeIdBase; + }); + } + +} diff --git a/org.argeo.api.uuid/src/org/argeo/api/uuid/NodeIdSupplier.java b/org.argeo.api.uuid/src/org/argeo/api/uuid/NodeIdSupplier.java new file mode 100644 index 000000000..ae9686c70 --- /dev/null +++ b/org.argeo.api.uuid/src/org/argeo/api/uuid/NodeIdSupplier.java @@ -0,0 +1,20 @@ +package org.argeo.api.uuid; + +import java.util.function.Supplier; + +/** A factory for node id base */ +public interface NodeIdSupplier extends Supplier { + long LEAST_SIG_RFC4122_VARIANT = (1l << 63); + + static long toNodeIdBase(byte[] node) { + assert node.length == 6; + return LEAST_SIG_RFC4122_VARIANT // base for Leach–Salz UUID + | (node[0] & 0xFFL) // + | ((node[1] & 0xFFL) << 8) // + | ((node[2] & 0xFFL) << 16) // + | ((node[3] & 0xFFL) << 24) // + | ((node[4] & 0xFFL) << 32) // + | ((node[5] & 0xFFL) << 40); // + } + +} diff --git a/org.argeo.api.uuid/src/org/argeo/api/uuid/SimpleUuidFactory.java b/org.argeo.api.uuid/src/org/argeo/api/uuid/SimpleUuidFactory.java deleted file mode 100644 index 71f8a134c..000000000 --- a/org.argeo.api.uuid/src/org/argeo/api/uuid/SimpleUuidFactory.java +++ /dev/null @@ -1,106 +0,0 @@ -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.DrbgParameters; -import java.security.NoSuchAlgorithmException; -import java.security.SecureRandom; -import java.time.Clock; -import java.util.UUID; - -/** - * Simple implementation of an {@link UuidFactory}, which can be used as a base - * class for more optimised implementations. - * - * @see https://datatracker.ietf.org/doc/html/rfc4122 - */ -public class SimpleUuidFactory extends AbstractAsyncUuidFactory { - private final static Logger logger = System.getLogger(SimpleUuidFactory.class.getName()); - public final static UuidFactory DEFAULT = new SimpleUuidFactory(null, -1, null); - -// private NodeId macAddressNodeId; -// private NodeId defaultNodeId; - private byte[] macAddressNodeId; - private byte[] defaultNodeId; - - public SimpleUuidFactory(byte[] nodeId, int offset, Clock clock) { - byte[] hardwareAddress = getHardwareAddress(); -// macAddressNodeId = hardwareAddress != null ? new NodeId(hardwareAddress, 0) : null; - macAddressNodeId = toNodeId(hardwareAddress, 0); - -// defaultNodeId = nodeId != null ? new NodeId(nodeId, offset) : macAddressNodeId; - defaultNodeId = nodeId != null ? toNodeId(nodeId, offset) : toNodeId(macAddressNodeId, 0); - if (defaultNodeId == null) - throw new IllegalStateException("No default node id specified"); - } - - @Override - protected SecureRandom newSecureRandom() { - SecureRandom secureRandom; - try { - secureRandom = SecureRandom.getInstance("DRBG", - DrbgParameters.instantiation(256, DrbgParameters.Capability.PR_AND_RESEED, "UUID".getBytes())); - } catch (NoSuchAlgorithmException e) { - try { - logger.log(DEBUG, "DRBG secure random not found, using strong"); - secureRandom = SecureRandom.getInstanceStrong(); - } catch (NoSuchAlgorithmException e1) { - logger.log(WARNING, "No strong secure random was found, using default"); - secureRandom = new SecureRandom(); - } - } - return secureRandom; - } - - /* - * TIME-BASED (version 1) - */ - - @Override - public UUID newTimeUUIDwithMacAddress() { - if (macAddressNodeId == null) - throw new UnsupportedOperationException("No MAC address is available"); - return newTimeUUID(timeUuidState.useTimestamp(), timeUuidState.getClockSequence(), macAddressNodeId, 0); - } - - @Override - public UUID newTimeUUID() { - return newTimeUUID(timeUuidState.useTimestamp(), timeUuidState.getClockSequence(), defaultNodeId, 0); - } - - /* - * RANDOM v4 - */ -// @Override -// public UUID randomUUID(Random random) { -// return newRandomUUID(random); -// } - -// @Override -// public UUID randomUUID() { -// return randomUUID(secureRandom); -// } -// -// static class NodeId extends ThreadLocal { -// private byte[] source; -// private int offset; -// -// public NodeId(byte[] source, int offset) { -// Objects.requireNonNull(source); -// this.source = source; -// this.offset = offset; -// if (offset < 0 || offset + 6 > source.length) -// throw new ArrayIndexOutOfBoundsException(offset); -// } -// -// @Override -// protected byte[] initialValue() { -// byte[] value = new byte[6]; -// System.arraycopy(source, offset, value, 0, 6); -// return value; -// } -// -// } -} 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 b926ccb36..780e8ad33 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 @@ -11,14 +11,20 @@ import java.time.ZonedDateTime; * @see https://datatracker.ietf.org/doc/html/rfc4122#section-4.2.1 */ public interface TimeUuidState { + long MOST_SIG_VERSION1 = (1l << 12); + long LEAST_SIG_RFC4122_VARIANT = (1l << 63); /** Start of the Gregorian time, used by time-based UUID (v1). */ final static Instant GREGORIAN_START = ZonedDateTime.of(1582, 10, 15, 0, 0, 0, 0, ZoneOffset.UTC).toInstant(); - long useTimestamp(); + long getLastTimestamp(); long getClockSequence(); + long getLeastSignificantBits(); + + long getMostSignificantBits(); + static boolean isNoMacAddressNodeId(byte[] nodeId) { return (nodeId[0] & 1) != 0; } diff --git a/org.argeo.api.uuid/src/org/argeo/api/uuid/UuidFactory.java b/org.argeo.api.uuid/src/org/argeo/api/uuid/UuidFactory.java index a29706184..78bb402cf 100644 --- a/org.argeo.api.uuid/src/org/argeo/api/uuid/UuidFactory.java +++ b/org.argeo.api.uuid/src/org/argeo/api/uuid/UuidFactory.java @@ -19,15 +19,11 @@ public interface UuidFactory extends Supplier { /* * TIME-BASED (version 1) */ - UUID timeUUID(); - UUID timeUUIDwithMacAddress(); - /* * NAME BASED (version 3 and 5) */ - UUID nameUUIDv5(UUID namespace, byte[] data); UUID nameUUIDv3(UUID namespace, byte[] data); -- 2.30.2