淘宝：
http://www.searchtb.com/2011/05/redis-storage.html
1 Redis 内存存储结构
本文是基于 Redis-v2.2.4 版本进行分析.
1.1 Redis 内存存储总体结构
Redis 是支持多key-value数据库(表)的,并用 RedisDb 来表示一个key-value数据库(表). redisServer 中有一个 redisDb *db; 成员变量, RedisServer 在初始化时,会根据配置文件的 db 数量来创建一个 redisDb 数组. 客户端在连接后,通过 SELECT 指令来选择一个 reidsDb,如果不指定,则缺省是redisDb数组的第1个(即下标是 0 ) redisDb. 一个客户端在选择 redisDb 后,其后续操作都是在此 redisDb 上进行的. 下面会详细介绍一下 redisDb 的内存结构.
redis 的内存存储结构示意图
redisDb 的定义:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
typedef
struct
redisDb
{
dict *dict;
dict *expires;
dict *blocking_keys;
dict *io_keys;
dict *watched_keys;
int
id;
} redisDb;
struct
|
redisDb 中 ,dict 成员是与实际存储数据相关的. dict 的定义如下:
|
1
2
3
4
5
6
7
8
9
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
54
55
56
57
58
59
60
61
62
63
|
typedef
struct
dictEntry
{
void
*key;
void
*val;
struct
dictEntry *next;
} dictEntry;
typedef
struct
dictType
{
unsigned
int
(*hashFunction)(
const
void
*key);
void
*(*keyDup)(
void
*privdata,
const
void
*key);
void
*(*valDup)(
void
*privdata,
const
void
*obj);
int
(*keyCompare)(
void
*privdata,
const
void
*key1,
const
void
*key2);
void
(*keyDestructor)(
void
*privdata,
void
*key);
void
(*valDestructor)(
void
*privdata,
void
*obj);
} dictType;
typedef
struct
dictht
{
dictEntry **table;
unsigned
long
size;
unsigned
long
sizemask;
unsigned
long
used;
} dictht;
typedef
struct
dict
{
dictType *type;
void
*privdata;
dictht ht[2];
int
rehashidx;
int
iterators;
} dict;
|
dict 是主要是由 struct dictht 的 哈唏表构成的, 之所以定义成长度为2的( dictht ht[2] ) 哈唏表数组,是因为 redis 采用渐进的 rehash,即当需要 rehash 时,每次像 hset,hget 等操作前,先执行N 步 rehash. 这样就把原来一次性的 rehash过程拆散到进行, 防止一次性 rehash 期间 redis 服务能力大幅下降. 这种渐进的 rehash 需要一个额外的 struct dictht 结构来保存.
struct dictht 主要是由一个 struct dictEntry 指针数组组成的, hash 表的冲突是通过链表法来解决的.
struct dictEntry 中的 key 指针指向用 sds 类型表示的 key 字符串, val 指针指向一个 struct redisObject 结构体, 其定义如下:
|
1
2
3
4
5
6
7
8
9
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
typedef
struct
redisObject
{
unsigned type:4;
unsigned storage:2;
unsigned encoding:4;
unsigned lru:22;
int
refcount;
void
*ptr;
} robj;
#define REDIS_STRING 0
#define REDIS_LIST 1
#define REDIS_SET 2
#define REDIS_ZSET 3
#define REDIS_HASH 4
#define REDIS_VMPOINTER 8
#define REDIS_ENCODING_RAW 0 /* Raw representation */
#define REDIS_ENCODING_INT 1 /* Encoded as integer */
#define REDIS_ENCODING_HT 2 /* Encoded as hash table */
#define REDIS_ENCODING_ZIPMAP 3 /* Encoded as zipmap */
#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define REDIS_ENCODING_INTSET 6 /* Encoded as intset */
#define REDIS_ENCODING_SKIPLIST 7 /* Encoded as skiplist */
|
1.2 Dict 结构
Dict 结构在<1.1Redis 内存存储结构>; 已经描述过了,这里不再赘述.
1.3 zipmap 结构
如果redisObject的type 成员值是 REDIS_HASH 类型的,则当该hash 的 entry 小于配置值: hash-max-zipmap-entries 或者value字符串的长度小于 hash-max-zipmap-value, 则可以编码成 REDIS_ENCODING_ZIPMAP 类型存储,以节约内存. 否则采用 Dict 来存储.
zipmap 其实质是用一个字符串数组来依次保存key和value,查询时是依次遍列每个 key-value 对,直到查到为止. 其结构示意图如下:
为了节约内存,这里使用了一些小技巧来保存 key 和 value 的长度. 如果 key 或 value 的长度小于ZIPMAP_BIGLEN(254),则用一个字节来表示,如果大于ZIPMAP_BIGLEN(254),则用5个字节保存,第一个字节为保存ZIPMAP_BIGLEN(254),后面4个字节保存 key或value 的长度.
- 初始化时只有2个字节,第1个字节表示 zipmap 保存的 key-value 对的个数(如果key-value 对的个数超过 254,则一直用254来表示, zipmap 中实际保存的 key-value 对个数可以通过 zipmapLen() 函数计算得到).
-
hset(nick,wuzhu) 后,
- 第1个字节保存key-value 对(即 zipmap 的entry 数量)的数量1
- 第2个字节保存key_len 值 4
- 第3~6 保存 key “nick”
- 第 7 字节保存 value_len 值 5
- 第 8 字节保存空闭的字节数 0 (当 该 key 的值被重置时,其新值的长度与旧值的长度不一定相等,如果新值长度比旧值的长度大,则 realloc 扩大内存; 如果新值长度比旧值的长度小,且相差大于 4 bytes ,则 realloc 缩小内存,如果相差小于 4,则将值往前移,并用 empty_len 保存空闲的byte 数)
- 第 9~13字节保存 value 值 “wuzhu”
- hset(age,30)
插入 key-value 对 (“age”,30)
- hset(nick,tide)
插入 key-value 对 (“nick”,”tide”), 后可以看到 empty_len 为1 ,
1.4 ziplist 结构
如果redisObject的type 成员值是 REDIS_LIST 类型的,则当该list 的 elem数小于配置值: hash-max-ziplist-entries 或者elem_value字符串的长度小于 hash-max-ziplist-value, 则可以编码成 REDIS_ENCODING_ZIPLIST 类型存储,以节约内存. 否则采用 Dict 来存储.
ziplist 其实质是用一个字符串数组形式的双向链表. 其结构示意图如下:
- ziplist header由3个字段组成:
- ziplist_bytes: 用一个uint32_t 来保存, 构成 ziplist 的字符串数组的总长度,包括 ziplist header,
- ziplist_tail_offset: 用一个uint32_t 来保存,记录 ziplist 的尾部偏移位置.
- ziplist_length: 用一个 uint16_t 来保存,记录 ziplist 中 elem 的个数
- ziplist node 也由 3 部分组成:
- prevrawlen: 保存上一个 ziplist node 的占用的字节数,包括: 保存prevarwlen,currawlen 的字节数和elem value 的字节数.
- currawlen&encoding: 当前elem value 的raw 形式存款所需的字节数及在ziplist 中保存时的编码方式(例如,值可以转换成整数,如示意图中的”1024”, raw_len 是 4 字节,但在 ziplist 保存时转换成 uint16_t 来保存,占2 个字节).
- (编码后的)value
可以通过 prevrawlen 和 currawlen&encoding 来遍列 ziplist.
ziplist 还能到一些小技巧来节约内存.
- len 的存储: 如果 len 小于 ZIP_BIGLEN(254),则用一个字节来保存; 否则需要 5 个字节来保存,第 1 个字节存 ZIP_BIGLEN,作为标识符.
- value 的存储: 如果 value 是数字类型的,则根据其值的范围转换成 ZIP_INT_16B, ZIP_INT_32B或ZIP_INT_64B 来保存,否则用 raw 形式保存.
1.5 adlist 结构
|
1
2
3
4
5
6
7
8
9
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
|
typedef
struct
listNode
{
struct
listNode *prev;
struct
listNode *next;
void
*value;
} listNode;
typedef
struct
listIter
{
listNode *next;
int
direction;
} listIter;
typedef
struct
list
{
listNode *head;
listNode *tail;
void
*(*dup)(
void
*ptr);
void
(*
free
)(
void
*ptr);
int
(*match)(
void
*ptr,
void
*key);
unsigned
int
len;
} list;
|
常见的双向链表,不作分析.
1.6 intset 结构
intset 是用一个有序的整数数组来实现集合(set). struct intset 的定义如下:
|
1
2
3
4
5
6
7
8
9
10
11
|
typedef
struct
intset
{
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;
|
- encoding: 来标识数组是 int16_t 类型, int32_t 类型还是 int64_t 类型的数组. 至于怎么先择是那种类型的数组,是根据其保存的值的取值范围来决定的,初始化时是 int16_t, 根据 set 中的最大值在 [INT16_MIN, INT16_MAX] , [INT32_MIN, INT32_MAX], [INT64_MIN, INT64_MAX]的那个取值范围来动态确定整个数组的类型. 例如set一开始是 int16_t 类型,当一个取值范围在 [INT32_MIN, INT32_MAX]的值加入到 set 时,则将保存 set 的数组升级成 int32_t 的数组.
- length: 表示 set 中值的个数
- contents: 指向整数数组的指针
1.7 zset 结构
首先，介绍一下 skip list 的概念，然后再分析 zset 的实现.
1.7.1 Skip List 介绍
1.7.1.1 有序链表
1) Searching a key in a Sorted linked list
|
1
2
3
4
5
6
7
|
cell *p =head ;
while
(p->next->key < x ) p=p->next ;
return
p ;
|
Note: we return the element proceeding either the element containing x
, or the smallest element with a key larger than x
(if x
does not exists)
2) inserting a key into a Sorted linked list
|
1
2
3
4
5
6
7
8
9
10
11
|
p=find(35);
CELL *p1 = (CELL *)
malloc
(
sizeof
(CELL));
p1->key=35;
p1->next = p->next ;
p->next = p1 ;
|
3) deleteing a key from a sorted list
|
1
2
3
4
5
6
7
8
9
|
p=find(37);
CELL *p1 =p->next;
p->next = p1->next ;
free
(p1);
|
1.7.1.2 SkipList(跳跃表)定义
SKIP LIST : A data structure for maintaing a set of keys in a sorted order.
Consists of several levels.
All keys appear in level 1
Each level is a sorted list.
If key x
appears in level i
, then it also appears in all levels below i
An element in level i
points (via down pointer) to the element with the same key in the level below.
In each level the keys and appear. (In our implementation, INT_MIN and INT_MAX
Top points to the smallest element in the highest level.
1.7.1.3 SkipList(跳跃表)操作
1) An empty SkipList
2) Finding an element with key x
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
p=top
While(1)
{
while
(p->next->key < x ) p=p->next;
If (p->down == NULL )
return
p->next
p=p->down ;
}
|
Observe that we return x
, if exists, or succ(x)
if x
is not in the SkipList
3) Inserting new element X
Determine k
the number of levels in which x
participates (explained later)
Do find(x), and insert x to the appropriate places in the lowest k
levels. (after the elements at which the search path turns down or terminates)
Example – inserting 119. k
=2
If k
is larger than the current number of levels, add new levels (and update top)
Example – inser(119) when k=4
Determining k
k – the number of levels at which an element x participate.
Use a random function OurRnd() — returns 1 or 0 (True/False) with equal probability.
k=1 ;
While( OurRnd() ) k++ ;
Deleteing a key x
Find x in all the levels it participates, and delete it using the standard ‘delete from a linked list’ method.
If one or more of the upper levels are empty, remove them (and update top)
Facts about SkipList
The expected number of levels is O( log n
)
(here n
is the numer of elements)
The expected time for insert/delete/find is O( log n
)
The expected size (number of cells) is O(n
)
1.7.2 redis SkipList 实现
/* ZSETs use a specialized version of Skiplists */
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
lin
分享到：
|
相关推荐
### Redis内存存储结构分析 #### 一、Redis内存存储总体结构概述 Redis是一种高性能的键值存储系统，它将所有数据存储在内存中，从而实现了非常快的数据读写速度。然而，这种设计也有其局限性，例如对于拥有大量...
3. **内存分析**：了解 Redis 数据结构（如 String、Hash、List、Set 和 Sorted Set）的内存占用情况，以及如何通过 Redis 命令获取相关统计信息。 4. **数据收集和排序**：收集每个 Key 的内存占用数据，根据大小...
总结来说，通过Key前缀分析Redis内存占用并导出结果到CSV文件，是一个涉及Redis内存管理、PHP编程、数据遍历、排序算法和文件操作等多个IT领域的综合实践。了解并掌握这些知识点，对于优化Redis的内存使用，提升系统...
在Redis内存分布分析中，涉及到的核心知识点包括Redis的数据结构存储、数据类型操作、内存管理机制以及命令执行过程解析。 首先，我们来了解Redis的数据结构存储。Redis作为一个高性能的键值存储系统，其内部通过...
总的来说，cpp-RCT是一个强大的Redis内存结构分析工具，它通过解析RDB文件，提供了丰富的查询和监控功能，从而帮助用户优化Redis的使用，提升系统的整体性能。通过深入学习和使用cpp-RCT，你可以更有效地管理和维护...
通过深入分析和理解Redis的工作原理，以及对业务需求的充分考虑，我们可以有效地避免和解决Redis内存占用飙升的问题，确保系统的稳定和高效运行。对于大型互联网公司如美团而言，良好的数据库管理是业务持续发展的...
总结，Redis流量分析涉及到多个层面，包括数据结构的选择、操作频率的监控、内存管理、持久化策略、网络优化以及使用适当的监控工具。通过对这些方面的深入了解和细致调整，可以有效控制和优化Redis的流量，确保系统...
本文将详细解释几个用于检查Redis内存状态的命令。 首先，`info memory`是查看Redis内存使用情况的基础命令。执行`redis-cli info memory`会返回一系列内存统计数据，其中包括： 1. `used_memory`: 表示Redis分配...
- **数据持久化**：与仅支持内存存储的Memcached不同，Redis支持将数据周期性地写入磁盘或通过追加记录文件的方式实现数据的持久化。此外，Redis还支持主从复制机制(master-slave replication)，使得数据能够在多个...
Redis作为一款优秀的键值存储系统，凭借其内存存储、高性能、丰富的数据结构以及强大的灵活性，在构建各种高性能应用程序时发挥着重要作用。利用好官方文档、社区资源和辅助工具，开发者可以更加高效地利用Redis的...
Redis的存储结构 Redis的安装 Redis的数据类型 字符串类型 列表类型 hash类型 集合类型 有序集合 Redis原理分析 过期时间设置 过期删除的原理 发布订阅 数据持久化 内存回收策略 单线程高性能原理 在Redis中使用Lua...
Redis的存储结构 Redis的安装 Redis的数据类型 字符串类型 列表类型 hash类型 集合类型 有序集合 Redis原理分析 过期时间设置 过期删除的原理 发布订阅 数据持久化 内存回收策略 单线程高性能原理 在Redis中使用Lua...
- 存储结构：Redis中的数据结构设计高效，如ziplist用于紧凑存储列表和哈希，intset用于存储整数集合。 3. Redis面试常见问题： - Redis与Memcached的区别：Memcached仅支持简单的键值对，而Redis提供更丰富的...
它以内存存储为主，速度快且支持多种数据结构，如字符串、哈希、列表、集合和有序集合等。了解Redis的数据结构和命令是进行内存分析的基础。 3. **Key前缀筛选**： 在Redis中，可以通过Key前缀来筛选特定类型的...
### Redis技术分析及运用 #### 一、Redis简介与特性 Redis是一种开源的键值（Key-Value）存储系统，属于非关系型数据库（NoSQL）的一种，它将数据存储在内存中，以提高数据访问速度。由于其高效的数据结构和丰富的...