Batching before that will help if you already know that most of the transactions touching a particular key are going to the same server. So not a clean partition, but "most of the time". This is the idea behind, e.g., http://www.ssrg.ece.vt.edu/papers/peluso-M2PAXOS-TR.pdf. You try to make sure people usually contact the owner of a particular partition, and use a variety of techniques from the literature to make that well-optimized (ideally, clients actually know which partitions they "should" be accessing, too).
Another approach is to restrict your transactions to deterministic ones (with possible "scouting" transactions to do things like secondary index lookups where you can't statically analyze which partitions they will hit), in which case you can batch all transactions, send them to all participant nodes, and run them afterwards without two-phase commit. This is the approach taken by Calvin (which can exploit per-node parallelism during execution because it uses deterministic, deadlock-free locking). Additionally, read-only transactions scoped to a partition can execute locally without any distributed access, because thanks to determinism serializability is guaranteed. See http://cs-www.cs.yale.edu/homes/dna/papers/calvin-tods14.pdf (and yes, it really can do 500,000 distributed TPC-C transactions per second--by my estimation, more than three orders of magnitude higher than the average total traffic you get, as suggested by your "100x more read transactions than write" estimate. Though of course your current average is higher than your 8-year average, I doubt it is 1000x higher).
Yet another idea is to try to combine coordination required for replication with that required for the distributed transaction, as Tapir does: https://github.com/UWSysLab/tapir. It enjoys the highest linearizable read/write "general" (as in, doesn't have to be submitted in one batch or need static analysis) transaction throughput I've seen of any leaderless georeplicated system (aka it processes transactions "fairly").
Still another approach is to forego serializability for a very slightly weaker guarantee, extended update serializability, which eliminates nearly all interesting anomalies but can allow for dramatically better performance: http://www.ssrg.ece.vt.edu/papers/opodis14-alvin.pdf demonstrates that on read-mostly workloads you can do very well with that even in absurd deployments (e.g. the georeplicated 7 datacenter one in the paper). Elsewhere in the thread you were talking about how "observational" consistency is what's important, which would suggest you are probably already relying on the "strong session" assumption (in which case EUS is indistinguishable from serializability), so I encourage you to give that a look.
All four represent pretty interesting points on the design space. It's not clear to me whether RockSolid would be better than, say, SQLite over Calvin, for your use case (in particular, I suspect Expensify would not find Calvin's requirement that transactions be statically analyzable terribly onerous, especially since you already require all transactions to be executed as stored procedures).
I will say that I'm pleased that a site receiving a reasonable amount of traffic is using SQLite. People consistently underestimate its performance.
Incidentally, the latest plan is to use http://sqlite.org/sessionintro.html to do the following:
1) Spin up multiple write threads
2) Every write thread opens its own database handle
3) Every write thread creates a new "session" object before each write command, and then creates a "changeset" afterwards
4) The first write thread to process a write command calls sqlite3changebatch_new() to create a new batch (initially empty)
5) It then calls sqlite3changebatch_add() to add the changeset to that batch, which returns SQLITE_OK to indicate that it does not conflict with anything in the (currently empty) batch
6) The next write thread calls sqlite3changebatch_add() on the existing batch, providing the write command's changeset
7) If sqlite3changebatch_add() returns SQLITE_OK then it creates a patchset from the changeset, and sends it to the slave.
8) Slaves apply and commit patchsets within the same batch in any order
9) On the other hand, if sqlite3changebatch_add() returns SQLITE_CONSTRAINT, then that means the new changeset conflicts with one or more existing changesets in the batch. In this scenario, it increments the batchID, calls sqlite3changebatch_zero() and then sqlite3changebatch_add() again (to initialize the new batch). It then creates and sends a patchset to the slave for committing in any order with changes in the new batch.
Re: SQLite's performance, I find the database is consistently underestimated in every regard -- performance, stability, functionality, etc. And the database isn't half as amazing as the team behind it. Those are some of the most solid engineers -- in a true sense of engineering (of which programming very rarely is) -- that I've met.
From a correctness perspective: SQLITE_CONSTRAINT will only detect write conflicts, not read conflicts, so you are losing serializability (instead you have snapshot isolation, which is what SQLite gives you by default with multiple writers). SI allows a variety of subtle anomalies that can screw you over; see https://wiki.postgresql.org/wiki/SSI and https://wiki.postgresql.org/wiki/Serializable. If you are currently using only a single-writer thread, you will never experience these issues, AFAIK, because you cannot form a "dangerous structure" (you can never have two R-W dependencies that conflict with each other because you can only have one R-W transaction at a time), but I could be wrong about that; however, if I'm not, this could lead to you dealing with some really bad bugs. Note that these kinds of anomalies have a tendency to pop up when you're using stored procedures to perform validation!
As for how much contention there will be, I'm not sure: that's one reason we haven't taken the plunge yet as we sorta want to determine this first. However, given that we have a huge number of users modifying unshared data (eg, our largest group still makes up a tiny fraction of the userbase), I suspect conflicts will be relatively few.
And to be clear: even a little write concurrency goes a long way. If we can even do two writes simultaneously, that doubles our write performance. But I personally suspect the average batch size of non-conflicting transactions will be in the dozens or even hundreds -- meaning I suspect we will achieve so much replication throughput that something else becomes the bottleneck before replication is saturated.
Only one way to find out however!
Still, with a total order, it's not that bad, because it's easy to identify gaps; with your algorithm, however, there's no total order between changesets within or across batches (at least, none that I can see in your algorithm), so you won't have any way of knowing whether there are gaps (at least, not without doing something silly like broadcasting every changeset)! Adding a total order seems like the easiest way to resolve that, but like I said even that case can be tricky. Also, your algorithm doesn't specify that replicas which receive changesets with batch ids with gaps in them wait to apply them until the gap is filled in (which means they have to know when the previous batch is done), or alternately that before a batch with a new id can be sent from the master all replicas must have synchronously applied all changes within the old batch. I think something like that is a requirement here in order for there not to be potential conflicts on your replicas during replication even if the master doesn't crash.
IMO, doing exactly your algorithm but delaying replication or transaction confirmation until a specified amount of time has passed (say 10 ms), then synchronously sending the entire changeset and incrementing the batch id (aka group commit) is a much better idea. You exchange marginally worse latency (and more bursty network usage) for a far less complex update scenario (yes, you're back to having a total ordering on writes at replicas you need to follow, but you can include multiple changesets in the batch). You can also have your master monitor number of writes and only turn on group commit if there's unusually high write volume.
(Also, belatedly reading one of your other comments more carefully, I'm fairly confident commitCount will also not work correctly if changesets can be applied out of order on different replicas, even if there was no data loss, since the same commitCount could include different sets of changesets at any one time).
Now I do agree that it's tricky to avoid "gaps" in the failure cases. However, every replica keeps a record of the past several million transactions (we aim for 3 days), and every transaction is assigned a unique ID. When a replica starts up, it "synchronizes" down every missing transaction it has, and at this point would "repair" any gaps it somehow obtained when it went down.
Admittedly, the exact details of that part are TBD, but it doesn't strike me as an unresolvable problem on the surface.
(1) In the event of a crash, how does it know which transactions it's missing without a total order on the write transactions?
(2) In the non-failure case, how do you know the transactions in one batch are ordered before the transactions in a subsequent batch (which requires the replica to identify any "gaps" within the previous batch so it can wait for them to come in before continuing on)?
I don't think any of this is unresolvable (just adding a total order would go a long way). I do think it's very tricky to get right, with lots of edge cases, and that if you can't efficiently identify missing transactions it potentially makes recovery unusably slow.
In any case, since I believe you are losing serializability with multiple writers, you should probably weigh that against any performance gains you get from multiple writers (I think even the group commit variant suffers from this problem).
This is difficult to reconcile with:
> - For the highest performance, you can designate a transaction as "asynchronous" and the master will commit immediately
because if the leader crashes, a replica becomes leader and starts accepting writes, then the old leader recovers as a replica, without something like an epoch number it won't be able to tell that it has commits that the current leader doesn't (using a unique incrementing transaction number based on just a counter at the leader won't work, because it won't necessarily be unique across leader elections thanks to the asynchronous commits).
Furthermore, every commit has a running SHA hash of all prior commits (and every node keeps a history of the last few million commits). This way any two nodes can compare their journals to make sure they agree -- and if there is any split, then the cluster kicks that node out.
Basically, there is no scenario in which a node that commits a different transaction (or a transaction in a different order) is allowed to remain in the cluster.
(I was one of the authors of SSI in Postgres)