Peter,
Thanks! His article and the ensuing discussion are great references. Of
course, it means I'm going to have to revisit the solution I came up with =)
Eddie
>From: Peter Huber <[EMAIL PROTECTED]>
>Reply-To: "A mailing list for discussion about Sun Microsystem's Java
> Servlet API Technology." <[EMAIL PROTECTED]>
>To: [EMAIL PROTECTED]
>Subject: Re: generating a truly unique session id
>Date: Wed, 12 Sep 2001 12:04:33 +0200
>
>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
>
_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp
___________________________________________________________________________
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
