基本結(jié)構(gòu)圖

key和value指向的是redisObject對象

type：標(biāo)識該對象用的是什么類型（String、List

Redis數(shù)據(jù)結(jié)構(gòu)

SDS

SDS有4個(gè)屬性：

• len：記錄了字符串長度，因此獲取字符串長度的時(shí)候時(shí)間復(fù)雜度O（1）
• alloc：分配給字符數(shù)組的空間長度。這樣在修改字符串的時(shí)候，只需要alloc-len來判斷剩余空間大小，可以用來判斷空間是否滿足修改條件，如果不滿足就會將SDS擴(kuò)容。因此不會出現(xiàn)C語言的緩沖區(qū)溢出問題
• flags：用來表示不同類型的SDS，表示len和alloc的類型不同，進(jìn)而保存的SDS分配給字節(jié)數(shù)組的大小不同。
• buf[]：字節(jié)數(shù)組，用來保存實(shí)際數(shù)據(jù)。不僅可以保存文本數(shù)據(jù)，還可以保存二進(jìn)制數(shù)據(jù)。

Redis底層由C語言實(shí)現(xiàn)，那么SDS與C語言字符串對比：

• O（1）獲得字符串長度：因?yàn)镾DS有l(wèi)en屬性
• 二進(jìn)制安全：SDS不僅可以保存文本數(shù)據(jù)，還能保存二進(jìn)制數(shù)據(jù)。SDS的使用len屬性來判斷是否遍歷完成，不會管'\0'的字符
• 不會發(fā)生緩沖區(qū)溢出：通過alloc-len來判斷剩余空間大小，可以用來判斷空間是否滿足修改條件，如果不滿足就會將SDS擴(kuò)容。因此不會出現(xiàn)C語言的緩沖區(qū)溢出問題

擴(kuò)容機(jī)制：

• 如果所需的SDS長度小于1MB,則翻倍 + 1
• 如果所需的SDS長度超過1MB,最后的擴(kuò)容大小應(yīng)該是newlen + 1MB + 1?

壓縮列表

ZipList分為這幾個(gè)部分：

• zlbytes：整個(gè)壓縮列表占用內(nèi)存字節(jié)數(shù)
• zltail：壓縮表尾部節(jié)點(diǎn)距離起始地址多少個(gè)字節(jié)，也就是列表尾的便宜量
• zllen：entry節(jié)點(diǎn)的個(gè)數(shù)
• entry部分：存儲數(shù)據(jù)的部分
• zlend：壓縮列表的結(jié)束點(diǎn)，固定在0xFF

entry的構(gòu)成：

• prevlen：前一個(gè)節(jié)點(diǎn)的長度，目的是實(shí)現(xiàn)從后往前遍歷
• encoding：記錄當(dāng)前節(jié)點(diǎn)實(shí)際的類型和長度，類型主要是字符串和整數(shù)
• data：記錄當(dāng)前節(jié)點(diǎn)的實(shí)際存儲數(shù)據(jù)，類型和長度由encoding決定

prevlen屬性的大小：

• 如果前一個(gè)節(jié)點(diǎn)的長度小于254字節(jié)，那么prevlen屬性需要1字節(jié)
• 如果前一個(gè)節(jié)點(diǎn)的長度大于等于254字節(jié)，那么prevlen屬性需要5字節(jié)

encoding屬性的大小：

• 如果當(dāng)前數(shù)據(jù)是整數(shù)，需要1字節(jié)
• 如果當(dāng)前的數(shù)據(jù)是字符串，會根據(jù)需要使用1、2、5字節(jié)的空間

連續(xù)更新問題：

• 壓縮列表新增某一個(gè)元素或者修改某一個(gè)元素，如果空間不夠，壓縮列表占用的內(nèi)存空間需要重新分配。當(dāng)更新的元素較大，會導(dǎo)致后續(xù)的prevlen也都要重新分配，從而引起連鎖更新的問題

quicklist

在 Redis 3.0 之前，List 對象的底層數(shù)據(jù)結(jié)構(gòu)是雙向鏈表或者壓縮列表。然后在 Redis 3.2 的時(shí)候，List 對象的底層改由 quicklist 數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。

quicklist就是雙向鏈表+壓縮列表的組合，quicklist鏈表中的每一個(gè)節(jié)點(diǎn)是一個(gè)壓縮列表。

