cgrzemba / 389-ds-base

Forked from 389-ds-base 5 years ago
Clone

fb27943 Ticket 49330 - Improve ndn cache performance 1.3.5

Authored and Committed by William Brown 6 years ago
    Ticket 49330 - Improve ndn cache performance 1.3.5
    
    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: lkrispend, tbordaz (thanks)
    
    fix
    
        
file modified
+6 -0
file modified
+1 -1
file modified
+1 -1
file modified
+517 -293