redis 為什么響應(yīng)快

 

①數(shù)據(jù)保存在內(nèi)存中

 

Redis 數(shù)據(jù)保存在內(nèi)存中，讀寫操作只要訪問內(nèi)存，不需要磁盤 IO。

 

②底層數(shù)據(jù)結(jié)構(gòu)

 

如下：

• Redis 的數(shù)據(jù)以 key：value 的格式存儲(chǔ)在散列表中，時(shí)間復(fù)雜度 o(1)。
• Redis 為 value 定義了豐富的數(shù)據(jù)結(jié)構(gòu)，包括動(dòng)態(tài)字符串、雙向鏈表、壓縮列表、hash、跳表和整數(shù)數(shù)組，可以根據(jù) value 的特性選擇選擇最高效的數(shù)據(jù)結(jié)構(gòu)。

 

③單線程模型

 

Redis 的網(wǎng)絡(luò) IO 和數(shù)據(jù)讀寫使用單線程模型，可以綁定 CPU，這避免了線程上下文切換帶來(lái)的開銷。

 

注意：Redis 6.0 對(duì)網(wǎng)絡(luò)請(qǐng)求引入了多線程模型，讀寫操作還是用單線程。

 

Redis 多線程網(wǎng)絡(luò)模型見下圖：

 

④IO 多路復(fù)用

 

Redis 采用 Epoll 網(wǎng)絡(luò)模型，如下圖：

 

內(nèi)核會(huì)一直監(jiān)聽新的 socket 連接事件的和已建立 socket 連接的讀寫事件，把監(jiān)聽到的事件放到事件隊(duì)列，Redis 使用單線程不停的處理這個(gè)事件隊(duì)列。這避免了阻塞等待連接和讀寫事件到來(lái)。

 

這些事件綁定了回調(diào)函數(shù)，會(huì)調(diào)用 Redis 的處理函數(shù)進(jìn)行處理。

 

Redis 底層數(shù)據(jù)結(jié)構(gòu)

 

Redis 有 5 種數(shù)據(jù)類型，包括：字符串、列表、集合、有序集合和字典。

 

Redis 底層的數(shù)據(jù)結(jié)構(gòu)有 6 種，包括：動(dòng)態(tài)字符串、雙向鏈表、壓縮列表（ziplist）、hash 表、跳表（skip list）和整數(shù)數(shù)組。

 

Redis 數(shù)據(jù)類型和底層數(shù)據(jù)結(jié)構(gòu)有如下對(duì)應(yīng)關(guān)系：

 

①字符串類型

 

底層數(shù)據(jù)結(jié)構(gòu)是動(dòng)態(tài)字符串。

 

②列表

 

如果同時(shí)滿足下面條件，就使用壓縮列表，否則使用雙向鏈表：

• 列表中單個(gè)元素小于 64 字節(jié)
• 列表中元素個(gè)數(shù)少于 512

 

壓縮列表在內(nèi)存中是一塊兒連續(xù)的內(nèi)存空間，結(jié)構(gòu)如下：

 

壓縮列表查找時(shí)間復(fù)雜度是 o(n)。

 

③集合

 

如果同時(shí)滿足下面條件，就使用有序整數(shù)數(shù)組，否則使用 hash 表：

• 集合中元素都是整數(shù)類型
• 集合中元素個(gè)數(shù)不超過 512 個(gè)

 

④有序集合

 

如果同時(shí)滿足下面 2 個(gè)條件，就使用壓縮列表，否則使用跳表：

• 集合中元素都小于 64 字節(jié)
• 集合中元素個(gè)數(shù)小于 128 個(gè)

 

注意：有序集合還有一個(gè) HASH 表用于保存集合中元素的分?jǐn)?shù)，做 ZSCORE 操作時(shí)，查詢的就是這個(gè) HASH 表，所以效率很高。

 

跳表的結(jié)構(gòu)如下：

 

如果不加索引，查找 10 這個(gè)數(shù)字需要查詢 10 次，使用了二級(jí)索引，查找 10 這個(gè)數(shù)字需要 5 次，而使用一級(jí)索引，需要查詢 3 次。

 

