redis相关知识

Redis1:配置文件 

如果认为Redis是一个key value存储, 可以使用它来代替MySQL；如果认为它是一个可以持久化的cache, 可能只是用它保存一些频繁访问的临时数据（代替Memcached）；除此之外，还可以把Redis当做一个轻量级的消息队列使用，因为它内置就支持 list数据结构和PUB/SUB命令；还可以当做一个轻量级的分布式锁系统。Redis是REmote DIctionary Server的缩写，在Redis在官方网站的解释是：

Redis is an open source, advanced key-value store. It is often referred to as a data structure server since keys can contain strings, hashes, lists, sets and sorted sets.

本文将会详细介绍Redis的配置文件。

1. Redis默认不是以守护进程的方式运行，可以通过该配置项修改，使用yes启用守护进程

daemonize no

2. 当Redis以守护进程方式运行时，Redis默认会把pid写入/var/run/redis.pid文件，可以通过pidfile指定

pidfile /var/run/redis.pid

3. 指定Redis监听端口，默认端口为6379，作者在自己的一篇博文中解释了为什么选用6379作为默认端口，因为6379在手机按键上MERZ对应的号码，而MERZ取自意大利歌女Alessia Merz的名字

port 6379

4. 绑定的主机地址

bind 127.0.0.1

5.当 客户端闲置多长时间后关闭连接，如果指定为0，表示关闭该功能

timeout 300

6. 指定日志记录级别，Redis总共支持四个级别：debug、verbose、notice、warning，默认为verbose

loglevel verbose

7. 日志记录方式，默认为标准输出，如果配置Redis为守护进程方式运行，而这里又配置为日志记录方式为标准输出，则日志将会发送给/dev/null

logfile stdout

8. 设置数据库的数量，默认数据库为0，可以使用SELECT 命令在连接上指定数据库id

databases 16

9. 指定在多长时间内，有多少次更新操作，就将数据同步到数据文件，可以多个条件配合

save

Redis默认配置文件中提供了三个条件：

save 900 1save 300 10save 60 10000

分别表示900秒（15分钟）内有1个更改，300秒（5分钟）内有10个更改以及60秒内有10000个更改。

10. 指定存储至本地数据库时是否压缩数据，默认为yes，Redis采用LZF压缩，如果为了节省CPU时间，可以关闭该选项，但会导致数据库文件变的巨大

rdbcompression yes

11. 指定本地数据库文件名，默认值为dump.rdb

dbfilename dump.rdb

12. 指定本地数据库存放目录

dir ./

13. 设置当本机为slav服务时，设置master服务的IP地址及端口，在Redis启动时，它会自动从master进行数据同步

slaveof

14. 当master服务设置了密码保护时，slav服务连接master的密码

masterauth

15. 设置Redis连接密码，如果配置了连接密码，客户端在连接Redis时需要通过AUTH 命令提供密码，默认关闭

requirepass foobared

16. 设置同一时间最大客户端连接数，默认无限制，Redis可以同时打开的客户端连接数为Redis进程可以打开的最大文件描述符数，如果设置 maxclients 0，表示不作限制。当客户端连接数到达限制时，Redis会关闭新的连接并向客户端返回max number of clients reached错误信息

maxclients 128

17. 指定Redis最大内存限制，Redis在启动时会把数据加载到内存中，达到最大内存后，Redis会先尝试清除已到期或即将到期的Key，当此方法处理 后，仍然到达最大内存设置，将无法再进行写入操作，但仍然可以进行读取操作。Redis新的vm机制，会把Key存放内存，Value会存放在swap区

maxmemory

18. 指定是否在每次更新操作后进行日志记录，Redis在默认情况下是异步的把数据写入磁盘，如果不开启，可能会在断电时导致一段时间内的数据丢失。因为redis本身同步数据文件是按上面save条件来同步的，所以有的数据会在一段时间内只存在于内存中。默认为no

appendonly no

19. 指定更新日志文件名，默认为appendonly.aof

appendfilename appendonly.aof

