天天看點
傳回

探索Redis設計與實作開篇：什麼是Redisredis 學習筆記

redis 學習筆記

這篇 redis 學習筆記主要介紹 redis 的資料結構和資料類型，并讨論資料結構的選擇以及應用場景的優化。

redis 是什麼?

Redis是一種面向“鍵/值”對類型資料的分布式NoSQL資料庫系統，特點是高性能，持久存儲，适應高并發的應用場景。

Redis 資料結構

  • 動态字元串 (Sds)
  • 雙端清單 (LINKEDLIST)
  • 字典
  • 跳躍表 (SKIPLIST)
  • 整數集合 (INTSET)
  • 壓縮清單 (ZIPLIST)

HUGOMORE42

動态字元串

Sds (Simple Dynamic String,簡單動态字元串)是 Redis 底層所使用的字元串表示,它被用 在幾乎所有的 Redis 子產品中

Redis 是一個鍵值對資料庫(key-value DB),資料庫的值可以是字元串、集合、清單等多種類 型的對象,而資料庫的鍵則總是字元串對象

在 Redis 中, 一個字元串對象除了可以儲存字元串值之外,還可以儲存 long 類型的值當字元串對象儲存的是字元串時,它包含的才是 sds 值,否則的話,它就 是一個 long 類型的值

動态字元串主要有兩個作用:

  1. 實作字元串對象(StringObject)
  2. 在 Redis 程式内部用作 char * 類型的替代品
雙端清單

雙端連結清單還是 Redis 清單類型的底層實作之一，當對清單類型的鍵進行操作——比如執行 RPUSH 、LPOP 或 LLEN 等指令時,程式在底層操作的可能就是雙端連結清單

雙端連結清單主要有兩個作用:

  • 作為 Redis 清單類型的底層實作之一;
  • 作為通用資料結構,被其他功能子產品所使用;

字典(dictionary),又名映射(map)或關聯數組(associative array), 它是一種抽象資料結 構,由一集鍵值對(key-value pairs)組成,各個鍵值對的鍵各不相同,程式可以将新的鍵值對 添加到字典中,或者基于鍵進行查找、更新或删除等操作

字典的應用

  1. 實作資料庫鍵空間(key space);
  2. 用作 Hash 類型鍵的其中一種底層實作;
Redis 是一個鍵值對資料庫,資料庫中的鍵值對就由字典儲存:每個資料庫都有一個與之相對應的字典,這個字典被稱之為鍵空間(key space)。

Redis 的 Hash 類型鍵使用字典和壓縮清單兩種資料結構作為底層實作

跳躍表

跳躍表(skiplist)是一種随機化的資料,由 William Pugh 在論文《Skip lists: a probabilistic alternative to balanced trees》中提出,這種資料結構以有序的方式在階層化的連結清單中儲存元素,它的效率可以和平衡樹媲美——查找、删除、添加等操作都可以在對數期望時間下完成, 并且比起平衡樹來說,跳躍表的實作要簡單直覺得多

和字典、連結清單或者字元串這幾種在 Redis 中大量使用的資料結構不同,跳躍表在 Redis 的唯一作用,就是實作有序集資料類型

跳躍表将指向有序集的 score 值和 member 域的指針作為元素,并以 score 值為索引,對有序集元素進行排序。

整數集合

整數集合(intset)用于有序、無重複地儲存多個整數值,它會根據元素的值,自動選擇該用什麼長度的整數類型來儲存元素

Intset 是集合鍵的底層實作之一,如果一個集合:

  1. 隻儲存着整數元素;

  2. 元素的數量不多;

    那麼 Redis 就會使用 intset 來儲存集合元素。

壓縮清單

Ziplist 是由一系列特殊編碼的記憶體塊構成的清單,一個 ziplist 可以包含多個節點(entry),每個節點可以儲存一個長度受限的字元數組(不以 \0 結尾的 char 數組)或者整數

Redis 資料類型

RedisObject

redisObject 是 Redis 類型系統的核心,資料庫中的每個鍵、值,以及 Redis 本身處理的參數,都表示為這種資料類型

redisObject 的定義位于 redis.h :

/*
* Redis 對象
*/
typedef struct redisObject {
    // 類型
    unsigned type:4;
    // 對齊位
    unsigned notused:2;
    // 編碼方式
    unsigned encoding:4;
    // LRU 時間(相對于 server.lruclock)
    unsigned lru:22;
    // 引用計數
    int refcount;
    // 指向對象的值
    void *ptr;
} robj;

type 、encoding 和 ptr 是最重要的三個屬性。

type 記錄了對象所儲存的值的類型,它的值可能是以下常量的其中一個

/*
* 對象類型
*/
#define REDIS_STRING 0 // 字元串
#define REDIS_LIST 1   // 清單
#define REDIS_SET 2    // 集合
#define REDIS_ZSET 3   // 有序集
#define REDIS_HASH 4   // 哈希表

