4 ms·
Part of the problem here is the confusion in terms between the databases world and the distributed systems world. "Consistency" has very different meanings in e
by mjb 7y ago
Part of the problem here is the confusion in terms between the databases world and the distributed systems world. "Consistency" has very different meanings in each, and "atomic" frequently has different practical meanings, for example. These terms even differ in local systems: look at what the LLVM docs and C++ spec imply about "atomic" (they use it to mean something close to 'linearizable'), while the database folks use a very different definition. Words are hard.
I think a lot of people coming from the distributed world assume that Serializable implies Strict Serializable, and don't think about the re-orderings that databases are allowed to do that break linearizability. That causes a lot of confusion, and even more confusion when databases become distributed.
- mehrdadn 7y agoCould you point to which part of the LLVM docs use "atomic" to mean "linearizable"? (I'm not even sure what you mean by that, but if you mean "sequentially consistent", that's explicitly its own subcategory under atomicity in the docs... it's definitely not what they mean by atomicity in general. [1]) [1] https://llvm.org/docs/Atomics.html#optimization-outside-atomic https://llvm.org/docs/Atomics.html#optimization-outside-atom...
- mjb 7y agoSorry, I think I was confusing LLVM's 'monotonic' with 'atomic'. The docs (https://llvm.org/docs/LangRef.html#ordering https://llvm.org/docs/LangRef.html#ordering) say: > In addition to the guarantees of unordered, there is a single total order for modifications by monotonic operations on each address. All modification orders must be compatible with the happens-before order. There is no guarantee that the modification orders can be combined to a global total order for the whole program (and this often will not be possible). The read in an atomic read-modify-write operation (cmpxchg and atomicrmw) reads the value in the modification order immediately before the value it writes. Am I wrong to read that as being equivalent to linearizability, in the case of atomic operations with monotonic ordering? I'm not an expert on compiler internals, so it could be that I'm reading the docs wrong. If there's a better reference, I'd love to see it.
- mehrdadn 7y agoCould you define explicitly what you mean by linearizability?
- mjb 7y agoThe defininition from Herlihy and Wing (https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf), page 471. More informally, aphyr's definition from https://aphyr.com/posts/313-strong-consistency-models https://aphyr.com/posts/313-strong-consistency-models works well: > each operation appears to take effect atomically at some point between its invocation and completion. Here, operations are on single values (the paper calls them objects). So they are things like "add 1 to x" and not things like "read y and add its value to x".
- mehrdadn 7y agoIf that's what you mean then linearizable can't be the same as monotonic since monotonicity is weaker than sequential consistency, not stronger. If I understand LLVM's docs correctly, the difference between monotonicity and sequential consistency is that the former is for a single address whereas the latter is for all addresses. They would've been more clear on this if they had said "that the modification orders for different addresses can be combined to a global total order for the whole program".