Is it safe to assume boost::uuid won't return

问题:

I'm using boost uuid to generate session ids.

std::string SessionGenerator::generate()
{
    boost::uuids::uuid id = m_rgen();
    m_ss.clear();
    m_ss.str("");
    m_ss << id;

    return m_ss.str();
}

Is it safe to assume that I'm never going to get a duplicate or should I be doing checks against active sessions?

Thanks

回答1:

Well, it depends.

When UUIDs are generated by one of the defined mechanisms, they are either guaranteed to be unique, different from all other generated UUIDs (that is, it has never been generated before and it will never be generated again), or it is extremely likely to be unique (depending on the mechanism).

It means that the problem may be on the generator you're using. They say they're using ITU-T specification.

Let's go to page 7 of the document. If you're using time and you can assume that:

• System time will not change.
• Node ID used to identify the machine won't change.

Then you can at least assert that:

"The UUID will be different from all other generated UUIDs" because time flows and the granularity is 100 ns.

There could be a collision if you need to share generated UUID with other machines or the time will change (do not forget that twice per year in many country there is time adjustment). That's why there is a Clock sequence field. Moreover it's pretty small so in this case you fall to assert that:

"The UUID is extremely likely to be unique."

If you're using, instead of this, a random number generator then you can assert only that:

"The UUID is extremely likely to be unique." because the requirement of a random number generator is not to generate unique numbers (but with a good random number generator your extremely likely will be EXTREMELY likely).

So in normal conditions (for example if you do not move one network card from one computer to the other and you change the time back to the past) I suppose that you can assume they're unique (using time). If you're using a random number generator you can't assume they're unique but just extremely likely to be unique (about probability of collisions...well...if it happens with a good random number generator you should stay at home for the next meteor shower).

References
http://blogs.msdn.com/b/oldnewthing/archive/2008/06/27/8659071.aspx
http://en.wikipedia.org/wiki/Birthday_attack

回答2:

If a single generator is producing all your uuids, they should be guaranteed unique. Disclaimer, I haven't looked at the code or documentation to verify this, but it is a design goal.

There are different classes of uuids, some of which include bits from the machine or environment on which it's running. Those will lessen the chances of collision with IDs produced elsewhere.

Even in the worst case, your chances of mangling an ID due to RAM errors are much higher than producing two identical IDs. And nobody worries about that.

回答3:

No you cannot assume that you never get a duplicate.
BUT you can have a look at wikipedia for the probability to get a duplicate.
And since boost followed the ITU specification, I think you can assume that there will never be a duplicate.