`
zl198751
  • 浏览: 273473 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

Redis内存存储结构分析

Redis数据结构 
阅读更多

淘宝：

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;                 /* The keyspace for this DB */
   
dict *expires;              /* Timeout of keys with a timeout set */
   
dict *blocking_keys;    /* Keys with clients waiting for data (BLPOP) */
   
dict *io_keys;              /* Keys with clients waiting for VM I/O */
   
dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
   
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;
   
/* This is our hash table structure. Every dictionary has two of this as we
   
* implement incremental rehashing, for the old to the new table. */
   
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; /* rehashing not in progress if rehashidx == -1 */
   
int iterators; /* number of iterators currently running */
   
} 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;   /* REDIS_VM_MEMORY or REDIS_VM_SWAPPING */
   
unsigned encoding:4;
   
unsigned lru:22;        /* lru time (relative to server.lruclock) */
   
int refcount;
   
void *ptr;
   
/* VM fields are only allocated if VM is active, otherwise the
   
* object allocation function will just allocate
   
* sizeof(redisObjct) minus sizeof(redisObjectVM), so using
   
* Redis without VM active will not have any overhead. */
   
} robj;
   
//type 占 4 bit,用来表示 key-value 中 value 值的类型,目前 redis 支持: string, list, set,zset,hash 5种类型的值.
   
/* Object types */
   
#define REDIS_STRING 0
   
#define REDIS_LIST 1
   
#define REDIS_SET 2
   
#define REDIS_ZSET 3
   
#define REDIS_HASH 4
   
#define REDIS_VMPOINTER 8
// storage 占 2 bit ,表示 此值是在 内存中,还是 swap 在硬盘上.
// encoding 占 4 bit ,表示值的编码类型,目前有 8种类型:
   
/* Objects encoding. Some kind of objects like Strings and Hashes can be
   
* internally represented in multiple ways. The 'encoding' field of the object
   
* is set to one of this fields for this object. */
   
#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 */
   
/* 如 type 是 REDIS_STRING 类型的,则其值如果是数字,就可以编码成 REDIS_ENCODING_INT,以节约内存.
   
* 如 type 是 REDIS_HASH 类型的,如果其 entry 小于配置值: hash-max-zipmap-entries 或 value字符串的长度小于 hash-max-zipmap-value, 则可以编码成 REDIS_ENCODING_ZIPMAP 类型存储,以节约内存. 否则采用 Dict 来存储.
   
* 如 type 是 REDIS_LIST 类型的,如果其 entry 小于配置值: list-max-ziplist-entries 或 value字符串的长度小于 list-max-ziplist-value, 则可以编码成 REDIS_ENCODING_ZIPLIST 类型存储,以节约内存; 否则采用 REDIS_ENCODING_LINKEDLIST 来存储.
   
*  如 type 是 REDIS_SET 类型的,如果其值可以表示成数字类型且 entry 小于配置值set-max-intset-entries, 则可以编码成 REDIS_ENCODING_INTSET 类型存储,以节约内存; 否则采用 Dict类型来存储.
   
*  lru: 是时间戳
   
*  refcount: 引用次数
   
*  void * ptr : 指向实际存储的 value 值内存块,其类型可以是 string, set, zset,list,hash ,编码方式可以是上述 encoding 表示的一种.
   
* 至于一个 key 的 value 采用哪种类型来保存,完全是由客户端的指令来决定的,如 hset ,则值是采用REDIS_HASH 类型表示的,至于那种编码(encoding),则由 redis 根据配置自动决定.
*/

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 的长度.

  1. 初始化时只有2个字节,第1个字节表示 zipmap 保存的 key-value 对的个数(如果key-value 对的个数超过 254,则一直用254来表示, zipmap 中实际保存的 key-value 对个数可以通过 zipmapLen() 函数计算得到).
    2. 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”
  3. hset(age,30)

    插入 key-value 对 (“age”,30)

  4. 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 其实质是用一个字符串数组形式的双向链表. 其结构示意图如下:

  1. ziplist header由3个字段组成:
    • ziplist_bytes: 用一个uint32_t 来保存, 构成 ziplist 的字符串数组的总长度,包括 ziplist header,
    • ziplist_tail_offset: 用一个uint32_t 来保存,记录 ziplist 的尾部偏移位置.
    • ziplist_length: 用一个 uint16_t 来保存,记录 ziplist 中 elem 的个数
  2. 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
//Searching an element <em>x</em>
   
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
//To insert 35 -
   
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
//To delete 37 -
   
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

相关推荐

    redis内存存储结构分析

    redis缓存解决方案和基本命令,redisredis内存存储结构分析.Redis的数据全部放在内存带来了高速的性能，但是也带来一些不合理之处。比如一个中型网站有100万注册用户，如果这些资料要用Redis来存储，内存的容量必须...

    云资源下载V1.2

    (5)Redis内存存储结构分析 (6)redis起步 (7)Redis容量及使用规划 (8)Redis新的存储模式diskstore (9)Redis学习笔记 (11)redis应用场景 (12)redis应用之日志汇总 (13)构建可扩展微博架构 (14)浅谈redis的键值设计 (15...

    Redis精品资料荟萃

    教程名称：Redis精品资料荟萃课程目录：【】Redis Cookbook【】Redis 内存存储结构分析【】Redis 深入浅出【】redis介绍【】Redis学习笔记【】《Redis实战》电子书【】深入了解redis【】高性能NoSQL数据库Redis 盛大...

    redis_3.2.9_内存分布分析

    这是本人分redis内部数据存储结构的过程文档，部分无用细节忽略，这是数据存储结构的分析，没有增、删、改、查的动态处理过程，需要参考部分源码查看

    redis开发的概要介绍与分析

    Redis是一个开源的、内存中的数据结构存储系统，它可以用作数据库、缓存和消息代理。Redis支持多种数据结构，包括字符串、哈希、列表、集合、有序集合等，并提供了丰富的API供开发者使用。 在Redis开发过程中，...

    聊聊高并发高可用那些事（Kafka、Redis、MySQL）

    # MySQL篇内容 - 一条SQL语句的执行流程 - InnoDB数据读取和写入过程 - 基本数据结构介绍 - MyIsAM InnoDB 等存储引擎 ...- Redis、Memcached 对比分析 - 数据结构以及应用场景 - 缓存雪崩、缓存击穿、缓存穿透 ......

    Redis-Source-Code-Analyze:Redis原始阅读和分析（Redis-3.2.5）-redis source code

    即使始终为它们提供服务并将它们修改到服务器内存中，Redis也会将它们存储在磁盘上。 这意味着Redis速度很快，但这也是非易失性的。 数据结构的实现强调内存效率，因此与使用高级编程语言建模的相同数据结构相比，...

    redis:redis源码分析与个人理解

    即使始终为它们提供服务并将它们修改到服务器内存中，Redis也会将它们存储在磁盘上。 这意味着Redis速度很快，但这也是非易失性的。 数据结构的实现强调内存效率，因此与使用高级编程语言建模的相同数据结构相比，...

    Redis-64-5.0.10.7z

    Redis通常用于缓存、消息队列、实时数据分析、计数器、排行榜等场景，Redis是一个功能强大的键值对存储数据库，具有高速、高可用、可扩展等特点，适用于各种应用场景。 它的主要特点包括： 速度快：Redis使用ANSI ...

    redis-source-analysis:redis-3.2.12源码分析

    即使始终为它们提供服务并将它们修改到服务器内存中，Redis也会将它们存储在磁盘上。 这意味着Redis速度很快，但这也是非易失性的。 数据结构的实现强调内存效率，因此与使用高级编程语言建模的相同数据结构相比，...

    redis安装配置详细教程.pdf

    Redis还具有多种应用场景，如在Web应用中存储会话信息、实现消息队列、排行榜和计数器、分布式锁以及实时分析等。例如，Redis的发布订阅功能可以用来实现消息队列，通过将消息发布到特定的频道，可以让订阅该频道的...

    安装和配置指引，通俗易懂

    Redis是一个开源的内存数据库，它被广泛用作缓存、消息队列和数据存储。Redis支持多种数据结构，如字符串、哈希表、列表、集合、有序集合等，使其非常灵活和强大。 Redis的特点包括： - 高性能：Redis数据存储在...

    Redis常用语法命令及使用示例详解

    Redis是一个开源的、内存中的数据结构存储系统，它可以用作数据库、缓存和消息中介。它支持多种数据类型，包括字符串（string）、哈希（hash）、列表（list）、集合（set）、有序集合（sorted set）等，并提供了丰富...

    redis源码分析教程之压缩链表ziplist详解

    压缩列表（ziplist）是由一系列特殊编码的内存块构成的列表，它对于Redis的数据存储优化有着非常重要的作用。这篇文章总结一下redis中使用非常多的一个数据结构压缩链表ziplist。该数据结构在redis中说是无处不在也...

    Redis缓存技术在自动气象站资料调用中的优化应用

    为了提高气象自动站资料的检索查询效率，采用基于内存Key-Value结构的Redis数据库技术，通过搭建Redis数据库集群，把数据缓存在内存中并实现主从复制，提出一种适合气象自动站数据特性的数据存储结构模型，使得高...

    java 大数据 spark flink redis hive hbase kafka 面试题 数据结构 算法 设计模式.zip

    存储结构（物理结构）：描述数据在计算机中如何具体存储。例如，数组的连续存储，链表的动态分配节点，树和图的邻接矩阵或邻接表表示等。 基本操作：针对每种数据结构，定义了一系列基本的操作，包括但不限于插入、...

    Practical-redis：这本书的代码-Practical Redis

    使用模式包括（但不限于）键值数据库，缓存服务器，消息代理，会话存储，分析引擎等。 关于实用Redis 顾名思义，实用Redis是Redis的动手指南，由代码驱动。 每章都基于一个应用程序（简单到中等复杂性），该应用...

    nosql 入门教程

    4.3.1 用内存映射文件存储数据　74 4.3.2 MongoDB集合和索引使用指南　75 4.3.3 MongoDB的可靠性和耐久性　75 4.3.4 水平扩展　76 4.4 键/值存储Memcached和Redis　78 4.4.1 Memcached的内部结构　78 4.4.2 Redis的...

    使用 Koa + MongoDB + Redis 搭建论坛系统.zip

    内存：包括随机访问内存 (RAM) 和只读存储器 (ROM)，用于临时或永久地存储程序和数据供CPU快速访问。 存储设备：如硬盘、固态硬盘 (SSD)、光盘驱动器等，用于长期保存大量的程序和数据。 输入/输出设备：如键盘、...

Magicbox
Global site tag (gtag.js) - Google Analytics