Hi Paul
Paul McCullagh wrote:
Hi Michael,
Your idea would not just allow us to run transactions in parallel on the
slave, but would also split transactions into pieces that could be run
in parallel. Which would be pretty cool!
But some things may be too complicated to allow for implementation in a
reasonable time.
For example, preventing "consistent read from looking at TXN1 updates
when TXN1 is committed but TXN2 is not", would probably have to be
implemented in the engine, and could be quite tricky.
I quite agree. The trickiness would depend on the engine. So ideally
the outside replication layer shouldn't concern itself much with execution
parallelization. The engine itself is the best judge here. I can imagine
that InnoDB, PBXT and ScaleDB could come up each with its own bag of tricks.
This could also be a problem: "The recovery layer should then ask the SE
to roll back TXN1 and reapply TXN", where TXN1 was a committed transaction.
I know of no way to rollback an already committed transaction, unless
maybe it was the last transaction committed.
It doesn't seem to be necessary because there was hole in my logic anyway.
What's committed is committed, it could be a base for subsequent committed
changes
so uncommitting it would be impossible for most engines.
In reality if TXN is parallelized to TXN1 + TXN2 + ..., then for crash recovery
purposes
TXNn are separate transactions as far as SE is concerned. So what the SE would
in fact do,
should it commit TXN2 before the crash, but not TXN1, is:
- roll forward TXN1, if necessary
- roll back TXN2
ask the replication layer for TXN, ignore events that has become part of TXN1,
reapply those that
are part of TXN2. This means that the SE should persist the correspondence
between TXN1 and its replication
events and there is no such SE I know of, parallel replication or not, but this
isn't drizzle's problem.
In general I would say that a solution that requires little, or no,
changes to the storage engines would be best, because they are already
so complicated.
I think the best solution would be to come up with a protocol that would allow
SE to do their stuff if the SE
so chooses. If the replication layer just provides the replication metadata and
transport layer while the SE
sticks its own opaque payload to the binlog, should it want to do physical
replication, this would be quite nice.
On the other hand a cooperative storage engine should be able to help the
replication layer with crash safe replication,
but it needs an interface, of which there's none in MySQL iirc. For example the
notorious problem of where to restart replication
after the slave crash can be solved by replication to SE cooperation, something
like this:
- the SE is aware it's executing replicated transactions and has access to some
form of replication txn id as it executes them
- at each commit it stores the replication txn number in the redo record for
the commit
- the SE knows at each moment such replication txn id that it has processed all
replication events before it. This number is also stored
in the redo log occasionally, a kind of replication checkpoint.
Then after a crash the SE will be able to tell the replication layer where to
restart replication, and will be able to avoid
applying the same even twice. This should even work for unsafe settings for
redo flushing when we can lose some committed transactions,
like innodb-flush-log-at-trx-commit=0.
Thanks,
Michael
Sorry, I am just pointing out problems without being constructive! :)
Best regards,
Paul
On May 12, 2009, at 2:28 AM, Michael Izioumtchenko wrote:
Clint Byrum wrote:
On May 9, 2009, at 5:53 AM, Paul McCullagh wrote:
As far as I know, the start time of a transaction is not significant.
Or do you maybe have an example of where this is the case?
If you focus on statement replication, then READ UNCOMMITTED would
possibly cause problems..
However, row based is the hot new thing, right? Row based replication
tells us which rows to update. Thinking about things in terms of rows
has made me think that we can actually do this w/o rolling back. Of
course, row based means it needs to be logged before knowing the
commit TX ID, but that is actually ok. We'll figure it out, and in
the process, we can figure out what ranges of IDs each transaction
modified. This will allow us to decide not to start transactions that
might modify the same rows as currently running transactions,
I think with row replication the deal is we shouldn't really be
worrying about this.
Imagine the following approach, not necessarily reflecting any
existing replication code, of course,
and assuming something like InnoDB as the storage engine.
- master logs events in the order the rows are updated.
By some magic it also throws away the updates that have been rolled back.
The update order is determined [mostly] by the storage engine which
has logs, transactions, all this good stuff.
There's no real need to replay the locks on the slave, it has all
already been decided upon and done on the master.
All we need to know is that if we apply the events one by one we'll
have the correct [in every sense] result at any given moment.
The challenge is to apply the events in parallel without losing most
of correctness.
- on the slave the event stream is split into one thread per X where X
is either:
- table
- a logical partition by unique key such as 'all records with
primary_key <X' and 'all records with primary_key >= X' being separate
threads
- with InnoDB it's probably not entirely unfeasible to update indexes
of the same table separately.
- each stream is fed into the engine by a separate thread using normal
interface.
This means a single master transaction is split into a few different
slave transactions which are all committed independently. TXN => TXN1
TXN2 ... TXNn.
The engine does locking as usual even though it shouldn't be necessary.
Let's address some challenges:
1. update order preservation. It seems to be a non issue because each
given record is processed by a single thread which receives the updates
in the right order. This means that we don't have to preserve the
order of master commits as long as we preserve the order of updates
for each row. This is the case when each table is processed by only
one thread, processing the same table by multiple threads
is considered separately.
2. crash recovery. Standard SE recovery could well leave us with TXN1
being committed while TXN2 being rolled back.
The recovery layer should then ask the SE to roll back TXN1 and
reapply TXN. The SE should therefore be able to understand
and satisfy such request.
3. consistent read. Something should prevent consistent read from
looking at TXN1 updates when TXN1 is committed but TXN2 is not.
The replication layer could instruct the server to instruct the SE to
ignore certain committed transactions
for consistent read purposes. So again the SE interface has to be
enhanced a bit. If the SE has an idea of transactions and consistent
read, it should be able to accept advice from the server as to which
transactions to exclude from the view.
4. for the logical partitioning case, updates that move records from
one partition to another, for the example above:
UPDATE t SET primary_key = X - 1 where primary_key = X.
Abstractly speaking, if each replication even has an increasing event
id, and also carries the event id from the previous
update of the same row, and we attach to each row the latest event it
has been updated with, then the problem is solved
by comparing row and event labels before applying the event, and
waiting for the proper update to arrive if necessary.
More practically, if we consider the following order of execution on
master:
TXN-A: BEGIN
(1) TXN-A: UPDATE t SET primary_key = X - 1 where primary_key = X
TXN-A: COMMIT
TXN-B: BEGIN
(2) TXN-B: DELETE FROM t where primary_k = X - 1;
(3) TXN-B: INSERT INTO t (primary_key...) VALUES (X - 1,...
TXN-B: COMMIT
with parallelization, the order of TXN-A then TXN-B can easily be
reversed because both TXN-B statements go to one thread,
and the TXN-A statement, to another. Obviously native SE locking on
the slave isn't going to help here unless we also coordinate between
two slave threads to preserve the commit order which defy the whole
parallelization idea.
I'm not 100% sure but what should help here is the replication layer
replacing the UPDATE in the replication stream with
(1a) DELETE FROM t WHERE primary_key = X;
(1b) INSERT INTO t (primary_key...) VALUES (X-1...);
In this case replication thread 1 (primary key <X) gets statements 1b,
then 2, then 3;
replication thread 2(primary key >= X) gets statement 1a, and the end
result will be correct even if thread 1 lags behind thread 2.
5. Consistent read again. It looks like if we don't preserve master
commit order, some consistent views read on the slave
will see the database as it has never been in any consistent read view
on the master. In the example above, if thread 2 lags behind,
then there may be a view where we see TXN-B committed but not TXN-A.
One possible answer to this is 'so what?'.
If we care, we shouldn't deliver this view to the user but rather
present him a view from just before TXN-A started.
The problem is passing that
information to the SE, in this case it would be 'for this SELECT,
don't include txn-B to the consistent read view even though it's
committed'.
6. parallel update of indexes of the same table? This could speed up
the inserts considerably but
is hardly possible without serious cooperation from the SE.
7. Multimaster replication and logically equivalent problem of local
updates. I don't know how to address it
but I think if you have multiple masters updating the same records
it's a different ballgame where there surely
must be some forms of addressing the relevant problems.
8. anything else I've missed?
Thank you,
Michael
The opinion(s) stated above, if any, are mine and don't necessarily
reflect those of my employer
thereby achieving what
Robert was suggesting, finding smaller slices than "table" to
parallelize on:
(T1) update foo set x=1 where id=1
(T2) update foo set x=2 where id=5
(T1) update foo set x=1 where id=5 (blocks)
(T2) commit (unblocks T1)
(T1) update foo set x=1 where id=100
(T1) update bar set z=9 where id=1
(T3) update foo set x=3 where id=50
(T3) update foo set x=3 where id=101
(T4) update foo set x=3 where id=100
(T1) commit
(T4) commit
(T3) commit
So, we start T1 and know that it changed row 1, so the range is 1:1 ,
then start looking forward for its commit id, all the while queueing
up T2-T4's row changes but not starting them. Then we find row 5
changed by T2. We keep track of its range too. Now we find that T2 is
committed. Next thing we find is that T1 has changed row 5. Its range
is now 1:5. Next we should find that it changed row 100, so now
1:100. While T1 was updating table bar, T3 came along and modified id
= 50. This hits the range, so we queue it to start after T1 commits.
We now set T3's range to 50:101. T4 is queued for starting after T3,
because its range it fits inside that range. Now once T1 commits, T3
is run and committed, then T4.
This means that some things that don't *have* to wait do wait.
However, I'm having a hard time imagining a situation where it starts
a transaction that might end up conflicting. And most of the time
we'll be able to start a lot of operations in parallel.
_______________________________________________
Mailing list: https://launchpad.net/~drizzle-discuss
Post to : [email protected]
Unsubscribe : https://launchpad.net/~drizzle-discuss
More help : https://help.launchpad.net/ListHelp
--
Paul McCullagh
PrimeBase Technologies
www.primebase.org
www.blobstreaming.org
pbxt.blogspot.com
_______________________________________________
Mailing list: https://launchpad.net/~drizzle-discuss
Post to : [email protected]
Unsubscribe : https://launchpad.net/~drizzle-discuss
More help : https://help.launchpad.net/ListHelp
