3 ms·

Seems like you could use a combination of time and unique machine ids to generate ordered sequences in a distributed system without the need for nodes to talk t

Seems like you could use a combination of time and unique machine ids to generate ordered sequences in a distributed system without the need for nodes to talk to each other.

felixgallo 11y ago
you can use time and unique machine IDs to get a unique identifier, but you can't get an ordering property in the absence of coordination.
phpnode 11y ago
It certainly seems that way, but one of the fundamental rules here is that you can't ordinarily trust clocks to keep in sync, they drift, jump backwards and forwards etc. Google solve this problem using synchronized atomic clocks in their data centres, which is not an option for most systems running on commodity hardware.
jdp 11y ago
That's the intuition behind systems like Flake (https://github.com/boundary/flake https://github.com/boundary/flake) and its predecessors. In systems like Flake you are able to get a useful roughly-ordered property which is good for generating ID's and organizing things like activity feeds. Things will be mostly sorted by time by encoding the time in the most significant bits, but they will be fuzzy because of machine and sequence ID's in the LSB's. You will get monotonically increasing ID's per-process because each one spinlocks locally against backwards drift, but you're not guaranteed to get monotonically increasing ID's globally across all processes. One process' time might drift forward, or you might have two ID's at the same time but the instance with the higher machine ID responded first.
gumballhead 11y ago
That's basically how Twitter Snowflake (https://blog.twitter.com/2010/announcing-snowflake https://blog.twitter.com/2010/announcing-snowflake) and Instragram (http://instagram-engineering.tumblr.com/post/10853187575/sharding-ids-at-instagram http://instagram-engineering.tumblr.com/post/10853187575/sha...) did it
gumballhead 11y ago
I also think that's how mobile databases for offline apps should work -- sort of as distributed slaves. If only the backend server has the authority to create unique ids, you end up juggling a complicated set of client and server based ids if your app needs to be able to create data offline.

Seems like you could use a combination of time and unique machine ids to generate ordered sequences in a distributed system without the need for nodes to talk to each other.

felixgallo 11y ago

you can use time and unique machine IDs to get a unique identifier, but you can't get an ordering property in the absence of coordination.

phpnode 11y ago

It certainly seems that way, but one of the fundamental rules here is that you can't ordinarily trust clocks to keep in sync, they drift, jump backwards and forwards etc. Google solve this problem using synchronized atomic clocks in their data centres, which is not an option for most systems running on commodity hardware.

jdp 11y ago

That's the intuition behind systems like Flake (https://github.com/boundary/flake https://github.com/boundary/flake) and its predecessors. In systems like Flake you are able to get a useful roughly-ordered property which is good for generating ID's and organizing things like activity feeds. Things will be mostly sorted by time by encoding the time in the most significant bits, but they will be fuzzy because of machine and sequence ID's in the LSB's. You will get monotonically increasing ID's per-process because each one spinlocks locally against backwards drift, but you're not guaranteed to get monotonically increasing ID's globally across all processes. One process' time might drift forward, or you might have two ID's at the same time but the instance with the higher machine ID responded first.

gumballhead 11y ago

That's basically how Twitter Snowflake (https://blog.twitter.com/2010/announcing-snowflake https://blog.twitter.com/2010/announcing-snowflake) and Instragram (http://instagram-engineering.tumblr.com/post/10853187575/sharding-ids-at-instagram http://instagram-engineering.tumblr.com/post/10853187575/sha...) did it

gumballhead 11y ago

I also think that's how mobile databases for offline apps should work -- sort of as distributed slaves. If only the backend server has the authority to create unique ids, you end up juggling a complicated set of client and server based ids if your app needs to be able to create data offline.