- 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 2 commits
-
-
zhanghailei authored
-
zhanghailei authored
-
- 10 Dec, 2013 1 commit
-
-
antirez authored
Redis hash table implementation has many non-blocking features like incremental rehashing, however while deleting a large hash table there was no way to have a callback called to do some incremental work. This commit adds this support, as an optiona callback argument to dictEmpty() that is currently called at a fixed interval (one time every 65k deletions).
-
- 05 Dec, 2013 1 commit
-
-
antirez authored
-
- 05 Nov, 2013 1 commit
-
-
antirez authored
-
- 28 Oct, 2013 1 commit
-
-
antirez authored
-
- 25 Oct, 2013 4 commits
-
-
antirez authored
-
antirez authored
-
Pieter Noordhuis authored
The irrelevant bits shouldn't be masked to 1. This can result in slots being skipped when the hash table is resized between calls to the iterator.
-
Pieter Noordhuis authored
-
- 20 Aug, 2013 1 commit
-
-
antirez authored
-
- 19 Aug, 2013 5 commits
-
-
antirez authored
-
antirez authored
Also a warning was suppressed by including unistd.h in redisassert.h (needed for _exit()).
-
antirez authored
The previous hashing used the trivial algorithm of xoring the integers together. This is not optimal as it is very likely that different hash table setups will hash the same, for instance an hash table at the start of the rehashing process, and at the end, will have the same fingerprint. Now we hash N integers in a smarter way, by summing every integer to the previous hash, and taking the integer hashing again (see the code for further details). This way it is a lot less likely that we get a collision. Moreover this way of hashing explicitly protects from the same set of integers in a different order to hash to the same number. This commit is related to issue #1240.
-
antirez authored
dict.c allows the user to create unsafe iterators, that are iterators that will not touch the dictionary data structure in any way, preventing copy on write, but at the same time are limited in their usage. The limitation is that when itearting with an unsafe iterator, no call to other dictionary functions must be done inside the iteration loop, otherwise the dictionary may be incrementally rehashed resulting into missing elements in the set of the elements returned by the iterator. However after introducing this kind of iterators a number of bugs were found due to misuses of the API, and we are still finding bugs about this issue. The bugs are not trivial to track because the effect is just missing elements during the iteartion. This commit introduces auto-detection of the API misuse. The idea is that an unsafe iterator has a contract: from initialization to the release of the iterator the dictionary should not change. So we take a fingerprint of the dictionary state, xoring a few important dict properties when the unsafe iteartor is initialized. We later check when the iterator is released if the fingerprint is still the same. If it is not, we found a misuse of the iterator, as not allowed API calls changed the internal state of the dictionary. This code was checked against a real bug, issue #1240. This is what Redis prints (aborting) when a misuse is detected: Assertion failed: (iter->fingerprint == dictFingerprint(iter->d)), function dictReleaseIterator, file dict.c, line 587.
- 19 Jan, 2013 1 commit
-
-
guiquanz authored
-
- 28 Nov, 2012 1 commit
-
-
charsyam authored
-
- 08 Nov, 2012 1 commit
-
-
antirez authored
-
- 05 Oct, 2012 1 commit
-
-
antirez authored
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.
-
- 21 Apr, 2012 1 commit
-
-
antirez authored
-
- 18 Apr, 2012 1 commit
-
-
antirez authored
-
- 07 Apr, 2012 2 commits
-
-
Erik Dubbelboer authored
-
Erik Dubbelboer authored
-
- 15 Mar, 2012 1 commit
-
-
huangz1990 authored
-
- 22 Jan, 2012 1 commit
-
-
antirez authored
fixed typo in hahs function seed default value. It is no longer used but fixed to retain the old constant as default anyway.
-
- 21 Jan, 2012 1 commit
-
-
antirez authored
Fix for hash table collision attack. We simply randomize hash table initialization value at startup time.
-
- 08 Nov, 2011 3 commits
-
-
antirez authored
dict.c: added macros in dict.h to set signed and unsigned 64 bit values directly inside the hash entry without using additional memory.
-
antirez authored
-
antirez authored
dict.c: added two lower level methods for directly manipulating hash entries. This is useful in order to set 64 bit integers as values directly inside the hash entry (in order to save memory), without casting, and even in 32 bit builds.
-
- 02 Nov, 2011 1 commit
-
-
antirez authored
-
- 10 May, 2011 1 commit
-
-
antirez authored
Introduced a safe iterator interface that can be used to iterate while accessing the dictionary at the same time. Now the default interface is consireded unsafe and should be used only with dictNext()
-
- 11 Feb, 2011 1 commit
-
-
antirez authored
fixed two diskstore issues, a quasi-deadlock creating problems with I/O speed and a race condition among threads
-
- 03 Nov, 2010 1 commit
-
-
antirez authored
-
- 15 Sep, 2010 1 commit
-
-
antirez authored
This should fix Issue 332: when there is a background process saving we still allow the hash tables to grow, but only when a critical treshold is reached. Formerly we prevented the resize at all triggering pathological O(N) behavior. Also there is a fix for the statistics in INFO about the number of keys expired
-
- 27 Jul, 2010 1 commit
-
-
antirez authored
-
- 24 Jul, 2010 1 commit
-
-
Benjamin Kramer authored
calloc is more effecient than malloc+memset when the system uses mmap to allocate memory. mmap always returns zeroed memory so the memset can be avoided. The threshold to use mmap is 16k in osx libc and 128k in bsd libc and glibc. The kernel can lazily allocate the pages, this reduces memory usage when we have a page table or hash table that is mostly empty. This change is most visible when you start a new redis instance with vm enabled. You'll see no increased memory usage no matter how big your page table is.
-