Home Database Redis Detailed explanation of redis data elimination strategy

Detailed explanation of redis data elimination strategy

Nov 28, 2019 pm 05:02 PM
redis

Detailed explanation of redis data elimination strategy

What this article talks about is that after redis sets the maximum memory, the size of the data set in the cache exceeds a certain proportion, and the elimination strategy implemented is not the strategy of deleting expired keys. Although both are very similar. (Recommended: redis video tutorial)

In redis, users are allowed to set the maximum memory size and enable the memory elimination function by configuring the maxmemory value in redis.conf. Very useful in situations.

Setting the maximum memory size can ensure that redis provides stable services to the outside world.

redis When the size of the memory data set increases to a certain size, the data elimination strategy will be implemented. Redis provides 6 data elimination strategies through maxmemory-policy setting strategy:

volatile-lru: Select the least recently used data from the data set (server.db[i].expires) with expiration time set for elimination.

volatile-ttl: Select the data that will expire from the data set (server.db[i].expires) that has set the expiration time.

volatile-random: Select the data that will expire from the set expiration time. Select any data from the data set (server.db[i].expires) for elimination

allkeys-lru: Select the least recently used data from the data set (server.db[i].dict) for elimination

allkeys-random: Select data arbitrarily from the data set (server.db[i].dict) to eliminate

no-enviction (eviction): prohibit the eviction of data

redis After it is determined to expel a key-value pair, the data will be deleted and the data change message will be published to the local (AOF persistence) and slave (master-slave connection)

LRU data elimination mechanism

The lru counter server.lrulock is saved in the server configuration and will be updated regularly (redis timer program serverCorn()). The value of server.lrulock is calculated based on server.unixtime.

In addition, it can be found from struct redisObject that each redis object will set the corresponding lru. It is conceivable that redisObject.lru will be updated every time the data is accessed.

The LRU data elimination mechanism is as follows: randomly select several key-value pairs in the data set, and remove the key-value pair with the largest lru among them. Therefore, you will find that redis does not guarantee to obtain the least recently used (LRU) key-value pairs in all data sets, but only a few randomly selected key-value pairs.

// redisServer 保存了 lru 计数器
struct redisServer {
...
unsigned lruclock:22; /* Clock incrementing every minute, for LRU */
...
};
// 每一个 redis 对象都保存了 lru
#define REDIS_LRU_CLOCK_MAX ((1<<21)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 10 /* LRU clock resolution in seconds */
typedef struct redisObject {
// 刚刚好 32 bits
// 对象的类型,字符串/列表/集合/哈希表
unsigned type:4;
// 未使用的两个位
unsigned notused:2; /* Not used */
// 编码的方式,redis 为了节省空间,提供多种方式来保存一个数据
// 譬如:“123456789” 会被存储为整数 123456789
unsigned encoding:4;
unsigned lru:22; /* lru time (relative to server.lruclock) */
// 引用数
int refcount;
// 数据指针
void *ptr;

} robj;
// redis 定时执行程序。联想:linux cron
int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
......
/* We have just 22 bits per object for LRU information.
* So we use an (eventually wrapping) LRU clock with 10 seconds resolution.
* 2^22 bits with 10 seconds resolution is more or less 1.5 years.
*
* Note that even if this will wrap after 1.5 years it&#39;s not a problem,
* everything will still work but just some object will appear younger
* to Redis. But for this to happen a given object should never be touched
* for 1.5 years.
*
* Note that you can change the resolution altering the
* REDIS_LRU_CLOCK_RESOLUTION define.

*/
updateLRUClock();
......
}
// 更新服务器的 lru 计数器
void updateLRUClock(void) {
server.lruclock = (server.unixtime/REDIS_LRU_CLOCK_RESOLUTION) &
REDIS_LRU_CLOCK_MAX;
}
Copy after login

TTL data elimination mechanism

The table in the redis data set data structure stores the expiration time of key-value pairs, that is, redisDb.expires. Similar to the LRU data elimination mechanism, the TTL data elimination mechanism is as follows: randomly select several key-value pairs from the expiration time table, and take out the key-value pair with the largest ttl and eliminate them.

