关于golang:redis数据结构

从本次开始，对 Redis 设计与实现进行浏览及相干读书笔记的记录。Redis 版本为 3.0

<!– more –>

sds数据结构位于sds.h/sdshdr

/*
 * 保留字符串对象的构造
 */
struct sdshdr {
    // buf 中已占用空间的长度
    int len;
    // buf 中残余可用空间的长度
    int free;
    // 数据空间
    char buf[];};

绝对于 C 语言的字符串，SDS 的长处在于

常数复杂度获取字符串长度
杜绝缓冲区溢出
缩小批改字符串所带来的内存重新分配（留神，开释空间时候，不会真的开释，而是设置 free 的值）

链表的相干代码在 adlist.h 中

链表节点listNode

/*
 * 双端链表节点
 */
typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

由多个 listNode 组成的双端链表

链表构造list

/*
 * 双端链表构造
 */
typedef struct list {
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值开释函数
    void (*free)(void *ptr);
    // 节点值比照函数
    int (*match)(void *ptr, void *key);
    // 链表所蕴含的节点数量
    unsigned long len;
} list;

redis中的字典应用哈希表实现，其代码在 dict.h 中

哈希表构造dictht

/*
 * 哈希表
 *
 * 每个字典都应用两个哈希表，从而实现渐进式 rehash。*/
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;    
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1 比方 7 号，当计算索引时候，7&sizemask 就能够失去
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

其中 dictEntry 为一个键值对

/*
 * 哈希表节点
 */
typedef struct dictEntry {    
    // 键
    void *key
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，造成链表 表明是一个链地址法解决哈希抵触
    struct dictEntry *next;
} dictEntry;

上面为了形象示意一个哈希表，给出一个例子

上面给出一个多个 dictEntry 连贯的哈希表

最终 Redis 中的字典数据结构如下

/*
 * 字典
 */
typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 公有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 目前正在运行的平安迭代器的数量
    int iterators; /* number of iterators currently running */
} dict;

/*
 * 字典类型特定函数
 */
typedef struct dictType {
    // 计算哈希值的函数 redis 默认的函数算法为 murmurhash2
    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;

redis 中的跳跃表构造代码为 redis.h/zskiplistNode 和redis.h/zskiplist

/* ZSETs use a specialized version of Skiplists */
/*
 * 跳跃表节点
 */
typedef struct zskiplistNode {
    // 成员对象
    robj *obj;
    // 分值 留神 redis 跳跃表依照节点从小到大排列
    double score;
    // 后退指针
    struct zskiplistNode *backward;
    // 层 数组大小依照幂次定律（越大的数呈现概率越小）1-32 随机数字
    struct zskiplistLevel {
        // 后退指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];} zskiplistNode;

/*
 * 跳跃表
 */
typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
} zskiplist;

上面给出一个简略的跳跃表例子

后退指针用于遍历跳跃表，上面的虚线为遍历过程

整数汇合 `intset`

当一个汇合外面只有整数值元素时候，且元素数量不超过 REDIS_SET_MAX_INTSET_ENTRIES 时候，汇合底层采纳整数汇合

#define REDIS_SET_MAX_INTSET_ENTRIES 512 /* 汇合中元素个数小于该值，set 底层应用 intset*/

redis 中整数汇合代码位于intset.h/intset

typedef struct intset {   
    // 编码方式
    uint32_t encoding;
    // 汇合蕴含的元素数量
    uint32_t length;
    // 保留元素的数组 依照从小到大的程序，且不反复
    int8_t contents[];} intset;

contents数组尽管是 int8_t，然而外面寄存的数据的实在类型由encoding 字段决定

降级操作

如果往下面的整数汇合中 append 类型为 int32 的 65535，则会产生降级，降级的过程次要包含将每个元素所占空间进行裁减，而后设置 encoding，降级完后为

降级操作

留神整数汇合无奈进行降级，降级之后，会始终继续该编码

压缩列表 `ziplist`

压缩列表其实就是一块间断内存，一个压缩列表包含多个节点（entry），每个 entry 保留一个字节数组或者整数值。在 redis 源码中，压缩列表没有数据结构代码定义，压缩列表是一种通过内存非凡编码方式实现的数据结构。他是通过定义一些基地址，而后应用偏移量来定义 ziplist，其中大量应用了宏函数定义

/*
 * ziplist 属性宏
 */
// 定位到 ziplist 的 bytes 属性，该属性记录了整个 ziplist 所占用的内存字节数
// 用于取出 bytes 属性的现有值，或者为 bytes 属性赋予新值
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))
// 定位到 ziplist 的 offset 属性，该属性记录了达到表尾节点的偏移量
// 用于取出 offset 属性的现有值，或者为 offset 属性赋予新值
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
// 定位到 ziplist 的 length 属性，该属性记录了 ziplist 蕴含的节点数量
// 用于取出 length 属性的现有值，或者为 length 属性赋予新值
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
// 返回 ziplist 表头的大小
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
// 返回指向 ziplist 第一个节点（的起始地位）的指针
#define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)
// 返回指向 ziplist 最初一个节点（的起始地位）的指针
#define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
// 返回指向 ziplist 末端 ZIP_END（的起始地位）的指针
#define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)

