10000 Monotonic sorting for UUID Variant 7 · cowtowncoder/java-uuid-generator@5563381 · GitHub
[go: up one dir, main page]
Skip to content

Commit 5563381

Browse files
HellblazerHellblazer
committed
Monotonic sorting for UUID Variant 7
1 parent 80512a1 commit 5563381

File tree

4 files changed

+73
-33
lines changed

4 files changed

+73
-33
lines changed

‎src/main/java/com/fasterxml/uuid/Generators.java

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -128,10 +128,8 @@ public static TimeBasedEpochGenerator timeBasedEpochGenerator()
128128

129129
/**
130130
* Factory method for constructing UUID generator that generates UUID using
131-
* variant 7 (time+random based), using specified Ethernet address
132-
* as the location part of UUID.
133-
* No additional external synchronization is used.
134-
*/
131+
* variant 7 (Unix Epoch time+random based).
132+
*/
135133
public static TimeBasedEpochGenerator timeBasedEpochGenerator(Random random)
136134
{
137135
return new TimeBasedEpochGenerator(random);

‎src/main/java/com/fasterxml/uuid/impl/TimeBasedEpochGenerator.java

Lines changed: 34 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -3,8 +3,10 @@
33
import java.security.SecureRandom;
44
import java.util.Random;
55
import java.util.UUID;
6+
import java.util.concurrent.locks.Lock;
7+
import java.util.concurrent.locks.ReentrantLock;
68

7-
import com.fasterxml.uuid.NoArgGenerator;
9+
import com.fasterxml.uuid.NoArgGenerator;
810
import com.fasterxml.uuid.UUIDType;
911

1012
/**
@@ -22,7 +24,9 @@
2224
* @since 4.1
2325
*/
2426
public class TimeBasedEpochGenerator extends NoArgGenerator
25-
{
27+
{
28+
private static final int ENTROPY_BYTE_LENGTH = 10;
29+
2630
/*
2731
/**********************************************************************
2832
/* Configuration
@@ -33,6 +37,9 @@ public class TimeBasedEpochGenerator extends NoArgGenerator
3337
* Random number generator that this generator uses.
3438
*/
3539
protected final Random _random;
40+
private long _lastTimestamp = -1;
41+
private final byte[] _lastEntropy = new byte[ENTROPY_BYTE_LENGTH];
42+
private final Lock lock = new ReentrantLock();
3643

3744
/*
3845
/**********************************************************************
@@ -69,25 +76,34 @@ public TimeBasedEpochGenerator(Random rnd)
6976
/* UUID generation
7077
/**********************************************************************
7178
*/
72-
79+
7380
@Override
7481
public UUID generate()
7582
{
76-
final long rawTimestamp = System.currentTimeMillis();
77-
final byte[] rnd = new byte[10];
78-
_random.nextBytes(rnd);
79-
80-
// Use only 48 lowest bits as per spec, next 16 bit from random
81-
// (note: UUIDUtil.constuctUUID will add "version" so it's only 12
82-
// actual random bits)
83-
long l1 = (rawTimestamp << 16) | _toShort(rnd, 8);
84-
85-
// And then the other 64 bits of random; likewise UUIDUtil.constructUUID
86-
// will overwrite first 2 random bits so it's "only" 62 bits
87-
long l2 = _toLong(rnd, 0);
88-
89-
// and as per above, this call fills in "variant" and "version" bits
90-
return UUIDUtil.constructUUID(UUIDType.TIME_BASED_EPOCH, l1, l2);
83+
lock.lock();
84+
try {
85+
long rawTimestamp = System.currentTimeMillis();
86+
if (rawTimestamp == _lastTimestamp) {
87+
boolean c = true;
88+
for (int i = ENTROPY_BYTE_LENGTH - 1; i >= 0; i--) {
89+
if (c) {
90+
byte temp = _lastEntropy[i];
91+
temp = (byte) (temp + 0x01);
92+
c = _lastEntropy[i] == (byte) 0xff && c;
93+
_lastEntropy[i] = temp;
94+
}
95+
}
96+
if (c) {
97+
throw new IllegalStateException("overflow on same millisecond");
98+
}
99+
} else {
100+
_lastTimestamp = rawTimestamp;
101+
_random.nextBytes(_lastEntropy);
102+
}
103+
return UUIDUtil.constructUUID(UUIDType.TIME_BASED_EPOCH, (rawTimestamp << 16) | _toShort(_lastEntropy, 0), _toLong(_lastEntropy, 2));
104+
} finally {
105+
lock.unlock();
106+
}
91107
}
92108

93109
/*

‎src/test/java/com/fasterxml/uuid/UUIDComparatorTest.java

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,8 +14,14 @@
1414
*/
1515
package com.fasterxml.uuid;
1616

17+
import java.util.ArrayList;
18+
import java.util.HashSet;
19+
import java.util.List;
20+
import java.util.Random;
1721
import java.util.UUID;
1822

23+
import com.fasterxml.uuid.impl.TimeBasedEpochGenerator;
24+
1925
import junit.framework.TestCase;
2026

2127
public class UUIDComparatorTest
@@ -100,4 +106,24 @@ public void testSorting()
100106
}
101107
}
102108
}
109+
110+
public void testSortingMV7() throws Exception {
111+
final int count = 10000000;
112+
Random entropy = new Random(0x666);
113+
final TimeBasedEpochGenerator generator = Generators.timeBasedEpochGenerator(entropy);
114+
List<UUID> created = new ArrayList<UUID>(count);
115+
for (int i = 0; i < count; i++) {
116+
created.add(generator.generate());
117+
}
118+
List<UUID> sortedUUID = new ArrayList<UUID>(created);
119+
sortedUUID.sort(new UUIDComparator());
120+
HashSet<UUID> unique = new HashSet<UUID>(count);
121+
122+
for (int i = 0; i < created.size(); i++) {
123+
assertEquals("Error at: " + i, created.get(i), sortedUUID.get(i));
124+
if (!unique.add(created.get(i))) {
125+
System.out.println("Duplicate at: " + i);
126+
}
127+
}
128+
}
103129
}

