出自：https://github.com/CyC2018/CS-Notes

微信公眾號(hào) 程序員喬戈里 編輯整理，轉(zhuǎn)載注明

• 一、概述

• 二、數(shù)據(jù)類型

• STRING

• LIST

• SET

• HASH

• ZSET

• 三、數(shù)據(jù)結(jié)構(gòu)

• 字典

• 跳躍表

• 四、使用場(chǎng)景

• 計(jì)數(shù)器

• 緩存

• 查找表

• 消息隊(duì)列

• 會(huì)話緩存

• 分布式鎖實(shí)現(xiàn)

• 其它

• 五、Redis 與 Memcached

• 數(shù)據(jù)類型

• 數(shù)據(jù)持久化

• 分布式

• 內(nèi)存管理機(jī)制

• 六、鍵的過期時(shí)間

• 七、數(shù)據(jù)淘汰策略

• 八、持久化

• RDB 持久化

• AOF 持久化

• 九、事務(wù)

• 十、事件

• 文件事件

• 時(shí)間事件

• 事件的調(diào)度與執(zhí)行

• 十一、復(fù)制

• 連接過程

• 主從鏈

• 十二、Sentinel

• 十三、分片

• 十四、一個(gè)簡(jiǎn)單的論壇系統(tǒng)分析

• 文章信息

• 點(diǎn)贊功能

• 對(duì)文章進(jìn)行排序

• 參考資料

一、概述

Redis 是速度非?？斓姆顷P(guān)系型（NoSQL）內(nèi)存鍵值數(shù)據(jù)庫，可以存儲(chǔ)鍵和五種不同類型的值之間的映射。

鍵的類型只能為字符串，值支持五種數(shù)據(jù)類型：字符串、列表、集合、散列表、有序集合。

Redis 支持很多特性，例如將內(nèi)存中的數(shù)據(jù)持久化到硬盤中，使用復(fù)制來擴(kuò)展讀性能，使用分片來擴(kuò)展寫性能。

二、數(shù)據(jù)類型

What Redis data structures look like

STRING

LIST

> rpush list-key item
(integer) 1
> rpush list-key item2
(integer) 2
> rpush list-key item
(integer) 3

> lrange list-key 0 -1
1) 'item'
2) 'item2'
3) 'item'

> lindex list-key 1
'item2'

> lpop list-key
'item'

> lrange list-key 0 -1
1) 'item2'
2) 'item'

SET

HASH

> hset hash-key sub-key1 value1
(integer) 1
> hset hash-key sub-key2 value2
(integer) 1
> hset hash-key sub-key1 value1
(integer) 0

> hgetall hash-key
1) 'sub-key1'
2) 'value1'
3) 'sub-key2'
4) 'value2'

> hdel hash-key sub-key2
(integer) 1
> hdel hash-key sub-key2
(integer) 0

> hget hash-key sub-key1
'value1'

> hgetall hash-key
1) 'sub-key1'
2) 'value1'

ZSET

三、數(shù)據(jù)結(jié)構(gòu)

字典

dictht 是一個(gè)散列表結(jié)構(gòu)，使用拉鏈法保存哈希沖突。

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

Redis 的字典 dict 中包含兩個(gè)哈希表 dictht，這是為了方便進(jìn)行 rehash 操作。在擴(kuò)容時(shí)，將其中一個(gè) dictht 上的鍵值對(duì) rehash 到另一個(gè) dictht 上面，完成之后釋放空間并交換兩個(gè) dictht 的角色。

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

rehash 操作不是一次性完成，而是采用漸進(jìn)方式，這是為了避免一次性執(zhí)行過多的 rehash 操作給服務(wù)器帶來過大的負(fù)擔(dān)。

