技術文章 » 深度剖析Redis九種資料結構實現原理，建議收藏

深度剖析Redis九種資料結構實現原理，建議收藏

2023-04-11 12:00:21

1. Redis介紹

Redis 是一個高效能的鍵值儲存系統，支援多種資料結構。

包含五種基本型別 String（字串）、Hash（雜湊）、List（列表）、Set（集合）、Zset（有序集合），和三種特殊型別 Geo（地理位置）、HyperLogLog（基數統計）、Bitmaps（點陣圖）。

每種資料結構都是為了解決特定問題而設計的，適用不同的場景。想要用好Redis，必須瞭解底層實現原理和使用技巧，同時結合具體的業務場景和需求進行選擇和使用。無論是工作還是面試中，這些必備的知識。

下面就詳細介紹一下每種資料型別的使用方式、實現原理和適用場景。

2. String（字串）

String（字串）是Redis中最基本的資料結構之一，它可以儲存任意型別的資料，包括數位、文字、序列化的物件等。Redis中的字串最大可以儲存512MB的資料。

使用方式

字串型別的操作是最基本的，包括設定值、獲取值、修改值、追加值等。字串型別支援的操作包括：

應用場景

  • 快取：將計算結果、資料庫查詢結果或者設定資料儲存在Redis中，可以提高應用的響應速度和吞吐量。
  • 計數器：使用Redis的自增和自減操作，實現簡單的計數器功能，如網站的存取次數統計
  • 限流：使用Redis的incr和expire命令，實現固定視窗演演算法的流量控制，防止系統過載。
  • 分散式鎖：使用SETNX操作實現分散式鎖，保證同一時刻只有一個執行緒存取臨界資源。
  • 對談管理：將使用者對談資訊儲存在Redis中，可以實現分散式Session。

內部編碼

Redis字串的內部編碼有三種：

  1. int編碼：當字串長度小於等於12位元組並且字串可以表示為整數時，Redis會使用int編碼。這樣可以節省記憶體，並且在執行一些命令時可以直接進行數值計算。
  2. embstr編碼：當字串長度小於等於39位元組時，Redis會使用embstr編碼。這種編碼方式會將字串和儲存它的結構體一起分配在記憶體中，這樣可以減少記憶體碎片和結構體的開銷。
  3. raw編碼：當字串長度大於39位元組或者字串不能表示為整數時，Redis會使用raw編碼。這種編碼方式直接將字串儲存在一個結構體中，沒有進行任何優化。

3. Hash（雜湊）

使用方式

雜湊型別是一種鍵值對的集合，其中鍵值對的值可以是字串、列表或者其他雜湊型別。雜湊型別支援的操作包括：

應用場景

  • 儲存物件：將物件的屬性和屬性值儲存在雜湊型別中，可以很方便地進行查詢和更新操作，比如常見的使用者資訊就適合使用雜湊型別儲存。

內部編碼

Redis雜湊型別的內部編碼有兩種：

  1. ziplist（壓縮列表）：當Hash型別的元素比較少，且元素的大小比較小（小於64位元組）時，Redis採用ziplist作為Hash型別的內部編碼。ziplist是一種緊湊的、壓縮的列表結構，可以節省記憶體空間。但是，ziplist只能進行線性查詢，不支援快速的隨機存取。
  2. hashtable（字典）：當Hash型別的元素比較多，或者元素的大小比較大（大於64位元組）時，Redis採用hashtable作為Hash型別的內部編碼。hashtable是一種基於連結串列的雜湊表結構，可以快速地進行隨機存取。但是，hashtable需要佔用更多的記憶體空間。

4. List（列表）

使用方式

Redis List型別是一個有序的字串列表，支援在列表的頭部或尾部新增元素，也支援在列表任意位置插入或刪除元素。支援的操作包括：

使用場景