其中，redis 对 entry 应用了数据结构形容，如下代码ziplist.c/zlentry

/*
 * 保留 ziplist 节点信息的构造
 */
typedef struct zlentry {
    // prevrawlen：前置节点的长度
    // prevrawlensize：编码 prevrawlen 所需的字节大小
    unsigned int prevrawlensize, prevrawlen;
    // len：以后节点值的长度
    // lensize：编码 len 所需的字节大小
    unsigned int lensize, len;
    // 以后节点 header 的大小
    // 等于 prevrawlensize + lensize
    unsigned int headersize;
    // 以后节点值所应用的编码类型
    unsigned char encoding;
    // 指向以后节点的指针
    unsigned char *p;
} zlentry;

ziplist 的创立

/* Create a new empty ziplist. 
 *
 * 创立并返回一个新的 ziplist 
 *
 * T = O(1)
 */
unsigned char *ziplistNew(void) {
    // ZIPLIST_HEADER_SIZE 是 ziplist 表头的大小
    // 1 字节是表末端 ZIP_END 的大小
    unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
    // 为表头和表末端调配空间
    unsigned char *zl = zmalloc(bytes);
    // 初始化表属性
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
    ZIPLIST_LENGTH(zl) = 0;
    // 设置表末端
    zl[bytes-1] = ZIP_END;

    return zl;
}

因为压缩列表次要就是为了节约内存，因而对于不同的数据，其编码方式不一样，后面咱们曾经晓得，entry 中次要放字节数组和整数，下表给出两种数据不同长度时候的编码

<center>    <!-- 将图片和文字居中 -->
<img src="

https://smypicture.oss-cn-bei…g”

     alt="无奈显示图片时显示的文字"
     style="zoom: 这里写图片的缩放百分比"/>
<br>        <!-- 换行 -->
字节数组编码    <!-- 题目 -->
</center>

</div>

<center>    <!-- 将图片和文字居中 -->
<img src="

https://smypicture.oss-cn-bei…g”

     alt="无奈显示图片时显示的文字"
     style="zoom: 这里写图片的缩放百分比"/>
<br>        <!-- 换行 -->
整数编码    <!-- 题目 -->
</center>

</div>

本次首先对 Redis 的相干数据结构进行介绍。Redis 对象次要分为 5 种：REDIS_STRING、REDIS_LIST、REDIS_HASH、REDIS_SET、REDIS_ZSET。上面首先给出 Redis 中对对象的代码示意

// 对象类型
#define REDIS_STRING 0
#define REDIS_LIST 1
#define REDIS_SET 2
#define REDIS_ZSET 3
#define REDIS_HASH 4

#define REDIS_LRU_BITS 24
#define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */
typedef struct redisObject {
    // 类型   类型说明符      位域名：位域长度   标识 type 占 4 个二进制位 因为有可能不须要一个残缺的字节
    // 1 个字节 8 位
    unsigned type:4;
    // 编码
    unsigned encoding:4;
    // 对象最初一次被拜访的工夫
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    // 援用计数
    int refcount;
    // 指向理论值的指针
    void *ptr;
} robj;

首先看到有 2 个字段，为类型和编码，类型就是 redis 的 5 种类型，编码就是这个类型底层是用什么编码方式实现

但实际上，Redis 的外部并不只是这 5 种对象，对于下面 5 种对象，都有几种底层实现形式，上面给出各数据结构底层实现的对应形式

REDIS_STRING 示意 redis 中的字符串类型，其底层由以下三种实现形式

