共计 4240 个字符，预计需要花费 11 分钟才能阅读完成。
Redis 基础数据结构
基础数据结构
sds 简单动态字符串
数据结构
typedef struct sdstr{int len // 字符串分配的字节
int free // 未使用的字节数
char buff[] // 存储字符串的数组
}sds 是字符串对象的底层实现之一
sds 的特性
赋值操作会统计字符串的长度然后将字符串存入 buff 里面, 同时设定长度和使用的长度
例如 “hello” 这个字符串的存储结构如下
{len:5,
free:0,
buff:['h','e','l','l','o','\0']
}修改的时候会比较麻烦, 分为两种情况
一是由段字符串变长: 例如: 由 ”hello” 变为 ”hello,redis”.
这个时候系统会检查原本的 sds 字符串是否有空余空间, 剩余空间为 0, 会分配等同于修改后字符串长度的剩余空间给 sds, 这个时候字符串的 free 属性会变为 11, 然后执行 sdscat(), 这个时候 buff 会变为 [‘h’,’e’,’l’,’l’,’o’,’,’,’r’,’e’,’d’,’i’,’s’,’\0′], 然后将字符串长度 len 修改为 11
最终结构如下
{len:11,
free:11,
buff:['h','e','l','l','o',',','r','e','d','i','s','\0']
}ps: 当长度小于 1M 是翻倍扩容, 超过 1M 时是以 1M 为标准定量扩容
二是由长字符串变短
例如: 由 ”hello,redis” 变为 ”redis”, 这个时候会释放多余空间, 同时把 free 值设为多出来的空间, 以便下次使用方便
修改后的结构大概如下
{len:5, // 字符串长度
free:17, // 原本 11, 加上释放到的 6 个字节
buff:['r','e','d','i','s','\0']
}需要释放的时候可以手动调用函数来释放空间
为什么要使用 sds?
- sds 可以杜绝缓冲区溢出的问题, 获取字符串长度复杂度为常数
- 二进制安全,sds 使用 len 属性来判断字符串的结束
- 减少字符串修改时的内存重分配次数
链表
数据结构
// 链表节点
typedef struct listNode{struct listNode *pre;
struct listNode *next;
void *value;
}listNode;
// 链表
typedef struct list{listNode * head; // 头节点
listNode * tail; // 尾节点
unsigned long len; // 节点数量
void *(*dup)(void *ptr); // 节点值复制函数
void (*free)(void *ptr); // 节点值释放函数
void (*match)(void *ptr,void *key); // 节点值对比函数
}链表是列表对象的底层实现之一
链表在 redis 中主要负责的是存储和维护某一类对象, 所常用到的操主要有遍历, 修改等
链表在 redis 中使用极为广泛,redis 的事务, 发布与订阅, 服务器中维护的 redisClient 信息等都是用链表结构进行的存储
字典
数据结构
// 哈希表
typedef struct dictht{dictEntry **table; // 哈希节点
unsigned long size; // 哈希表大小
unsigned long sizemask; // 哈希表掩码, 用于计算索引值
unsigned long used; // 已有节点数量
} dictht;
// 哈希节点
typedef struct dictEntry{void *key;// 键
union {void *val;
uint64_tu64;
int64_ts64;
} v;
struct dictEntry *next;
}dictEntry;
// 字典
typedef struct dict{dictType *type; // 类型特定函数
void *privdata; // 私有数据
dictht ht[2]; // 哈希表 ht[0]常用 ht[1]rehash 时候使用
int rehashidx; //rehash 标识
}dict;字典是数据库的底层实现
解决键冲突
redis 使用链地址法 (separate chaining) 来解决键冲突, 当两个键的 index 值相同时, 会把第二个键放到第一个键的前面, 查询时对这个 index 的哈希节点链表进行遍历
rehash:
当哈希表的负载因子 (load factor) 大于设定值时(平时为 1, 在 BGREWRITEAOF 时为 5), 哈希表会进行 rehash 操作
rehash 采用渐进式的方式进行执行, 具体流程就是把 ht[0]里面的数据重新进行哈希计算放到 ht[1], 此时的哈希查询操作两个表同时提供服务, 写入操作则只有 ht[1]提供, 这样 ht[0]处于只减不增的状态, 最终当 ht[0]里面的所有数据都被转移到 ht[1]时,rehashidx 被设为 -1, 表明 rehash 结束, 删除 ht[0], 并将 ht[1]设为 ht[0], 同时重新分配新的 ht[1]
ps: 负载因子 = used /size;
跳跃表
数据结构
// 跳跃表节点
typedef struct zskiplistNode {
sds ele;
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;跳跃表是有序集合的底层实现之一
跳跃表中的头结点不计算在 length 长度之内, 跳跃表的节点排序按照分值从小到大排序
每次创建新节点的时候,redis 会根据幂次定律随机生成一个 1 -32 的层数作为 level 数组的大小, 每个节点都有指向表尾方向的前进指针和之前表头方向的后退指针, 这两个指针可以让程序方便的遍历所有节点, 层的跨度用于记录两点之间的距离, 跨度可以用来计算 rank 值. 节点的分值是一个 double 值, 节点的对象是一个指针, 指向一个保存着 sds 字符串的字符串对象(下一节讲 redis 对象)
整数集合
数据结构
typedef struct intset{uint32_t encoding;// 编码方式
uint32_t length;// 集合包含的元素数量
int8_t contents[];// 保存元素的数组
} intset;顾名思义整数集合是用来保存整数值的抽象数据结构
集合中不会出现重复元素
contents 数组中保存的整数值有小到大排列
length 等于 contents 的长度
虽然 contents 的定义是 int8_t 但实际上 contents 的值类型由 encoding 决定
升级
当一个新元素超过原来整数集合 encoding 定义的值的类型时, 会进行升级, 升级结果会使集合的 encoding 变成所有数组中元素的值最大的数据类型, 并且不支持降级
例如: 有一个整数集合[1,2,3], 本身的编码为 int8, 现在增加一个 300 的数字进该集合, 会导致集合的编码升级为 int16, 这个时候列表的大小由 8 ×3=24 变为 16×4=64, 即便 int8 可以存储前三个值, 但是为了简单起见, 仍然会为集合中每一个元素分配同样的空间
压缩列表
压缩列表被用作列表键和哈希键的底层实现
压缩列表属于特殊的结构, 是一种数据存储的方式, 目的是为了节约内存, 是一种采用特殊编码的连续内存块组成的顺序型 (sequential) 数据结构.
大致结构如下:
| zlbytes | zltail | zllen | entry1 | entry2 | … | zlend |
|---|
每个压缩列表由如下三部分组成
| previous_entry_length | encoding | content |
|---|---|---|
| 前一节点的长度 | 记录 content 的类型和长度 | 节点的值 |
如果前一个节点长度小于 254 字节,previous_entry_length 会使用 1 字节空间保存这个长度, 如果大于 254 字节, 将使用 5 字节长度保存这个值, 这个机制会引起 ” 连锁更新 ”
连锁更新: 假设现有连续的三个压缩列表节点 l1,l2,l3, 长度分别为 253,253,253, 现在往第一个节点前添加一个长度超过 254 的节点, 这个时候 l1 要给 previous_entry_length 分配 5 个字节来存储长度, 所以列表本身长度会变为 257, 这将导致 l2 也需要 5 字节存储 l1 的长度,l3 也会产生同样的变化, 这样由一个列表操作引起的一系列更新操作成为连锁更新。
下面关于 Redis 的文章您也可能喜欢，不妨参考下：
Ubuntu 14.04 下 Redis 安装及简单测试 http://www.linuxidc.com/Linux/2014-05/101544.htm
Redis 主从复制基本配置 http://www.linuxidc.com/Linux/2015-03/115610.htm
CentOS 7 下 Redis 的安装与配置 http://www.linuxidc.com/Linux/2017-02/140363.htm
Ubuntu 14.04 安装 Redis 与简单配置 http://www.linuxidc.com/Linux/2017-01/139075.htm
Ubuntu 16.04 环境中安装 PHP7.0 Redis 扩展 http://www.linuxidc.com/Linux/2016-09/135631.htm
Redis 单机 & 集群离线安装部署 http://www.linuxidc.com/Linux/2017-03/141403.htm
CentOS 7.0 安装 Redis 3.2.1 详细过程和使用常见问题 http://www.linuxidc.com/Linux/2016-09/135071.htm
Ubuntu 16.04 环境中安装 PHP7.0 Redis 扩展 http://www.linuxidc.com/Linux/2016-09/135631.htm
Ubuntu 15.10 下 Redis 集群部署文档 http://www.linuxidc.com/Linux/2016-06/132340.htm
Redis 实战 中文 PDF http://www.linuxidc.com/Linux/2016-04/129932.htm
本文永久更新链接地址：http://www.linuxidc.com/Linux/2017-06/145175.htm
