Redis——数据布局

目录
1.动态字符串SDS
1.1SDS底层源码
1.2 SDS动态扩容
1.3动态字符串SDS长处 
2.IntSet 
2.1底层布局
2.2有序性
2.3.IntSet布局扩容
2.4总结
3.Dict
3.1底层布局
3.2.Dict扩容 
3.3Dict紧缩
 3.4.Dict的rehash
1.分配空间
2. 设置 rehashidx
3. 渐进式 rehash
Redis 采用渐进式 rehash 战略，克制一次性 rehash 大量键对服务器性能造成影响。具体步骤如下：
4. 迁移完成
4.ZipList
4.1底层布局
4.1.1 ZipList
 4.1.2 Entry
4.2.Encoding编码
设计上风
4.3.ZipList的连锁更新题目
5.QuickList
5.1总结
6.SKipList
6.1底层布局源码
 6.2总结
7.RedisObject
7.1.Redis的编码方式

---

1.动态字符串SDS

   我们都知道Redis生存的key是字符串value每每是字符串大概字符串的聚集。可见字符串是redis中最常见的一种数据布局。
  redis底层是c语言编写的，不过redis并没有直接使用c语言中的字符串，因为c语言字符串存在许多题目：

1. //c语言
2. char* s = "hello"
3. //本质是字符串数组：{'h','e','l','l','o','\0'}

复制代码

• 获取字符串长度须要通过运算（获取字符串长度还须要 - 竣事标识符）
  
• 非二进制安全（不能包罗特别字符）
  
• 不可修改
  

  以是Redis构建了一种新的字符串，动态字符串简称SDS
  1.1SDS底层源码

   flags：redis为了办理数据布局体巨细受限题目创建了差别的SDS数据布局范例（比如uint8_t只能存储巨细为255个字节数组字符串），flags重要作用就是用来存储SDS的范例信息，在redis中，差别SDS在存储容量和内存使用服从上各有差别。借助flags字段，redis可以或许依据实际需求选用合适的SDS范例，从而实现内存的高效使用
  flags默认值如下
  

  比方，一个字符串包罗name的sds布局如下：

flags：1表现使用type8来存储数据

1.2 SDS动态扩容

   SDS之以是叫动态字符串，因为它具备动态扩容的本领
  
  步骤如下：
  1.redis首先会去申请新的内存空间：申请规则如下
  如果我们新的字符串巨微小于1M,则新空间为扩张后字符串长度两倍+1（淘汰内存分配的次数淘汰性能开销）
  如果新字符串巨细大于1M，则新空间为扩展后字符串长度+1M+1。称为内存分配。（大于1M字符串如果再扩张为2倍非常浪费内存空间）
  2.再把原数组数据赋值过来
  
  1.3动态字符串SDS长处 

   

• 1.获取字符串长度的时间复杂度为0（1）
  
• 2.支持动态扩容
  
• 3.淘汰内存分配次数
  
• 4.二进制安全
  

  

---

2.IntSet 

   IntSet是Redis中Set聚集的一种实现方式，基于整数数组来实现的，而且具备长度可变，有序等特性。
  2.1底层布局

   encoding着实和动态字符串SDS的flags作用一样记录使用哪种数据范例 ，此中encoding包罗三种模式，表现存储的整数巨细差别：
  

2.2有序性

   为了方便查找，Redis会在intset中全部的整数按照升序依次生存在contens数组中，
  如今每个数组中的每个数字都在int16_t范围内，因此采用的编码方式是INTSET_ENC_INT16
  

   

• 1.IntSet底层采用的是连续的数组来存储元素，而且每个元素的范例雷同，那么每个元素内存中所占空间巨细是固定的。
  
• 2.intset会有寻址公式startPtr + (sizeof(int16)*index)通过这种寻址公式，intset可以高效的访问数组中任意元素，通过将起始地点startPtr加上偏移量（sizeof(int16)*index），就能得到指定索引位置元素的内存地点。
  
• 3.startPtr：这是整数聚集底层数组的起始地点。根据上面那幅图就是Header包罗的部分
  
• sizeof(int16)：sizeof是一个用于获取数据范例所占字节数的操纵符，int16表现 16 位整数，
  
• index：这是数组中元素的索引
  

  
2.3.IntSet布局扩容

   IntSet支持动态升级本领，如果当前数据布局存储不了要添加数据的巨细就会升级编码
  举个栗子：
  如今假设有一个IntSet，元素为{5，10，20}采用的编码是INTSET_ENC_INT16则每个整数占2个字节
  

   我们向该此中添加一个数字：5000,这个数字超出了int16_t的范围，intset会主动升级编码方式到合适的巨细。
