天天看點

redis十種資料類型及底層原理

作者:LinkSLA智能運維管家

概述

Redis 是一個開源的高性能鍵值資料庫,它支援多種資料類型,可以滿足不同的業務需求。本文将介紹 Redis 的10種資料類型,分别是

  • string(字元串)
  • hash(哈希)
  • list(清單)
  • set(集合)
  • zset(有序集合)
  • stream(流)
  • geospatial(地理)
  • bitmap(位圖)
  • bitfield(位域)
  • hyperloglog(基數統計)

String

概述

string 是 Redis 最基本的資料類型,它可以存儲任意類型的資料,比如文本、數字、圖檔或者序列化的對象。一個 string 類型的鍵最大可以存儲 512 MB 的資料。

string 類型的底層實作是 SDS(simple dynamic string),它是一個動态字元串結構,由長度、空閑空間和位元組數組三部分組成。SDS有3種編碼類型:

  • embstr:占用64Bytes的空間,存儲44Bytes的資料
  • raw:存儲大于44Bytes的資料
  • int:存儲整數類型

embstr和raw存儲字元串資料,int存儲整型資料

應用場景

string 類型的應用場景非常廣泛,比如:

  • 緩存資料,提高通路速度和降低資料庫壓力。
  • 計數器,利用 incr 和 decr 指令實作原子性的加減操作。
  • 分布式鎖,利用 setnx 指令實作互斥通路。
  • 限流,利用 expire 指令實作時間視窗内的通路控制。

底層原理

embstr結構

embstr 結構存儲小于等于44個位元組的字元串,embstr 每次開辟64個byte的空間

  • 前19個byte用于存儲embstr 結構
  • 中間的44個byte存儲資料
  • 最後為\0符号

raw結構

redis十種資料類型及底層原理

embstr和raw的轉換

在存儲字元串的時候,redis會根據資料的長度判斷使用哪種結構

  • 如果長度小于等于44個位元組,就會選擇embstr 結構
  • 如果長度大于44個byte,就會選擇raw結構
127.0.0.1:6379> object encoding str
"embstr"
# str指派44個位元組的字元串
127.0.0.1:6379> set str 1234567890123456789012345678901234567890abcd
OK
127.0.0.1:6379> object encoding str
"embstr"
# str2指派45個位元組的字元串
127.0.0.1:6379> set str2 1234567890123456789012345678901234567890abcde
OK
127.0.0.1:6379> object encoding str2
"raw"
127.0.0.1:6379> set num 123
OK
127.0.0.1:6379> object encoding num
"int"
           

Hash

概述

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

Hash類型的底層實作有三種:

  • ziplist:壓縮清單,當hash達到一定的門檻值時,會自動轉換為hashtable結構
  • listpack:緊湊清單,在Redis7.0之後,listpack正式取代ziplist。同樣的,當hash達到一定的門檻值時,會自動轉換為hashtable結構
  • hashtable:哈希表,類似map

應用場景

hash 類型的應用場景主要是存儲對象,比如:

  • 使用者資訊,利用 hset 和 hget 指令實作對象屬性的增删改查。
  • 購物車,利用 hincrby 指令實作商品數量的增減。
  • 配置資訊,利用 hmset 和 hmget 指令實作批量設定和擷取配置項。

底層原理

Redis在存儲hash結構的資料,為了達到記憶體和性能的平衡,也針對少量存儲和大量存儲分别設計了兩種結構,分别為:

  • ziplist(redis7.0之前使用)和listpack(redis7.0之後使用)
  • hashTable

從ziplist/listpack編碼轉換為hashTable編碼是通過判斷元素數量或單個元素Key或Value的長度決定的:

  • hash-max-ziplist-entries:表示當hash中的元素數量小于或等于該值時,使用ziplist編碼,否則使用hashtable編碼。ziplist是一種壓縮清單,它可以節省記憶體空間,但是通路速度較慢。hashtable是一種哈希表,它可以提高通路速度,但是占用記憶體空間較多。預設值為512。
  • hash-max-ziplist-value:表示當 hash中的每個元素的 key 和 value 的長度都小于或等于該值時,使用 ziplist編碼,否則使用 hashtable編碼。預設值為 64。

