4 ms·

One of the constraints is that lexicographic sorting must order the nodes by generation time. This precludes wrapping. It's a little weird that they didn't just

One of the constraints is that lexicographic sorting must order the nodes by generation time. This precludes wrapping. It's a little weird that they didn't just reserve or add some bits for sorting within milliseconds before or instead of having to increment the randomness.

jonas21 8y ago
Yeah, they could have constrained the random value to always start with the highest bit set to 0. Then they would be guaranteed to be able to generate 2^79 values per millisecond. But that's sort of an implementation detail. You could write an implementation that did that and still be compatible with all other implementations.
Dylan16807 8y ago
> One of the constraints is that lexicographic sorting must order the nodes by generation time. This precludes wrapping. I suppose, if you're particularly worried about the one-node situation. > It's a little weird that they didn't just reserve or add some bits for sorting within milliseconds before or instead of having to increment the randomness. There's no particular reason to make the fields separate. If you mask out the top bit of the random number then they can share and also make overflow effectively impossible. It's also worth noting that there are two bits that go completely unused. They could eat overflow if the layout was slightly rearranged.
- daveFNbuck 8y ago
  > I suppose, if you're particularly worried about the one-node situation This algorithm doesn't work if you have multiple nodes, so I don't think any other situation is relevant here. > There's no particular reason to make the fields separate. If you mask out the top bit of the random number then they can share and also make overflow effectively impossible Yes, this is what I meant by reserving some bits. > It's also worth noting that there are two bits that go completely unused. They could eat overflow if the layout was slightly rearranged. Yeah, it's super weird they didn't do that. I guess they just really like having a power of two number of bits.
  - Dylan16807 8y ago
    > This algorithm doesn't work if you have multiple nodes Then what's the random part for? > Yes, this is what I meant by reserving some bits. What I'm saying is, if you separate it out into an increment-field and a random-field, then you need a lot of bits and you need to fundamentally change how it works. If you merely make sure your random number starts below some threshold, you only need 1 bit, or a small fraction of a bit. You would still increment the random number, but you wouldn't have to worry about hitting the max value if you always start between 0 and 2^79.9, for example.
    - daveFNbuck 8y ago
      > Then what's the random part for? It's for multiple nodes, which is why this algorithm doesn't make any sense for their use case.

jonas21 8y ago

Yeah, they could have constrained the random value to always start with the highest bit set to 0. Then they would be guaranteed to be able to generate 2^79 values per millisecond. But that's sort of an implementation detail. You could write an implementation that did that and still be compatible with all other implementations.

Dylan16807 8y ago

> One of the constraints is that lexicographic sorting must order the nodes by generation time. This precludes wrapping. I suppose, if you're particularly worried about the one-node situation. > It's a little weird that they didn't just reserve or add some bits for sorting within milliseconds before or instead of having to increment the randomness. There's no particular reason to make the fields separate. If you mask out the top bit of the random number then they can share and also make overflow effectively impossible. It's also worth noting that there are two bits that go completely unused. They could eat overflow if the layout was slightly rearranged.

daveFNbuck 8y ago
> I suppose, if you're particularly worried about the one-node situation This algorithm doesn't work if you have multiple nodes, so I don't think any other situation is relevant here. > There's no particular reason to make the fields separate. If you mask out the top bit of the random number then they can share and also make overflow effectively impossible Yes, this is what I meant by reserving some bits. > It's also worth noting that there are two bits that go completely unused. They could eat overflow if the layout was slightly rearranged. Yeah, it's super weird they didn't do that. I guess they just really like having a power of two number of bits.
- Dylan16807 8y ago
  > This algorithm doesn't work if you have multiple nodes Then what's the random part for? > Yes, this is what I meant by reserving some bits. What I'm saying is, if you separate it out into an increment-field and a random-field, then you need a lot of bits and you need to fundamentally change how it works. If you merely make sure your random number starts below some threshold, you only need 1 bit, or a small fraction of a bit. You would still increment the random number, but you wouldn't have to worry about hitting the max value if you always start between 0 and 2^79.9, for example.
  - daveFNbuck 8y ago
    > Then what's the random part for? It's for multiple nodes, which is why this algorithm doesn't make any sense for their use case.