深入剖析 redis 数据淘汰策略

2013-10-17  来源:本站原创  分类:编程  人气:4 

概述

在 redis 中,允许用户设置最大使用内存大小 server.maxmemory,在内存限定的情况下是很有用的。譬如,在一台 8G 机子上部署了 4 个 redis 服务点,每一个服务点分配 1.5G 的内存大小,减少内存紧张的情况,由此获取更为稳健的服务。

redis 内存数据集大小上升到一定大小的时候,就会施行数据淘汰策略。redis 提供 6种数据淘汰策略:

  1. volatile-lru:从已设置过期时间的数据集(server.db[i].expires)中挑选最近最少使用的数据淘汰
  2. volatile-ttl:从已设置过期时间的数据集(server.db[i].expires)中挑选将要过期的数据淘汰
  3. volatile-random:从已设置过期时间的数据集(server.db[i].expires)中任意选择数据淘汰
  4. allkeys-lru:从数据集(server.db[i].dict)中挑选最近最少使用的数据淘汰
  5. allkeys-random:从数据集(server.db[i].dict)中任意选择数据淘汰
  6. no-enviction(驱逐):禁止驱逐数据

redis 确定驱逐某个键值对后,会删除这个数据并,并将这个数据变更消息发布到本地(AOF 持久化)和从机(主从连接)。

LRU 数据淘汰机制

在服务器配置中保存了 lru 计数器 server.lrulock,会定时(redis 定时程序 serverCorn())更新,server.lrulock 的值是根据 server.unixtime 计算出来的。

另外,从 struct redisObject 中可以发现,每一个 redis 对象都会设置相应的 lru。可以想象的是,每一次访问数据的时候,会更新 redisObject.lru。

LRU 数据淘汰机制是这样的:在数据集中随机挑选几个键值对,取出其中 lru 最大的键值对淘汰。所以,你会发现,redis 并不是保证取得所有数据集中最近最少使用(LRU)的键值对,而只是随机挑选的几个键值对中的。

Code Sample

01

02

03

04

05

06

07

08

09

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53


// 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'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;

}

TTL 数据淘汰机制

redis 数据集数据结构中保存了键值对过期时间的表,即 redisDb.expires。和 LRU 数据淘汰机制类似,TTL 数据淘汰机制是这样的:从过期时间的表中随机挑选几个键值对,取出其中 ttl 最大的键值对淘汰。同样你会发现,redis 并不是保证取得所有过期时间的表中最快过期的键值对,而只是随机挑选的几个键值对中的。

总结

redis 每服务客户端执行一个命令的时候,会检测使用的内存是否超额。如果超额,即进行数据淘汰。

Code Sample

001

002

003

004

005

006

007

008

009

010

011

012

013

014

015

016

017

018

019

020

021

022

023

024

025

026

027

028

029

030

031

032

033

034

035

036

037

038

039

040

041

042

043

044

045

046

047

048

049

050

051

052

053

054

055

056

057

058

059

060

061

062

063

064

065

066

067

068

069

070

071

072

073

074

075

076

077

078

079

080

081

082

083

084

085

086

087

088

089

090

091

092

093

094

095

096

097

098

099

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207


// 执行命令

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'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;

}