‎src/test/java/com/fasterxml/uuid/UUIDGeneratorTest.java

Lines changed: 11 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -250,13 +250,15 @@ public void testV7value()
250250
* Test of generateTimeBasedEpochUUID() method,
251251
* of class com.fasterxml.uuid.UUIDGenerator.
252252
*/
253-
public void testGenerateTimeBasedEpochUUID()
253+
public void testGenerateTimeBasedEpochUUID() throws Exception
254254
{
255255
// this test will attempt to check for reasonable behavior of the
256256
// generateTimeBasedUUID method
257+
258+
Random entropy = new Random(0x666);
257259

258260
// we need a instance to use
259-
TimeBasedEpochGenerator uuid_gen = Generators.timeBasedEpochGenerator();
261+
TimeBasedEpochGenerator uuid_gen = Generators.timeBasedEpochGenerator(entropy);
260262

261263
// first check that given a number of calls to generateTimeBasedEpochUUID,
262264
// all returned UUIDs order after the last returned UUID
@@ -268,14 +270,16 @@ public void testGenerateTimeBasedEpochUUID()
268270

269271
// before we generate all the uuids, lets get the start time
270272
long start_time = System.currentTimeMillis();
273+
Thread.sleep(2); // Clean start time
271274

272275
// now create the array of uuids
273276
for (int i = 0; i < uuid_array.length; i++) {
274277
uuid_array[i] = uuid_gen.generate();
275278
}
276-
279+
277280
// now capture the end time
278281
long end_time = System.currentTimeMillis();
282+
Thread.sleep(2); // Clean end time
279283

280284
// check that none of the UUIDs are null
281285
checkUUIDArrayForNonNullUUIDs(uuid_array);
@@ -284,7 +288,7 @@ public void testGenerateTimeBasedEpochUUID()
284288
checkUUIDArrayForCorrectVariantAndVersion(uuid_array, UUIDType.TIME_BASED_EPOCH);
285289

286290
// check that all the uuids were generated with correct order
287-
// checkUUIDArrayForCorrectOrdering(uuid_array);
291+
checkUUIDArrayForCorrectOrdering(uuid_array);
288292

289293
// check that all uuids were unique
290294
checkUUIDArrayForUniqueness(uuid_array);
@@ -757,26 +761,22 @@ private void checkUUIDArrayForCorrectCreationTimeReorder(UUID[] uuidArray,
757761
}
758762
}
759763

760-
// Modified version for Variant 7 (Unix Epoch timestamps)
764+
// Modified version for Variant 7 (Unix Epoch monotonic timestamps)
761765
private void checkUUIDArrayForCorrectCreationTimeEpoch(UUID[] uuidArray,
762766
long startTime, long endTime)
763767
{
764-
765-
// 21-Feb-2020, tatu: Not sure why this would be checked, as timestamps come
766-
// from
767-
// System.currenTimeMillis()...
768768
assertTrue("Start time: " + startTime + " was after the end time: " + endTime, startTime <= endTime);
769769

770770
// let's check that all uuids in the array have a timestamp which lands
771771
// between the start and end time
772772
for (int i = 0; i < uuidArray.length; i++) {
773773
byte[] temp_uuid = UUIDUtil.asByteArray(uuidArray[i]);
774774
ByteBuffer buff = ByteBuffer.wrap(temp_uuid);
775-
long uuid_time = buff.getLong() >>> 16;
775+
final long uuid_time = buff.getLong() >>> 16;
776776
// now check that the times are correct
777777
assertTrue("Start time: " + startTime + " was not before UUID timestamp: " + uuid_time,
778778
startTime <= uuid_time);
779-
assertTrue("UUID timestamp: " + uuid_time + " was not before the end time: " + endTime,
779+
assertTrue("UUID: " + i + " timestamp: " + uuid_time + " was not before the end time: " + endTime,
780780
uuid_time <= endTime);
781781
}
782782
}

0 commit comments

Comments
 (0)
0