跳表的每一層都是一個(gè)有序鏈表，最下面一層保存了全部數(shù)據(jù)。跳表插入、刪除、查詢的時(shí)間復(fù)雜度是 o(logN)。跳表需要存儲(chǔ)額外的索引節(jié)點(diǎn)，會(huì)增加額外的空間開銷。

 

⑤字典

 

如果同時(shí)滿足下面 2 個(gè)條件，就使用壓縮列表，否則使用 hash 表：

• 字典中每個(gè) entry 的 key/value 都小于 64 字節(jié)
• 字典中元素個(gè)數(shù)小于 512 個(gè)

 

Redis 緩存淘汰策略

 

Redis 總共有 8 種淘汰策略，如下圖：

 

volatile-lfu 和 allkeys-lfu 策略是 4.0 版本新增的：

• lru：是按照數(shù)據(jù)的最近最少訪問原則來(lái)淘汰數(shù)據(jù)，可能存在的問題是如果大批量冷數(shù)據(jù)最近被訪問了一次，就會(huì)占用大量?jī)?nèi)存空間，如果緩存滿了，部分熱數(shù)據(jù)就會(huì)被淘汰掉。
• lfu：是按照數(shù)據(jù)的最小訪問頻率訪問次數(shù)原則來(lái)淘汰數(shù)據(jù)，如果兩個(gè)數(shù)據(jù)的訪問次數(shù)相同，則把訪問時(shí)間較早的數(shù)據(jù)淘汰。

 

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

 

Redis 持久化的方式有 2 種，一種是寫后日志（AOF），一種是內(nèi)存快照（RDB）。

 

①AOF 日志

 

AOF 日志記錄了每一條收到的命令，Redis 故障宕機(jī)恢復(fù)時(shí)，可以加載 AOF 日志中的命令進(jìn)行重放來(lái)進(jìn)行故障恢復(fù)。

 

AOF 有 3 種同步策略，如下圖：

 

如果不是對(duì)丟失數(shù)據(jù)特別敏感的業(yè)務(wù)，推薦使用 everysec，對(duì)主線程的阻塞少，故障后丟失數(shù)據(jù)只有 1s。

 

②RDB 快照

 

RDB 快照是一個(gè)內(nèi)存快照，記錄了 Redis 某一時(shí)刻的全部數(shù)據(jù)。

 

③混合日志

 

從 Redis 4.0 開始，AOF 文件也可以保存 RDB 快照，AOF 重寫的時(shí)候 Redis 會(huì)把 AOF 文件內(nèi)容清空，先記錄一份 RDB 快照，這份數(shù)據(jù)以"REDIS"開頭。

 

記錄 RDB 內(nèi)容后，AOF 文件會(huì)接著記錄 AOF 命令。故障恢復(fù)時(shí)，先加載 AOF 文件中 RDB 快照，然后回放 AOF 文件中后面的命令。

 

④主從同步

 

Redis 主從同步時(shí)，主節(jié)點(diǎn)會(huì)先生成一份 RDB 快照發(fā)送給從節(jié)點(diǎn)，把快照之后的命令寫入主從同步緩存區(qū)（replication buffer），從節(jié)點(diǎn)把 RDB 文件加載完成后，主節(jié)點(diǎn)把緩存區(qū)命令發(fā)送給從節(jié)點(diǎn)。

 

⑤AOF 重寫

 

AOF 日志是用記錄命令的方式追加的，這樣可能存在對(duì)同一個(gè) key 的多條命令，這些命令是可以合并成 1 條的。比如對(duì)同一個(gè) key 的多個(gè) set 操作日志，可以合成一條。

 

⑥阻塞點(diǎn)

 

AOF 重寫和 RDB 快照?qǐng)?zhí)行的過程中，Redis 都會(huì) Fork 一個(gè)子進(jìn)程來(lái)執(zhí)行操作，子進(jìn)程執(zhí)行過程中是不是阻塞主線程的。

 

但是要注意 2 點(diǎn)：

