Redis的5种类型对象与底层实现

redis在日常coding中使用的场景越来越多，关于redis的背景铺垫就不在此赘述，献上官方介绍。

Redis is an open source (BSD licensed), in-memory data structure store, used as a database, cache and message broker. It supports data structures such as strings, hashes, lists, sets, sorted sets with range queries, bitmaps, hyperloglogs, geospatial indexes with radius queries and streams. Redis has built-in replication, Lua scripting, LRU eviction, transactions and different levels of on-disk persistence, and provides high availability via Redis Sentinel and automatic partitioning with Redis Cluster.

---

本篇主要讲解redis的五种类型对象及底层的实现原理，并简单总结redis在实现过程中的部分优化方式。

redis的对象都可以用以下结构表示

typedef struct redisObject{
   //类型
   unsigned tyep:4;
   //编码
   unsingned encoding:4;
   //指向底层实现的数据结构的指针
   void *ptr;
   //...
}

---

其中的类型属性(type)即我们通常说的五种类型对象分别为：STRING,LIST,HASH,SET以及ZSET。而encoding属性记录对象所使用的编码，即底层的实现，每种类型属性都对应着两种以上编encoding属性。Redis的类型与底层编码共有以下的对应关系

类型对象	编码	中文释义
STRING	INT	使用整数值实现的对象
STRING	EMBSTR	使用embstr编码的sds字符串对象
STRING	RAW	sds
LIST	ZIPLIST	压缩列表
LIST	LIKEDLIST	双端列表
HASH	ZIPLIST	压缩列表
HASH	HASHTABLE	字典
SET	INTSET	整数集合
SET	HASHTABLE	字典
ZSET	ZIPLIST	压缩列表
ZSET	SKIPLIST	跳跃表+字典

String

编码格式

String 的底层实现为int,sds(simple dynamic string)和embrStr,其中embtSds是sds的优化版。其中embstr是只读的，对string对象的任何修改都会使embstr升级为sds.
1、当存储对象为整数，且可以被表现为long类型时，redis会使用int存储对象。
2、当存储对象为string，且长度小于等于32字节时候，会使用embstr存储对象。
3、当存储对象为string，且长度大于32字节时会使用sds存储对象。
embstr与sds的区别在于redisObject对象创建时只生成一次，redisObject与ptr对象排列在一起，而sds编码格式下会生成两次，首先创建redisObject，再创建*ptr对象。

优化点

SDS属于redis实现的str，具有其基本格式如下

sds示例.png

sds具有以下特点
1、存在参数表示sds的长度，求长度时间复杂度O(1)
2、存在预分配策略，新增字段不需要频繁分配内存，不存在缓冲区溢出风险(string小于1M，未分配长度等于已分配长度，string大于1M, 未分配长度为1M)，且存在惰性释放的能力。

List

list底层基于linledList和zipList
linkedlist属于双端无环链表

ziplist即压缩列表，当list健对象只存在少量node节点，且每个节点值也比较短，会使用压缩列表作为底层编码。压缩列表的组成如下 压缩列表组成部分.png
单个entry格式如下 压缩节点组成部分.png 其中content为值，previous可以算出前一个节点的位置，encoding表示存储的是int还是string。

为什么说压缩列表的压缩体现在哪里？
如上图所示：字段与字段之间是是紧密排列在一起的，通过previous可以定位到前一个节点，实现从后到前的遍历。而linkedlist通过pre next指针指向下一个节点，两个指针至少占用16个字节。

Hash

hash底层基于ziplist或hashtable
其中ziplist如list中介绍，其中的区别在于作为hash的底层实现时候，key与value紧密存储在一起，其他与作为list底层一致。

hashtable结构如下 hash表结构.png 其中hash表存在一个数组，用来做ReHash用，关于ReHash的操作可以参考相关资料，其中dictht的结构如下
hashtable示意.png 如同所示，hashtable包括包括四个部分，1)table为一个dictEntry的数组，每个dictEntry s包括key,value以及next, 2)size为entry数组的长度，sizemask为长度减一，用来计算在数组中的位置，used表示hashtable目前有的节点数。

Set

set底层基于intSet以及hashTable，其中intSet为只存储数字的结构，关于整数集合结构如下图所示 整数集合.png

而hashTable存储时候，将相关值存储在key上，value为null

ZSet

zset底层基于ziplist以及 skipList与hashTable的结合。其中zipList中集合的元素按分值从小到大排序，分值较小的元素放在左边，元素值与分值紧密排列在一起。

有需集合对象在skipList与hashTable存在格式如下 有序集合同时保存在字典和跳跃表中.png