0

I overheard a discussion about using timestamps as unique identifiers when storing some data in a database. Person A pointed out that there's a risk of collisions. Person B replied that it's very unlikely to happen with the identifier generation rates at question.

My question is: how likely is it? Is there a way to estimate the probability of getting a collision, or the amount of collisions you're going to get in some timespan?

I'm interested in both theoretical and practical answers.

closed as unclear what you're asking by Scant Roger, Ixrec, user40980, user22815, gnat Dec 29 '15 at 22:47

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    What algorithm is being used? Just timestamps, or uuids as your tag suggests? – Winston Ewert Dec 26 '15 at 17:38
  • Just whatever way you can get a timestamp. Let's say time.time() in Python or NOW() in PostgreSQL. – Miikka Dec 26 '15 at 17:41
  • 4
    Well, if you have a probability distribution for estimating how many new identifiers you need, then it's easy to estimate collisions (if not, you can only guess). But the real questions are: How bad is it if a collision happens? Can you be certain it will always stay unlikely, no matter what happens to this project in the future? How hard is it in your programming environment to just generate a random number or even a proper guid and not have to think about any of this? – Ixrec Dec 26 '15 at 17:43
  • 3
    Who will be generating the timestamps and with what granularity (second, millisecond, nanosecond)? – Bart van Ingen Schenau Dec 26 '15 at 17:58
  • @Ixrec: +1 for "How bad is it". You can theorize a lot about the probability, but if it happens, you get the downsides and will have to deal with it. If severity of a collision is low, the probability does not matter as much. If severity is really high: don't care about probability, but make it impossible. – Sjoerd Job Postmus Dec 26 '15 at 18:09
13

Firstly, why aren't you using a counter? Usually that's all you need.

Secondly, you should use uuids rather than timestamps. They've solved this problem, and there is no really no good reason for you to try to solve it yourself, potentially opening yourself up to problems.

Thirdly, the calculation you should do is called the birthday problem. The original birthday problem asks how likely it is that two people in a group share a birthday. It should be clear this is pretty much the same as asking how likely it is that two timestamps where generated at the same millisecond (or whatever granularity).

As it turns out, you only need 23 people for the probability of a shared birthday to exceed 50%. This is much less than most people expect (hence sometimes being called the birthday paradox). It's also why there's a good chance that collisions are more likely than you are expecting.

You can read about how to compute it on Wikipedia or use the online calculator at WolfromAlpha:

Just to give an example, if you generate 10 ids a second with a granularity of milliseconds, the probability of a collision is 1 in 23. On average, you'll have a collision every 23 seconds.

But it's worse than that. The assumption in this math is that every possible birthday is equally likely. That's not true for birthdays, more people on born in the spring. It's also not going to be true for your timestamps. You are going to get much heavier on certain times of the day than others.

What's worst of all, is that a sudden increase of usage, resulting in a large increase of the chance of collisions is exactly the time you don't want a mysterious random failure like will result.

Don't use timestamps. Just don't. Use uuids which have been engineered by smart people to avoid the collision problem.

  • 1
    Simple counter doesn't work in non-coordinated distributed systems. UUID generation isn't trivial either; they also use timestamp, but also e.g. machine id, sequence number (per machine), and some entropy. – phadej Dec 27 '15 at 15:16
  • 2
    @phadej, from the development perspective, UUID generation is usually trivial since its typically either in your standard library or package you can install. – Winston Ewert Dec 27 '15 at 17:25
  • The birthday problem is completely irrelevant. The word "timestamp" means both a date and a time (time since epoch). – BobDalgleish Dec 29 '15 at 14:09
  • @BobDalgleish, the name birthday problem is often used to refer to a generalized form as I've done here. – Winston Ewert Dec 29 '15 at 16:27
4

Person A pointed out that there's a risk of collisions. Person B replied that it's very unlikely to happen with the identifier generation rates at question.

Both may be correct for right now, but it isn't right now you care about so much. It's what happens later that will do you in. What happens when the rate you're generating rows increases? What will you do when someone who provided you with a batch of data comes back and says they need to adjust the times because their clocks were wrong and the new values overlap with those of other rows?

B is essentially admitting that it's impossible to guarantee that a collision won't happen. If he can't make that guarantee, he can't guarantee his system will function correctly and will be sent back to the drawing board to come up with a scheme for dealing with them. After coming up with one without the same risks (very likely to involve the counter B doesn't want to use), the rate they occur no longer matters.

Is there a way to estimate the probability of getting a collision, or the amount of collisions you're going to get in some timespan?

Given enough information, sure, but there are a lot of things that would be very difficult to quantify in a way that will give you a meaningful answer.

Alan Kay famously said that the best way to predict the future is to invent it. I'm going to twist that a bit and say that the best way to estimate the probability of a collision is to force it to zero. In this case, that means using the guaranteed-unique primary keys provided by any database worth it salt. Unless you can make an awfully strong case against the extra space required to store them, you're better off going that route instead of a too-clever-by-half solution that tries to embed intelligence into what should be essentially a random number.

1

Consider that for any precision of a time-based ID, you could use the same data type to store a simple counter. This will always accommodate at least as many records as a time-based ID, and probably many more, since the time-based ID wastes potential IDs for every unit of timer resolution in which an ID is not generated.

If the timestamp is meaningful, you could save it separately. In looking for a citation to explain why primary keys should always be arbitrary, I discovered that this is more controversial than I realized; I thought it was settled twenty years ago. Suffice it to say that there are important advantages to using arbitrary, a.k.a. surrogate IDs.

  • 1
    Simple counter doesn't work in non-coordinated distributed system. – phadej Dec 27 '15 at 15:14
  • 2
    @phadej That isn't what the OP described. – Kevin Krumwiede Dec 27 '15 at 17:26

Not the answer you're looking for? Browse other questions tagged or ask your own question.