String
数据结构
struct sdshdr {
int len;//记录buf数组中已使用字节的数量等于SDS所保存字符串的长度
int alloc;//记录对象分配的内存空间
char flag;//记录字符串类型。
char buf[];//字节数组，用于保存字符串
}
示例
string示例.png
这里就可以存储"Redis C",而C只能读取Redis字符串
对C字符串和SDS之间的区别进行总结
| C字符串 | SDS |
|---|---|
| 获取字符串长度的复杂度为O(N) | 获取字符串长度的复杂度为O(1) |
| API是不安全的，可能会造成缓存区溢出 | API是安全的，不会造成缓存区溢出 |
| 修改字符串长度N次必然需要执行N次内存重分配 | 修改字符串长度N次最多需要执行N次内存重分配 |
| 只能保存文本数据 | 可以保存文件或则二进制数据 |
| 可以使用所有<string.h>库中的函数 | 可以使用一部分<string.h>库中的函数 |
链表
数据结构
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 long len;
} list;
示例
image.png
链表的特点
- 链表呗广泛用于实现Redis的个钟功能，比如列表键，发布与订阅、慢查询、监视器等。
- Redis的链表是双向无环链表。
- listIter的结构是为了遍历list使用的。与java Iterator类似
- list定义的三个函数是为了抽象node的value使用。value的类型不同，三个函数的内容也不同，类似于JAVA的抽象方法。
MAP
数据结构
typedef struct dictEntry {
void *key; //键
union { //值
void *val; //字符串或别的值
uint64_t u64; //无符号数字
int64_t s64; //有符号数字
double d; //浮点
} v;
struct dictEntry *next; //指向下个哈希表节点,形成链表
} dictEntry;
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]; //哈希表
long rehashidx; //rehash索引,当rehash不在进行时,值为-1
unsigned long iterators; //当前iterators遍历的数量
} dict;
结构示例
image.png
map特色
- rehash
- 为字典的ht[1]哈希表分配空间,,这个哈希表的空间大小取决于要执行的操作,以及ht[0]当前包含的键值对数量(也即使ht[0].used属性的值):
* 如果执行的是扩展操作,那么ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方幂;
* 如果执行的是收缩操作,那么ht[1]的大小为第一个大于等于ht[0].used的2的n次幂.
- 将保存在ht[0]中的所有键值对rehash到ht[1]上面;
3.当ht[0]包含的所有键值对都迁移到ht[1]之后(ht[0]变为空表),释放ht[0],将ht[1]设置为ht[0],并在ht[1]新创建一个空白哈希表,为下一次rehash做准备.
- rehash的扩展与收缩条件
- 服务器当前没有执行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的负载因子大于等于1.
- 服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表负载因子大于等于5.
- 哈希表的负载因子小于0.1时,程序自动开始对哈希表执行收缩操作.
负载因子公式: load_factor = ht[0].used / ht[0].size;
java-hashMap负载因子为0.75 转换为redis的负载因子为 0.75;
- 渐进式rehash
如果 ht[0] 里只保存着四个键值对， 那么服务器可以在瞬间就将这些键值对全部 rehash 到 ht[1] ； 但是， 如果哈希表里保存的键值对数量不是四个， 而是四百万、四千万甚至四亿个键值对， 那么要一次性将这些键值对全部 rehash 到 ht[1] 的话， 庞大的计算量可能会导致服务器在一段时间内停止服务。
因此， 为了避免 rehash 对服务器性能造成影响， 服务器不是一次性将 ht[0] 里面的所有键值对全部 rehash 到 ht[1] ， 而是分多次、渐进式地将 ht[0] 里面的键值对慢慢地 rehash 到 ht[1] 。
以下是哈希表渐进式 rehash 的详细步骤：
- 为 ht[1] 分配空间， 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。 - 在 rehash 进行期间，ht[0]只会执行删除'查找,对字典执行添加只会作用于ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。
- 随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1， 表示 rehash 操作已完成。
代码示例
//新增替换的时候调用该方法
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
long index;
dictEntry *entry;
dictht *ht;
//如果当前正在rehash,则调用一步rehash,转移一个table数组
if (dictIsRehashing(d)) _dictRehashStep(d);
/* Get the index of the new element, or -1 if
* the element already exists. (查找key,如果存在返回-1)*/
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
return NULL;
/* Allocate the memory and store the new entry.
* Insert the element in top, with the assumption that in a database
* system it is more likely that recently added entries are accessed
* more frequently. (分配内存,rehash时插入到ht[1]上面)*/
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;
/* Set the hash entry fields. (设置key值)*/
dictSetKey(d, entry, key);
return entry;
}
跳跃表
数据结构
typedef struct zskiplistNode {
sds ele; //对象
double score; //分值
struct zskiplistNode *backward; //后退指针
struct zskiplistLevel { //层
struct zskiplistNode *forward; //前进指针
unsigned long span; //跨度
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;//头尾节点
unsigned long length; //list长度
int level; //表中层数最大的节点层数
} zskiplist;
示例
跳表结构示例
如果不懂跳表的数据结构可以阅读一下:http://zhangtielei.com/posts/blog-redis-skiplist.html
跳表特色
- 跳跃表示有序集合的底层实现之一
- Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成,其中zskiplist用于保存跳跃表信息,而zskiplistNode则用于标示跳跃表节点.
3.每个跳跃表节点的层高都是1至64之间的随机数.
4.在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的成员对象可以相同(<<redis设计与实现>>说对象唯一,是因为跳跃表永远都是和dict一起使用,所以已经过滤掉了重复对象)
代码:
//插入代码
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level;
//校验数据
serverAssert(!isnan(score));
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
/* store rank that is crossed to reach the insert position(查询插入位置) */
rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < 0)))//因为level[0]是前指针,所以在遍历i=0时是往前遍历,找到插入的前一个指针
{
rank[i] += x->level[i].span;
x = x->level[i].forward;
}
update[i] = x;
}
level = zslRandomLevel();//获取随机level
...省略算法代码
x->backward = (update[0] == zsl->header) ? NULL : update[0];
if (x->level[0].forward) //level[0]就是backward一样
x->level[0].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
return x;
}
- 跳跃表中的节点按照分值大小进行排序,当分值相同时,节点按照成员对象大小进行排序.
整数集合
数据结构
typedef struct intset {
uint32_t encoding; //编码方式INT16,INT32,INT64
uint32_t length; //数量
int8_t contents[]; //保存元素的数组
} intset;
示例
image.png
image.png
整数列表特色
- 整数集合是集合键的底层实现之一
- 不同的编码是为了节约内存,数字小的时候会用INT16的方式
- 整数集合只支持升级操作,不支持降级操作
- 数组以有序,无重复的方式保存集合
代码示例:
//插入代码
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
uint8_t valenc = _intsetValueEncoding(value);
uint32_t pos;
if (success) *success = 1;
if (valenc > intrev32ifbe(is->encoding)) {
//升级编码长度
return intsetUpgradeAndAdd(is,value);
} else {
//查询value是否存在返回1,不存在返回0 pos返回前一个位置
if (intsetSearch(is,value,&pos)) {
if (success) *success = 0;
return is;
}
is = intsetResize(is,intrev32ifbe(is->length)+1);//扩容,删除也会清空内存
if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);//不是最后一个移动位置
}
_intsetSet(is,pos,value);//设置值
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
压缩列表
数据结构
压缩列表没有数据结构,只有一个大的内存快,通过内存地址计算各个属性
组成部分视图:
代码实现:
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))//定义ziplist头部分
#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl))) //记录zip的大小
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t)))) //记录zip尾节点距离压缩列表起始地址有多少字节,定位尾节点地址
#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))//节点的长度
entry的数据结构:
typedef struct zlentry {
unsigned int prevrawlensize; //记录了前一个节点的长度，通过这个值，可以进行指针计算，从而跳转到上一个节点。
unsigned int prevrawlen; // 前一个entry长度
unsigned int lensize; // entry的字节大小
unsigned int len;
unsigned int headersize; /* prevrawlensize + lensize. */
unsigned char encoding; //节点类型可能是整数或者字符串
unsigned char *p; /* Pointer to the very start of the entry, that
is, this points to prev-entry-len field. */
} zlentry;
