Sean Parent wrote:
ZUIDs <http://opensource.adobe.com/classadobe_1_1zuid__t.html>
Hmm, I guess I would think zuid should be its own little library. There is already a GUID in the vault which again might benefit from collaboration here:
http://www.boost-consulting.com/vault/index.php -- guid_v3.zip
Interesting - this is not quite a conforming GUID (deviates in many of the same ways that ZUIDs do from the specification but I try to be honest and not call them GUIDs...
<http://www.uddi.org/pubs/draft-leach-uuids-guids-01.txt>
AFAICT the node ID in the boost code is purely dependent on the clock - this makes the entire ID uniqueness of the ID a function of time (making for a fairly high probability of collision). The ZUID code includes machine specific and process specific information in the node generation and has code to synchronize threads to avoid collisions from requesting IDs from separate threads at the same time.
Most people don't even bother with proper GUIDs nowadays, they just generate a cryptographic quality random number. The probability of a collision is "sufficiently low for most practical uses".
For a good cryptographic random number generator it assumes that you have some high entropy source of data from which you can harvest bits (a clock will only give you a couple bits of entropy at best). The problem is a bit simpler for a UUID - as you only need a unique value as a node ID to base the UUID off of - the node ID could come from a cryptographic quality random number generator (if you have one) - the usual source for the node ID is the machine MAC ID but that leads to privacy issues. Using MD5 and a pool of unique and high entropy values one can distill a reasonably unique node ID. Once you have the node ID - it is useful to be able to generate additional IDs quickly (for example, if you want most objects in your application to have a persistent and globally unique ID - this is a good thing). UUIDs provide for that as well - typically generating a new truly random number will take significant time (assuming you have an an entropy source). If you know of a good library for cryptographic quality random numbers I'm interested - that's the core issue right now for the ZUID library is ensuring enough entropy for the node ID. Sean
Sean Parent wrote:
If you know of a good library for cryptographic quality random numbers I'm interested - that's the core issue right now for the ZUID library is ensuring enough entropy for the node ID.
I don't know of a portable library for obtaining entropy; I'd expect /dev/urandom to be one on POSIX OSes but its quality would probably vary. For Windows XP, there is RtlGenRandom: http://windowssdk.msdn.microsoft.com/en-us/library/ms732683.aspx and the algorithm behind it is explained in: http://blogs.msdn.com/michael_howard/archive/2005/01/14/353379.aspx For GUIDs, one would typically obtain "a sufficient amount" of entropy only once at startup and use it as a seed for a high quality PRNG, so speed shouldn't be an issue. I haven't needed a portable PRNG implementation so far (usually I also need other crypto facilities and use whatever the crypto library provides) so I'm not sure whether a de-facto standard has emerged as is the case with encryption (AES) and hash functions (SHA2).
participants (2)
-
Peter Dimov -
Sean Parent