概述

Redis 是一個開源的高性能鍵值數(shù)據(jù)庫，它支持多種數(shù)據(jù)類型，可以滿足不同的業(yè)務(wù)需求。本文將介紹 Redis 的10種數(shù)據(jù)類型，分別是

• string（字符串）
• hash（哈希）
• list（列表）
• set（集合）
• zset（有序集合）
• stream（流）
• geospatial（地理）
• bitmap（位圖）
• bitfield（位域）
• hyperloglog（基數(shù)統(tǒng)計）

String

概述

string 是 Redis 最基本的數(shù)據(jù)類型，它可以存儲任意類型的數(shù)據(jù)，比如文本、數(shù)字、圖片或者序列化的對象。一個 string 類型的鍵最大可以存儲 512 MB 的數(shù)據(jù)。

string 類型的底層實現(xiàn)是 SDS（simple dynamic string），它是一個動態(tài)字符串結(jié)構(gòu)，由長度、空閑空間和字節(jié)數(shù)組三部分組成。SDS有3種編碼類型：

• embstr：占用64Bytes的空間，存儲44Bytes的數(shù)據(jù)
• raw：存儲大于44Bytes的數(shù)據(jù)
• int：存儲整數(shù)類型

embstr和raw存儲字符串?dāng)?shù)據(jù)，int存儲整型數(shù)據(jù)

應(yīng)用場景

string 類型的應(yīng)用場景非常廣泛，比如：

• 緩存數(shù)據(jù)，提高訪問速度和降低數(shù)據(jù)庫壓力。
• 計數(shù)器，利用 incr 和 decr 命令實現(xiàn)原子性的加減操作。
• 分布式鎖，利用 setnx 命令實現(xiàn)互斥訪問。
• 限流，利用 expire 命令實現(xiàn)時間窗口內(nèi)的訪問控制。

底層原理

embstr結(jié)構(gòu)

embstr 結(jié)構(gòu)存儲小于等于44個字節(jié)的字符串，embstr 每次開辟64個byte的空間

• 前19個byte用于存儲embstr 結(jié)構(gòu)
• 中間的44個byte存儲數(shù)據(jù)
• 最后為符號

raw結(jié)構(gòu)

image

embstr和raw的轉(zhuǎn)換

在存儲字符串的時候，redis會根據(jù)數(shù)據(jù)的長度判斷使用哪種結(jié)構(gòu)

• 如果長度小于等于44個字節(jié)，就會選擇embstr 結(jié)構(gòu)
• 如果長度大于44個byte，就會選擇raw結(jié)構(gòu)

127.0.0.1:6379>objectencodingstr
"embstr"
#str賦值44個字節(jié)的字符串
127.0.0.1:6379>setstr1234567890123456789012345678901234567890abcd
OK
127.0.0.1:6379>objectencodingstr
"embstr"
#str2賦值45個字節(jié)的字符串
127.0.0.1:6379>setstr21234567890123456789012345678901234567890abcde
OK
127.0.0.1:6379>objectencodingstr2
"raw"
127.0.0.1:6379>setnum123
OK
127.0.0.1:6379>objectencodingnum
"int"

Hash

概述

hash 是一個鍵值對集合，它可以存儲多個字段和值，類似于編程語言中的 map 對象。一個 hash 類型的鍵最多可以存儲 2^32 - 1 個字段。

Hash類型的底層實現(xiàn)有三種：

• ziplist：壓縮列表，當(dāng)hash達(dá)到一定的閾值時，會自動轉(zhuǎn)換為hashtable結(jié)構(gòu)
• listpack：緊湊列表，在Redis7.0之后，listpack正式取代ziplist。同樣的，當(dāng)hash達(dá)到一定的閾值時，會自動轉(zhuǎn)換為hashtable結(jié)構(gòu)
• hashtable：哈希表，類似map

應(yīng)用場景

hash 類型的應(yīng)用場景主要是存儲對象，比如：

• 用戶信息，利用 hset 和 hget 命令實現(xiàn)對象屬性的增刪改查。
• 購物車，利用 hincrby 命令實現(xiàn)商品數(shù)量的增減。
• 配置信息，利用 hmset 和 hmget 命令實現(xiàn)批量設(shè)置和獲取配置項。

底層原理

Redis在存儲hash結(jié)構(gòu)的數(shù)據(jù)，為了達(dá)到內(nèi)存和性能的平衡，也針對少量存儲和大量存儲分別設(shè)計了兩種結(jié)構(gòu)，分別為：

• ziplist（redis7.0之前使用）和listpack（redis7.0之后使用）
• hashTable

從ziplist/listpack編碼轉(zhuǎn)換為hashTable編碼是通過判斷元素數(shù)量或單個元素Key或Value的長度決定的：

• hash-max-ziplist-entries：表示當(dāng)hash中的元素數(shù)量小于或等于該值時，使用ziplist編碼，否則使用hashtable編碼。ziplist是一種壓縮列表，它可以節(jié)省內(nèi)存空間，但是訪問速度較慢。hashtable是一種哈希表，它可以提高訪問速度，但是占用內(nèi)存空間較多。默認(rèn)值為512。
• hash-max-ziplist-value：表示當(dāng) hash中的每個元素的 key 和 value 的長度都小于或等于該值時，使用 ziplist編碼，否則使用 hashtable編碼。默認(rèn)值為 64。

