5 ms·

Yes. Linearizable means both serializable and externally consistent (or is sometimes used as just a synonym for the latter), and FDB has these properties with r

Yes. Linearizable means both serializable and externally consistent (or is sometimes used as just a synonym for the latter), and FDB has these properties with respect to transactions.

polskibus 8y ago
That would mean that SSI is not used to provide Serializable isolation. level. If so, what is used instead? 2 phase locking? I thought it's not very scalable ?
- voidmain 8y ago
  I explain the basics of our concurrency control here: https://news.ycombinator.com/item?id=16877950 https://news.ycombinator.com/item?id=16877950 I guess textbook SSI is willing to "reorder" conflicting transactions if the result is still serializable, which could violate external consistency if you don't have any other bounds on the order. In the language of SSI, fdb simply aborts the later of any pair of read/write transactions with an rw-conflict, in accordance with a fixed ordering which is externally consistent. I guess it could also be that your book uses an idiosyncratic definition of linearizable, like trying to apply it to individual operations within transactions, which might rule out any optimistic concurrency method. It might just be better to delete this word from your vocabulary in the database field because there is no wide agreement on what it means. The first two hits on Google for me are Wikipedia and Peter Bailis, and they give clearly conflicting definitions, though I think fdb satisfies both!
  - polskibus 8y ago
    Thanks, I'd love to have a bit more of your attention, foundationdb seems very interesting but I need to know a bit more :) Let me expand the definition in Kleppmann's book then.I think it is important because it creates a difference between SSI and typical Serializable level based on 2PL. The below is paraphrasing the definitions on p. 324-329. The book references http://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf http://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf. (I must admit, I read the book, not the paper). Basic idea - make a system appear as if there were only one copy of the data and ALL operations on it are atomic. In this model, there may be replicas, but we don't care about them. As soon as a client completes a write to the db, all clients reading the db must be able to see the value just written. In SSI this is not true, because you may the snapshot may not include writes more recent than the snapshot -> reads from the snapshot are not lineraizable. Linearizable CAS register is equivalent to consensus, and can provide total order. It is therefore what most developers would love to have (if cost was not an issue :) )
    - voidmain 8y ago
      From the paper you link: "A history is serializable if it is equivalent to one in which transactions appear to execute sequentially, i.e., without interleaving... A history is strictly serializable if the transactions’ order in the sequential history is compatible with their precedence order... Linearizability can be viewed as a special case of strict serializability where transactions are restricted to consist of a single operation applied to a single object." In these terms, FoundationDB has the strict serializability property, and thus if you do exactly one operation in each FoundationDB transaction then that is linearizable. But that kind of linearizability is much less powerful than what FoundationDB actually gives you. You cannot efficiently maintain global invariants, like indexes, with single-operational linearizability. I don't think this definition is very useful! I think strict serializability (which is to say serializability & external consistency) is what you actually want. A linearizable CAS register can be implemented in FDB as simply as this: @fdb.transactional def compare_and_set( tr, key, vold, vnew ): if tr[key] == vold: tr[key] = vnew but this is not the limit of what you can do.
      - polskibus 8y ago
        Thank you very much for your in-depth explanation, I believe the only thing left for me is to run FDB myself, sounds very promising :) FDB replacing zookeper + sth else would reduce the complexity of target distributed system, almost too good to be true.
  - polskibus 8y ago
    as far as I know SSI as implemented in Postgresql, aborts the way you describe, as per https://drkp.net/papers/ssi-vldb12.pdf https://drkp.net/papers/ssi-vldb12.pdf
    - benmmurphy 8y ago
      postgresql is not strictly serializable/externally consistent for example this will commit under serializable: create table counters(counter int); insert into counters(counter) values(1); BEGIN TRANSACTION ISOLATION LEVEL serializable; select sum(counter) from counters; /* insert sum into counters. wait until committing next transaction before executing the insert */ insert into counters(counter) values(1); COMMIT; /* this transaction should commit before doing the insert in the above transaction and after the above transaction has calculated the sum */ BEGIN TRANSACTION ISOLATION LEVEL serializable; insert into counters(counter) values(10); COMMIT; both transactions commit and the final table looks like: 1, 10, 1 which is possible if the first transaction committed first, and then the second transaction committed. but it is possible for another client to see the table as: [1], [1, 10], [1, 1, 10] which is a sequence of states which should not be possible. if you see [1], [1, 10] then you should see [1, 10, 11] as the last state. hence it violates external consistency.
      - cakoose 8y ago
        Even without external consistency, a I'm having trouble coming up with an ordering of the transactions that yields [1], [1, 10], [1, 1, 10]. Is that because PostgreSQL's "SERIALIZABLE" doesn't follow the "some serial order" definition? Or maybe I'm missing something else?
        anarazel 8y ago
        Well, benmmurphy isn't talking about serializability (some correct ordering exists), but strict serializabilty (roughly: at least one correct ordering corresponds to wall clock order). PG does have the former, but not the latter.

