[sldev] Texture Garbage Collection (was Re: UMA Grid - Offline for a bit)

[James Cook]

The client generates UUIDs.  The nice thing about UUIDs is that they can
be generated anywhere and used throughout the system.  Note that
lluuid.cpp is using both the time and the Ethernet card MAC address to
generate the ID.  The MD5 is to prevent someone from reversing out your
MAC address if you give them a UUID you generated.

UUIDs don't collide unless you're doing something wrong.  UUIDs are 128
bit numbers.  2^10 ~= 10^3, so 2^128 ~= 10^36.

Assuming you generate 1 million UUIDs per second, that's 10^30 seconds
before you collide.  Assume you're doing that on each of 1 billion
computers.  10^21 seconds before collision.

(Yes, it's actually much less than that due to the fact you have an ever
expanding list of UUIDs to check against.  This is called the "birthday
paradox" because it's the reason that a classroom of 30 people is highly
likely to have two people with the same birthday.  But the use of the
time and MAC helps make collisions less likely.)

http://www.vendian.org/envelope/TemporaryURL/time.html

A year is 10^7 seconds.  The universe is about 10^18 seconds old.  10^21
seconds is a long time.

:-)

James

John Hurliman wrote:
> Jason Giglio wrote:
>> Callum Lerwick wrote:
>>> Not sure how SL generates UUIDs, there's no exact standard, but if
>>
>> I bet you 5 lindens they just pull 16 bytes out of /dev/urandom, then
>> if it collides do a sequential count down to the next open slot.
>>
>> I don't think any UUIDs are generated client side.
>>
>> -Jason 
> 
> Send the money to Eddy Stryker in-world, none of the above is correct.
> http://opensecondlife.org:8180/source/xref/linden/indra/llmath/lluuid.cpp
> 
> The current time and a random seed are used as input which are MD5ed to
> get the final UUID. UUIDs are used for almost everything and a collision
> usually doesn't matter unless it's in the same context (two assets can't
> have the same UUID, two simulators can't have the same UUID, two parcels
> can't have the same UUID, etc). There is no good way for the client to
> do collision checking for asset uploads, in the extremely rare case of a
> collision while uploading a texture or whatever I believe the server
> will just return an error (or maybe the whole asset cluster will fail,
> haven't tested). The client generally does not get to create UUIDs that
> are stored on the server, the odd case is the client-generated
> transactionID that goes in to the combine() function with the
> secureSessionID (MD5 of the two) to create an assetID. Causing a
> collision here would be theoretically possible, but rainbow table
> attacks are defeated by the secureSessionID salt, and brute forcing to
> create a collision before the secureSessionID expires isn't very feasible.
> 
> John Hurliman
> _______________________________________________
> Click here to unsubscribe or manage your list subscription:
> /index.html

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 249 bytes
Desc: OpenPGP digital signature
Url : http://lists.secondlife.com/pipermail/sldev/attachments/20070408/1d87512c/signature-0001.pgp