How to generate a random 8 digit string and verify that it was not generated already in feasible amount of time?

I need to generate a random string 8 digit long and next time when I generate the random number make sure it was not already generated. If we simply think I have to store every confirmation number generated and every time I try to generate a new one, verify that it was not already generated by looking at the stored values. But if the already generated numbers are a lot, it can take significant time to validate that. What is the best way to approach this problem?