數據結構

Redis常見的數據結構

• String：緩存對象
• Hash：緩存對象、購物車
• List：消息隊列
• Set：點贊、共同關注
• ZSet：排序

Zset底層？

Zset底層的數據結構是由壓縮鏈表或跳表實現的

• 如果有序集合的元素 < 128，并且每個元素 < 64字節時，會用壓縮列表作為Zset類型的底層數據結構
• 如果有序集合的元素不滿足上面的條件，會用跳表作為Zset類型的底層數據結構

跳表是怎么實現的？

跳表在創建節點時，隨機生成每個節點的層數。

跳表在創建節點時，先生成[0, 1]的隨機數，如果隨機數 < 0.25，層數就會增加一層；然后繼續生成下一個隨機數，直到隨機數 > 0.25結束，最終確定該節點的層數

為什么Zset使用跳表而不是B+樹？

1. B+樹的設計目標是優化磁盤，通過減少樹的高度來降低磁盤尋道次數；跳表是基于鏈表，通過多級索引加速查詢，內存訪問模式更符合CPU緩存局部性。Redis是內存數據庫，數據完全存儲在內存中，不需要優化磁盤IO，B+樹的磁盤特性對Redis意義不大，跳表的設計更優
2. 跳表相比B+樹實現起來更簡單，B+樹插入和刪除可能需要觸發節點的分裂和合并，跳表插入時只需要隨機生成層高，刪除時直接移除節點并調整指針即可。
3. B+樹每個節點需要存儲多個鍵值和葉子節點，存在內存碎片；跳表每個節點只需要存儲鍵值、層高、多個前向指針，內存占用更緊湊。

壓縮列表是怎么實現的?

壓縮列表是由連續內存塊組成的順序型數據結構，類似數組。

• 查找第一個元素和最后一個元素時間復雜度：O(1)
• 查找其他元素：只能逐個查找，復雜度O(n)

壓縮列表的缺點：會發生連鎖更新，導致壓縮列表占用的內存空間要多次重新分配，這回直接影響到壓縮列表的訪問性能。

壓縮列表只適合保存數據量不多的場景。

quicklist和listpack這兩種數據結構就是為了盡可能地保持壓縮列表節省內存的優勢

哈希表怎么擴容的？

在正常服務請求階段，插入的數據都會寫到哈希表1中，此時哈希表2沒有被分配空間，隨著數據量的增多，觸發了rehash操作：

1. 給哈希表2分配空間，一般比哈希表1大2倍
2. 將哈希表1的數據移動到哈希表2中
3. 遷移完成后，把哈希表1的空間釋放，并把哈希表2設置為哈希表1，在哈希表1新創建一個空白的哈希表，為下次rehash做準備。

存在問題：如果哈希表1非常大，那么每次遷移到哈希表2的時候，可能會對redis造成阻塞，無法響應其他請求。

解決：在rehash進行期間，每次進行新增、刪除、查找操作，redis除了操作哈希表1，還會操作redis2，這樣就把一次大量數據的遷移工作分攤到了多個請求中。

注：哈希表擴容時，如果來了一個讀請求，會現在哈希表1里查找；如果沒找到，才會到哈希表2里查找。

String是用什么存儲的？為什么不用c語言的字符串？

redis中的string字符串使用SDS數據結構存儲的，SDS結構如下：

• len：記錄了字符串的長度
• alloc：分配給字節數組的空間長度
• flags：用來表示不同類型的SDS（sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64）
• buf[]：字符數組，用來保存實際數據

SDS數據結構可以O(1)獲取字符串長度，c語言的字符串需要O(n)

SDS不需要"\0"來表示字符串結尾，有個len來記錄字符串的長度（但是她為了兼容部分c的庫函數，還是加了"\0"）

C語言的字符串在追加的時候是不安全的，程序內部不會判斷緩沖區大小是否夠用，當緩沖區發生溢出后會導致程序異常；SDS結構里加入alloc和len，這樣可以通過alloc - len來判斷剩余緩沖區的大小，當緩沖區大小不夠用時，redis會自動擴大SDS的空間大小。

線程模型

Redis為什么快？

單線程的redis吞吐量可以達到10w/s

1. Redis大部分的操作都在內存中完成的，redis的瓶頸可能是機器的內存或網絡帶寬而非CPU
2. Redis采用單線程模型可以避免多線程之間的競爭，省去了多線程切換帶來的開銷
3. Redis采用IO多路復用機制處理大量客戶端的Socket請求，在只運行單線程的情況下，該機制允許內核同時存在多個監聽Socket和已連接Socket。