• Fork 子進(jìn)程的過程中，Redis 主線程會(huì)拷貝一份內(nèi)存頁(yè)表（記錄了虛擬內(nèi)存和物理內(nèi)存的映射關(guān)系）給子進(jìn)程，這個(gè)過程是阻塞的，Redis 主線程內(nèi)存越大，阻塞時(shí)間越長(zhǎng)。
• 子進(jìn)程和 Redis 主線程共用一塊兒物理內(nèi)存，如果新的請(qǐng)求到來(lái)，必須使用 copy on write 的方式，拷貝要修改的數(shù)據(jù)頁(yè)到新的內(nèi)存空間進(jìn)行修改。如下圖：

 

注意：如果開啟了內(nèi)存大頁(yè)，每次拷貝都需要分配 2MB 的內(nèi)存。

 

Redis 高可用

 

下圖是一個(gè)“一主二從三哨兵”的架構(gòu)圖：

 

從圖我們可以看到哨兵之間、哨兵和主從節(jié)點(diǎn)之間、哨兵和客戶端之間都建立了連接。

 

如果主節(jié)點(diǎn)掛了，哨兵集群需要完成主從切換，如下圖：

 

下面我們依次來(lái)聊一下這 4 個(gè)步驟。

 

①判斷主節(jié)點(diǎn)下線

 

當(dāng)一個(gè)哨兵監(jiān)控到主節(jié)點(diǎn)下線時(shí)，就會(huì)給其他哨兵發(fā)送確認(rèn)命令，其他命令會(huì)根據(jù)自己的判斷回復(fù)"Y"或"N"。

 

如果有 n/2+1 以上數(shù)量的哨兵都認(rèn)為主節(jié)點(diǎn)下線了，才會(huì)判定主節(jié)點(diǎn)下線。這里的n是哨兵集群的數(shù)量。

 

n/2+1 這個(gè)參數(shù)由 quorum 參數(shù)配置，比如有 5 個(gè)哨兵，這里一般配置成 3。也可以配置成其他值。

 

②選舉新主節(jié)點(diǎn)

 

主節(jié)點(diǎn)被判定下線后，哨兵集群會(huì)重新選擇新的主節(jié)點(diǎn)。

 

淘汰不穩(wěn)定從節(jié)點(diǎn)：根據(jù)配置參數(shù) down-after-milliseconds * 10 來(lái)淘汰。

 

down-after-milliseconds 表示主從節(jié)點(diǎn)斷開時(shí)間，10 表示次數(shù)，如果從節(jié)點(diǎn)跟主節(jié)點(diǎn)斷開時(shí)間超過 down-after-milliseconds 的次數(shù)達(dá)到了 10 次以上，從節(jié)點(diǎn)就被淘汰了。

 

slave-priority 參數(shù)：配置了從節(jié)點(diǎn)的優(yōu)先級(jí)，選擇從節(jié)點(diǎn)時(shí)哨兵會(huì)優(yōu)先選擇優(yōu)先級(jí)高的從節(jié)點(diǎn)。

 

復(fù)制進(jìn)度：Redis 有一個(gè)記錄主從增量復(fù)制的緩存區(qū)叫 repl_backlog_buffer。

 

這是一個(gè)環(huán)形結(jié)構(gòu)的緩沖區(qū)，如下圖：

 

主節(jié)點(diǎn)有一個(gè)寫偏移量 master_repl_offset，從節(jié)點(diǎn)也有一個(gè)偏移量 slave_repl_offset。

 

優(yōu)先選擇 slave_repl_offset 最接近 master_repl_offset 的從節(jié)點(diǎn)作為新的主節(jié)點(diǎn)。

 

所以，上圖中偏移量為 114 的從節(jié)點(diǎn)優(yōu)先被選為新的主節(jié)點(diǎn)。

 

ID 編號(hào)：優(yōu)先級(jí)和參數(shù)都一樣的情況下，ID 編號(hào)小的從節(jié)點(diǎn)優(yōu)先被選為新主節(jié)點(diǎn)。

 

③選舉哨兵 Leader

 

第一個(gè)判斷主節(jié)點(diǎn)下線的哨兵節(jié)點(diǎn)收到其他節(jié)點(diǎn)的回復(fù)并確定主節(jié)點(diǎn)下線后，就會(huì)給其他哨兵發(fā)送命令申請(qǐng)成為哨兵 Leader。

 

