Redis底层数据架构 指令流转微路径背景学习Redis文章目录一. 底层数据架构二. redisObject三. 指令流转 精细化路径四. 注意事项一. 底层数据架构图片来源知乎文章熬夜冠军图为一张非常经典的 Redis 字典dict底层数据结构 关系图。Redis 的数据库、哈希键Hash、集合键Set等底层都广泛使用了这种结构。我们可以从左到右、层层剥离地来理解这套设计redisDb数据库入口作用 Redis 服务器中的一个数据库实例。内部 包含一个指向 dict 的指针。你在 Redis 中执行的类似 SET key value 的操作所有的键值对最终都存储在这个底层的字典结构中。dict字典核心外壳核心设计 包含一个数组 dictht ht[2]里面固定有两个哈希表。ht[0] 通常情况下使用的原生哈希表。ht[1] 处于 渐进式 rehash渐进式扩容/缩容 时才会使用的哈希表。dictht哈希表内部 包含一个 dictEntry table 指针它指向一个哈希表数组即图中的 dictEntry*[3]。哈希表的主要职责是计算 Key 的哈希值并映射到对应的数组槽位Bucket上。dictEntry*[3] 与链地址法解决哈希冲突这是一个大小为 3 的指针数组槽位。拉链法 当两个不同的 Key 算出了相同的哈希值时它们会被分配到同一个槽位。Redis 采用单向链表链地址法来解决这种冲突。图中第一个和第二个槽位的指针分别指向了不同的 dictEntry 节点形成了一个个链表。dictEntry真正的键值对节点每个节点包含两个核心指针void key 指向键在 Redis 中Key 永远是一个 String 字符串底层是 SDS 结构。void value 指向值。这是一个万能指针void*使得 Redis 的值可以是各种各样的对象类型即图中最右侧的 String、List、Hash、Set、Zset 等。核心设计亮点为什么设计两个 ht 图中最精妙的地方在于 dictht ht[2]。当单张哈希表里的数据太多导致链表过长、查询变慢时Redis 需要扩容rehash Redis 会为 ht[1] 分配一个更大的空间。 重点是Redis 不会一次性把 ht[0] 的数据全部复制到 ht[1]因为数据量大时会卡死服务器。 它是每次收到客户端读写请求时顺便搬运一部分数据过去直到搬空。这就是大名鼎鼎的渐进式 Rehash。诸如SDS、intset、quicklist等数据结构网上已有相当数量的讲解文章本文不再阐述本文重点在于数据架构and指令流转过程。有关quicklist等数据结构具体可看该篇文章【Redis】万字长文带你深入Redis底层数据结构二. redisObject为了让全局 dict 能够管理各种五花八门的数据类型String、List、Hash 等Redis 抽象出了 redisObject 结构体。全局 dictEntry 的 void* value 指针指向的就是它。redisObject 内部主要包含三个核心信息type类型 对外暴露的类型如 String、List、Hash、Set、ZSet。encoding编码/底层结构 决定了当前这个对象在底层究竟是用什么数据结构存的。比如是 Listpack、Skiplist、Intset、Quicklist 还是另一个 Dict。ptr指针 真正指向底层这些具体结构如 Listpack 内存块、Skiplist 节点的指针。小例子需要结合第一章节中的图来理解1. 你执行 SET name jack 时 全局 dict 里创建了一个 dictEntry。 key 指针 - 指向一个 SDS 字符串内容是 name。 value 指针 - 指向一个 redisObject其 type Stringencoding EMBSTR 或 RAW。这个 redisObject 的 ptr 指针 - 指向另一个 SDS 字符串内容是 jack。2. 你执行 HSET user:1 name tom age 18 时假设数据量很小 全局 dict 里创建了一个 dictEntry。 key 指针 - 指向一个 SDS 字符串内容是 user:1。 value 指针 - 指向一个 redisObject其 type Hashencoding Listpack。这个 redisObject 的 ptr 指针 - 指向一块连续的 Listpack 内存块里面紧凑地挨着存放了 name, tom, age, 18。三. 指令流转 精细化路径以 SISMEMBER web:users 10086检查元素在不在集合里 为例找到对应的 redisDb 实例。进入全局 dict锁定主力哈希表 ht[0]。计算 “web:users” 的哈希值通过索引直接定位到 dictht 数组的某个槽位。如果槽位有链表顺序比对 Key 的 SDS 字符串找到对应的 dictEntry。提取 dictEntry 的 value 指针找到 redisObject。检查 redisObject 的 type 为 Setencoding 为 INTSET。通过 ptr 指针进入 intset 结构在连续的整数数组中利用二分查找法寻找 10086。找到了返回 1没找到返回 0。四. 注意事项定位 dictEntry 不是纯“顺序查找”在第三步进入 dictht 的 table 数组时Redis 不是从第 0 个槽位傻傻地往后挨个排查的。真正过程 Redis 会先用哈希算法计算你的 Key得到一个哈希值然后通过位运算hash sizemask直接一击必中定位到数组的某个具体槽位Bucket这个过程是O ( 1 ) O(1)O(1)的。什么时候顺序查找 只有当发生哈希冲突也就是好几个不同的 Key 被分配到了同一个槽位、挂成了单向链表时Redis 才会沿着这个槽位的链表进行顺序查找。一个 DB 实例只有一个全局 dict用来装所有的 Key 和 Value 对象的映射关系。在这个视角下listpack、skiplist 被包含 在它的 value 里面。但是虽然全局dict只有一个但dict也可作为局部“打工人”当你的 Hash 键或者 Set 键里面的数据量变得特别巨大、Listpack 或 Intset 撑不住的时候Redis 会把底层的结构也升级转化为一个私有的、局部的 dict 来存储键值对。简单来说全局 dict 包含 redisObjectredisObject 根据实际情况选择 listpack/skiplist/intset/局部dict 之一作为其真正的底层承载。全局有一个大 dict底层结构被它包含在 Redis 中任何键值对的操作首先面对的都是数据库实例redisDb里的那个全局 dict我们也叫它 Keyspace键空间。这个全局 dict 里的 dictEntry 的Key 永远是一个 String也就是 SDS。比如你执行 SET name jack这个 “name” 就是全局 dict 里的 Key。这个全局 dict 里的 dictEntry 的Value 并不是直接指向具体的 listpack 或 skiplist而是指向一个通用的通用结构体——redisObject。
Redis底层数据架构 指令流转微路径背景学习Redis文章目录一. 底层数据架构二. redisObject三. 指令流转 精细化路径四. 注意事项一. 底层数据架构图片来源知乎文章熬夜冠军图为一张非常经典的 Redis 字典dict底层数据结构 关系图。Redis 的数据库、哈希键Hash、集合键Set等底层都广泛使用了这种结构。我们可以从左到右、层层剥离地来理解这套设计redisDb数据库入口作用 Redis 服务器中的一个数据库实例。内部 包含一个指向 dict 的指针。你在 Redis 中执行的类似 SET key value 的操作所有的键值对最终都存储在这个底层的字典结构中。dict字典核心外壳核心设计 包含一个数组 dictht ht[2]里面固定有两个哈希表。ht[0] 通常情况下使用的原生哈希表。ht[1] 处于 渐进式 rehash渐进式扩容/缩容 时才会使用的哈希表。dictht哈希表内部 包含一个 dictEntry table 指针它指向一个哈希表数组即图中的 dictEntry*[3]。哈希表的主要职责是计算 Key 的哈希值并映射到对应的数组槽位Bucket上。dictEntry*[3] 与链地址法解决哈希冲突这是一个大小为 3 的指针数组槽位。拉链法 当两个不同的 Key 算出了相同的哈希值时它们会被分配到同一个槽位。Redis 采用单向链表链地址法来解决这种冲突。图中第一个和第二个槽位的指针分别指向了不同的 dictEntry 节点形成了一个个链表。dictEntry真正的键值对节点每个节点包含两个核心指针void key 指向键在 Redis 中Key 永远是一个 String 字符串底层是 SDS 结构。void value 指向值。这是一个万能指针void*使得 Redis 的值可以是各种各样的对象类型即图中最右侧的 String、List、Hash、Set、Zset 等。核心设计亮点为什么设计两个 ht 图中最精妙的地方在于 dictht ht[2]。当单张哈希表里的数据太多导致链表过长、查询变慢时Redis 需要扩容rehash Redis 会为 ht[1] 分配一个更大的空间。 重点是Redis 不会一次性把 ht[0] 的数据全部复制到 ht[1]因为数据量大时会卡死服务器。 它是每次收到客户端读写请求时顺便搬运一部分数据过去直到搬空。这就是大名鼎鼎的渐进式 Rehash。诸如SDS、intset、quicklist等数据结构网上已有相当数量的讲解文章本文不再阐述本文重点在于数据架构and指令流转过程。有关quicklist等数据结构具体可看该篇文章【Redis】万字长文带你深入Redis底层数据结构二. redisObject为了让全局 dict 能够管理各种五花八门的数据类型String、List、Hash 等Redis 抽象出了 redisObject 结构体。全局 dictEntry 的 void* value 指针指向的就是它。redisObject 内部主要包含三个核心信息type类型 对外暴露的类型如 String、List、Hash、Set、ZSet。encoding编码/底层结构 决定了当前这个对象在底层究竟是用什么数据结构存的。比如是 Listpack、Skiplist、Intset、Quicklist 还是另一个 Dict。ptr指针 真正指向底层这些具体结构如 Listpack 内存块、Skiplist 节点的指针。小例子需要结合第一章节中的图来理解1. 你执行 SET name jack 时 全局 dict 里创建了一个 dictEntry。 key 指针 - 指向一个 SDS 字符串内容是 name。 value 指针 - 指向一个 redisObject其 type Stringencoding EMBSTR 或 RAW。这个 redisObject 的 ptr 指针 - 指向另一个 SDS 字符串内容是 jack。2. 你执行 HSET user:1 name tom age 18 时假设数据量很小 全局 dict 里创建了一个 dictEntry。 key 指针 - 指向一个 SDS 字符串内容是 user:1。 value 指针 - 指向一个 redisObject其 type Hashencoding Listpack。这个 redisObject 的 ptr 指针 - 指向一块连续的 Listpack 内存块里面紧凑地挨着存放了 name, tom, age, 18。三. 指令流转 精细化路径以 SISMEMBER web:users 10086检查元素在不在集合里 为例找到对应的 redisDb 实例。进入全局 dict锁定主力哈希表 ht[0]。计算 “web:users” 的哈希值通过索引直接定位到 dictht 数组的某个槽位。如果槽位有链表顺序比对 Key 的 SDS 字符串找到对应的 dictEntry。提取 dictEntry 的 value 指针找到 redisObject。检查 redisObject 的 type 为 Setencoding 为 INTSET。通过 ptr 指针进入 intset 结构在连续的整数数组中利用二分查找法寻找 10086。找到了返回 1没找到返回 0。四. 注意事项定位 dictEntry 不是纯“顺序查找”在第三步进入 dictht 的 table 数组时Redis 不是从第 0 个槽位傻傻地往后挨个排查的。真正过程 Redis 会先用哈希算法计算你的 Key得到一个哈希值然后通过位运算hash sizemask直接一击必中定位到数组的某个具体槽位Bucket这个过程是O ( 1 ) O(1)O(1)的。什么时候顺序查找 只有当发生哈希冲突也就是好几个不同的 Key 被分配到了同一个槽位、挂成了单向链表时Redis 才会沿着这个槽位的链表进行顺序查找。一个 DB 实例只有一个全局 dict用来装所有的 Key 和 Value 对象的映射关系。在这个视角下listpack、skiplist 被包含 在它的 value 里面。但是虽然全局dict只有一个但dict也可作为局部“打工人”当你的 Hash 键或者 Set 键里面的数据量变得特别巨大、Listpack 或 Intset 撑不住的时候Redis 会把底层的结构也升级转化为一个私有的、局部的 dict 来存储键值对。简单来说全局 dict 包含 redisObjectredisObject 根据实际情况选择 listpack/skiplist/intset/局部dict 之一作为其真正的底层承载。全局有一个大 dict底层结构被它包含在 Redis 中任何键值对的操作首先面对的都是数据库实例redisDb里的那个全局 dict我们也叫它 Keyspace键空间。这个全局 dict 里的 dictEntry 的Key 永远是一个 String也就是 SDS。比如你执行 SET name jack这个 “name” 就是全局 dict 里的 Key。这个全局 dict 里的 dictEntry 的Value 并不是直接指向具体的 listpack 或 skiplist而是指向一个通用的通用结构体——redisObject。