ziplist與listpack

ziplist/listpack都是hash結構用來存儲少量資料的結構。從Redis7.0後,hash預設使用ziplist結構。因為 ziplist有一個緻命的缺陷,就是連鎖更新,當一個節點的長度發生變化時,可能會導緻後續所有節點的長度字段都要重新編碼,這會造成極差的性能

ziplist結構

ziplist是一種緊湊的連結清單結構,它将所有的字段和值順序地存儲在一塊連續的記憶體中。

redis十種資料類型及底層原理

Redis中ziplist源碼

typedef struct {
  /* 當使用字元串時,slen表示為字元串長度 */
  unsigned char *sval;
  unsigned int slen;
  /* 當使用整形時,sval為NULL,lval為ziplistEntry的value */
  long long lval;
} ziplistEntry;
           

listpack結構

redis十種資料類型及底層原理

zipList的連鎖更新問題

ziplist的每個entry都包含previous_entry_length來記錄上一個節點的大小,長度是1個或5個byte:

  • 如果前一節點的長度小于254個byte,則采用1個byte來儲存這個長度值
  • 如果前一節點的長度大于等于254個byte,則采用5個byte來儲存這個長度值,第一個byte為0xfe,後四個byte才是真實長度資料

假設,現有有N個連續、長度為250~253個byte的entry,是以entry的previous_entry_length屬性占用1個btye

redis十種資料類型及底層原理

當第一節長度大于等于254個bytes,導緻第二節previous_entry_length變為5個bytes,第二節的長度由250變為254。而第二節長度的增加必然會影響第三節的previous_entry_length。ziplist這種特殊套娃的情況下産生的連續多次空間擴充操作成為連鎖更新。新增、删除都可能導緻連鎖更新的産生。

listpack是如何解決的

redis十種資料類型及底層原理
  1. 由于ziplist需要倒着周遊,是以需要用previous_entry_length記錄前一個entry的長度。而listpack可以通過total_bytes和end計算出來。是以previous_entry_length不需要了。
  2. listpack 的設計徹底消滅了 ziplist 存在的級聯更新行為,元素與元素之間完全獨立,不會因為一個元素的長度變長就導緻後續的元素内容會受到影響。
  3. 與ziplist做對比的話,犧牲了記憶體使用率,避免了連鎖更新的情況。從代碼複雜度上看,listpack相對ziplist簡單很多,再把增删改統一做處理,從listpack的代碼實作上看,極簡且高效。

hashTable

hashTable是一種散清單結構,它将字段和值分别存儲在兩個數組中,并通過哈希函數計算字段在數組中的索引

redis十種資料類型及底層原理

Redis中hashTable源碼

struct dict {
    dictType *type;
    dictEntry **ht_table[2];
    unsigned long ht_used[2];
    long rehashidx; /* 當進行rehash時,rehashidx為-1 */
    int16_t pauserehash; /* 如果rehash暫停,pauserehash則大于0,(小于0表示代碼錯誤)*/
    signed char ht_size_exp[2]; /* 哈希桶的個數(size = 1<<exp) */
};

typedef struct dict {
    dictEntry **table;
    dictType *type;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
    void *privdata;
} dict;

typedef struct dictEntry {
    void *key;
    void *val;
    struct dictEntry *next;
} dictEntry;
           

ziplist和hashTable的轉換

redis十種資料類型及底層原理
127.0.0.1:6379> hset h1 id 123456789012345678901234567890123456789012345678901234567890abcd
(integer) 1
127.0.0.1:6379> object encoding h1
"ziplist"
127.0.0.1:6379> hset h2 id 123456789012345678901234567890123456789012345678901234567890abcde
(integer) 1
127.0.0.1:6379> object encoding h2
"hashtable"

           

ziplist的廢棄

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

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

hashTable變得越來越長怎麼辦

擴容,hashTabel是怎麼擴容的?使用的是漸進式擴容rehash。rehash會重新計算哈希值,且将哈希桶的容量擴大。

