• A
    Use SipHash hash function to mitigate HashDos attempts. · adeed29a
    antirez 提交于
    This change attempts to switch to an hash function which mitigates
    the effects of the HashDoS attack (denial of service attack trying
    to force data structures to worst case behavior) while at the same time
    providing Redis with an hash function that does not expect the input
    data to be word aligned, a condition no longer true now that sds.c
    strings have a varialbe length header.
    
    Note that it is possible sometimes that even using an hash function
    for which collisions cannot be generated without knowing the seed,
    special implementation details or the exposure of the seed in an
    indirect way (for example the ability to add elements to a Set and
    check the return in which Redis returns them with SMEMBERS) may
    make the attacker's life simpler in the process of trying to guess
    the correct seed, however the next step would be to switch to a
    log(N) data structure when too many items in a single bucket are
    detected: this seems like an overkill in the case of Redis.
    
    SPEED REGRESION TESTS:
    
    In order to verify that switching from MurmurHash to SipHash had
    no impact on speed, a set of benchmarks involving fast insertion
    of 5 million of keys were performed.
    
    The result shows Redis with SipHash in high pipelining conditions
    to be about 4% slower compared to using the previous hash function.
    However this could partially be related to the fact that the current
    implementation does not attempt to hash whole words at a time but
    reads single bytes, in order to have an output which is endian-netural
    and at the same time working on systems where unaligned memory accesses
    are a problem.
    
    Further X86 specific optimizations should be tested, the function
    may easily get at the same level of MurMurHash2 if a few optimizations
    are performed.
    adeed29a
dict.h 7.1 KB