漸進(jìn)式 rehash 通過記錄 dict 的 rehashidx 完成，它從 0 開始，然后每執(zhí)行一次 rehash 都會(huì)遞增。例如在一次 rehash 中，要把 dict[0] rehash 到 dict[1]，這一次會(huì)把 dict[0] 上 table[rehashidx] 的鍵值對(duì) rehash 到 dict[1] 上，dict[0] 的 table[rehashidx] 指向 null，并令 rehashidx++。

在 rehash 期間，每次對(duì)字典執(zhí)行添加、刪除、查找或者更新操作時(shí)，都會(huì)執(zhí)行一次漸進(jìn)式 rehash。

采用漸進(jìn)式 rehash 會(huì)導(dǎo)致字典中的數(shù)據(jù)分散在兩個(gè) dictht 上，因此對(duì)字典的查找操作也需要到對(duì)應(yīng)的 dictht 去執(zhí)行。

跳躍表

是有序集合的底層實(shí)現(xiàn)之一。

跳躍表是基于多指針有序鏈表實(shí)現(xiàn)的，可以看成多個(gè)有序鏈表。

在查找時(shí)，從上層指針開始查找，找到對(duì)應(yīng)的區(qū)間之后再到下一層去查找。下圖演示了查找 22 的過程。

與紅黑樹等平衡樹相比，跳躍表具有以下優(yōu)點(diǎn)：

• 插入速度非常快速，因?yàn)椴恍枰M(jìn)行旋轉(zhuǎn)等操作來維護(hù)平衡性；

• 更容易實(shí)現(xiàn)；

• 支持無鎖操作。

四、使用場(chǎng)景

計(jì)數(shù)器

可以對(duì) String 進(jìn)行自增自減運(yùn)算，從而實(shí)現(xiàn)計(jì)數(shù)器功能。

Redis 這種內(nèi)存型數(shù)據(jù)庫的讀寫性能非常高，很適合存儲(chǔ)頻繁讀寫的計(jì)數(shù)量。

緩存

將熱點(diǎn)數(shù)據(jù)放到內(nèi)存中，設(shè)置內(nèi)存的最大使用量以及淘汰策略來保證緩存的命中率。

查找表

例如 DNS 記錄就很適合使用 Redis 進(jìn)行存儲(chǔ)。

查找表和緩存類似，也是利用了 Redis 快速的查找特性。但是查找表的內(nèi)容不能失效，而緩存的內(nèi)容可以失效，因?yàn)榫彺娌蛔鳛榭煽康臄?shù)據(jù)來源。

消息隊(duì)列

List 是一個(gè)雙向鏈表，可以通過 lpush 和 rpop 寫入和讀取消息

不過最好使用 Kafka、RabbitMQ 等消息中間件。

會(huì)話緩存

可以使用 Redis 來統(tǒng)一存儲(chǔ)多臺(tái)應(yīng)用服務(wù)器的會(huì)話信息。

當(dāng)應(yīng)用服務(wù)器不再存儲(chǔ)用戶的會(huì)話信息，也就不再具有狀態(tài)，一個(gè)用戶可以請(qǐng)求任意一個(gè)應(yīng)用服務(wù)器，從而更容易實(shí)現(xiàn)高可用性以及可伸縮性。

分布式鎖實(shí)現(xiàn)

在分布式場(chǎng)景下，無法使用單機(jī)環(huán)境下的鎖來對(duì)多個(gè)節(jié)點(diǎn)上的進(jìn)程進(jìn)行同步。

可以使用 Redis 自帶的 SETNX 命令實(shí)現(xiàn)分布式鎖，除此之外，還可以使用官方提供的 RedLock 分布式鎖實(shí)現(xiàn)。

其它

Set 可以實(shí)現(xiàn)交集、并集等操作，從而實(shí)現(xiàn)共同好友等功能。

ZSet 可以實(shí)現(xiàn)有序性操作，從而實(shí)現(xiàn)排行榜等功能。

五、Redis 與 Memcached

兩者都是非關(guān)系型內(nèi)存鍵值數(shù)據(jù)庫，主要有以下不同：

