In relational databases such as MySQL, database data is stored in a row record format. Similarly, we often say that Redis is an in-memory database composed of key-value pairs. Specifically, it is stored in what form. Let’s take a look at the source code below.
The data structure
redis.h/redisServerA record byredis.h/redisDbAn array of structures, each of theseredisDbIs a database, in Redis the default number of databases byREDIS_DEFAULT_DBNUMParameter control, default is 16.
typedef struct redisDb {
// Database key space, which holds all the key pairs in the database
dict *dict; /* The keyspace for this DB */
// The expiration time of the key, the key of the dictionary is the key, the value of the dictionary is the expiration event UNIX timestamp
dict *expires; /* Timeout of keys with a timeout set */
// The key that is blocking
dict *blocking_keys; /* Keys with clients waiting for data (BLPOP) */
// Unblocking key
dict *ready_keys; /* Blocked keys that received a PUSH */
// The key being monitored by the WATCH command
dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS */
struct evictionPoolEntry *eviction_pool; /* Eviction pool of keys */
// Database number
int id; /* Database ID */
// Average TTL of database keys, statistics
long long avg_ttl; /* Average TTL, just for stats */
} redisDb;
Copy the code- dict 以
A dictionary tableData structures store real database data - expires 以
A dictionary tableData structures are stored in all databasesKey KeyExpiration time data of
Data is stored
Dictionary (Hashtable). The underlying foundation determines the high-level architecture, so Redis databaseBuild, find, add, remove, expireAnd so on also use the features of the dictionary.
- Key KeyOne for each bond
String object - Value the ValueEach value can be
String object, list object, hash object, collection object, ordered collection objectAny one of them
The data to find
O(1), the search processing speed is very fast.
Data date
Lazy to delete
redis.c/expireIfNeededFor implementation, all on the databaseQuery, Delete, check keysThis function checks whether the key is expired, and removes the key when it expires. When detecting the existence of expired keys, AOF files are written, Slave nodes are notified, event subscription notifications are sent, and key deletion is finally performed
/* * Check if the key has expired and, if so, remove it from the database. * Returning 0 indicates that the key has no expiration time, or that the key is not expired. * Returning 1 indicates that the key has been removed because it is out of date. * /
int expireIfNeeded(redisDb *db, robj *key) {
// Retrieve the expiration time of the key
mstime_t when = getExpire(db,key);
mstime_t now;
// There is no expiration time
if (when < 0) return 0; /* No expire for this key */
// If the server is loading, no expiration checks are done
if (server.loading) return 0;
now = server.lua_caller ? server.lua_time_start : mstime();
// When the server is running in replication mode
// Affiliate nodes do not actively delete keys
// It only returns a logically correct return value
// The actual delete operation is not performed until the master node sends the delete command
// To ensure data synchronization
if(server.masterhost ! =NULL) return now > when;
// Run here to indicate that the key has an expiration date and the server is the primary node
/* Return when this key has not expired */
// If not, 0 is returned
if (now <= when) return 0;
/* Delete the key */
server.stat_expiredkeys++;
// Propagate expiration information to AOF files and affiliated nodes
propagateExpire(db,key);
// Send event notification
notifyKeyspaceEvent(REDIS_NOTIFY_EXPIRED,
"expired",key,db->id);
// Delete the expired key from the database
return dbDelete(db,key);
}
Copy the codePeriodically delete
redis.c/activeExpireCycleFunction implementation, which will be periodically executed by Redis functionredis.c/serverCronCalled when the function executes
- Fast modeThe function is evaluated by mode setting
timeout, defaults to 1000 subtlety in fast mode, otherwise set based on 25% CPU execution time - Number of processingThe database is normally initialized with 16, and here 16 will be processed by default for full scan in each database
redisdbtheexpiresThis dictionary table randomly selects 20 entries for examination - Processing stops when function execution times out or expired keys that have been removed account for 25% of the total number of expired keys in the database
void activeExpireCycle(int type) {
/* This function has some global state in order to continue the work * incrementally across calls. */
// Static variable, used to accumulate data when the function is continuously executed
static unsigned int current_db = 0; /* Last DB tested. */
static int timelimit_exit = 0; /* Time limit hit in previous call? * /
static long long last_fast_cycle = 0; /* When last fast cycle ran. */
unsigned int j, iteration = 0;
// The default number of databases per process
unsigned int dbs_per_call = REDIS_DBCRON_DBS_PER_CALL;
// The start time of the function
long long start = ustime(), timelimit;
// Fast mode
if (type == ACTIVE_EXPIRE_CYCLE_FAST) {
/* Don't start a fast cycle if the previous cycle did not exited * for time limt. Also don't repeat a fast cycle for the same period * as the fast cycle total duration itself. */
// If timelimit_exit was not triggered last time, no processing is performed
if(! timelimit_exit)return;
// If a certain amount of time has elapsed since the last execution, no processing is performed
if (start < last_fast_cycle + ACTIVE_EXPIRE_CYCLE_FAST_DURATION*2) return;
// Run this command to record the current time
last_fast_cycle = start;
}
/* We usually should test REDIS_DBCRON_DBS_PER_CALL per iteration, with * two exceptions: * * In general, the function only handles REDIS_DBCRON_DBS_PER_CALL databases, * unless: * * 1) Don't test more DBs than we have limit, we want to scan all DBs * in this iteration, As there is work to do in some DB and we don't want * expired keys to use memory for too much time. This time, all databases need to be scanned, * this prevents too many expired keys from taking up space */
if (dbs_per_call > server.dbnum || timelimit_exit)
dbs_per_call = server.dbnum;
/* We can use at max ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC percentage of CPU time * per iteration. Since this function gets called with a frequency of * server.hz times per second, the following is the max amount of * microseconds we can spend in this function. */
// Upper limit of microseconds for function processing
// ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC defaults to 25, which is 25% of CPU time
timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100;
timelimit_exit = 0;
if (timelimit <= 0) timelimit = 1;
// If you are running in fast mode
// Then you can run at most FAST_DURATION microseconds
// Default is 1000 (microseconds)
if (type == ACTIVE_EXPIRE_CYCLE_FAST)
timelimit = ACTIVE_EXPIRE_CYCLE_FAST_DURATION; /* in microseconds. */
// Walk through the database
for (j = 0; j < dbs_per_call; j++) {
int expired;
// Points to the database to be processed
redisDb *db = server.db+(current_db % server.dbnum);
/* Increment the DB now so we are sure if we run out of time * in the current DB we'll restart from the next. This allows to * distribute the time evenly across DBs. */
// Increments the DB counter by one if the do loop is timed out
// Then next time it will start directly from the next DB
current_db++;
/* Continue to expire if at the end of the cycle more than 25% * of the keys were expired. */
do {
unsigned long num, slots;
long long now, ttl_sum;
int ttl_samples;
/* If there is nothing to expire try next DB ASAP. */
// Get the number of keys with expiration time in the database
// If the number is 0, skip the database
if ((num = dictSize(db->expires)) == 0) {
db->avg_ttl = 0;
break;
}
// Get the number of key-value pairs in the database
slots = dictSlots(db->expires);
// The current time
now = mstime();
/* When there are less than 1% filled slots getting random * keys is expensive, so stop here waiting for better times... * The dictionary will be resized asap. */
// The database usage is less than 1%, so scanning is too laborious (most of them MISS)
// Skip and wait for the dictionary shrink program to run
if (num && slots > DICT_HT_INITIAL_SIZE &&
(num*100/slots < 1)) break;
/* The main collection cycle. Sample random keys among keys * with an expire set, Checking for expired ones. * * Sample counter */
// Expired key counters have been processed
expired = 0;
// Total TTL counter for the key
ttl_sum = 0;
// The total number of key counters processed
ttl_samples = 0;
// A maximum of LOOKUPS_PER_LOOP keys can be checked at a time
if (num > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)
num = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP;
// Start traversing the database
while (num--) {
dictEntry *de;
long long ttl;
// Randomly remove a key from Expires with an expiration date
if ((de = dictGetRandomKey(db->expires)) == NULL) break;
/ / calculate TTL
ttl = dictGetSignedIntegerVal(de)-now;
// If the key is expired, delete it and increment the expired counter by one
if (activeExpireCycleTryExpire(db,de,now)) expired++;
if (ttl < 0) ttl = 0;
// Accumulate the TTL of the key
ttl_sum += ttl;
// Accumulate the number of processing keys
ttl_samples++;
}
/* Update the average TTL stats for this database. */
// Update average TTL statistics for this database
if (ttl_samples) {
// Calculate the current average
long long avg_ttl = ttl_sum/ttl_samples;
// If this is the first time to set the average TTL of the database, initialize it
if (db->avg_ttl == 0) db->avg_ttl = avg_ttl;
/* Smooth the value averaging with the previous one. */
// Take the average of the last and current average TTL of the database
db->avg_ttl = (db->avg_ttl+avg_ttl)/2;
}
/* We can't block forever here even if there are many keys to * expire. So after a given amount of milliseconds return to the * caller waiting for the other active expire cycle. */
// We can't deal with expired keys for too long,
// So this function will return after a certain amount of time
// Update the number of iterations
iteration++;
// Perform this operation 16 times
if ((iteration & 0xf) = =0 && /* check once every 16 iterations. */
(ustime()-start) > timelimit)
{
// If the number of iterations is exactly a multiple of 16
// And the traversal time exceeded timelimit
// Then disconnect timelimit_exit
timelimit_exit = 1;
}
// Time out, return
if (timelimit_exit) return;
/* We don't repeat the cycle if there are less than 25% of keys * found expired in the current DB. */
// If the deleted expired keys account for 25% of the total database keys with expired time
// Then no more traversal
} while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4); }}Copy the codeconclusion
- Redis uses different encoding format and data structure to build five object types according to data capacity. We often say Redis is a key-value database, mainly because it adopts the form of dictionary table to construct and store data of different data types in space, and makes full use of the characteristics of hash table quick addressing. This ensures high performance in data query and processing, and makes full use of the rehash feature of dictionary tables to expand data storage
- As mentioned earlier, Redis is an event-driven single-threaded service that defines time and file events to work together in a single-threaded environment. Key expiration maintenance is stored in a dictionary table equivalent to data storage. In order not to greatly affect Redis processing performance and maintenance cost, the lazy deletion and periodic deletion coexistence strategy is adopted. The elegant design can see the author’s deep thinking on the use of performance and the existence of many adaptive algorithms, which is worth learning
reference
Redis Design and Implementation