概述

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

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

String

概述

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

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

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

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

應(yīng)用場(chǎng)景

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

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

底層原理

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

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

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

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

image

embstr和raw的轉(zhuǎn)換

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

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

127.0.0.1:6379>objectencodingstr
"embstr"
#str賦值44個(gè)字節(jié)的字符串
127.0.0.1:6379>setstr1234567890123456789012345678901234567890abcd
OK
127.0.0.1:6379>objectencodingstr
"embstr"
#str2賦值45個(gè)字節(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 是一個(gè)鍵值對(duì)集合，它可以存儲(chǔ)多個(gè)字段和值，類似于編程語(yǔ)言中的 map 對(duì)象。一個(gè) hash 類型的鍵最多可以存儲(chǔ) 2^32 - 1 個(gè)字段。

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

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

應(yīng)用場(chǎng)景

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

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

底層原理

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

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

從ziplist/listpack編碼轉(zhuǎn)換為hashTable編碼是通過(guò)判斷元素?cái)?shù)量或單個(gè)元素Key或Value的長(zhǎng)度決定的：

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

ziplist與listpack

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

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

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

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

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

image

zipList的連鎖更新問(wèn)題

ziplist的每個(gè)entry都包含previous_entry_length來(lái)記錄上一個(gè)節(jié)點(diǎn)的大小，長(zhǎng)度是1個(gè)或5個(gè)byte：

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

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

image

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

listpack是如何解決的

image

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

hashTable

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

image

Redis中hashTable源碼

structdict{
dictType*type;
dictEntry**ht_table[2];
unsignedlonght_used[2];
longrehashidx;/*當(dāng)進(jìn)行rehash時(shí)，rehashidx為-1*/
int16_tpauserehash;/*如果rehash暫停，pauserehash則大于0，（小于0表示代碼錯(cuò)誤）*/
signedcharht_size_exp[2];/*哈希桶的個(gè)數(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個(gè)數(shù)太大、key太長(zhǎng)、value太長(zhǎng)三者有其一的時(shí)候會(huì)有以下問(wèn)題：

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

hashTable變得越來(lái)越長(zhǎng)怎么辦

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

rehash 步驟

image

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

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

   ht[0].used
   

   ）：

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

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

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

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

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

漸進(jìn)式 rehash

Redis中的這種重新哈希的操作因?yàn)椴皇且淮涡匀?/span>rehash，而是分多次來(lái)慢慢的將ht[0]中的鍵值對(duì)rehash到ht[1]，故而這種操作也稱之為漸進(jìn)式rehash。漸進(jìn)式rehash可以避免集中式rehash帶來(lái)的龐大計(jì)算量，是一種分而治之的思想。

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

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

List

概述

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

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

應(yīng)用場(chǎng)景

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

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

底層原理

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

• 在Redis3.2之前，list使用的是linkedlist和ziplist
• 在Redis3.2~Redis7.0之間，list使用的是quickList，是linkedlist和ziplist的結(jié)合
• 在Redis7.0之后，list使用的也是quickList，只不過(guò)將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存儲(chǔ)了一個(gè)雙向列表，每個(gè)列表的節(jié)點(diǎn)是一個(gè)ziplist，所以實(shí)際上quicklist并不是一個(gè)新的數(shù)據(jù)結(jié)構(gòu)，它就是linkedlist和ziplist的結(jié)合，然后被命名為快速列表。ziplist內(nèi)部entry個(gè)數(shù)可在redis.conf配置

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

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

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

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

和Hash結(jié)構(gòu)一樣，因?yàn)?/span>ziplist有連鎖更新問(wèn)題，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;/*單個(gè)節(jié)點(diǎn)的填充因子*/
unsignedintcompress:QL_COMP_BITS;/*不壓縮的端節(jié)點(diǎn)深度；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元素個(gè)數(shù)，最大65535*/
unsignedintencoding:2;/*RAW==1orLZF==2*/
unsignedintcontainer:2;/*PLAIN==1orPACKED==2*/
unsignedintrecompress:1;/*當(dāng)前l(fā)istpack是否需要再次壓縮*/
unsignedintattempted_compress:1;/*測(cè)試用*/
unsignedintextra:10;/*備用*/
}quicklistNode;

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

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

Set

概述

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

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

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

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

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

應(yīng)用場(chǎng)景

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

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

底層原理

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

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

intset

intset是一種緊湊的數(shù)組結(jié)構(gòu)，它只保存int類型的數(shù)據(jù)，它將所有的元素按照從小到大的順序存儲(chǔ)在一塊連續(xù)的內(nèi)存中。intset會(huì)根據(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)一個(gè)集合滿足以下兩個(gè)條件時(shí)，Redis 會(huì)選擇使用intset編碼：

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