ziplist與listpack

ziplist/listpack都是hash結(jié)構(gòu)用來存儲少量數(shù)據(jù)的結(jié)構(gòu)。從Redis7.0后，hash默認(rèn)使用listpack結(jié)構(gòu)。因為 ziplist有一個致命的缺陷，就是連鎖更新，當(dāng)一個節(jié)點的長度發(fā)生變化時，可能會導(dǎo)致后續(xù)所有節(jié)點的長度字段都要重新編碼，這會造成極差的性能

ziplist結(jié)構(gòu)

ziplist是一種緊湊的鏈表結(jié)構(gòu)，它將所有的字段和值順序地存儲在一塊連續(xù)的內(nèi)存中。Redis中ziplist源碼

typedefstruct{
/*當(dāng)使用字符串時,slen表示為字符串長度*/
unsignedchar*sval;
unsignedintslen;
/*當(dāng)使用整形時，sval為NULL,lval為ziplistEntry的value*/
longlonglval;
}ziplistEntry;

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

image

zipList的連鎖更新問題

ziplist的每個entry都包含previous_entry_length來記錄上一個節(jié)點的大小，長度是1個或5個byte：

• 如果前一節(jié)點的長度小于254個byte，則采用1個byte來保存這個長度值
• 如果前一節(jié)點的長度大于等于254個byte，則采用5個byte來保存這個長度值，第一個byte為0xfe，后四個byte才是真實長度數(shù)據(jù)

假設(shè)，現(xiàn)有有N個連續(xù)、長度為250~253個byte的entry，因此entry的previous_entry_length屬性占用1個btye

image

當(dāng)?shù)谝还?jié)長度大于等于254個bytes，導(dǎo)致第二節(jié)previous_entry_length變?yōu)?個bytes，第二節(jié)的長度由250變?yōu)?54。而第二節(jié)長度的增加必然會影響第三節(jié)的previous_entry_length。ziplist這種特殊套娃的情況下產(chǎn)生的連續(xù)多次空間擴(kuò)展操作成為連鎖更新。新增、刪除都可能導(dǎo)致連鎖更新的產(chǎn)生。

listpack是如何解決的

image

1. 由于ziplist需要倒著遍歷，所以需要用previous_entry_length記錄前一個entry的長度。而listpack可以通過total_bytes和end計算出來。所以previous_entry_length不需要了。
2. listpack 的設(shè)計徹底消滅了 ziplist 存在的級聯(lián)更新行為，元素與元素之間完全獨立，不會因為一個元素的長度變長就導(dǎo)致后續(xù)的元素內(nèi)容會受到影響。
3. 與ziplist做對比的話，犧牲了內(nèi)存使用率，避免了連鎖更新的情況。從代碼復(fù)雜度上看，listpack相對ziplist簡單很多，再把增刪改統(tǒng)一做處理，從listpack的代碼實現(xiàn)上看，極簡且高效。

hashTable

hashTable是一種散列表結(jié)構(gòu)，它將字段和值分別存儲在兩個數(shù)組中，并通過哈希函數(shù)計算字段在數(shù)組中的索引

image

Redis中hashTable源碼