成為 Leader 的條件如下：

• 收到贊成票必須大于等 quorum 值
• 必須拿到半數(shù)以上的贊成票

 

如果集群配置了 5 個(gè)哨兵，quorum 的值設(shè)置為 3，其中一個(gè)哨兵節(jié)點(diǎn)掛了，很有可能會(huì)判斷到主節(jié)點(diǎn)下線，但是因?yàn)檫x舉不出哨兵 Leader 而不能切換。

 

如果集群有 2 個(gè)哨兵，其中一個(gè)掛了，那必定選不出哨兵 Leader。

 

下面的圖展示了哨兵一成功當(dāng)選 Leader 的過程：

 

④主節(jié)點(diǎn)切換

 

選出新主節(jié)點(diǎn)和哨兵 Leader 后，哨兵 Leader 會(huì)執(zhí)行主從切換的操作。

 

完成后會(huì)做一些事件通知：

• 通知其他哨兵新主節(jié)點(diǎn)地址
• 通知所有從節(jié)點(diǎn)新的主節(jié)點(diǎn)地址，從節(jié)點(diǎn)收到后向新主節(jié)點(diǎn)請(qǐng)求主從同步
• 通知客戶端連接新主節(jié)點(diǎn)

 

⑤主從切換過程中請(qǐng)求處理

 

如果客戶端的讀請(qǐng)求會(huì)發(fā)送到從節(jié)點(diǎn)，可以正常處理。在客戶端收到新主節(jié)點(diǎn)地址通知前寫請(qǐng)求會(huì)失敗。客戶端可以采取一些應(yīng)急措施應(yīng)對(duì)主節(jié)點(diǎn)下線，比如緩存寫請(qǐng)求。

 

為了能夠及時(shí)獲取到新主節(jié)點(diǎn)信息，客戶端可以訂閱哨兵的主節(jié)點(diǎn)下線事件和新主節(jié)點(diǎn)變更事件。

 

Redis 為什么變慢了

 

Redis 變慢了的原因有很多，總結(jié)一下有 11 個(gè)，見下圖：

 

從圖中看出，Redis 變慢原因主要有兩類：阻塞主線程和操作系統(tǒng)限制。

 

①主線程阻塞

 

AOF 重寫和 RDB 快照：前面已經(jīng)講過了，Redis 在 AOF 重寫時(shí)，主線程會(huì) Fork 出一個(gè) bgrewriteaof 子進(jìn)程。Redis 進(jìn)行 RDB 快照時(shí)主線程會(huì) Fork 出一個(gè) bgsave 子進(jìn)程。

 

這兩個(gè)操作表面上看不阻塞主線程，但 Fork 子進(jìn)程的這個(gè)過程是在主線程完成的。

 

Fork 子進(jìn)程時(shí) Redis 需要拷貝內(nèi)存頁(yè)表，如果 Redis 實(shí)例很大，這個(gè)拷貝會(huì)耗費(fèi)大量的 CPU 資源，阻塞主線程的時(shí)間也會(huì)變長(zhǎng)。

 

內(nèi)存大頁(yè)：Redis 默認(rèn)支持內(nèi)存大頁(yè)是 2MB，使用內(nèi)存大頁(yè)，一定程度上可以減少 Redis 的內(nèi)存分配次數(shù)，但是對(duì)數(shù)據(jù)持久化會(huì)有一定影響。

 

Redis 在 AOF 重寫和 RDB 快照過程中，如果主線程收到新的寫請(qǐng)求，就需要 CopyOnWrite。

 

使用了內(nèi)存大頁(yè)，即使 Redis 只修改其中一個(gè)大小是 1kb 的 key，也需要拷貝一整頁(yè)的數(shù)據(jù)，即 2MB。在寫入量較多時(shí)，大量拷貝就會(huì)導(dǎo)致 Redis 性能下降。

 

命令復(fù)雜度高：執(zhí)行復(fù)雜度高的命令是造成 Redis 阻塞的常見原因。比如對(duì)一個(gè) set 或者 list 數(shù)據(jù)類型執(zhí)行 SORT 操作，復(fù)雜度是 O(N+M*log(M))。

 