Redis的單線程指的是”接收客戶端請求 -> 解析請求 -> 進行讀寫數據操作 -> 發送數據給客戶端“這個過程是一個線程完成的，但是Redis程序不是單線程的，Redis在啟動時，會啟動后臺線程

關閉文件、AOF刷盤、釋放內存這些任務會創建單獨的線程來處理，如果放在主線程來處理，Redis主線程就會發生阻塞。

Redis6也采用多個IO線程來處理網絡請求，因為隨著硬件的升級，Redis的性能瓶頸出現在網絡IO的處理上

Redis怎么實現IO多路復用

因為Redis是單線程的，所有的操作都是按順序進行，由于讀寫操作等待用戶的輸入和輸出都是阻塞的，IO多路復用就是為了單線程的服務同時處理多個客戶端的請求。

多路：指多個網絡連接客戶端

復用：指復用同一個進程

IO多路復用是使用一個線程來檢查多個Socket的就緒狀態，在單個線程中通過記錄跟蹤每個Socket的狀態來管理處理多個IO流

日志

Redis的持久化方式？

Redis的讀寫操作都是發生在內存的，但是redis重啟后，內存中的數據就會丟失，為了保證內存中的數據不丟失，就需要持久化機制，把數據存儲到磁盤，這樣Redis重啟后就能從磁盤中恢復數據，Redis主要有兩種持久化方式，分別是：

1. AOF日志：每執行一條寫操作，就會把該命令以追加的方式寫入文件中，redis重啟時，會逐一執行這個文件里的命令將數據恢復。redis由三種寫回磁盤的策略：

   • Always：每次寫操作命令執行完后，同步將AOF日志數據寫回磁盤
   • Everysec：每次寫操作命令執行完后，先將命令寫到緩沖區中，再每隔一秒將數據寫回磁盤
   • No：Redis不控制寫回磁盤的時機，交給操作系統控制，每次寫操作后先將命令寫到緩沖區，由操作系統決定何時將命令寫回磁盤。

2. RDB快照：RDB快照只記錄一瞬間的內存數據，記錄的是實際的數據。Redis有兩個命令來生成RDB快照：

   • save命令：在主線程中生成RDB文件（會阻塞主線程）
   • bgsave命令：創建一個子線程來生成RDB文件（避免阻塞主線程）

AOF日志記錄的是操作命令，用AOF做故障恢復時，需要全量把日志全部執行一遍，一旦AOF日志非常多，會造成Redis恢復操作慢。所以引入了RDB快照（記錄一瞬間的內存數據，記錄的是實際數據，AOF文件記錄的是命令操作的日志，而不是實際數據）

內存淘汰和過期刪除

內存淘汰和過期刪除的區別？

內存淘汰是在內存滿時會觸發內存淘汰策略來淘汰一些不必要的資源

過期刪除是將已過期的鍵值對進行刪除

內存淘汰策略有哪些？

內存淘汰：當Redis內存達到設置的閾值時，Redis就會主動挑選部分key刪除以釋放更多的內存。

Redis在每次處理客戶端命令時，都會對內存使用情況判斷，如果必要，則執行內存淘汰。內存淘汰的策略有：

1. 前綴：
   • allkeys：對所有的key進行淘汰，從dict的哈希表中挑選
   • volatile：只對設置了TTL的key進行淘汰，從expires的哈希表中挑選
2. 后綴：
   • ttl：淘汰ttl小的
   • random：隨機挑選
   • lru：基于LRU算法
   • lfu：基于LFU算法

過期刪除策略？

redis的失效緩存不會立即刪除，而是使用惰性刪除 + 定期刪除這兩種策略配合

1. 惰性刪除：在訪問或修改key時，判斷key是否過期，如果過期就刪除key；如果沒有過期，就不做處理，返回正常的鍵值對
2. 定期刪除：每隔一段時間隨機從數據庫中取出一部分key進行檢查，刪除過期的key，如果過期的key≥選舉的key的四分之一，則再次選取，直到＜四分之一，這個過程可能會很長時間，所以需要設置循環的上限。

集群

Redis主從同步