structdict{
dictType*type;
dictEntry**ht_table[2];
unsignedlonght_used[2];
longrehashidx;/*當(dāng)進(jìn)行rehash時，rehashidx為-1*/
int16_tpauserehash;/*如果rehash暫停，pauserehash則大于0，（小于0表示代碼錯誤）*/
signedcharht_size_exp[2];/*哈希桶的個數(shù)(size=1<
};

typedefstructdict{
dictEntry**table;
dictType*type;
unsignedlongsize;
unsignedlongsizemask;
unsignedlongused;
void*privdata;
}dict;

typedefstructdictEntry{
void*key;
void*val;
structdictEntry*next;
}dictEntry;

ziplist和hashTable的轉(zhuǎn)換

image

127.0.0.1:6379>hseth1id123456789012345678901234567890123456789012345678901234567890abcd
(integer)1
127.0.0.1:6379>objectencodingh1
"ziplist"
127.0.0.1:6379>hseth2id123456789012345678901234567890123456789012345678901234567890abcde
(integer)1
127.0.0.1:6379>objectencodingh2
"hashtable"

ziplist的廢棄

顯然是ziplist在field個數(shù)太大、key太長、value太長三者有其一的時候會有以下問題：

1. ziplist每次插入都有開辟空間，連續(xù)的
2. 查詢的時候，需要從頭開始計算，查詢速度變慢

hashTable變得越來越長怎么辦

擴(kuò)容，hashTabel是怎么擴(kuò)容的？使用的是漸進(jìn)式擴(kuò)容rehash。rehash會重新計算哈希值，且將哈希桶的容量擴(kuò)大。

rehash 步驟

image

擴(kuò)展哈希和收縮哈希都是通過執(zhí)行rehash來完成，這其中就涉及到了空間的分配和釋放，主要經(jīng)過以下五步：

1. 為字典dict的ht[1]哈希表分配空間，其大小取決于當(dāng)前哈希表已保存節(jié)點數(shù)（即：

   ht[0].used
   

   ）：

• 如果是擴(kuò)展操作則ht[1]的大小為2的n次方中第一個大于等于ht[0].used * 2屬性的值（比如used=3，此時ht[0].used * 2=6，故2的3次方為8就是第一個大于used * 2的值（2 的 2 次方 6））。
• 如果是收縮操作則ht[1]大小為 2 的 n 次方中第一個大于等于ht[0].used的值

• 將字典中的屬性rehashidx的值設(shè)置為0，表示正在執(zhí)行rehash操作

• 將ht[0]中所有的鍵值對依次重新計算哈希值，并放到ht[1]數(shù)組對應(yīng)位置，每完成一個鍵值對的rehash之后rehashidx的值需要自增1

• 當(dāng)ht[0]中所有的鍵值對都遷移到ht[1]之后，釋放ht[0]，并將ht[1]修改為ht[0]，然后再創(chuàng)建一個新的ht[1]數(shù)組，為下一次rehash做準(zhǔn)備

• 將字典中的屬性rehashidx設(shè)置為-1，表示此次rehash操作結(jié)束，等待下一次rehash

漸進(jìn)式 rehash

Redis中的這種重新哈希的操作因為不是一次性全部rehash，而是分多次來慢慢的將ht[0]中的鍵值對rehash到ht[1]，故而這種操作也稱之為漸進(jìn)式rehash。漸進(jìn)式rehash可以避免集中式rehash帶來的龐大計算量，是一種分而治之的思想。

在漸進(jìn)式rehash過程中，因為還可能會有新的鍵值對存進(jìn)來，此時Redis的做法是新添加的鍵值對統(tǒng)一放入ht[1]中，這樣就確保了ht[0]鍵值對的數(shù)量只會減少。

當(dāng)正在執(zhí)行rehash操作時，如果服務(wù)器收到來自客戶端的命令請求操作，則會先查詢ht[0]，查找不到結(jié)果再到ht[1]中查詢

List

概述

list 是一個有序的字符串列表，它按照插入順序排序，并且支持在兩端插入或刪除元素。一個 list 類型的鍵最多可以存儲 2^32 - 1 個元素。

redis3.2以后，list 類型的底層實現(xiàn)只有一種結(jié)構(gòu)，就是quicklist。版本不同時，底層實現(xiàn)是不同的，下面會講解。

應(yīng)用場景

list 類型的應(yīng)用場景主要是實現(xiàn)隊列和棧，比如：

• 消息隊列，利用 lpush 和 rpop 命令實現(xiàn)生產(chǎn)者消費(fèi)者模式。
• 最新消息，利用 lpush 和 ltrim 命令實現(xiàn)固定長度的時間線。
• 歷史記錄，利用 lpush 和 lrange 命令實現(xiàn)瀏覽記錄或者搜索記錄。

底層原理

在講解list結(jié)構(gòu)之前，需要先說明一下list結(jié)構(gòu)編碼的更替，如下

• 在Redis3.2之前，list使用的是linkedlist和ziplist
• 在Redis3.2~Redis7.0之間，list使用的是quickList，是linkedlist和ziplist的結(jié)合
• 在Redis7.0之后，list使用的也是quickList，只不過將ziplist轉(zhuǎn)為listpack，它是listpack、linkedlist結(jié)合版

linkedlist與ziplist

在Redis3.2之前，linkedlist和ziplist兩種編碼可以選擇切換，它們之間的轉(zhuǎn)換關(guān)系如圖

同樣地，ziplist轉(zhuǎn)為linkedlist的條件可在redis.conf配置

list-max-ziplist-entries 512
list-max-ziplist-value 64

quickList（ziplist、linkedlist結(jié)合版）

quicklist存儲了一個雙向列表，每個列表的節(jié)點是一個ziplist，所以實際上quicklist并不是一個新的數(shù)據(jù)結(jié)構(gòu)，它就是linkedlist和ziplist的結(jié)合，然后被命名為快速列表。ziplist內(nèi)部entry個數(shù)可在redis.conf配置

list-max-ziplist-size -2
# -5: 每個ziplist最多為 64 kb  <-- 影響正常負(fù)載，不推薦
# -4: 每個ziplist最多為 32 Kb  <-- 不推薦
# -3: 每個ziplist最多為 16 Kb  <-- 最好不要使用
# -2: 每個ziplist最多為 8 Kb   <-- 好
# -1: 每個ziplist最多為 4 Kb   <-- 好
# 正數(shù)為ziplist內(nèi)部entry個數(shù)

ziplist通過特定的LZF壓縮算法來將節(jié)點進(jìn)行壓縮存儲，從而更進(jìn)一步的節(jié)省空間，而很多場景都是兩端元素訪問率最高，我們可以通過配置list-compress-depth來排除首尾兩端不壓縮的entry個數(shù)。

list-compress-depth 0
# - 0：不壓縮（默認(rèn)值）
# - 1：首尾第 1 個元素不壓縮
# - 2：首位前 2 個元素不壓縮
# - 3：首尾前 3 個元素不壓縮
# - 以此類推

quickList（listpack、linkedlist結(jié)合版）

和Hash結(jié)構(gòu)一樣，因為ziplist有連鎖更新問題，redis7.0將ziplist替換為listpack，下面是新quickList的結(jié)構(gòu)圖

image

Redis中l(wèi)istpack源碼

typedefstructquicklist{
quicklistNode*head;
quicklistNode*tail;
unsignedlongcount;/*所有列表包中所有條目的總數(shù)，占用16bits，最大65536*/
unsignedlonglen;/*quicklistNode的數(shù)量*/
signedintfill:QL_FILL_BITS;/*單個節(jié)點的填充因子*/
unsignedintcompress:QL_COMP_BITS;/*不壓縮的端節(jié)點深度；0=off */
unsignedintbookmark_count:QL_BM_BITS;
quicklistBookmarkbookmarks[];
}quicklist;
typedefstructquicklistNode{
structquicklistNode*prev;
structquicklistNode*next;
unsignedchar*entry;
size_tsz;/*當(dāng)前entry占用字節(jié)*/
unsignedintcount:16;/*listpack元素個數(shù)，最大65535*/
unsignedintencoding:2;/*RAW==1orLZF==2*/
unsignedintcontainer:2;/*PLAIN==1orPACKED==2*/
unsignedintrecompress:1;/*當(dāng)前l(fā)istpack是否需要再次壓縮*/
unsignedintattempted_compress:1;/*測試用*/
unsignedintextra:10;/*備用*/
}quicklistNode;

