Hi David, I'm not a DB expert by any means, but I've been doing some work on transaction isolation recently and your description reminded me of one of the problems I encountered. I was using row-level locks, but the same principle applies to page-level locks.
Consider two transactions, each of which reads, increments and writes the same value. If you use shared locks for reading and exclusive locks for writing, as you described, then both transactions can read the value without conflict, and one of them can write it. When the second transaction wants to write the value, you have to decide what kind of isolation semantics you want. If you choose read-committed semantics, the second transaction is allowed to write the value, overwriting the first transaction's write - that's called a lost update. If you choose linearisable semantics, the second transaction has to be rolled back and retried so that its read occurs after the first transaction's write. Whichever semantics you choose, all replicas replaying the master's transactions must make the same choice about which of the two writes occurs first. As far as I can tell, that means replicas can't parallelise transactions that perform writes. (You could have a deterministic rule for deciding which transaction gets rolled back when there's a conflict, but if you run the transactions in parallel there's no guarantee that the same conflicts will occur on all replicas.) So if you want the replicas to remain consistent, I think the best you can do in terms of parallelism is to parallelise transactions that only perform reads. Which, for replicas, are probably irrelevant. Hopefully I've overlooked a better solution, in which case I'd love to hear about it. Cheers, Michael On 19/04/16 08:30, David Barrett wrote: > Thank you so much for the detailed response! I'm really surprised that > MySQL and Oracle are so... basic for replication. Here this whole time > I've assumed they had some magic capability, huh. Anyway, regarding this: > > On Mon, Apr 18, 2016 at 10:04 PM, Adam Midvidy <[email protected] > <mailto:[email protected]>> wrote: > > I can't think of any CP systems used in industry that use your idea > of batching non-conflicting replication updates and allowing > replicas to apply them in parallel. ... The reason why this approach > isn't popular is that efficiently detecting non-conflicting > transactions is actually not a trivial task by any means > > > Maybe I'm just naive, but it seems straightforward to detect conflicting > transactions. Basically: > > 1. Start out with: > - nonConflictingBatchID = 0 > > 2. Set a callback that is called every time a query touches a page. In > this callback, maintain a series of sets: > - pagesReadByThisTransaction > - pagesWrittenByThisTransaction > > 3. Before you commit, compare those pages to: > - pagesReadByCommittedTransactions > - pagesWrittenByCommittedTransactions > > 3. It's totally fine for the new transaction to read from a page read by > other transactions already committed. But if you read from a page > written by another transaction, or write to a page read by another > transaction, then you know that the new transaction conflicts with one > or more of the previous, already committed transactions. > > 4. If there are no conflicts, then commit this new transaction with > confidence that it didn't conflict with any of the other transactions in > this batch. Send out this transaction to slaves with the current > "nonConflictingBatchID", signaling to slaves that they are free to > commit this transaction simultaneous to other transactions in the same > batch. Also: > - pagesReadByCommittedTransactions += pagesReadByThisTransaction + > pagesWrittenByThisTransaction; // A write is also a read > - pagesWrittenByCommittedTransactions += pagesWrittenByThisTransaction; > > 5. If there is a conflict, however, then you can still go ahead and > commit this transaction on the master. However, increment the > "nonConflictingBatchID" before replicating out the transaction, to > signal "wait for all previous batches to finish being committed before > committing", and then set: > - pagesReadByCommittedTransactions = pagesReadByThisTransaction; > - pagesWrittenByCommittedTransactions = pagesWrittenByThisTransaction; > > This doesn't actually seem that hard, and maintaining a series of > unordered sets of page numbers seems like it'll be pretty fast -- much > faster than the queries themselves, at least. > > As for: > > and that when the workload is composed of non-conflicting > transactions, partitioning (sharding) provides the same performance > benefits with less complexity. > > > True sharding isn't an option as mentioned before. But this effectively > creates "ephemeral shards" by detecting non-conflicting queries in > realtime. In practice I don't actually think it'll take much to get > pretty massive improvements: if I can get even *two* non-conflicting > commits on average, that's the same performance advantage of having 2 > perfectly disjoint shards. But in practice, I expect we'll get vastly > more concurrency than that, as we have millions of users across a large > database -- the odds that two transactions back to back are even for the > same company (not to mention, linked in such a way as to conflict) seems > really rare. > > Anyway, that's my plan above. I'd be curious for your thoughts if you > think it'll work, or if I'm missing something obvious. Thanks! > > -david > > > > > > _______________________________________________ > p2p-hackers mailing list > [email protected] > http://lists.zooko.com/mailman/listinfo/p2p-hackers >
0x9FC527CC.asc
Description: application/pgp-keys
signature.asc
Description: OpenPGP digital signature
_______________________________________________ p2p-hackers mailing list [email protected] http://lists.zooko.com/mailman/listinfo/p2p-hackers