bigkey 操作：如果一個(gè) key 的 value 非常大，創(chuàng)建的時(shí)候分配內(nèi)存會(huì)很耗時(shí)，刪除的時(shí)候釋放內(nèi)存也很耗時(shí)。

 

Redis 4.0 以后引入了 layfree 機(jī)制，可以使用子進(jìn)程異步刪除，從而不影響主線程執(zhí)行。用 UNLINK 命令替代 DEL 命令，就可以使用子進(jìn)程異步刪除。

 

Redis 6.0 增加了配置項(xiàng) lazyfree-lazy-user-del，配置成 yes 后，del 命令也可以用子進(jìn)程異步刪除。

 

如果 lazyfree-lazy-user-del 不設(shè)置為 yes，那 Redis 是否采用異步刪除，是要看刪除的時(shí)機(jī)的。

 

對(duì)于 String 類型和底層采用整數(shù)數(shù)組和壓縮列表的數(shù)據(jù)類型，Redis 是不會(huì)采用異步刪除的。

 

從節(jié)點(diǎn)全量同步：從節(jié)點(diǎn)全量同步過程中，需要先清除內(nèi)存中的數(shù)據(jù)，然后再加載 RDB 文件，這個(gè)過程中是阻塞的，如果有讀請(qǐng)求到來(lái)，只能等到加載 RDB 文件完成后才能處理請(qǐng)求，所以響應(yīng)會(huì)很慢。

 

另外，如果 Redis 實(shí)例很大，也會(huì)造成 RDB 文件太大，從庫(kù)加載時(shí)間長(zhǎng)。所以盡量保持 Redis 實(shí)例不要太大，比如單個(gè)實(shí)例限制 4G，如果超出就采用切片集群。

 

AOF 同步寫盤：Appendfsync 策略有 3 種：always、everysec、no，如果采用 always，每個(gè)命令都會(huì)同步寫盤，這個(gè)過程是阻塞的，等寫盤成功后才能處理下一條命令。

 

除非是嚴(yán)格不能丟數(shù)據(jù)的場(chǎng)景，否則盡量不要選擇 always 策略，推薦盡量選擇 everysec 策略，如果對(duì)丟失數(shù)據(jù)不敏感，可以采用 no。

 

內(nèi)存達(dá)到 maxmemory：需要使用淘汰策略來(lái)淘汰部分 key。即使采用 lazyfree 異步刪除，選擇 key 的過程也是阻塞的。

 

可以選擇較快的淘汰策略，比如用隨機(jī)淘汰來(lái)替換 LRU 和 LFU 算法淘汰。也可以擴(kuò)大切片數(shù)量來(lái)減輕淘汰 key 的時(shí)間消耗。

 

②操作系統(tǒng)限制

 

使用了 swap：使用 swap 的原因是操作系統(tǒng)不能給 Redis 分配足夠大的內(nèi)存，如果操作其他開啟了 swap，內(nèi)存數(shù)據(jù)就需要不停地跟 swap 換入和換出，對(duì)性能影響非常大。

 

操作系統(tǒng)沒有能力分配內(nèi)存的原因也可能是其他進(jìn)程使用了大量的內(nèi)存。

 

網(wǎng)絡(luò)問題：如果網(wǎng)卡負(fù)載很大，對(duì) Redis 性能影響會(huì)很大。這一方面有可能 Redis 的訪問量確實(shí)很高，另一方面也可能是有其他流量大的程序占用了帶寬。

這個(gè)最好從運(yùn)維層面進(jìn)行監(jiān)控。

 

線程上下文切換：Redis 雖然是單線程的，但是在多核 CPU 的情況下，也可能會(huì)發(fā)生上下文切換。

 

如果主線程從一個(gè)物理核切換到了另一個(gè)物理核，那就不能使用 CPU 高效的一級(jí)緩存和二級(jí)緩存了。

 

如下圖所示：

 

為防止這種情況，可以把 Redis 綁定到一個(gè) CPU 物理核。

 

