Here is some text of Steve Woodcock I once found on theserverside.com.
Note: The SecureRandom generator which is used in the impl. takes "some" =
time to
calculate it's first output (approx. 3 Seconds on my TB1GHz) but then it =
works in
tolerable time.
---cite-begin---
EJB GUID generation techniques rely on a database to provide a sequencing=
mechanism or singleton objects, or a combination of
both. This is a GUID generator that does not need a singleton or a databa=
se - can
be safely pooled on a single machine and deployed
in a cluster to provide completely scalable performance.
The problem of generating unique IDs can essentially be broken down as un=
iqueness
over space and uniqueness over time which,
when combined, produces a globally unique sequence.
Taking the UUID and GUID Internet standards draft for the Network Working=
Group by
Paul J. Leach, Microsoft, and Rich Salz,
Certco, as a starting point we assume that the GUID be represented as a 3=
6-digit
alphanumeric (including hyphens) of the format
xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx.
The first 20 characters represent the uniqueness over time (the low 32-bi=
ts of the
time stamp as the first 8, the next 4 as the mid 16
bits of the time stamp, the next 4 as the high value of the time stamp mu=
ltiplexed
with the version, and the next 4 a combination of the
clock sequence high -multiplexed with the variant field - and the low bit=
s) Note:
The internet guidelines suggest the timestamp as a
60-bit value to a precision of 100ns since 00:00:00.00, 15 October 1582 (=
the date
of Gregorian reform to the Christian calendar)
The last 12 characters are a 48-bit node identifier usually implemented a=
s the
IEEE 802 address, which gives uniqueness over space.
These are combined to produce a unique sequence.
Some of the main problems in an EJB implementation of this technique are:=
-
1) there is no access to the traditional IEEE 802 address.
2) more than one object can exist at the same time and so generate the sa=
me time
stamp at a granularity of a millisecond (Java's
timestamp granularity).
3) a clock sequence or equivalent is used as a way of reading/writing a v=
alue to
storage (e.g. a database or system file) that can be
used in case the clock is set backwards and as a seed for the number sequ=
ence.
This is even more of a problem when a cluster of
machines do not use the same database.
4) Singletons are not portable and not recommended in the EJB specs.
Previous solutions have required a database or a singleton object techniq=
ue to try
and overcome these limitations.
However, by taking the following format we can address these issues in a =
simple
manner.
1) (1-8 hex characters) use the low 32 bits of System.currentTimeMillis()=
=2E We
could use the recommended date format by adding
12219292800000L to the system time long before grabbing the low 32 bits b=
ut there
doesn't seem much point.This gives us a
uniqueness of a millisecond - therefore any clashing object will have to =
be
generated within the same millisecond.
But this does not give us a uniqueness in space or complete uniqueness in=
time. -
2) (9-16 hex characters) the IP address of the machine as a hex represent=
ation of
the 32 bit integer underlying IP - gives us a spatial
uniqueness to a single machine - guarantees that these characters will be=
different for machines in a cluster or on a LAN.
We now have machine uniqueness per millisecond - but this does not accoun=
t for
multiple objects on a machine, clock sequence
being reset or the same object producing multiple GUIDs per millisecond.
3) (17-24 hex characters) the hex value of the Stateless Session bean obj=
ect's
hashCode (a 32 bit int) - in the Java language spec -
the hashcode value of Object is defined as -
** As much as is reasonably practical, the hashCode method defined by cla=
ss object
does return distinct integers for distinct
objects. (This is typically implemented by converting the internal addres=
s of the
object into an integer, but this implementation
technique is not required by the Java programming language.)**
This removes the need for a singleton object as the Stateless bean uses i=
ts own
hashCode as part of the GUID - so even if two
objects create a value at the same millisecond on the same machine these
characters will be different. Remember the hashCode is
not over-ridden here so the implementation will be the one for Object. No=
te - on
machines with low RAM the most significant
characters will always be 00 in the hashcode sequence.
So we now have a number that is unique to the millisecond, the IP address=
and the
object creating it.
There is still the possibility that the same object can produce many GUID=
s within
the same millisecond or the clock may be reset.
4) (25-32 hex characters) a random 32 bit integer generated for each meth=
od
invocation from the SecureRandom java class using
SecureRandom.nextInt(). This method produces a cryptographically strong
pseudo-random integer. The Java lang defines this as -
** Returns a pseudo-random, uniformly distributed int value drawn from th=
is random
number generator's sequence. The general
contract of nextInt is that one int value in the specified range is pseud=
orandomly
generated and returned. All n possible int values are
produced with (approximately) equal probability.**
By adding a random int to the GUID for each new request we now have a GUI=
D that
has a combination of the following four properties
1) is unique to the millisecond
2) is unique to the machine
3) is unique to the object creating it
4) is unique to the method call for the same object
The only possible theoretical conflicts are:
1) that two objects on the same machine are assigned the exact same hashC=
ode (I do
not know of any implementations that do this
but there may be some out there) and at the same millisecond must also ge=
t the
same integer value from the SecureRandom
implementation.
2) The same int value is returned from the SecureRandom object in subsequ=
ent
method calls for the same object.
3) A reset clock (which would require a redeployment of the bean) will pr=
oduce an
identical hashcode for the new deployment as a
previous one AND the random values will have to be the same in the same r=
epeated
millisecond value as in a previous sequence.
There is no problem using this approach to create a pool of GUID generato=
rs or
using such pools in a cluster. Also performance is
excellent as the SecureRandom seed can be initialised in the ejbCreate me=
thod and
the subsequent nextInt() numbers are quick to
produce.
The basic implementation code can be found below - there are some utility=
methods
etc omitted. A demo of this code is available at
www.activescript.co.uk.
--------------- Code follows -----------------
// class variables used to cache some of the data
private int timeLow; //32 bits
private int node; // 32 bits
private String hexInetAddress; //32 bits
private String thisHashCode; // 32 bits
private String midValue;
//In order to speed up the method calls we can cache some infomation in t=
he create
method
public void ejbCreate() throws CreateException {
try {
StringBuffer tmpBuffer =3D new StringBuffer();
// initalise the secure random instance
seeder =3D new SecureRandom();
// get the inet address
InetAddress inet =3D InetAddress.getLocalHost();
byte [] bytes =3D inet.getAddress();
hexInetAddress =3D hexFormat(getInt(bytes),8);
// get the hashcode
thisHashCode =3D hexFormat(this.hashCode(),8);
/* set up a cached midValue as this is the same per method
/ call as is object specific and is the
/ ...-xxxx-xxxx-xxxx-xxxx.. mid part of the sequence
*/
tmpBuffer.append("-");
tmpBuffer.append(hexInetAddress.substring(0,4));
tmpBuffer.append("-");
tmpBuffer.append(hexInetAddress.substring(4));
tmpBuffer.append("-");
tmpBuffer.append(thisHashCode.substring(0,4));
tmpBuffer.append("-");
tmpBuffer.append(thisHashCode.substring(4));
midValue =3D tmpBuffer.toString();
// load up the randomizer first value
int node =3D seeder.nextInt();
} catch (Exception e) {
throw new CreateException ("error - failure to create bean " + e);
}
}
//The actual method call to get the unique numbers is then very simple
public String getUUID() throws RemoteException
{
long timeNow =3D System.currentTimeMillis();
timeLow =3D (int) timeNow & 0xFFFFFFFF;
int node =3D seeder.nextInt();
return (hexFormat(timeLow, 8) + midValue + hexFormat(node, 8));
}
----------------Code Ends --------------------
Any comments would be welcome regarding the implemetation or anything I m=
ight have
missed that is obvious.
Cheers
Steve Woodcock
---cite-end---
___________________________________________________________________________
To unsubscribe, send email to [EMAIL PROTECTED] and include in the body
of the message "signoff SERVLET-INTEREST".
Archives: http://archives.java.sun.com/archives/servlet-interest.html
Resources: http://java.sun.com/products/servlet/external-resources.html
LISTSERV Help: http://www.lsoft.com/manuals/user/user.html