1. 全量同步：以下情況會發生全量同步

   • 主從集群首次建立連接
   • 從服務器斷開連接時間過長

   步驟：

   1. 從服務器發送SYNC命令，開始請求同步
   2. 主服務器收到SYNC命令后，生成RDB快照，并將生成的RDB文件發送到從服務器中
   3. 從服務器收到RDB文件后，先清空當前的數據集，并載入RDB文件中的數據
   4. 在RDB文件傳輸的過程中，如果又有新的指令，主服務器會將新的指令先放在緩沖區中，一旦RDB文件傳輸完成，主服務器又會將緩沖區里的命令發給從服務器，保證數據的一致性。

2. 增量同步：允許從服務器從斷點處繼續同步

   步驟：

   1. 從服務器在網絡恢復后，發送psync命令
   2. 主服務器收到psync命令后，告訴從服務器接下來要用增量同步的方式同步數據
   3. 主服務器將從服務器斷開這段時間內執行的命令，發送給從服務器。

   （斷開這段時間內執行的命令會存在主服務器的環形緩沖區中，主要存放的是最近傳播的寫命令，如果緩沖區里的一部分數據還沒同步給從服務器，就已經被覆蓋了，主服務器就會再次采取全量同步）

哨兵機制的原理？

redis的主從集群中，主從模式是讀寫分離的，如果主節點掛了，需要選擇一個主節點變成從節點，如果沒有哨兵機制，那么只能人工選擇一個主節點變成從節點，還要通知其他從節點現在主節點的變更。

哨兵機制主要是實現了主從節點的故障轉移，他會檢測主節點是否存活，如果主節點掛了，就會選取一個從節點當成主節點，并且把新的主節點信息通知給其他的從節點。

哨兵機制選擇主節點的算法？

1. 故障節點主觀下線：哨兵節點會定時對redis集群里的所有節點發送心跳包檢測節點是否正常，如果一個節點沒有恢復哨兵節點的心跳包，則認為該節點主觀下線

2. 故障節點客觀下線：當一個節點被標記成故障，不代表這個節點下線了，但是如果哨兵集群中有超過quorum數量的哨兵節點認為該redis節點主觀下線，則該redis客觀下線

   如果下線的redis節點是從節點或哨兵節點，則沒有后續操作了；如果是主節點，則開始故障轉移，從剩下的從節點中選出一個節點升級為主節點

3. 哨兵集群中選擇Leader：要從redis集群中選擇一個節點變成主節點，必須先從哨兵節點中選取leader，一個哨兵節點至少要拿到quorunm個贊成票，才能成為Leader

4. 哨兵Leader選擇新主節點：哨兵Leader從redis從節點中選擇一個redis節點作為主節點

   • 首先判斷slave節點與master節點斷開時間長短，如果超過指定值（down-after-milliseconds * 10）則會排除該slave節點。
   • 然后判斷slave節點的slave-priority值，值越小優先級越高。（如果是0則用不參與選舉，默認是0）
   • 如果slave-priority一樣，則判斷slave節點的offset值，越大說明數據越新，優先級越高。
   • 最后是判斷slave節點的運行id大小，越小優先級越高。

Redis集群的模式？

Redis緩存數據量大到一臺服務器無法緩存時，就需要使用Redis切片集群，將數據分布在不同的服務器上，降低對單主節點的依賴。

一個切片有16384個哈希插槽，這些哈希插槽類似數據分區，根據他的key被映射到一個哈希槽中。

場景

為什么使用Redis

1. Redis具備高性能：如果用戶第一次訪問Mysql中的某些數據，這個過程比較慢，因為是從磁盤上讀取的；如果將該用戶的數據緩存在Redis中，下次在訪問這些數據的時候就可以直接從Redis中讀取了，操作Redis緩存就是直接操作內存，速度快。【需要考慮Mysql和Redis中的數據一致性】
2. Redis具備高并發：單臺Redis的QPS是Mysql的10倍，所以訪問Redis能承受的請求遠遠大于Mysql，因此可以考慮將數據庫中一部分數據緩存到Redis中，這樣就不需要每次請求都到數據庫中查了。

為什么Redis比Mysql快？

1. Redis是基于內存存儲、Mysql是基于磁盤存儲
2. Redis是基于鍵值對結構，支持簡單的數據結構；Mysql需要定義表結構、索引等復雜的數據結構
3. Redis采用單線程可以避免多線程之間的競爭，省去了多線程切換帶來的開銷。

本地緩存和分布式緩存的區別

本地緩存：將數據存儲在本地應用程序或服務器上，用于加速數據訪問，本地緩存通常是使用內存作為存儲介質，利用內存的高速讀寫來提高訪問速度。

