4 ms·

How about this: 1. A read is returned with a map of the network the replying node has become consistent with. 2. A client that is not satisfied with the map c

How about this: 1. A read is returned with a map of the network the replying node has become consistent with. 2. A client that is not satisfied with the map can read again from the other partition. These two steps get around the proof by changing one of its assumptions (that the operation to read a value can only involve a request to one node).

satisfice 2y ago
How can it know what it is consistent with? Anything could have happened since the last update. All it knows is that it most recently got an update at a certain time. It may or may not be consistent.
fallingsquirrel 2y ago
Consider the following sequence* of events: 1. client A reads from partition X 2. client A is unsatisfied with the network map, and requests another read from partition Y 3. (meanwhile) client B writes a value to partition X 4. client A reads from partition Y, sees the value is the same as partition X's (stale) value, and accepts the value as consistent This is the same kind of behavior you might get if your servers used e.g. a buggy version of Raft or something. You can't get around the proof by just relabeling some of your server nodes as client nodes. * In the spirit of distributed systems, I use this term loosely :)
- Dylan16807 2y ago
  The value is now stale, but it was correct at some point between the read starting and the read finishing, right? That can happen with any read. Even without any partitions. Can't it? In that case I don't see the problem.
  - lmm 2y ago
    > The value is now stale, but it was correct at some point between the read starting and the read finishing, right? Not necessarily. Maybe both versions of it were from partial writes that were never committed, so your invariants are violated (if we're talking about e.g. a credit account A and debit account B scenario). > That can happen with any read. Even without any partitions. Can't it? Depends on your isolation level. If your system has serializable transactions then it's supposed to give you a history equivalent to one where all transactions were executed serially, for example.
    - Dylan16807 2y ago
      > Not necessarily. Maybe both versions of it were from partial writes that were never committed, so your invariants are violated (if we're talking about e.g. a credit account A and debit account B scenario). I'm pretty sure the scenario above is looking at committed writes. If you're reading uncommitted writes, you're not really in the market for consistency to being with. (Or you could be handling consistency by waiting to see if the transaction succeeds or fails, making sure it would fail if the data you read got backed out. But in that situation nothing goes wrong here.) > Depends on your isolation level. If your system has serializable transactions then it's supposed to give you a history equivalent to one where all transactions were executed serially, for example. Even then, a new write can happen before your "read finished" packet arrives at the client, making the read stale. Your entire transaction is now doomed to fail, but you won't know until you try to start committing it. For pure read operations, I'm not convinced it's a proper stale read unless the value was stale before the read operation started.
      - lmm 2y ago
        > I'm pretty sure the scenario above is looking at committed writes. > If you're reading uncommitted writes, you're not really in the market for consistency to being with. But what does "committed" mean when you're only reading from one partition in a partitioned scenario? You literally can't tell whether what you're reading is committed or not (or rather, you have to build your own protocol for when a write is considered committed). > For pure read operations, I'm not convinced it's a proper stale read unless the value was stale before the read operation started. I think you can get a read that is half from a prior stale operation and half from a subsequent uncommitted operation, or something on those lines.
        Dylan16807 2y ago
        > But what does "committed" mean when you're only reading from one partition in a partitioned scenario? I would say you can't make new commits in that situation? I don't know, I didn't make up the scenario, I think you need to figure out your own answer and/or get clarification from fallingsquirrel if you want to talk about that kind of problem. > I think you can get a read that is half from a prior stale operation and half from a subsequent uncommitted operation, or something on those lines. What's the full timeline for that? If you're specifically talking about the ABA problem, that's trivial to fix with a generation counter.
anderskaseorg 2y ago
You’re certainly allowed to make the client a more active participant in your consensus protocol, but then it needs to play by the same rules if you want the system to have guarantees. For example, you need to handle network partitions between clients and some servers, and you need to be able to reconcile multiple reads from servers that might have seen different sets of writes. The CAP theorem still applies to the system as a whole.
deleted 2y ago
[deleted]
Dylan16807 2y ago
Do you have a plan for doing writes in that scenario? It's not proper availability without writes. If the partitions are configured for consistency, and they can't hear from each other, then at most one will accept writes. If the client relays metadata between the partitions to make the write happen in both, then you don't actually have a partition anymore. Also in practical terms, the nodes almost always have better contact with each other than the client has to the nodes. The situation where the client can connect to both sides of a partition is unlikely enough that if you add code for it you're probably getting negative value. It wastes time and can add scary bugs.

satisfice 2y ago

How can it know what it is consistent with? Anything could have happened since the last update. All it knows is that it most recently got an update at a certain time. It may or may not be consistent.

fallingsquirrel 2y ago

Consider the following sequence* of events: 1. client A reads from partition X 2. client A is unsatisfied with the network map, and requests another read from partition Y 3. (meanwhile) client B writes a value to partition X 4. client A reads from partition Y, sees the value is the same as partition X's (stale) value, and accepts the value as consistent This is the same kind of behavior you might get if your servers used e.g. a buggy version of Raft or something. You can't get around the proof by just relabeling some of your server nodes as client nodes. * In the spirit of distributed systems, I use this term loosely :)

Dylan16807 2y ago
The value is now stale, but it was correct at some point between the read starting and the read finishing, right? That can happen with any read. Even without any partitions. Can't it? In that case I don't see the problem.
- lmm 2y ago
  > The value is now stale, but it was correct at some point between the read starting and the read finishing, right? Not necessarily. Maybe both versions of it were from partial writes that were never committed, so your invariants are violated (if we're talking about e.g. a credit account A and debit account B scenario). > That can happen with any read. Even without any partitions. Can't it? Depends on your isolation level. If your system has serializable transactions then it's supposed to give you a history equivalent to one where all transactions were executed serially, for example.
  - Dylan16807 2y ago
    > Not necessarily. Maybe both versions of it were from partial writes that were never committed, so your invariants are violated (if we're talking about e.g. a credit account A and debit account B scenario). I'm pretty sure the scenario above is looking at committed writes. If you're reading uncommitted writes, you're not really in the market for consistency to being with. (Or you could be handling consistency by waiting to see if the transaction succeeds or fails, making sure it would fail if the data you read got backed out. But in that situation nothing goes wrong here.) > Depends on your isolation level. If your system has serializable transactions then it's supposed to give you a history equivalent to one where all transactions were executed serially, for example. Even then, a new write can happen before your "read finished" packet arrives at the client, making the read stale. Your entire transaction is now doomed to fail, but you won't know until you try to start committing it. For pure read operations, I'm not convinced it's a proper stale read unless the value was stale before the read operation started.
    - lmm 2y ago
      > I'm pretty sure the scenario above is looking at committed writes. > If you're reading uncommitted writes, you're not really in the market for consistency to being with. But what does "committed" mean when you're only reading from one partition in a partitioned scenario? You literally can't tell whether what you're reading is committed or not (or rather, you have to build your own protocol for when a write is considered committed). > For pure read operations, I'm not convinced it's a proper stale read unless the value was stale before the read operation started. I think you can get a read that is half from a prior stale operation and half from a subsequent uncommitted operation, or something on those lines.
      - Dylan16807 2y ago
        > But what does "committed" mean when you're only reading from one partition in a partitioned scenario? I would say you can't make new commits in that situation? I don't know, I didn't make up the scenario, I think you need to figure out your own answer and/or get clarification from fallingsquirrel if you want to talk about that kind of problem. > I think you can get a read that is half from a prior stale operation and half from a subsequent uncommitted operation, or something on those lines. What's the full timeline for that? If you're specifically talking about the ABA problem, that's trivial to fix with a generation counter.

anderskaseorg 2y ago

You’re certainly allowed to make the client a more active participant in your consensus protocol, but then it needs to play by the same rules if you want the system to have guarantees. For example, you need to handle network partitions between clients and some servers, and you need to be able to reconcile multiple reads from servers that might have seen different sets of writes. The CAP theorem still applies to the system as a whole.

deleted 2y ago

[deleted]

Dylan16807 2y ago

Do you have a plan for doing writes in that scenario? It's not proper availability without writes. If the partitions are configured for consistency, and they can't hear from each other, then at most one will accept writes. If the client relays metadata between the partitions to make the write happen in both, then you don't actually have a partition anymore. Also in practical terms, the nodes almost always have better contact with each other than the client has to the nodes. The situation where the client can connect to both sides of a partition is unlikely enough that if you add code for it you're probably getting negative value. It wastes time and can add scary bugs.