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.
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.
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.
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
