分散式架構Redis中有哪些資料結構及底層實現原理

引言

面完了負載均衡，正向代理，反向代理，終於鬆了一口氣，然後話題轉向了快取Redis，為什麼是這個順序呢？

回想了一下系統架構，我大概知道原因了。

Redis 處於服務最上層。面試官是按照這個順序從上到下考察我對整個系統設計能力，圍著整個系統自頂向下的結構考察基礎。不糾結這麼多，反正先問後問，Redis一定是你必須掌握的。

1、面試官：我看你提到，專案中使用了Reids作為快取，為什麼是Reids而不是其他，Redis有什麼優勢嗎？

問題分析： Redis的設計理念已經成了很多一線網際網路公司自主研發分散式快取框架的標杆，因為相比傳統的 Memcache ，Redis 豐富的資料結構實在太香。

答：

• 首先 Redis 支援豐富的資料結構，新版本資料結構從最初的5種變成9種。
• 其次 Redis 是讀寫單程序單執行緒，不用考慮並行讀寫的複雜場景，速度也快。
• Reids 功能完備，支援資料持久化，支援主從複製和叢集。
• 還有Lua指令碼，事務，釋出訂閱模型，Reids 都支援。

在高並行請求時，為何我們頻繁提到快取技術？最直接的原因是，磁碟IO及網路開銷是直接請求記憶體IO千百上千倍，做個簡單計算，如果我們需要某個資料，該資料從資料庫磁碟讀出來需要0.0045S，經過網路請求傳輸需要0.0005S，那麼每個請求完成最少需要0.005S，該資料伺服器每秒最多隻能響應200個請求，而如果該資料存於本機記憶體裡，讀出來只需要100us，那麼每秒能夠響應10000個請求。通過將資料儲存到離CPU更近的未位置，減少資料傳輸時間，提高處理效率，這就是快取的意義。

給您列舉一個我利用Reids把專案QPS提到幾十萬級別的案例：

一個風控系統在日常24H中 Redis叢集 QPS 曲線圖，從業務低峰期幾千或晚高峰最高30W，一個 Redis 叢集都可輕鬆應對，30WQPS 在大型系統中流量並不算高，且不是核心系統，如果在多幾倍幾十倍多流量，一個結構優良的Redis 叢集都可輕鬆應對，這充分說明了我們為什麼要使用快取，快取可以把系統響應能力提高N個數量級，遠高於傳統基於硬碟的關係型資料庫

 面試官心想：看來是做足了功課。

2、面試官：剛剛你提到Redis是單執行緒，為什麼單執行緒模型的 Redis 效能不減。

 問題分析：成功挖坑，提到單執行緒肯定會問我為什麼要這樣設計。

 答：

單執行緒不代表一定就慢，單執行緒有一個最大好處就是節省執行緒切換的開銷，更不用考慮並行讀寫帶來的複雜操作場景，這就大大節省了執行緒間切換的時間了。

單執行緒模型避免了多執行緒的頻繁上下文切換，這也避免了多執行緒可能產生的競爭問題。

Reids 是基於記憶體的讀寫操作，記憶體肯定比傳統磁碟IO資料庫快。

Reids 核心是基於非阻塞的IO多路複用機制。

3、面試官：那你剛剛說的Redis資料結構都有哪幾種，如何選擇使用哪種？

問題分析： 常用的5種，重點學會這5種資料結構的使用足夠了。

 答：比較常用的有5種

字串 String： 字串是 Redis 中最為基礎的資料儲存型別，資料結構簡單，可儲存文字，Json，圖片資料等任何二進位制檔案。如姓名，訂單號等，對於一些特殊的資料結構，比如List、Set等，建議採用相應的下面介紹的List和Set資料結構進行儲存，這樣不僅可以節省儲存空間還可以提高操作效率。

列表 List： 類似 Java 中的 List ，按照插入順序排序的字串連結串列，在插入時，如果該鍵並不存在，Redis將為該鍵建立一個新的連結串列。與此相反，如果連結串列中所有的元素均被移除，那麼該鍵也將會被從資料庫中刪除。

集合 Set： 類似 Java 中的set，但它是一個無序集合，用於儲存無序(存入和取出的順序不一定相同)元素，值不能重複。可以使用Redis的Set資料型別跟蹤一些唯一性資料，比如存取系統的唯一IP地址，唯一使用者ID等資訊，再比如在微博應用中，每個人的好友存在一個集合（set）中，這樣求兩個人的共同好友的操作，可能就只需要用求交集命令即可。

有序集合 Sorted Set： 類似 Java 中的 TreeSet，支援從小到大排序的 set，適用於排行榜結構的資料儲存。

Hash： 型別相當於Java中的HashMap，所以該型別非常適合於儲存值物件的資訊，比如使用者基本資訊物件含有暱稱、性別和Age等屬性，可以使用Hash來儲存User物件，Key可以為使用者的唯一ID屬性。

除此之外，新版本的Redis還提供了點陣圖，地理座標，流幾種結構。

深入分析