listpack內(nèi)部entry個數(shù)可在redis.conf配置

List-Max-listpack-size -2
# -5: 每個listpack最多為 64 kb  <-- 影響正常負(fù)載，不推薦
# -4: 每個listpack最多為 32 Kb  <-- 不推薦
# -3: 每個listpack最多為 16 Kb  <-- 最好不要使用
# -2: 每個listpack最多為 8 Kb   <-- 好
# -1: 每個listpack最多為 4 Kb   <-- 好
# 正數(shù)為listpack內(nèi)部entry個數(shù)

Set

概述

set 是一個無序的字符串集合，它不允許重復(fù)的元素。一個 set 類型的鍵最多可以存儲 2^32 - 1 個元素。

set 類型的底層實現(xiàn)有兩種：

• intset，整數(shù)集合
• hashtable（哈希表）。哈希表和 hash 類型的哈希表相同，它將元素存儲在一個數(shù)組中，并通過哈希函數(shù)計算元素在數(shù)組中的索引

Redis 會根據(jù) set 中元素的數(shù)量和類型來選擇合適的編碼方式，當(dāng) set 達(dá)到一定的閾值時，會自動轉(zhuǎn)換編碼方式。

typedefstructintset{
uint32_tencoding;
uint32_tlength;
int8_tcontents[];
}intset;

應(yīng)用場景

set 類型的應(yīng)用場景主要是利用集合的特性，比如：

• 去重，利用 sadd 和 scard 命令實現(xiàn)元素的添加和計數(shù)。
• 交集，并集，差集，利用 sinter，sunion 和 sdiff 命令實現(xiàn)集合間的運(yùn)算。
• 隨機(jī)抽取，利用 srandmember 命令實現(xiàn)隨機(jī)抽獎或者抽樣。

底層原理

在講解set結(jié)構(gòu)之前，需要先說明一下set結(jié)構(gòu)編碼的更替，如下

• 在Redis7.2之前，set使用的是intset和hashtable
• 在Redis7.2之后，set使用的是intset、listpack、hashtable

intset

intset是一種緊湊的數(shù)組結(jié)構(gòu)，它只保存int類型的數(shù)據(jù)，它將所有的元素按照從小到大的順序存儲在一塊連續(xù)的內(nèi)存中。intset會根據(jù)傳入的數(shù)據(jù)大小，encoding分為int16_t、int32_t、int64_t

127.0.0.1:6379>saddset123
(integer)1
127.0.0.1:6379>objectencodingset
"intset"
127.0.0.1:6379>saddsetabcd
(integer)1
127.0.0.1:6379>objectencodingset
"hashtable"

intset 和 hashtable 的轉(zhuǎn)換

在Redis7.2之前，當(dāng)一個集合滿足以下兩個條件時，Redis 會選擇使用intset編碼：

• 集合對象保存的所有元素都是整數(shù)值
• 集合對象保存的元素數(shù)量小于等于512個（默認(rèn)）

intset最大元素數(shù)量可在redis.conf配置

set-max-intset-entries 512

為什么加入了listpack

在redis7.2之前，sds類型的數(shù)據(jù)會直接放入到編碼結(jié)構(gòu)式為hashtable的set中。其中，sds其實就是redis中的string類型。

而在redis7.2之后，sds類型的數(shù)據(jù)，首先會使用listpack結(jié)構(gòu)當(dāng) set 達(dá)到一定的閾值時，才會自動轉(zhuǎn)換為hashtable。

添加listpack結(jié)構(gòu)是為了提高內(nèi)存利用率和操作效率，因為 hashtable 的空間開銷和碰撞概率都比較高。

hashtable 的空間開銷高

hashtable 的空間開銷高是因為它需要預(yù)先分配一個固定大小的數(shù)組來存儲鍵值對，而這個數(shù)組的大小通常要大于實際存儲的元素個數(shù)，以保證較低的裝載因子。裝載因子是指 hashtable 中已經(jīng)存儲的元素個數(shù)和數(shù)組大小的比值，它反映了 hashtable 的空間利用率