encoding 記錄了對象所儲存的值的編碼,它的值可能是以下常量的其中一個

/*
* 對象編碼
*/
#define REDIS_ENCODING_RAW 0    // 編碼為字元串
#define REDIS_ENCODING_INT 1    // 編碼為整數
#define REDIS_ENCODING_HT 2     // 編碼為哈希表
#define REDIS_ENCODING_ZIPMAP 3 // 編碼為 zipmap(2.6 後不再使用)
#define REDIS_ENCODING_LINKEDLIST 4 // 編碼為雙端連結清單
#define REDIS_ENCODING_ZIPLIST 5    // 編碼為壓縮清單
#define REDIS_ENCODING_INTSET 6     // 編碼為整數集合
#define REDIS_ENCODING_SKIPLIST 7    // 編碼為跳躍表

ptr 是一個指針,指向實際儲存值的資料結構,這個資料結構由 type 屬性和 encoding 屬性決定。

當執行一個處理資料類型的指令時,Redis 執行以下步驟:

  1. 根據給定key,在資料庫字典中查找和它像對應的redisObject,如果沒找到,就傳回 NULL 。
  2. 檢查redisObject的type屬性和執行指令所需的類型是否相符,如果不相符,傳回類 型錯誤。
  3. 根據redisObject的encoding屬性所指定的編碼,選擇合适的操作函數來處理底層的 資料結構。
  4. 傳回資料結構的操作結果作為指令的傳回值。
字元串

REDIS_STRING (字元串)是 Redis 使用得最為廣泛的資料類型,它除了是 SET 、GET 等指令 的操作對象之外,資料庫中的所有鍵,以及執行指令時提供給 Redis 的參數,都是用這種類型 儲存的。

字元串類型分别使用 REDIS_ENCODING_INT 和 REDIS_ENCODING_RAW 兩種編碼

隻有能表示為 long 類型的值,才會以整數的形式儲存,其他類型 的整數、小數和字元串,都是用 sdshdr 結構來儲存
哈希表

REDIS_HASH (哈希表)是HSET 、HLEN 等指令的操作對象

它使用 REDIS_ENCODING_ZIPLIST和REDIS_ENCODING_HT 兩種編碼方式

Redis 中每個hash可以存儲232-1鍵值對（40多億）

清單

REDIS_LIST(清單)是LPUSH 、LRANGE等指令的操作對象

它使用 REDIS_ENCODING_ZIPLIST和REDIS_ENCODING_LINKEDLIST 這兩種方式編碼

一個清單最多可以包含232-1 個元素(4294967295, 每個清單超過40億個元素)。

集合

REDIS_SET (集合) 是 SADD 、 SRANDMEMBER 等指令的操作對象

它使用 REDIS_ENCODING_INTSET 和 REDIS_ENCODING_HT 兩種方式編碼

Redis 中集合是通過哈希表實作的，是以添加，删除，查找的複雜度都是O(1)。

集合中最大的成員數為 232 - 1 (4294967295, 每個集合可存儲40多億個成員)

有序集

REDIS_ZSET (有序集)是ZADD 、ZCOUNT 等指令的操作對象

它使用 REDIS_ENCODING_ZIPLIST和REDIS_ENCODING_SKIPLIST 兩種方式編碼

不同的是每個元素都會關聯一個double類型的分數。redis正是通過分數來為集合中的成員進行從小到大的排序。

有序集合的成員是唯一的,但分數(score)卻可以重複。

集合是通過哈希表實作的，是以添加，删除，查找的複雜度都是O(1)。 集合中最大的成員數為 232 - 1 (4294967295, 每個集合可存儲40多億個成員)

Redis各種資料類型_以及它們的編碼方式

過期時間

在資料庫中,所有鍵的過期時間都被儲存在 redisDb 結構的 expires 字典裡:

typedef struct redisDb {
    // ...
    dict *expires;
    // ...
} redisDb;

expires 字典的鍵是一個指向 dict 字典(鍵空間)裡某個鍵的指針,而字典的值則是鍵所指 向的資料庫鍵的到期時間,這個值以 long long 類型表示

過期時間設定

Redis 有四個指令可以設定鍵的生存時間(可以存活多久)和過期時間(什麼時候到期):

  • EXPIRE 以秒為機關設定鍵的生存時間;
  • PEXPIRE 以毫秒為機關設定鍵的生存時間;
  • EXPIREAT 以秒為機關,設定鍵的過期 UNIX 時間戳;
  • PEXPIREAT 以毫秒為機關,設定鍵的過期 UNIX 時間戳。
雖然有那麼多種不同機關和不同形式的設定方式,但是 expires 字典的值隻儲存“以毫秒為機關的過期 UNIX 時間戳” ,這就是說,通過進行轉換,所有指令的效果最後都和 PEXPIREAT 指令的效果一樣。