rehash 步驟

redis十種資料類型及底層原理

擴充哈希和收縮哈希都是通過執行rehash來完成,這其中就涉及到了空間的配置設定和釋放,主要經過以下五步:

  1. 為字典dict的ht[1]哈希表配置設定空間,其大小取決于目前哈希表已儲存節點數(即:ht[0].used):
  2. 如果是擴充操作則ht[1]的大小為2的n次方中第一個大于等于ht[0].used * 2屬性的值(比如used=3,此時ht[0].used * 2=6,故2的3次方為8就是第一個大于used * 2的值(2 的 2 次方 6))。
  3. 如果是收縮操作則ht[1]大小為 2 的 n 次方中第一個大于等于ht[0].used的值
  4. 将字典中的屬性rehashidx的值設定為0,表示正在執行rehash操作
  5. 将ht[0]中所有的鍵值對依次重新計算哈希值,并放到ht[1]數組對應位置,每完成一個鍵值對的rehash之後rehashidx的值需要自增1
  6. 當ht[0]中所有的鍵值對都遷移到ht[1]之後,釋放ht[0],并将ht[1]修改為ht[0],然後再建立一個新的ht[1]數組,為下一次rehash做準備
  7. 将字典中的屬性rehashidx設定為-1,表示此次rehash操作結束,等待下一次rehash

漸進式 rehash

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

在漸進式rehash過程中,因為還可能會有新的鍵值對存進來,此時Redis的做法是新添加的鍵值對統一放入ht[1]中,這樣就確定了ht[0]鍵值對的數量隻會減少。

當正在執行rehash操作時,如果伺服器收到來自用戶端的指令請求操作,則會先查詢ht[0],查找不到結果再到ht[1]中查詢

List

概述

list 是一個有序的字元串清單,它按照插入順序排序,并且支援在兩端插入或删除元素。一個 list 類型的鍵最多可以存儲 2^32 - 1 個元素。

redis3.2以後,list 類型的底層實作隻有一種結構,就是quicklist。版本不同時,底層實作是不同的,下面會講解。

應用場景

list 類型的應用場景主要是實作隊列和棧,比如:

  • 消息隊列,利用 lpush 和 rpop 指令實作生産者消費者模式。
  • 最新消息,利用 lpush 和 ltrim 指令實作固定長度的時間線。
  • 曆史記錄,利用 lpush 和 lrange 指令實作浏覽記錄或者搜尋記錄。

底層原理

在講解list結構之前,需要先說明一下list結構編碼的更替,如下

  • 在Redis3.2之前,list使用的是linkedlist和ziplist
  • 在Redis3.2~Redis7.0之間,list使用的是quickList,是linkedlist和ziplist的結合
  • 在Redis7.0之後,list使用的也是quickList,隻不過将ziplist轉為listpack,它是listpack、linkedlist結合版

linkedlist與ziplist

在Redis3.2之前,linkedlist和ziplist兩種編碼可以選擇切換,它們之間的轉換關系如圖

redis十種資料類型及底層原理

同樣地,ziplist轉為linkedlist的條件可在redis.conf配置

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

quickList(ziplist、linkedlist結合版)

quicklist存儲了一個雙向清單,每個清單的節點是一個ziplist,是以實際上quicklist并不是一個新的資料結構,它就是linkedlist和ziplist的結合,然後被命名為快速清單。

redis十種資料類型及底層原理

ziplist内部entry個數可在redis.conf配置

list-max-ziplist-size -2
# -5: 每個ziplist最多為 64 kb  <-- 影響正常負載,不推薦
# -4: 每個ziplist最多為 32 Kb  <-- 不推薦
# -3: 每個ziplist最多為 16 Kb  <-- 最好不要使用
# -2: 每個ziplist最多為 8 Kb   <-- 好
# -1: 每個ziplist最多為 4 Kb   <-- 好
# 正數為ziplist内部entry個數

           