• 如果裝載因子過高，那么 hashtable 的性能會下降，因為碰撞的概率會增加
• 如果裝載因子過低，那么 hashtable 的空間利用率會下降，因為數(shù)組中會有很多空閑的位置

因此，hashtable 需要在裝載因子和空間利用率之間做一個平衡，通常裝載因子的推薦值是 0.75

hashtable 的碰撞概率高

hashtable 的碰撞概率高是因為它使用了一個散列函數(shù)來將任意長度的鍵映射到一個有限范圍內(nèi)的整數(shù)，作為數(shù)組的索引

散列函數(shù)的設(shè)計很重要，它應(yīng)該盡可能地保證不同的鍵能夠均勻地分布在數(shù)組中，避免出現(xiàn)某些位置過于擁擠，而其他位置過于稀疏的情況。然而，由于散列函數(shù)的輸出范圍是有限的，而鍵的取值范圍是無限的，所以不可能完全避免兩個不同的鍵被散列到同一個位置上，這就產(chǎn)生了碰撞。碰撞會影響 hashtable 的性能，因為它需要額外的處理方式來解決沖突，比如開放尋址法或者鏈地址法

舉例說明，假設(shè)有一個大小為8的hashtable，使用取模運(yùn)算作為散列函數(shù)，即h(k) = k mod 8?，F(xiàn)在有四個鍵：5，13，21，29，它們都被散列到索引1處

image

這就是一個碰撞的例子，因為四個鍵都映射到了同一個索引。這種情況可能是由于以下原因造成的：

• 散列函數(shù)的選擇不合適，沒有充分利用hashtable的空間。
• 鍵的分布不均勻，有些區(qū)間的鍵出現(xiàn)的頻率更高。
• hashtable的大小太小，不能容納所有的鍵。

為了解決碰撞，redis采用了鏈地址法。就是在每個索引處維護(hù)一個鏈表，存儲所有散列到該索引的鍵。但是，如果鏈表過長，查找效率會降低。因此，一般建議保持hashtable的負(fù)載因子（即鍵的數(shù)量除以hashtable的大?。┰谝欢ǚ秶鷥?nèi)，比如0.5到0.75之間。如果負(fù)載因子過高或過低，可以通過擴(kuò)容或縮容來調(diào)整hashtable的大小

intset 、listpack和hashtable的轉(zhuǎn)換

intset 、listpack和hashtable這三者的轉(zhuǎn)換時根據(jù)要添加的數(shù)據(jù)、當(dāng)前set的編碼和閾值決定的。

• 如果要添加的數(shù)據(jù)是整型，且當(dāng)前set的編碼為intset，如果超過閾值由intset直接轉(zhuǎn)為hashtable

  閾值條件為：set-max-intset-entries ，intset最大元素個數(shù)，默認(rèn)512

• 如果要添加的數(shù)據(jù)是字符串，分為三種情況

  閾值條件為：set-max-listpack-entries：最大元素個數(shù)，默認(rèn)128set_max_listpack_value：最大元素大小，默認(rèn)64以上兩個條件需要同時滿足才能進(jìn)行編碼轉(zhuǎn)換

  • 當(dāng)前set的編碼為intset：如果沒有超過閾值，轉(zhuǎn)換為listpack；否則，直接轉(zhuǎn)換為hashtable
  • 當(dāng)前set的編碼為listpack：如果超過閾值，就轉(zhuǎn)換為hashtable
  • 當(dāng)前set的編碼為hashtable：直接插入，編碼不會進(jìn)行轉(zhuǎn)換

ZSet

概述

Redis 中的 zset 是一種有序集合類型，它可以存儲不重復(fù)的字符串元素，并且給每個元素賦予一個排序權(quán)重值（score）。Redis 通過權(quán)重值來為集合中的元素進(jìn)行從小到大的排序。zset 的成員是唯一的，但權(quán)重值可以重復(fù)。一個 zset 類型的鍵最多可以存儲 2^32 - 1 個元素。

Redis中zset源碼

typedefstructzskiplistNode{
sdsele;
doublescore;
structzskiplistNode*backward;
structzskiplistLevel{
structzskiplistNode*forward;
unsignedlongspan;
}level[];
}zskiplistNode;

typedefstructzskiplist{
structzskiplistNode*header,*tail;
unsignedlonglength;
intlevel;
}zskiplist;

typedefstructzset{
dict*dict;
zskiplist*zsl;
}zset;

應(yīng)用場景

zset 類型的應(yīng)用場景主要是利用分?jǐn)?shù)和排序的特性，比如：

• 排行榜，利用 zadd 和 zrange 命令實現(xiàn)分?jǐn)?shù)的更新和排名的查詢
• 延時隊列，利用 zadd 和 zpopmin 命令實現(xiàn)任務(wù)的添加和執(zhí)行，并且可以定期地獲取已經(jīng)到期的任務(wù)
• 訪問統(tǒng)計，可以使用 zset 來存儲網(wǎng)站或者文章的訪問次數(shù)，并且可以按照訪問量進(jìn)行排序和篩選。

底層原理

Redis在存儲zset結(jié)構(gòu)的數(shù)據(jù)，為了達(dá)到內(nèi)存和性能的平衡，針對少量存儲和大量存儲分別設(shè)計了兩種結(jié)構(gòu)，分別為：

• ziplist（redis7.0之前使用）和listpack（redis7.0之后使用）
• skiplist