Similarly, you will find that redis is not guaranteed to obtain the fastest expiring key-value pairs in all expiration time tables, but only a few randomly selected key-value pairs.

Summary

When each redis service client executes a command, it will detect whether the memory used is excessive. If it exceeds the limit, the data will be eliminated.

// 执行命令
int processCommand(redisClient *c) {
......
// 内存超额
/* Handle the maxmemory directive.
*
* First we try to free some memory if possible (if there are volatile
* keys in the dataset). If there are not the only thing we can do
* is returning an error. */
if (server.maxmemory) {
int retval = freeMemoryIfNeeded();
if ((c->cmd->flags & REDIS_CMD_DENYOOM) && retval == REDIS_ERR) {
flagTransaction(c);
addReply(c, shared.oomerr);
return REDIS_OK;
}
}
......
}
// 如果需要,是否一些内存
int freeMemoryIfNeeded(void) {
size_t mem_used, mem_tofree, mem_freed;
int slaves = listLength(server.slaves);
// redis 从机回复空间和 AOF 内存大小不计算入 redis 内存大小
/* Remove the size of slaves output buffers and AOF buffer from the
* count of used memory. */
mem_used = zmalloc_used_memory();
// 从机回复空间大小
if (slaves) {
listIter li;
listNode *ln;
listRewind(server.slaves,&li);
while((ln = listNext(&li))) {
redisClient *slave = listNodeValue(ln);
unsigned long obuf_bytes = getClientOutputBufferMemoryUsage(slave);
if (obuf_bytes > mem_used)
mem_used = 0;
else
mem_used -= obuf_bytes;
}
}
// server.aof_buf && server.aof_rewrite_buf_blocks
if (server.aof_state != REDIS_AOF_OFF) {
mem_used -= sdslen(server.aof_buf);
mem_used -= aofRewriteBufferSize();
}
// 内存是否超过设置大小
/* Check if we are over the memory limit. */
if (mem_used <= server.maxmemory) return REDIS_OK;
// redis 中可以设置内存超额策略
if (server.maxmemory_policy == REDIS_MAXMEMORY_NO_EVICTION)
return REDIS_ERR; /* We need to free memory, but policy forbids. */
/* Compute how much memory we need to free. */
mem_tofree = mem_used - server.maxmemory;
mem_freed = 0;
while (mem_freed < mem_tofree) {
int j, k, keys_freed = 0;
// 遍历所有数据集
for (j = 0; j < server.dbnum; j++) {
long bestval = 0; /* just to prevent warning */
sds bestkey = NULL;
struct dictEntry *de;
redisDb *db = server.db+j;
dict *dict;
// 不同的策略,选择的数据集不一样
if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM
{
dict = server.db[j].dict;
} else {
dict = server.db[j].expires;
}
// 数据集为空,继续下一个数据集
if (dictSize(dict) == 0) continue;
// 随机淘汰随机策略:随机挑选
/* volatile-random and allkeys-random policy */
if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM ||
server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM)
{
de = dictGetRandomKey(dict);
bestkey = dictGetKey(de);
}
// LRU 策略:挑选最近最少使用的数据
/* volatile-lru and allkeys-lru policy */
else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
{
// server.maxmemory_samples 为随机挑选键值对次数
// 随机挑选 server.maxmemory_samples个键值对,驱逐最近最少使用的数据
for (k = 0; k < server.maxmemory_samples; k++) {
sds thiskey;
long thisval;
robj *o;
// 随机挑选键值对
de = dictGetRandomKey(dict); 
// 获取键
thiskey = dictGetKey(de); 
/* When policy is volatile-lru we need an additional lookup
* to locate the real key, as dict is set to db->expires. */
if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
de = dictFind(db->dict, thiskey);
o = dictGetVal(de); 
// 计算数据的空闲时间
thisval = estimateObjectIdleTime(o);
// 当前键值空闲时间更长,则记录
/* Higher idle time is better candidate for deletion */
if (bestkey == NULL || thisval > bestval) {
bestkey = thiskey;
bestval = thisval;
}
}
} 
// TTL 策略:挑选将要过期的数据
/* volatile-ttl */
else if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_TTL) {
// server.maxmemory_samples 为随机挑选键值对次数
// 随机挑选 server.maxmemory_samples个键值对,驱逐最快要过期的数据
for (k = 0; k < server.maxmemory_samples; k++) {
sds thiskey;
long thisval;
de = dictGetRandomKey(dict);
thiskey = dictGetKey(de);
thisval = (long) dictGetVal(de);
/* Expire sooner (minor expire unix timestamp) is better
* candidate for deletion */
if (bestkey == NULL || thisval < bestval) {
bestkey = thiskey;
bestval = thisval;
}
}
}
// 删除选定的键值对
/* Finally remove the selected key. */
if (bestkey) {
long long delta;
robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
// 发布数据更新消息,主要是 AOF 持久化和从机
propagateExpire(db,keyobj);
// 注意, propagateExpire() 可能会导致内存的分配, propagateExpire()
提前执行就是因为 redis 只计算 dbDelete() 释放的内存大小。倘若同时计算 dbDelete() 释放的内存
和 propagateExpire() 分配空间的大小,与此同时假设分配空间大于释放空间,就有可能永远退不出这个循环。
// 下面的代码会同时计算 dbDelete() 释放的内存和 propagateExpire() 分配空间的大小:
// propagateExpire(db,keyobj);
// delta = (long long) zmalloc_used_memory();
// dbDelete(db,keyobj);
// delta -= (long long) zmalloc_used_memory();
// mem_freed += delta;
/////////////////////////////////////////
/* We compute the amount of memory freed by dbDelete() alone.
* It is possible that actually the memory needed to propagate
* the DEL in AOF and replication link is greater than the one
* we are freeing removing the key, but we can&#39;t account for
* that otherwise we would never exit the loop.
*
* AOF and Output buffer memory will be freed eventually so
* we only care about memory used by the key space. */
// 只计算 dbDelete() 释放内存的大小
delta = (long long) zmalloc_used_memory();
dbDelete(db,keyobj);
delta -= (long long) zmalloc_used_memory();
mem_freed += delta;
server.stat_evictedkeys++;
// 将数据的删除通知所有的订阅客户端
notifyKeyspaceEvent(REDIS_NOTIFY_EVICTED, "evicted",
keyobj, db->id);
decrRefCount(keyobj);
keys_freed++; 
// 将从机回复空间中的数据及时发送给从机
/* When the memory to free starts to be big enough, we may
* start spending so much time here that is impossible to
* deliver data to the slaves fast enough, so we force the
* transmission here inside the loop. */
if (slaves) flushSlavesOutputBuffers();
}
} 
// 未能释放空间,且此时 redis 使用的内存大小依旧超额,失败返回
if (!keys_freed) return REDIS_ERR; /* nothing to free... */
}
return REDIS_OK;
}
Copy after login

