The role of rehash
As our Redis operation continues to execute, the number of key-value pairs stored in the hash table will gradually increase or decrease. When the data in the dictionary is too large, more key conflicts will occur, resulting in an increase in the cost of querying data. When data is reduced, the allocated memory is still occupied, resulting in memory waste. In order to keep the load factor of the hash table within a reasonable range, the program needs to expand or shrink the size of the hash table
The principle of rehash
- Rehash: First let’s look at the dictionary and hash table structure definitions
/* * dictionary */
typedef struct dict {
// Type specific functions
dictType *type;
// Private data
void *privdata;
/ / a hash table
dictht ht[2];
/ / rehash index
// When rehash is not in progress, the value is -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
// The number of security iterators currently running
int iterators; /* number of iterators currently running */
} dict;
Copy the code/ / a hash table
typedef struct dictht {
// Hash table array
dictEntry **table;
// Hash table size
unsigned long size;
// Hash table size mask, used to calculate index values
// always equal to size-1
unsigned long sizemask;
// The number of existing nodes in the hash table
unsigned long used;
} dictht;
Copy the codeIf rehashidx == -1, rehash is to reallocate memory on HT [1] and migrate data from HT [0] to HT [1].
- Progressive: The process of rehash is not done all at once, but rather a number of migrations at a time, in dictionary reads and writes, and in timed events
Expansion process source code analysis
So it’s a dictionary-related operation, and scaling usually happens when you need to Set keys, so we went straight to the dict.c file to see if there are any functions that Add or Set strings. By searching and looking at the code, we found a function that has similar logic
int dictAdd(dict *d, void *key, void *val)
{
// Try adding a key to the dictionary and return a new hash node containing the key
// T = O(N)
dictEntry *entry = dictAddRaw(d,key);
// todo ...
}
Copy the codeThis function calls dictAddRaw(…) Method Allocate memory to dict to continue to view dictAddRaw(…) The code of
dictEntry *dictAddRaw(dict *d, void *key)
{
int index;
dictEntry *entry;
dictht *ht;
// Single-step rehash if conditions permit
// T = O(1)
if (dictIsRehashing(d)) _dictRehashStep(d);
/* Get the index of the new element, or -1 if * the element already exists. */
// Calculate the key index in the hash table
// If the value is -1, the key already exists
// T = O(N)
if ((index = _dictKeyIndex(d, key)) == - 1)
return NULL;
// T = O(1)
/* Allocate the memory and store the new entry */
// If the dictionary is rehashing, add the new key to hash table 1
// Otherwise, add the new key to hash 0
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
// Allocate space for the new node
entry = zmalloc(sizeof(*entry));
// Insert the new node into the list header
entry->next = ht->table[index];
ht->table[index] = entry;
// Update the number of nodes used in the hash table
ht->used++;
/* Set the hash entry fields. */
// Set the key of the new node
// T = O(1)
dictSetKey(d, entry, key);
return entry;
}
Copy the codeContinue to see the code in _dictKeyIndex
static int _dictKeyIndex(dict *d, const void *key)
{
unsigned int h, idx, table;
dictEntry *he;
/* Expand the hash table if needed */
/ / single-step rehash
// T = O(N)
if (_dictExpandIfNeeded(d) == DICT_ERR)
return - 1;
/* Compute the key hash value */
// Calculate the hash value of key
h = dictHashKey(d, key);
// T = O(1)
for (table = 0; table <= 1; table++) {
// Calculate the index value
idx = h & d->ht[table].sizemask;
/* Search if this slot does not already contain the given key */
// Check whether the key exists
// T = O(1)
he = d->ht[table].table[idx];
while(he) {
if (dictCompareKeys(d, key, he->key))
return - 1;
he = he->next;
}
// All nodes in hash table 0 do not contain keys
// If the rehahs is in progress at this point, continue to rehash hash hash table 1
if(! dictIsRehashing(d))break;
}
// return the index value
return idx;
}
Copy the codeBy looking at the code above, we can find several key points that pass through the calculation of index values in the dictionary
// Calculate the hash value of key
h = dictHashKey(d, key);
idx = h & d->ht[table].sizemask;
Copy the codeAnd we can also see the cost of finding a key when there’s a key conflict
he = d->ht[table].table[idx];
while(he) {
if (dictCompareKeys(d, key, he->key))
return - 1;
he = he->next;
}
Copy the codeThe most important is _dictExpandIfNeeded through the function name we feel this is related to expansion
static int _dictExpandIfNeeded(dict *d)
{
/* Incremental rehashing already in progress. Return. */
// Progressive rehash is already underway, returning directly
if (dictIsRehashing(d)) return DICT_OK;
/* If the hash table is empty expand it to the initial size. */
If the dictionary (hash table 0) is empty, create and return hash table 0 of initial size
// T = O(1)
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
/* If we reached the 1:1 ratio, and we are allowed to resize the hash * table (global setting) or we should avoid it but the ratio between * elements/buckets is over the "safe" threshold, we resize doubling * the number of buckets. */
If one of the following two conditions is true, the dictionary is expanded
// 1) The ratio between the number of nodes used in the dictionary and the size of the dictionary is close to 1:1
// and dict_can_resize is true
// 2) The ratio between the number of nodes used and the dictionary size exceeds dict_force_resize_ratio
if (d->ht[0].used >= d->ht[0].size &&
(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
// The size of the new hash table is at least twice the number of nodes currently in use
// T = O(N)
return dictExpand(d, d->ht[0].used*2);
}
return DICT_OK;
}
Copy the codeIt can be seen from the above code that the most fundamental memory allocation operation is at _dictExpandIfNeeded(…). Function. This function will determine that when the number of used key values on the hash table is dict_force_resize_ratio(representing constant 5), the memory will be reallocated, and the memory size is 2 times that of the used memory
conclusion
- The whole source code process, we found in the implementation
dictAdd(...)Is called when a key value is added to the dictionary_dictExpandIfNeeded(...)To viewht[0].used/ht[0].size > 5Whether it istrueIf yes, reallocate the memory with the size ofht[0].used * 2 - In the view
dictAddRaw(...)Function code, there is a command
// Single-step rehash if conditions permit
// T = O(1)
if (dictIsRehashing(d)) _dictRehashStep(d);
Copy the codeThe function of _dictRehashStep is to perform a migration of key values from H [0] to H [1]. Searching for this function in dict.c, you will find that this function will be called for dict related read and write operations, which also verifies that the rehahs process is not completed in one step, but gradually
Shrink process source code analysis
Dictionary memory shrinkage is mainly in timed events, timed check, judgment, related code as follows
void databasesCron(void) {
// todo ...
// Rehash the hash table when no BGSAVE or BGREWRITEAOF execution is performed
if (server.rdb_child_pid == - 1 && server.aof_child_pid == - 1) {
/* We use global counters so if we stop the computation at a given * DB we'll be able to start from the successive in the next * cron loop iteration. */
static unsigned int resize_db = 0;
static unsigned int rehash_db = 0;
unsigned int dbs_per_call = REDIS_DBCRON_DBS_PER_CALL;
unsigned int j;
/* Don't test more DBs than we have. */
// Set the number of databases to be tested
if (dbs_per_call > server.dbnum) dbs_per_call = server.dbnum;
/* Resize */
// Resize the dictionary
for (j = 0; j < dbs_per_call; j++) {
tryResizeHashTables(resize_db % server.dbnum);
resize_db++;
}
/* Rehash */
// Progressively rehash the dictionary
if (server.activerehashing) {
for (j = 0; j < dbs_per_call; j++) {
int work_done = incrementallyRehash(rehash_db % server.dbnum);
rehash_db++;
if (work_done) {
/* If the function did some work, stop here, we'll do * more at the next cron loop. */
break;
}
}
}
}
}
Copy the codeIn addition to looping and judging, the above code has two more special functions
tryResizHashTables, related source code
void tryResizeHashTables(int dbid) {
if (htNeedsResize(server.db[dbid].dict))
dictResize(server.db[dbid].dict);
if (htNeedsResize(server.db[dbid].expires))
dictResize(server.db[dbid].expires);
}
//htNeedsResize
int htNeedsResize(dict *dict) {
long long size, used;
size = dictSlots(dict);
used = dictSize(dict);
return (size && used && size > DICT_HT_INITIAL_SIZE &&
(used*100/size < REDIS_HT_MINFILL));
}
Copy the codeIf used* 100 / size < REDIS_HT_MINFILL is true, dictResize will be called to reallocate memory
incrementallyRehash, related source code
int incrementallyRehash(int dbid) {
/* Keys dictionary */
if (dictIsRehashing(server.db[dbid].dict)) {
dictRehashMilliseconds(server.db[dbid].dict,1);
return 1; /* already used our millisecond for this loop... * /
}
/* Expires */
if (dictIsRehashing(server.db[dbid].expires)) {
dictRehashMilliseconds(server.db[dbid].expires,1);
return 1; /* already used our millisecond for this loop... * /
}
return 0;
}
//dictRehashMillisecnods
/* Rehash the dictionary in 100 steps for a given number of milliseconds. * * T = O(N) */
int dictRehashMilliseconds(dict *d, int ms) {
// Record the start time
long long start = timeInMilliseconds();
int rehashes = 0;
while(dictRehash(d,100)) {
rehashes += 100;
// If time is up, jump out
if (timeInMilliseconds()-start > ms) break;
}
return rehashes;
}
Copy the codeAnalysis shows that this function performs 100 hash table data migrations of the dictionary being rehashed 1 millisecond at a time.
conclusion
- Hash table shrinkage is performed primarily within timed events
- Memory shrinkage occurs when the ratio of used keys and values is less than 0.1 of the allocated memory
- In addition to the data migration described above during read and write operations, data migration also occurs during timed events. In addition, data cannot be migrated if there is no read/write operation for a long time