磁盤性能低：對(duì)于 AOF 同步寫盤的使用場(chǎng)景，如果磁盤性能低，也會(huì)影響 Redis 的響應(yīng)。可以優(yōu)先采用性能更好的 SSD 硬盤。

 

設(shè)計(jì)排行榜功能

 

Redis 的 zset 類型保存了分?jǐn)?shù)值，可以方便的實(shí)現(xiàn)排行榜的功能。

 

比如要統(tǒng)計(jì) 10 篇文章的排行榜，可以先建立一個(gè)存放 10 篇文章的 zset，每當(dāng)有讀者閱讀一篇文章時(shí)，就用 ZINCRBY 命令給這篇文章的分?jǐn)?shù)加 1，最后可以用 range 命令統(tǒng)計(jì)排行榜前幾位的文章。

 

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

 

①Redis 單節(jié)點(diǎn)的分布式鎖

 

如下圖，一個(gè)服務(wù)部署了 2 個(gè)客戶端，獲取分布式鎖時(shí)一個(gè)成功，另一個(gè)就失敗了。

 

Redis 一般使用 setnx 實(shí)現(xiàn)分布式鎖，命令如下：

SETNX KEY_NAME VALUE

設(shè)置成功返回 1，設(shè)置失敗返回 0。使用單節(jié)點(diǎn)分布式鎖存在一些問題。

 

客戶端 1 獲取鎖后發(fā)生了故障：結(jié)果鎖就不能釋放了，其他客戶端永遠(yuǎn)獲取不到鎖。

 

解決方法是用下面命令對(duì) key 設(shè)置過期時(shí)間：

SET key value [EX seconds] [PX milliseconds] NX

 

客戶端 2 誤刪除了鎖：解決方法是對(duì) key 設(shè)置 value 時(shí)加入一個(gè)客戶端表示，比如在客戶端 1 設(shè)置 key 時(shí)在 value 前拼接一個(gè)字符串 application1，刪除的時(shí)候做一下判斷。

 

②Redis 紅鎖

 

Redis 單節(jié)點(diǎn)會(huì)有可靠性問題，節(jié)點(diǎn)故障后鎖操作就會(huì)失敗。Redis 為了應(yīng)對(duì)單點(diǎn)故障的問題，設(shè)計(jì)了多節(jié)點(diǎn)的分布式鎖，也叫紅鎖。

 

主要思想是客戶端跟多個(gè) Redis 實(shí)例請(qǐng)求加鎖，只有超過半數(shù)的實(shí)例加鎖成功，才認(rèn)為成功獲取了分布式鎖。

 

如下圖，客戶端分別跟 3 個(gè)實(shí)例請(qǐng)求加鎖，有 2 個(gè)實(shí)例加鎖成功，所以獲取分布式鎖成功：

 

緩存雪崩、擊穿、穿透

 

①緩存雪崩

 

Redis 做緩存時(shí)，如果同一時(shí)間大量緩存數(shù)據(jù)失效，客戶端請(qǐng)求會(huì)大量發(fā)送到數(shù)據(jù)庫(kù)，導(dǎo)致數(shù)據(jù)庫(kù)壓力激增。

 

如下圖：

 

應(yīng)對(duì)方法主要有 3 個(gè)：

• 給 key 設(shè)置過期時(shí)間時(shí)加一個(gè)小的隨機(jī)數(shù)
• 限流
• 服務(wù)降級(jí)

 

②緩存擊穿

 

某個(gè)熱點(diǎn) key，突然過期了，大量請(qǐng)求發(fā)送到了數(shù)據(jù)庫(kù)。解決方案是給熱點(diǎn) key 不設(shè)置過期時(shí)間。

 

③緩存穿透

 

某個(gè)熱點(diǎn) key，查詢緩存和查詢數(shù)據(jù)庫(kù)都沒有，就發(fā)生了緩存穿透。

 

如下圖：

 

應(yīng)對(duì)方法主要有 2 個(gè)：

• 緩存熱點(diǎn)的空值和缺省值
• 查詢數(shù)據(jù)庫(kù)之前先查詢布隆過濾器

 

數(shù)據(jù)傾斜

 