Yes. Linearizable means both serializable and externally consistent (or is sometimes used as just a synonym for the latter), and FDB has these properties with respect to transactions.

polskibus 8y ago

That would mean that SSI is not used to provide Serializable isolation. level. If so, what is used instead? 2 phase locking? I thought it's not very scalable ?

voidmain 8y ago
I explain the basics of our concurrency control here: https://news.ycombinator.com/item?id=16877950 https://news.ycombinator.com/item?id=16877950 I guess textbook SSI is willing to "reorder" conflicting transactions if the result is still serializable, which could violate external consistency if you don't have any other bounds on the order. In the language of SSI, fdb simply aborts the later of any pair of read/write transactions with an rw-conflict, in accordance with a fixed ordering which is externally consistent. I guess it could also be that your book uses an idiosyncratic definition of linearizable, like trying to apply it to individual operations within transactions, which might rule out any optimistic concurrency method. It might just be better to delete this word from your vocabulary in the database field because there is no wide agreement on what it means. The first two hits on Google for me are Wikipedia and Peter Bailis, and they give clearly conflicting definitions, though I think fdb satisfies both!
- polskibus 8y ago
  Thanks, I'd love to have a bit more of your attention, foundationdb seems very interesting but I need to know a bit more :) Let me expand the definition in Kleppmann's book then.I think it is important because it creates a difference between SSI and typical Serializable level based on 2PL. The below is paraphrasing the definitions on p. 324-329. The book references http://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf http://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf. (I must admit, I read the book, not the paper). Basic idea - make a system appear as if there were only one copy of the data and ALL operations on it are atomic. In this model, there may be replicas, but we don't care about them. As soon as a client completes a write to the db, all clients reading the db must be able to see the value just written. In SSI this is not true, because you may the snapshot may not include writes more recent than the snapshot -> reads from the snapshot are not lineraizable. Linearizable CAS register is equivalent to consensus, and can provide total order. It is therefore what most developers would love to have (if cost was not an issue :) )
  - voidmain 8y ago
    From the paper you link: "A history is serializable if it is equivalent to one in which transactions appear to execute sequentially, i.e., without interleaving... A history is strictly serializable if the transactions’ order in the sequential history is compatible with their precedence order... Linearizability can be viewed as a special case of strict serializability where transactions are restricted to consist of a single operation applied to a single object." In these terms, FoundationDB has the strict serializability property, and thus if you do exactly one operation in each FoundationDB transaction then that is linearizable. But that kind of linearizability is much less powerful than what FoundationDB actually gives you. You cannot efficiently maintain global invariants, like indexes, with single-operational linearizability. I don't think this definition is very useful! I think strict serializability (which is to say serializability & external consistency) is what you actually want. A linearizable CAS register can be implemented in FDB as simply as this: @fdb.transactional def compare_and_set( tr, key, vold, vnew ): if tr[key] == vold: tr[key] = vnew but this is not the limit of what you can do.
    - polskibus 8y ago
      Thank you very much for your in-depth explanation, I believe the only thing left for me is to run FDB myself, sounds very promising :) FDB replacing zookeper + sth else would reduce the complexity of target distributed system, almost too good to be true.
- polskibus 8y ago
  as far as I know SSI as implemented in Postgresql, aborts the way you describe, as per https://drkp.net/papers/ssi-vldb12.pdf https://drkp.net/papers/ssi-vldb12.pdf
  - benmmurphy 8y ago
    postgresql is not strictly serializable/externally consistent for example this will commit under serializable: create table counters(counter int); insert into counters(counter) values(1); BEGIN TRANSACTION ISOLATION LEVEL serializable; select sum(counter) from counters; /* insert sum into counters. wait until committing next transaction before executing the insert */ insert into counters(counter) values(1); COMMIT; /* this transaction should commit before doing the insert in the above transaction and after the above transaction has calculated the sum */ BEGIN TRANSACTION ISOLATION LEVEL serializable; insert into counters(counter) values(10); COMMIT; both transactions commit and the final table looks like: 1, 10, 1 which is possible if the first transaction committed first, and then the second transaction committed. but it is possible for another client to see the table as: [1], [1, 10], [1, 1, 10] which is a sequence of states which should not be possible. if you see [1], [1, 10] then you should see [1, 10, 11] as the last state. hence it violates external consistency.
    - cakoose 8y ago
      Even without external consistency, a I'm having trouble coming up with an ordering of the transactions that yields [1], [1, 10], [1, 1, 10]. Is that because PostgreSQL's "SERIALIZABLE" doesn't follow the "some serial order" definition? Or maybe I'm missing something else?
      - anarazel 8y ago
        Well, benmmurphy isn't talking about serializability (some correct ordering exists), but strict serializabilty (roughly: at least one correct ordering corresponds to wall clock order). PG does have the former, but not the latter.