ziplist通過特定的LZF壓縮算法來将節點進行壓縮存儲,進而更進一步的節省空間,而很多場景都是兩端元素通路率最高,我們可以通過配置list-compress-depth來排除首尾兩端不壓縮的entry個數。

list-compress-depth 0
# - 0:不壓縮(預設值)
# - 1:首尾第 1 個元素不壓縮
# - 2:首位前 2 個元素不壓縮
# - 3:首尾前 3 個元素不壓縮
# - 以此類推
           

quickList(listpack、linkedlist結合版)

和Hash結構一樣,因為ziplist有連鎖更新問題,redis7.0将ziplist替換為listpack,下面是新quickList的結構圖

redis十種資料類型及底層原理

Redis中listpack源碼

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* 所有清單包中所有條目的總數,占用16 bits,最大65536 */
    unsigned long len;          /* quicklistNode 的數量 */
    signed int fill : QL_FILL_BITS;       /* 單個節點的填充因子 */
    unsigned int compress : QL_COMP_BITS; /* 不壓縮的端節點深度;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;
           
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *entry;
    size_t sz;             /* 目前entry占用位元組 */
    unsigned int count : 16;     /* listpack元素個數,最大65535 */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* PLAIN==1 or PACKED==2 */
    unsigned int recompress : 1; /* 目前listpack是否需要再次壓縮 */
    unsigned int attempted_compress : 1; /* 測試用 */
    unsigned int extra : 10; /* 備用 */
} quicklistNode;
           

listpack内部entry個數可在redis.conf配置

List-Max-listpack-size -2
# -5: 每個listpack最多為 64 kb  <-- 影響正常負載,不推薦
# -4: 每個listpack最多為 32 Kb  <-- 不推薦
# -3: 每個listpack最多為 16 Kb  <-- 最好不要使用
# -2: 每個listpack最多為 8 Kb   <-- 好
# -1: 每個listpack最多為 4 Kb   <-- 好
# 正數為listpack内部entry個數
           

Set

概述

set 是一個無序的字元串集合,它不允許重複的元素。一個 set 類型的鍵最多可以存儲 2^32 - 1 個元素。

set 類型的底層實作有兩種:

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

Redis 會根據 set 中元素的數量和類型來選擇合适的編碼方式,當 set 達到一定的門檻值時,會自動轉換編碼方式。

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

           

應用場景

set 類型的應用場景主要是利用集合的特性,比如:

  • 去重,利用 sadd 和 scard 指令實作元素的添加和計數。
  • 交集,并集,差集,利用 sinter,sunion 和 sdiff 指令實作集合間的運算。
  • 随機抽取,利用 srandmember 指令實作随機抽獎或者抽樣。

底層原理

在講解set結構之前,需要先說明一下set結構編碼的更替,如下

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

intset

intset是一種緊湊的數組結構,它隻儲存int類型的資料,它将所有的元素按照從小到大的順序存儲在一塊連續的記憶體中。intset會根據傳入的資料大小,encoding分為int16_t、int32_t、int64_t

redis十種資料類型及底層原理
127.0.0.1:6379> sadd set 123
(integer) 1
127.0.0.1:6379> object encoding set
"intset"
127.0.0.1:6379> sadd set abcd
(integer) 1
127.0.0.1:6379> object encoding set
"hashtable"
           

intset 和 hashtable 的轉換

在Redis7.2之前,當一個集合滿足以下兩個條件時,Redis 會選擇使用intset編碼:

  • 集合對象儲存的所有元素都是整數值
  • 集合對象儲存的元素數量小于等于512個(預設)

intset最大元素數量可在redis.conf配置

set-max-intset-entries 512
           

為什麼加入了listpack

在redis7.2之前,sds類型的資料會直接放入到編碼結構式為hashtable的set中。其中,sds其實就是redis中的string類型。

而在redis7.2之後,sds類型的資料,首先會使用listpack結構當 set 達到一定的門檻值時,才會自動轉換為hashtable。

添加listpack結構是為了提高記憶體使用率和操作效率,因為 hashtable 的空間開銷和碰撞機率都比較高。

hashtable 的空間開銷高

