Ticket 49330 - Improve ndn cache performance 1.3.6
Backport from 1.3.7 master.
Bug Description: Normalised DN's are a costly process to update
and maintain. As a result, a normalised DN cache was created. Yet
it was never able to perform well. In some datasets with large sets
of dn attr types, the NDN cache actively hurt performance.
The issue stemmed from 3 major issues in the design of the NDN
cache.
First, it is a global cache which means it exists behind
a rwlock. This causes delay as threads wait behind the lock
to access or update the cache (especially on a miss).
Second, the cache was limited to 4073 buckets. Despite the fact
that a prime number on a hash causes a skew in distribution,
this was in an NSPR hash - which does not grow dynamically,
rather devolving a bucket to a linked list. AS a result, once you
passed ~3000 your lookup performance would degrade rapidly to O(1)
Finally, the cache's lru policy did not evict least used - it
evicted the 10,000 least used. So if you tuned your cache
to match the NSPR map, every inclusion that would trigger a
delete of old values would effectively empty your cache. ON bigger
set sizes, this has to walk the map (at O(1)) to clean 10,000
elements.
Premature optimisation strikes again ....
Fix Description: Throw it out. Rewrite. We now use a hash
algo that has proper distribution across a set. The hash
sizes slots to a power of two. Finally, each thread has
a private cache rather than shared which completely eliminates
a lock contention and even NUMA performance issues.
Interestingly this fix should have improvements for DB
imports, memberof and refint performance and more.
Some testing has shown in simple search workloads a 10%
improvement in throughput, and on complex searches a 47x
improvement.
https://pagure.io/389-ds-base/issue/49330
Author: wibrown
Review by: lkrispen, tbordaz