6 ms·

Yes, we've made a lot of good progress on this front, though nothing ready to demo. Multi-threaded replication is really exciting stuff. As it stands, our "se

Yes, we've made a lot of good progress on this front, though nothing ready to demo. Multi-threaded replication is really exciting stuff. As it stands, our "selective sync" capability already gives a lot of headroom for write capacity, but multi-threaded replication will raise that ceiling even higher.

Jweb_Guru 10y ago
The fundamental issue you're going to run into is that unless you have "genuine partial replication" where only certain shards have a key, or restrict your queries to key/value ones where the key can be determined automatically and used to route to a per-shard master, you can't detect conflicts committed on different nodes without executing half a round trip, which is going to be bottlenecked by the slowest node in your "fast" quorum. That's why nobody uses Generalized Consensus in practice. 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 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 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 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 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.
- quinthar 10y ago
  Thanks for all these links, I have some reading to do! Also, to clarify one point, we're not doing multi-master writes/replication -- just multi-threaded writes/replication. Incidentally, the latest plan is to use http://sqlite.org/sessionintro.html 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.
  - Jweb_Guru 10y ago
    Oh okay. That sounds a lot like OCC in terms of the tradeoffs involved. If you're looking for implementation hints, you might want to check out Silo (http://db.csail.mit.edu/pubs/silo.pdf http://db.csail.mit.edu/pubs/silo.pdf). It's really hard to beat for transactions that are mostly nonconflicting (if transactions are mostly conflicting it is hard to exploit multiple writers unless you are very clever about how you go about it; I can dredge up a few links if you're interested). My overall understanding is that the usual rule is that unless you have highly partitionable workloads, single writer almost always wins, but I think your current strategy is also going to suffer from a lot of contention even in cases with no conflicts: the write batch is going to be constantly bouncing between cores and require lots of locking, which could easily substantially degrade performance over what it currently is (though obviously, benchmark :P). 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 https://wiki.postgresql.org/wiki/SSI and https://wiki.postgresql.org/wiki/Serializable 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!

Jweb_Guru 10y ago

The fundamental issue you're going to run into is that unless you have "genuine partial replication" where only certain shards have a key, or restrict your queries to key/value ones where the key can be determined automatically and used to route to a per-shard master, you can't detect conflicts committed on different nodes without executing half a round trip, which is going to be bottlenecked by the slowest node in your "fast" quorum. That's why nobody uses Generalized Consensus in practice. 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 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 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 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 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.

quinthar 10y ago
Thanks for all these links, I have some reading to do! Also, to clarify one point, we're not doing multi-master writes/replication -- just multi-threaded writes/replication. Incidentally, the latest plan is to use http://sqlite.org/sessionintro.html 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.
- Jweb_Guru 10y ago
  Oh okay. That sounds a lot like OCC in terms of the tradeoffs involved. If you're looking for implementation hints, you might want to check out Silo (http://db.csail.mit.edu/pubs/silo.pdf http://db.csail.mit.edu/pubs/silo.pdf). It's really hard to beat for transactions that are mostly nonconflicting (if transactions are mostly conflicting it is hard to exploit multiple writers unless you are very clever about how you go about it; I can dredge up a few links if you're interested). My overall understanding is that the usual rule is that unless you have highly partitionable workloads, single writer almost always wins, but I think your current strategy is also going to suffer from a lot of contention even in cases with no conflicts: the write batch is going to be constantly bouncing between cores and require lots of locking, which could easily substantially degrade performance over what it currently is (though obviously, benchmark :P). 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 https://wiki.postgresql.org/wiki/SSI and https://wiki.postgresql.org/wiki/Serializable 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!