解決連鎖更新：

• 通過控制鏈表節(jié)點(diǎn)中的壓縮列表的大小或者元素個(gè)數(shù)，來規(guī)避連鎖更新的問題。因?yàn)閴嚎s列表元素越小，連鎖更新帶來的影響就越小，從而性能提升

哈希表

dictht有這幾個(gè)屬性：

• dictEntry **table：數(shù)組的每一個(gè)元素是指向哈希表節(jié)點(diǎn)的指針
• size：哈希表大小
• sizemask：掩碼，用于計(jì)算索引值
• used：哈希表已有的entry個(gè)數(shù)

哈希沖突：
當(dāng)兩個(gè)key不同，但是索引值相同，就會發(fā)生沖突

解決辦法是采用拉鏈法：

• 被分配到同一個(gè)哈希桶上的多個(gè)節(jié)點(diǎn)用一個(gè)單項(xiàng)鏈表連接起來
• 但是也有缺點(diǎn)，當(dāng)鏈表長度過長的時(shí)候，查詢效率很低。

解決辦法是rehash，分為三步：

1. 給哈希表2分配空間，一般比哈希表1大一倍
2. 將哈希表1數(shù)據(jù)遷移到哈希表2
3. 遷移完成后，哈希表1的空間釋放，并把哈希表2設(shè)置為哈希表1，然后在新哈希表2創(chuàng)建出一個(gè)空白的哈希表，為下次rehash做準(zhǔn)備

?但是也有問題，遷移的過程很耗時(shí)間，因此采用了漸進(jìn)式rehash：

1. 給哈希表2分配空間，一般比哈希表1大一倍
2. 在rehash期間，每次哈希表元素新增、刪除、查找的時(shí)候，Redis會執(zhí)行對應(yīng)的操作外，還會將哈希表1中索引位置上的所有dictEntry遷移到哈希表2
3. 遷移完成后，哈希表1的空間釋放，并把哈希表2設(shè)置為哈希表1，然后在新哈希表2創(chuàng)建出一個(gè)空白的哈希表，為下次rehash做準(zhǔn)備

rehash觸發(fā)條件：

• 負(fù)載因子 = 哈希表已保存的節(jié)點(diǎn)數(shù)量 / 哈希表大小
• 當(dāng)負(fù)載因子大于等于1，并且redis沒有進(jìn)行RDB快照和AOF重寫的時(shí)候，進(jìn)行rehash
• 當(dāng)負(fù)載因子大于等于5，說明哈希沖突非常嚴(yán)重，不管也沒用RDB快照和AOF重寫，都會強(qiáng)制執(zhí)行rehash

整數(shù)集合

intset有這幾個(gè)屬性：

• encoding：編碼方式，比如?INTSET_ENC_INT16，那么contents就是一個(gè)int16_t類型的數(shù)組
• length：集合包含的元素?cái)?shù)量
• contents：雖然被聲明為?int8_t 類型，但是實(shí)際上是由保存的數(shù)據(jù)大小由encoding決定

升級規(guī)則：

• 當(dāng)我們將一個(gè)新元素加入集合中，如果新元素的類型(int32_t)比現(xiàn)有元素的類型(int16_t)都要長，需要擴(kuò)寬contents數(shù)組的大小。
• 在原本的數(shù)組上，將每個(gè)元素按間隔類型分割，比如如果encoding屬性值為INTSET_ENC_INT16，那么間隔就是16位。
• 比如現(xiàn)在有3個(gè)類型為int16_t的元素，每個(gè)都是16位長度，然后往整數(shù)集合里面加入一個(gè)新元素65535，這個(gè)新元素類型用int32_t保存，然后對contents擴(kuò)容，會在原本的空間的大小之上多出80位（4 * 32 - 3 * 16 = 80），這樣就能保證可以存下4個(gè)int32_t的元素
• 然后從后往前依次填充，最終再把65535這個(gè)元素放到最后。

整數(shù)集合升級的好處：

• 如果讓一個(gè)數(shù)組保存int16_t、int32_t、int64_t的元素，最好的方式就是用int64_t類型，但是會造成空間的浪費(fèi)。
• 整數(shù)升級保證了我們只需要int64_t類型的元素再進(jìn)行擴(kuò)容，因此可以節(jié)約資源內(nèi)存
• 另外，整數(shù)集合不支持降級?

