Redis简介及数据结构

一、介绍一下Redis

首先，肯定是去官网看看官方是怎么介绍Redis的啦。

Introduction to Redis
Learn about the Redis open source project
redis.io

一大堆没见过的技术：lua(Lua脚本)、replication(复制)、Redis Sentinel(哨兵)、Redis Cluster(Redis 集群)，当然我们也会有看得懂的技术：transactions(事务)、different levels of on-disk persistence(数据持久化)、LRU eviction(LRU淘汰机制)…

至少官方介绍Redis的第一句应该是可以很容易看懂：“Redis is an open source (BSD licensed),in-memory data structure store, used as a database,cache and message broker.”
Redis是一个开源的，基于内存的数据结构存储，可用作于数据库、缓存、消息中间件。

从官方的解释上，我们可以知道：Redis是基于内存，支持多种数据结构。
从经验的角度上，我们可以知道：Redis常用作于缓存。
就我个人认为：学习一种新技术，先把握该技术整体的知识(思想)，再扣细节，这样学习起来会比较轻松一些。所以我们先以"内存"、“数据结构”、"缓存"来对Redis入门。

1.1为什么要用Redis？

从上面可知：Redis是基于内存，常用作于缓存的一种技术，并且Redis存储的方式是以key-value的形式。

我们可以发现这不就是Java的Map容器所拥有的特性吗，那为什么还需要Redis呢？

• Java实现的Map是本地缓存，如果有多台实例(机器)的话，每个实例都需要各自保存一份缓存，缓存不具有一致性
• Redis实现的是分布式缓存，如果有多台实例(机器)的话，每个实例都共享一份缓存，缓存具有一致性。

Java实现的Map不是专业做缓存的，JVM内存太大容易挂掉的。一般用做于容器来存储临时数据，缓存的数据随着JVM销毁而结束。Map所存储的数据结构，缓存过期机制等等是需要程序员自己手写的。

Redis是专业做缓存的，可以用几十个G内存来做缓存。Redis一般用作于缓存，可以将缓存数据保存在硬盘中，Redis重启了后可以将其恢复。原生提供丰富的数据结构、缓存过期机制等等简单好用的功能。

参考资料：

• 为什么要用redis而不用map做缓存? https://segmentfault.com/q/1010000009103999

1.2为什么要用缓存？

如果我们的网站出现了性能问题(访问时间慢)，按经验来说，一般是由于数据库撑不住了。因为一般数据库的读写都是要经过磁盘的，而磁盘的速度可以说是相当慢的(相对内存来说)

有了缓存之后，我们的访问就变成这样了：有了缓存提高了并发和性能

二、Redis的数据结构

本文不会讲述命令的使用方式，具体的如何使用可查询API。
Redis 命令参考：http://doc.redisfans.com/
try Redis(不用安装Redis即可体验Redis命令)：http://try.redis.io/

Redis支持丰富的数据结构，常用的有string、list、hash、set、sortset这几种。学习这些数据结构是使用Redis的基础！

“Redis is written in ANSI C”–>Redis由C语言编写

首先还是得声明一下，Redis的存储是以key-value的形式的。Redis中的key一定是字符串，value可以是string、list、hash、set、sortset这几种常用的。

但要值得注意的是：Redis并没有直接使用这些数据结构来实现key-value数据库，而是基于这些数据结构创建了一个对象系统。

简单来说：Redis使用对象来表示数据库中的键和值。每次我们在Redis数据库中新创建一个键值对时，至少会创建出两个对象。一个是键对象，一个是值对象。

Redis中的每个对象都由一个redisObject结构来表示：

typedef struct redisObject{
    // 对象的类型
    unsigned type 4:;
    // 对象的编码格式
    unsigned encoding:4;
    // 指向底层实现数据结构的指针
    void * ptr;
    //.....
}robj;

2.1SDS简单动态字符串

简单动态字符串(Simple dynamic string,SDS)

Redis中的字符串跟C语言中的字符串，是有点差距的。

Redis使用sdshdr结构来表示一个SDS值：

struct sdshdr{
    // 字节数组，用于保存字符串
    char buf[];
    // 记录buf数组中已使用的字节数量，也是字符串的长度
    int len;
    // 记录buf数组未使用的字节数量
    int free;
}

使用SDS的好处

1. sdshdr数据结构中用len属性记录了字符串的长度。那么获取字符串的长度时，时间复杂度只需要O(1)。
2. SDS不会发生溢出的问题，如果修改SDS时，空间不足。先会扩展空间，再进行修改！(内部实现了动态扩展机制)。
3. SDS可以减少内存分配的次数(空间预分配机制)。在扩展空间时，除了分配修改时所必要的空间，还会分配额外的空闲空间(free 属性)。
4. SDS是二进制安全的，所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据。

2.2链表

对于链表而言，我们不会陌生的了。在大学期间肯定开过数据结构与算法课程，链表肯定是讲过的了。在Java中Linkedxxx容器底层数据结构也是链表+[xxx]的。我们来看看Redis中的链表是怎么实现的：