數(shù)據(jù)類型

Memcached 僅支持字符串類型，而 Redis 支持五種不同的數(shù)據(jù)類型，可以更靈活地解決問題。

數(shù)據(jù)持久化

Redis 支持兩種持久化策略：RDB 快照和 AOF 日志，而 Memcached 不支持持久化。

分布式

Memcached 不支持分布式，只能通過在客戶端使用一致性哈希來實(shí)現(xiàn)分布式存儲(chǔ)，這種方式在存儲(chǔ)和查詢時(shí)都需要先在客戶端計(jì)算一次數(shù)據(jù)所在的節(jié)點(diǎn)。

Redis Cluster 實(shí)現(xiàn)了分布式的支持。

內(nèi)存管理機(jī)制

• 在 Redis 中，并不是所有數(shù)據(jù)都一直存儲(chǔ)在內(nèi)存中，可以將一些很久沒用的 value 交換到磁盤，而 Memcached 的數(shù)據(jù)則會(huì)一直在內(nèi)存中。

• Memcached 將內(nèi)存分割成特定長(zhǎng)度的塊來存儲(chǔ)數(shù)據(jù)，以完全解決內(nèi)存碎片的問題。但是這種方式會(huì)使得內(nèi)存的利用率不高，例如塊的大小為 128 bytes，只存儲(chǔ) 100 bytes 的數(shù)據(jù)，那么剩下的 28 bytes 就浪費(fèi)掉了。

六、鍵的過期時(shí)間

Redis 可以為每個(gè)鍵設(shè)置過期時(shí)間，當(dāng)鍵過期時(shí)，會(huì)自動(dòng)刪除該鍵。

對(duì)于散列表這種容器，只能為整個(gè)鍵設(shè)置過期時(shí)間（整個(gè)散列表），而不能為鍵里面的單個(gè)元素設(shè)置過期時(shí)間。

七、數(shù)據(jù)淘汰策略

可以設(shè)置內(nèi)存最大使用量，當(dāng)內(nèi)存使用量超出時(shí)，會(huì)施行數(shù)據(jù)淘汰策略。

Redis 具體有 6 種淘汰策略：

作為內(nèi)存數(shù)據(jù)庫，出于對(duì)性能和內(nèi)存消耗的考慮，Redis 的淘汰算法實(shí)際實(shí)現(xiàn)上并非針對(duì)所有 key，而是抽樣一小部分并且從中選出被淘汰的 key。

使用 Redis 緩存數(shù)據(jù)時(shí)，為了提高緩存命中率，需要保證緩存數(shù)據(jù)都是熱點(diǎn)數(shù)據(jù)?？梢詫?nèi)存最大使用量設(shè)置為熱點(diǎn)數(shù)據(jù)占用的內(nèi)存量，然后啟用 allkeys-lru 淘汰策略，將最近最少使用的數(shù)據(jù)淘汰。

Redis 4.0 引入了 volatile-lfu 和 allkeys-lfu 淘汰策略，LFU 策略通過統(tǒng)計(jì)訪問頻率，將訪問頻率最少的鍵值對(duì)淘汰。

八、持久化

Redis 是內(nèi)存型數(shù)據(jù)庫，為了保證數(shù)據(jù)在斷電后不會(huì)丟失，需要將內(nèi)存中的數(shù)據(jù)持久化到硬盤上。

RDB 持久化

將某個(gè)時(shí)間點(diǎn)的所有數(shù)據(jù)都存放到硬盤上。

可以將快照復(fù)制到其它服務(wù)器從而創(chuàng)建具有相同數(shù)據(jù)的服務(wù)器副本。

如果系統(tǒng)發(fā)生故障，將會(huì)丟失最后一次創(chuàng)建快照之后的數(shù)據(jù)。

如果數(shù)據(jù)量很大，保存快照的時(shí)間會(huì)很長(zhǎng)。

AOF 持久化

將寫命令添加到 AOF 文件（Append Only File）的末尾。