當(dāng) zset 中的元素個數(shù)和元素值的長度比較小的時候，Redis 使用ziplist/listpack來節(jié)省內(nèi)存空間。當(dāng) zset 中的元素個數(shù)和元素值的長度達(dá)到一定閾值時，Redis 會自動將ziplist/listpack轉(zhuǎn)換為skiplist，以提高操作效率

具體來說，當(dāng) zset 同時滿足以下兩個條件時，會使用 listpack作為底層結(jié)構(gòu)：

• 元素個數(shù)小于 zset_max_listpack_entries ，默認(rèn)值為 128
• 元素值的長度小于zset_max_listpack_value，默認(rèn)值為 64

當(dāng) zset 中不滿足以上兩個條件時，會使用 skiplist 作為底層結(jié)構(gòu)。

skiplist

跳躍表是一種隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)，實質(zhì)就是一種可以進(jìn)行二分查找的有序鏈表。跳躍表在原有的有序鏈表上面增加了多級索引，通過索引來實現(xiàn)快速查找。跳躍表不僅能提高搜索性能，同時也可以提高插入和刪除操作的性能

image

跳躍表相比于其他平衡樹結(jié)構(gòu)，有以下幾個優(yōu)點和缺點：

優(yōu)點：

• 實現(xiàn)簡單，易于理解和調(diào)試
• 插入和刪除操作只需要修改局部節(jié)點的指針，不需要像平衡樹那樣進(jìn)行全局調(diào)整
• 可以利用空間換時間，通過增加索引層來提高查找效率
• 支持快速的范圍查詢，可以方便地返回指定區(qū)間內(nèi)的所有元素

缺點：

• 空間復(fù)雜度較高，需要額外存儲多級索引
• 隨機(jī)性太強(qiáng)，性能不穩(wěn)定，最壞情況下可能退化成鏈表
• 不支持快速的倒序遍歷，需要額外的指針來實現(xiàn)

redis的skiplist

skiplist有一個層數(shù)上的問題，當(dāng)層數(shù)過多，會影響查詢效率。而Redis 使用了一個隨機(jī)函數(shù)來決定每個節(jié)點的層數(shù)，這個隨機(jī)函數(shù)的期望值是 1/(1-p) ，其中 p 是一個概率常數(shù)，Redis 中默認(rèn)為 0.25。這樣可以保證跳躍表的平均高度為 log (1/p) n ，其中 n 是節(jié)點數(shù)。Redis 還限制了跳躍表的最大層數(shù)為 32 ，這樣可以避免過高的索引層造成空間浪費(fèi)

Stream

概述

stream 是一個類似于日志的數(shù)據(jù)結(jié)構(gòu)，它可以記錄一系列的鍵值對，每個鍵值對都有一個唯一的 ID。一個 stream 類型的鍵最多可以存儲 2^64 - 1 個鍵值對。

stream 類型的底層實現(xiàn)是 rax（基數(shù)樹），它是一種壓縮的前綴樹結(jié)構(gòu)，它將所有的鍵值對按照 ID 的字典序存儲在一個樹形結(jié)構(gòu)中。rax 可以快速地定位、插入、刪除任意位置的鍵值對

應(yīng)用場景

stream 類型的應(yīng)用場景主要是實現(xiàn)事件驅(qū)動的架構(gòu)，比如：

• 消息隊列，利用 xadd 和 xread 命令實現(xiàn)生產(chǎn)者消費(fèi)者模式。
• 操作日志，利用 xadd 和 xrange 命令實現(xiàn)操作記錄和回放。
• 數(shù)據(jù)同步，利用 xadd 和 xreadgroup 命令實現(xiàn)多個消費(fèi)者組之間的數(shù)據(jù)同步。

底層原理

Rax Tree

rax tree是一種基于基數(shù)樹（radix tree）的變體，也叫做壓縮前綴樹（compressed prefix tree）,它被應(yīng)用于redis stream中，用來存儲streamID，其數(shù)據(jù)結(jié)構(gòu)為

typedefstructraxNode{
uint32_tiskey:1;/*Doesthisnodecontainakey?*/
uint32_tisnull:1;/*AssociatedvalueisNULL(don'tstoreit).*/
uint32_tiscompr:1;/*前綴是否壓縮*/
uint32_tsize:29;/*Numberofchildren,orcompressedstringlen.*/
unsignedchardata[];
}raxNode;

• iskey：是否包含key

• isnull：是否存儲value值

• iscompr：前綴是否壓縮。決定了size存儲的是什么和data的數(shù)據(jù)結(jié)構(gòu)

• size
  

  ：

  • iscompr=0：節(jié)點為非壓縮節(jié)點，size是孩子節(jié)點的數(shù)量
  • iscompr=1：節(jié)點為壓縮節(jié)點，size是已壓縮的字符串長度

• data
  

  ：

  • iscompr=0：節(jié)點為非壓縮節(jié)點，數(shù)據(jù)格式為[header strlen=0][abc][a-ptr][b-ptr][c-ptr](value-ptr?)。其有size個字符，
  • iscompr=1：節(jié)點為壓縮節(jié)點，數(shù)據(jù)格式為[header strlen=3][xyz][z-ptr](value-ptr?)。

為了便于理解，設(shè)定一些場景舉例說明

