452
|
|
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.
|
Alexey Kopytov |
11 years ago
|
|
|
451
|
|
|
Alexey Kopytov |
11 years ago
|
|
|
450
|
|
|
jenkins at percona |
11 years ago
|
|
|
449
|
|
|
jenkins at percona |
11 years ago
|
|
|
448
|
|
|
jenkins at percona |
11 years ago
|
|
|
447
|
|
|
jenkins at percona |
11 years ago
|
|
|
446
|
|
|
Alexey Kopytov |
11 years ago
|
|
|
445
|
|
|
jenkins at percona |
11 years ago
|
|
|
444
|
|
|
jenkins at percona |
11 years ago
|
|
|
443
|
|
|
jenkins at percona |
11 years ago
|
|
|
442
|
|
|
jenkins at percona |
11 years ago
|
|
|
441
|
|
|
jenkins at percona |
11 years ago
|
|
|
440
|
|
|
jenkins at percona |
11 years ago
|
|
|
439
|
|
|
Stewart Smith |
11 years ago
|
|
|
438
|
|
|
jenkins at percona |
11 years ago
|
|
|
437
|
|
|
jenkins at percona |
11 years ago
|
|
|
436
|
|
|
jenkins at percona |
11 years ago
|
|
|
435
|
|
|
jenkins at percona |
11 years ago
|
|
|
434
|
|
|
jenkins at percona |
11 years ago
|
|
|
433
|
|
|
jenkins at percona |
11 years ago
|
|
|