9 comments

  • pnathan 8 hours 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 8 hours 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?

  • hansvm 10 hours 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 13 hours 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 11 hours 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 9 hours 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 9 hours 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 10 hours 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.
      • speedstyle 18 minutes 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
      • mrkeen 9 hours 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.

      • QuantumNomad_ 10 hours 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 10 hours 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_ 9 hours 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 9 hours 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 8 hours 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 11 minutes ago
                  In the sense that a client couldn't have received milkshake 3 before ordering burger 8. But yes, many numberings might satisfy this
                • QuantumNomad_ 6 hours ago
                  Yes, exactly :)
  • patryk_builds 10 hours ago
    [flagged]
  • arbor-group 9 hours ago
    [flagged]
  • feralcortex 12 hours ago
    [flagged]
  • fwlr 12 hours ago
    [flagged]