場景一：只插入foot

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

image

其中，z-ptr指向的葉子節(jié)點的iskey=1，標(biāo)識foot這個key。下圖為使用樹狀圖的形式來展現(xiàn)其數(shù)據(jù)結(jié)構(gòu)

場景二：插入foot后，插入footer

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

image

其插入過程為：

1. 與foot節(jié)點中每個字符進(jìn)行比較，獲得最大公共前綴foot
2. 將er作為foot的子節(jié)點，其iskey=1，標(biāo)識foot這個key
3. 將er的子節(jié)點的iskey=1，標(biāo)識footer這個key

下圖為使用樹狀圖的形式來展現(xiàn)其數(shù)據(jù)結(jié)構(gòu)

場景三：插入foot后，插入fo

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

image

其插入過程為：

1. 與foot節(jié)點中每個字符進(jìn)行比較，獲得最大公共前綴fo
2. 將foot拆成fo和ot
3. 將ot作為fo的子節(jié)點，其iskey=1，標(biāo)識fo這個key
4. 設(shè)置ot的子節(jié)點的iskey=1，標(biāo)識foot這個key

下圖為使用樹狀圖的形式來展現(xiàn)其數(shù)據(jù)結(jié)構(gòu)

場景四：插入foot后，插入foobar

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

image

其插入過程為：

1. 與foot節(jié)點中每個字符進(jìn)行比較，獲得最大公共前綴foo
2. 將foot拆成foo和t
3. 將footbar拆成foo、b、ar
4. 將t、b作為foo的子節(jié)點
5. 設(shè)置ot的子節(jié)點的iskey=1，標(biāo)識foot這個key
6. 將ar作為b的子節(jié)點
7. 設(shè)置ar的子節(jié)點的iskey=1，標(biāo)識footbar這個key

下圖為使用樹狀圖的形式來展現(xiàn)其數(shù)據(jù)結(jié)構(gòu)

Stream

stream的底層使用了rax tree和listpack兩種結(jié)構(gòu)，rax tree用來存儲streamID，而listpack用來存儲對應(yīng)的值，結(jié)構(gòu)圖如下：

image

Hyperloglog

概述

HyperLogLog 是一種概率數(shù)據(jù)結(jié)構(gòu)，用于在恒定的內(nèi)存大小下估計集合的基數(shù)（不同元素的個數(shù)）。它不是一個獨立的數(shù)據(jù)類型，而是一種特殊的 string 類型，它可以使用極小的空間來統(tǒng)計一個集合中不同元素的數(shù)量，也就是基數(shù)。一個 hyperloglog 類型的鍵最多可以存儲 12 KB 的數(shù)據(jù)

hyperloglog 類型的底層實現(xiàn)是 SDS（simple dynamic string），它和 string 類型相同，只是在操作時會使用一種概率算法來計算基數(shù)。hyperloglog 的誤差率為 0.81%，也就是說如果真實基數(shù)為 1000，那么 hyperloglog 計算出來的基數(shù)可能在 981 到 1019 之間

應(yīng)用場景

hyperloglog 類型的應(yīng)用場景主要是利用空間換時間和精度，比如：

• 統(tǒng)計網(wǎng)站的獨立訪客數(shù)（UV）
• 統(tǒng)計在線游戲的活躍用戶數(shù)（DAU）
• 統(tǒng)計電商平臺的商品瀏覽量
• 統(tǒng)計社交網(wǎng)絡(luò)的用戶關(guān)注數(shù)
• 統(tǒng)計日志分析中的不同事件數(shù)

假如需要統(tǒng)計某商品的用戶關(guān)注數(shù)，可以通過以下方式：

>PFADDgoodA"1"
1
>PFADDgoodA"2"
1
>PFADDgoodA"3"
1
>PFCOUNTgoodA
3

GEO

概述

geospatial 是一種用于存儲和查詢地理空間位置的數(shù)據(jù)類型，它基于 sorted set 數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，利用 geohash 算法將經(jīng)緯度編碼為二進(jìn)制字符串，并作為 sorted set 的 score 值。Redis geospatial 提供了一系列的命令來添加、刪除、搜索和計算地理空間位置，例如：

• GEOADD key longitude latitude member [longitude latitude member …]：將一個或多個地理空間位置（經(jīng)度、緯度、名稱）添加到指定的 key 中
• GEOPOS key member [member …]：返回一個或多個地理空間位置的經(jīng)緯度
• GEODIST key member1 member2 [unit]：返回兩個地理空間位置之間的距離，可以指定單位（m, km, mi, ft）
• GEORADIUS key longitude latitude radius unit [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count] [ASC|DESC] [STORE key] [STOREDIST key]：返回指定圓心和半徑內(nèi)的地理空間位置，可以指定返回坐標(biāo)、距離、哈希值、數(shù)量、排序方式等，也可以將結(jié)果存儲到另一個 key 中
• GEORADIUSBYMEMBER key member radius unit [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count] [ASC|DESC] [STORE key] [STOREDIST key]: 返回以指定成員為圓心的指定半徑內(nèi)的地理空間位置，其他參數(shù)同 GEORADIUS

應(yīng)用場景

