518146 - Generate shorter GUIDs than nsIUUIDGenerator

Status: RESOLVED FIXED

(Firefox :: Sync, defect, P3)

Description

[Ed Lee :Mardak]

uuidgen.generateUUID returns a 38 character GUID like
{494c6659-5c94-7746-be55-6461e7dae103}

We already strip off the {}s and end up with 36 characters and could get down to 32 hex digits.

If we use something base64-like, we could encode 128bits of information in ~22 characters. Base64 actually pads data out to multiples of 4 characters, so 128 bits would show up as 24 characters.

If we don't care about the full 128-bit range, we can shortcut with 126 bits which would result in 4x fewer possibilities.

126 comes from 21 6-bit values. If we drop that to 20 characters, it would be a 120-bit GUID that provides 1.329227995784917e+36 possible values.

Part of the reason for shorter guids is to save on some overhead from returning/requesting a list of GUIDs and some minor savings per record.

Comment 1

[Ed Lee :Mardak]

These 71 characters don't need to be %escaped

1234567890-qwertyuiopasdfghjkl'zxcvbnm.~!*()_QWERTYUIOPASDFGHJKLZXCVBNM

But ! and ' might do strange things in a shell.

21 71-value values stores more than 129 bits of information.

How many bits of GUID do we want?

Comment 2

[Ed Lee :Mardak]

http://hg.mozilla.org/labs/weave/rev/4dbecb081aa1
Randomly generate 10 characters from a pool of 70 possible characters for an equivalent 61.29-bit GUID which should have around 1% chance of collision (within a collection) after ~100 million records.