20. 指定更新日志条件，共有3个可选值： 
no：表示等操作系统进行数据缓存同步到磁盘（快） 
always：表示每次更新操作后手动调用fsync()将数据写到磁盘（慢，安全） 
everysec：表示每秒同步一次（折衷，默认值）

appendfsync everysec

21. 指定是否启用虚拟内存机制，默认值为no，简单的介绍一下，VM机制将数据分页存放，由Redis将访问量较少的页即冷数据swap到磁盘上，访问多的页面由磁盘自动换出到内存中（在后面的文章我会仔细分析Redis的VM机制）

vm-enabled no

22. 虚拟内存文件路径，默认值为/tmp/redis.swap，不可多个Redis实例共享

vm-swap-file /tmp/redis.swap

23. 将所有大于vm-max-memory的数据存入虚拟内存,无论vm-max-memory设置多小,所有索引数据都是内存存储的(Redis的索引数据 就是keys),也就是说,当vm-max-memory设置为0的时候,其实是所有value都存在于磁盘。默认值为0

vm-max-memory 0

24. Redis swap文件分成了很多的page，一个对象可以保存在多个page上面，但一个page上不能被多个对象共享，vm-page-size是要根据存储的 数据大小来设定的，作者建议如果存储很多小对象，page大小最好设置为32或者64bytes；如果存储很大大对象，则可以使用更大的page，如果不 确定，就使用默认值

vm-page-size 32

25. 设置swap文件中的page数量，由于页表（一种表示页面空闲或使用的bitmap）是在放在内存中的，，在磁盘上每8个pages将消耗1byte的内存。

vm-pages 134217728

26. 设置访问swap文件的线程数,最好不要超过机器的核数,如果设置为0,那么所有对swap文件的操作都是串行的，可能会造成比较长时间的延迟。默认值为4

vm-max-threads 4

27. 设置在向客户端应答时，是否把较小的包合并为一个包发送，默认为开启

glueoutputbuf yes

28. 指定在超过一定的数量或者最大的元素超过某一临界值时，采用一种特殊的哈希算法

hash-max-zipmap-entries 64hash-max-zipmap-value 512

29. 指定是否激活重置哈希，默认为开启（后面在介绍Redis的哈希算法时具体介绍）

activerehashing yes

30. 指定包含其它的配置文件，可以在同一主机上多个Redis实例之间使用同一份配置文件，而同时各个实例又拥有自己的特定配置文件

include /path/to/local.conf

Redis2:server启动过程

本文将通过分析代码来介绍Redis的启动过程，通过查看Redis 的启动脚本，得知Redis的启动时从Redis.c的main方法开始的。Redis启动可以分为以下几个步骤：

1.    初始化Redis服务器全局配置

2.    重置服务器Save参数（具体下文详解）和加载配置文件

3.    初始化服务器

4.    加载数据库

5.    开始网络监听

   一，初始化Redis服务器全局配置。这一步骤主要是主要是根据Redis.h中设置的Static值来初始化Redis服务器配置，这里设置是Redis服务器的默认配置。如：

·         TCP Port，Redis Client的缺省Timeout；

·         Redis缺省的数据库数目；

·         Redis Append 持久化方式的参数设置；

·         Redis的所支持的各种数据结构的缺省值的设置；

·         Redis内存Swap相关设置；

·         Redis Master & Slave相关的配置；

·         Redis Command Table初始化。

 二，加载配置文件：

      这一步是通过读取的配置文件来对Redis服务器进行设置，将会覆盖上一步的某些缺省设置。打开下载下来的Redis源代码，我们可以看到其根目录下有一个默认的配置文件redis.conf。需要注意的是，如果在启动Redis的时候没有指定配置文件，则Redis服务器在启动的时候是不会加载这个默认的配置文件进行配置的。而且这个默认的配置文件和第一步中得全局默认缺省配置不尽相同，比如针对Redis的Append模式的数据保存策略的配置，redis.conf里面的设置是：

save 900 1 -------15分钟内一次更新
save 300 10 ------5分钟内10次更新
save 60 10000 ---1分钟内10000次更新。

