10-28 09:35 阅读 59

关注

聊聊Redis数据类型

Key的设计

首先聊一下Redis的Key的设计， 一般情况下可以遵循以下原则:

• 用: 分割

• 表名作为key的前缀

• 中间段是主键值

• 尾段是列名

举个例子: user:1:username,   user:1:code

数据类型

//redis db typedef struct redisDb{     int id; //数据库序号, 0-15     long avg_ttl; // 平均ttl     dict *dict; //所有的kv      dict *expires;  // 存储key的过期时间     dict *blocking_keys;//blpop存储阻塞key和客户端对象     dict *ready_keys; //阻塞后push 响应阻塞客户端，存储阻塞后push的key和客户端对象     dict *watched_keys; // 存储watch监控的key和客户端对象 }redisDb; //redisObject typedef struct redisObject{     unsigned type:4; //表示对象类型 String  list hash set zset     unsigned encoding:4;     void *ptr; //底层实现数据结构指针     int refcount;// 引用计数     unsigned lru:LRU_BITS;// LRU_BITS为24bit 记录最后一次被命令程序访问的时间, 高16位存储一个分钟级别的时间戳, 低8位最近被访问的次数 }rObj; 复制代码

String

表达3种值的类型, 字符串，整数，浮点数, encoding是 int,raw, embstr

SDS 存储字符串和整型数据