使用 AOF 持久化需要設(shè)置同步選項(xiàng)，從而確保寫命令什么時(shí)候會(huì)同步到磁盤文件上。這是因?yàn)閷?duì)文件進(jìn)行寫入并不會(huì)馬上將內(nèi)容同步到磁盤上，而是先存儲(chǔ)到緩沖區(qū)，然后由操作系統(tǒng)決定什么時(shí)候同步到磁盤。有以下同步選項(xiàng)：

• always 選項(xiàng)會(huì)嚴(yán)重減低服務(wù)器的性能；

• everysec 選項(xiàng)比較合適，可以保證系統(tǒng)崩潰時(shí)只會(huì)丟失一秒左右的數(shù)據(jù)，并且 Redis 每秒執(zhí)行一次同步對(duì)服務(wù)器性能幾乎沒有任何影響；

• no 選項(xiàng)并不能給服務(wù)器性能帶來多大的提升，而且也會(huì)增加系統(tǒng)崩潰時(shí)數(shù)據(jù)丟失的數(shù)量。

隨著服務(wù)器寫請(qǐng)求的增多，AOF 文件會(huì)越來越大。Redis 提供了一種將 AOF 重寫的特性，能夠去除 AOF 文件中的冗余寫命令。

九、事務(wù)

一個(gè)事務(wù)包含了多個(gè)命令，服務(wù)器在執(zhí)行事務(wù)期間，不會(huì)改去執(zhí)行其它客戶端的命令請(qǐng)求。

事務(wù)中的多個(gè)命令被一次性發(fā)送給服務(wù)器，而不是一條一條發(fā)送，這種方式被稱為流水線，它可以減少客戶端與服務(wù)器之間的網(wǎng)絡(luò)通信次數(shù)從而提升性能。

Redis 最簡(jiǎn)單的事務(wù)實(shí)現(xiàn)方式是使用 MULTI 和 EXEC 命令將事務(wù)操作包圍起來。

十、事件

Redis 服務(wù)器是一個(gè)事件驅(qū)動(dòng)程序。

文件事件

服務(wù)器通過套接字與客戶端或者其它服務(wù)器進(jìn)行通信，文件事件就是對(duì)套接字操作的抽象。

Redis 基于 Reactor 模式開發(fā)了自己的網(wǎng)絡(luò)事件處理器，使用 I/O 多路復(fù)用程序來同時(shí)監(jiān)聽多個(gè)套接字，并將到達(dá)的事件傳送給文件事件分派器，分派器會(huì)根據(jù)套接字產(chǎn)生的事件類型調(diào)用相應(yīng)的事件處理器。

時(shí)間事件

服務(wù)器有一些操作需要在給定的時(shí)間點(diǎn)執(zhí)行，時(shí)間事件是對(duì)這類定時(shí)操作的抽象。

時(shí)間事件又分為：

• 定時(shí)事件：是讓一段程序在指定的時(shí)間之內(nèi)執(zhí)行一次；

• 周期性事件：是讓一段程序每隔指定時(shí)間就執(zhí)行一次。

Redis 將所有時(shí)間事件都放在一個(gè)無序鏈表中，通過遍歷整個(gè)鏈表查找出已到達(dá)的時(shí)間事件，并調(diào)用相應(yīng)的事件處理器。

事件的調(diào)度與執(zhí)行

服務(wù)器需要不斷監(jiān)聽文件事件的套接字才能得到待處理的文件事件，但是不能一直監(jiān)聽，否則時(shí)間事件無法在規(guī)定的時(shí)間內(nèi)執(zhí)行，因此監(jiān)聽時(shí)間應(yīng)該根據(jù)距離現(xiàn)在最近的時(shí)間事件來決定。

事件調(diào)度與執(zhí)行由 aeProcessEvents 函數(shù)負(fù)責(zé)，偽代碼如下：