hashtable 的空間開銷高是因為它需要預先配置設定一個固定大小的數組來存儲鍵值對,而這個數組的大小通常要大于實際存儲的元素個數,以保證較低的裝載因子。裝載因子是指 hashtable 中已經存儲的元素個數和數組大小的比值,它反映了 hashtable 的空間使用率

  • 如果裝載因子過高,那麼 hashtable 的性能會下降,因為碰撞的機率會增加
  • 如果裝載因子過低,那麼 hashtable 的空間使用率會下降,因為數組中會有很多空閑的位置

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

hashtable 的碰撞機率高

hashtable 的碰撞機率高是因為它使用了一個散列函數來将任意長度的鍵映射到一個有限範圍内的整數,作為數組的索引

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

舉例說明,假設有一個大小為8的hashtable,使用取模運算作為散列函數,即h(k) = k mod 8。現在有四個鍵:5,13,21,29,它們都被散列到索引1處

redis十種資料類型及底層原理

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

  • 散列函數的選擇不合适,沒有充分利用hashtable的空間。
  • 鍵的分布不均勻,有些區間的鍵出現的頻率更高。
  • hashtable的大小太小,不能容納所有的鍵。

為了解決碰撞,redis采用了鍊位址法。就是在每個索引處維護一個連結清單,存儲所有散列到該索引的鍵。但是,如果連結清單過長,查找效率會降低。是以,一般建議保持hashtable的負載因子(即鍵的數量除以hashtable的大小)在一定範圍内,比如0.5到0.75之間。如果負載因子過高或過低,可以通過擴容或縮容來調整hashtable的大小

intset 、listpack和hashtable的轉換

intset 、listpack和hashtable這三者的轉換時根據要添加的資料、目前set的編碼和門檻值決定的。

  • 如果要添加的資料是整型,且目前set的編碼為intset,如果超過門檻值由intset直接轉為hashtable
  • 門檻值條件為:

    set-max-intset-entries ,intset最大元素個數,預設512

  • 如果要添加的資料是字元串,分為三種情況
  • 門檻值條件為:

    set-max-listpack-entries:最大元素個數,預設128

    set_max_listpack_value:最大元素大小,預設64

    以上兩個條件需要同時滿足才能進行編碼轉換

    • 目前set的編碼為intset:如果沒有超過門檻值,轉換為listpack;否則,直接轉換為hashtable
    • 目前set的編碼為listpack:如果超過門檻值,就轉換為hashtable
    • 目前set的編碼為hashtable:直接插入,編碼不會進行轉換

ZSet

概述

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

Redis中zset源碼

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;
           

應用場景

zset 類型的應用場景主要是利用分數和排序的特性,比如:

  • 排行榜,利用 zadd 和 zrange 指令實作分數的更新和排名的查詢
  • 延時隊列,利用 zadd 和 zpopmin 指令實作任務的添加和執行,并且可以定期地擷取已經到期的任務
  • 通路統計,可以使用 zset 來存儲網站或者文章的通路次數,并且可以按照通路量進行排序和篩選。

底層原理

Redis在存儲zset結構的資料,為了達到記憶體和性能的平衡,針對少量存儲和大量存儲分别設計了兩種結構,分别為:

  • ziplist(redis7.0之前使用)和listpack(redis7.0之後使用)
  • skiplist

當 zset 中的元素個數和元素值的長度比較小的時候,Redis 使用ziplist/listpack來節省記憶體空間。當 zset 中的元素個數和元素值的長度達到一定門檻值時,Redis 會自動将ziplist/listpack轉換為skiplist,以提高操作效率

具體來說,當 zset 同時滿足以下兩個條件時,會使用 listpack作為底層結構:

  • 元素個數小于 zset_max_listpack_entries ,預設值為 128
  • 元素值的長度小于zset_max_listpack_value,預設值為 64

當 zset 中不滿足以上兩個條件時,會使用 skiplist 作為底層結構。

skiplist

跳躍表是一種随機化的資料結構,實質就是一種可以進行二分查找的有序連結清單。跳躍表在原有的有序連結清單上面增加了多級索引,通過索引來實作快速查找。跳躍表不僅能提高搜尋性能,同時也可以提高插入和删除操作的性能

