linux

baotiao, feels like another iterator issue. Was this ARM or Intel? How many cores?

this is intel with 64 cores.

I guess the performance cause by the iterate the lf_hash and copy the item to create new readview.
the non-lockfree hash only need add the lock and doing memcpy then unlock.

When there is little items in lf_hash, then the iterator operation is faster than the lock, memcpy, unlock operation. However, when there is lots of items in lf_hash, the iterator operation will cause much more time..

so if there is an operation can directly copy the lf_hash and store it in readview without lock?

No locks acquired during ReadView snapshot. I'm afraid direct copy won't work either.

If we compare original:

mutex_enter(&trx_sys.mutex);

memcpy(snapshot, &trx_sys.rw_trx_ids, sizeof(trx_sys.rw_trx_ids));

mutex_exit(&trx_sys.mutex);

versus new:

lf_hash_iterate(copy_one_id);

memcpy() is certainly cheaper than lf_hash iteration. But it requires all 560 threads to acquire trx_sys.mutex, which is certainly more expensive.

I will need to look into that. It feels like the problem is the same as in MDEV-20630. IIRC for 560 threads we must have 1024 dummy nodes, which have to be iterated.

Did you try comparing 500 threads? Or 1000 threads?

Yes, I try to comparing 560 threads.

If you make lf_hash_iterate less overhead. I MDEV-20630 don't need to reinit the hash_table size..

Right, I guess if MDEV-20630 can be worked around be reinit-ing the hash, this one can't.

Testing 500 and 1000 threads (lf vs non-lf) should prove my guess (I'm expecting lf to be faster with these thread counts).

I kind of reproduced this on my Broadwell
lf (e6a9ce27591abd612dbb1d6b89cf4b5f2cd24a42)
14601.65 (500 threads), 13634.36 (560 threads)

pre-lf (1464f4808c08155fd10ba09eae2bb2c3f177482c)
15786.70 (560 threads)

And I confirm iterator is high in the profile.

baotiao, are you benchmarking on SkyLake?

May be this is worth exploring:

diff --git a/mysys/lf_hash.c b/mysys/lf_hash.c

index a7c0767..76d45b2 100644

--- a/mysys/lf_hash.c

+++ b/mysys/lf_hash.c

@@ -419,7 +419,7 @@ int lf_hash_insert(LF_HASH *hash, LF_PINS *pins, const void *data)

     return 1;

   }

   csize= hash->size;

-  if ((my_atomic_add32(&hash->count, 1)+1.0) / csize > MAX_LOAD)

+  if ((my_atomic_add32(&hash->count, 1)+1.0) / csize > MAX_LOAD && csize < 128)

     my_atomic_cas32(&hash->size, &csize, csize*2);

   return 0;

 }

The above limits number of dummy nodes. It brings performance to pre-lf level.

As far as I understand, if you have less dummy nodes, you'll have more hash collisions. Basically all nodes between two dummy nodes is one hash bucket. So with a limit like csize < 128 you pretty much change the hash from O(1) to O(N).

May be it'd be better to increase MAX_LOAD? It'll still be O(1) but with a larger constant factor.

increase MAX_LOAD also cause more conflict.. as you said, change the algorithm from O(1) to O(MAX_LOAD)..

Looks like my patches for MDEV-20630 did make some difference for this workload: https://github.com/MariaDB/server/commits/bb-10.5-svoj-MDEV-20630
I can see performance is brought almost to the pre-lf level.

I think that the lock-free hash table belongs to the runtime team, which sanja is the leader of. InnoDB trx_sys.rw_trx_hash is merely using that code. There are also bigger worries: ThreadSanitizer is giving warnings, and apparently there are occasional crashes on the ARM platform.

ARM fixed in MDEV-23510 ( e0ba68ba34f5623cfa3c61e2e1966971703297f5 ). Structure was slightly changed (though commit message probably incorrect) and the misuse of volatile as a key was replaced. Its probably not enough to replace the pointer dereference hits krizhanovsky noted in MDEV-20630

In 10.6, thanks to MDEV-24167 having introduced a small rw-lock, we can do something similar to MDEV-20612 and have a regular hash table where we would embed the rw-locks. Possibly we can simply follow the solution of MDEV-22871 and MDEV-26828, and use a spinlock when a futex-like system call (MDEV-26476) is not available.

On ARMv8 we might want to implement MDEV-26609, that is, limit the number of pointers per cache line.

I'm running a synthetic benchmark, which does

UPDATE t1 set i = i+1

