Strict-serializability, but at what cost, for what purpose?
muratbuffalo.blogspot.com
muratbuffalo.blogspot.com
It’s already hard enough to write correct software, we should be pushing hard problems like transaction isolation deep into the database so they can be solved correctly once, instead of 1000s of times incorrectly.
Most applications that depend on strong consistency in their database could be rewritten to require less strict guarantees, but why?
Strict serializability should be the default. Engineers working in performance sensitive settings and who really know what they’re doing can always loosen this constraint in the narrow part of the application where it matters.
It’s crazy to me that anyone would ask a developer to justify why they need strict serializability. It should be the opposite, you should be forced to justify why you’re using a looser isolation level for performance reasons just like we force developers to justify why they’re introducing more performant, but less readable code!
If this was some theoretical question that we hadn’t figured out if it was practical or possible yet, I would have more sympathy for this line of thinking, but it’s not anymore.
Spanner, CockroachDB, and FoundationDB have all proven that these systems can be scaled, and economically so.
FoundationDB scales incredibly well with great performance characteristics. That’s evidence enough to me that the cost of strict serializability is worth it for 99% of applications.
Only Spanner currently offers properly scalable strict serializability, as FoundationDB clusters have a size limit (that is very forgiving, and enough for most use cases).
Apache Cassandra is working on providing scalable (without restriction) strict serializable transactions[1], and they should arrive fairly soon. So far as I am aware, at this time it will be the only distributed database besides Spanner offering fully scalable and fast global transactions with this level of isolation.
[1] https://cwiki.apache.org/confluence/display/CASSANDRA/CEP-15... (Disclaimer) I'm one of the authors
I think your characterization of Cassandra as “fully scalable” in a way that other systems are not is misleading, but I won’t argue it with you :p
The cluster size limitations are also greatly overstated and mostly a hold over from stale documentation from 2013. You can (and companies do) run FDB clusters with 100s or 1000s of nodes without issue.
Cassandra supports this too but in my experience it gets quite difficult to operate at that point, although I’m sure recent versions have gotten much better about this.
If you only care about raw write throughout I think your statement is mostly accurate, but for general purpose workloads I would argue that FDB is a system “as scalable as Cassandra” that also offers strictly serializable (and interactive!) transactions which makes it much more broadly applicable to a wide variety of use cases.
Disclosure: I work on FaunaDB.
It may not happen in practice today, but as your clusters grow your exposure to such a failure is increased, and the NxN communication overhead grows does it not?
It's certainly more scalable than other systems offering this isolation today (besides Spanner), but algorithmically at least I believe the proposal we are developing for Cassandra is strictly more scalable, as the cost and failure exposure grow only with the transaction scope, not the cluster.
Not to ding FaunaDB, though. It probably is the most scalable database offering this level of isolation that is deployable on your own hardware - assuming it is? I know it is primarily a managed service, like Spanner.
I'm also not aware how large any real world clusters have gotten with FaunaDB in practice as yet. Do you have any data on that?
No, that's not correct. FaunaDB is inspired by Calvin, but is not a direct implementation of Calvin. Transactions are applied independently on each storage host, though checking OCC locks may involve peers within a single replica.
> assuming it is
We used to offer on-premises delivery, but we are strictly a managed service now.
> I'm also not aware how large any real world clusters have gotten with FaunaDB in practice as yet. Do you have any data on that?
I'm not at liberty to say.
I’m not talking about transaction application, but obtaining your slot in the global transaction log. How does a replica know it isn’t missing a transaction from some other shard if that shard is offline come its turn to declare transactions in the log? It must at least receive a message saying no transactions involving it were declared by that shard, no?
This is pretty core to the Calvin approach, unless I misunderstand it.
> I'm not at liberty to say.
I think scalability is something that is a function of both theoretical expectations and practical demonstration.
A transaction is committed to the log with sufficient information necessary for the log (and each storage host) to know whether any particular host is involved in that transaction. There's no need for a message to prove a host's absence from that transaction - it has all it needs in the log to determine that it isn't involved. There is some complexity around how that information maps to the cluster's physical topology, but hosts which aren't involved in a transaction don't process that transaction and need not check with any other host to know that fact.
[ETA] That information is derived from the read set when constructing the transaction to propose to the log. Logical partitions that weren't a part of that read set don't need to know that they weren't involved - that fact is obvious from their absence.
> I think scalability is something that is a function of both theoretical expectations and practical demonstration.
I agree with you, though as a commercial product operated as a service, that practical demonstration is naturally limited in this forum.
> that fact is obvious from their absence.
Yes, but absence from what? There must be some message that contains the relevant portion of the log declared by each other shard. If that shard is offline, so it cannot declare its transactions at all, how does the system continue? This absence is one step back from the one you are discussing.
If a shard’s leader is offline, a new leader must be elected before its slot comes around for processing - and until this happens all transactions in later slots must wait, as it might have declared a transaction that interferes with those a later slot would declare.
If no leader can be elected (because a majority of replicas are offline) then the entire log stops, no?
You're under the mistaken impression that we have the same data/log architecture as described in the Calvin paper, which requires that every host talk with every other host. That is not true of FaunaDB.
If not, we’re now in an unfortunate situation where neither your practical nor theoretical capabilities are public knowledge.
> every host talk with every other host
Only every shard
> you seem to think you know more about FaunaDB's architecture than you do
You are perhaps being uncharitable. The only public statements I am aware of about Fauna's capabilities relate to its Calvin heritage. I have only been asking if my understanding is correct regarding both Calvin and its application to Fauna. However, none of the prior issues you responded to were problems with the original Calvin paper either, at least by my reading.
> for scalability, this insertion process happens in batches, and the log itself is replicated and partitioned
This is the link's total exposition on this topic, but it is consistent with my reading of the Calvin paper.
If any log partition becomes unavailable, the log in its entirety becomes unavailable until that partition recovers[1].
Anyway, it feels like we’ve wasted enough of each others’ time without making much progress. Might as well leave it there.
[1] ... and every log partition must communicate with every replica, hence NxN (or MxN)
The salient aspect of the paper is how it derives the log logically, not how that is mechanically implemented in a real system outside of academia.
> However, none of the prior issues you responded to were problems with the original Calvin paper either, at least by my reading.
I wasn't clear what exactly you do (or don't) know of the architecture which would lead you to believe this NxN messaging story, as that relates directly to your contention regarding the scalability (or not) of the architecture. That much is clear to me now.
I understand scalability by being able to handle more traffic through adding more nodes to your cluster. But if you want to handle more traffic, adding more replicas to a single Accord replica set won't help. Any two (fast path) quorums must intersect. And that intersection point for two queries is where you need to spend resources to handle both queries.
So - unless I'm missing something here - in order to scale out to be able to handle more traffic, you must shard the data, there's no way around it. Even assuming 0 failures won't help.
And once you shard your data and use multiple Paxos/Raft/EPaxos/Accord/whatever groups, you lose strict serializability across the shards.
Nope. That's precisely what Accord manages to maintain. It is not the first such protocol to do so, but so far none of the others have left the lab.
1) That the result of an operation is reflected in the database before a response is given to the client
2) That every operation that starts after another operation's response was given to a client has the effect of being executed after.
Accord enforces both of these properties. Accord only avoids enforcing an ordering (2) on transactions that are commutative, i.e. where it is impossible to distinguish one order of execution from another. This requires analysis of a transaction and its entire graph of dependencies, i.e. its conflicts, their conflicts, etc. So, if your most recent transaction operates over the entire database, it is ordered with every transaction that has ever gone before.
Cockroach does not do this. If it did, it would be globally strict serializable.
If you read their Jepsen report and blog posts carefully, the anomaly they suffer from is not caused by a read transaction that started after previous write transactions had completed, but by a read transaction running concurrently with two other write transactions which both commit while the read is still running, and the read sees the writes in the wrong order. The definition you’ve provided above does not cover this case (I think) but its still a violation of strict serializability which makes me think your definition is too loose.
Correct me if I’m wrong though, at this level things get quite confusing.
If w1 and w2 overlap their execution then any serializable execution is strict serializable, so w1 must have finished before w2 began. In this case (2) applies and w1 must have the effect of executing before w2, to all observers, including r.
If w1 and w2 are commutative then it doesn’t matter in what order they execute as they’re equivalent. If not, then at some point their dependency graphs intersect and will be/have been ordered wrt each other by the same restrictions.
edit: in the example given in the Jepsen report, with Accord r would have to execute either before w1; after w1 and before w2; or after them both. This is because one of the following must occur:
1) r takes a dependency on both w1 and w2 and executes after them both;
2) r takes a dependency on only w1; w2 takes a dependency on r, so w2 executes after r, and r executes after w1
3) w1 and w2 both take a dependency on r, so that r executes before either
Edit: Ah ok I see you edited it. Ok that makes sense if it works.
w2 may hit different nodes than w1 in a sharded database?
Or is the leader-Paxos approach in Accord operate over all nodes in the database regardless of the shards the keys fall into? (I guess that is the only explanation.) But then scalability of these global transactions would be limited, no?
Thank you for your detailed explanations.
If r arrives at C1 before w1, w1 must witness it and take a dependency on its execution. If it arrives at C2 after w2, then r takes a dependency on w2’s execution. In this case, w1 will not execute until r does, and r will not execute until w2 does, and so it is simply not the case that w1 happened first - w1’s commit will not have been acknowledged to the client yet, and the actual order of execution will end up w2,r,w1, which is entirely correct to all observers since w1 and w2 will now overlap their execution.
> operate over all nodes in the database regardless of the shards the keys fall into
Nope, it’s all entirely independent for each shard. The (implied) dependency graph is what ties shards together, so only when they interact.
I get it now. It is all thanks to separating the operation as 1. agreeing on WAL, 2. executing after waiting all WAL agreements stabilizing.
There is a separation between the two. This can introduce waits (which could be theoretically unbounded for EPaxos but Tempo and Accord bounds this).
Maybe in some sense this is in the same spirit of Calvin's serializing WAL first and executing it later. But Accord avoids a single entity doing the serialization and achieves it via a leaderless Paxos approach which uses dependency graphs for WAL serialization, and later using another protocol for WAL execution after settlement.
Yes, it is very similar in effect, with the absence of a global log conferring some important differences with pluses and minuses. I expect to offer interactive transactions eventually, for instance, which may or may not be difficult for Calvin, and faults on a “log shard” are isolated with Accord, but have global impact with Calvin. But snapshot queries are much easier with Calvin.
Once we offer interactive transactions we’ll have to detect cycles, but that should be relatively straightforward since execution dependencies are managed explicitly.
> Accord only avoids enforcing an ordering (2) on transactions that are commutative
If the committed state in the database records the transactions in a different order than an external observer could have observed them being accepted by the database, then you don't have what Spanner calls "external consistency" - I thought this is what you mean when you say "global strict serializability", but now I'm not so sure.
Cockroach does enforce this property, but only for transactions that touch the same (key-value layer) keys. They talk about this a bit in their article on "life without atomic clocks"[0].
In SpiceDB[1], we take advantage of this property (when Cockroach is selected as the backing datastore) to give us external consistency by forcing all transactions to overlap. This prevents the New Enemy Problem[2], which is what Google calls the problem of transaction ordering when seen from an authorization perspective.
Your description of Accord sounded very similar to how Cockroach works from this perspective, but there may be some subtlety that I am missing. Cockroach exposes snapshots via "as of system time" queries, which can expose "bad" ordering back to the client in future queries - if Accord doesn't allow snapshot queries then I suppose it wouldn't be an issue.
[0]: https://cockroachlabs.com/blog/living-without-atomic-clocks/...
So, property (1) provides this for non-overlapping commutative transactions. If w1 writes c1, then finishes; w2 writes c2 then finishes; then if r1,r2,r3, etc don't overlap either w1 or w2 either, then they must correctly witness their execution order and be "externally consistent".
If transaction executions overlap, we must work harder to ensure we see each others' strict serializable order, and so we simply avoid ordering ourselves with transactions that cannot affect our outcome. If these other transactions cannot affect our outcome, then we can't witness anything externally about them, by definition.
Are there any plans for accord to permit snapshot queries?
The system maintains a logical clock, and the logical clock enforces the strict serializability condition globally. The logical clock is just cheaper to maintain if the coordinator proposes a value that is already correctly ordered by the loosely synchronized clocks.
edit: sorry, I misread your post as interpreting the loosely synchronized clocks as being necessary for correctness. I answer (very loosely) how strict serializability is maintained in a sibling comment, but in brief a dependency set of all conflicting transactions that might potentially execute earlier is maintained, and a transaction executes in logical timestamp order wrt these dependencies (and, hence, also their dependencies). If a transaction and its dependencies never interacts with another transaction or its dependencies, then their execution order is commutative, i.e. any ordering is indistinguishable from any other.
A lot of Ink is wrongly interpreted because people not think about the SIZE of the (data/problem).
MOST, if not ALL(99%) of the thinking about this stuff is for the very end of the scale: Terabytes, dozen/thousand of machines, insane latency, etc.
MOST, if not ALL(99%) of the ACTUAL data people deal with, the one that matters, is in the low of gigabytes, at best. One, maybe 2 servers, answer in a second(is) is more than ok.
You can fit most databases in an iPhone with spare to work.
Instead, the real trouble that people face is wrong schema/query designs, and introducing bugs and other stuff that the RDBMs thankfully correct/protect against.
Making the primary store MORE strict is a big win to alleviate the real issues.
I think the article is talking about distributed systems where it's costly to guarantee ordering among multiple entity groups (shards for example), and there are "never" transactions across those entity groups. For example, the database hosting your website and the database backing my website can't talk to each other, so it doesn't really matter that transactions that we execute against our database don't appear in a defined order; we don't even know that the other exists.
I do agree with the sentiment that if those two databases are at the same company, eventually you'll be burned by not being able to do transactions across them. Ever try to make an atomic change to two git repositories? Not possible, but often quite annoying. This is doubly annoying when you start having internal sync processes because two teams used two different database to ultimately build, what looks like to the user, one app.
My philosophy is that if strict serializability ever makes it impossible to run my service, I'm already so rich that I can just sell the service and let someone else deal with the problem. So far, no dice on that.
I know your intent wasn't to discuss this. But you could
1) combine them
2) use tags or git hashes as your URI
3) create a third repo that uses git submodules to combine them by said git hash
Trying to maintain global state by having both gitrepos be compatible at the same wall time isn't as important as it seems. There are lots of ways to meaningfully deal with this.
The lower your scale, the more you can get away with using a "high scalability" database. Who cares how concurrent transactions are reconciled when you've never seen one? I would wager that most users aren't actually handling the caveats at application layer. They're just not hitting the weird stuff often enough to ever really consider it.
In my opinion the trick to implementing this without too many performance issues is to add the HTTP cookies feature to database engine protocols.
Every transaction with the DB engine should require a client "transaction sequence logical clock" cookie. The returned result set should return the updated cookie, which should then be "threaded" through all the way to a web browser cookie or GUI client local store.
That way, individual users will always be telling the database engine (or cluster!) that they need to see their previous transactions in a linear order, but concurrent users could potentially have a slightly difference perspective on things. Cache entries could also be tagged with the clock cookies and then used to verify if they're still valid or need to be refreshed.
An important feature would be to have a union operator on the clock cookies that provides a new cookie that is "in the future" of all provided clock cookies. This would allow cross-user queries to correctly reflect the required input transactions.
Similarly, it should be possible to use a special "now" cookie, which is identical to typical single-server DB behaviour with serializable transactions.
Last but not least, "now minus t seconds" would produce the equivalent to what you get if you do read-only queries against an asynchronous replica.
This would allow combinations not possible with a naive DB engine that always enforces a single serialized transaction sequence, but the default behaviour would be very safe and consistent.
The computer science for this exists. There are lamport timestamp implementations using compressed tree representations, for example. The timestamps could be tracked per table, which would allow transactions across unrelated tables to be independently serialized.
Essentially, transactions should form a directed acyclic graph much like Git commits instead of a strictly linear linked list. There are many analogies: Git commit hashes are a type of cookie that can be passed around and used for various things, you need to provide a predecessor commit hash for new commits, and the hashes are used to keep caches (local repos) 100% consistent with the central transaction history, etc...
https://www.microsoft.com/en-us/research/project/concurrent-...
I implemented multiversion concurrency control in Java (https://github.com/samsquire/multiversion-concurrency-contro...) and I am yet to get to the point where I'm distributing it between machines for multimachine transactions.
I have a simple read timestamp that is monotonically increasing. If I knew the read timestamps of other shards, distributed by raft log I could implement transactions across shards.
When we started to build the distributed database TiDB, we had the similar discussion - whether we need to provide a so strong consistence for the customers? Inspired by Google Spanner, we also wanted to let the application programmers to take easy and not struggle with the consistent problems in applications layer by themselves.
So we decided to provide the strong consistency. But unlike Google Spanner, we couldn’t use TureTime API, so we introduced a standalone timestamp service named TSO to allocate timestamp. Using TSO is simple to guarantee all transactions’ order, but this introduces another problem - if the TiDB is deployed crossing different regions, the transaction latency is high.
Another example for consistency is from our realtime analytical processing design. TiDB is a HTAP(hybrid transaction/analytical processing) database. It is normal to keep consistency in the TP part, but for the AP part, is it necessary to keep consistency? If there is an update in the table, does the customer really need to get the latest data from the AP part? Here we still choose “YES”, we want our customers to focus on their business and not worry whether the query data result is consistent of not.
Of course, keeping consistency in the database comes at a cost. Now we have been trying our best to optimize the latency and performance problems :sob:
IMO, we choose a right way. We now have supported strong consistency at first, and then we can provide a loose consistency for performance too, but on the other hand, if we only build a loose consistent database at first, it is hard to provide a strong consistency for the customers.
The Postgres default of "Read committed" gives me shivers on the other hand...
> If I were to make a concurrent map data structure whose operations are not linearizable and then put it on a library and give it to my users, any user of that library would come back to me and say that my library has a bug. They may not be able to tell me exactly what it is, but they'll understand that there is a bug in it.
> However, if I take the same concurrent map data structure, and put in an application and call that application a "Key-Value store" or a "Database" (DBMS) and give it to the typical database users, it seems they may certainly use it for a several decades without ever complaining that this "Database" is not linearizable (or serializable as the DB folks call it).
https://concurrencyfreaks.blogspot.com/2020/06/you-say-read-...
(On a slightly meta level, you can see this happening for a great many issues in programming. Memory safety is undeniably nice, but approximately none of the worlds databases or kernels are written in memory safe languages. Type safety is nice but a huge majority of frontend code is untyped. Don't even get me started on the value of unit testing vs its absence in academic code)
That's my entire point. Start with strong models and weaken when you decide you need it. Thus rule out entire classes of bugs for 99% of your code and closely scrutinize the 1% with weakened guarantees to know that it works. That is kind of the entire premise behind Rust. Make it extremely visible where the dragons may exist, because you have the key to unlock that door.
Regarding memory safety, 70% of CVEs at Microsoft and in Chrome are memory safety bugs. I would say the choice of languages without memory safety is more based on legacy than some kind of insightful choice.
https://msrc-blog.microsoft.com/2019/07/16/a-proactive-appro...
https://security.googleblog.com/2022/03/whats-up-with-in-wil...
You say this as if legacy choices are not some of the most persistent choices that exist in technology. I don't disagree that 70% of CVEs is memory safety related, but still my previous point stands that none of the popular kernels or databases are written in Rust.
A new database developer with a bright idea is basically confronted with the choice to either:
1. Write it in C and get it merged into Postgres relatively quickly. (Within the year or so)
2. Write it in Rust and also have to implement the rest of a RDBMS, then have to find a user base.
When confronted with that kind of choice, most devs would choose option 1 every time and I can't blame them for that even though I love memory safety.
Strict-serializability pretty much guarantees that you don't need any extra business logic to resolve logical states you know you won't, but turns out end up with. If your changes go out in-order over the wire, you know it will be go in with that order on the other end, either that end is temporal or spatial away.
However, strict-serializability doesn't solve either business logic errors or collaboration issues. If you have wrong transaction wrapping (things should happen in one transaction got split), or you have race condition locally, SS doesn't help on that. SS doesn't solve collaboration issues because the real-time ordering means both of you will end up in the same state, but if naively implemented, that same state may not be what you would expect (you still need to solve conflicts, and how you solve the conflict has to match the user expectation).
Then it goes back to what I originally said, for client-side devs, what they are looking for is to not write any extra business logic to handle states they know they won't end up with when their requests to the server went out in order. For many of these business logics, SS is too strong. A combination of serializability and linearizabily, as the author suggested, could be sufficient. It is just hard to articulate what combination that will be for broad spectrum of business applications.
I have been collecting some links on this topic
So that is the purpose. If you solve this at the database layer you relieve your developers of this burden and reduce bugs. You can argue that the cost is too high (it may be) but there is clearly a benefit to balance it out. Especially if the cost keeps dropping (as it seems to be doing) the balance tips every in favour of stricter consistency models.
“Technically speaking, every read-only transaction could return the empty-set (which was the initial state of the database) and not be in violation of the serializability guarantee --- this is legal since the system can bring read-only transactions “back in time” and get a slot in the serial order before any transactions that write to the database.”
https://fauna.com/blog/serializability-vs-strict-serializabi...