文章目錄
- 資料類型和資料結構對應
- 全局hash表和expires過期字典
- 五大對象
-
- 應用場景總結
- 五大對象的好處
- encoding屬性設定對象所使用的編碼
- 操作鍵的兩種基本指令
- 七大資料結構
-
- 複雜度
- SDS
-
- SDS 與C字元串的差別
- hashtable
- 雙端連結清單linkedlist
- 壓縮清單（ziplist）
- 跳表
- 整數集合intset
- quicklist
- 為什麼list需要用quicklist？
- 面試題
-
- 為什麼String類型需要64位元組的記憶體空間？
- redis為什麼使用整數數組和壓縮清單？
- Redis為什麼用跳表而不用平衡樹？
- intset與ziplist相比
- 海量資料統計
-
- bitmap
- HyperLogLog基數統計
- 聚合統計、排序統計、二值狀态統計、基數統計總結
- GEO（LBS）
- 面試題
-
- 如何統計出一億使用者10天連續簽到的使用者總數？
- 設計一個資料結構
資料類型和資料結構對應
List、Hash、Set和Sorted Set被稱為
集合類型
，它們的特點是一個鍵對應了一個集合的資料。而String是
一對一
。
全局hash表和expires過期字典
詳細原文
- 資料庫主要由
dict和 expires
- 資料庫的鍵總是一個
string
- 當資料量過大，redis會采用rehash來解決hash沖突，rehash中如果一次性遷移所有資料會導緻線程阻塞，可以采用
漸進式rehash
- Redis使用
惰性删除和定期删除
五大對象
口 Redis 資料庫中的每個鍵值對的鍵和值都是一個對象。
口伺服器在執行某些指令之前， 會先檢查給定鍵的類型能否執行指定的指令， 而檢查一個鍵的類型就是檢查鍵的
值對象的類型
。
口Redis的對象系統帶有
引用計數
實作的
記憶體回收機制
， 當一個對象不再被使用時， 該對象所占用的記憶體就會被
自動釋放
。
口Redis 會共享值為0到9999的字元串對象。
口對象會記錄自己的最後一次被通路的時間
LRU
， 這個時間可以用于計算對象的
空轉時間
。
應用場景總結
| 對象 | 适用場景 |
|---|---|
| String | 緩存功能、計數、共享Session、限速 |
| hash | 存儲對象 |
| list | 消息隊列、文章清單（可以分頁）、棧、隊列、有限集合 |
| set | 利用交集求共同好友、 利用唯一性，可以統計通路網站的所有獨立IP、 推薦功能（給使用者打上tag，推薦的時候根據 |
| zset | 排行榜系統、延遲消息隊列 |
五大對象的好處
Redis 并沒有直接使用SDS這類的資料結構來實作鍵值對資料庫， 而是基于這些資料結建構立了一個包含
五種不同類型對象的對象系統
1、通過這五種不同類型的對象， Redis 可以在執行指令之前， 根據對象的類型來判斷一個對象是否可以執行給定的指令。
2、我們可以針對不同的使用場景， 為對象設定多種不同的資料結構， 進而優化對象在不同場景下的使用效率。
3、Redis 的對象系統還實作了基于
引用計數技術
的
記憶體回收機制
，當程式不再使用某個對象的時候， 這個對象所占用的記憶體就會被自動釋放；
4、Redis 還通過
引用計數技術
實作了對象共享機制， 這一機制可以在适當的條件下， 通過讓多個資料庫鍵共享同一個對象來節約記憶體。
5、最後， Redis 的對象帶有
通路時間記錄資訊
， 該資訊可以用于計算資料庫鍵的空轉時長， 在伺服器啟用了
maxmemory
功能的情況下，空轉時長較大的那些鍵可能會
優先被伺服器删除
。
encoding屬性設定對象所使用的編碼
Redis可以根據不同的使用場景來為一個對象設定不同的編碼， 進而優化對象在某一場景下的效率。極大地提升了Redis的靈活性和效率
例如String對象有
int raw embstr
三種不同的編碼
操作鍵的兩種基本指令
Redis中用于操作鍵的指令基本上可以分為兩種類型。
1、可以對5種鍵都進行操作，如下：
2、隻能對特定的鍵執行操作，一共五種 ，例如：set 、get 隻能對字元串，hset、hget 隻能對hash鍵。
七大資料結構
複雜度
對于String類型來說，找到哈希桶就能直接增删改查了，是以，哈希表的
O(1)
操作複雜度也就是它的複雜度了。
和String類型不同，一個集合類型的值，第一步是通過
全局哈希表
找到對應的哈希桶位置，第二步是在集合中再增删改查。
時間複雜度如下：
- 單元素操作是基礎；
- 範圍操作非常耗時；
- 統計操作通常高效；
- 例外情況隻有幾個。
第一，
單元素操作
，是指每一種集合類型對單個資料實作的
增删改查
操作。例如，Hash類型的HGET、HSET和HDEL，這些操作的複雜度由
底層采用的資料結構
決定，是以它們的複雜度都是O(1)。
集合類型支援同時對多個元素進行增删改查，例如Hash類型的HMGET和HMSET，這些操作的複雜度，就是由單個元素操作複雜度和元素個數決定的。例如，HMSET增加M個元素時，複雜度就
從O(1)變成O(M)
。
第二，
範圍操作
，是指集合類型中的
周遊操作
，可以傳回集合中的所有資料，比如Hash類型的
HGETALL
和Set類型的
SMEMBERS
，這類操作的複雜度一般是
O(N)
，比較耗時，我們應該盡量避免。
Redis從2.8版本開始提供了
SCAN系列操作
（包括HSCAN，SSCAN和ZSCAN），這類操作實作了
漸進式周遊
，每次隻傳回有限數量的資料。這樣一來，相比于HGETALL、SMEMBERS這類操作來說，就避免了一次性傳回所有元素而導緻的Redis阻塞。
第三，
統計操作
，是指集合類型對集合中所有元素個數的記錄，例如LLEN和SCARD。這類操作複雜度隻有O(1)，這是因為當集合類型采用
壓縮清單、雙向連結清單、整數數組
這些資料結構時，這些結構中專門記錄了元素的個數統計，是以可以高效地完成相關操作。
第四，
例外情況
，是指某些資料結構的特殊記錄，例如壓縮清單和雙向連結清單都會記錄表頭和表尾的偏移量。這樣一來，對于List類型的
LPOP、RPOP、LPUSH、RPUSH
這四個操作來說，它們是在清單的頭尾增删元素，這就可以通過偏移量直接定位，是以它們的複雜度也隻有O(1)，可以實作快速操作。
SDS
simple dynamic string 簡單動态字元串
String類型具體是怎麼儲存資料的呢？embstr和raw底層就是SDSredis-資料結構複習資料類型和資料結構對應全局hash表和expires過期字典五大對象七大資料結構海量資料統計
SDS的定義redis-資料結構複習資料類型和資料結構對應全局hash表和expires過期字典五大對象七大資料結構海量資料統計
SDS 與C字元串的差別
| C字元串 | SDS |
|---|---|
擷取 | 擷取 |
| API是不安全的，可能會造成緩沖區溢出 | API是安全的，不會造成緩沖區溢出 |
| 修改字元串N次必然需要執行N次記憶體重配 | 空間預配置設定(記憶體重配置設定次數從必定N次降低為最多N次) 惰性空間釋放(優化縮短操作) |
| 隻能儲存文本資料 | 可以儲存二進制或文本資料，以len屬性判斷結束而不是\0 |
| 可以使用<string.h>庫中的函數 | 可以使用<string.h>庫中一部分的函數 |
hashtable
- 字典被廣泛用于實作 Redis 的各種功能， 其中包括資料庫和
哈希鍵
hashtable
哈希鍵
- Redis 中的字典使用哈希表作為底層實作， 每個字典帶有兩個哈希表， 一個平時使用， 另一個僅在進行 rehash 時使用。
- 哈希表使用
鍊位址法
單向連結清單
- 在對哈希表進行擴充或者收縮操作時， 程式需要将現有哈希表包含的所有鍵值對
rehash
rehash
漸進式
完整的字典結構：
雙端連結清單linkedlist
重點概述
- 連結清單被廣泛用于實作 Redis 的各種功能， 比如清單鍵、 釋出與訂閱、 慢查詢、 螢幕等。
- 每個連結清單節點由一個
listNode
前置節點和後置節點
雙端連結清單
- 每個連結清單使用一個
list
- 因為連結清單表頭節點的前置節點和表尾節點的後置節點
都指向 NULL
無環連結清單
- 通過為連結清單設定不同的類型特定函數， Redis 的連結清單可以用于儲存各種不同類型的值。
- 每個雙端連結清單節點都儲存了一個
字元串對象
清單元素
。
Redis的連結清單結構
redis-資料結構複習資料類型和資料結構對應全局hash表和expires過期字典五大對象七大資料結構海量資料統計 redis-資料結構複習資料類型和資料結構對應全局hash表和expires過期字典五大對象七大資料結構海量資料統計
實作的特性可以總結如下：
- 雙端：連結清單節點帶有prev和next指針， 擷取某個節點的前置節點和後置節點的複雜度都是O(1)。
- 無環： 表頭節點的prev指針和表尾節點的next 指針都指向NULL， 對連結清單的通路以NULL為終點。
-
帶表頭指針和表尾指針
通過list結構的head指針和tail指針， 程式擷取連結清單的表頭節點和表尾節點的複雜度為O(1)。
-
帶連結清單長度計數器
程式使用
list
len
- 多态：連結清單節點使用 void＊指針來儲存節點值， 并且可以通過list結構的
dup、free、 match
壓縮清單（ziplist）
可以存儲任意二進制串、資料無序、可以對每個資料項進行不同的變長編碼。
結構如下：
表頭有三個字段：
zlbytes
：清單長度
zltail
：清單尾的偏移量
zllen
：清單中的entry個數，
表尾還有一個
zlend
表示清單結束。
壓縮清單之是以能節省記憶體，就在于它是用一系列連續的entry儲存資料。這些entry會挨個兒放置在記憶體中，不需要再用額外的指針進行連接配接，這樣就可以節省指針所占用的空間。
跳表
- 跳躍表中的節點按照
分值從小到大
成員對象從小到大
- 在同一個跳躍表中， 多個節點可以包含相同的分值， 但每個節點的成員對象必須是唯一的。
- 跳躍表支援
平均 O(logN）、 最壞O(N)
批量處理節點
- Redis 使用跳躍表作為
sorted set
跳躍表
sorted set
- 在大部分情況下 ， 跳躍表的效率可以和平衡樹相媲美， 并且因為跳躍表的實作比平衡樹要來得更為簡單， 是以有不少程式都使用跳躍表來代替平衡樹。
-
skiplist
zskiplist
zskiplistNode
zskiplist
跳躍表資訊
zskiplistNode
跳躍表節點
- 每個跳躍表節點的層高都是
1~32之間的随機數
跳躍表的實作
zskiplistNode 和zskiplist 共同實作skiplist
zskiplist 包含的屬性：
header ：指向跳躍表的表頭節點。
tail ：指向跳躍表的表尾節點。
level：記錄目前跳躍表内， 層數最大的那個節點的層數（表頭節點的層數不在内）
length：記錄跳躍表的長度（表頭節點不計算在内）
zskiplistNode 結構， 該結包含以下屬性：
層（level ）
：節點中用 Ll 、 L2 、 L3 等字樣标記節點的各個層， Ll 代表第一層， L2代表第二層， 以此類推。
每個層都帶有兩個屬性：
前進指針和跨度
。 在上面的圖檔中， 連線上帶有數字的箭頭就代表前進指針， 而那個數字就是跨度。 當程式從表頭向表尾進行周遊時， 通路會沿着層的前進指針進行。
-
前進指針
表尾
-
跨度
距離
後退指針BW
：節點中用
BW
字樣标記節點的後退指針， 它指向位于目前節點的前一個節點。 後退指針在程式從表尾向表頭周遊時使用。
分值（ score ）
：各個節點中的1.0、 2.0和3.0是節點所儲存的分值。 在跳躍表中，節點按各自所儲存的分值
從小到大排列
。
成員對象（obj）
：各個節點中的o1、 o2和o3是節點所儲存的成員對象。
Redis skiplist和經典skiplist對比
- Redis skiplist的分數(score)允許重複，經典skiplist是不允許的
- 在比較時，不僅比較分數（skiplist的key），還比較資料本身（skiplist的value）。在Redis的skiplist實作中，
score+key
- 第1層連結清單不是一個單向連結清單，而是一個雙向連結清單。這是為了
友善以倒序方式
整數集合intset
- 整數集合是
集合鍵set
- 整數集合的底層實作為數組， 這個數組以
按插入有序、 無重複
- 更新操作為整數集合帶來了操作上的靈活性， 井且盡可能地節約了記憶體。
- 整數集合隻支援更新操作， 不支援降級操作。
整數集合的組成
-
contents 數組
是整數集合的底層實作，整數集合的每個元素都是 contents 數組的一個數組項， 各個項在數組中
按值從小到大
不包含任何重複項
-
length屬性
記錄了整數集合包含的 元素數量
-
encoding屬性
有三種取值int16_t、int32_t、int64_t
quicklist
quicklist是一個連結清單，連結清單的每個節點都是一個
ziplist
。
比如，一個包含3個節點的quicklist，如果每個節點的ziplist又包含4個資料項，那麼對外表現上，這個list就總共包含12個資料項。
為什麼list需要用quicklist？
- 雙向連結清單的缺點
-
記憶體開銷比較大
-
容易産生記憶體碎片
-
-
ziplist的缺點
它不利于修改操作，每次資料變動都會引發一次記憶體的重新配置設定。特别是當ziplist長度很長的時候，一次realloc可能會導緻大批量的資料拷貝，進一步降低性能。
于是，結合了雙向連結清單和ziplist的優點，quicklist就應運而生了。
面試題
為什麼String類型需要64位元組的記憶體空間？
因為記錄實際資料僅需16位元組，但是String類型還需要額外的記憶體空間記錄資料長度、空間使用等資訊，這些資訊也叫作中繼資料，占了48位元組。
是以當實際儲存的資料較小時，中繼資料的空間開銷就顯得比較大了，有點“喧賓奪主”的意思。
64位元組分為兩部分，每部分32位元組
第一個32位元組
由上面的分析得知，一個String鍵值對占32位元組，分為：
- 每個編碼的RedisObject中繼資料部分占8位元組（int、embstr、raw均為8位元組）
redis-資料結構複習資料類型和資料結構對應全局hash表和expires過期字典五大對象七大資料結構海量資料統計 - 指針部分被直接指派為8位元組的整數了
- 有效資訊占16位元組（雙Long，每個8位元組）
第二個32位元組
Redis會使用一個
全局哈希表
儲存所有鍵值對，哈希表的每一項是一個
dictEntry
的結構體，用來指向一個鍵值對。
dictEntry結構中有三個8位元組的指針，分别指向
key、value、下一個dictEntry
，三個指針共24位元組，如下圖所示：
但是，這三個指針隻有24位元組，為什麼會占用了32位元組呢？因為jemalloc在配置設定記憶體時，會根據我們申請的位元組數N，找一個比N大，但是
最接近N的2的幂次數
作為配置設定的空間，這樣可以減少頻繁配置設定的次數。
redis為什麼使用整數數組和壓縮清單？
整數數組和壓縮清單在查找時間複雜度方面并沒有很大的優勢，那為什麼Redis還會把它們作為底層資料結構呢？
節省記憶體空間
整數數組和壓縮清單都是在記憶體中配置設定一塊
連續的位址空間
，然後把集合中的元素一個接一個地放在這塊空間内，非常緊湊。當資料量比較小時适合使用，當資料量大了就不适合了。
Redis為什麼用跳表而不用平衡樹？
範圍查找的時候，平衡樹比skiplist操作要複雜。
- 在平衡樹上，我們找到指定範圍的小值之後，還需要以
中序周遊
- 在skiplist上進行範圍查找就非常簡單，隻需要在找到小值之後，對第1層連結清單進行若幹步的周遊就可以實作。
skiplist插入和删除更簡單
平衡樹的插入和删除操作可能引發子樹的調整，邏輯複雜，而skiplist的插入和删除隻需要修改相鄰節點的指針，操作簡單又快速。
skiplist記憶體占用更小
從記憶體占用上來說，skiplist比平衡樹更小一些。一般來說，平衡樹每個節點包含2個指針（分别指向左右子樹），而skiplist每個節點包含的指針數目平均為1/(1-p)，具體取決于參數p的大小。如果像Redis裡的實作一樣，取p=1/4，那麼平均每個節點包含1.33個指針，比平衡樹更有優勢。
從算法實作難度上來比較，skiplist比平衡樹要簡單得多。
intset與ziplist相比
ziplist可以存儲任意二進制串，而intset隻能存儲整數。
ziplist是無序的，而intset是從
小到大
有序的。是以，在ziplist上查找隻能周遊，而在intset上可以進行二分查找，性能更高。
ziplist可以對每個資料項進行不同的
變長編碼
，而intset隻能整體使用一個統一的編碼（encoding）。
海量資料統計
bitmap
是什麼？
Bitmap是用String類型作為底層資料結構實作的一種
統計二值狀态
的資料類型。String類型是會儲存為二進制的位元組數組，是以，Redis就把位元組數組的每個bit位利用起來，用來表示一個元素的二值狀态。你可以把Bitmap看作是一個
bit數組
。
bitmap底層資料結構圖示：
- redisObject.type的值為
REDIS_STRING
- sdshdr.len的值為1，表示這個 SDS 儲存了一位元組長的位數組。
- buf數組中的buf[0］位元組儲存了一位元組長的位數組。
- buf數組中的buf[1］位元組儲存了sds程式自動追加到值的末尾的空字元‘\0’。
四個指令
redis提供了
SETBIT、 GETBIT、BITCOUNT、BITOP
四個指令用于處理bitmap。
-
SETBIT
用于為
指定偏移量
二進制位
-
GETBIT
用于擷取位數組指定偏移量上的二進制位的值
-
BITCOUNT
用于統計位數組裡面， 值為1的二進制位的數量
-
BITOP
可以對多個位數組進行
按位與（ and ）、 按位或（ or ）、 按位異或( xor）、按位取反（ not ）
HyperLogLog基數統計
HyperLogLog是一種用于
基數統計（去重）
的資料集合類型，它的最大優勢就在于，當集合元素數量非常多時，它計算基數所需的空間總是固定的，而且還很小。
典型應用場景：一天内有多少使用者登入，因為使用者可能重複登入，但是隻記一次，是以需要去重。
存在以下的特點：
- 能夠使用極少的記憶體來統計巨量的資料，在 Redis 中實作的 HyperLogLog，隻需要
12K記憶體
2^64
- 計數存在一定的誤差，誤差率整體較低。标準誤差為 0.81% 。
- 誤差可以被設定輔助計算因子進行降低。
實作原理
内部維護了
16384
個桶來記錄各自桶的元素數量，當添加元素時，通過 hash 算法将這個元素分派到其中的一個桶中，同樣的元素總是會散列到同樣的桶。這樣總的去重計數就是所有非零桶的總和。
聚合統計、排序統計、二值狀态統計、基數統計總結
GEO（LBS）
将使用者給定的
地理位置資訊
儲存起來，并對這些資訊進行操作。
GEO常用語LBS（Location-Based Service）
GEO本身并沒有設計新的底層資料結構，而是直接使用了
Sorted Set
集合類型
面試題
如何統計出一億使用者10天連續簽到的使用者總數？
海量資料+二值狀态 ====》bitmap
Bitmap支援用
BITOP
指令對多個Bitmap按位做
與、或、異或
的操作，操作的結果會儲存到一個新的Bitmap中。
我以按位“與”操作為例來具體解釋一下。從下圖中，可以看到，三個Bitmap bm1、bm2和bm3，對應bit位做“與”操作，結果儲存到了一個新的Bitmap中
隻有全1，最後的bitmap中相應位置才能為1。
由此想到，用bitmap的每一位記錄一位使用者的打卡情況（打了為1，沒有打為0）。然後對10個Bitmap做
BITTOP“與”操作
，得到的結果也是一個Bitmap。在這個Bitmap中，隻有10天都簽到的使用者對應的bit位上的值才會是1。最後，我們可以用
BITCOUNT
統計下Bitmap中的1的個數，這就是連續簽到10天的使用者總數了。
記憶體開銷
每天使用1個1億位的Bitmap，大約占12MB的記憶體（10^8/8/1024/1024），10天的Bitmap的記憶體開銷約為120MB，記憶體壓力不算太大。
在實際應用還可以進行優化，比如對Bitmap設定
過期時間
，讓Redis自動删除不再需要的簽到記錄，以節省記憶體開銷。
設計一個資料結構
Redis鍵值對中的每一個值都是用RedisObject儲存的，是以先要了解這個基本對象結構
RedisObject的内部組成包括了：
- type：表示值的類型，涵蓋了我們前面學習的五大基本類型；
- encoding：是值的編碼方式，用來表示Redis中實作各個基本類型的底層資料結構，例如SDS、壓縮清單、哈希表、跳表等；
- lru：記錄了這個對象最後一次被通路的時間，用于淘汰過期的鍵值對；
- refcount：記錄了對象的引用計數；
- *ptr：是指向資料的指針。
了解了RedisObject結構後，定義一個新的資料類型也就不難了。
設計步驟：