面试必会系列 - 3.1 Redis知识点大汇总（数据类型，内存模型，持久化，缓存击穿，集群，一致性哈希等等）
本文已收錄至 Github（MD-Notes），若博客中圖片模糊或打不開，可以來我的 Github 倉庫，包含了完整圖文：https://github.com/HanquanHq/MD-Notes，涵蓋了互聯(lián)網(wǎng)大廠面試必問的知識點，講解透徹，長期更新中，歡迎一起學習探討 ~
更多內(nèi)容，可以訪問：
面試必會系列專欄：https://blog.csdn.net/sinat_42483341/category_10300357.html
操作系統(tǒng)系列專欄：https://blog.csdn.net/sinat_42483341/category_10519484.html
目錄
- Redis
- 常問問題
- Redis 五種基本數(shù)據(jù)結(jié)構(gòu)
- 1、字符串 string
- 2、列表 list
- 3、字典 hash
- 4、集合 set
- 5、有序集合 zset
- 內(nèi)存模型
- 數(shù)據(jù)類型
- 使用
- 在 Java 中的 API 使用
- 持久化
- RDB
- AOF
- 緩存常見問題
- 緩存擊穿
- 緩存穿透
- 緩存雪崩
- 緩存一致性（雙寫問題）
- Redis 集群
- AKF 拆分原則
- 拆分之后，怎么知道數(shù)據(jù)存在哪臺機器了？去哪里取數(shù)據(jù)？
- AKF 存在的問題：CAP定理
- 集群一般使用奇數(shù)臺
- Sentinel 哨兵
- 一致性哈希
- 普通的哈希算法存在的問題：
- 一致性哈希算法的優(yōu)點
- hash環(huán)的偏斜
- 虛擬節(jié)點
Redis
常問問題
采用單工作 worker 線程，6.x 版本有多 IO threads（Tomcat，Netty 也有 IO threads）；
Redis 二進制安全：自身不會做編解碼，不會變化你的數(shù)據(jù)，你在客戶端要提供二進制的字節(jié)數(shù)組，不同客戶端之間要統(tǒng)一編碼。Zookeeper，HBase，Kafka 都是二進制安全的。
Redis 天生單線程，多 server 共同請求時，不需要加鎖。缺點：不能充分發(fā)揮服務(wù)器核數(shù)，所以進行了 IO/計算隔離，增加多個 IO 線程，worker 還是單線程。
聊：持久化 -> 同步 -> 集群 -> 中間件（分布式，ES…）讓對方覺得你的技術(shù)棧非常豐富
技術(shù)選型：Redis，memcached 怎么選擇？Redis 相比 memcached，計算向數(shù)據(jù)移動；支持模塊化，如布隆過濾器，也可以自己C++開發(fā)更多的數(shù)據(jù)類型
Redis 五種基本數(shù)據(jù)結(jié)構(gòu)
string(字符串)、list(列表)、hash(字典)、set(集合) 和 zset(有序集合)
1、字符串 string
Redis 中的字符串是一種 動態(tài)字符串，這意味著使用者可以修改，它的底層實現(xiàn)有點類似于 Java 中的 ArrayList，有一個字符數(shù)組，從源碼的 sds.h/sdshdr 文件 中可以看到 Redis 底層對于字符串的定義 SDS，即 Simple Dynamic String 結(jié)構(gòu)。
我們通常使用 SET 和 GET 來設(shè)置和獲取字符串值。
Redis 規(guī)定了字符串的長度不得超過 512 MB。
2、列表 list
相當于 Java 語言中的 LinkedList，注意它是鏈表而不是數(shù)組。這意味著 list 的插入和刪除操作非常快，時間復(fù)雜度為 O(1)，但是索引定位很慢，時間復(fù)雜度為 O(n)。
基本操作
- LPUSH 和 RPUSH 分別可以向 list 的左邊（頭部）和右邊（尾部）添加一個新元素；
- LRANGE 命令可以從 list 中取出一定范圍的元素；
- LINDEX 命令可以從 list 中取出指定下表的元素，相當于 Java 鏈表操作中的 get(int index) 操作；
3、字典 hash
Redis 中的字典相當于 Java 中的 HashMap，內(nèi)部實現(xiàn)也差不多類似，都是通過 “數(shù)組 + 鏈表” 的鏈地址法來解決部分 哈希沖突，同時這樣的結(jié)構(gòu)也吸收了兩種不同數(shù)據(jù)結(jié)構(gòu)的優(yōu)點。
4、集合 set
Redis 的集合相當于 Java 語言中的 HashSet，它內(nèi)部的鍵值對是無序、唯一的。它的內(nèi)部實現(xiàn)相當于一個特殊的字典，字典中所有的 value 都是一個值 NULL。
5、有序集合 zset
這可能使 Redis 最具特色的一個數(shù)據(jù)結(jié)構(gòu)了，它類似于 Java 中 SortedSet 和 HashMap 的結(jié)合體，一方面它是一個 set，保證了內(nèi)部 value 的唯一性，另一方面它可以為每個 value 賦予一個 score 值，用來代表排序的權(quán)重。
它的內(nèi)部實現(xiàn)用的是一種叫做 「跳躍表」 的數(shù)據(jù)結(jié)構(gòu)，由于比較復(fù)雜，所以在這里簡單提一下原理就好了：
想象你是一家創(chuàng)業(yè)公司的老板，剛開始只有幾個人，大家都平起平坐。后來隨著公司的發(fā)展，人數(shù)越來越多，團隊溝通成本逐漸增加，漸漸地引入了組長制，對團隊進行劃分，于是有一些人又是員工又有組長的身份。
再后來，公司規(guī)模進一步擴大，公司需要再進入一個層級：部門。于是每個部門又會從組長中推舉一位選出部長。
跳躍表就類似于這樣的機制，最下面一層所有的元素都會串起來，都是員工，然后每隔幾個元素就會挑選出一個代表，再把這幾個代表使用另外一級指針串起來。然后再在這些代表里面挑出二級代表，再串起來。最終形成了一個金字塔的結(jié)構(gòu)。
想一下你目前所在的地理位置：亞洲 > 中國 > 某省 > 某市 > …，就是這樣一個結(jié)構(gòu)！
內(nèi)存模型
- epoll
- Nginx 也用了 epoll
- fd
- 紅黑樹
-
零拷貝
-
sendfile
-
mmap
-
epoll 源碼沒有用到 mmap，epoll 用的是紅黑樹和雙端鏈表，是 redis 用到了 mmap
-
理解為：我們使用 epoll 的時候要注意用 mmap 輔助，來避免 read/write 多一次拷貝，而非系統(tǒng)內(nèi)核幫你維護了 mmap
-
編譯器將 epoll_create 編譯為了 int 80 中斷等一系列匯編指令，交給CPU就行了。C代碼中雖然是顯式調(diào)用 epoll_create ，但C翻譯成匯編的時候就翻譯成了相應(yīng)的0x80中斷以及相關(guān)指令的
-
-
數(shù)據(jù)類型
- string
- bitmap：可以做布隆過濾器
- list
- hashmap
- set
- sorted_set（zsest）
- 排序的實現(xiàn)：跳躍表
使用
-
管道
(printf "PING\r\nPING\r\nPING\r\n"; sleep 1) | nc localhost 6379- 只用了一個命令的開銷時間
- 服務(wù)器將被迫回復(fù)一個隊列答復(fù)
-
發(fā)布/訂閱 pubsub
- 發(fā)送者 publish test1 hello
- 訂閱者 subscribe test1
- 場景：聊天室，啟動多個 redis 去接收訂閱消息
- redis1：將消息實時推送給用戶
- redis2：存入 zset，用來取某個時間窗口的歷史消息
- redis3：啟一個 service ，將最新消息推給 kafka，然后異步存入db
-
事務(wù)
- 無論誰先開啟事務(wù)，exec命令先到達的client，事務(wù)先被執(zhí)行
- watch 某個 key，如果發(fā)生更改，事務(wù)不執(zhí)行
-
布隆過濾器
- RedisBloom模塊
- 用小空間解決大量數(shù)據(jù)匹配，避免緩存穿透
- 有一定的誤判率
布隆過濾器升級版
- Counting Bloom Filter
- 布谷鳥過濾器
在 Java 中的 API 使用
- 使用 Jedis 連接 Redis 客戶端
- google 的布隆過濾器 BloomFilter，需要定義好預(yù)估數(shù)據(jù)量的大小和誤差率
- 布隆過濾器的其他使用場景：爬蟲（防止重復(fù)爬取網(wǎng)頁），推薦系統(tǒng)（防止重復(fù)推送內(nèi)容 ）
持久化
默認開啟 RDB + AOF 混合使用。為什么做緩存還要持久化？這樣避免你重啟之后Redis空了，導(dǎo)致請求全部穿透到數(shù)據(jù)庫。
RDB
save 900 1 save 300 10 save 60 10000dbfilename dump.rdb dir /var/lib/redis/6379- 時點性
- save，阻塞的，比如關(guān)機維護
- bgsave，后臺的，fork子進程
AOF
appendonly yes appendfilename "appendonly.aof"auto-aof-rewrite-percentage 100 auto-aof-rewrite-min-size 64mbappendfsync always appendfsync everysec appendfsync no- 將寫操作記錄到文件中
- 丟失數(shù)據(jù)少
- 可以和 RDB 同時開啟
- 4.0 以前，重寫 AOF 時，刪除抵消的命令，合并重復(fù)的命令
- 4.0 以后，重寫 AOF 時，將老的數(shù)據(jù) RDB 到 AOF 文件中，再將增量數(shù)據(jù)以指令的方式 append 到 AOF 文件中
緩存常見問題
緩存擊穿
作為緩存，受到內(nèi)存大小限制，可能：
- key 超過了過期時間
- key 被 LRU LFU 清掉了
因為 某些 key 不在 redis 里面了，大量并發(fā)來找這個 key 的時候，這時候客戶端去直接請求數(shù)據(jù)庫，這就是擊穿。
這個問題怎么解決？
只要發(fā)現(xiàn)某個key不存在，就讓所有對這個key的請求去搶一把鎖。也就是說，
讓第一個找key的請求，執(zhí)行一個setnx，類似于放一把鎖。只有獲得鎖的人才能去數(shù)據(jù)庫查，其他的請求讓它們失敗，sleep等待幾秒鐘之后，重新去 redis 取數(shù)據(jù)。
這會存在一個問題：
1、如果第一個拿到鎖的人掛了，別人也拿不到鎖，這樣就死鎖了。可以設(shè)置鎖的過期時間來避免這個問題。
2、由于我設(shè)置了過期時間，可能會發(fā)生這樣的情況：拿到鎖的人沒掛，但是可能由于網(wǎng)絡(luò)擁塞或者數(shù)據(jù)庫擁塞，鎖超時了，又有一個人拿到這個鎖，又去數(shù)據(jù)庫取，更加擁塞了。
針對這個問題，可以開啟多個線程，一個線程去庫里取數(shù)據(jù)，另一個線程去給鎖的超時時間延長。這樣會讓代碼邏輯變得復(fù)雜。
3、像上面這樣，你自己去實現(xiàn)分布式協(xié)調(diào)很麻煩。因此我們引入Zokeeper，這個以后再講~
緩存穿透
從業(yè)務(wù)接收查詢的，是你系統(tǒng)里面根本不存在的數(shù)據(jù)。這就是緩存穿透。
怎么解決？使用布隆過濾器
- 你可以在客戶端中包含布隆過濾器的算法
- 你可以在客戶端只包含算法，在redis中存放bitmap
- 你可以直接在redis中集成布隆模塊：RedisBloom模塊
布隆過濾器的缺點
只能增加，不能刪除，如果你的業(yè)務(wù)刪除了數(shù)據(jù)庫中的某條數(shù)據(jù)，無法在布隆過濾器中刪除這個key
解決方式
你可以使用布谷鳥過濾器等其他支持刪除操作的過濾器，或者設(shè)置一個空 key
緩存雪崩
和擊穿有些類似，都是后面有數(shù)據(jù)的情況。和緩存擊穿不同的是，緩存擊穿指 并發(fā)查同一條數(shù)據(jù)，緩存雪崩是 不同數(shù)據(jù)都過期了，很多數(shù)據(jù)都查不到從而查數(shù)據(jù)庫。
- 大量 key 同時失效，間接造成大量的訪問到達 DB
怎么解決？要考慮兩種情況：
1、每天都要更新數(shù)據(jù)的情況，例如每天零點要刷新緩存。這時候可以依賴擊穿的解決方案。或者在業(yè)務(wù)層加一個小延時：判斷如果是零點就延時，隨機sleep幾秒，這樣不會把流量一大波流量同時放過來。
對于能夠提前預(yù)知的時點數(shù)據(jù)，比如京東雙11的頁面樣式、圖片等，可以提前推到客戶端本地，到雙11零點的時候直接切換即可。
2、與時點性無關(guān)（并不需要在某個時間刷新緩存）的話，可以設(shè)置隨機過期時間。
緩存一致性（雙寫問題）
更新緩存的的Design Pattern有四種：Cache aside, Read through, Write through, Write behind caching
如何保證緩存與數(shù)據(jù)庫的雙寫一致性？https://www.jianshu.com/p/2936a5c65e6b
分布式系統(tǒng)里要么通過 2PC 或是 Paxos 協(xié)議保證一致性，要么就是拼命的降低并發(fā)時臟數(shù)據(jù)的概率
緩存系統(tǒng)適用的場景就是非強一致性的場景，所以它屬于CAP中的AP，BASE理論。
異構(gòu)數(shù)據(jù)庫本來就沒辦法強一致，我們只是減少時間窗口，達到最終一致性。
還有別忘了設(shè)置過期時間，這是個兜底方案
Redis 集群
單機、單節(jié)點、單實例存在的問題
- 單點故障（主從、主備，一變多，多機數(shù)據(jù)存的是一樣的）
- 容量有限
- 單機壓力過大（分片集群，sharding 分片，不同分片存儲的是不一樣的數(shù)據(jù)）
單機單點問題的解決方式：AKF
AKF 拆分原則
- X軸（主從復(fù)制）：可以是Redis實例的副本，數(shù)據(jù)庫的副本等
- 讀寫分離，增加備用性，解決單點故障 問題
- 全量鏡像，不能解決容量有限 的問題
- Y軸（按業(yè)務(wù)拆分）：數(shù)據(jù)分開存儲，客戶端按照業(yè)務(wù)指定查詢哪個庫
- 解決容量有限 的問題
- Z軸（哈希取模）：在按照不同業(yè)務(wù)拆分的前提下，將同一個業(yè)務(wù)將數(shù)據(jù)再拆分，存到不同的庫中
- 數(shù)據(jù)量足夠小，更易發(fā)揮單機性能
拆分之后，怎么知道數(shù)據(jù)存在哪臺機器了？去哪里取數(shù)據(jù)？
可以在客戶端自己實現(xiàn)；可以用代理的中間件；
AKF 存在的問題：CAP定理
- 一致性（Consistency）：分布式系統(tǒng)中的所有數(shù)據(jù)備份，在同一時刻是否同樣的值
- 可用性（Availability）：集群中一部分節(jié)點故障后，集群整體是否還能響應(yīng)客戶端的讀寫請求
- 分區(qū)容忍性（Partition tolerance）：是否能夠容忍發(fā)生網(wǎng)絡(luò)分區(qū)，對外表現(xiàn)出數(shù)據(jù)的不一致
- 例如，向注冊中心集群注冊50臺tomcat，有的僅成功注冊了40臺，不影響使用，可容忍
集群一般使用奇數(shù)臺
當存活節(jié)點過半的時候，就可以解決容錯問題，正常提供服務(wù)
為什么是奇數(shù)臺？你看，3個節(jié)點4個節(jié)點都最多允許1個節(jié)點掛掉，但是：
- 4臺服務(wù)器成本高于3臺服務(wù)器成本
- 不管你是4節(jié)點還是3個節(jié)點，都只允許掛1個，風險是一樣的
Sentinel 哨兵
- 監(jiān)控
- 提醒
- 自動故障遷移
- 流言協(xié)議：主服務(wù)器是否下線
- 投票協(xié)議：重新選主，故障遷移
一致性哈希
由于redis是單點，但是項目中不可避免的會使用多臺Redis緩存服務(wù)器，那么怎么把緩存的Key均勻的映射到多臺Redis服務(wù)器上，且隨著緩存服務(wù)器的增加或減少時做到最小化的減少緩存Key的命中率呢？這樣就需要我們自己實現(xiàn)分布式。http://www.zsythink.net/archives/1182
普通的哈希算法存在的問題：
當緩存服務(wù)器數(shù)量發(fā)生變化時，會引起緩存的雪崩，大量緩存同一時間失效。
當緩存服務(wù)器數(shù)量發(fā)生變化時，幾乎所有緩存的位置都會發(fā)生改變。怎樣才能盡量減少受影響的緩存呢？
hash（服務(wù)器A的IP地址） % 2^32 hash（服務(wù)器B的IP地址） % 2^32 hash（服務(wù)器C的IP地址） % 2^32一致性哈希算法的優(yōu)點
假設(shè)服務(wù)器B出現(xiàn)了故障，我們現(xiàn)在需要將服務(wù)器B移除，那么，我們將上圖中的服務(wù)器B從hash環(huán)上移除即可。圖片4仍然會被緩存到服務(wù)器C中，圖片1與圖片2仍然會被緩存到服務(wù)器A中，這與服務(wù)器B移除之前并沒有任何區(qū)別。
hash環(huán)的偏斜
如果服務(wù)器被映射成下圖中的模樣，那么被緩存的對象很有可能大部分集中緩存在某一臺服務(wù)器上。
我們應(yīng)該怎樣防止hash環(huán)的偏斜呢？一致性hash算法中使用"虛擬節(jié)點"解決了這個問題
虛擬節(jié)點
“虛擬節(jié)點"是"實際節(jié)點”（實際的物理服務(wù)器）在hash環(huán)上的復(fù)制品,一個實際節(jié)點可以對應(yīng)多個虛擬節(jié)點。
從上圖可以看出，A、B、C三臺服務(wù)器分別虛擬出了一個虛擬節(jié)點，當然，如果你需要，也可以虛擬出更多的虛擬節(jié)點。引入虛擬節(jié)點的概念后，緩存的分布就均衡多了。如果你還不放心，可以虛擬出更多的虛擬節(jié)點，以便減小hash環(huán)偏斜所帶來的影響，虛擬節(jié)點越多，hash環(huán)上的節(jié)點就越多，緩存被均勻分布的概率就越大。
總結(jié)
以上是生活随笔為你收集整理的面试必会系列 - 3.1 Redis知识点大汇总（数据类型，内存模型，持久化，缓存击穿，集群，一致性哈希等等）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 左神算法：分别用递归和非递归方式实现二叉
- 下一篇： 左神算法：二叉树的最大 / 最小深度（普