from 10 to 10 000 concurrent client connections, with table defined as

CREATE OR REPLACE TABLE t1 SELECT 0 as i;

Problem - if I run 256 clients after 10 000 clients, I get 700 000 queries per minute. If I run it before, I get 1 200 000 queries per minute. That's 40% regression. The profiler confirms that it is searching for something in lf_hash.
match_pins alone takes 14% of the whole CPU.

I agree with markoInnodb should try another kind of hash, that does not suffer garbage collections issues, especially since there now high performance hashes in Innodb, that can be protected by new scalable slim reader-writer lock, transactional memory lock guard, and what not.

FWIW: the biggest problem with lf_hash is memory fragmentation, which causes iterator to thrash dTLB. I had ~80% performance improvement by allocating nodes close to each other. This solution is under 100 LOC.

I trust that, and I'd take what works, as long as it works. Currently, lf thing suffers GC issues. and non-lf thing maybe would not. We're not using lock-free because lock-free algorithms are beautiful. It should improve performance, that's all

wlad uhm, does this issue have anything to do with GC? I thought it is about poor performance of lf_hash iterator, which doesn't touch GC at all.

...and you would certainly not see this problem with UPDATE t1 set i = i+1, because it doesn't snapshot ReadVew. It should be something like sysbench oltp_rw, probably in read-committed mode, with backup locks disabled (unless they were fixed in the meantime).

Nah, I do see this problem exactly with this workload. Below the full technology demonstration, I did not use sysbench this time . I also reran it, just to make sure I did not make a mistake. match_pins around 15% CPU.
load_test.cc

wlad, what you see is a different problem. Original problem was about lf_hash iterator, but your updates unveil pure lf_hash GC issue. Nevertheless having GC (match_pins()) consume 15% of CPU is not acceptable indeed.

One thing worth keeping in mind is that these 15% come from 2 lf_hash'es: MDL and trx_sys. There's also lf_hash of table definition cache on the way, but it has different load pattern and shouldn't contribute to match_pins().

It is also nice to see numbers like 700 000QPS and 1 200 000QPS, IIRC in pre-lf trx_sys (10.2) we couldn't go over ~100 000QPS.

Speaking of updates. With current lf_hash implementation rw_trx_hash concurrency tends to 100%, that is threads can perform hash operations without blocking each other. But it has overhead: GC.

If you partition rw_trx_hash and use mutex/rw_lock for protection, concurrency is going to be lower, roughly (100 - 100 / N)% (where N is number of partitions). That is if you have 4 partitions it will be 75%, for 10 partitions - 90%, etc.

I must admit I'm unsure which approach is going to provide better throughput. Partitioned hash sounds promising. Although lf_hash has room for improvement as well: it should be possible to make GC much faster than it currently is.

Speaking of quintessence of the problem: current MVCC implementation would probably never scale well for over 10000 connections. It has to snapshot identifiers of all connections, organise them for quick access (currently it is sort+bsearch). It is obvious that the more connections one has, the more expensive MVCC handling becomes. Dunno, probably there're better MVCC approaches out there.

svoj, to clarify - the numbers I gave is queries per minute, not per second. It would be fabulous is this would be QPS, but in fact I run test for a minute, and reported the overall number (bear in mind, it is a laptop with 4 real cores, so maybe it is still fine this way). There is also quite a contention on a single row that the test operates on. 15 % come almost all from trx_sys.

Function Name	Total CPU [unit, %]	Self CPU [unit, %]	Module	Category

| + [External Code]	152441 (99,85 %)	9526 (6,24 %)	Multiple modules	IO | Networking | Driver | Graphics | File System | Kernel

|| + tp_callback	128592 (84,22 %)	58 (0,04 %)	server.dll	IO | Networking | Driver | File System | Kernel

||| + threadpool_process_request	126337 (82,75 %)	56 (0,04 %)	server.dll	IO | Networking | Driver | File System | Kernel

|||| + do_command	125615 (82,27 %)	101 (0,07 %)	server.dll	IO | Networking | Driver | File System | Kernel

||||| + dispatch_command	125169 (81,98 %)	398 (0,26 %)	server.dll	IO | Networking | Driver | File System | Kernel

|||||| + mysql_parse	118937 (77,90 %)	98 (0,06 %)	server.dll	IO | Networking | Driver | File System | Kernel

||||||| + mysql_execute_command	112364 (73,60 %)	383 (0,25 %)	server.dll	IO | Networking | Driver | File System | Kernel

