tree 49b79d1a2d78d68bda57224ec2e33d924665a605
parent 17807ed3a09c8e8b6b4e7df6797dcd0555d06089
author Willy Tarreau <w@1wt.eu> 1613575615 +0100
committer Willy Tarreau <w@1wt.eu> 1615385476 +0100
encoding latin1

OPTIM: lb-leastconn: do not unlink the server if it did not change

Due to the two-phase server reservation, there are 3 calls to
fwlc_srv_reposition() per request, one during assign_server() to reserve
the slot, one in connect_server() to commit it, and one in process_stream()
to release it. However only one of the first two will change the key, so
it's needlessly costly to take the lock, remove a server and insert it
again at the same place when we can already figure we ought not to even
have taken the lock.

Furthermore, even when the server needs to move, there can be quite some
contention on the lbprm lock forcing the thread to wait. During this time
the served and nbpend server values might have changed, just like the
lb_node.key itself. Thus we measure the values again under the lock
before updating the tree. Measurements have shown that under contention
with 16 servers and 16 threads, 50% of the updates can be avoided there.

This patch makes the function compute the new key and compare it to
the current one before deciding to move the entry (and does it again
under the lock forthe second test).

This removes between 40 and 50% of the tree updates depending on the
thread contention and the number of servers. The performance gain due
to this (on 16 threads) was:

   16 servers:  415 krps -> 440 krps (6%, contention on lbprm)
    4 servers:  554 krps -> 714 krps (+29%, little contention)

One point worth thinking about is that it's not logic to update the
tree 2-3 times per request while it's only read once. half to 2/3 of
these updates are not needed. An experiment consisting in subscribing
the server to a list and letting the readers reinsert them on the fly
showed further degradation instead of an improvement.

A better approach would probably consist in avoinding writes to shared
cache lines by having the leastconn nodes distinct from the servers,
with one node per value, and having them hold an mt-list with all the
servers having that number of connections. The connection count tree
would then be read-mostly instead of facing heavy writes, and most
write operations would be performed on 1-3 list heads which are way
cheaper to migrate than a tree node, and do not require updating the
last two updated neighbors' cache lines.

(cherry picked from commit 5064ab6a982a82c275393220716b75c13789de89)
Signed-off-by: Willy Tarreau <w@1wt.eu>