使用listNode结构来表示每个节点：

typedef strcut listNode{
    //前置节点
    strcut listNode  *pre;
    //后置节点
    strcut listNode  *pre;
    //节点的值
    void  *value;
}listNode

使用listNode是可以组成链表了，Redis中使用list结构来持有链表：

typedef struct list{
    //表头结点
    listNode  *head;
    //表尾节点
    listNode  *tail;
    //链表长度
    unsigned long len;
    //节点值复制函数
    void *(*dup) (viod *ptr);
    //节点值释放函数
    void  (*free) (viod *ptr);
    //节点值对比函数
    int (*match) (void *ptr,void *key);
}list

Redis链表的特性

Redis的链表有以下特性：

• 无环双向链表
• 获取表头指针，表尾指针，链表节点长度的时间复杂度均为O(1)
• 链表使用void *指针来保存节点值，可以保存各种不同类型的值

2.3哈希表

声明：《Redis设计与实现》里边有"字典"这么一个概念，我个人认为还是直接叫哈希表比较通俗易懂。

在Redis中，key-value的数据结构底层就是哈希表来实现的。对于哈希表来说，我们也并不陌生。在Java中，哈希表实际上就是数组+链表的形式来构建的。

在Redis里边，哈希表使用dictht结构来定义：

typedef struct dictht{
    //哈希表数组
    dictEntry **table;  
    //哈希表大小
    unsigned long size;    
    //哈希表大小掩码，用于计算索引值
    unsigned long sizemark;     
    //哈希表已有节点数量
    unsigned long used;
}dictht

typedef struct dictEntry {
    //键
    void *key;
    //值
    union {
        void *value;
        uint64_tu64;
        int64_ts64;
    }v;    
    //指向下个哈希节点，组成链表
    struct dictEntry *next;
}dictEntry;

Redis中哈希冲突时：是将新节点添加在链表的表头。

rehash的过程

在对哈希表进行扩展或者收缩操作时，reash过程并不是一次性地完成的，而是渐进式地完成的。

Redis在rehash时采取渐进式的原因：数据量如果过大的话，一次性rehash会有庞大的计算量，这很可能导致服务器一段时间内停止服务。

2.4跳跃表(shiplist)

跳跃表(shiplist)是实现sortset(有序集合)的底层数据结构之一！

Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成。

typedef struct zskiplistNode {
    // 后退指针
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    robj *obj;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
} zskiplistNode;

2.5整数集合(intset)

整数集合是set(集合)的底层数据结构之一。当一个set(集合)只包含整数值元素，并且元素的数量不多时，Redis就会采用整数集合(intset)作为set(集合)的底层实现。

typedef struct intset {
    // 编码方式
    unit32_t encoding;
    // 集合包含的元素数量
    unit32_t lenght;
    // 保存元素的数组
    int8_t contents[];
} intset;

2.6压缩列表(ziplist)

压缩列表(ziplist)是list和hash的底层实现之一。如果list的每个都是小整数值，或者是比较短的字符串，压缩列表(ziplist)作为list的底层实现。

三、Redis中数据结构的对象

3.1字符串(stirng)对象

string类型有三种编码格式：

• int：整数值，这个整数值可以使用long类型来表示
• embstr：字符串值，这个字符串值的长度小于32字节
• raw：字符串值，这个字符串值的长度大于32字节

3.2列表(list)对象

list类型有两种编码格式：

• ziplist：字符串元素的长度都小于64个字节&&总数量少于512个
• linkedlist：字符串元素的长度大于64个字节||总数量大于512个

3.3哈希(hash)对象

hash类型有两种编码格式：

• ziplist：key和value的字符串长度都小于64字节&&键值对总数量小于512
• hashtable：key和value的字符串长度大于64字节||键值对总数量大于512

3.4集合(set)对象

set类型有两种编码格式：

• intset：保存的元素全都是整数&&总数量小于512
• hashtable：保存的元素不是整数||总数量大于512

3.5有序集合(sortset)对象

sortset类型有两种编码格式：

• ziplist：元素长度小于64&&总数量小于128
• skiplist：元素长度大于64||总数量大于128

3.6Redis对象一些细节

1. 服务器在执行某些命令的时候，会先检查给定的键的类型能否执行指定的命令。
2. Redis的对象系统带有引用计数实现的内存回收机制。
3. Redis会共享值为0到9999的字符串对象
4. 对象会记录自己的最后一次被访问时间，这个时间可以用于计算对象的空转时间。

最后，本文主要讲了一下Redis常用的数据结构，以及这些数据结构的底层设计是怎么样的。整体来说不会太难，因为这些数据结构我们在学习的过程中多多少少都接触过了。

至于我们在使用的时候挑选哪些数据结构作为存储，可以简单看看：

• string–>简单的key-value
• list–>有序列表(底层是双向链表)–>可做简单队列
• set–>无序列表(去重)–>提供一系列的交集、并集、差集的命令
• hash–>哈希表–>存储结构化数据
• sortset–>有序集合映射(member-score)–>排行榜