redis数据结构设计

一. 数据结构简介

要搞清楚redis数据结构，首先需要知道和redis数据相关的三层结构：

五种数据类型

String（字符串）、List（列表）、Hash（哈希）、Set（集合）和 Sorted Set（有序集合）

type key --- 获取key的value类型

六种底层存储结构

简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组

依据具体存储的数据决定的——编码数据类型

object encoding key --- 获取key的value的实际编码类型

数据类型与底层存储结构

二. K-V组织结构

redis是非关系型的键值对数据库。底层实现类似java的HashMap，用数组+链表实现。数组就是keyhash后取模槽位，链表解决hash冲突。

2.1 redisDB

redis 包括16个数据库——redisDb。存储数据放在里边dict中

typedef struct redisDb {dict *dict; ----- kv储存                 dict *expires;     -- 过期时间dict *blocking_keys;       --    阻塞队列dict *ready_keys;      --- key和客户端关系     dict *watched_keys;  --- watch实现等       int id;                      long long avg_ttl;           unsigned long expires_cursor;  list *defrag_later;          
} redisDb;

2.2 dict

dict 为真实存储k-v关系的地方。储存关系从外到内dict-->dictht-->dictEntry

typedef struct dict {dictType *type;void *privdata;dictht ht[2]; --- 两个数组存储。一个用于服务，一个用于rehashlong rehashidx; unsigned long iterators;  
} dict;typedef struct dictht {dictEntry **table;    unsigned long size;unsigned long sizemask;unsigned long used;
} dictht;
typedef struct dictEntry {void *key; ----- keyunion {     ----value，四个字段一个只会用一个void *val;  uint64_t u64;int64_t s64;double d;} v;struct dictEntry *next; --- hash冲突
} dictEntry;typedef struct redisObject {unsigned type:4;     ---- 数据类型，用于约束客户端命令 4bitunsigned encoding:4;  --- 编码数据类型4bitunsigned lru:LRU_BITS;   24bitint refcount;    ----引用计数。4bytevoid *ptr;   --- 真实存储内存的指针。8byte
} robj;

2.3 渐进式rehash

dict 数据结构中，dictht ht[2]存储数据——ht[0]和ht[1]——我们称为哈希表1和哈希表2. 一开始，刚插入数据时，默认使用哈希表 1，此时的哈希表 2 并没有被分配空间。随着数据逐步增多，Redis 开始执行 rehash，这个过程分为三步：
-1.给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
-2.把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；
-3.释放哈希表 1 的空间
第二步涉及大量的数据拷贝，如果一次性把哈希表 1 中的数据都迁移完，会造成 Redis 线程阻塞，无法服务其他请求.Redis 采用了渐进式 rehash来解决这个问题。

第二步拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries.

redis本身还会有一个定时任务在执行rehash，如果没有键值对操作时，这个定时任务会周期性地搬移一些数据到新的哈希表中，这样可以缩短整个rehash的过程。

三. String 详解

String 类型的底层实现只有一种数据结构——简单动态字符串sds

3.1 简单动态字符串实现详解

3.1.1 redis 3.2版本之前

实现源码

struct sdshdr {int len;       --- 已使用长度int free;     ---  剩余空间， 不是用多少申请多少，后边详细介绍char buf[]; ---  真正存储数据
};

实现问题

3.2版本实现，用int类型存储长度和剩余空间。int占用4个字节，每个字符一个字节。当存储字符很少时，造成严重的空间浪费。

3.1.2 redis 3.2 之后版本

实现源码

3.2版本之后，根据实际存储的字符长度采用不同的结构来存储。一可以节省空间，二容易实现内存缓存行适配。