如果一個鍵是過期的,那它什麼時候會被删除?

下邊是參考答案

  1. 定時删除:在設定鍵的過期時間時,建立一個定時事件,當過期時間到達時,由事件處理 器自動執行鍵的删除操作。
  2. 惰性删除:放任鍵過期不管,但是在每次從 dict 字典中取出鍵值時,要檢查鍵是否過 期,如果過期的話,就删除它,并傳回空;如果沒過期,就傳回鍵值。
  3. 定期删除:每隔一段時間,對expires字典進行檢查,删除裡面的過期鍵

Redis 使用的過期鍵删除政策是惰性删除加上定期删除

應用場景

  • 緩存
  • 隊列
  • 需要精準設定過期時間的應用
比如你可以把上面說到的sorted set的score值設定成過期時間的時間戳，那麼就可以簡單地通過過期時間排序，定時清除過期資料了，不僅是清除Redis中的過期資料，你完全可以把Redis裡這個過期時間當成是對資料庫中資料的索引，用Redis來找出哪些資料需要過期删除，然後再精準地從資料庫中删除相應的記錄
  • 排行榜應用，取TOP N操作
    這個需求與上面需求的不同之處在于，前面操作以時間為權重，這個是以某個條件為權重，比如按頂的次數排序，這時候就需要我們的sorted set出馬了，将你要排序的值設定成sorted set的score，将具體的資料設定成相應的value，每次隻需要執行一條ZADD指令即可
  • 統計頁面通路次數
使用 incr 指令 定時使用 getset 指令 讀取資料 并設定新的值 0
  • 使用set 設定标簽

例如假設我們的話題D 1000被加了三個标簽tag 1,2,5和77，就可以設定下面兩個集合：

$ redis-cli sadd topics:1000:tags 1
(integer) 1
$ redis-cli sadd topics:1000:tags 2
(integer) 1
$ redis-cli sadd topics:1000:tags 5
(integer) 1
$ redis-cli sadd topics:1000:tags 77
(integer) 1
$ redis-cli sadd tag:1:objects 1000
(integer) 1
$ redis-cli sadd tag:2:objects 1000
(integer) 1
$ redis-cli sadd tag:5:objects 1000
(integer) 1
$ redis-cli sadd tag:77:objects 1000
(integer) 1

要擷取一個對象的所有标簽：

$ redis-cli smembers topics:1000:tags
1. 5
2. 1
3. 77
4. 2

獲得一份同時擁有标簽1, 2,10和27的對象清單。

這可以用SINTER指令來做，他可以在不同集合之間取出交集

記憶體優化

問題

: Instagram的照片數量已經達到3億，而在Instagram裡，我們需要知道每一張照片的作者是誰，下面就是Instagram團隊如何使用Redis來解決這個問題并進行記憶體優化的。

具體方法，參考下邊這篇文章：

節約記憶體：Instagram的Redis實踐

。

天下無難試之Redis面試刁難大全

Redis在網際網路技術存儲方面使用如此廣泛，幾乎所有的後端技術面試官都要在Redis的使用和原理方面對小夥伴們進行各種刁難。作為一名在網際網路技術行業打擊過成百上千名【請允許我誇張一下】的資深技術面試官，看過了無數落寞的身影失望的離開，略感愧疚，故獻上此文，希望各位讀者以後面試勢如破竹，永無失敗！

探索Redis設計與實作開篇：什麼是Redisredis 學習筆記

Redis有哪些資料結構？

字元串String、字典Hash、清單List、集合Set、有序集合SortedSet。

如果你是Redis中進階使用者，還需要加上下面幾種資料結構HyperLogLog、Geo、Pub/Sub。

如果你說還玩過Redis Module，像BloomFilter，RedisSearch，Redis-ML，面試官得眼睛就開始發亮了。

使用過Redis分布式鎖麼，它是什麼回事？

先拿setnx來争搶鎖，搶到之後，再用expire給鎖加一個過期時間防止鎖忘記了釋放。

這時候對方會告訴你說你回答得不錯，然後接着問如果在setnx之後執行expire之前程序意外crash或者要重新開機維護了，那會怎麼樣？

這時候你要給予驚訝的回報：唉，是喔，這個鎖就永遠得不到釋放了。緊接着你需要抓一抓自己得腦袋，故作思考片刻，好像接下來的結果是你主動思考出來的，然後回答：我記得set指令有非常複雜的參數，這個應該是可以同時把setnx和expire合成一條指令來用的！對方這時會顯露笑容，心裡開始默念：摁，這小子還不錯。

假如Redis裡面有1億個key，其中有10w個key是以某個固定的已知的字首開頭的，如果将它們全部找出來？

