• A
    Hash function switched to murmurhash2. · 99c3338c
    antirez 提交于
    The previously used hash function, djbhash, is not secure against
    collision attacks even when the seed is randomized as there are simple
    ways to find seed-independent collisions.
    
    The new hash function appears to be safe (or much harder to exploit at
    least) in this case, and has better distribution.
    
    Better distribution does not always means that's better. For instance in
    a fast benchmark with "DEBUG POPULATE 1000000" I obtained the following
    results:
    
        1.6 seconds with djbhash
        2.0 seconds with murmurhash2
    
    This is due to the fact that djbhash will hash objects that follow the
    pattern `prefix:<id>` and where the id is numerically near, to near
    buckets. This improves the locality.
    
    However in other access patterns with keys that have no relation
    murmurhash2 has some (apparently minimal) speed advantage.
    
    On the other hand a better distribution should significantly
    improve the quality of the distribution of elements returned with
    dictGetRandomKey() that is used in SPOP, SRANDMEMBER, RANDOMKEY, and
    other commands.
    
    Everything considered, and under the suspect that this commit fixes a
    security issue in Redis, we are switching to the new hash function.
    If some serious speed regression will be found in the future we'll be able
    to step back easiliy.
    
    This commit fixes issue #663.
    99c3338c
dict.c 24.2 KB