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

编码格式

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属于双端无环链表

压缩列表组成部分.png

压缩节点组成部分.png

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

Hash

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

hash表结构.png

hashtable示意.png

Set

整数集合.png

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

ZSet

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

有序集合同时保存在字典和跳跃表中.png