0

I've been struggling with this problem for a little while... How to hide the order that records were created in, basically. You typically do this by generating a "GUID". But this GUID is arbitrarily chosen to be a very large number, essentially a number so large that it will encompass all records ever created.

But the question is, if it is too small. If later on down the road there turns out to be a number twice as big as the last "biggest" number. Then we can know from the IDs that the ones with the length of the first GUID are part of the first group of people that were using the system. So there is the creeping in of that original problem: the order of the records is now no-longer hidden.

If you simplify the problem, you can say at first there are 100 possible slots, so everyone out of the possible hundred get a random number 1-100. When it reaches 100, then you grow to the next chunk, let's say 200 or 1000. So then everyone from that point forwards gets a random number 101-1000. But this means the first group is still identifiable. Once this number becomes too small, we go to lets say 10,000. Then numbers 1001-10000 are for the next set, but we can now tell the first two groups of people from the third.

To hide this, it is as if you need to recalculate every ID and do a batch update of all possible URLs using these IDs, or cross-references. Then you would just provide a new random number out of the random set. But the problem with this is if the IDs were written down on paper or used on a platform outside of what you own (like they post a link on twitter), then it would break with this approach.

So it seems the only viable solution is to pick a number large enough that it will never, ever be crossed. But this seems like a moving target. It seems you could always need a bigger number.

As such, I'm wondering if there are any alternative solutions instead of picking an arbitrarily large random number as the size of the set of GUIDs.

5

It seems you could always need a bigger number.

Not really. In theory perhaps, obviously there's always a bigger number, but you'll run into limits of physics pretty quickly.

With a random 128 bit ID, you could store around an exabyte of IDs before running into problems with collisions. That's just storing the IDs, presumably you'll want to be storing data associated with those IDs.

If you increase the size to a 256 bit ID it's difficult to even conceive of the number of records you could store without issue. With 512 bits you'd only be a couple orders of magnitude short of being able to randomly generate an ID for every atom in the universe without worrying about collisions.


Wait, you want more IDs?? Ok, since you don't care about practical limitations (such as the likelyhood of the human race going extinct before turning the entire universe into a storage medium, or the lack of desire to use the entire universe as a storage medium in the first place), let's just look at the math behind it then:

  • Let n be the number of IDs you want
  • Let p be the chance of collisions (ie p = 0.01 is a 1% probability)
  • Let b be the minimum number of bits each ID requires

Then, from Wikipedia (also here):

n = sqrt(2 * 2^b * ln(1 / (1 - p))

Solving for b and simplifying:

n^2 = 2 * 2^b * ln(1 / (1 - p))
2^b = n^2 / (2 * ln(1 / (1 - p)))
b * ln(2) = ln(n^2 / (2 * ln(1 / (1 - p))))
b = ln(n^2 / (2 * ln(1 / (1 - p)))) / ln(2)
b = log2(n^2 / (2 * ln(1 / (1 - p))))
b = log2(n^2) - log2(2 * ln(1 / (1 - p)))
b = log2(n^2) - log2(2 * ln((1 - p)^(-1)))
b = log2(n^2) - log2(2 * -ln(1 - p))

Calculating this is another problem, as 1 - p can be small enough to cause significant error (n^2 isn't so much of an issue as any exponent from n can be multiplied outside the log2). You can use log1p to avoid the issue:

b = log2(n^2) - log2(2 * -log1p(-p))

As an arbitrary example, let's suppose the universe can hold 101000 bits of information, and we want to assign each bit of storage its own random identifier with 10-15 chance of collision:

b = log2((10^1000)^2) - log2(2 * -log1p(-10^-15))
b = log2(10^2000) - log2(2 * -log1p(-10^-15))
b = 2000 * log2(10) - log2(2 * -log1p(-10^-15))

Evaluating with the following python:

from math import log, log1p
log2 = lambda x : log(x, 2)
2000 * log2(10) - log2(2 * -log1p(-10**-15))

We get 6692.6851 bits, rounding up to 6693 bits required. Now you can plug in your estimation for the number of bits it's possible to store and you have your answer.


But now we have another problem. If the universe only has 101000 bits of storage space, we can't store 6693*101000 bits of IDs (that's what you get for trying to assign a random ID to every bit of information the universe can store, you maniac).

Let's add some variables and improve the equation:

  • Let d equal the number of data bits to be stored alongside each ID (not counting the size of the ID itself)
  • Let n be the number of bits you can store
  • Let r equal the number of rows you can store (a row being the size of b + d)

Now we can come up with the following equation for r:

r = n / (b + d)
r = n / (log2(r^2) - log2(2 * -ln(1 - p)) + d)

I don't believe this is solvable, but it can be approximated with only a few rounds of recursion starting with a guess of r = n. Since n is so large, some tricks can be used to get an approximate answer:

Let t = log10(r)
log10(r) = log10(n / (log2(r^2) - log2(2 * -ln(1 - p)) + d))
t = log10(n) - log10(log2((10^t)^2) - log2(2 * -ln(1 - p)) + d)
t = log10(n) - log10(2 * t * log2(10) - log2(2 * -ln(1 - p)) + d)
t = log10(n) - log10(2 * t * log2(10) - log2(2 * -log1p(-p)) + d))