Redis List型別由於支援在列表的頭部或尾部新增元素，也支援在列表任意位置插入或刪除元素，因此非常適合以下場景：

  • 訊息佇列：Redis List型別常被用作輕量級的訊息佇列，生產者將訊息插入佇列尾部，消費者從佇列頭部彈出訊息進行處理，可以使用LPUSH、RPUSH、BLPOP、BRPOP等命令實現。
  • 時間序列：使用Redis的LPUSH和RPUSH命令，將時間序列的資料按照時間順序新增到列表的頭部或尾部，然後使用LRANGE命令，查詢一段時間範圍內的資料，實現時間序列的查詢。
  • 排行榜：Redis List型別可以用於實現排行榜功能，將每個使用者的得分作為元素值插入到列表中，使用LINSERT、LREM、LINDEX等命令進行排名操作，使用LRANGE命令查詢排名前幾的使用者，可以使用LPUSH、LINSERT、LREM、LINDEX、LRANGE等命令實現。
  • 計數器：Redis List型別可以將每個元素視為計數器的值，可以使用LPUSH、RPUSH、LINDEX、LREM等命令實現。
  • 最近存取記錄：Redis List型別可以用於記錄最近存取的記錄，將最新的存取記錄插入列表頭部，當列表長度超過設定的值時，使用LTRIM命令刪除最舊的記錄，可以使用LPUSH、LINDEX、LTRIM等命令實現。

內部編碼

Redis List型別內部編碼有兩種，分別是ziplist和linkedlist。

  • ziplist

ziplist是一種特殊的編碼方式，它可以將小資料量的列表儲存在一個連續的記憶體塊中，節省了記憶體空間，同時還可以提高存取效率。

ziplist編碼的列表最大長度為2^16-1個元素，每個元素可以是字串型別、整數型別或浮點數型別。在ziplist中，每個元素都被儲存為一個位元組陣列，幷包含一個字首和一個字尾，用於標識該元素的型別和長度。

  • linkedlist

linkedlist是一種常規的雙向連結串列結構，它可以儲存任意長度的列表，並且支援高效的插入和刪除操作。在linkedlist中，每個節點都包含了一個指向前一個節點和後一個節點的指標，以及一個儲存元素資料的指標。

linkedlist適用於儲存大數量的列表，它沒有像ziplist那樣的記憶體限制，但是會佔用更多的記憶體空間。

5. Set（集合）

使用方式

Redis Set（集合）是一個無序的字串集合，其中每個元素都是唯一的，不允許重複。Redis Set型別支援的操作包括：

使用場景

Redis Set型別的使用場景包括：

  • 標籤系統：使用Set型別儲存每個標籤對應的物件列表，以便快速查詢包含特定標籤的物件。可以使用SADD、SREM、SISMEMBER、SMEMBERS等命令實現。
  • 好友關係：將每個使用者的好友列表作為一個集合，可以使用SADD、SREM、SISMEMBER、SDIFF、SINTER、SUNION等命令實現。
  • 共同好友：使用SINTER命令計算出兩個使用者的共同好友，可以使用SADD、SINTER、SUNION等命令實現。
  • 排名系統：將每個使用者的得分作為元素值插入到集合中，使用ZADD、ZREM、ZRANK、ZSCORE等命令進行排名操作，使用ZREVRANGE命令查詢排名前幾的使用者，可以使用ZADD、ZREM、ZRANK、ZSCORE、ZREVRANGE等命令實現。
  • 訂閱關係：使用Set型別儲存使用者訂閱的內容，以便快速獲取使用者訂閱的內容。

總的來說，Set型別適用於需要儲存一組不重複的資料，並支援集合操作的場景。

內部編碼

Redis Set型別的內部編碼有兩種：

  1. intset（整數集合）：當Set型別只包含整數型別的資料，並且元素數量較少（小於512個）時，Redis會使用intset作為Set型別的內部編碼。intset是一種緊湊的、壓縮的整數集合結構，可以節省記憶體空間，並且支援快速的查詢、插入和刪除操作。在intset中，所有元素都按照從小到大的順序排列，並且可以使用不同的編碼方式（16位元、32位元、64位元）儲存不同大小範圍內的整數。
  2. hashtable（字典）：當Set型別包含字串型別或者元素數量較多時，Redis會使用hashtable作為Set型別的內部編碼。hashtable是一種基於連結串列的雜湊表結構，可以快速地進行隨機存取、插入和刪除操作。在hashtable中，每個元素都被儲存為一個字串，並且使用雜湊函數將字串對映到一個桶中，然後在桶中進行查詢、插入和刪除操作。