本地緩存：由于本地緩存是存儲在本地內存中，訪問速度快，而且能夠降低對遠程服務器的訪問次數；但是本地緩存的可擴展性收到硬件資源的限制，無法支持大規模的數據存儲。

分布式緩存：將數據存儲在多個分布式節點上，通過協同工作來提供高性能的數據訪問服務，利用多臺服務器來分擔數據存儲和訪問的壓力。

分布式緩存：節點可以動態擴展，能夠支持大規模數據存儲和訪問的需求；但是相對本地緩存，分布式存儲的訪問速度相對慢，因為數據需要從多個節點進行訪問，且需要通過網絡進行數據傳輸。

Redis分布式鎖的實現原理？

分布式鎖是分布式環境下并發控制的一種機制，用來控制某個資源在同一時刻只能被一個應用使用。

Redis本身可以被多個客戶端共享，可以用來保存分布式鎖，而且Redis的讀寫性能高，可以應對高并發鎖的場景。

redis的set命令有個nx參數可以實現”key不存在時插入“，所以可以使用它實現分布式鎖：

• 如果key不存在，則表示插入成功（加鎖成功）
• 如果key存在，則表示插入失敗（加鎖失敗）

加鎖的操作要注意：

1. 加鎖包括了：讀取鎖變量、檢查鎖變量值、設置鎖變量三個操作，需要以原子操作的方式完成，所以使用set命令要帶上nx選項來實現加鎖。
2. 鎖變量需要設置過期時間，以免客戶端拿到鎖后發生異常，導致鎖一直無法釋放
3. 鎖變量的值需要能夠區分來自不同客戶端的加鎖操作。

大Key問題？

字符串類型的Key對應的Value值占用空間很大就是大Key問題

大Key問題會導致：內存占用過高，從而觸發內存淘汰策略；大Key會占用大量內存，導致性能下降；會造成網絡擁堵；會導致主從同步延遲

解決：

1. 對大Key進行拆分，將一個含有數萬成員的hashkey拆分成多個hashkey；
2. 將不適用Redis的數據移到別的地方存儲，并在Redis中異步刪除這個數據

什么是熱key？

一般是以key的請求頻率來判斷的，例如：

1. QPS集中在特定的key
2. 帶寬使用率集中在特定的Key
3. CPU使用時間占比集中在特定的Key

解決：

1. 將對應的熱ky進行復制并遷移到其他的數據分片，來解決單個數據分片的熱key壓力
2. 如果熱key的產生來自讀請求，可以使用讀寫分離架構來降低每個數據分片的讀請求，也可以不斷增加從節點。

怎么保證redis和mysql數據緩存的一致性？

1. 對于讀數據，如果redis不命中，會先去數據庫中查詢后加載到redis中
2. 對于寫數據，會更新數據庫后去刪除緩存

緩存系統就是CAP中的AP，通過犧牲強一致性來提高性能，如果需要數據庫和緩存保持強一致性，就不適合用緩存。

緩存的過期時間設置是太短、太長都不好：

• 太短的話，請求可能會比較多的落在數據庫上，就失去了緩存的意義
• 太長的話，緩存中的臟數據會讓系統長時間處于一個延遲的狀態，會浪費內存。

通過一些方案是可以達到最終一致性的（針對刪除緩存異常的情況）：

1. 刪除緩存重試策略（消息隊列）：如果刪除緩存失敗，可以從消息隊列中重新讀取數據，然后再刪除緩存；如果刪除緩存成功，就要把數據從消息隊列中移除，避免重復操作。
2. 訂閱MySQL binlog，再操作緩存：正常操作是先更新數據庫，再刪除緩存，一旦數據庫更新成功，就會產生一條變更日志記錄再binlog里，我們通過訂閱binlog日志，拿到要操作的數據，然后執行緩存刪除。

緩存雪崩、緩存擊穿、緩存穿透是什么？