曾經有面試官問我，你看過Reids原始碼嗎，我說沒有看過，他說有精力可以研究一下，Redis那幾種常用的資料結構底層實現原理還是值得學習的。

1、簡單動態字串結構，Redis字串的實現方式

簡單動態字串（simple dynamic string）簡稱SDS。Redis使用C語言編寫，但是傳統的C字串使用長度為 N+1 的字串陣列來表示長度為N的字串，所以為了獲取一個長度為C字串的長度，必須遍歷整個字串。和C字串不同，動態字串的資料結構中，有專門用於儲存字串長度的變數，我們可以通過獲取len屬性的值，直接知道字串長度，從一定程度上提高了讀取效率。

 Redis原始碼中，動態字串的定義：

/*  
 * 儲存字串物件的結構  
 */  
struct sdshdr {  
    // buf 中已佔用空間的長度  
    int len;  
    // buf 中剩餘可用空間的長度  
    int free;  
    // 資料空間  
    char buf[];  
};

len 變數，用於記錄buf 中已經使用的空間長度。

free 變數，用於記錄buf 中還空餘的空間，初次分配空間，一般沒有空餘，在對字串修改的時候，會有剩餘空間出現，這樣做是為了杜絕C語言中緩衝區溢位的可能性，當我們需要對一個SDS進行修改的時候，Redis 會在執行拼接操作之前，預先檢查給定SDS空間是否足夠，如果不夠，會先拓展SDS的空間，然後再執行拼接操作。

buf 字元陣列，用於記錄我們的字串（記錄Redis）。

2、連結串列資料結構，List 底層結構

連結串列還是常規的普通雙端連結串列，可以支援反向查詢和遍歷，更方便操作，通過增刪節點來靈活地調整連結串列的長度，雙端連結串列在Redis內部也是被多次使用：

• 事務模組使用雙端連結串列依序儲存輸入的命令。
• 伺服器模組使用雙端連結串列來儲存多個使用者端。
• 訂閱/傳送模組使用雙端連結串列來儲存訂閱模式的多個使用者端。
• 事件模組使用雙端連結串列來儲存時間事件（time event）。

3、跳躍表，sorted set底層結構

 Redis sorted set的內部使用HashMap和跳躍表(SkipList)來保證資料的儲存和有序，（如果你還不瞭解紅黑樹，需要先額外補補功課），HashMap裡放的是成員到score的對映，而跳躍表裡存放的是所有的成員，排序依據是HashMap裡存的score，使用跳躍表的結構可以獲得比較高的查詢效率，並且在實現上比較簡單。

那為什麼Redis的作者使用 SkipList 結構而不是紅黑樹？

紅黑樹：紅黑樹的查詢效率很高，但是在進行重新平衡時，會涉及到大量節點的變化，因此實現和操作起來都比較複雜。

跳躍表：通過簡單的多層索引結構，實現簡單，且能達到近似於紅黑樹的查詢效率，插入節點（多層插入）不需要像紅黑樹那樣有額外操作。而且跳躍表還能實現範圍查詢及輸出，而紅黑樹只支援單個元素查詢，對於範圍查詢效率低。

關於快取的一些演演算法

（偷偷告訴你，這幾個關於Reids的演演算法很大概率也會被問到，需要多少知道幾種）

常用快取資料淘汰策略

快取是非常寶貴的資源，不能把所有資料都放入快取，只能把最重要的或者要求查詢速度最快的資料快取起來，比如微博熱門話題排行榜功能，通常使用快取查詢，而不是資料庫。

FIFO（First In First Out）： 先進先出演演算法，即先放入快取的先被移除。

LRU（Least Recently Used）： 最近最少使用演演算法，使用時間距離現在最久的那個被移除。

LFU（Least Frequently Used）： 最不常用演演算法，一定時間段內使用次數（頻率）最少的那個被移除。

快取資料更新策略

• 定時任務從資料庫直接更新快取：適用於對時間不敏感的資料。
• 查詢時寫快取，即查詢優先查詢快取，若快取未命中，查詢資料庫，將返回結果寫入快取，資料更新時先 delete快取，再更新快取。
• MQ 訊息非同步更新快取，後文中會針對MQ的應用做單獨講解。

總結

這一節重點講解分散式快取 Redis ，本地快取不一定每個專案都會使用，但是 Redis 資料設計合理，保證超高命中率，叢集足夠穩定，那完全可以替代一級本地快取。所以 Redis 非常值得你花更多時間學習。分散式快取是面試必問。

Redis 是建設高效能網站後臺不可缺少的工具，無論你是面試業務開發工程師還是架構師，都需要熟練掌握。

關於Redis，推薦閱讀黃建宏的《Redis 設計與實現》，能夠掌握Redis的5種資料結構，Redis 的持久化方式 RDB 和 AOF，兩者有什麼優點和缺點，如何選型，以及瞭解高可用 Redis 叢集的建設方案。

以上就是分散式架構Redis中有哪些資料結構及底層實現原理的詳細內容，更多關於分散式架構Redis底層資料結構及原理的資料請關注it145.com其它相關文章！