如果一个字符串对象保留的是整数值，且这个整数值能够用 long 类型示意，则字符串对象会奖整数值保留在字符串对象的 ptr 属性中，此时会将 ptr 的 void* 转换为 long

127.0.0.1:6379> set number "1"
OK
127.0.0.1:6379> object encoding number
"int"

如果字符串保留的是一个字符串值，且长度大于 32 字节，redis 的字符串对象就会采纳简略动静字符串（SDS）实现

127.0.0.1:6379> set longstr "Hello, my name is Shi Linkun, is a programmer who loves code, I hope that each blog can let myself consolidate their knowledge, but also let everyone get a little knowledge, thank you"
OK
127.0.0.1:6379> object encoding longstr
"raw"

这里先不对 SDS 进行具体简介，后续独自对其进行形容

如果字符串对象保留的是一个字符串，且长度小于等于 32 字节，则应用 embstr 编码实现

127.0.0.1:6379> set story "hello my name is shilinkun"
OK
127.0.0.1:6379> object encoding story
"embstr"

留神 redis3.0 版本中理论距离为 39 字节

#define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 39
robj *createStringObject(char *ptr, size_t len) {if (len <= REDIS_ENCODING_EMBSTR_SIZE_LIMIT)
        return createEmbeddedStringObject(ptr,len);
    else
        return createRawStringObject(ptr,len);
}

为什么是 39 字节，这里参考这个知乎的解释

embstr 是一块间断的内存区域，由 redisObject 和 sdshdr 组成。其中 redisObject 占 16 个字节，当 buf 内的字符串长度是 39 时，sdshdr 的大小为 8 +39+1=48，那一个字节是 ’\0’。加起来刚好 64。是不是发现了什么？
typedef struct redisObject {
 unsigned type:4;
 unsigned encoding:4;
 unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
 int refcount;
 void *ptr;
} robj;
struct sdshdr {
 unsigned int len;
 unsigned int free;
 char buf[];};
从 2.4 版本开始，redis 开始应用 jemalloc 内存分配器。这个比 glibc 的 malloc 要好不少，还省内存。在这里能够简略了解，jemalloc 会调配 8，16，32，64 等字节的内存。embstr 最小为 16+8+8+1=33，所以最小调配 64 字节。当字符数小于 39 时，都会调配 64 字节。

int->raw

向一个保留整数数值的字符串对象应用 APPEND 命令，就会使得 int 转变为 raw
embstr->raw

对 embstr 类型的字符串，执行任何的批改命令，都会变为 raw

字符串命令的实现在 t_string.c 中

列表对象底层次要由 2 种编码方式：REDIS_ENCODING_ZIPLIST、REDIS_ENCODING_LINKEDLIST

ziplist 是指应用压缩列表实现

linklist 是应用双端链表实现

redis.h

#define REDIS_LIST_MAX_ZIPLIST_ENTRIES 512 /*list 中元素个数小于该值，list 底层应用 ziplist*/
#define REDIS_LIST_MAX_ZIPLIST_VALUE 64 /*list 中所有的字符串长度小于该值，list 底层应用 ziplist*/

上述两个宏定义别离与 redis 的配置文件中 list-max-ziplist-entries 和list-max-ziplist-value对应

哈希对象次要有 2 种编码方式，REDIS_ENCODING_ZIPLIST和REDIS_ENCODING_HT

ziplist 作为底层实现，先放入键，后放入值

#define REDIS_HASH_MAX_ZIPLIST_ENTRIES 512 // 哈希对象保留的键值对数量小于 512 个，应用 ziplist;
#define REDIS_HASH_MAX_ZIPLIST_VALUE 64 // 哈希对象保留的所有键值对的键和值的字符串长度都小于 64 字节, 应用 ziplist;

上述两个宏定义别离与 redis 的配置文件中 hash-max-ziplist-entries 和hash-max-ziplist-value对应

汇合的底层编码方式也是两种：REDIS_ENCODING_INTSET和REDIS_ENCODING_HT

应用该编码方式作为汇合的底层实现时候，个别是整数汇合，比方

应用哈希表作为汇合的底层实现形式时，所有的值作为键，但对应的值为 null

#define REDIS_SET_MAX_INTSET_ENTRIES 512 /* 汇合中元素个数小于该值，且全为整数，set 底层应用 intset*/

对应的 redis 配置文件选项为set-max-intset-entries

