001: /*
002:
003: Derby - Class org.apache.derby.impl.services.uuid.BasicUUIDFactory
004:
005: Licensed to the Apache Software Foundation (ASF) under one or more
006: contributor license agreements. See the NOTICE file distributed with
007: this work for additional information regarding copyright ownership.
008: The ASF licenses this file to you under the Apache License, Version 2.0
009: (the "License"); you may not use this file except in compliance with
010: the License. You may obtain a copy of the License at
011:
012: http://www.apache.org/licenses/LICENSE-2.0
013:
014: Unless required by applicable law or agreed to in writing, software
015: distributed under the License is distributed on an "AS IS" BASIS,
016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017: See the License for the specific language governing permissions and
018: limitations under the License.
019:
020: */
021:
022: package org.apache.derby.impl.services.uuid;
023:
024: import org.apache.derby.iapi.services.monitor.Monitor;
025: import org.apache.derby.catalog.UUID;
026: import org.apache.derby.iapi.services.uuid.UUIDFactory;
027:
028: /**
029:
030: A hack implementation of something similar to a DCE UUID
031: generator. Generates unique 128-bit numbers based on the
032: current machine's internet address, the current time, and
033: a sequence number. This implementation should be made to
034: conform to the DCE specification. ("DEC/HP, Network Computing
035: Architecture, Remote Procedure Call Runtime Extensions
036: Specification, version OSF TX1.0.11," Steven Miller, July
037: 23, 1992. This is part of the OSF DCE Documentation.
038: Chapter 10 describes the UUID generation algorithm.)
039: <P>
040: Some known deficiencies:
041: <ul>
042: <li> Rather than using the 48-bit hardware network address,
043: it uses the 32-bit IP address. IP addresses are not
044: guaranteed to be unique.
045: <li> There is no provision for generating a suitably unique
046: number if no IP address is available.
047: <li> Two processes running on this machine which start their
048: respective UUID services within a millisecond of one another
049: may generate duplicate UUIDS.
050: </ul>
051: <P>
052: However, the intention is that UUIDs generated from this class
053: will be unique with respect to UUIDs generated by other DCE
054: UUID generators.
055:
056: **/
057:
058: public final class BasicUUIDFactory implements UUIDFactory {
059: /*
060: ** Fields of BasicUUIDFactory.
061: */
062:
063: private long majorId; // 48 bits only
064: private long timemillis;
065:
066: public BasicUUIDFactory() {
067: Object env = Monitor.getMonitor().getEnvironment();
068: if (env != null) {
069: String s = env.toString();
070: if (s != null)
071: env = s;
072:
073: majorId = ((long) env.hashCode());
074:
075: } else {
076: majorId = Runtime.getRuntime().freeMemory();
077: }
078:
079: majorId &= 0x0000ffffffffffffL;
080: resetCounters();
081: }
082:
083: //
084: // Constants and fields for computing the sequence number. We started out with monotonically
085: // increasing sequence numbers but realized that this causes collisions at the
086: // ends of BTREEs built on UUID columns. So now we have a random number
087: // generator. We generate these numbers using a technique from Knuth
088: // "Seminumerical Algorithms," section 3.2 (Generating Uniform Random Numbers).
089: // The formula is:
090: //
091: // next = ( (MULTIPLIER * current) + STEP ) % MODULUS
092: //
093: // Here
094: //
095: // MODULUS = int size.
096: // MULTIPLIER = fairly close to the square root of MODULUS to force the
097: // sequence number to jump around. satisifies the rule that
098: // (MULTIPLIER-1) is divisible by 4 and by all the primes which
099: // divide MODULUS.
100: // STEP = a large number that keeps the sequence number jumping around.
101: // must be relatively prime to MODULUS.
102: // INITIAL_VALUE = a number guaranteeing that the first couple sequence numbers
103: // won't be monotonically increasing.
104: //
105: // The sequence numbers should jump around and cycle through all numbers which fit in an int.
106:
107: private static final long MODULUS = (1L << 32);
108: private static final long MULTIPLIER = ((1L << 14) + 1);
109: private static final long STEP = ((1L << 27) + 1);
110: private static final long INITIAL_VALUE = (2551218188L);
111:
112: private long currentValue;
113:
114: /*
115: ** Methods of UUID
116: */
117:
118: /**
119: Generate a new UUID.
120: @see UUIDFactory#createUUID
121: **/
122: public synchronized UUID createUUID() {
123: long cv = currentValue = ((MULTIPLIER * currentValue) + STEP)
124: % MODULUS;
125: if (cv == INITIAL_VALUE) {
126: bumpMajor();
127: }
128: int sequence = (int) cv;
129:
130: return new BasicUUID(majorId, timemillis, sequence);
131: }
132:
133: /**
134: Recreate a UUID previously generated UUID value.
135: @see UUIDFactory#recreateUUID
136: **/
137: public UUID recreateUUID(String uuidstring) {
138: return new BasicUUID(uuidstring);
139: }
140:
141: /**
142: @see UUIDFactory#recreateUUID
143: **/
144: public UUID recreateUUID(byte[] b) {
145: return new BasicUUID(b);
146: }
147:
148: private void bumpMajor() {
149:
150: // 48 bits only
151: majorId = (majorId + 1L) & 0x0000ffffffffffffL;
152: if (majorId == 0L)
153: resetCounters();
154:
155: }
156:
157: private void resetCounters() {
158: timemillis = System.currentTimeMillis();
159: currentValue = INITIAL_VALUE;
160: }
161: }
|