Rendered at 17:21:07 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
pnathan 1 days ago [-]
Intuitively, this is not possible at speed. These properties do not combine under failure.
On the other hand, intuition is wrong periodically. Is there a TLA+ proof?
lmz 1 days ago [-]
The "gapless sequence" would need some very strong guarantees from the client / caller to actually make it gapless as the caller can have its own failure after advancing the sequence. I don't think this actually does 2 phase commit, does it?
Edit: it says you should reconcile when the sequence is uncertain - maybe I'm stupid but I don't see a method to do so on the client?
vlovich123 1 days ago [-]
[flagged]
hansvm 1 days ago [-]
Something seems fishy here. What am I missing?
> no torn state
Doesn't there exist a failure mode where you allocate from a batch, fsync that you've done that allocation, the application fails to do anything with that counter, and you thereby introduce a gap in whichever "gapless" sequence you're trying to construct? The primitive exposed here might be able to be gapless, but the API doesn't look like it'll compose nicely into creating an application with the gapless property you're trying to enforce.
That desync between application state and tsoracle state seems more likely when you consider other features like requesting a batch of timestamps (which is necessary to hit the stated performance numbers).
> gapless, high-throughput, monotonic
WAT? You don't get all three of these at once with any implementation. Looking at this implementation, you (as predicted) don't get it here either. It basically uses a partitioned allocation strategy -- allocate a window to each node, each node allocates from its window (seems at first blush like a reasonably good implementation of that strategy, not knocking it, at least not without reading further). That's not both gapless and monotonic though. Absolutely nothing enforces within-window synchronization from one node to the next. You do (eventually) get gaplessness if no node is ever eventually always idle, but only because you explicitly left a hole to fill as you allocated a bigger number before sometimes filling that hole with a smaller number. It's not monotonic.
Edit 1: Okay, I see, the sequence interface is different from the timestamp interface. That resolves the "gapless, high-throughput, monotonic" concern. Not the other points yet.
Edit 2: Yeah, I have a lot of concerns about the timestamp itself re monotonicity. It looks like [physical_ms: u46; logical: u18]. There's basically no high-throughput way to use a structure like that to enforce monotonicity in any meaningful way across nodes. To illustrate the problem (not a proof, just intuition-building), zoom in right next to a physical ms boundary. Microseconds of skew can cause two machines right next to each other to issue timestamps on one side or the other of that boundary. No matter what you do with the logical partition, that noise is going to dominate the resulting sort order. If those two nodes publish their respective timestamps, you can absolutely see a later timestamp before you see an earlier timestamp. You could even have the slow node observe time t+1 from the fast node and then afterward produce time t. Maybe the devil's in the details with the definition of "monotonic," but that seems like an incredibly hard abstraction to use correctly. This is marketed as providing timestamps you can use to order events across machines, but I'm not seeing anything better than what you would get with just a per-node monotonic clock.
LoganDark 1 days ago [-]
Do we know that this benefits from the same domain specific optimization that an organically made implementation would? Have you performed real-world comparative benchmarks? Stuff like this doesn't just come out of the blue with AI. Not saying you did a bad job, just skeptical
gr__or 1 days ago [-]
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 1 days ago [-]
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 1 days ago [-]
I would reach for Lamport clocks in order to avoid the need for a sequence number oracle, e.g Alice tells Charlie about lunch plans, then Charlie corrects them, and Bob (or some central server) doesn't need to know about either.
Does this implementation actually relate to Lamport clocks in some way?
thruway516 1 days ago [-]
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 1 days ago [-]
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.
speedstyle 17 hours ago [-]
Make it less distributed. A single leader can serialize hundreds of thousands of requests, even with the replication for proper consistency. It may not be 'scalable' beyond that, but very few systems are, the OP's problem statement has 100% contention. Ideally you can avoid having such a problem
QuantumNomad_ 1 days ago [-]
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 1 days ago [-]
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_ 1 days ago [-]
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 1 days ago [-]
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.
mrkeen 1 days ago [-]
I believe Quantum is saying:
Burger maker is granted seqnos 0..9
Milkshake maker is granted seqnos 10..19
They both get busy serving their items as quickly as possible
In what sense can we declare that burger eight (#7) was served before milkshake three (#12) ?
speedstyle 17 hours ago [-]
In the sense that a client couldn't have received milkshake 3 before ordering burger 8. But yes, many numberings might satisfy this
On the other hand, intuition is wrong periodically. Is there a TLA+ proof?
Edit: it says you should reconcile when the sequence is uncertain - maybe I'm stupid but I don't see a method to do so on the client?
> no torn state
Doesn't there exist a failure mode where you allocate from a batch, fsync that you've done that allocation, the application fails to do anything with that counter, and you thereby introduce a gap in whichever "gapless" sequence you're trying to construct? The primitive exposed here might be able to be gapless, but the API doesn't look like it'll compose nicely into creating an application with the gapless property you're trying to enforce.
That desync between application state and tsoracle state seems more likely when you consider other features like requesting a batch of timestamps (which is necessary to hit the stated performance numbers).
> gapless, high-throughput, monotonic
WAT? You don't get all three of these at once with any implementation. Looking at this implementation, you (as predicted) don't get it here either. It basically uses a partitioned allocation strategy -- allocate a window to each node, each node allocates from its window (seems at first blush like a reasonably good implementation of that strategy, not knocking it, at least not without reading further). That's not both gapless and monotonic though. Absolutely nothing enforces within-window synchronization from one node to the next. You do (eventually) get gaplessness if no node is ever eventually always idle, but only because you explicitly left a hole to fill as you allocated a bigger number before sometimes filling that hole with a smaller number. It's not monotonic.
Edit 1: Okay, I see, the sequence interface is different from the timestamp interface. That resolves the "gapless, high-throughput, monotonic" concern. Not the other points yet.
Edit 2: Yeah, I have a lot of concerns about the timestamp itself re monotonicity. It looks like [physical_ms: u46; logical: u18]. There's basically no high-throughput way to use a structure like that to enforce monotonicity in any meaningful way across nodes. To illustrate the problem (not a proof, just intuition-building), zoom in right next to a physical ms boundary. Microseconds of skew can cause two machines right next to each other to issue timestamps on one side or the other of that boundary. No matter what you do with the logical partition, that noise is going to dominate the resulting sort order. If those two nodes publish their respective timestamps, you can absolutely see a later timestamp before you see an earlier timestamp. You could even have the slow node observe time t+1 from the fast node and then afterward produce time t. Maybe the devil's in the details with the definition of "monotonic," but that seems like an incredibly hard abstraction to use correctly. This is marketed as providing timestamps you can use to order events across machines, but I'm not seeing anything better than what you would get with just a per-node monotonic clock.
Does this implementation actually relate to Lamport clocks in some way?
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.
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?