有序汇合底层实现为：REDIS_ENCODING_ZIPLIST和REDIS_ENCODING_SKIPLIST

当应用压缩列表作为有序汇合的底层实现时候，压缩列表的 entry 有 2 个值，一个是值，一个是得分，同时依照得分由小到大进行排列

当应用跳跃表进行底层实现时候，一个有序汇合同时包含：

一个跳跃表
一个字典

为什么有序汇合须要同时应用跳跃表和字典来实现?

在实践上，有序汇合能够独自应用字典或者跳跃表的其中一种数据结构来实现，但无论独自应用字典还是跳跃表，在性能上对比起同时应用字典和跳跃表都会有所升高。举个例子，如果咱们只应用字典来实现有序汇合，那么尽管以 O(1)复杂度查找成员的分值这一个性会被保留，然而，因为字典以无序的形式来保留汇合元素，所以每次在执行范畴型操作——比方 ZRANK、ZRANGE 等命令时，程序都须要对字典保留的所有元素进行排序，实现这种排序须要至多 O(NlogN)工夫复杂度，以及额定的 O(N)内存空间（因为要创立一个数组来保留排序后的元素)。

另一方面，如果咱们只应用跳跃表来实现有序汇合，那么跳跃表执行范畴型操作的所有长处都会被保留，但因为没有了字典，所以依据成员查找分值这一操作的复杂度将从 O(1)回升为 O(logN)。因为以上起因，为了让有序汇合的查找和范畴型操作都尽可能快地执行，Redis 抉择了同时应用字典和跳跃表两种数据结构来实现有序汇合。

#define REDIS_ZSET_MAX_ZIPLIST_ENTRIES 128 /* 有序汇合中元素个数小于该值，zset 底层应用 ziplist*/
#define REDIS_ZSET_MAX_ZIPLIST_VALUE 64 /* 有序汇合中元素长度小于该值，zset 底层应用 ziplist*/

上述两个宏定义别离与 redis 的配置文件中 zset-max-ziplist-entries 和zset-max-ziplist-value对应

这一次把 redis 的数据结构和对应的对象实现形式大抵说了一遍，最重要的还是什么时候应用什么数据结构，并且各种数据结构一些命令的工夫复杂度等，这些其实还没有进行论述，前面会独自开一章进行解说，因为在理论我的项目中，咱们要针对不同场景对数据结构进行选取

本人的网址：www.shicoder.top
欢送加群聊天 452380935

本文由博客一文多发平台 OpenWrite 公布！

关于golang:redis数据结构

引言

数据结构

简略动静字符串 SDS

链表

字典

跳跃表

整数汇合 `intset`

压缩列表 `ziplist`

对象

REDIS_STRING

REDIS_ENCODING_INT

REDIS_ENCODING_RAW

REDIS_ENCODING_EMBSTR

三个编码的转换

相干命令

REDIS_LIST

REDIS_ENCODING_ZIPLIST

REDIS_ENCODING_LINKLIST

编码转换

REDIS_HASH

REDIS_ENCODING_ZIPLIST

REDIS_ENCODING_HT

编码转换

REDIS_SET

REDIS_ENCODING_INTSET

REDIS_ENCODING_HT

编码转换

REDIS_ZSET

REDIS_ENCODING_ZIPLIST

REDIS_ENCODING_SKIPLIST

编码转换

总结

Just My Socks（注册教程内含优惠码）

关于golang:redis数据结构

引言

数据结构

简略动静字符串 SDS

链表

字典

跳跃表

整数汇合 intset

压缩列表 ziplist

对象

REDIS_STRING

REDIS_ENCODING_INT

REDIS_ENCODING_RAW

REDIS_ENCODING_EMBSTR

三个编码的转换

相干命令

REDIS_LIST

REDIS_ENCODING_ZIPLIST

REDIS_ENCODING_LINKLIST

编码转换

REDIS_HASH

REDIS_ENCODING_ZIPLIST

REDIS_ENCODING_HT

编码转换

REDIS_SET

REDIS_ENCODING_INTSET

REDIS_ENCODING_HT

编码转换

REDIS_ZSET

REDIS_ENCODING_ZIPLIST

REDIS_ENCODING_SKIPLIST

编码转换

总结

Just My Socks（注册教程 内含优惠码）

整数汇合 `intset`

压缩列表 `ziplist`

Just My Socks（注册教程内含优惠码）