• 緩存雪崩：大量緩存數據同時失效，或redis宕機，如果有大量的用戶請求，都無法在redis中處理，于是請求直接訪問數據庫，造成數據庫的壓力，嚴重的會導致數據庫宕機

  • 如果要給緩存設置過期時間，應該避免大量的數據設置同一個過期時間，可以在設置過期時間的時候給這些數據加上隨機數，這樣數據就不會在同一時間過期
  • 當業務線程在處理用戶請求時，如果訪問的數據不在redis里，就加個互斥鎖，保證同一時間只能由一個請求來構建緩存（未能獲取互斥鎖的請求要么鎖釋放后重新讀取緩存，要么返回空值或默認值），互斥鎖一定要設置過期時間，不然一個請求拿到鎖可能因為一些意外而阻塞，這時其他請求也一直拿不到鎖。
  • 讓緩存“永久有效”，將更新緩存的工作交給后臺線程定時更新

• 緩存擊穿：緩存中某個熱點數據過期，大量的請求訪問該熱點數據，就無法從緩存中讀取，直接訪問數據庫，數據庫很容易被高并發的請求沖垮。

  • 當業務線程在處理用戶請求時，如果訪問的數據不在redis里，就加個互斥鎖，保證同一時間只能由一個請求來構建緩存（未能獲取互斥鎖的請求要么鎖釋放后重新讀取緩存，要么返回空值或默認值），互斥鎖一定要設置過期時間，不然一個請求拿到鎖可能因為一些意外而阻塞，這時其他請求也一直拿不到鎖。
  • 不給熱點數據設置過期時間，由后臺異步更新緩存，或者在熱點數據過期前，提前通知后臺線程更新緩存

  緩存擊穿可以理解成時緩存雪崩的一個子集，緩存雪崩指的是大量的key過期，而緩存擊穿特指的是熱點key過期。

• 緩存穿透：用戶訪問的數據即不在緩存中，也不在數據庫中，導致請求在訪問緩存時，發現緩存缺失，再去訪問數據庫，數據庫也沒有對應的數據，當有大量的這種請求到來，數據庫的壓力就會很大。

  • 在Api入口處判斷要請求的參數是否合法，如果不合法直接返回錯誤，防止進一步去訪問數據庫和緩存
  • 可以爭對查詢的數據，在緩存中也設置一個空值或默認值，這樣后續的請求就可以從緩存中獲取空值或默認值返回給應用，而不會繼續查詢數據庫
  • 布隆過濾器：在寫入數據庫數據時，先用布隆過濾器做個標記，在用戶請求到來時，業務線程確認緩存失效后，可以通過查詢布隆過濾器快速判斷數據是否存在，不存在就不通過查詢數據庫來判斷數據庫來判斷數據是否存在。即使發生了緩存穿透，大量的請求只會查詢Redis和布隆過濾器，而不會查詢數據庫。

介紹一下布隆過濾器的原理

在寫入數據庫數據時，先用布隆過濾器做個標記。

請求過來會先經過布隆過濾器，布隆過濾器先判斷數據庫中是否存在這條數據，如果不存在，就會拒絕這個請求。

注意，布隆過濾器判斷一個元素不存在時，它絕對不存在；但是如果它判斷一個元素存在，這個元素可能會不存在。

如何實現秒殺場景處理高并發以及超賣現象？

1. 在數據庫層面：

   • 在查詢商品庫存時加排他鎖，比如“select * from goods where id = #{id} for update”，此時相當于對id為#{id}的數據行加鎖，其他線程可以使用select讀取數據，但是如果是select for update、update、delete都會阻塞，直到線程A提交事務，其他線程才能獲得鎖。
   • 在更新數據庫的時候，可以通過加一個庫存限制的條件“select * from goods where id = #{id} and stock > 0”

2. 利用分布式鎖：同一個key，同一個時間只有一個客戶端拿到鎖，其他客戶端會陷入無限等待來嘗試獲取鎖，只有獲得鎖的客戶端才能執行接下來的業務邏輯

   缺點：同一個商品在多個用戶同時下單時，會基于分布式鎖串行化處理，導致沒法同時處理用同一個商品的大量下單請求。

3. 利用Redis的incr、decr的原子性 + 異步性：

   • 系統初始化時，將商品庫存加到Redis中
   • 收到秒殺請求時，再redis中進行預減庫存（利用incr、decr的原子性），當redis中庫存不足時，直接返回秒殺失敗
   • 把秒殺請求放入異步隊列，返回正在排隊中
   • 服務端異步請求出隊（有些商品規定用戶只能購買一次，防止重復秒殺），出隊成功的商品可以生成秒殺訂單，扣減庫存
   • 用戶在客戶端申請秒殺請求后，會有個定時任務進行查詢，查看秒殺是否成功，如果秒殺成功就進入秒殺訂單詳情，否則就會提示秒殺失敗。