在實際使用中，當Set型別的元素全部為整數型別時，建議使用intset編碼；而當Set型別的元素包含非整數型別時，才使用hashtable編碼。

6. Zset（有序集合）

使用方式

Redis中的Zset（有序集合）是一個鍵值對集合，其中每個元素都關聯一個分值（score），通過分值進行排序，可以看作是一個字典（dict）和一個跳躍列表（skip list）的混合體，它可以儲存多個相同的元素，但每個元素必須有一個唯一的score值。

支援的操作包括：

使用場景

Redis Zset是一種有序集合，其使用場景主要包括以下幾個方面：

  • 排行榜：使用Zset型別可以實現排行榜功能，將每個使用者的得分作為元素值插入到集合中，使用ZADD、ZINCRBY、ZREM等命令進行排名操作，使用ZRANGE、ZREVRANGE命令查詢排名前幾的使用者。
  • 最近存取記錄：使用Zset型別可以用於記錄最近存取的記錄，將最新的存取記錄插入集合中，使用ZREMRANGEBYRANK命令刪除最舊的記錄，使用ZRANGE命令查詢最近存取的記錄。
  • 計數器：Redis Zset可以用於實現計數器功能，比如統計某個頁面的存取次數、統計某個廣告的點選量等。將頁面ID或廣告ID作為成員(member)儲存在Zset中，以存取次數或點選量作為分數(score)儲存。
  • 好友關係：Redis Zset可以用於儲存使用者之間的關注關係以及使用者之間的互動，比如點贊、評論等。可以將使用者ID作為成員(member)儲存在Zset中，將時間戳或者其他標識作為分數(score)儲存，以此記錄使用者之間的互動情況。

內部編碼

Redis Zset的內部編碼有兩種：

  1. ziplist編碼：當Zset中元素個數小於128個，並且所有元素的長度都小於64位元組時，Redis會使用ziplist編碼儲存Zset。這種編碼方式可以節省記憶體空間，並且可以提高存取效率，但是不支援隨機存取和範圍查詢。
  2. skiplist編碼：當Zset中元素個數大於等於128個，或者有一個元素的長度大於64位元組時，Redis會使用skiplist編碼儲存Zset。這種編碼方式支援高效的隨機存取和範圍查詢，但是需要佔用更多的記憶體空間。

7. Geo（地理位置）

使用方式

Redis Geo（地理位置）是一個鍵值對集合，其中每個元素都包含一個經度和緯度，可以用於儲存地理位置資訊並支援基於位置的搜尋。Redis Geo支援的操作包括：

Redis Geo型別適用於需要儲存地理位置資訊並支援基於位置的搜尋的場景，比如附近的人、附近的商家等。

使用場景

Redis Geo型別的使用場景如下：

  1. 位置服務：用於儲存地理位置資訊，如餐廳、商店、機場、醫院等的經緯度資訊，可以通過 Geo 庫提供的命令查詢指定範圍內的所有商家資訊。
  2. 車輛監控：用於車輛位置跟蹤和監控，可以將車輛的經緯度資訊儲存在 Redis 中，並通過 Geo 庫提供的命令查詢車輛的位置，以及在指定半徑內的其他車輛資訊。
  3. 物流配送：用於儲存配送員的位置資訊，以及需要配送的訂單資訊的經緯度資訊，可以通過 Geo 庫提供的命令查詢配送員在指定範圍內的訂單資訊，以提高配送效率。
  4. 電商推薦：用於儲存使用者的位置資訊，以及商家和商品的經緯度資訊，可以通過 Geo 庫提供的命令查詢指定範圍內的商家和商品資訊，以提供更加精準的推薦服務。
  5. 遊戲地圖：用於儲存遊戲地圖的位置資訊和玩家的位置資訊，可以通過 Geo 庫提供的命令查詢玩家在遊戲地圖上的位置，以及在指定半徑內的其他玩家資訊，以提供更加豐富的遊戲體驗。
  6. 社交應用：用於儲存使用者的位置資訊，以及附近的其他使用者的位置資訊，可以通過 Geo 庫提供的命令查詢指定範圍內的使用者資訊，以提供更加精準的社交服務。

