Say I have 500MB of memory to work with, but 100 terabytes of IDs I want to generate. I want these IDs (GUIDs) to be randomly selected and applied to records, so they shouldn't appear in order when selected. Also, I have 1 billion petabytes (in this example) of possible IDs, which is way too many to actually generate. So I only select 100 terabytes initially out of the possible space. I'm not sure how many IDs that would be, but say it's on the order of 10^32 or something large (I don't know the exact number). So basically, this is the situation:
- A gigantic space of possible IDs (10^32, or more precisely I am focusing on the number being 1 billion petabytes, an unreasonably large amount of data).
- A subset of these IDs which are randomly selected. In this case, 100 terabytes of IDs.
- A computer that is limited to 500MB or so, so all the possible IDs needed can't possibly fit into memory.
- The computer only has 10GB of disk space.
The question is how to architect a fast system for generating these IDs.
After some thought my approach was to consider generating a Trie. Say the IDs are 32 characters matching
/[0-9]/. Then we would generate the equivalent of 100 terabytes in the trie, 1 character at a time. This removes the need of storing duplicate characters by probably a few orders of magnitude of memory. But still it would require about 100 terabytes of memory to construct the trie, so that doesn't work.
So basically in the extreme case where we can't possibly store 100TB on the computer or even on a few external hard drives, we need the "cloud" to solve this. That is, we need to somehow use the cloud to check if the IDs have already been used, and then to generate one if it's not been created or used.
The question is how to optimally do this so it takes the least amount of time to generate all the IDs.
Not looking for answers like "don't worry about duplicates", or "that's too many IDs to generate". I would like to know how to specifically solve this problem.
What I have resorted to is basically:
- Check in "cloud" database if record exists.
- If so, try a different value and repeat.
- If not, then save it to the database.
But this is extremely slow and would take weeks of computer time to run and generate the IDs. It seems like there could be a data structure and algorithm to make this faster.