|||||||| - mysql_update	59004 (38,65 %)	822 (0,54 %)	server.dll	IO | Networking | File System | Kernel

|||||||| + trans_commit_stmt	46516 (30,47 %)	32 (0,02 %)	server.dll	IO | Networking | Driver | File System | Kernel

||||||||| + ha_commit_trans	46434 (30,41 %)	96 (0,06 %)	server.dll	IO | Networking | Driver | File System | Kernel

|||||||||| + ha_commit_one_phase	40267 (26,37 %)	13 (0,01 %)	server.dll	IO | Networking | Driver | File System | Kernel

||||||||||| + commit_one_phase_2	40254 (26,37 %)	69 (0,05 %)	server.dll	IO | Networking | Driver | File System | Kernel

|||||||||||| + innobase_commit	40037 (26,22 %)	55 (0,04 %)	server.dll	IO | Networking | Driver | File System | Kernel

||||||||||||| + innobase_commit_ordered_2	33424 (21,89 %)	20 (0,01 %)	server.dll	IO | Networking | Kernel

|||||||||||||| + trx_commit_for_mysql	33358 (21,85 %)	29 (0,02 %)	server.dll	IO | Networking | Kernel

||||||||||||||| + trx_t::commit	29979 (19,64 %)	28 (0,02 %)	server.dll	IO | Kernel

|||||||||||||||| + trx_t::commit_persist	29951 (19,62 %)	38 (0,02 %)	server.dll	IO | Kernel

||||||||||||||||| + trx_t::commit_in_memory	28322 (18,55 %)	179 (0,12 %)	server.dll	IO | Kernel

|||||||||||||||||| + lf_hash_delete	22832 (14,95 %)	66 (0,04 %)	server.dll	IO | Kernel

||||||||||||||||||| + l_delete	22701 (14,87 %)	35 (0,02 %)	server.dll	IO | Kernel

|||||||||||||||||||| + lf_pinbox_real_free	22477 (14,72 %)	127 (0,08 %)	server.dll	IO | Kernel

||||||||||||||||||||| + lf_dynarray_iterate	22347 (14,64 %)	17 (0,01 %)	server.dll	Kernel

|||||||||||||||||||||| + recursive_iterate	22330 (14,63 %)	242 (0,16 %)	server.dll	Kernel

||||||||||||||||||||||| + recursive_iterate	21569 (14,13 %)	431 (0,28 %)	server.dll	Kernel

|||||||||||||||||||||||| + match_pins	21138 (13,84 %)	21135 (13,84 %)	server.dll	Kernel

||||||||||||||||||||||||| - [System Call] ntoskrnl.exe	3 (0,00 %)	3 (0,00 %)	ntoskrnl.exe	Kernel

||||||||||||||||||||||| - match_pins	519 (0,34 %)	519 (0,34 %)	server.dll	

oh, 4 cores, c'mon

Note that your profiler refers to lf_dynarray_iterate(), while the bug is about lf_hash_iterate().

But match_pins() is a problem for sure.

BTW, I'd suggest you to check if TLB load is an issue.

svoj, for buf_pool.page_hash and lock_sys.rec_hash we have one rw-lock per cache line. That is, on AMD64 with 64-byte cache lines, each rw-lock covers 7 pointers. As a side effect of acquiring the lock, you will also have loaded those 7 pointers.

MDEV-26609 demonstrated that on systems with 128-byte cache lines, it could be useful to only use 64 bytes each cache line, to limit the lock contention.

The maximum number of concurrent transactions is innodb_page_size/16*128. With the default innodb_page_size=16k and a 64-byte cache line, we might allocate a hash array for all 131,072 elements, or 149,796 elements with the rw-locks (2,340 of them). I think that using a bit over 1 megabyte for the hash array might be acceptable. Using your formula, this would reduce concurrency by less than 5‰.

marko, yeah, it may work and fix issue described by Wlad. Although it is not evident (to me) if it is going to fix snapshot performance where you need to collect all active rw transactions id's as well as aggregate min(trx->no).

Luckily rw_trx_hash_t framework is friendly for experiments. Hope it can get tested on systems that have more than 4 laptop cores too.

svoj, to my understanding, our performance testing on Microsoft Windows is currently limited to laptop-grade hardware. On GNU/Linux we have more choice.

The hash table traversal for making a snapshot could acquire a shared lock on one hash array slice at a time. That lock could be elided on processors that support it, as in MDEV-26769. As far as I understand, the read view creation does not care about entries that would be added or removed afterwards.