而上一步里面的默认缺省配置确实：

save 60*60 1 -------一个小时内1次更新
save 300 100 ------5分钟内100次更新
save 60 10000 ---1分钟内10000次更新。

    因此我们在启动Redis的时候如果默认配置不能满足要求，则需要指明配置文件进行配置。

 

   三，初始化服务器：

   初始化服务器是在initServer()方法中完成的，次方法利用上两步设置的参数进一步初始化服务器：

·         创建用来维护clients和slaves的list

·         创建共享对象。redisObject这个struct里有个变量叫做refcount，这个变量就是用来实现共享的。Redis的对象目前Redis只支持共享StringObject。Redis的共享对象有两大类比：第一类：Redis server的各种操作需要经常用到的各类对象，如：Redis Command的分隔符"\r\n",用于Redis command的reply的"+OK\r\n"或者"-ERR\r\n"等对象，因为在Redis的各种操作这类对象要被频繁使用，所以就在启动Redis的时候创建好，然后共用这些对象，减少时间成本和空间成本；第二，类的共享对象就是对应于数字的StringObject，如：Set "olylakers1" 1234; Set "olylakes2" 1234;在Redis内部，"olylakers1"和"olylakers2"这两个key都指向由数字1234转化的StringObject。这样在海量数据和特定存储内容下，可以节省大量的内存空间。可用通过REDIS_SHARED_INTEGERS这个参数来指定Redis启动的时候创建多少个第二类共享对象，默认的参数是10000，即创建的StrongObject个取值范围是0-9999之间。

·         创建Pub/Sub通道

·         初始化网络监听EventLoop的相关内容，如eventLoop，timeEvent，fileEvent等

·         如果开启了VM，则初始化虚拟内存相关的IO/Thread

 四，加载数据：

   根据配置的不同，Redis加载数据的源也不一样，如果在配置文件里设置了appendonly  yes（默认是no），那么就从appendfile加载数据，反之则从RedisDb加载数据

·          从appendfile加载数据：我们先来看一下appendfile的内容是什么。下面的一条记录摘取自appendfile：SET $9 olylakers $3 oly。很显，appendfile保存的就是redis server接收到的各种命令，那么从appendfile加载数据就是redis server从appenfile里面读取这些命令的记录，然后重新把这些命令执行一遍即可。需要注意的是，如果开启了VM，那么在从appendfile加载数据的时候可能要涉及swap操作。

·         从redisdb加载数据：如果没有开启appendonly，那么则需要从db file加载数据到内存，其过程是：

1.    通过处理select命令，选择DB

2.    然后从db file读取key和value

3.    检查key是否过期，如果过期则跳过这个key，如果不过期，则把数据Add到对应的db的dict中

4.    如果开启了VM，则从db file中load数据，也可能涉及到swap操作

 五，开始网络监听：

         Redis的网络监听没有采用libevent等，而是自己实现了一套简单的机遇event驱动的API，具体见ae.c。

Redis3:持久化 

 redis使用了两种文件格式：全量数据和增量请求。全量数据格式是把内存中的数据写入磁盘，

便于下次读取文件进行加载；增量请求文件则是把内存中的数据序列化为操作请求，用于读取文件进行replay得到数据，序列化的操作包括SET、RPUSH、SADD、ZADD。

redis对interger根据值范围采用不同的编码存储，具体如下：

值范围	字节数(byte)	编码格式
[0, 1 << 6 – 1]	1	00 | value
[1 << 6, 1 << 14 – 1]	2	01 | (value >> 8) | value & oxFF
[1 << 14, 1 << 31 – 1]	5	10 000000 | htonl(value)

  redis对数值类的string object编码存储格式如下：

值范围	字节数(byte)	编码格式
[-(1 << 7), 1 << 7 – 1]	2	1100 0000 | value & 0xFF
[-(1 << 15), 1 << 15 – 1]	3	1100 0001 | (value >> 8) & 0xFF | value & oxFF
[-(1 << 31)], 1 << 31 – 1]	5	1100 0010 |   value & oxFF | (value >> 8) & 0xFF | (value >> 16) & 0xFF | (value >> 24) & 0xFF

 