geospatial 的應(yīng)用是地理位置搜索、分析和展示，例如地圖應(yīng)用、導(dǎo)航應(yīng)用、位置服務(wù)應(yīng)用等。例如，可以使用 geospatial 來實現(xiàn)以下功能：

• 統(tǒng)計某個區(qū)域內(nèi)的商家或用戶數(shù)量
• 查詢某個位置附近的餐館或酒店
• 計算兩個位置之間的距離或行駛時間
• 顯示某個位置周圍的景點或活動

Bitmap

概述

bitmap 不是一個獨立的數(shù)據(jù)類型，而是一種特殊的 string 類型，它可以將一個 string 類型的值看作是一個由二進(jìn)制位組成的數(shù)組，并提供了一系列操作二進(jìn)制位的命令。一個 bitmap 類型的鍵最多可以存儲 2^32 - 1 個二進(jìn)制位。

bitmap 類型的底層實現(xiàn)是 SDS（simple dynamic string），它和 string 類型相同，只是在操作時會將每個字節(jié)拆分成 8 個二進(jìn)制位。

應(yīng)用場景

bitmap 類型的應(yīng)用場景主要是利用二進(jìn)制位的特性，比如：

• 統(tǒng)計用戶活躍度，利用 setbit 和 bitcount 命令實現(xiàn)每天或每月用戶登錄次數(shù)的統(tǒng)計。
• 實現(xiàn)布隆過濾器，利用 setbit 和 getbit 命令實現(xiàn)快速判斷一個元素是否存在于一個集合中。
• 實現(xiàn)位圖索引，利用 bitop 和 bitpos 命令實現(xiàn)對多個條件進(jìn)行位運(yùn)算和定位

假如需要統(tǒng)計每個用戶的當(dāng)天登錄次數(shù)統(tǒng)計。

首先，需要規(guī)定bitmap的格式，假設(shè)為{userid}:{年份}:{第幾天} {秒數(shù)} {是否登錄}

將userid為100的用戶，記錄他在2024年第100天中第1秒，是否登錄

SETBIT100010011
0

將userid為100的用戶，記錄他在2024年第100天中第10240 秒，是否登錄

SETBIT1000100102401
0

將userid為100的用戶，記錄他在2024年第100天中第86400 秒，是否登錄

SETBIT1000100864001
0

統(tǒng)計userid為100的用戶，在2024年第100天的登錄次數(shù)

BITCOUNT1000100
3

Bitfield

概述

bitfield結(jié)構(gòu)是基于字符串類型的一種擴(kuò)展，可以讓你對一個字符串中的任意位進(jìn)行設(shè)置，增加和獲取操作，就像一個位數(shù)組一樣

可以操作任意位長度的整數(shù)，從無符號的1位整數(shù)到有符號的63位整數(shù)。這些值是使用二進(jìn)制編碼的Redis字符串來存儲的

bitfield結(jié)構(gòu)支持原子的讀，寫和增加操作，使它們成為管理計數(shù)器和類似數(shù)值的好選擇

使用場景

Bitfield的使用場景與bitmap 類似，主要是一些需要用不同位長度的整數(shù)來表示狀態(tài)或?qū)傩缘膱龊?，例如?/span>

• 用一個32位的無符號整數(shù)來表示用戶的金幣數(shù)量，用一個32位的無符號整數(shù)來表示用戶殺死的怪物數(shù)量，可以方便地對這些數(shù)值進(jìn)行設(shè)置，增加和獲取
• 用一個16位的有符號整數(shù)來表示用戶的等級，用一個16位的有符號整數(shù)來表示用戶的經(jīng)驗值，可以方便地對這些數(shù)值進(jìn)行設(shè)置，增加和獲取
• 用一個8位的無符號整數(shù)來表示用戶的性別，用一個8位的無符號整數(shù)來表示用戶的年齡，可以方便地對這些數(shù)值進(jìn)行設(shè)置，增加和獲取

bitfield和bitmap都是基于string類型的位操作，但是有一些區(qū)別：

• bitmap只能操作1位的無符號整數(shù)，而bitfield可以操作任意位長度的有符號或無符號整數(shù)
• bitmap只能設(shè)置或獲取指定偏移量上的位，而bitfield可以對指定偏移量上的位進(jìn)行增加或減少操作
• bitmap可以對多個字符串進(jìn)行位運(yùn)算，而bitfield只能對單個字符串進(jìn)行位操作
• bitmap的偏移量是從0開始的，而bitfield的偏移量是從最高有效位開始的

例如，使用bitfield存儲用戶的個人信息，

• 用一個8位的無符號整數(shù)來表示用戶的性別，0表示男，1表示女
• 用一個8位的無符號整數(shù)來表示用戶的年齡，范圍是0-255
• 用一個16位的無符號整數(shù)來表示用戶的身高，單位是厘米，范圍是0-65535
• 用一個16位的無符號整數(shù)來表示用戶的體重，單位是克，范圍是0-65535

假設(shè)有一個用戶，性別是女，年齡是25，身高是165厘米，體重是50千克，可以用以下命令來存儲和獲取這些信息：

>BITFIELDuserinfoSETu8#01SETu8#125SETu16#2165SETu16#350000
0
0
0
0

然后，獲取這個用戶的信息，性別、年齡、身高、體重

>BITFIELDuserinfoGETu8#0GETu8#1GETu16#2GETu16#3
1
25
165
50000