redis十種資料類型及底層原理

跳躍表相比于其他平衡樹結構,有以下幾個優點和缺點:

優點:

  • 實作簡單,易于了解和調試
  • 插入和删除操作隻需要修改局部節點的指針,不需要像平衡樹那樣進行全局調整
  • 可以利用空間換時間,通過增加索引層來提高查找效率
  • 支援快速的範圍查詢,可以友善地傳回指定區間内的所有元素

缺點:

  • 空間複雜度較高,需要額外存儲多級索引
  • 随機性太強,性能不穩定,最壞情況下可能退化成連結清單
  • 不支援快速的倒序周遊,需要額外的指針來實作

redis的skiplist

skiplist有一個層數上的問題,當層數過多,會影響查詢效率。而Redis 使用了一個随機函數來決定每個節點的層數,這個随機函數的期望值是 1/(1-p) ,其中 p 是一個機率常數,Redis 中預設為 0.25。這樣可以保證跳躍表的平均高度為 log (1/p) n ,其中 n 是節點數。Redis 還限制了跳躍表的最大層數為 32 ,這樣可以避免過高的索引層造成空間浪費

Stream

概述

stream 是一個類似于日志的資料結構,它可以記錄一系列的鍵值對,每個鍵值對都有一個唯一的 ID。一個 stream 類型的鍵最多可以存儲 2^64 - 1 個鍵值對。

stream 類型的底層實作是 rax(基數樹),它是一種壓縮的字首樹結構,它将所有的鍵值對按照 ID 的字典序存儲在一個樹形結構中。rax 可以快速地定位、插入、删除任意位置的鍵值對

應用場景

stream 類型的應用場景主要是實作事件驅動的架構,比如:

  • 消息隊列,利用 xadd 和 xread 指令實作生産者消費者模式。
  • 記錄檔,利用 xadd 和 xrange 指令實作操作記錄和回放。
  • 資料同步,利用 xadd 和 xreadgroup 指令實作多個消費者組之間的資料同步。

底層原理

Rax Tree

rax tree是一種基于基數樹(radix tree)的變體,也叫做壓縮字首樹(compressed prefix tree),它被應用于redis stream中,用來存儲streamID,其資料結構為

typedef struct raxNode {
    uint32_t iskey:1;     /* Does this node contain a key? */
    uint32_t isnull:1;    /* Associated value is NULL (don't store it). */
    uint32_t iscompr:1;   /* 字首是否壓縮 */
    uint32_t size:29;     /* Number of children, or compressed string len. */
    unsigned char data[];
} raxNode;
           
  • iskey:是否包含key
  • isnull:是否存儲value值
  • iscompr:字首是否壓縮。決定了size存儲的是什麼和data的資料結構
  • size:
    • iscompr=0:節點為非壓縮節點,size是孩子節點的數量
    • iscompr=1:節點為壓縮節點,size是已壓縮的字元串長度
  • data:
    • iscompr=0:節點為非壓縮節點,資料格式為[header strlen=0][abc][a-ptr][b-ptr][c-ptr](value-ptr?)。其有size個字元,
    • iscompr=1:節點為壓縮節點,資料格式為[header strlen=3][xyz][z-ptr](value-ptr?)。

為了便于了解,設定一些場景舉例說明

場景一:隻插入foot

資料結構為:

redis十種資料類型及底層原理

其中,z-ptr指向的葉子節點的iskey=1,辨別foot這個key。下圖為使用樹狀圖的形式來展現其資料結構

redis十種資料類型及底層原理

場景二:插入foot後,插入footer

資料結構為:

redis十種資料類型及底層原理

其插入過程為:

  1. 與foot節點中每個字元進行比較,獲得最大公共字首foot
  2. 将er作為foot的子節點,其iskey=1,辨別foot這個key
  3. 将er的子節點的iskey=1,辨別footer這個key

下圖為使用樹狀圖的形式來展現其資料結構

redis十種資料類型及底層原理