def aeProcessEvents():
    # 獲取到達(dá)時(shí)間離當(dāng)前時(shí)間最接近的時(shí)間事件
    time_event = aeSearchNearestTimer()
    # 計(jì)算最接近的時(shí)間事件距離到達(dá)還有多少毫秒
    remaind_ms = time_event.when - unix_ts_now()
    # 如果事件已到達(dá)，那么 remaind_ms 的值可能為負(fù)數(shù)，將它設(shè)為 0
    if remaind_ms < 0:
        remaind_ms = 0
    # 根據(jù) remaind_ms 的值，創(chuàng)建 timeval
    timeval = create_timeval_with_ms(remaind_ms)
    # 阻塞并等待文件事件產(chǎn)生，最大阻塞時(shí)間由傳入的 timeval 決定
    aeApiPoll(timeval)
    # 處理所有已產(chǎn)生的文件事件
    procesFileEvents()
    # 處理所有已到達(dá)的時(shí)間事件
    processTimeEvents()

將 aeProcessEvents 函數(shù)置于一個(gè)循環(huán)里面，加上初始化和清理函數(shù)，就構(gòu)成了 Redis 服務(wù)器的主函數(shù)，偽代碼如下：

從事件處理的角度來看，服務(wù)器運(yùn)行流程如下：

十一、復(fù)制

通過使用 slaveof host port 命令來讓一個(gè)服務(wù)器成為另一個(gè)服務(wù)器的從服務(wù)器。

一個(gè)從服務(wù)器只能有一個(gè)主服務(wù)器，并且不支持主主復(fù)制。

連接過程

1. 主服務(wù)器創(chuàng)建快照文件，發(fā)送給從服務(wù)器，并在發(fā)送期間使用緩沖區(qū)記錄執(zhí)行的寫命令?？煺瘴募l(fā)送完畢之后，開始向從服務(wù)器發(fā)送存儲(chǔ)在緩沖區(qū)中的寫命令；

2. 從服務(wù)器丟棄所有舊數(shù)據(jù)，載入主服務(wù)器發(fā)來的快照文件，之后從服務(wù)器開始接受主服務(wù)器發(fā)來的寫命令；

3. 主服務(wù)器每執(zhí)行一次寫命令，就向從服務(wù)器發(fā)送相同的寫命令。

主從鏈

隨著負(fù)載不斷上升，主服務(wù)器可能無法很快地更新所有從服務(wù)器，或者重新連接和重新同步從服務(wù)器將導(dǎo)致系統(tǒng)超載。為了解決這個(gè)問題，可以創(chuàng)建一個(gè)中間層來分擔(dān)主服務(wù)器的復(fù)制工作。中間層的服務(wù)器是最上層服務(wù)器的從服務(wù)器，又是最下層服務(wù)器的主服務(wù)器。

十二、Sentinel

Sentinel（哨兵）可以監(jiān)聽集群中的服務(wù)器，并在主服務(wù)器進(jìn)入下線狀態(tài)時(shí)，自動(dòng)從從服務(wù)器中選舉出新的主服務(wù)器。

十三、分片

分片是將數(shù)據(jù)劃分為多個(gè)部分的方法，可以將數(shù)據(jù)存儲(chǔ)到多臺(tái)機(jī)器里面，這種方法在解決某些問題時(shí)可以獲得線性級(jí)別的性能提升。

假設(shè)有 4 個(gè) Redis 實(shí)例 R0，R1，R2，R3，還有很多表示用戶的鍵 user:1，user:2，... ，有不同的方式來選擇一個(gè)指定的鍵存儲(chǔ)在哪個(gè)實(shí)例中。

• 最簡(jiǎn)單的方式是范圍分片，例如用戶 id 從 0~1000 的存儲(chǔ)到實(shí)例 R0 中，用戶 id 從 1001~2000 的存儲(chǔ)到實(shí)例 R1 中，等等。但是這樣需要維護(hù)一張映射范圍表，維護(hù)操作代價(jià)很高。