Somewhat related to this, in MDEV-20612 we introduced a combination of lock_sys.latch and individual rw-locks inside lock_sys.rec_hash.array. An attempt to duplicate that would easily make the trx_sys equivalent of lock_sys.latch a bottleneck.

The 4 core laptop outlines the performance bugs much better than GNU/Linux, for which , no matter what patch is applied , all test differences would usually fall into 1-2% noise ratio (also, GNU/Linux has a real problem with providing a succinct, readable, usable profiler output). Until Linux can provide a profile that can pinpoint a problem, I'd have to stick to Windows laptops, with 4 core, or whatever cores we'll have.

I have not been actively working on this, but I keep this "in progress" so that I will not forget about this. Hopefully I will be able to return to this soon.

Like I wrote earlier, if we assume the default innodb_page_size=16k, the new trx_sys.rw_trx_hash could be an array that is a bit over 1 megabyte on a 64-bit system. The first element in each cache line would be a slim mutex or rw-lock (4 or 8 bytes), and the subsequent elements would be pointers to something similar to what we currently have:

struct rw_trx_hash_element_t

{

// constructor and destructor omitted for clarity

  trx_id_t id; /* lf_hash_init() relies on this to be first in the struct */

  /**

    Transaction serialization number.

    Assigned shortly before the transaction is moved to COMMITTED_IN_MEMORY

    state. Initially set to TRX_ID_MAX.

  */

  Atomic_counter<trx_id_t> no;

  trx_t *trx;

  mysql_mutex_t mutex;

};

We might eliminate the mutex and simply let each hash array mutex protect the contents of all hash bucket chains that reside in that cache line (it would be 7 on AMD64 and up to 15 on IA-32). If we do that, we might just let the transaction commit number be a normal variable. But, we would need a next-bucket pointer. The new structure could be like this:

struct rw_hash_element

{

  trx_id_t id; // duplicate of trx->id, to avoid dereferencing trx

  trx_id_t no; // transaction commit number, for read view creation

  trx_t *trx;

  rw_hash_element *next;

};

This is 32 bytes per element (or 24 on a 32-bit system, or 16 if we omitted the redundant id field). We might try to pack multiple elements per cache line (2 on AMD64) to improve the locality of reference. If the element mutex turns out to be necessary for performance, then we would probably want to have only one element per cache line.

An alternative hash table element could be as follows:

struct element

{

  trx_id_t no;

  trx_t *trx;

};

In this variant, the trx->id would not be duplicated, and the next pointer would be in trx_t in the same cache line with n_ref, id, state and possibly also rw_trx_hash_element.

On AMD64, this would allow us to pack 3 elements and one rw-lock in a 64-byte cache line. On ARMv8, it would be 7 elements per 128-byte cache line.

We might go one more step further and move also the commit number to trx_t::no, and directly store trx_t pointers in the hash array (7 to 15 trx_t* per cache line). In trx_t, we would like all of the following to be in a single cache line: n_ref, state, id, no, next, rw_trx_hash_element, mutex. We seem to be fine: 4+4+8+8+ptr+ptr+4=36 or 44 bytes (more than 4 bytes for mutex if SUX_LOCK_GENERIC is needed, that is, the underlying operating system does not support anything futex-like).

If the underlying operating system does not support futex, I would use the 32-bit std::atomic based rw_lock as a pure spinlock, like we do for the buf_pool.page_hash latches.

wlad, I posted a rough prototype. It survived the regression tests, but I did not check performance yet. It turns out that thanks to having the commit number directly in trx_t::no, we do not need any back pointer from trx_t to the hash table element. The only extra thing we need is a trx_t::rw_trx_hash pointer to the next trx_t in the hash bucket chain.

I refined my prototype, implemented the cache line alignment of trx_t and while doing that, replaced pointless 8×256 bytes of padding with alignment constraints. I tried to determine the optimal compile-time constant size for the hash table. On my dual Intel Xeon E5-2630 v4 system (2×2×10 threads), the sweet spot of throughput (average number of transactions per second) according to my quick testing (30-second sysbench oltp_update_index with 8×100,000 rows and innodb_flush_log_at_trx_commit=0 on fast NVMe storage) appears to be 64 payload cells if we ignore the last column. For higher loads, 256 (and maybe even more) cells would seem to help.

The performance dip at 80 concurrent connections was due to a checkpoint flush in the middle of my scripted prepare+benchmark run. In each case, the top throughput was reached at 160 concurrent connections (4 times the number of CPU hardware threads).
The compile-time parameter can be changed as follows:

diff --git a/storage/innobase/include/trx0sys.h b/storage/innobase/include/trx0sys.h

index 6caa02fcf6e..51f4bb8fe4f 100644

--- a/storage/innobase/include/trx0sys.h

+++ b/storage/innobase/include/trx0sys.h

@@ -330,7 +330,7 @@ constexpr uint32_t TRX_SYS_DOUBLEWRITE_SPACE_ID_STORED_N= 1783657386;

 class rw_trx_hash_t

 {

   /** number of payload elements in array[] */

-  static constexpr size_t n_cells= 128;

+  static constexpr size_t n_cells= 64;

   /** Hash cell chain */

   struct hash_chain

   {

I conducted some further tests on 10.9:

Like with the 10.6 test, at 80 concurrent connections there was some concurrent checkpoint flushing activity.

Unfortunately, we can see that at higher concurrency, the lock-free hash table performs better. For 10.6 it did not seem to be the case. The table below duplicates the table of the previous comment, but adds a bottom row for the baseline performance:

The different characteristics in 10.9 could be explained by MDEV-14425 and related changes in 10.8. My microbenchmarks are definitely too small for drawing any conclusion.

In any case, I think that the cache line optimized trx_t allocation could be adopted (after some performance testing).

I applied some cleanup in MDEV-28313 and rebased the lock-free hash table replacement on it. We can only observe a consistent performance regression:

The numbers at 80 concurrent connections are unreliable, because a checkpoint flush occurred during that in my microbenchmark.

I merged MDEV-28313 to 10.9 to create a new baseline, and then merged this on top. The results are just as bad as with 10.6. We can only observe an improvement at 20 concurrent connections; there is a regression in all other cases:

Apart from some recovery code, there are two sources of trx_sys.rw_trx_hash traversal, which will be affected by MDEV-20630:

1. cloning a read view
   • in trx_sys.snapshot_ids() executed via ReadViewBase::snapshot() and ReadView::open()
   • in trx_sys.clone_oldest_view() executed via purge_sys.clone_oldest_view()
2. determining the minimum transaction identifier in any read view

In MySQL 8.0.29, trx_rw_min_trx_id() was partly removed as redundant and partly replaced with a simpler operation.

I created something similar, replacing trx_sys.get_min_trx_id() with trx_sys.find_same_or_older(). I expect it to improve performance of operations that involve secondary indexes. The new hash table traversal trx_sys.find_same_or_older() employs short circuit evaluation, in a strictly read-only operation (not even acquiring any mutex).

I reran the 30-second 8×100,000-row Sysbench oltp_update_index with innodb_flush_log_at_trx_commit=0 to get some quick indication of the impact:

The last two rows indicate that there is quite a bit of variation in the throughput, in addition to the checkpoint glitch that occurs during the 80-connection test.

The combination with MDEV-26603 must also be tested against a baseline with innodb_flush_log_at_trx_commit=1:

So, unfortunately even this fix does not cure the counterintuitive regression revealed by MDEV-26603.
Side note: At 160 concurrent connections, the durable configuration innodb_flush_log_at_trx_commit=1 resulted in better throughput than innodb_flush_log_at_trx_commit=0, possibly thanks to the group commit locks acting as a throttle that prevented more costly contention elsewhere.

axel, can you please run your standard benchmarks on 10.6+patch?

I filed a separate ticket MDEV-28445 for the clean-up, because it did not show any difference (for the better or the worse) in axel’s standard test battery. Therefore, we cannot claim that it would fix this performance regression.

I guess that our standard test batteries might not exercise locking conflicts at all, especially on secondary indexes. Something bigger like TPC-C might show a difference.

MDEV-28445 caused a performance regression MDEV-30357. As a part of the fix, I would implement a cache that avoids some repeated traversal of trx_sys.rw_trx_hash in repeated invocations of trx_sys_t::find_same_or_older() within the same transaction.

MDEV-20630 may be more rewarding to fix first. I see that the lock-free hash table is using std::memory_order_seq_cst, while a less intrusive memory order (or explicit memory barriers) might work. I have not studied that code in much detail. What I attempted so far was to make InnoDB invoke the expensive operations less often (MDEV-28445, MDEV-30357), and to replace the lock-free hash table trx_sys.rw_trx_hash with a locking one, which resulted in worse performance.

Automated message:
----------------------------
Since this issue has not been updated since 6 weeks, it's time to move it back to Stalled.