3 ms·

I think the whole idea of generating random ids is flawed. Why take a chance when there is no need? Just take some machine id (seq. number, MAC), timestamp and

by Drdrdrq 11y ago

I think the whole idea of generating random ids is flawed. Why take a chance when there is no need? Just take some machine id (seq. number, MAC), timestamp and a big enough per-machine counter and there can be no collision, guaranteed. No need to use random.voodoo().

sgk284 11y ago
Hardware companies have definitely been lazy and reused MAC addresses. But what's worse is that the total space is as low as 48 bits. The probability of a collision is orders of magnitude higher than if you just grab some random bytes out of /dev/urandom and generate a type-4 UUID. For a discussion on the benefits of your approach (a type-1 UUID) vs a random id (a type-4 UUID), check out the wikipedia article: https://en.wikipedia.org/wiki/Universally_unique_identifier https://en.wikipedia.org/wiki/Universally_unique_identifier Randomness is great because it doesn't require any synchronization or access to some special token.
- michaelmior 11y ago
  If you get identical MAC addresses on machines operating the same service, presumably on the same network, you have bigger problems than ID generation.
- Drdrdrq 11y ago
  Mac addresses should be unique; at least for network cards. The address space of 48bits is not that small. Also, see the warning about entropy in your linked article. There is a difference between mathematical random() and CS random().
mmalone 11y ago
It's easier to generate a random identifier and if the generator is good the probability of a collision is lower than the probability that you HDD will fuck up in an uncorrectable way while storing the identifier (as I've pointed out elsewhere in thread). So the answer is that random identifiers are easier to do in a distributed system and, in reality, have the same guarantees.
- Drdrdrq 11y ago
  Sure. But you are not lowering one risk on account of the other, so what's that got to do with anything? You will still have the same chance of HDD error, but now you also add a (admittedly small) chance of id collision. As for simplicity... You need some unique device identifiers in any distributed system, so why not just use these? I know MongoDB is not popular around here, but their ObjectIds are (imho) a much better approach than yours. Much more robust and less prone to errors when planets align just right. That said, I have seen worse solutions than yours and made my share of bad decisions too, so I don't judge you. This is just a technical opinion, given that this particular problem wouldn't even exist if you avoided randomness.
  - mmalone 11y ago
    There are legitimate reasons to have / not have some form of node id, and/or a timestamp, in an identifier. One reason to have them is that you don't need as good a PRNG. However, with a good PRNG the collision probabilities are astronomically low either way. The point of the comparison to HDD error rates is meant to indicate that the collision probability is well within what is typically considered an acceptable risk level. There's a higher probability of much worse things happening, and I accept those risks for similar pragmatic reasons. Why should I behave any differently in this case? I do encourage anyone implementing this sort of system to do the math themselves and take whatever precautions they deem necessary. I've done so and decided that the additional complexity and space trade off of the alternative approaches make them inferior for our use cases. That doesn't mean ours is universally the best choice. That's why we have UUID1 and UUID4, for instance.
    - Drdrdrq 11y ago
      Ok, we seem to have different approaches... :) I understand your position, I just think other (deterministic) solutions are safer (meaning: less likely to cause trouble). I know it is easy to be smart now that we know what happened, but I think the post nicely shows some of the dangers when using nondeterministic ids. I am quite sure it would be easier to find cause for duplicates if you were not using random. Anyway, at least you caught a nice bug. :)

by Drdrdrq 11y ago

sgk284 11y ago

Hardware companies have definitely been lazy and reused MAC addresses. But what's worse is that the total space is as low as 48 bits. The probability of a collision is orders of magnitude higher than if you just grab some random bytes out of /dev/urandom and generate a type-4 UUID. For a discussion on the benefits of your approach (a type-1 UUID) vs a random id (a type-4 UUID), check out the wikipedia article: https://en.wikipedia.org/wiki/Universally_unique_identifier https://en.wikipedia.org/wiki/Universally_unique_identifier Randomness is great because it doesn't require any synchronization or access to some special token.

michaelmior 11y ago
If you get identical MAC addresses on machines operating the same service, presumably on the same network, you have bigger problems than ID generation.
Drdrdrq 11y ago
Mac addresses should be unique; at least for network cards. The address space of 48bits is not that small. Also, see the warning about entropy in your linked article. There is a difference between mathematical random() and CS random().

mmalone 11y ago

It's easier to generate a random identifier and if the generator is good the probability of a collision is lower than the probability that you HDD will fuck up in an uncorrectable way while storing the identifier (as I've pointed out elsewhere in thread). So the answer is that random identifiers are easier to do in a distributed system and, in reality, have the same guarantees.

Drdrdrq 11y ago
Sure. But you are not lowering one risk on account of the other, so what's that got to do with anything? You will still have the same chance of HDD error, but now you also add a (admittedly small) chance of id collision. As for simplicity... You need some unique device identifiers in any distributed system, so why not just use these? I know MongoDB is not popular around here, but their ObjectIds are (imho) a much better approach than yours. Much more robust and less prone to errors when planets align just right. That said, I have seen worse solutions than yours and made my share of bad decisions too, so I don't judge you. This is just a technical opinion, given that this particular problem wouldn't even exist if you avoided randomness.
- mmalone 11y ago
  There are legitimate reasons to have / not have some form of node id, and/or a timestamp, in an identifier. One reason to have them is that you don't need as good a PRNG. However, with a good PRNG the collision probabilities are astronomically low either way. The point of the comparison to HDD error rates is meant to indicate that the collision probability is well within what is typically considered an acceptable risk level. There's a higher probability of much worse things happening, and I accept those risks for similar pragmatic reasons. Why should I behave any differently in this case? I do encourage anyone implementing this sort of system to do the math themselves and take whatever precautions they deem necessary. I've done so and decided that the additional complexity and space trade off of the alternative approaches make them inferior for our use cases. That doesn't mean ours is universally the best choice. That's why we have UUID1 and UUID4, for instance.
  - Drdrdrq 11y ago
    Ok, we seem to have different approaches... :) I understand your position, I just think other (deterministic) solutions are safer (meaning: less likely to cause trouble). I know it is easy to be smart now that we know what happened, but I think the post nicely shows some of the dangers when using nondeterministic ids. I am quite sure it would be easier to find cause for duplicates if you were not using random. Anyway, at least you caught a nice bug. :)