[大数据]Redis专题4——Redis数据结构对应的底层实现

Redis数据结构对应的底层实现

1.1 String 对应的SDS

Redis: SDS ,simple dynamic string .简单的动态字符串

1、二进制安全的数据结构

2、提供了内存预分配机制，避免了频繁的内存分配

3、兼容c语言的函数库

char data[] = “ttt\0”; 原本的c语言是会char是以 '\0’为结束符的，现在sds有长度显示

struct sdshdr {
int len;
int free;
char buf[];
};

1.2 List的底层实现

List是一个有序（按加入的时序排序）的数据结构，Redis采用quicklist(双端链表)和ziplist作为List的底层实现。

Redis ziplist conf文件设置字段

• list-max-ziplist-size -2 // 单个ziplist节点最大能存储 8kb ,超过则进行分裂,将数据存储在新的ziplist节点中

• list-compress-depth 1 // 0 代表所有节点，都不进行压缩，1， 代表从头节点往后走一个，尾节点往前走一个不用压缩，其他的全部压缩，2，3，4 … 以此类推

1.3 Hash的底层实现（Important）

Hash 数据结构底层实现为一个字典( dict ),也是RedisBb用来存储K-V的数据结构,当数据量比较小，或者单个元素比较小时，底层用ziplist存储，数据大小和元素数量阈值可以通过如下参数设置。

Redis conf文件配置参数

• hash-max-ziplist-entries 512 // ziplist 元素个数超过 512 ，将改为hashtable编码

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

1.4 Set的底层实现

Set 为无序的，自动去重的集合数据类型，Set 数据结构底层实现为一个value 为 null 的字典( dict ),当数据可以用整形表示时，Set集合将被编码为intset数据结构。

两个条件任意满足时Set将用hashtable存储数据。
1， 元素个数大于 set-max-intset-entries ,
2 ， 元素无法用整形表示

Redis.conf文件的参数
set-max-intset-entries 512 // intset 能存储的最大元素个数，超过则用hashtable编码

1.5 ZSet的底层数据结构

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

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

跳表的方式，创建索引值

Redis的type和object encoding

type 查看数据类型

object encoding 返回的是值的内部表示形式的类型。

Redis字典相关介绍

面试中遇到了Redis字典中问题，从三个方面进行回答：

1、数据结构 2、元素增加过程 3、扩容

1、数据结构

Hash数据类型，初始创建hash数据类型是默认使用的是ZIPLIST（压缩列表），当满足下面两个条件中的任意一个时候，Hash键的数据结构将会变为字典，加快查询速度。

1、哈希表中某个键或某个值大于server.hash_max_ziplist_value （默认值为 64 ）。

2、压缩列表中的节点数量大于 server.hash_max_ziplist_entries （默认值为 512 ）。

Redis 字典新建时默认将会创建一个哈希表数组，保存两个哈希表。其中 ht[0] 哈希表在第一次往字典中添加键值时分配内存空间，而另一个 ht[1] 将会在下文中扩容/缩容才会进行空间分配。

dict数据结构，主要字段 dictht ht[2]对应两个hash表， rehashidx 重hash的标志位

dictht数据结构， sizehash表大小， used 表中使用字段，类似HashTable中Table

dictEntry数据结构，就类似HashTable中链表的一项

2、元素增加过程

当我们往一个新字典中添加元素，默认将会为字典中 ht[0] 哈希表分配空间，默认情况下哈希表 table 数组大小为 4（DICT_HT_INITIAL_SIZE）。新添加元素的键值将会经过哈希算法，确定哈希表数组的位置，然后添加到相应的位置,如图所示：

继续增加元素，此时如果两个不同键经过哈希算法产生相同的哈希值，这样就发生了哈希碰撞， Redis将会采用链表的方式解决hash碰撞。

当我们元素增加越来越多时，哈希碰撞情况将会越来越频繁，这就会导致链表长度过长，极端情况下 O(1) 查询效率退化成 O(N) 的查询效率。为此，字典必须进行扩容，这样就会使触发字典 rehash 操作。

3、扩容

当 Redis 进行 Rehash 扩容操作，首先将会为字典没有用到 ht[1] 哈希表分配更大空间。

ps: ht[1] 哈希表大小为第一个大于等于 ht[0].used*2 的 2^2(2的n 次方幂)

扩容 操作需要将 ht[0]所有键值对都 Rehash 到 ht[1] 中，如果键值过多，假设存在十亿个键值对，这样一次性的迁移，势必导致服务器会在一段时间内停止服务。另外如果每次 rehash 都会阻塞当前操作，这样对于客户端处理非常不友好。为了避免 rehash对服务器的影响，Redis 采用渐进式的迁移方式，慢慢将数据迁移分散到多个操作步骤。这个操作依赖字典中一个属性 rehashidx,这是一个索引位置计数器，记录下一个哈希表 table 数组上元素，默认情况为值为 -1。rehashidx表示要从ht[0]表中的下标，并将该元素复制到ht[1]。

渐进式Rehash方式 : http://redisbook.com/preview/dict/incremental_rehashing.html

字典的流程和类型

Ziplist详解

zlbytes: 4字节，记录ziplist占用内存字节数

zltail: 4字节，记录尾节点距离起始位置多少字节

zllen: 2字节，记录整个列表的节点数

entryX: 变长字节，节点的长度由内容决定，具体内容查看下图

zlend: 1字节，特殊值0xFF标记压缩列表的结尾

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系