以当前案例来说流程如下：
  

• 1.升级编码为INTSET_ENC_INT32每个整数占4字节，并按照新的编码方式及元素个数分配新的内存空间。
  
• 2.倒序依次将数组中的元素拷贝到扩容后的精确位置
  
• 3.将待添加的元素放入数组末了
  
• 4.末了，将inset的encoding属性改为INTSET_ENC_INT32,将length属性改为4
  

  

---

  这里你大概会有疑问为什么不正序添加元素而是采用倒序添加元素
  
  重要是克制数据覆盖题目：IntSet在内存中是连续存储的，新分配的内存空间和旧内存空间存在重叠。当进行编码升级时，新元素范例的字节数会比原范例大。（要么添加到全部元素之后要么添加到全部元素之前，因为这个数要么就是负数很小，要么就是整数很大比如-5000or5000）如果正序添加元素，在将原Intset中的元素复制到新数组时，由于新元素占用空间更大，大概会覆盖尚未处置惩罚的后续元素。
  
  

2.4总结

   

• 1.Redis会确保Inset中的元素唯一，有序
  
• 2.具备范例升级机制，可以节流内存空间
  
• 3.底层采用二分查找方式来查询
  

  

---

3.Dict

   Dict是dictionary也就是字典的简称。redis是一个键值型（Key-Value pair)的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系Dict来实现的。
Dict由三部分构成，分别是：哈希表（DictHashTable),哈希节点（DictEntry),字典（Dict)
  3.1底层布局

   dict（字典）
  

• 1.type表现字典范例（差别场景下使用差别字典范例，扩展性很强）
  
• 2.ht[2]表是两个hash表，一个用于存储数据，一个用于重新构建hash表的时间使用
  
• 3.rehashidx表现是否进行rehash
  

  
  对于dictht（哈希表）
  

• 1.第一个字段 table表现指针指向存储hash节点数组的指针
  
• 2.size代表hash表的巨细也就是数组的巨细
  
• 3.掩码sizemask，用于盘算键值对存储的位置
  
• 4.used表现有多少个元素，因为会有hash辩论生存到数组同一个位置这样就形成链表
  

  DictEntry（hash节点）：就表现一个链表数据布局
  

---

  当我们向dict添加键值对时，redis首先根据key盘算出hash值（h),然后使用h&sizemask(按位与)来盘算元素应该存储到数组中的哪个索引位置。我们存储k1=v1,假设k1的哈希值h =1,则1&3=1,因此k1=v1要存储到数组角标1位置。
  

3.2.Dict扩容 

   Dict中的HashTable就是数组联合单向链表的实现，当集会合元素较多时，必然导致哈希辩论增多，链表过长，则查询，服从会大大低沉。
Dict在每次新增链值对时都会查抄负载因子 (LoadFactor=used/size),满意以下两种情况时会触发哈希表扩容：
  

• 哈希表的LoadFactor>=1,而且服务器没有实行bgsave 大概bgrewriteaof等背景历程；(因为这些背景历程对cpu使用非常高而且大量io读写，这时扩容影响性能)
  
• 哈希表的LoadFactor>5;
  

  底层源码实行逻辑如下 

3.3Dict紧缩

   dict除了扩容以外，每次删除元素时，也会对负载因子做查抄，当LoadFactor<0.1时，会做哈希表紧缩；
  实现逻辑如下
  

  
 3.4.Dict的rehash

   不管是扩容照旧紧缩，肯定会创建新的哈希表，导致哈希表的size和sizemask变革，而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新盘算索引，插入新的哈希表，这个过程称为rehash。
  实现步骤如下：
  

  
  1.分配空间

  

• 扩展操纵：为 ht[1] 分配空间，其巨细是第一个大于即是 ht[0].used * 2 的 2 的幂。
  
• 紧缩操纵：为 ht[1] 分配空间，其巨细是第一个大于即是 ht[0].used 的 2 的幂。
  
• 
  
  

  2. 设置 rehashidx

    把 dict 布局里的 rehashidx 设置为 0，这表明 rehash 操纵正式开始。     

      3. 渐进式 rehash

   Redis 采用渐进式 rehash 战略，克制一次性 rehash 大量键对服务器性能造成影响。具体步骤如下：

   

