Date: Sun, 27 Feb 2000 11:16:35 +0000 (GMT)
From: Riley Williams <rhw@MemAlpha.cx>
> The only time it won't be unique is if someone copies a
> filesystem using dd. This admittedly does happen with
> floppies from time to time, but there's not much we can do
> to prevent that.
Can you guarantee that?
Yes, I can. Well, at least to approximately the same probabilty that
all of the oxygen in the room won't suddenly decide to go into one
corner, suffocating everybody else in the world. (This isn't *likely*
to happen, but it is *possible*. :-)
As I see it, to make a guarantee like that, the UUID generating
algorithm needs to include something specific to the machine it's
running on, as well as something relating to the current time.
The use of genuine random numbers can only come a poor second to
this - remember that even 1 2 3 4 5 6 7 is a valid sequence of
random numbers.
That's correct; UUID's have this property. To quote from
draft-leach-uuids-guids-01.txt:
> A UUID is an identifier that is unique across both space and time,
> with respect to the space of all UUIDs. To be precise, the UUID
> consists of a finite bit space. Thus the time value used for
> constructing a UUID is limited and will roll over in the future
> (approximately at A.D. 3400, based on the specified algorithm). A
> UUID can be used for multiple purposes, from tagging objects with an
> extremely short lifetime, to reliably identifying very persistent
> objects across a network.
>
> The generation of UUIDs does not require that a registration
> authority be contacted for each identifier. Instead, it requires a
> unique value over space for each UUID generator. This spatially
> unique value is specified as an IEEE 802 address, which is usually
> already available to network-connected systems. This 48-bit address
> can be assigned based on an address block obtained through the IEEE
> registration authority. This section of the UUID specification
> assumes the availability of an IEEE 802 address to a system desiring
> to generate a UUID, but if one is not available section 4 specifies a
> way to generate a probabilistically unique one that can not conflict
> with any properly assigned IEEE 802 address.
The short version of the story is that if you have 128 bits, and you use
48 bits for an ethernet address, and 64 bits for a timestamp expressed
in 100's of nanoseconds since midnight GMT October 15, 1582, and use a a
couple of other bits for a generation counter (to deal with reboots and
other situations where the block might be adjusted backwards), you can
get pretty good.
Also, if you have a genuinely good random number generator, simply
generating 122-bit random number (The other 6 bits are set to a specific
pattern to distinguish them from non-type-4 UUID's) works pretty well.
Yes, there is a one in 2**122 chance you might pick the same UUID,
assuming that you have a good random number generator. But those are
pretty small odds. It's much more likely that a cosmic ray will alter
some location in memory, causing the system to crash or misbehave
randomly. It's really small enough not to worry about.
- Ted
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Tue Feb 29 2000 - 21:00:18 EST