• 還有一種方式是哈希分片，使用 CRC32 哈希函數(shù)將鍵轉(zhuǎn)換為一個(gè)數(shù)字，再對(duì)實(shí)例數(shù)量求模就能知道應(yīng)該存儲(chǔ)的實(shí)例。

根據(jù)執(zhí)行分片的位置，可以分為三種分片方式：

• 客戶端分片：客戶端使用一致性哈希等算法決定鍵應(yīng)當(dāng)分布到哪個(gè)節(jié)點(diǎn)。

• 代理分片：將客戶端請(qǐng)求發(fā)送到代理上，由代理轉(zhuǎn)發(fā)請(qǐng)求到正確的節(jié)點(diǎn)上。

• 服務(wù)器分片：Redis Cluster。

十四、一個(gè)簡(jiǎn)單的論壇系統(tǒng)分析

該論壇系統(tǒng)功能如下：

• 可以發(fā)布文章；

• 可以對(duì)文章進(jìn)行點(diǎn)贊；

• 在首頁可以按文章的發(fā)布時(shí)間或者文章的點(diǎn)贊數(shù)進(jìn)行排序顯示。

文章信息

文章包括標(biāo)題、作者、贊數(shù)等信息，在關(guān)系型數(shù)據(jù)庫中很容易構(gòu)建一張表來存儲(chǔ)這些信息，在 Redis 中可以使用 HASH 來存儲(chǔ)每種信息以及其對(duì)應(yīng)的值的映射。

Redis 沒有關(guān)系型數(shù)據(jù)庫中的表這一概念來將同種類型的數(shù)據(jù)存放在一起，而是使用命名空間的方式來實(shí)現(xiàn)這一功能。鍵名的前面部分存儲(chǔ)命名空間，后面部分的內(nèi)容存儲(chǔ) ID，通常使用 : 來進(jìn)行分隔。例如下面的 HASH 的鍵名為 article:92617，其中 article 為命名空間，ID 為 92617。

點(diǎn)贊功能

當(dāng)有用戶為一篇文章點(diǎn)贊時(shí)，除了要對(duì)該文章的 votes 字段進(jìn)行加 1 操作，還必須記錄該用戶已經(jīng)對(duì)該文章進(jìn)行了點(diǎn)贊，防止用戶點(diǎn)贊次數(shù)超過 1?？梢越⑽恼碌囊淹镀庇脩艏蟻磉M(jìn)行記錄。

為了節(jié)約內(nèi)存，規(guī)定一篇文章發(fā)布滿一周之后，就不能再對(duì)它進(jìn)行投票，而文章的已投票集合也會(huì)被刪除，可以為文章的已投票集合設(shè)置一個(gè)一周的過期時(shí)間就能實(shí)現(xiàn)這個(gè)規(guī)定。

對(duì)文章進(jìn)行排序

為了按發(fā)布時(shí)間和點(diǎn)贊數(shù)進(jìn)行排序，可以建立一個(gè)文章發(fā)布時(shí)間的有序集合和一個(gè)文章點(diǎn)贊數(shù)的有序集合。（下圖中的 score 就是這里所說的點(diǎn)贊數(shù)；下面所示的有序集合分值并不直接是時(shí)間和點(diǎn)贊數(shù)，而是根據(jù)時(shí)間和點(diǎn)贊數(shù)間接計(jì)算出來的）

參考資料

• Carlson J L. Redis in Action[J]. Media.johnwiley.com.au, 2013.

• 黃健宏. Redis 設(shè)計(jì)與實(shí)現(xiàn) [M]. 機(jī)械工業(yè)出版社, 2014.

• REDIS IN ACTION

• Skip Lists: Done Right

• 論述 Redis 和 Memcached 的差異

• Redis 3.0 中文版- 分片

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

• Using Redis as an LRU cache

• 出自以下公眾號(hào)
  

————  e n d ————