Applicable scenarios

Let’s take a look at the applicable scenarios of several strategies:

1. allkeys-lru: If our application’s access to the cache conforms to a power law distribution ( That is, there are relatively hot data), or we are not very clear about the cache access distribution of our application, we can choose the allkeys-lru strategy.

2. allkeys-random: If our application has equal access probability to cache keys, we can use this strategy.

3. volatile-ttl: This strategy allows us to prompt Redis which keys are more suitable for eviction.

In addition, the volatile-lru strategy and volatile-random strategy are suitable when we apply one Redis instance to both cache and persistent storage. However, we can also achieve the same result by using two Redis instances. effect, it is worth mentioning that setting the key expiration time will actually consume more memory, so we recommend using the allkeys-lru strategy to use memory more efficiently.

For more redis knowledge, please pay attention to the redis introductory tutorial column.

The above is the detailed content of Detailed explanation of redis data elimination strategy. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
1 months ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Solution to 0x80242008 error when installing Windows 11 10.0.22000.100 Solution to 0x80242008 error when installing Windows 11 10.0.22000.100 May 08, 2024 pm 03:50 PM

1. Start the [Start] menu, enter [cmd], right-click [Command Prompt], and select Run as [Administrator]. 2. Enter the following commands in sequence (copy and paste carefully): SCconfigwuauservstart=auto, press Enter SCconfigbitsstart=auto, press Enter SCconfigcryptsvcstart=auto, press Enter SCconfigtrustedinstallerstart=auto, press Enter SCconfigwuauservtype=share, press Enter netstopwuauserv , press enter netstopcryptS

