Generating unique tokens in a NodeJS, Crypto Token authentication environment

Using nodejs and crypto, right now, when a user logs in, I generate a random auth token:

var token = crypto.randomBytes(16).toString('hex');

I know it's unlikely, but there is a tiny chance for two tokens to be of the same value.

This means a user could, in theory, authenticate on another account.

Now, I see two obvious methods to get pass this:

When I generate the token, query the user's database and see if a Token with the same value already exists. If it does, just generate another one. As you can see, this is not perfect since I am adding queries to the database.
Since every user has a unique username in my database, I could
generate a random token using the username as a secret generator key. This way, there is no way of two tokens having the same value. Can crypto do that? Is it secure?

How would you do it?

Solution

It's too unlikely to worry about it happening by chance. I would not sacrifice performance to lock and check the database for it.

Consider this excerpt from Pro Git about the chance of random collisions between 20-byte SHA-1 sums:

Here’s an example to give you an idea of what it would take to get a SHA-1 collision [by chance]. If all 6.5 billion humans on Earth were programming, and every second, each one was producing code that was the equivalent of the entire Linux kernel history (1 million Git objects) and pushing it into one enormous Git repository, it would take 5 years until that repository contained enough objects to have a 50% probability of a single SHA-1 object collision. A higher probability exists [for average projects] that every member of your programming team will be attacked and killed by wolves in unrelated incidents on the same night.

(SHA-1 collisions can be directly constructed now, so the quote is now less applicable to SHA-1, but it's still valid when considering collisions of random values.)

If you are still worried about that probability, then you can easily use more random bytes instead of 16.

But regarding your second idea: if you hashed the random ID with the username, then that hash could collide, just like the random ID could. You haven't solved anything.