跳表

跳表是在鏈表的基礎(chǔ)上改進(jìn)過來的，是一個(gè)多層有序鏈表。

跳表zskiplist有以下屬性：

• 跳表的頭尾節(jié)點(diǎn)head，tail
• 跳表的長度length
• 跳表的最大層數(shù)level

跳表節(jié)點(diǎn)zskiplistNode有以下幾個(gè)屬性：

• ele：SDS結(jié)構(gòu)存儲數(shù)據(jù)
• score：節(jié)點(diǎn)的分?jǐn)?shù)，浮點(diǎn)型
• backward：指向上一個(gè)節(jié)點(diǎn)的回退指針，支持從表尾向表頭遍歷，也就是ZREVRANGE命令
• level：是個(gè)zskiplistLevel數(shù)組，zskiplistLevel包含了兩個(gè)字段，一個(gè)是forward，指向下一層能調(diào)到哪個(gè)節(jié)點(diǎn)，span記錄了距離下個(gè)節(jié)點(diǎn)的步數(shù)。數(shù)據(jù)結(jié)構(gòu)就表示每個(gè)節(jié)點(diǎn)是個(gè)多層結(jié)構(gòu)

跳表節(jié)點(diǎn)層數(shù)設(shè)置：

• 跳表的相鄰兩層的節(jié)點(diǎn)數(shù)量最理想的比例是 2:1，查找復(fù)雜度可以降低到 O(logN)。?
• Redis在創(chuàng)建節(jié)點(diǎn)的時(shí)候，會生成范圍為[0, 1]的隨機(jī)數(shù)，如果這個(gè)隨機(jī)數(shù)小于0.25（相當(dāng)于概率25%），那么層數(shù)就增加一層。然后繼續(xù)生成下一個(gè)隨機(jī)數(shù)，直到隨機(jī)數(shù)的結(jié)構(gòu)大于0.25就結(jié)束
• 這樣的做法，相當(dāng)于每增加一層的概率不超過 25%，層數(shù)越高，概率越低，層高最大限制是 64。

為什么用跳表而不用平衡樹？?

• 從內(nèi)存占用上，跳表比平衡樹更靈活：平衡樹每個(gè)節(jié)點(diǎn)包含2個(gè)指針，跳表每個(gè)節(jié)點(diǎn)包含的指針數(shù)目為1/（1-p），在redis中p=0.25，平均每個(gè)節(jié)點(diǎn)包含1.33個(gè)指針，內(nèi)存占用更少
• 在做范圍查詢的時(shí)候，跳表比平衡樹操作更簡單：在平衡樹中我們找到特定范圍的最小值后，還需要以中序遍歷的順序?qū)ふ移渌怀^大值的節(jié)點(diǎn)，所以中序遍歷不容易實(shí)現(xiàn)。而跳表就很簡單，只需要找到最小值后，對第一層的節(jié)點(diǎn)進(jìn)行若干步的遍歷即可
• 在算法實(shí)現(xiàn)難度上，跳表更簡單。平衡樹的插入和刪除操作可能引發(fā)子樹的調(diào)整，子樹邏輯復(fù)雜。而跳表的插入和刪除只需要修改相鄰的節(jié)點(diǎn)，操作簡單又迅速。

listpack

quicklist并沒有完全解決連鎖更新問題，因?yàn)閝uicklist還是使用了壓縮列表來保存元素，于是有了listpack

listpack結(jié)構(gòu)：

• listpack頭包含兩個(gè)屬性，分別記錄了listpack總字節(jié)數(shù)和元素?cái)?shù)量。然后listpack也有一個(gè)結(jié)尾標(biāo)識。listpack entry是listpack的節(jié)點(diǎn)

listpack entry：

• encoding：定于元素的編碼類型，會對不同長度的整數(shù)和字符串進(jìn)行編碼
• data：實(shí)際存放的數(shù)據(jù)
• len：encdong+data的總長度

將prevlen改成len之后能不能從后往前遍歷？

• 答案是可以。lpDecodeBacklen函數(shù)已經(jīng)實(shí)現(xiàn)了?

Redis數(shù)據(jù)對象有哪些