struct sdshdr{     int len;// 数组中已经使用的字节的数量     int free;// 数组未使用的字节的数量     char buf[]; //用于保存字符串长度 } 复制代码

优势:

• 在C字符串的基础上加入了free和len字段， 获取字符串长度， SDS是O(1), C字符串是O(n)

• SDS由于记录了长度， 在可能造成缓冲去溢出时自动重新分配内存，杜绝了缓冲区溢出

• 可以存放二进制数据，字符串长度len作为结束标识

场景:

存储字符串和整型数据， 存储key, AOF缓冲区和用户缓冲区

list

存储有序，可重复的元素，最多个数2^32 -1个(40亿), encoding 是quicklist

压缩列表ziplist: 一系列特殊编码的连续内存块组成的顺序型数据结构，节省内存，是一个字节数组，包含多个节点，每个节点保存一个字节数组或一个整数。

• zlbytes: 压缩列表的字节长度

• zltail: 压缩列表尾元素相对于压缩列表起始地址的偏移量

• zlen: 压缩列表的元素个数

• entry1.. entryx: 压缩列表的各个节点

• zlend: 压缩列表的结尾， 占一个字节 恒为0xFF(255)

entryX元素编码结果:

• previous_entry_length: 前一个元素的长度

• encoding: 当前元素编码

• content: 内容

typedef struct zlentry{     unsigned int prevrawlensize;// previous_entry_length字段长度     unsigned int prevawlen;//previous_entry_length存储内容     unsigned int lensize;//encoding 长度     unsigned int len;// 数据内容长度     unsigned int headersize;// 当前元素首部长度     unsigned char encoding;//数据类型     unsigned char *p;// 元素首地址 } zlentry; 复制代码

quickList 是 linkedList 和ziplist的结合

typedef struct quicklist{     quicklistNode *head;     quicklistNode *tail;     unsigned long count;// 所有数据项个数     unsigned int len; //ziplist个数     int fill :16; //ziplist大小限定, list-max-ziplist-size;     unsigned int compress :16;//节点压缩深度设置, list-compress-depth }quicklist; 复制代码

typedef struct quicklistNode{     struct quicklistNode *prev;     struct quicklistNode *next;     unsigned char *zl;// 数据指针，没被压缩指向ziplist, 压缩后指向quicklistLZF;     unsigned int sz;//指向ziplist总长度     unsigned int count :16; //ziplist中数据项     unsigned int encoding :2;// 编码方式     unsigned int container :2;// 预留字段，1--NONE, 2-ziplist     unsigned int recompress :1;//解压标记     unsigned int attepted_compress;//测试     unsigned int extra :10; //扩展字段 }quicklistNode; 复制代码

quicklist每个节点的实际存储为ziplist, 节省内存。 可以对ziplist进行压缩，算法为LZF，基本思想是数据与前面重复的记录重复位置及长度，不重复记录原始数据

typedef struct quicklistLZF{     unsigned int sz;//长度     char compressed[];//数组 }quicklistLZF; 复制代码

Set

无序，唯一元素， 集合中最大的成员数 2^32-1, encoding是inset 和hashtable

intset : 有序的整数集合， 连续存储结构, redis集合类型都是整数且处在64位有符号整数范围内

typedef struct intset{     uint32_t encoding;     uint32_t length;     int8_t contents[]; }intset; 复制代码

sortedset

元素本身无序不重复，每个元素关联一个分数，可根据分数排序，分数可重复, encoding是ziplist skiplist

跳跃表: 有序链表分层

typedef struct  zskiplistNode{     sds ele;     double scrore;// 分值     struct zskiplistNode *backward;// 后退指针，指向当前节点最底层的前一个节点     struct zskiplistLevel{         struct zskiplistNode * forward;//本层下个节点         unsigned int span;// 本层下个节点到本节点的元素个数     }level[];  } zskiplistNode; typedef struct zskiplist{     struct skiplistNode *header, *tail;     unsigned long length;     int level; }zskiplist; 复制代码

优势:

• 可以快速找到节点

• 在O(1)的时间复杂复杂度下,快速获取头节点，尾节点， 长度和高度;

hash

String类型的field和value的映射表，每个hash可以存储2^32-1键值对, encoding 是 hashtable和ziplist

• 数组

  存储数据的容器，头指针+ 偏移量快速定位数据所在的内存地址

• Hash函数

  任意长度的输入通过散列算法转换成固定类型，固定长度的散列值。

• 数组下标= hash(key)%数组容量

• Hash冲突 redis通过链表解决

typedef struct dictht{     dictEntry **table;     unsigned long size; //哈希表数组大小     unsigned long sizemask; // 映射位置掩码， size-1     unsigned long used; // 已有节点数目包含next 单链表数据 }dictht 复制代码

hash表数组初始容量为4，每次扩容为2倍， 索引值为hash值&掩码值。

typedef struct dictEntry{     void *key;     union{         void *val;         uint64_t u64;         int64_t s64;         double d;     }v; struct dictEntry *next; }dictEntry; 复制代码

typedef struct dict {     dictType *type;     void *privdata;     dictht ht[2];     long rehashidx;     int iterators; }  复制代码

typedef struct dictType{     //计算hash值的函数     unsigned int (*hashFuction)(const void *key);     // 复制键的函数     void *(*keyDup)(void *privdata, const void *key);     //复制值的函数     vood *(*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; 复制代码

扩容过程:

• 初始申请4个dictEntry, 后面申请为当前hash表的一倍

• rehashidx=0 表示进行rehash操作

• 新增加数据在hash表h[1]

• 修改，删除，查询在老hash表h[0], 新hash表h[1]{rehash中}

• h[0]数据重新计算索引后迁移到h[1]，称为rehash

渐进式hash: 服务器忙， 一个节点hash,如果闲批量hash

bitmap

位操作

geo

处理位置信息

stream

可持久化的消息队列, 底层使用了listPack和Rax树

缓存过期和淘汰策略

maxmemory 默认为0, 不限制, 作为DB使用的时候配合禁止驱逐的淘汰策略.

如果要限制，一般设置物理内存的3/4。此时必须设置maxmemory-policy

删除策略

删除策略有定时删除，惰性删除和主动删除三种方式， 目前采用惰性删除和主动删除的方式

• 定时删除

  设置过期时间的同时，创建定时器， 定时器在键的过期时间来临时，立即执行对键的删除操作。

• 惰性删除

  在key访问时，如果发现已经失效，就删除它

• 主动删除

  配置 maxmemory-policy

主动删除策略

• LRU

  在数据集中随机挑选几个键值对，取出其中lru最大的键值对淘汰。

  volatile-lru: 从设置已过期时间的数据集中挑选

  allkeys-lru: 从数据集中挑选

• LFU

  最不经常使用,相应的也有 volatile-Lfu和allkeys-lfu

• random

  随机，相应的也有volatile-random和allkeys-random

• ttl

  volatile-ttl， 从过期时间的表里随机挑选几个键值对， 取出其中ttl最小的键值对淘汰

• noenviction

  禁止驱逐

作者：Learn1993
链接：https://juejin.cn/post/7023669113918586917