Path: utzoo!attcan!uunet!lll-winken!lll-tis!mordor!joyce!ames!mailrus!husc6!mit-eddie!apollo!mishkin
From: mishkin@apollo.COM (Nathaniel Mishkin)
Newsgroups: comp.unix.wizards
Subject: Re: Unique number generator?
Message-ID: <3e5da7d6.13422@apollo.COM>
Date: 9 Sep 88 15:05:00 GMT
References: <775@goofy.megatest.UUCP>
Reply-To: mishkin@apollo.com (Nathaniel Mishkin)
Organization: Apollo Computer, Chelmsford, MA
Lines: 51

In article <775@goofy.megatest.UUCP> djones@megatest.UUCP (Dave Jones) writes:
>What's the best way for a process to generate a network-wide
>unique number which will remain unique over time?  (A very, very 
>high probability of uniqueness may have to be good enough.)

As part of Apollo Network Computing System (NCS), we addressed this very
issue.  The Apollo OS has long used unique identifiers (UIDs).  UIDs
prove to be very useful in a distributed environment.  They can be
generated in a distributed fashion (no appeal to a central authority
required) and they always mean the same thing (you never have to check
to make sure that identifier that you got at some earlier time still
refers to what you think it refers to).  

The Apollo OS UIDs are 64 bits long and consist of a 36 bit time value
(16ms units) and a 20 bit "node number" (all Apollo workstations have
such a number in hardware) and some other (currently unused bits).  The
software ensures that even if you try to generate UIDs "too fast", you
still get unique ones (it keeps enough "spares").

Anyway, when we did NCS we realized we'd have to generalize this scheme
somewhat, so we invented what we call "Universal UIDS" (UUIDS).  UUIDs
are 128 bits longs and consists of a 48 bit time value (4us units) and
a 64 bit location (and again some unused bits).  The location is
represented roughly like Berkeley "struct sockaddr" (minus the "port")
-- there's a 8 bit "address family" and 7 bytes (zero padded) of network
address.  A host can pick whatever it wants as the location, as long
as it's unique.  (E.g. it can use PF_INET and its IP address or it could
use PF_NS and its ethernet address.)  People occasionally tell me things
like how ISO addresses can be 1024 bits long and all I can do is shrug
and sigh for now.  (I think UUID generation will be the least of the
problems a system with 1024 bit network address will have.)

On Unix systems NCS's default UUID generator uses IP-type UUIDs and to
make sure that it's generating unique time values, stores the last UUID
generated in a file (that is accessed under flock/lockf calls).  Not
terribly fast, but you don't generate UUIDs all that often and better
right than fast.  (Systems that have decent shared memory support could
probably do a better job.)  With a little effort, I can probably extract
the UUID generation stuff from the NCS source code and make it generally
available.  It's not all that complicated, although if you want almost
anything to work on various flavors of Unix, MS/DOS, and VMS (as we do),
almost nothing is easy.

NCS uses UUIDs to indentify network interfaces, objects, object types,
and "activities" (processes making remote calls).



-- 
                    -- Nat Mishkin
                       Apollo Computer Inc., Chelmsford, MA
                       mishkin@apollo.com