intset最大元素?cái)?shù)量可在redis.conf配置

set-max-intset-entries 512

為什么加入了listpack

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

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

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

hashtable 的空間開銷高

hashtable 的空間開銷高是因?yàn)樗枰A(yù)先分配一個(gè)固定大小的數(shù)組來(lái)存儲(chǔ)鍵值對(duì)，而這個(gè)數(shù)組的大小通常要大于實(shí)際存儲(chǔ)的元素個(gè)數(shù)，以保證較低的裝載因子。裝載因子是指 hashtable 中已經(jīng)存儲(chǔ)的元素個(gè)數(shù)和數(shù)組大小的比值，它反映了 hashtable 的空間利用率

• 如果裝載因子過(guò)高，那么 hashtable 的性能會(huì)下降，因?yàn)榕鲎驳母怕蕰?huì)增加
• 如果裝載因子過(guò)低，那么 hashtable 的空間利用率會(huì)下降，因?yàn)閿?shù)組中會(huì)有很多空閑的位置

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

hashtable 的碰撞概率高

hashtable 的碰撞概率高是因?yàn)樗褂昧艘粋€(gè)散列函數(shù)來(lái)將任意長(zhǎng)度的鍵映射到一個(gè)有限范圍內(nèi)的整數(shù)，作為數(shù)組的索引

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

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

image

這就是一個(gè)碰撞的例子，因?yàn)樗膫€(gè)鍵都映射到了同一個(gè)索引。這種情況可能是由于以下原因造成的：

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

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

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

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

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

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

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

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

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

ZSet

概述

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

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)用場(chǎng)景

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

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

底層原理

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

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

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

具體來(lái)說(shuō)，當(dāng) zset 同時(shí)滿足以下兩個(gè)條件時(shí)，會(huì)使用 listpack作為底層結(jié)構(gòu)：

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

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

skiplist

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

image

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

優(yōu)點(diǎn)：

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

缺點(diǎn)：

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

redis的skiplist

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

Stream

概述

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

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

應(yīng)用場(chǎng)景

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

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

底層原理

Rax Tree

rax tree是一種基于基數(shù)樹（radix tree）的變體，也叫做壓縮前綴樹（compressed prefix tree）,它被應(yīng)用于redis stream中，用來(lái)存儲(chǔ)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：是否存儲(chǔ)value值

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

• size
  

  ：

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

• data
  

  ：

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

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

場(chǎng)景一：只插入foot

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

image

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

場(chǎng)景二：插入foot后，插入footer

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

image

其插入過(guò)程為：

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

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

場(chǎng)景三：插入foot后，插入fo

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

image

其插入過(guò)程為：

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

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

場(chǎng)景四：插入foot后，插入foobar

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

image

其插入過(guò)程為：

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

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

Stream

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

image

Hyperloglog

概述

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

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

應(yīng)用場(chǎng)景

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

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

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

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

GEO

概述

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

• GEOADD key longitude latitude member [longitude latitude member …]：將一個(gè)或多個(gè)地理空間位置（經(jīng)度、緯度、名稱）添加到指定的 key 中
• GEOPOS key member [member …]：返回一個(gè)或多個(gè)地理空間位置的經(jīng)緯度
• GEODIST key member1 member2 [unit]：返回兩個(gè)地理空間位置之間的距離，可以指定單位（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é)果存儲(chǔ)到另一個(gè) key 中
• GEORADIUSBYMEMBER key member radius unit [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count] [ASC|DESC] [STORE key] [STOREDIST key]: 返回以指定成員為圓心的指定半徑內(nèi)的地理空間位置，其他參數(shù)同 GEORADIUS

應(yīng)用場(chǎng)景

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

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

Bitmap

概述

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

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

應(yīng)用場(chǎng)景

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

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

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

首先，需要規(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)計(jì)userid為100的用戶，在2024年第100天的登錄次數(shù)

BITCOUNT1000100
3

Bitfield

概述

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

可以操作任意位長(zhǎng)度的整數(shù)，從無(wú)符號(hào)的1位整數(shù)到有符號(hào)的63位整數(shù)。這些值是使用二進(jìn)制編碼的Redis字符串來(lái)存儲(chǔ)的

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

使用場(chǎng)景

Bitfield的使用場(chǎng)景與bitmap 類似，主要是一些需要用不同位長(zhǎng)度的整數(shù)來(lái)表示狀態(tài)或?qū)傩缘膱?chǎng)合，例如：

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

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

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

例如，使用bitfield存儲(chǔ)用戶的個(gè)人信息，

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

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

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

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

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