Analyze PHP function bottlenecks and improve execution efficiency Analyze PHP function bottlenecks and improve execution efficiency Apr 23, 2024 pm 03:42 PM

PHP function bottlenecks lead to low performance, which can be solved through the following steps: locate the bottleneck function and use performance analysis tools. Caching results to reduce recalculations. Process tasks in parallel to improve execution efficiency. Optimize string concatenation, use built-in functions instead. Use built-in functions instead of custom functions.

Golang API caching strategy and optimization Golang API caching strategy and optimization May 07, 2024 pm 02:12 PM

The caching strategy in GolangAPI can improve performance and reduce server load. Commonly used strategies are: LRU, LFU, FIFO and TTL. Optimization techniques include selecting appropriate cache storage, hierarchical caching, invalidation management, and monitoring and tuning. In the practical case, the LRU cache is used to optimize the API for obtaining user information from the database. The data can be quickly retrieved from the cache. Otherwise, the cache can be updated after obtaining it from the database.

Caching mechanism and application practice in PHP development Caching mechanism and application practice in PHP development May 09, 2024 pm 01:30 PM

In PHP development, the caching mechanism improves performance by temporarily storing frequently accessed data in memory or disk, thereby reducing the number of database accesses. Cache types mainly include memory, file and database cache. Caching can be implemented in PHP using built-in functions or third-party libraries, such as cache_get() and Memcache. Common practical applications include caching database query results to optimize query performance and caching page output to speed up rendering. The caching mechanism effectively improves website response speed, enhances user experience and reduces server load.

How to use Redis cache in PHP array pagination? How to use Redis cache in PHP array pagination? May 01, 2024 am 10:48 AM

Using Redis cache can greatly optimize the performance of PHP array paging. This can be achieved through the following steps: Install the Redis client. Connect to the Redis server. Create cache data and store each page of data into a Redis hash with the key "page:{page_number}". Get data from cache and avoid expensive operations on large arrays.

How to upgrade Win11 English 21996 to Simplified Chinese 22000_How to upgrade Win11 English 21996 to Simplified Chinese 22000 How to upgrade Win11 English 21996 to Simplified Chinese 22000_How to upgrade Win11 English 21996 to Simplified Chinese 22000 May 08, 2024 pm 05:10 PM

First you need to set the system language to Simplified Chinese display and restart. Of course, if you have changed the display language to Simplified Chinese before, you can just skip this step. Next, start operating the registry, regedit.exe, directly navigate to HKEY_LOCAL_MACHINESYSTEMCurrentControlSetControlNlsLanguage in the left navigation bar or the upper address bar, and then modify the InstallLanguage key value and Default key value to 0804 (if you want to change it to English en-us, you need First set the system display language to en-us, restart the system and then change everything to 0409) You must restart the system at this point.

Can navicat connect to redis? Can navicat connect to redis? Apr 23, 2024 pm 05:12 PM

Yes, Navicat can connect to Redis, which allows users to manage keys, view values, execute commands, monitor activity, and diagnose problems. To connect to Redis, select the "Redis" connection type in Navicat and enter the server details.

How to find the update file downloaded by Win11_Share the location of the update file downloaded by Win11 How to find the update file downloaded by Win11_Share the location of the update file downloaded by Win11 May 08, 2024 am 10:34 AM

1. First, double-click the [This PC] icon on the desktop to open it. 2. Then double-click the left mouse button to enter [C drive]. System files will generally be automatically stored in C drive. 3. Then find the [windows] folder in the C drive and double-click to enter. 4. After entering the [windows] folder, find the [SoftwareDistribution] folder. 5. After entering, find the [download] folder, which contains all win11 download and update files. 6. If we want to delete these files, just delete them directly in this folder.

See all articles