Hi Paul, I think even the slave restart idea has problems, because on restart you can violate serialization requirements on the start transaction.
T0 T1 (Start TXID: T0) T2 (Start TXID: T0) Now suppose T1 and T2 deadlock. T2 is chosen as the deadlock victim. T1 commits and T2 restarts. However, if you do this you have just transformed the dependency graph as follows: T0 T1 (Start TXID: T0) T2 (Start TXID: T1) In this case it appears you need to roll back not one but both to avoid this transformation. As you add more threads to the mix the cases seem to get weirder--it appears there are instances where you would have to roll back committed transactions as well. This can also happen if you have a slave failure, BTW, not just a deadlock. It just keeps getting uglier. :( So far in this thread nobody has brought up the issue of shared locks, intent locks, and lock promotion. These are three further bits of nastiness that make deadlocks both more likely on the slave and also almost impossible to reason about in advance. IMHO any attempt to achieve parallelization in the general case is therefore doomed to failure. Meanwhile, everyone on this thread agrees that parallel replication would make the world a better place. It seems as if we need to proceed by asking two questions: 1.) In which cases does parallelization work reliably? For example: - Shards. - Groups of tables that belong to different application components. - Within particular tables whose updates are known to be independent and insensitive to ordering. INSERT-only tables are a simple but important example. - In cases where you have analyzed all tables/keys in the transaction *and* the user does not care about view consistency for SELECTs on the slave. This amounts to dynamic partitioning. 2.) What features could Drizzle supply that would make it easier to implement parallelization in these cases? - Ensure table names, keys, and values are easily visible in row updates (they have to be anyway...). - Make it easy to track schema changes in the log so you can do dynamic partition analysis quickly and accurately. - How about logging table partition names? If you partition for performance across spindles, it stands to reason you might be able to use this to guide replication as well. - How about making it easier to do file-system level backup/restore of shards? That makes provisioning and error recovery easier. - How in general can Drizzle make it easier to identify data partitions both automatically as well as with help from users? Just my $0.02. Cheers, Robert On 5/8/09 3:05 AM PDT, "Paul McCullagh" <[email protected]> wrote: > > > On May 8, 2009, at 10:52 AM, Clint Byrum wrote: > >> (T0) commit >> (T2) update foo set value='b' where key=1 >> (T1) update foo set value='a' where key=1 (blocks on lock) >> (T2) *must* wait on T1 for commit order >> >> I agree that you're in a world of hurt here. As you said, this is a >> broken serialization.. one that can only be solved by either >> timeout, as you suggest, > > A timeout is not required because all of these deadlocks can be > detected, using a "wait-for" graph (although there is no instance that > detects deadlocks across engines). > > Transaction that need to be restarted do not have to wait. This can be > done immediately, because the other transaction(s) will probably > complete before the restarted transaction get that far again. > >> or full table serialization. > > This is not a good solution because in a high concurrency environment > you will have a set of tables that are accessed by most transactions. > The result will probably not be much better than single threaded > execution on the slave. > >> *so*, what if we *do* add the table info as before, but *don't* >> serialize on it all the time? when we finish a transaction early, we >> check to see if there are unfinished transactions w/ any of the >> tables we modified, and restart ours. >> >> This would thrash horribly where people are incrementing a single >> counter with lots of concurrent threads. > > Thrashing is a problem with the "restart deadlocked transactions" > solution. > > Mostly because transactions that wish to commit "too soon" must be > killed. > > This problem could maybe be eased by starting transactions in the > commit order. So they run in parallel, but transactions that must > commit first are slightly ahead. > > Note that transactions that don't have (row-level) update conflicts > will run through without a problem. > > This is something that is would be extremely difficult to predict > beforehand. So the only answer is to go for it, and handle problems > later (by restarting transactions that try to violate the rules). > > > -- > Paul McCullagh > PrimeBase Technologies > www.primebase.org > www.blobstreaming.org > pbxt.blogspot.com > > > > -- Robert Hodges, CTO, Continuent, Inc. Email: [email protected] Mobile: +1-510-501-3728 Skype: hodgesrm _______________________________________________ Mailing list: https://launchpad.net/~drizzle-discuss Post to : [email protected] Unsubscribe : https://launchpad.net/~drizzle-discuss More help : https://help.launchpad.net/ListHelp