redis支持字符串压缩存储，压缩的编码格式如下：

1100 0011

compl_len (压缩后的长度)

orig_len (压缩前的长度)

comp_value (压缩后的内容)

 

2.6.1        data文件格式

 

 

2.6.2        append文件格式

 

RedisDb	*2	$6	SELECT		$length(index)		index:long
entry	*3	$3	SET	$length(key)	key	$length(value)	value
entry	*3	$5	RPUSH	$length(key)	key	$length(value)	value
entry	*3	$4	SADD	$length(key)	key	$length(value)	value
entry	*3	$4	ZADD	$length(key)	key	$length(score)	score:double	$length(value)	value
entry	…
RedisDb	…
RedisDb	…
entry
entry
entry

 

 

redis是一个支持持久化的内存数据库，也就是说redis需要经常将内存中的数据同步到磁盘来保证持久化。redis支持两种持久化方式，一种是 Snapshotting（快照）也是默认方式，另一种是Append-only file（缩写aof）的方式。下面分别介绍

Snapshotting
       快照是默认的持久化方式。这种方式是就是将内存中数据以快照的方式写入到二进制文件中,默认的文件名为dump.rdb。可以通过配置设置自动做快照持久 化的方式。我们可以配置redis在n秒内如果超过m个key被修改就自动做快照，下面是默认的快照保存配置

save 900 1  #900秒内如果超过1个key被修改，则发起快照保存
save 300 10 #300秒内容如超过10个key被修改，则发起快照保存
save 60 10000

下面介绍详细的快照保存过程

1.redis调用fork,现在有了子进程和父进程。

2. 父进程继续处理client请求，子进程负责将内存内容写入到临时文件。由于os的写时复制机制（copy on write)父子进程会共享相同的物理页面，当父进程处理写请求时os会为父进程要修改的页面创建副本，而不是写共享的页面。所以子进程的地址空间内的数 据是fork时刻整个数据库的一个快照。

3.当子进程将快照写入临时文件完毕后，用临时文件替换原来的快照文件，然后子进程退出。

client 也可以使用save或者bgsave命令通知redis做一次快照持久化。save操作是在主线程中保存快照的，由于redis是用一个主线程来处理所有 client的请求，这种方式会阻塞所有client请求。所以不推荐使用。另一点需要注意的是，每次快照持久化都是将内存数据完整写入到磁盘一次，并不 是增量的只同步脏数据。如果数据量大的话，而且写操作比较多，必然会引起大量的磁盘io操作，可能会严重影响性能。

另外由于快照方式是在一定间隔时间做一次的，所以如果redis意外down掉的话，就会丢失最后一次快照后的所有修改。如果应用要求不能丢失任何修改的话，可以采用aof持久化方式。下面介绍

Append-only file
    
aof 比快照方式有更好的持久化性，是由于在使用aof持久化方式时,redis会将每一个收到的写命令都通过write函数追加到文件中(默认是 appendonly.aof)。当redis重启时会通过重新执行文件中保存的写命令来在内存中重建整个数据库的内容。当然由于os会在内核中缓存 write做的修改，所以可能不是立即写到磁盘上。这样aof方式的持久化也还是有可能会丢失部分修改。不过我们可以通过配置文件告诉redis我们想要 通过fsync函数强制os写入到磁盘的时机。有三种方式如下（默认是：每秒fsync一次）

appendonly yes              //启用aof持久化方式
# appendfsync always      //每次收到写命令就立即强制写入磁盘，最慢的，但是保证完全的持久化，不推荐使用
appendfsync everysec     //每秒钟强制写入磁盘一次，在性能和持久化方面做了很好的折中，推荐
# appendfsync no    //完全依赖os，性能最好,持久化没保证

aof 的方式也同时带来了另一个问题。持久化文件会变的越来越大。例如我们调用incr test命令100次，文件中必须保存全部的100条命令，其实有99条都是多余的。因为要恢复数据库的状态其实文件中保存一条set test 100就够了。为了压缩aof的持久化文件。redis提供了bgrewriteaof命令。收到此命令redis将使用与快照类似的方式将内存中的数据 以命令的方式保存到临时文件中，最后替换原来的文件。具体过程如下