概述

常見的對象有以下五種：

• String：二進(jìn)制安全的，特性是可以包含任何數(shù)據(jù)比如一個(gè)序列化的對象，一個(gè)鍵最大能存儲512M。適用于簡短的字符場景。底層數(shù)據(jù)結(jié)構(gòu)采用的是SDS或者INT編碼
• Hash：鍵值對數(shù)據(jù)結(jié)構(gòu)，相當(dāng)于編程語言的Map。適用于存儲、讀取、修改用戶屬性。底層數(shù)據(jù)結(jié)構(gòu)是哈希表或者壓縮列表
• Set：包含字符串的無序集合，增刪查找快。使用于最新消息排行榜，消息隊(duì)列。底層數(shù)據(jù)結(jié)構(gòu)是哈希表或者整數(shù)集合
• Sort Set: 將Set集合加一個(gè)權(quán)重參數(shù)score，元素按照score排序。特性是在插入元素的時(shí)候自然排序。適用于排行榜、帶權(quán)重的消息隊(duì)列。底層數(shù)據(jù)結(jié)構(gòu)是跳表或者壓縮列表

String

字符串對象的內(nèi)部編碼（encoding）有 3 種 ：int、raw和 embstr。

• int：如果一個(gè)字符串對象保存的是整數(shù)值，并且這個(gè)整數(shù)值可以用long類型表示，那么這個(gè)字符串對象會被保存在redisObject對象的prt中，同時(shí)將encoding設(shè)置成int
• embstr：如果一個(gè)字符串對象保存的是字符串，并且這個(gè)字符串對象小于等于32字節(jié)。那么字符串對象將用SDS表示，同時(shí)encoding設(shè)置成embstr
• raw：如果一個(gè)字符串對象保存的是字符串，并且這個(gè)字符串對象大于32字節(jié)。那么字符串對象將用SDS表示，同時(shí)encoding設(shè)置成raw

embstr和raw都會用SDS來保存值，但不同之處在于embstr會通過一次內(nèi)存分配函數(shù)來分配一塊連續(xù)的內(nèi)存空間來保存redisObject和SDS。而raw編碼會調(diào)用兩次內(nèi)存分配函數(shù)分別分配redisObject和SDS。

embstr相比raw好處：

• embstr編碼創(chuàng)建字符串對象只用調(diào)用一次內(nèi)存分配函數(shù)，而raw編碼需要兩次
• 釋放embstr編碼的字符串對象同樣也只需要調(diào)用一次內(nèi)存釋放函數(shù)
• 因?yàn)閑mbstr編碼的字符串對象的所有數(shù)據(jù)都保存在一塊連續(xù)的內(nèi)存空間，可以更好的利用cpu緩存提升性能

但embstr也有缺點(diǎn)：

• 如果字符串的長度需要重新分配空間時(shí)，整個(gè)redisObject和sds都需要重新分配空間，所以embstr編碼的字符串對象實(shí)際上是只讀的。redis沒有為embstr編碼的字符串對象編寫任何修改的程序。當(dāng)我們對embstr編碼的字符串對象執(zhí)行修改的命令，實(shí)際上是先將編碼從embstr轉(zhuǎn)換成raw，再做修改。?

List

底層是雙向鏈表和壓縮列表

• 如果列表中的元素小于512個(gè)，列表每個(gè)元素的值都小于64字節(jié)，redis會用壓縮列表存儲
• 否則用雙向鏈表

在redis3.2之后，使用quicklist作為底層數(shù)據(jù)結(jié)構(gòu)

Hash

• 如果哈希類型元素個(gè)數(shù)小于512個(gè)，并且所有值小于64字節(jié)，Redis會用壓縮列表底層數(shù)據(jù)結(jié)構(gòu)?
• 否則用哈希表

?在redis7.0，壓縮列表結(jié)構(gòu)被拋棄，使用listpack

Set

• 如果集合中的元素都是整數(shù)且元素個(gè)數(shù)小于512使用整數(shù)集合
• 否則用哈希表

Zset

• 如果有序集合元素小于128個(gè)，并且每個(gè)元素大小小于64字節(jié)，使用壓縮列表
• 否則用跳表

Redis7.0已經(jīng)將壓縮列表廢棄使用listpack?