Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Flake: A Decentralized, K-Ordered Unique ID Generator in Erlang

blog.boundary.com

Post reply on HN
Print view View original

11–18 of 18 posts

Re: Flake: A Decentralized, K-Ordered Unique ID Generator in Erlang

#11

Post by rdtsc »

mjb wrote: post #9
rdtsc wrote: post #7

Earlier quoted context omitted.

> Why [time, node id, seq] and not [time, seq, node id] Would you rely on sub-millisecond synchronization between nodes _and_ an almost exact load amount? In other words for a particular millisecond seq order is only relevant on that particular node, so node should come first.

> In other words for a particular millisecond seq order is only relevant on that particular node, so node should come first. It still seems to me that T_0,0,A (issued by node A at T_0 with seq number 0) would tend to come before T_0,1,B so putting the sequence number first does add some value. On the other hand, the ordering T_0,A,0 > Would you rely on sub-millisecond synchronization between nodes _and_ an almost exa…

> On the other hand, the ordering T_0,A,0 Still don't see it. We are already making the assumption that the millisecond part is the same T_0. So then seq will depend strictly on the count of previous such IDs issued by that node only (would you agree with that?). So that is why I said that it doesn't make sense to compare seq number from A -- (0) and a seq number of B -- (1) before considering the identity of A & B. You would effectively order by relative load between all your machines at that particular time, at that time frame it would be things like disk access, cache states and so on.

EDIT:

In addition. Ordering T_0,A,0 Let's look at a longer example:

T_0,A,0

T_0,A,1

T_0,B,0

T_0,B,1

T_0,B,2

T_0,B,3

T_0,C,1

T_0,C,2

T_0,C,3

T_0,D,0

I think is a lot better order than

T_0,0,A

T_0,0,B

T_0,0,C

T_0,0,D

T_0,1,A

T_0,1,B

T_0,1,C

T_0,2,B,

T_0,2,C

T_0,3,B

T_0,3,C

Re: Flake: A Decentralized, K-Ordered Unique ID Generator in Erlang

#12

Post by jerf »

mjb wrote: post #2

A couple of questions about this: - Why [time, node id, seq] and not [time, seq, node id]? That would improve ordering if you have approximately equal load on each box. - Isn't a 16 bit seq number overkill? Handing some of those bits to the unique ID would have made unique ID assignment easier. Duplicate MACs can and do exist (especially if you buy a lot of hardware from the same vendors). - The quality of the orderi…

Funny, I thought the exact opposite about the sequence numbers; 16-bit sequence number is cutting it awfully fine for a "unique" ID in the space of a millisecond. Slow-as-molasses Perl can count to 2^16 in 3ms on my machine. Cutting bits out of the node id by hashing MAC, interface name, and a few other things and giving that to the sequence would have made more sense to me. (And you do that hash once at init time.)

In information theory terms, the node ids are carrying log2(number of nodes) bits of information, whereas the node ids are carrying something more like log2(maximum seq id). The latter is almost certainly larger than the former, and at 16 computer-bits allocated for the sequence number overflow would be a real concern of mine, if not on this year's hardware than in a few more years.

Re: Flake: A Decentralized, K-Ordered Unique ID Generator in Erlang

#15

Post by foobarbazetc »

thezilch wrote: post #8
alpb wrote: post #6

For those interested, there is also Snowflake by Twitter on GitHub https://github.com/twitter/snowflake

Snowflake is referenced in the article "Credits" with a distinction between the products -- though, the product name is a bit dubious. It [Flake] differs primarily in that we allow ourselves a wider address space in which to fit ids which means we don’t have to think about timestamp truncation or coordination of worker ids.

Yeah. But the hard part is the 64bit representation. If you have 128 bits, you can no longer be a standard int. And you can just use UUIDs if you don't care about k-ordering.

Re: Flake: A Decentralized, K-Ordered Unique ID Generator in Erlang

#16

Post by mumrah »

mjb wrote: post #2

A couple of questions about this: - Why [time, node id, seq] and not [time, seq, node id]? That would improve ordering if you have approximately equal load on each box. - Isn't a 16 bit seq number overkill? Handing some of those bits to the unique ID would have made unique ID assignment easier. Duplicate MACs can and do exist (especially if you buy a lot of hardware from the same vendors). - The quality of the orderi…

You'd be hard pressed to generate 2^16-1 ids in a millisecond, so yea - it's probably overkill.
Post reply on HN