On May 7, 2009, at 6:39 PM, Robert Hodges wrote:
Hi Clint,
This is an interesting idea and one that we noodled about for quite
some
time while working on Sequoia and other clustering software.
However, I
think it will not be so easy to implement. The problem is that while
recording the "beginning" commit number can help you sort out views
of the
data, it does not help with ordering locks and will lead to
deadlocks on the
slave. The problem becomes apparent when you allow multi-statement
transaction.
Well I'm glad some smart people have already taken a look at this
before I got too far. ;)
Consider the following situation on the master after some
transaction T0
commits:
(T0) commit
(T1) begin
(T2) begin
(T1) update foo set value='a' where key=1
(T1) update bar set value='a' where key=1
(T2) update bar set value='b' where key=1 (T2 BLOCKS)
(T1) commit (T2 UNBLOCKS)
(T2) update foo set value='b' where key=1
(T2) commit
These will go into the binlog as follows:
(T0)
(T1: Start TXID=T0)
(T2: Start TXID=T0)
If you now parallelize on the slave using the start TXID, T1 and T2
execute
together. You can now easily get the following order of execution:
(T1) begin
(T2) begin
(T1) update foo set value='a' where key=1
(T2) update bar set value='b' where key=1
(T1) update bar set value='a' where key=1 (T1 BLOCKS)
(T2) update foo set value='b' where key=1 (DEADLOCK)
So really what has been presented are two ways around the locking issue.
* Record tables that were locked while running, and use this in
addition to the "start TXID" to avoid starting two queries that lock
the same table at the same time.
* Use a very low/non-existant lock wait timeout, when a lock is timed
out, rollback the txn and wait for any on the same concurrency level
to complete.
The former would limit parallelization of a single table set to a
single thread. I know in my experience, most apps have 2 or 3 tables
that get most of the pain. This one's implementation is pretty easy.
We need to record the tables that were locked while it was running (I
don't know this part of mysql/Drizzle very well, so I don't know if
this part is simple), and on the slave we just add a LOCK TABLES
x,y,z to the beginning of every transaction. Ultimately this is still
very valuable and pretty easy to work around from an application
standpoint, but lets dive more into what you were talking about with
deadlocks..
The rollback solution would work most of the time but be really hard
to predict. Still, the reason the example deadlocks is that the
original transactions did not follow the deadlock avoidance principle
of ordering updates to tables predictably (I always read that one was
supposed to update tables in alphabetical order). If those
transactions were always updating bar first, then foo, the window for
deadlocks would be much, much smaller (MySQL's manual actually says
"Access your tables and rows in a fixed order. Then transactions form
well-defined queues and do not deadlock.", but I don't know if thats
true. ;). Anyway, observe:
(T0) commit
(T1) begin
(T2) begin
(T1) update foo set value='a' where key=1
(T2) update bar set value='b' where key=1
-- So now, either transaction is vulnerable to the other locking its
desired rows..
(T1) update bar set value='a' where key=1 (T1 Blocks)
(T2) update foo set value='b' where key=1 (DEADLOCK)
Whereas if they were ordered in the recommended way:
(T0) commit
(T1) begin
(T2) begin
(T1) update foo set value='a' where key=1
(T2) update foo set value='b' where key=1 (T2 Blocks)
(T2) update bar set value='b' where key=1
(T1) update bar set value='a' where key=1
(T1) commit (T2 unblocked)
(T2) commit
No deadlock. Yay. I know that things get more complicated with more
tables, but as long as one can predict that this might happen
sometimes, I think we're still ok.
You also mentioned this nasty bugger:
master:
(T0) commit
(T1) update foo set value='a' where key=1
(T2) update bar set value='b' where key=1
(T1) commit
(T2) commit
Because T2 might end up getting the lock first on the slave, you'd have
(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, or full table serialization. *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.
Really though, neither of these solutions precludes the other. So one
thought is to allow the slave to decide. This doesn't seem all that
out of line:
slave_serialize_tables=foo,bar
Adding the LOCK TABLES bit whenever those tables are locked in a
transaction, but otherwise using the deadlock retry method.
One possible solution is to have T1 acquire all locks in advance,
which
should preserve the original serialization but eliminate deadlock.
However,
that means you can't just execute SQL commands on the slave to apply
changes. Another option is to apply the approach only on groups of
autocommit transactions, but that would rule out a lot of the value.
In general it seems the easier solution is to look for application
features
that partition data into disjoint sets so you can replicate in
parallel
streams. In this case you typically need the application author to
provide
some hints. It would be interesting to think how Drizzle could make
that
process easier.
I think the issue is what is harder for users to do? Identify which
tables in their application need serialization, or rewriting their app
to be partitioned?
I do like the idea of having hints. A simple idea for doing this would
be to simply fence databases off from one another for cross-db joins
and updates, and have multiple replication logs generated from each
database.
_______________________________________________
Mailing list: https://launchpad.net/~drizzle-discuss
Post to : [email protected]
Unsubscribe : https://launchpad.net/~drizzle-discuss
More help : https://help.launchpad.net/ListHelp