Our example of 101000 bits of storage in python, supposing that you only want to store IDs and no associated data:

# -*- coding: utf-8 -*-
from math import log, log1p, ceil
log2 = lambda x : log(x, 2)
log10 = lambda x : log(x, 10)

def id_size(d, n, p):
    t = log10(n)
    old_t = 0
    while t != old_t:
        old_t = t 
        t = log10(n) - log10(2 * t * log2(10) - log2(2 * -log1p(-p)) + d)
    n_log = log10(n)
    n_string = str(10**(n_log % 1)) + str('e') + str(int(n_log))
    print "Given " + n_string + " bits of storage, to generate random IDs with " + str(p) + " chance of collision, each associated with " + str(d) + " bits of data would require " + str(int(ceil(t))) + " bit IDs (t ≈ " + str(t) + ")"

id_size(0, 10**1000, 10**-15)

Resulting in:

Given 9.99999999999e999 bits of storage, to generate random IDs with 1e-15 chance of collision, each associated with 0 bits of data would require 997 bit IDs (t ≈ 996.176051348)
  • I understand that, but an atom is significantly larger than quantum effects, I imagine you could have a 2^512 bits of information per atom lol, stored in quantum something effects. – Lance Pollard Feb 17 at 3:48
  • 2
    @LancePollard Does the edit help? You should probably make it clear in your question that you're thinking on an impractically large theoretical scale. If you want to actually estimate the amount of information the universe could hold, that's probably better suited to physics.stackexchange.com. – AndrolGenhald Feb 17 at 16:38
  • 1
    I guess I didn't really answer your question about an alternative solution, got caught up in the math. Maybe it's at least somewhat useful though. In practice, I don't really see that there's a real issue here in the first place. – AndrolGenhald Feb 17 at 16:42
0

What you seem to be asking about is not Globally Unique IDentifiers (or Universally Unique IDentifiers). Those are generally used when multiple parties need to generate IDs of objects belonging to a shared set and they ensure that there will be no collisions. In your case, one party seems to own all the data, so it can be any type of identifier.

However, let's assume you use UUID version 4 as your identifiers. This gives you 5.3 undecillion identifiers. Unless your doing something at the magnitude of tracking every single bacteria on Earth, you can rest assured you will not run out of identifiers.

  • While there are about 5.3 undecillion IDs possible with UUID version 4, you'll run into collisions well before that (50% probability at around 2.3 quintillion). – AndrolGenhald Feb 17 at 3:37
  • I am wondering how to do this theoretically at the scale of every quantum particle interaction in the universe or to the order of magnitude of the universe of quarks of that. That is, an essentially infinite yet finite size, 10^{120^{120^{120}}}, etc.. So limiting it to something large on earth escapes the question. – Lance Pollard Feb 17 at 3:50
  • Trying to see if there is a solution that doesn't make an arbitrary judgement as to the amount of space you will need. – Lance Pollard Feb 17 at 3:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.