使用keys指令可以掃出指定模式的key清單。

對方接着追問：如果這個redis正在給線上的業務提供服務，那使用keys指令會有什麼問題？

這個時候你要回答redis關鍵的一個特性：redis的單線程的。keys指令會導緻線程阻塞一段時間，線上服務會停頓，直到指令執行完畢，服務才能恢複。這個時候可以使用scan指令，scan指令可以無阻塞的提取出指定模式的key清單，但是會有一定的重複機率，在用戶端做一次去重就可以了，但是整體所花費的時間會比直接用keys指令長。

使用過Redis做異步隊列麼，你是怎麼用的？

一般使用list結構作為隊列，rpush生産消息，lpop消費消息。當lpop沒有消息的時候，要适當sleep一會再重試。

如果對方追問可不可以不用sleep呢？list還有個指令叫blpop，在沒有消息的時候，它會阻塞住直到消息到來。

如果對方追問能不能生産一次消費多次呢？使用pub/sub主題訂閱者模式，可以實作1:N的消息隊列。

如果對方追問pub/sub有什麼缺點？在消費者下線的情況下，生産的消息會丢失，得使用專業的消息隊列如rabbitmq等。

如果對方追問redis如何實作延時隊列？我估計現在你很想把面試官一棒打死如果你手上有一根棒球棍的話，怎麼問的這麼詳細。但是你很克制，然後神态自若的回答道：使用sortedset，拿時間戳作為score，消息内容作為key調用zadd來生産消息，消費者用zrangebyscore指令擷取N秒之前的資料輪詢進行處理。

到這裡，面試官暗地裡已經對你豎起了大拇指。但是他不知道的是此刻你卻豎起了中指，在椅子背後。

如果有大量的key需要設定同一時間過期，一般需要注意什麼？

如果大量的key過期時間設定的過于集中，到過期的那個時間點，redis可能會出現短暫的卡頓現象。一般需要在時間上加一個随機值，使得過期時間分散一些。

Redis如何做持久化的？

bgsave做鏡像全量持久化，aof做增量持久化。因為bgsave會耗費較長時間，不夠實時，在停機的時候會導緻大量丢失資料，是以需要aof來配合使用。在redis執行個體重新開機時，會使用bgsave持久化檔案重新建構記憶體，再使用aof重放近期的操作指令來實作完整恢複重新開機之前的狀态。

對方追問那如果突然機器掉電會怎樣？取決于aof日志sync屬性的配置，如果不要求性能，在每條寫指令時都sync一下磁盤，就不會丢失資料。但是在高性能的要求下每次都sync是不現實的，一般都使用定時sync，比如1s1次，這個時候最多就會丢失1s的資料。

對方追問bgsave的原理是什麼？你給出兩個詞彙就可以了，fork和cow。fork是指redis通過建立子程序來進行bgsave操作，cow指的是copy on write，子程序建立後，父子程序共享資料段，父程序繼續提供讀寫服務，寫髒的頁面資料會逐漸和子程序分離開來。

Pipeline有什麼好處，為什麼要用pipeline？

可以将多次IO往返的時間縮減為一次，前提是pipeline執行的指令之間沒有因果相關性。使用redis-benchmark進行壓測的時候可以發現影響redis的QPS峰值的一個重要因素是pipeline批次指令的數目。

Redis的同步機制了解麼？

Redis可以使用主從同步，從從同步。第一次同步時，主節點做一次bgsave，并同時将後續修改操作記錄到記憶體buffer，待完成後将rdb檔案全量同步到複制節點，複制節點接受完成後将rdb鏡像加載到記憶體。加載完成後，再通知主節點将期間修改的操作記錄同步到複制節點進行重放就完成了同步過程。

是否使用過Redis叢集，叢集的原理是什麼？

Redis Sentinal着眼于高可用，在master當機時會自動将slave提升為master，繼續提供服務。

Redis Cluster着眼于擴充性，在單個redis記憶體不足時，使用Cluster進行分片存儲。

微信公衆号【黃小斜】大廠程式員，網際網路行業新知，終身學習踐行者。關注後回複「Java」、「Python」、「C++」、「大資料」、「機器學習」、「算法」、「AI」、「Android」、「前端」、「iOS」、「考研」、「BAT」、「校招」、「筆試」、「面試」、「面經」、「計算機基礎」、「LeetCode」 等關鍵字可以擷取對應的免費學習資料。 

                     ​

存儲 NoSQL unix 資料庫 Redis Redis設計與實作 行資料存儲 Redis資料存儲 Redis設計與實作sds 資料存儲函數
上一篇: 《深入分析JavaWeb技術内幕》讀書筆記 《深入分析JavaWeb技術内幕》讀書筆記  一.Web請求過程與架構
下一篇: 對企業級應用開發的思考（3）--業務層的實作方式

繼續閱讀