什么是數(shù)據(jù)傾斜？看下面這個(gè)面試題：如果 Redis 有一個(gè)熱點(diǎn) key，QPS 能達(dá)到 100w，該如何存儲(chǔ)？

 

如果這個(gè)熱點(diǎn) key 被放到一個(gè) Redis 實(shí)例上，這個(gè)實(shí)例面臨的訪問壓力會(huì)非常大。

 

如下圖，redis3 這個(gè)實(shí)例保存了 foo 這個(gè)熱點(diǎn) key，訪問壓力會(huì)很大：

 

解決方法主要有兩個(gè)：

 

①使用客戶端本地緩存來(lái)緩存 key。

 

這樣改造會(huì)有兩個(gè)問題：

• 客戶端緩存的熱點(diǎn) key 可能消耗大量?jī)?nèi)存。
• 客戶端需要保證本地緩存和 Redis 緩存的一致性。

 

②給熱點(diǎn) key 加一個(gè)隨機(jī)前綴，讓它保存到不同的 Redis 實(shí)例上。

 

這樣也會(huì)存在兩個(gè)問題：

• 客戶端在訪問的時(shí)候需要給這個(gè) key 加前綴
• 客戶端在刪除的時(shí)候需要根據(jù)所有前綴來(lái)刪除不同實(shí)例上保存的這個(gè) key

 

Bitmap 使用

 

有一道經(jīng)典的面試題，10 億整數(shù)怎么在內(nèi)存中去重排序？

 

我們先算一下 10 億整數(shù)占的內(nèi)存，JAVA 一個(gè)整數(shù)類型占四字節(jié)，占用內(nèi)存大小約：

10億 * 4 / 1024 / 1024 = 3.7G

 

占得內(nèi)存太大了，如果內(nèi)存不夠，怎么辦呢？

 

①Bitmap 介紹

 

Bitmap 類型使用的數(shù)據(jù)結(jié)構(gòu)是 String，底層存儲(chǔ)格式是二進(jìn)制的 bit 數(shù)組。假如我們有 1、4、6、9 四個(gè)數(shù)，保存在 bit 數(shù)組中如下圖：

 

在這個(gè) bit 數(shù)組中用 10 個(gè) bit 的空間保存了四個(gè)整數(shù)，占用空間非常小。

 

再回到面試題，我們使用 bit 數(shù)組長(zhǎng)度是 10 億整數(shù)中 （最大值-最小值+1）。

 

如果有負(fù)數(shù)，需要進(jìn)行一個(gè)轉(zhuǎn)化，所有數(shù)字加最小負(fù)數(shù)的絕對(duì)值。比如 {-2, 0, 1, 3}，我們轉(zhuǎn)換成 {0, 2, 3, 5}，因?yàn)閿?shù)組下標(biāo)必須從 0 開始。

 

②使用場(chǎng)景

 

員工打卡記錄：在一個(gè)有 100 個(gè)員工的公司，要統(tǒng)計(jì)一個(gè)月內(nèi)員工全勤的人數(shù)，可以每天創(chuàng)建一個(gè) Bitmap，簽到的員工 bit 位置為 1。

 

要統(tǒng)計(jì)當(dāng)天簽到的員工只要用 BITCOUNT 命令就可以。

 

要統(tǒng)計(jì)當(dāng)月全勤的員工，只要對(duì)當(dāng)月每天的 Bitmap 做交集運(yùn)算就可以。

 

命令如下：

BITOP AND srckey1 srckey2 srckey3 ... srckey30

 

srckeyN 表示第 N 天的打卡記錄 Bitmap。

 

統(tǒng)計(jì)網(wǎng)站日活躍用戶：比如網(wǎng)站有 10 萬(wàn)個(gè)用戶，這樣我們創(chuàng)建一個(gè)長(zhǎng)度為 10 萬(wàn)的 Bitmap，每個(gè)用戶 id 占一個(gè)位，如果用戶登錄，就把 bit 位置為 1，日終的時(shí)候用 BITCOUNT 命令統(tǒng)計(jì)出當(dāng)天登錄過的用戶總數(shù)。

 

作者：jinjunzhu

編輯：陶家龍

出處：轉(zhuǎn)載自公眾號(hào)程序員jinjunzhu