psteitz 2004/01/25 14:25:20
Modified: id/src/java/org/apache/commons/id/uuid UUIDClock.java
Added: id/src/java/org/apache/commons/id/uuid UUIDSystemClock.java
id/src/test/org/apache/commons/id/uuid
UUIDSystemClockTest.java
Removed: id/src/test/org/apache/commons/id/uuid UUIDClockTest.java
Log:
Added uuid system clock enhancements contributed by Tim Reilly, bz #26272.
Revision Changes Path
1.2 +38 -142
jakarta-commons-sandbox/id/src/java/org/apache/commons/id/uuid/UUIDClock.java
Index: UUIDClock.java
===================================================================
RCS file:
/home/cvs/jakarta-commons-sandbox/id/src/java/org/apache/commons/id/uuid/UUIDClock.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- UUIDClock.java 11 Jan 2004 09:10:18 -0000 1.1
+++ UUIDClock.java 25 Jan 2004 22:25:20 -0000 1.2
@@ -3,7 +3,7 @@
* ====================================================================
* The Apache Software License, Version 1.1
*
- * Copyright (c) 2002-2003 The Apache Software Foundation. All rights
+ * Copyright (c) 2003-2004 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
@@ -56,34 +56,36 @@
package org.apache.commons.id.uuid;
+
/**
- * <p>UuidClock.java provides a timing mechanism for returning the current time in
- * 100-nano second intervals since 00:00:00.00, 15 October 1582.</p>
+ * <p>UUIDClock.java provides a timing mechanism for returning the current time in
+ * 100-nano second intervals since 00:00:00.00, 15 October 1582</p>
*
- * <p>As described below this is useful for generating Version 1 UUIDs.</p>
+ * <p>As described below this is useful for generating Version 1 UUIDs</p>
*
- * <p>For more information regarding the IETF Draft Uuid specification
+ * <p>For more information regarding the IETF Draft UUID specification
* see http://www.ietf.org/internet-drafts/draft-mealling-uuid-urn-01.txt</p>
*
- * <p>Selected segements of Draft pertaining to this class:</p>
- * <pre>
- * ====================================================================
- * Timestamp
- * The timestamp is a 60 bit value. For Uuid version 1, this is
+ * <p>Selected quotes from IETF document pertaining to this class:</p>
+ *
+ * <p>====================================================================</p>
+ * <dl>
+ * <dt>Timestamp</dt>
+ * <dd>"The timestamp is a 60 bit value. For UUID version 1, this is
* represented by Coordinated Universal Time (UTC) as a count of 100-
* nanosecond intervals since 00:00:00.00, 15 October 1582 (the date of
- * Gregorian reform to the Christian calendar).
+ * Gregorian reform to the Christian calendar)."</dd>
*
- * Clock Adjustment
- * UUIDs may be created at a rate greater than the system clock resolution.
+ * <dt>Clock Adjustment</dt>
+ * <dd>"UUIDs may be created at a rate greater than the system clock resolution.
* Therefore, the system must also maintain an adjustment value to be added to
* the lower-order bits of the time. Logically, each time the system clock
* ticks, the adjustment value is cleared. Every time a UUID is generated,
* the current adjustment value is read and incremented atomically, then added
- * to the UTC time field of the UUID.
+ * to the UTC time field of the UUID."</dd>
*
- * Clock Overrun
- * The 100 nanosecond granularity of time should prove sufficient even for
+ * <dt>Clock Overrun</dt>
+ * <dd>"The 100 nanosecond granularity of time should prove sufficient even for
* bursts of UUID creation in the next generation of high-performance
* multiprocessors. If a system overruns the clock adjustment by requesting
* too many UUIDs within a single system clock tick, the UUID service may
@@ -92,15 +94,12 @@
* terminating the request
* reissuing the request until it succeeds
* stalling the UUID generator until the system clock catches up.
- *
+ * <br>...<br>
* If the processors overrun the UUID generation frequently, additional node
- * identifiers and clocks may need to be added.
- * ====================================================================
- *
- * The quotations above are protected under the following copyright notice:
- *
- * Copyright (C) The Internet Society (2003). All Rights Reserved.
+ * identifiers and clocks may need to be added."</dd>
*
+ * <p>The above quotations are protected under the following copyright notice </p>
+ * <p><code>Copyright (C) The Internet Society (2003). All Rights Reserved.
* This document and translations of it may be copied and furnished to
* others, and derivative works that comment on or otherwise explain it
* or assist in its implementation may be prepared, copied, published
@@ -113,138 +112,35 @@
* developing Internet standards in which case the procedures for
* copyrights defined in the Internet Standards process must be
* followed, or as required to translate it into languages other than
- * English.
- *
- * The limited permissions granted above are perpetual and will not be
+ * English.</p>
+ * <p>The limited permissions granted above are perpetual and will not be
* revoked by the Internet Society or its successors or assignees.
- *
* This document and the information contained herein is provided on an
* "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
* TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
* BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
+ * HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
+ * MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.</code></p>
*
- * </pre>
- *------------------------------------------------------------------------
+ * ====================================================================
*
- * @author Commons-Uid team
* @version $Revision$ $Date$
+ *
*/
-public class UUIDClock extends Thread {
-
- /** Default life of the UuidClock thread in milliseconds */
- public static final long DEFAULT_THREAD_LIFE = 200;
+public interface UUIDClock {
/** Offset from GregorianCalendar Change over to Jan 1 1970 00:00:00.00 */
- public static final long GREGORIAN_CHANGE_OFFSET = 12219292800000L;
-
- /** Maximum ticks per millisecond interval */
- public static final long TICKS_PER_MILLI = 10000L;
-
- /** Life time of the clock thread in milliseconds */
- private static long threadLife = DEFAULT_THREAD_LIFE;
-
- /** Singleton instance of the UuidClock */
- private static UUIDClock clock = null;
-
- /** The counter for nanoseconds generated during this system interval(ms) */
- private int generatedThisMilli;
-
- /** The current time in milliseconds held in this clock thread. */
- private long currentTimeMillis;
-
- /** Time when the clock thread should die */
- private long expires = threadLife;
-
- /**
- * Private constructor for clock implementation. Utilizes a single thread to
- * increment the clock every milli seconds this should be more
- * accurate than System.currentTimeMillis() as described in
- * the javaworld article:
- * http://www.javaworld.com/javaworld/javaqa/2003-01/01-qa-0110-timing.html
- */
-
- private UUIDClock() {
- setDaemon(true);
- setPriority(Thread.MAX_PRIORITY);
- currentTimeMillis = System.currentTimeMillis();
- start();
- }
-
- /**
- * Returns the thread life in milliseconds. If the clock thread is not
- * accessed within this time span the thread will die off.
- *
- * @return thread life time span in milliseconds
- */
- public static long getThreadLife() {
- return UUIDClock.threadLife;
- }
-
- /**
- * @param threadLife milliseconds this thread should live for. Each
- * call to getCurrentTime resets the expiration time value.
- */
- public static void setThreadLife(long threadLife) {
- UUIDClock.threadLife = threadLife;
- }
-
- /**
- * Threads run method that increments the clock and resets the generated
- * nano seconds counter.
- */
- public void run() {
- try {
- while (--expires >= 0) {
- Thread.sleep(1);
- currentTimeMillis++;
- generatedThisMilli = 1;
- }
- } catch (InterruptedException e) {
- System.out.println("UuidClock thread interrupted");
- }
- }
-
- /**
- * Returns the internal time milliseconds for the UuidClock instance
- * @return the clock threads current time in milliseconds
- */
- private long getCurrentTimeMillis() {
- return currentTimeMillis;
- }
-
- /**
- * Returns the current time as described in the clock resolution and
- * timestamp sections of the uuid specification.
- *
- * @return the current time in 100-nano second intervals (simulated)
- */
- private long currentTime() {
- this.expires = threadLife;
- // Stall until counter is reset to limit only 10000 intervals per
- // millisecond interval
- while (generatedThisMilli > TICKS_PER_MILLI) {
- //wait for thread to reset
- }
-
- long currentTime =
- ((currentTimeMillis + GREGORIAN_CHANGE_OFFSET) * TICKS_PER_MILLI);
+ long GREGORIAN_CHANGE_OFFSET = 12219292800000L;
- return currentTime + (generatedThisMilli++);
- }
+ /** Maximum ticks per millisecond interval (1 millisecond = 1 000 000
nanoseconds) / 100 */
+ long INTERVALS_PER_MILLI = 10000L;
/**
- * Static method returns the clocks current time in 100-nanosecond intervals
- * since the Gregorian calander change. Calendar.GREGORIAN_OFFSET
+ * <p>Returns the current time.</p>
*
- * @return Coordinated Universal Time (UTC) as a count of 100- nanosecond
- * intervals since 00:00:00.00, 15 October 1582
+ * @return the current time in 100-nano second intervals since 00:00:00.00,
+ * 15 October 1582 UTC.
*/
- public static synchronized long getCurrentTime() {
- if (clock == null || !clock.isAlive()) {
- clock = null;
- clock = new UUIDClock();
- }
- return clock.currentTime();
- }
+ long getUUIDTime();
}
1.1
jakarta-commons-sandbox/id/src/java/org/apache/commons/id/uuid/UUIDSystemClock.java
Index: UUIDSystemClock.java
===================================================================
/*
* $Header:
/home/cvs/jakarta-commons-sandbox/id/src/java/org/apache/commons/id/uuid/UUIDSystemClock.java,v
1.1 2004/01/25 22:25:20 psteitz Exp $
* ====================================================================
* The Apache Software License, Version 1.1
*
* Copyright (c) 2004 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution, if
* any, must include the following acknowledgement:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgement may appear in the software itself,
* if and wherever such third-party acknowledgements normally appear.
*
* 4. The names "The Jakarta Project", "Commons", and "Apache Software
* Foundation" must not be used to endorse or promote products derived
* from this software without prior written permission. For written
* permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called "Apache"
* nor may "Apache" appear in their names without prior written
* permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*/
package org.apache.commons.id.uuid;
/**
* <p><code>UUIDSystemClock</code> provides a timing mechanism for returning the
current
* time in 100-nano second intervals since 00:00:00.00, 15 October 1582</p>
*
* <p>@see org.apache.commons.uid.uuid.UUIDClock</p>
*
* <p>In instances where 10,000 or more uuid's may be generated in a millisecond
* this Clock should not be used instead see UUIDThreadClock.</p>
*/
public final class UUIDSystemClock extends Thread implements UUIDClock {
/** Counter for the number of calls during the current millisecond */
private static long generatedThisMilli = 0;
/** The current time in milliseconds held in this clock thread. */
private static long currentTimeMillis;
/** Singleton instance of this clock */
private static UUIDSystemClock clock = null;
/**
* Private constructor for singleton class.
*/
private UUIDSystemClock() {
super();
}
/** @see org.apache.commons.uid.uuid#getCurrentTime() */
public long getUUIDTime() {
synchronized (UUIDSystemClock.class) {
if (currentTimeMillis != System.currentTimeMillis()) {
currentTimeMillis = System.currentTimeMillis();
generatedThisMilli = 0;
}
// Set time as current time millis plus offset times 100 ns ticks
long currentTime =
(currentTimeMillis + GREGORIAN_CHANGE_OFFSET)
* INTERVALS_PER_MILLI;
// Return the same time - generator/client code must check to see if
overclocked
if (generatedThisMilli + 1 >= INTERVALS_PER_MILLI) {
return (currentTime + generatedThisMilli);
}
// Return the uuid time plus the artifical tick incremented
return (currentTime + generatedThisMilli++);
}
}
/**
* <p>Returns the singleton instance of the UUIDSystem clock.</p>
*
* <p>This clock may return the same time if the maximum intervals per
* millisecond have been reached. It is the clock's client code's
* responsibility to handle duplicate times.</p>
*
* @return UUIDSystemClock the singleton instance of the UUIDSystemClock.
*/
public static UUIDClock getInstance() {
if (clock == null) {
clock = new UUIDSystemClock();
}
return clock;
}
}
1.1
jakarta-commons-sandbox/id/src/test/org/apache/commons/id/uuid/UUIDSystemClockTest.java
Index: UUIDSystemClockTest.java
===================================================================
/*
*===================================================================
* The Apache Software License, Version 1.1
*
* Copyright (c) 2002-2004 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution,
* if any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "Apache" and "Apache Software Foundation" and
* "Apache Geronimo" must not be used to endorse or promote products
* derived from this software without prior written permission. For
* written permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called "Apache",
* "Apache Geronimo", nor may "Apache" appear in their name, without
* prior written permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*
* ====================================================================
*/
package org.apache.commons.id.uuid;
import java.util.Arrays;
import junit.framework.Test;
import junit.framework.TestCase;
import junit.framework.TestResult;
import junit.framework.TestSuite;
import junit.textui.TestRunner;
/**
* Unit tests for [EMAIL PROTECTED] UuidSystemClock}.
*
* @version $Revision: 1.1 $ $Date: 2004/01/25 22:25:20 $
* @author Commons-Uid team
*/
public class UUIDSystemClockTest extends TestCase {
/** Continuous test mode */
public static final String continuous = "Continuous";
/**
* Constructor for test
*
* @param name String name of the test
*/
public UUIDSystemClockTest(String name) {
super(name);
}
/**
* Main application method
*
* @param args String arguments array
*/
public static void main(String[] args) {
if (args.length != 0 && args[0].equalsIgnoreCase("-" + continuous)) {
while (true) {
TestResult result = TestRunner.run(suite());
if (result.failureCount() != 0) {
System.exit(-1);
}
}
}
else {
TestRunner.run(suite());
}
}
/** @see junit.framework.TestCase#suite() */
public static Test suite() {
TestSuite suite = new TestSuite(UUIDSystemClockTest.class);
suite.setName("UUID System Clock Tests");
return suite;
}
//-------------------------------------------------------------------------
/** @see junit.framework.TestCase#setUp() */
protected void setUp() throws Exception {
super.setUp();
}
/**
* Make sure that time stamps generated by concurrent threads
* are unique. UUIDSystemClock has an effective limit of 10,000 UUID
* Generated prior to duplicates being returned for a given 1 ms time
* interval. The UUIDGenerator must account for this and either use a
* different node identifier, throw an exception, etc. This test ensures
* multiple clients will recieve unique values up to the limit 10,0000.
*
* @throws Exception a testing exception.
*/
public void testUnique() throws Exception {
/*
* Number of timestamps to generate on each thread
*/
int iterations = 2500;
/*
* Number of client threads
*/
int threadCount = 4;
// Launch threadCount client threads and set them
// off generating time stamps
long[][] threadTimes = new long[threadCount][iterations];
Thread[] clockClients = new Thread[threadCount];
for (int i = 0; i < threadCount; i++) {
clockClients[i] = new ClockClient(threadTimes[i], iterations);
clockClients[i].start();
}
// Wait until all the threads are done
boolean working = true;
while (working) {
working = false;
for (int i = 0; i < threadCount; i++) {
if (clockClients[i].isAlive()) {
working = true;
}
}
}
// Gather up all of the times and test for uniqueness
long[] times = new long[iterations * threadCount];
int k = 0;
for (int i = 0; i < threadCount; i++) {
for (int j = 0; j < iterations; j++) {
times[k++] = threadTimes[i][j];
}
}
// Ridiculously inefficient, but effective -- sort and walk
Arrays.sort(times);
for (int i = 0; i < times.length - 1; i++) {
if (times[i] == times[i + 1]) {
fail("Duplicate time stamps generated: " + times[i] + " " + i);
}
}
}
/**
* Make sure that generated time stamps are within expected ranges.
* Need to look at this some more -- tolerance is now 2 x
* the effective resolution (on my Win2K is 16ms - range may vary on
* platforms up to 10 to 50ms.
*
* @throws Exception a testing exception.
*/
public void testRange() throws Exception {
long time = 0;
long baseTime = 0;
long maxResolution = findSystemResolution() * 2;
for (int i = 0; i < 100; i++) {
Thread.currentThread().sleep(10);
baseTime = System.currentTimeMillis();
for (int j = 0; j < 100; j++) {
time = UUIDSystemClock.getInstance().getUUIDTime();
assertTrue("Generated timestamp too large",
time < ((baseTime + UUIDClock.GREGORIAN_CHANGE_OFFSET +
maxResolution) * UUIDClock.INTERVALS_PER_MILLI));
assertTrue("Generated timestamp too small",
time > ((baseTime + UUIDClock.GREGORIAN_CHANGE_OFFSET -
maxResolution) * UUIDClock.INTERVALS_PER_MILLI));
}
}
}
/**
* Finds the systems currentTimeMillis resolution (the difference in
* milliseconds when System.currentTimeMillis is not equal to the last call
* to System.currentTimeMillis). On windows this may be from 10 to 50 ms.
*
* @return Returns the maximum found of the systems effective time resolution.
*/
public int findSystemResolution() {
int resolution = 1;
long baseTime = 0;
long newTime = 0;
for ( int i = 0; i < 10; i++ ) {
baseTime = System.currentTimeMillis();
newTime = System.currentTimeMillis();
while (newTime == baseTime) {
newTime = System.currentTimeMillis();
}
if (newTime - baseTime > resolution) {
resolution = (int) (newTime - baseTime);
}
}
System.out.println("Using system time resolution: " + resolution + " ms.");
return resolution;
}
//--------------------------------------------------------------------------
/**
* UuidClock client thread
*/
protected static class ClockClient extends Thread {
/**
* Generated time stamps
*/
protected long[] times;
/**
* Number of time stamps to generate on this thread
*/
protected int iterations;
/**
* Constructor for the ClockClient thread.
*
* @param times an array of times generated.
* @param iterations the number of time stamps the generate.
*/
ClockClient(long[] times, int iterations) {
super();
this.times = times;
this.iterations = iterations;
}
/**
* Run method of this thread generates n-iterations timestamps.
*/
public void run() {
for (int i = 0; i < iterations; i++) {
times[i] = UUIDSystemClock.getInstance().getUUIDTime();
}
}
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