場景三:插入foot後,插入fo

資料結構為:

redis十種資料類型及底層原理

其插入過程為:

  1. 與foot節點中每個字元進行比較,獲得最大公共字首fo
  2. 将foot拆成fo和ot
  3. 将ot作為fo的子節點,其iskey=1,辨別fo這個key
  4. 設定ot的子節點的iskey=1,辨別foot這個key

下圖為使用樹狀圖的形式來展現其資料結構

redis十種資料類型及底層原理

場景四:插入foot後,插入foobar

資料結構為:

redis十種資料類型及底層原理

其插入過程為:

  1. 與foot節點中每個字元進行比較,獲得最大公共字首foo
  2. 将foot拆成foo和t
  3. 将footbar拆成foo、b、ar
  4. 将t、b作為foo的子節點
  5. 設定ot的子節點的iskey=1,辨別foot這個key
  6. 将ar作為b的子節點
  7. 設定ar的子節點的iskey=1,辨別footbar這個key

下圖為使用樹狀圖的形式來展現其資料結構

redis十種資料類型及底層原理

Stream

stream的底層使用了rax tree和listpack兩種結構,rax tree用來存儲streamID,而listpack用來存儲對應的值,結構圖如下:

redis十種資料類型及底層原理

Hyperloglog

概述

HyperLogLog 是一種機率資料結構,用于在恒定的記憶體大小下估計集合的基數(不同元素的個數)。它不是一個獨立的資料類型,而是一種特殊的 string 類型,它可以使用極小的空間來統計一個集合中不同元素的數量,也就是基數。一個 hyperloglog 類型的鍵最多可以存儲 12 KB 的資料

hyperloglog 類型的底層實作是 SDS(simple dynamic string),它和 string 類型相同,隻是在操作時會使用一種機率算法來計算基數。hyperloglog 的誤差率為 0.81%,也就是說如果真實基數為 1000,那麼 hyperloglog 計算出來的基數可能在 981 到 1019 之間

應用場景

hyperloglog 類型的應用場景主要是利用空間換時間和精度,比如:

  • 統計網站的獨立訪客數(UV)
  • 統計線上遊戲的活躍使用者數(DAU)
  • 統計電商平台的商品浏覽量
  • 統計社交網絡的使用者關注數
  • 統計日志分析中的不同僚件數

假如需要統計某商品的使用者關注數,可以通過以下方式:

> PFADD goodA "1"
1
> PFADD goodA "2"
1
> PFADD goodA "3"
1
> PFCOUNT goodA
3

           

GEO

概述

geospatial 是一種用于存儲和查詢地理空間位置的資料類型,它基于 sorted set 資料結構實作,利用 geohash 算法将經緯度編碼為二進制字元串,并作為 sorted set 的 score 值。Redis geospatial 提供了一系列的指令來添加、删除、搜尋和計算地理空間位置,例如:

  • GEOADD key longitude latitude member [longitude latitude member …]:将一個或多個地理空間位置(經度、緯度、名稱)添加到指定的 key 中
  • GEOPOS key member [member …]:傳回一個或多個地理空間位置的經緯度
  • 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]:傳回指定圓心和半徑内的地理空間位置,可以指定傳回坐标、距離、哈希值、數量、排序方式等,也可以将結果存儲到另一個 key 中
  • GEORADIUSBYMEMBER key member radius unit [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count] [ASC|DESC] [STORE key] [STOREDIST key]: 傳回以指定成員為圓心的指定半徑内的地理空間位置,其他參數同 GEORADIUS

應用場景

geospatial 的應用是地理位置搜尋、分析和展示,例如地圖應用、導航應用、位置服務應用等。例如,可以使用 geospatial 來實作以下功能:

  • 統計某個區域内的商家或使用者數量
  • 查詢某個位置附近的餐館或酒店
  • 計算兩個位置之間的距離或行駛時間
  • 顯示某個位置周圍的景點或活動

Bitmap

概述