• 在 rehash 期间，每次对字典实行增、删、查、改操纵时，步伐除了完成指定操纵之外，还会顺带将 ht[0] 哈希表在 rehashidx 索引上的全部键值对 rehash 到 ht[1]，然后将 rehashidx 的值加 1。
  
• 别的，Redis 还会在定时任务里对字典进行 rehash 操纵，每次处置惩罚肯定数量的键值对。
  

   4. 迁移完成

      当 ht[0] 中的全部键值对都被 rehash 到 ht[1] 之后，开释 ht[0]，将 ht[1] 设置为 ht[0]，并创建一个新的空缺哈希表作为 ht[1]，同时将 rehashidx 设置为 -1，表明 rehash 操纵竣事。        

      

---

4.ZipList

   ziplist是一种特别的"双端链表",由一系列特别编码的连续内存块构成。可以在任意一端进行压入/弹出操纵，而且"该操纵的时间复杂度为0(1)。当列表或哈希元素数量较少且值较小时会采用这种布局。
  4.1底层布局

4.1.1 ZipList

 4.1.2 Entry

   ZipList中的Entiy井不像平凡链表那样记录前后节点的指针，因为记录两个指针要占用16个字节，浪费内存。而是采用
了下面的布局：
  

  previous_entry_length:前一节点的长度，占1个或5个字节。
  

• 如果前一节点的长度小于254字节，则采用1个字节来生存这个长度值
  
• 如果前一节点的长度大于254字书，则采用5个字节来生存这个长废值，第一个字节为oxfe,后四个字节才是真实长度数据
  

  encoding:编码属性，记录contentent的数据范例（字符串照旧整数）以及长度，占用1个，2个或5个字节
  
content:负责生存节点的数据，可以是字符串或整数
  

---

  ZipList的Entry这样设计不光在节流内存空间的同时，包管数据的高效存储和访问，而且支持正向和反向遍历等操纵。
  
  1.记录前置节点长度（previous_entry_length）和当前节点长度（encoding）的字段，会根据实际长度动态调解。
  2.反向遍历：借助记录前一个 Entry 的长度（previous_entry_length），可以或许从后往前反向遍历 ZipList。在某些场景下，反向遍历是须要的，比如实现栈的操纵时，就须要从后往前访问元素。
  4.2.Encoding编码

   ZipListEntry中的encoding编码分为字符串和整数两种
  整数编码：当 entry 存储整数时，encoding 用 1 字节表现 。通过 encoding 可确定整数范例及实际巨细
  常见整数编码如下：
  

• ZIP_INT_8B ：对应二进制 11111110 ，表现 8 位整数，content（数据部分）占 1 字节 
  
• ZIP_INT_16B ：对应二进制 1100 0000 ，表现 16 位整数，content 占 2 字节 。
  
• ZIP_INT_24B ：对应二进制 1111 0000 ，表现 24 位整数，content 占 3 字节 。
  
• ZIP_INT_32B ：对应二进制 1110 0000 ，表现 32 位整数，content 占 4 字节 。
  
• ZIP_INT_64B ：对应二进制 1101 0000 ，表现 64 位整数，content 占 8 字节 。
  
• ZIP_INT_2C ：对应二进制 11111101 ，表现 2 位有符号整数，实际取值范围有限 。
  

  字节数组（字符串）编码：当 entry 存储字符串时，根据字符串长度差别，encoding 有 3 种编码方式，编码的第一个字节前 2 位表现数据范例，后续位标识字符串实际长度：
  

  总结：
  1.判断数据范例：encoding 第一个字节的前 2 位用于确定数据范例，二进制 11 开头表现整数 ；非 11 开头则是字节数组（字符串）。
  2.剖析字节数组长度：对于字节数组编码，确定是字节数组范例后，根据前 2 位具体值判断是哪种字符串编码，再依据对应规则剖析出字符串长度。
  设计上风

  

• 节流内存：根据数据实际范例和长度选择合适编码，克制固定长度存储造成的内存浪费。如存储小整数或短字符串时，使用较少字节数编码。
  
• 快速剖析：通过 encoding 编码，可快速确定数据范例和长度，在读取 entry 数据时提高剖析服从 。
  

  
4.3.ZipList的连锁更新题目

     ZipList 的每个节点（Entry）包罗一个记录前一个节点长度的属性 previous_entry_length ，该属性占用 1 个或 5 个字节：     

• 若前一节点长度小于 254 字节，用 1 字节生存长度值。
  
• 若前一节点长度大于即是 254 字节，用 5 字节生存长度值，第一个字节固定为 0xfe ，后 4 字节是真实长度数据。
  
