I'm probably being naive and stupid in ways I'm too stupid to imagine but isn't this basically just id = 0; GET() => id++

▲

alfanick an hour ago | parent | next [-]

Long story short, it always ends up with Lamport's clocks (or some variation of them). Some are easy, some are overly overcomplicated. Some implementation are just reinventing Lamport's clocks, because authors didn't know about them before.

	▲	mrkeen 37 minutes ago \| parent [-]
		I would reach for Lamport clocks in order to avoid the need for sequence number oracle, e.g Alice tells Charlie about lunch plans, then Charlie corrects them, and Bob doesn't need to know about either. Does this implementation actually relate to Lamport clocks in some way?

▲

thruway516 2 hours ago | parent | prev [-]

Yes. Now do it on a production level distributed system with thousands of request per second with network latency and network failure and every race condition you can think of. Orders of magnitude more difficult.

▲

mrkeen an hour ago | parent | next [-]

I'm skeptical in the opposite direction (i.e. too difficult to have been solved)

I believe there's a tension between high-throughput (distributed) and centralised (id++), and I'm not sure it can be wished away.

I built a paxos implementation that could assign values to sequential keys. It runs at a decent speed when there's no contention, but slows down when different paxos nodes are asked to assign to the same key (they argue and retry etc.). A partial solution is to use a leader (i.e. putting id++ on one node), which prevents that kind of chatter.

Another partial solution is topics/partitions (which is just a fancy way of keeping independent id++ counters that don't interfere with one another.). I don't count this as a solution because it's morally equivalent to running multiple clusters that don't know about each other.

I can't quite picture the bookkeeping that would let 10 nodes record contiguous ids without paying the centralisation cost.

▲

QuantumNomad_ 2 hours ago | parent | prev [-]

I don’t understand either.

If I have three machines, all getting a slice of 300 ids each at the same time (same timestamp bits), then there is no way to tell how the total 900 ids are supposed to actually be ordered in terms of what time they happened exactly. You only know the order of each group of 300, but not how the items from the three groups interleave with each other. So then what’s the point of having the timestamp oracle in the first place?

▲

thruway516 an hour ago | parent [-]

Yes, thats the point of a global timestamp oracle- for when you require the 900 ids to be ordered globally across machines for whatever reason. Plenty of use cases/reasons (ordering transactions, maintaining global logs etc). It's the whole point of distributed systems

▲

QuantumNomad_ an hour ago | parent [-]

But I mean, if each node is grabbing batches of ids from the oracle like the “gapless sequence” call of the OP link provides, then there is no way to know how the items in the batches should interleave.

	▲	thruway516 an hour ago \| parent [-]
		That is what the OP is saying, that their implementation guarantees strictly monotonic timestamps (ie it will tell you how they interleave in your parlance). Gapless sequences is a different (but related) problem. Its not a new problem and there are existing solutions, op is just presenting their Rust implementation with some enhancements. I suggest you read the wikipedia article on Race conditions and then read/skim the article on Lamport timestamps to understand what OP is trying to solve/claiming to do.