lp:~akopytov/percona-server/bug1131189

Created by Alexey Kopytov on 2013-02-22 and last modified on 2013-03-25
Get this branch:
bzr branch lp:~akopytov/percona-server/bug1131189
Only Alexey Kopytov can upload to this branch. If you are Alexey Kopytov please log in for upload directions.

Branch merges

Related bugs

Related blueprints

Branch information

Recent revisions

452. By Alexey Kopytov on 2013-03-25

Bug #1131189: Remove trx_list scan from read_view_open_now()

The patch introduces a concept if "trx descriptors" which is a global
ordered array containing IDs of transactions in either TRX_ACTIVE or
TRX_PREPARED state. It allows to replace the trx_list scan in
read_view_open_now() and read_cursor_view_create_for_mysql() with a
binary search on the descriptors array and two memcpy()s.

Goals of using the ID array of transactions in certain states:

- we remove dependencies on trx_struct size and cache locality of those
  structures in memory
- per-node copying is replaced with memcpy()
- we don't have to check trx_struct fields for each trx_list node, such
  as ID, state and no.

Since there is no transaction serialization numbers (i.e. trx->no) in the
descriptors array, this check was replaced by keeping a separate,
trx->no ordered list (trx_sys->trx_serial_list). Getting the current
minimum for the current read view is then simply a matter of getting
trx->no of the first element from trx_serial_list.

Costs for maintaining the descriptors array:

- whenever a transaction is started, we need to insert its ID into the
  descriptors array. This in most cases is very cheap, as transactions
  are started with increasing IDs, so we can just add it as the last
  element in the descriptors array. In the unlikely case when this
  invariant does not hold (which is impossible with the current code),
  we look for the right slot using a linear search. A binary search
  would work better for cases when the right slot is far away from the
  array end, but again, this is defensive against future code changes
  that could possibly lead to breaking the ascending order in which new
  IDs are added, and we hope that it will be "mostly ascending", so a
  linear search should be faster;

- whenever a transaction is committed, we need to remove its ID from the
  descriptors array. Which is performed by ut_memmove() on the array. We
  could theoretically allow unused array slots but that would: 1)
  increase the size of descriptors by the 'used/unused' flag; 2) make
  using memcpy() in read_view_open_now() impossible, as we would also
  have to filter unused slots and 3) make the operation of adding a new
  descriptor scan the array for an unused slot;

- when removing a transaction ID from the descriptors array, we first
  have to find the corresponding slot with a binary search. We could
  avoid this by maintaining the "trx -> descriptors slot" mapping, but
  since the array may be resized or reordered on insertion, keeping
  this association is not practically feasible;

All of the above is performed under the kernel_mutex. But benchmarks
prove this overhead is negligible as compared to the list scan in
read_view_open_now().

The initial size of the descriptors array is 1000 slots (i.e. 8000
bytes). It is resized whenever we need more descriptors.

The patch also renames 'conc_state' to 'state' in trx_struct. The patch
would be much smaller without this change, but the purpose is to make
sure we notice any code changes around transaction states, as it is
critical for correct descriptors array maintenance. I tried implementing
a getter/setter pair of functions for trx state, but the patch got even
messier, because trx state may be changed with kernel_mutex either
locked or unlocked, whereas we can only manipulate the descriptors array
with the mutex locked.

451. By Alexey Kopytov on 2013-03-15

Automerge of the fix for bug #1131187.

450. By <email address hidden> on 2013-02-20

Merge lp:~laurynas-biveinis/percona-server/bug1117067-5.5

449. By <email address hidden> on 2013-02-20

Merge lp:~akopytov/percona-server/bug1125259

448. By <email address hidden> on 2013-02-20

Merge lp:~laurynas-biveinis/percona-server/bug1089265-5.5

447. By <email address hidden> on 2013-02-19

Merge lp:~gl-az/percona-server/BT-26980-5.5-bug1068210

446. By Alexey Kopytov on 2013-02-15

Bug #1126077: Remove clang warnings

Fixed an annoying warning in the InnoDB code produced by clang.

This is a backport from 5.6.

445. By <email address hidden> on 2013-02-14

Merge lp:~sergei.glushchenko/percona-server/55-tp

444. By <email address hidden> on 2013-02-14

Empty merge from Percona Server 5.1

443. By <email address hidden> on 2013-02-13

Empty merge from Percona Server 5.1

Branch metadata

Branch format:
Branch format 7
Repository format:
Bazaar repository format 2a (needs bzr 1.16 or later)
Stacked on:
lp:percona-server/5.5
This branch contains Public information 
Everyone can see this information.

Subscribers