bitmap 不是一個獨立的資料類型,而是一種特殊的 string 類型,它可以将一個 string 類型的值看作是一個由二進制位組成的數組,并提供了一系列操作二進制位的指令。一個 bitmap 類型的鍵最多可以存儲 2^32 - 1 個二進制位。

bitmap 類型的底層實作是 SDS(simple dynamic string),它和 string 類型相同,隻是在操作時會将每個位元組拆分成 8 個二進制位。

應用場景

bitmap 類型的應用場景主要是利用二進制位的特性,比如:

  • 統計使用者活躍度,利用 setbit 和 bitcount 指令實作每天或每月使用者登入次數的統計。
  • 實作布隆過濾器,利用 setbit 和 getbit 指令實作快速判斷一個元素是否存在于一個集合中。
  • 實作位圖索引,利用 bitop 和 bitpos 指令實作對多個條件進行位運算和定位

假如需要統計每個使用者的當天登入次數統計。

首先,需要規定bitmap的格式,假設為{userid}:{年份}:{第幾天} {秒數} {是否登入}

将userid為100的使用者,記錄他在2024年第100天中第1秒,是否登入
SETBIT 1000:2024:100 1 1
0

           
将userid為100的使用者,記錄他在2024年第100天中第10240 秒,是否登入
SETBIT 1000:2024:100 10240 1
0
           
将userid為100的使用者,記錄他在2024年第100天中第86400 秒,是否登入
SETBIT 1000:2024:100 86400 1
0
           
統計userid為100的使用者,在2024年第100天的登入次數
BITCOUNT 1000:2024:100
3
           

Bitfield

概述

bitfield結構是基于字元串類型的一種擴充,可以讓你對一個字元串中的任意位進行設定,增加和擷取操作,就像一個位數組一樣

可以操作任意位長度的整數,從無符号的1位整數到有符号的63位整數。這些值是使用二進制編碼的Redis字元串來存儲的

bitfield結構支援原子的讀,寫和增加操作,使它們成為管理計數器和類似數值的好選擇

使用場景

Bitfield的使用場景與bitmap 類似,主要是一些需要用不同位長度的整數來表示狀态或屬性的場合,例如:

  • 用一個32位的無符号整數來表示使用者的金币數量,用一個32位的無符号整數來表示使用者殺死的怪物數量,可以友善地對這些數值進行設定,增加和擷取
  • 用一個16位的有符号整數來表示使用者的等級,用一個16位的有符号整數來表示使用者的經驗值,可以友善地對這些數值進行設定,增加和擷取
  • 用一個8位的無符号整數來表示使用者的性别,用一個8位的無符号整數來表示使用者的年齡,可以友善地對這些數值進行設定,增加和擷取

bitfield和bitmap都是基于string類型的位操作,但是有一些差別:

  • bitmap隻能操作1位的無符号整數,而bitfield可以操作任意位長度的有符号或無符号整數
  • bitmap隻能設定或擷取指定偏移量上的位,而bitfield可以對指定偏移量上的位進行增加或減少操作
  • bitmap可以對多個字元串進行位運算,而bitfield隻能對單個字元串進行位操作
  • bitmap的偏移量是從0開始的,而bitfield的偏移量是從最高有效位開始的

例如,使用bitfield存儲使用者的個人資訊,

  • 用一個8位的無符号整數來表示使用者的性别,0表示男,1表示女
  • 用一個8位的無符号整數來表示使用者的年齡,範圍是0-255
  • 用一個16位的無符号整數來表示使用者的身高,機關是厘米,範圍是0-65535
  • 用一個16位的無符号整數來表示使用者的體重,機關是克,範圍是0-65535

假設有一個使用者,性别是女,年齡是25,身高是165厘米,體重是50千克,可以用以下指令來存儲和擷取這些資訊:

> BITFIELD user:1:info SET u8 #0 1 SET u8 #1 25 SET u16 #2 165 SET u16 #3 50000
0
0
0
0
           

然後,擷取這個使用者的資訊,性别、年齡、身高、體重

> BITFIELD user:1:info GET u8 #0 GET u8 #1 GET u16 #2 GET u16 #3
1
25
165
50000           

繼續閱讀