typedef char *sds;struct __attribute__ ((__packed__)) sdshdr5 {unsigned char flags; /* 3 lsb of type, and 5 msb of string length */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {uint8_t len; /* used */uint8_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {uint16_t len; /* used */uint16_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {uint32_t len; /* used */uint32_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
........
// 不同数据类型选择逻辑
static inline char sdsReqType(size_t string_size) {if (string_size < 32)  return SDS_TYPE_5;if (string_size < 0xff) //2^8 -1  return SDS_TYPE_8;if (string_size < 0xffff) // 2^16 -1  return SDS_TYPE_16;if (string_size < 0xffffffff)  // 2^32 -1 return SDS_TYPE_32;return SDS_TYPE_64;
}unsigned char flags-- 用一个字节的前3位表示不同的数据类型。SDS_TYPE_5 一个字节的后5位可以存储32以内的长度。

3.2 为什么没有使用c语言字符数组实现

1. 二进制安全的数据结构-- 不同语言客户端通信
1. 提供了内存预分配机制，避免频繁扩容
1. 兼容c语言的函数库

3.3 常用API

String 常用API/> help @string /> SET/GET 
/> SETNX 
/> GETRANGE/SETRANGE/> INCR/INCRBY/DECR/DECRBY/> GETBIT/SETBIT/BITOPS/BITCOUNT/> MGET/MSET

3.3 String 编码数据类型补充

对一个String类型数据执行 object encoding ${key}. 可能返回：

embstr 字符串

线程操作系统缓存行大小为64字节，一个redisObject 占用16个字节。String类型sds结构初数据以为大约4个字节，那么String本身44个字节以内，一个缓存行就可以存储。这种情况存储为包装字符串结构，embstr

redis存储String value数据时，会检查是否是20位（int最大值）程度以内的数字，如果是底层int编码存储。因为redisObject #ptr 占8个字节。

raw 引用

整体结构存储大于一个缓存行则用指针，存储在其他内存中。

代码块

三. List 详解

3.1常用命令

/> help @listLPUSH key element [element ...] --左追加
RPOP key      --右获取
RPUSH key element [element ...]  --右追加
LPOP key  --左获取
BLPOP key [key ...] timeout   -- 堵塞获取
BRPOP key [key ...] timeout
BRPOPLPUSH source destination timeout
RPOPLPUSH  source destination
LINDEX key index   --索引获取
LLEN key   --长度
LINSERT key BEFORE|AFTER pivot element --指定元素前后添加
LRANGE key start stop --- 遍历
LREM key count element  -- 删除
LSET key index element   -- 指定位置
LTRIM key start stop  --截取

3.2 底层结构

从常用命令可以看出，list支持左右操作，很自然想到使用双端链表实现。通过pre，next指针支持遍历。但是一个指针占用8个字节，造成我们很大比例的内存空间被指针占用。所以redis做了优化。redis采用双端链表（quicklist）+ ziplist（压缩链表实现）作为底层实现list。

3.2.1 ziplist

ziplist结构

entry结构

zIbytes 当前ziplist 占用大小
zItail 当前ziplist 末尾指针，支持从后遍历
zllen 当前ziplist entry长度
zlend 标识数据结尾一个字节

对于entry：

prerawlen ：前一个entry的长度，便于访问前一个entry的地址。根据前一个数据长度可能占用1字节或者4个字节
len ：当前entry的长度，便于访问后一个entry的地址。这个长度比较复杂

len长度规则
data：数据

3.2.2 quicklist

redis 不可能将所有数据都放在ziplist中，这样随机访问性能很差。redis通过双端链表来维护ziplist之间的关系。

quicklist

//  单个ziplist节点最大能存储  8kb  ,超过则进行分裂,将数据存储在新的ziplist节点中。 -2 8kb，-1 4kb。再大不推荐
list-max-ziplist-size  -2   
//  0 代表所有节点，都不进行压缩，1表示首位不压缩，其他压缩。依次类推
list-compress-depth  1

四. Hash 详解

4.1常用命令

/> help  @hash 
HSET key field value [field value ...]
HGET key field
HMGET key field [field ...]
HKEYS key
HGETALL key
HVALS key
HEXISTS key field
HDEL key field [field ...]
HINCRBY key field increment
HINCRBYFLOAT key field increment
HLEN key
HSCAN key cursor [MATCH pattern] [COUNT count]
HSETNX key field value
HSTRLEN key field

4.2底层结构

hash 值底层结构用的就是 redisDb中的dict。不同点在于对于value，满足一定条件时使用ziplist，否则用hashtable。

//  ziplist 元素个数超过 512 ，将改为hashtable编码 
hash-max-ziplist-entries  512    
//  单个元素大小超过 64 byte时，将改为hashtable编码
hash-max-ziplist-value    64

4.3 hash比较String

比较hash和String，其实是比较一个对象的多个属性存储场景。一个属性存储一个kv，还是一个user存储一个kv。
-1. 数据量大时，String造成rehash更频繁
-2. String 更加灵活，支持比较细粒度的过期等功能
-3. hash 整体存储，有效降低rehash，不能单一个设置过期时间等

五. Set 详解

##5.1 常用命令
/> help  @setSADD key member [member ...]              SCARD key                                                 SISMEMBER key memberSPOP key [count]SDIFF key [key ...]SINTER key [key ...]SUNION key [key ...]SMEMBERS keySRANDMEMBER key [count]SREM key member [member ...]SMOVE source destination memberSUNIONSTORE destination key [key ...]SDIFFSTORE destination key [key ...]SINTERSTORE destination key [key ...]SSCAN key cursor [MATCH pattern] [COUNT count]

5.2 底层结构

Set 为无序的，自动去重的集合数据类型，Set 数据结构底层实现为一个value 为 null 的字典( dict ),当数据可以用整形表示时，Set集合将被编码为intset数据结构,此时set是有序的。两个条件任意满足时Set将用hashtable存储数据。

1 元素个数大于 set-max-intset-entries
2 元素无法用整形表示

六. ZSet 详解

6.1 常用命令

/> help @sorted_set

  ZADD key [NX|XX] [CH] [INCR] score member [score member ...]ZCARD keyZCOUNT key min maxZINCRBY key increment memberZRANGE key start stop [WITHSCORES]ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT offset count]ZRANK key memberZREM key member [member ...]ZREMRANGEBYRANK key start stopZREMRANGEBYSCORE key min maxZREVRANGE key start stop [WITHSCORES]ZREVRANGEBYSCORE key max min [WITHSCORES] [LIMIT offset count]ZREVRANK key memberZSCAN key cursor [MATCH pattern] [COUNT count]ZSCORE key member

6.2 底层结构

ZSet 为有序的，自动去重的集合数据类型，ZSet 数据结构底层实现为字典(dict) + 跳表(skiplist) ,当数据比较少时，用ziplist编码结构存储。

// 元素个数超过128 ，将用skiplist编码
zset-max-ziplist-entries  128    
// 单个元素大小超过 64 byte, 将用 skiplist编码
zset-max-ziplist-value     64

6.2.1 ziplist

每个元素分为两个entry存储。

image.png

6.2.2 skiplist

跳表，通过多集索引来提高查询和修改性能。 zskiplist存储了header和tail的地址，总数据和最高索引层。查找数据时从最高索引层开始二分查找。

image.png

七. GEO 算法

根据地球经纬度，首先按照东经180到西经180，纬度范围是南纬90到北纬90，分位四个象限，分别用00,01，10,11表示,每个象限再均分四个象限，直到满足需要的精度。这个划分结构，我们知道前缀越相同，距离越近。

image.png

优点

GeoHash利用Z阶曲线进行编码，Z阶曲线可以将二维所有点都转换成一阶曲线。地理位置坐标点通过编码转化成一维值，利用有序数据结构如B树、SkipList等，均可进行范围搜索。因此利用GeoHash算法查找邻近点比较快

缺点

Z 阶曲线有一个比较严重的问题，虽然有局部保序性，但是它也有突变性。在每个 Z 字母的拐角，都有可能出现顺序的突变。

喜欢的朋友记得点赞、收藏、关注哦！！！

redis数据结构设计

一. 数据结构简介

二. K-V组织结构

2.1 redisDB

2.2 dict

2.3 渐进式rehash

三. String 详解

3.1 简单动态字符串实现详解

3.1.1 redis 3.2版本之前

实现源码

实现问题

3.1.2 redis 3.2 之后版本

实现源码

3.2 为什么没有使用c语言字符数组实现

3.3 常用API

3.3 String 编码数据类型补充

三. List 详解

3.1常用命令

3.2 底层结构

3.2.1 ziplist

3.2.2 quicklist

四. Hash 详解

4.1常用命令

4.2底层结构

4.3 hash比较String

五. Set 详解

5.2 底层结构

六. ZSet 详解

6.1 常用命令

6.2 底层结构

6.2.1 ziplist

6.2.2 skiplist

七. GEO 算法

优点

缺点

相关文章