相关文章
  • 深入剖析 redis 数据淘汰策略 2013-10-17

    概述 在 redis 中,允许用户设置最大使用内存大小 server.maxmemory,在内存限定的情况下是很有用的.譬如,在一台 8G 机子上部署了 4 个 redis 服务点,每一个服务点分配 1.5G 的内存大小,减少内存紧张的情况,由此获取更为稳健的服务. redis 内存数据集大小上升到一定大小的时候,就会施行数据淘汰策略.redis 提供 6种数据淘汰策略: volatile-lru:从已设置过期时间的数据集(server.db[i].expires)中挑选最近最少使用的数据淘汰

  • 深入剖析 redis RDB 持久化策略 2014-09-13

    简介 redis 持久化 RDB.AOF redis 提供两种持久化方式:RDB 和 AOF.redis 允许两者结合,也允许两者同时关闭. RDB 可以定时备份内存中的数据集.服务器启动的时候,可以从 RDB 文件中回复数据集. AOF 可以记录服务器的所有写操作.在服务器重新启动的时候,会把所有的写操作重新执行一遍,从而实现数据备份.当写操作集过大(比原有的数据集还大),redis 会重写写操作集. 本篇主要讲的是 RDB 持久化,了解 RDB 的数据保存结构和运作机制.redis 主要在

  • 一个简单的 Cache 淘汰策略 2013-11-19

    本文是<轻量级 Java Web 框架架构设计>的系列博文. Smart 框架一切都围绕着轻量.简单.实用的方向在努力,对于 Cache 插件也不例外.最近忙着拉项目,所以投入在 Smart 的精力就不多了.前几天有朋友想让我写一个 Cache 淘汰策略,当时脑海里有几个算法,例如: LRU(Least Recently Used):最近最少使用算法,淘汰"最后访问时间"较早的. LFU(Least Frequently Used):最不经常使用算法,淘汰"访问次

  • Redis数据存储解决方案 2014-08-01

    1.背景 1.1 Redis简介 官方网站:http://redis.io/,Redis是REmote DIctionary Server的缩写. Redis是一个开源的使用ANSI C语言编写.支持网络.可基于内存亦可持久化的日志型.Key-Value数据库,并提供多种语言的API.从2010年3月15日起,Redis的开发工作由VMware主持.它跟 memcached 类似,不过数据可以持久化,而且支持的数据类型很丰富.它在保持键值数据库简单快捷特点的同时,又吸收了部分关系数据库的优点.从

  • Redis数据持久化 2015-04-15

    总的来说有两种持久化方案:RDB和AOF RDB方式按照一定的时间间隔对数据集创建基于时间点的快照. AOF方式记录Server收到的写操作到日志文件,在Server重启时通过回放这些写操作来重建数据集.该方式类似于MySQL中基于语句格式的binlog.当日志变大时Redis可在后台重写日志. 若仅期望数据在Server运行期间存在则可禁用两种持久化方案.在同一Redis实例中同时开启AOF和RDB方式的数据持久化方案也是可以的.该情况下Redis重启时AOF文件将用于重建原始数据集,因为叫R

  • 使用PHP导出Redis数据到另一个Redis中的代码 2014-10-14

    这篇文章主要介绍了使用PHP导出Redis数据到另一个Redis中的方法,需要的朋友可以参考下 从某个 Redis db 导出数据到另一个 Redis db 的PHP脚本: $from = '127.0.0.1:6200/6'; $to = '127.0.0.1:6200/8'; $from_redis = redis_init($from); $to_redis = redis_init($to); $keys = $from_redis->keys('*'); $count = 0; $to

  • 深入剖析Redis RDB持久化机制 2013-12-18

    本文来自@凡趣科技 pesiwang同学的投稿分享,对Redis RDB文件持久化的内部实现进行了源码分析. 本文分析源码基于 Redis 2.4.7 stable 版本.下面是其文章原文: rdb是redis保存内存数据到磁盘数据的其中一种方式(另一种是AOF).Rdb的主要原理就是在某个时间点把内存中的所有数据的快照保存一份到磁盘上.在条件达到时通过fork一个子进程把内存中的数据写到一个临时文件中来实现保存数据快照.在所有数据写完后再把这个临时文件用原子函数rename(2)重命名为目标r

  • Redis数据分片以及扩容 2013-11-21

    投稿介绍:xiaotianqio,资深linux菜鸟程序员,搜索系统砖家,曾混迹于百度的互联网吊丝.刚开始接触Redis,大言不惭,聊卿一读. 场景 一开始数据比较少,一台服务器的内存就足够,因此一个Redis 就能满足需求,但是随着业务发展,数据量变大,可能需要在多台服务器上运行多个Redis,所以需要将已有的数据进行分片(避免数据丢失),不同的片交给不同的Redis 服务.如果在一开始就考虑到这个问题,在只有一个Redis时,也将数据存放在Redis的不同db中,当增加Redis时,将dum

  • Redis 数据同步 redis-port 2015-04-19

    redis-port 网站 : https://github.com/wandoulabs/redis-port redis-port 是一个 Redis 工具,通过解析 rdb 文件,实现 Redis 主节点和从节点的数据同步. 示例: $ cat dump.rdb | ./redis-port decode 2>/dev/null {"db":0,"type":"string","expireat":0,"

  • 深入剖析redis事务机制 2013-11-07

    redis 事务简述 MULTI,EXEC,DISCARD,WATCH 四个命令是 redis 事务的四个基础命令.其中: MULTI,告诉 redis 服务器开启一个事务.注意,只是开启,而不是执行 EXEC,告诉 redis 开始执行事务 DISCARD,告诉 redis 取消事务 WATCH,监视某一个键值对,它的作用是在事务执行之前如果监视的键值被修改,事务会被取消. 在介绍 redis 事务之前,先来展开 redis 命令队列的内部实现. redis 命令队列 redis 允许一个客户

  • 标准STP中的集成数据验证策略 2014-04-30

    Ruth Rose是一名数据验证专家.她擅长预测模型领域的数据质量和数据分析.她曾在耶路撒冷的希伯来大学学过数学,并在各种创业公司和微软以色列研发中心工作过.目前,她在PayPal/eBay风险部担任分析验证主管. 在一个数据不断增长的世界,软件测试涉及不同的数据验证程序,这些程序是传统质量保证方法的一个组成部分.本文旨在为非数据人员提供数据验证工具,同时也为回归测试和功能测试提供更多自动且迅速的工具和测试策略. 本文中,我将详细介绍数据验证的两种方法:自下而上法和自上而下法.这两种方法在不同的

  • 在数据库组件中用业务规则剖析挑选数据 2012-06-08

    直接去 techsmith 吧 http://www.screencast.com/t/6o6iWQac

  • 解决Redis持久化之大数据服务暂停问题 2012-09-08

    Redis持久化是有两种方式:RDB和AOF 对这两种方式的官方文档的翻译请看: http://latteye.com/2011/11/redis-persistence.html RDB就是快照存储,比如"每1个小时对redis进行快照存储".那么, save这个参数就应该设置save 3600 1000 //前一次快照3600秒后,当有超过1000个key被改动的时候就进行一次快照更新RDB快照产生dump.rdb文件,当每到快照时间,更新文件. AOF是存储所有的写操作,分两个步

  • 利用管道完成数据从MySQL到Redis的高效迁移 2013-12-11

    Mysql到Redis数据的迁移,可以使用"管道输出"的方式把mysql命令行产生的迁移数据内容转换为Redis可识别的格式直接传递给redis-cli,redis-cli命令行工具有一个批量插入模式,是专门为批量执行命令设计的.关键就是把Mysql查询的内容格式化成redis-cli可用的数据格式. 准备在每行数据中执行的redis命令如下: HSET stock [id] [CONCAT(t.sku_code, ':', t.tax_cost_price, ':', t.wh_na

  • HDFS集中式的缓存管理原理与代码剖析 2015-04-08

    Hadoop 2.3.0已经发布了,其中最大的亮点就是集中式的缓存管理(HDFS centralized cache management).这个功能对于提升Hadoop系统和上层应用的执行效率与实时性有很大帮助,本文从原理.架构和代码剖析三个角度来探讨这一功能. 主要解决了哪些问题 用户可以根据自己的逻辑指定一些经常被使用的数据或者高优先级任务对应的数据,让他们常驻内存而不被淘汰到磁盘.例如在Hive或Impala构建的数据仓库应用中fact表会频繁地与其他表做JOIN,显然应该让fact常驻

  • redis 3.0的集群部署 2015-05-04

    redis 3.0的集群部署 分类: redis2014-05-15 11:53 10832人阅读 评论(2) 收藏 举报 redis 目录(?)[+] 文章转载自: 转载请注明出处:http://hot66hot.iteye.com/admin/blogs/2050676 最近研究redis-cluster,正好搭建了一个环境,遇到了很多坑,系统的总结下,等到redis3 release出来后,换掉memCache 集群. 一:关于redis cluster 1:redis cluster的现

  • 解密Redis持久化 2013-10-11

    本文内容来源于Redis作者博文,Redis作者说,他看到的所有针对Redis的讨论中,对Redis持久化的误解是最大的,于是他写了一篇长文来对Redis的持久化进行了系统性的论述.文章非常长,也很值得一看,NoSQLFan将主要内容简述成本文. 什么是持久化,简单来讲就是将数据放到断电后数据不会丢失的设备中.也就是我们通常理解的硬盘上. 写操作的流程 首先我们来看一下数据库在进行写操作时到底做了哪些事,主要有下面五个过程. 客户端向服务端发送写操作(数据在客户端的内存中) 数据库服务端接收到写

  • 谈谈陌陌争霸在数据库方面踩过的坑( Redis 篇) 2014-03-23

    注:陌陌争霸的数据库部分我没有参与具体设计,只是参与了一些讨论和提出一些意见.在出现问题的时候,也都是由肥龙.晓靖.Aply 同学判断研究解决的.所以我对 Redis 的判断大多也从他们的讨论中听来,加上自己的一些猜测,并没有去仔细阅读 Redis 文档和阅读 Redis 代码.虽然我们最终都解决了问题,但本文中说描述的技术细节还是很有可能与事实相悖,请阅读的同学自行甄别. 在陌陌争霸之前,我们并没有大规模使用过 Redis .只是直觉上感觉 Redis 很适合我们的架构:我们这个游戏不依赖数据

  • 使用大数据时,别忘了关注Linux内存管理器 2014-05-16

    声明:我们常常以为,一旦我们(的代码)出了什么状况,那肯定是操作系统在作祟,而在99%的情况下,结果都会是别的原因.因此我们会谨慎地作出是操作系统导致了某个问题这样的假设,除非你遇到了与下面的例子类似的情况. 一切从我们的一个客户报告了他们的CitusDB集群的性能问题开始.这个客户设计的集群使得他们的工作数据集合可以放进内存,但是他们的查询次数显示他们的查询已经需要访问磁盘.这自然会导致查询效率下降10倍到100倍. 我们开始着手研究这个问题,首先检查CitusDB的查询分发机制,然后再检查机

  • Redis错误配置详解 2015-02-20

    笔者在运行了上千个Redis数据库实例后,不仅发现了使用Redis时遇到的一些令人头疼的问题,更是探索到了解决这些问题的简单解决方案,其中包括复制缓冲区限制.复制超时和客户端缓冲区等一系列容易遇到的难题. 以下为译文: Redis提供了许多提高和维护高效内存数据库使用的工具.在无需额外配置应用层的前提下,Redis独特的数据类型.指令和命令调优就可以满足应用的需求,但是错误的配置,更确切的说那些机外设备可能导致操作麻烦和性能问题.虽然导致了一些令人头疼的问题,但是解决方案是存在的,而且解决方案可