內部編碼

Redis Geo型別內部使用zset來儲存地理位置資訊，其中元素的score值為經度，member值為經緯度組合的字串。在使用GEORADIUS和GEORADIUSBYMEMBER命令搜尋元素時，Redis會構建一個跳躍表，以實現高效的搜尋。

8. HyperLogLog（基數統計）

使用方式

Redis HyperLogLog（基數統計）是一種基於概率統計的資料結構，用於估計大型資料集合的基數（不重複元素的數量），以及對多個集合進行並、交運算等。HyperLogLog的優點是可以使用極少的記憶體空間，同時可以保證較高的準確性。

每個 HyperLogLog 鍵只需要花費 12 KB 記憶體，就可以計算接近 2^64 個不同元素的基數。

使用場景

HyperLogLog的使用場景主要包括以下幾個方面：

  • 使用者去重：使用HyperLogLog可以對海量的使用者資料進行去重，快速地統計出不重複的使用者數量。
  • 網站UV統計：使用HyperLogLog可以對網站的存取紀錄檔進行分析，統計出每天、每週、每月的獨立訪客數量。
  • 廣告點選統計：使用HyperLogLog可以對廣告的點選資料進行分析，統計出獨立點選使用者的數量，以及對多個廣告進行並、交運算等。
  • 資料庫查詢優化：使用HyperLogLog可以對資料庫中的資料進行去重，減少查詢的資料量，提高查詢效率。
  • 分散式計算：使用HyperLogLog可以在分散式系統中對資料進行去重、並、交等操作，以支援分散式計算。

使用HyperLogLog可以大大減少記憶體佔用和計算時間，是處理巨量資料量去重計數的有效工具。

內部編碼

Redis HyperLogLog型別的內部編碼使用的"稀疏矩陣"和」稠密矩陣「。

當計數較少時，採用」稀疏矩陣「，其中絕大部分元素都是0。計數增多後，超過閾值後，會轉換成」稠密矩陣「。

9. Bitmaps（點陣圖）

使用方式

Redis Bitmaps（點陣圖）是一種緊湊的資料結構，可以用於表示一個只有0和1的陣列。點陣圖可以用於高效地儲存大規模的布林值，以及進行位運算、點陣圖圖形化等操作。Redis Bitmaps支援的操作包括：

使用場景

Redis Bitmaps適用於需要高效地儲存大規模的布林值，並進行位運算、統計等操作的場景。比如：

  • 統計線上使用者數：使用Bitmaps型別來表示使用者的線上狀態，例如一個bit位表示一個使用者，當用戶登入時將對應的bit位置為1，當用戶退出時將其位置為0。這樣可以非常方便地進行線上使用者的統計。
  • 黑白名單統計：在網路安全中，可以使用點陣圖記錄IP地址的存取情況、黑白名單等資訊。
  • 統計使用者存取行為：例如將每個頁面或功能點表示為一個bit位，使用者存取時將對應的bit位置為1，未存取則為0。這樣就可以方便地統計使用者的存取習慣，瞭解使用者對產品的喜好和熱點等資訊。
  • 布隆過濾器：這是最常用的場景，布隆過濾器是一種用於快速判斷某個元素是否在集合中的演演算法，在巨量資料量場景下其效率非常高。Redis的Bitmaps型別可以用來實現布隆過濾器，節約儲存空間，並提高查詢效率。

內部編碼

Redis Bitmaps型別的內部編碼使用了一種稱為「壓縮點陣圖」的資料結構。它通過使用兩個陣列來儲存點陣圖資料：一個儲存實際位的值，另一個儲存每個位元組中1的個數。這種編碼方式可以大大壓縮點陣圖資料的大小。