技術文章 » 聊一聊redis十種資料型別及底層原理

聊一聊redis十種資料型別及底層原理

2023-05-09 12:02:06

概述

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結構

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中ziplist原始碼

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

listpack結構

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

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

listpack是如何解決的

  1. 由於ziplist需要倒著遍歷，所以需要用previous_entry_length記錄前一個entry的長度。而listpack可以通過total_bytes和end計算出來。所以previous_entry_length不需要了。
  2. listpack 的設計徹底消滅了 ziplist 存在的級聯更新行為，元素與元素之間完全獨立，不會因為一個元素的長度變長就導致後續的元素內容會受到影響。
  3. 與ziplist做對比的話，犧牲了記憶體使用率，避免了連鎖更新的情況。從程式碼複雜度上看，listpack相對ziplist簡單很多，再把增刪改統一做處理，從listpack的程式碼實現上看，極簡且高效。

hashTable

hashTable是一種雜湊表結構，它將欄位和值分別儲存在兩個陣列中，並通過雜湊函數計算欄位在陣列中的索引

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的轉換

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 步驟

擴充套件雜湊和收縮雜湊都是通過執行rehash來完成，這其中就涉及到了空間的分配和釋放，主要經過以下五步：

  1. 為字典dict的ht[1]雜湊表分配空間，其大小取決於當前雜湊表已儲存節點數（即：ht[0].used）：
    • 如果是擴充套件操作則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的值
  2. 將字典中的屬性rehashidx的值設定為0，表示正在執行rehash操作
  3. 將ht[0]中所有的鍵值對依次重新計算雜湊值，並放到ht[1]陣列對應位置，每完成一個鍵值對的rehash之後rehashidx的值需要自增1
  4. 當ht[0]中所有的鍵值對都遷移到ht[1]之後，釋放ht[0]，並將ht[1]修改為ht[0]，然後再建立一個新的ht[1]陣列，為下一次rehash做準備
  5. 將字典中的屬性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兩種編碼可以選擇切換，它們之間的轉換關係如圖

同樣地，ziplist轉為linkedlist的條件可在redis.conf設定

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

quickList（ziplist、linkedlist結合版）

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

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中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

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處

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

  • 雜湊函數的選擇不合適，沒有充分利用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的編碼為intset：如果沒有超過閾值，轉換為listpack；否則，直接轉換為hashtable
    • 當前set的編碼為listpack：如果超過閾值，就轉換為hashtable
    • 當前set的編碼為hashtable：直接插入，編碼不會進行轉換

    閾值條件為：
    set-max-listpack-entries：最大元素個數，預設128
    set_max_listpack_value：最大元素大小，預設64
    以上兩個條件需要同時滿足才能進行編碼轉換

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的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

資料結構為：

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

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

資料結構為：

其插入過程為：

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

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

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

資料結構為：

其插入過程為：

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

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

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

資料結構為：

其插入過程為：

  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

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

Stream

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

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