1. redis调用fork ，现在有父子两个进程
2. 子进程根据内存中的数据库快照，往临时文件中写入重建数据库状态的命令
3.父进程继续处理client请求，除了把写命令写入到原来的aof文件中。同时把收到的写命令缓存起来。这样就能保证如果子进程重写失败的话并不会出问题。
4.当子进程把快照内容写入已命令方式写到临时文件中后，子进程发信号通知父进程。然后父进程把缓存的写命令也写入到临时文件。
5.现在父进程可以使用临时文件替换老的aof文件，并重命名，后面收到的写命令也开始往新的aof文件中追加。

需要注意到是重写aof文件的操作，并没有读取旧的aof文件，而是将整个内存中的数据库内容用命令的方式重写了一个新的aof文件,这点和快照有点类似。 

 

Redis4:数据结构

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 的定义:

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;

 

redisDb 中 ,dict 成员是与实际存储数据相关的. dict 的定义如下:

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 结构体, 其定义如下:

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 结构

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 的定义如下:

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

//Searching an element x

 

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 33 34 35 36 37 38 39 40 41 42 43

typedef struct zskiplistNode   {   robj *obj;   double score;   struct zskiplistNode *backward;   struct zskiplistLevel   {   struct zskiplistNode *forward;   unsigned int span;   } level[];   } zskiplistNode;   typedef struct zskiplist   {   struct zskiplistNode *header, *tail;   unsigned long length;   int level;   } zskiplist;   typedef struct zset   {   dict *dict;   zskiplist *zsl;   } zset;

zset 的实现用到了2个数据结构: hash_table 和 skip list (跳跃表),其中 hash table 是使用 redis 的 dict 来实现的,主要是为了保证查询效率为 O(1),而 skip list (跳跃表) 是用来保证元素有序并能够保证 INSERT 和 REMOVE 操作是 O(logn)的复杂度。

1) zset初始化状态

createZsetObject函数来创建并初始化一个 zset

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

robj *createZsetObject(void)   {   zset *zs = zmalloc(sizeof(*zs));   robj *o;   zs->dict = dictCreate(&zsetDictType,NULL);   zs->zsl = zslCreate();   o = createObject(REDIS_ZSET,zs);   o->encoding = REDIS_ENCODING_SKIPLIST;   return o;   }

zslCreate()函数用来创建并初如化一个 skiplist。 其中，skiplist 的 level 最大值为 ZSKIPLIST_MAXLEVEL=32 层。

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

zskiplist *zslCreate(void)   {   int j;   zskiplist *zsl;   zsl = zmalloc(sizeof(*zsl));   zsl->level = 1;   zsl->length = 0;   zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);   for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {   zsl->header->level[j].forward = NULL;   zsl->header->level[j].span = 0;   }   zsl->header->backward = NULL;   zsl->tail = NULL;   return zsl;   }

2) ZADD myzset 1 “one”

ZADD 命令格式：

ZADD key score member

1. 根据 key 从 redisDb 进行查询，返回 zset 对象。
2. 以 member 作为 key,score 作为 value ，向 zset的 dict 进行中插入;
3. 如果返回成功，表明 member 没有在 dict 中出现过，直接向 skiplist 进行插入。
4. 如果步骤返回失败，表明以 member 已经在 dict中出现过，则需要先从 skiplist 中删除，然后以现在的 score 值重新插入。

3) ZADD myzset 3 “three”

4) ZADD myzset 2 “two”

 

 

redis学习系列 

 淘宝的redis内存分析

淘宝关于zipmap和skiplist的分析

http://rdc.taobao.com/blog/cs/?tag=redis 

 

redis各个点的分析,值得一看!!!

 

协议,主从复制,事件模型,持久化

 

http://www.cnblogs.com/liping13599168/category/293173.html

http://www.cnblogs.com/huli/archive/2010/06/06/1752778.html