Check and insert among a million user IDs

A service holds about a million user IDs. Each request carries a user ID: if it is not in the set yet, add it. Decide how to store the IDs and run this check-and-insert, and talk through the trade-offs between latency, memory and accuracy (for example an exact hash set versus a probabilistic structure).