- 20 Feb, 2017 2 commits
-
-
antirez authored
-
antirez authored
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.
-
- 02 Jan, 2017 1 commit
-
-
oranagra authored
-
- 30 Dec, 2016 1 commit
-
-
oranagra authored
-
- 20 Sep, 2016 1 commit
-
-
antirez authored
Recently we moved the "return ASAP" condition for the Delete() function from checking .size to checking .used, which is smarter, however while testing the first table alone always works to ensure the dict is totally emtpy, when we test the .size field, testing .used requires testing both T0 and T1, since a rehashing could be in progress.
-
- 14 Sep, 2016 3 commits
-
-
antirez authored
What they say about "naming things" in programming?
-
antirez authored
Optimizations suggested and originally implemented by @oranagra. Re-applied by @antirez using the modified API.
-
oranagra authored
Notes by @antirez: This patch was picked from a larger commit by Oran and adapted to change the API a bit. The basic idea is to avoid double lookups when there is to use the value of the deleted entry. BEFORE: entry = dictFind( ... ); /* 1st lookup. */ /* Do somethjing with the entry. */ dictDelete(...); /* 2nd lookup. */ AFTER: entry = dictUnlink( ... ); /* 1st lookup. */ /* Do somethjing with the entry. */ dictFreeUnlinkedEntry(entry); /* No lookups!. */
-
- 12 Sep, 2016 1 commit
-
-
oranagra authored
(Change cherry-picked and modified by @antirez from a larger commit provided by @oranagra in PR #3223).
-
- 07 Sep, 2016 6 commits
- 25 Apr, 2016 1 commit
-
-
Oran Agra authored
-
- 01 Oct, 2015 1 commit
-
-
antirez authored
-
- 14 Jul, 2015 1 commit
-
-
antirez authored
The command reports information about the hash table internal state representing the specified database ID. This can be used in order to investigate rehashings, memory usage issues and for other debugging purposes.
-
- 27 Mar, 2015 2 commits
-
-
antirez authored
No semantical changes since to make dict.c truly able to scale over the 32 bit table size limit, the hash function shoulds and other internals related to hash function output should be 64 bit ready.
-
antirez authored
rehashidx is always positive in the two code paths, since the only negative value it could have is -1 when there is no rehashing in progress, and the condition is explicitly checked.
-
- 11 Feb, 2015 11 commits
-
-
antirez authored
The old version of SPOP with "count" argument used an API call of dict.c which was actually designed for a different goal, and was not capable of good distribution. We follow a different three-cases approach optimized for different ratiion between sets and requested number of elements. The implementation is simpler and allowed the removal of a large amount of code.
-
antirez authored
Fixed by @oranagra, thank you.
-
antirez authored
-
antirez authored
Avoid code repetition introduced with PR #2367, also fixes the return value to always return 0 if there is nothing more to rehash.
-
Sun He authored
-
antirez authored
This is very similar to the optimization applied to dictGetRandomKeys, but applied to the single key variant. Related to issue #2306.
-
antirez authored
Related to issue #2306.
-
antirez authored
We use the invariant that the original table ht[0] is never populated up to the index before the current rehashing index. Related to issue #2306.
-
antirez authored
Related to issue #2306.
-
antirez authored
Related to issue #2306.
-
antirez authored
Related to issue #2306.
-
- 23 Jan, 2015 1 commit
-
-
antirez authored
-
- 29 Sep, 2014 2 commits
-
-
Matt Stancliff authored
Some language in the comment was difficult to understand, so this commit: clarifies wording, removes unnecessary words, and relocates some dependent clauses closer to what they actually describe. I also tried to break up longer chains of thought (if X, then Y, and Q, and also F, so obviously M) into more manageable chunks for ease of understanding.
-
Michael Parker authored
Closes #1351
-
- 26 Aug, 2014 2 commits
- 18 Aug, 2014 1 commit
-
-
Cong Ding authored
Closes #878
-
- 13 Aug, 2014 1 commit
-
-
antirez authored
-
- 20 Mar, 2014 1 commit
-
-
antirez authored
This new function is useful to get a number of random entries from an hash table when we just need to do some sampling without particularly good distribution. It just jumps at a random place of the hash table and returns the first N items encountered by scanning linearly. The main usefulness of this function is to speedup Redis internal sampling of the key space, for example for key eviction or expiry.
-
- 04 Mar, 2014 1 commit
-
-
zhanghailei authored
-