• 
  
  

     假设存在 N 个连续的、长度在 250 - 253 字节之间的 Entry ，此时每个 Entry 的 previous_entry_length 都仅需 1 字节表现。若在队首插入一个 254 字节的数据：     

     

• 第二个 Entry 的 previous_entry_length 就得从 1 字节扩展为 5 字节 ，这使第二个 Entry 长度变为 254 字节。
  
• 第二个 Entry 长度变革后，第三个 Entry 的 previous_entry_length 也需从 1 字节变为 5 字节 ，依此类推，后续全部 Entry 都会因前一个长度的改变而改变 。
  

     这种特别情况下产生的连续多次空间扩展操纵，就是连锁更新（Cascade Update） 。不光插入操纵，删除操纵也大概引发连锁更新。比如删除一个节点后，相邻节点记录的前置节点长度发生变革，若涉及长度从小于 254 字节变为大于即是 254 字节（或反之），就大概引发连锁更新。   

---

5.QuickList

   ZipList固然节流内存，但申请内存必须是连续空间，如果内存占用过多，申请内存服从很低。以是当我们要存储大量数据，超出ZipList最佳上限那么可以创建多个ZipList来分片存储数据。
  Redis3.2版本引入了新的数据布局QuickList，它是一个双端链表，只不过链表中的每个节点都是ZipList
  

  
  1.为了克制QuickList中的每个ZipList中entry过多，Redis提供了一个设置项：list-max-ziplist-size来限定。
  

• 如果值为正，则代表ziplist的允许的entry个数的最大值
  
• 如果值为负，则代表ziplist的最大内存巨细，分5种情况：
  

  1:每个ziplist的内存占用不能超过4kb
  -2:每个ziplist的内存占用不能超过8kb
  -3:每个ziplist的内存占用不能超过16kb
  -4:每个ziplist的内存占用不能超过32kb
  -5:每个ziplist的内存占用不能超过64kb
  其默认值为-2:
  

  
  2.除了控制ziplist的巨细，quicklist-comprest还可以对节点的ZipList做压缩。通过设置项ist-compress-depth来控制。因为链表一样平常都是从首尾访问较多，以是首尾是不压缩的。这个参数是控制首尾不压缩的节点个数：
  

• 0:特别值，代表不压缩
  
• 1:标示quicklist的首尾各有1个节点不压缩，中间节点压缩
  
• 2:标示quicklist的首尾各有2个节点不压缩，中间节点压缩
  

  以此类推
  默认值：
  

  
  QuickList团体布局图如下 

5.1总结

   

• quickList是一个节点为ZipList的双端链表
  
• 节点采用ZipList，办理了传统链表的内存占用题目
  
• 控制了ZipList巨细，办理连续内存空间申请服从题目
  
• 中间节点可以压缩，进一步节流了内存
  

  

---

6.SKipList

   SkipList（跳表）是一种用于实现有序聚集的数据布局。首先是链表，但与传统链表相比有几点差别：
  

• 元素按照升序排列存储
  
• 节点大概包罗多个指针，指针跨度差别。
  

  

6.1底层布局源码

   score:分值是用于排序的依据
  ele:实际存储的数据
  backward:退却指针用于从尾向头遍历跳跃表
  zskiplistLevel:层数组则用于实现多层索引布局，每个元素包罗一个进步指针（forward）和跨度（span）。跨度表现从当前节点到下一个节点之间的元素数量
  调表布局图：

 6.2总结

   

• 调表是一个双向链表，每个节点都包罗score和ele值
  
• 节点按照score值排序，score值一样按照ele字典排序
  
• 每个节点都可以包罗多层指针，层数是1到32之间的随机数
  
• 差别层指针到下一个节点的跨度差别，层级越高，跨度越大
  
• 增删改查服从与红黑树根本一致，实现却更简单
  

  

---

7.RedisObject

   Redis中的任意数据范例的键和值都会被封装为一个RedisObject，也叫做Redis对象，源码如下：
  

  
  RedisObject是 Redis 实现多数据范例支持的关键布局。借助 type 和 encoding 字段，Redis 可以或许机动存储和处置惩罚差别范例的数据，同时使用引用计数和 LRU/LFU 机制管理内存。
  7.1.Redis的编码方式

   Redis会根据存储数据范例的差别，选择差别的编码方式，共包罗11种差别范例：
  

   String，List，Set，Zset，Hash每一种数据范例对应几种差别编码：
  
  

  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。