redis緩存數據結構

『壹』 redis常用數據結構介紹和業務應用場景分析

redis內置了很多常用數據結構，了解這些數據結構的功能和應用場景能夠讓我們在需求開發時靈活運用來解決實際問題。

String是redis中最基礎的數據結構，你可以把它用作緩存最基礎的kv（key-value）類型的緩存(value最大為512MB)，只需要把需要緩存的對象進行string的編解碼即可。另外String也可以保存數值類型的數據，就可以來實現計數功能（redi提供了incr等原子操作）

常見應用場景

List列表更多的時候是把它當成隊列使用(最大2^32 - 1個元素)，使用入隊出隊功能，如果來使用它作為各種列表的話，很多時候不具備防重功能在使用的時候不是很方便。

常見應用場景

Set是一種無序不重復的集合，添加刪除檢查是否存在都是O(1)的時間復雜度。

常見應用場景

hash是一個map結構，可以像存儲對象的多個欄位一樣存儲一個key的多類數據。

常見應用場景

redis中的pub/sub可以實現廣播功能，類似rocketmq中的broadcast

常見應用場景

除了上述最基本的數據結構外，redis還提供了一些其他的數據結構，有的是需要安裝相關redis stack來使用的。

bitmap本質上還是使用的string字元串，不過可以通過bit來進行操作，把這個key的value值想像成bit組成的數組。

常見應用場景

bloomfilter（也叫布隆過濾器）可以理解成一種特殊的set集合，它可以用來判斷一個值是否在這個集合中，不過不同於普通的set，它的判斷存在一定誤判的可能（假陽性），如果bloomfilter判斷一個值不在這個集合中，那麼一定不在，但是如果判斷在，那麼有可能不在。

常見應用場景

hyperloglog是一種概率性的去重計數數據結構，可以實現一定精度的去重計數

常見應用場景

geohash可以實現距離計算、距離查詢等地理位置相關的功能

常見應用場景

『貳』 redis 常見數據結構以及使用場景分析

Redis 提供了 5種數據結構，每一種數據結構有各種的使用場景。
1、String 字元串
字元串類型是 Redis 最基礎的數據結構，首先鍵都是字元串類型，而且 其他幾種數據結構都是在字元串類型基礎上構建的，我們常使用的 set key value 命令就是字元串。常用在緩存、計數、共享Session、限速等。
2、Hash 哈希
在Redis中，哈希類型是指鍵值本身又是一個鍵值對 結構，形如value={{field1，value1}，...{fieldN，valueN}}，添加命令：hset key field value。哈希可以用來存放用戶信息，比如實現購物車
3、List 列表
列表（list）類型是用來存儲多個有序的字元串。可以做簡單的消息隊列的功能。另外，可以利用 lrange 命令，做基於 Redis的分頁功能，性能極佳，用戶體驗好。
4、Set 集合
集合（set）類型也是用來保存多個的字元串元素，但和列表類型不一 樣的是，集合中不允許有重復元素，並且集合中的元素是無序的，不能通過 索引下標獲取元素。利用 Set 的交集、並集、差集等操作，可以計算共同喜好，全部的喜好，自己獨有的喜好等功能。
5、Sorted Set 有序集合
Sorted Set 多了一個權重參數 Score，集合中的元素能夠按 Score 進行排列。可以做排行榜應用，取 TOP N 操作。

『叄』 Redis的五種數據結構及其底層實現原理

redis的字元串類型是由一種叫做簡單動態字元串(SDS)的數據類型來實現

SDC和C語言字元串的區別：
1：SDS保存了字元串的長度，而C語言不保存，只能遍歷找到第一個的結束符才能確定字元串的長度
2：修改SDS，會檢查空間是否足夠，不足會先擴展空間，防止緩沖區溢出，C字元串不會檢查
3：SDS的預分配空間機制，可以減少為字元串重新分配空間的次數
備註：重新分配空間方式，小於1M的數據 翻倍+1，例如：13K+13K+1，如果大於1M，每次多分配1M，例如：10M+1M+1,如果字元串變短，並不會立即縮短，而是採用惰性空間釋放，有專門的API可以釋放多餘空間

hash結構里其實是一個字典，有許多的鍵值對
redis的哈希表是一個dictht結構體：

哈希表節點的結構體如下：

hash演算法：
當要將一個新的鍵值對添加到字典裡面時， 程序需要先根據鍵值對的鍵計算出哈希值和索引值， 然後再根據索引值， 將包含新鍵值對的哈希表節點放到哈希表數組的指定索引上面。

hash沖突解決方式：鏈表法，後入的放到最前面
rehash：
鍵值數據量變動時，時為了讓哈希表的負載因子（load factor）維持在一個合理的范圍之內， 當哈希表保存的鍵值對數量太多或者太少時， 程序需要對哈希表的大小進行相應的擴展或者收縮。
如果是擴充，新數組的空間大小為 大於2*used的2的n次方，比如：used=5,則去大於10的第一個2的n次方，為16
如果是縮小，新數組的空間大小為第一個不大於used的2的n次方，比如：used=5,則新大小為4

redis的list列表是使用雙向鏈表來實現的
···
typedef struct listNode {
struct listNode * pre; //前置節點
struct listNode * next; //後置節點
void * value; //節點的值
}

typedef struct list {
listNode *head; //表頭節點
listNode tail; //表尾節點
unsigned long len; //鏈表所包含的節點數量
void ( p) (void ptr); //節點值賦值函數 這里有問題
void ( free) (void ptr); //節點值釋放函數
int ( match) (void *ptr, void *key) //節點值對比函數
}
···

1：有序集合的底層實現之一是跳錶， 除此之外跳錶它在 Redis 中沒有其他應用。
2：整數集合（intset）是集合鍵的底層實現之一： 當一個集合只包含整數值元素， 並且這個集合的元素數量不多時， Redis 就會使用整數集合作為集合鍵的底層實現。
3：數據少是，使用ziplist(壓縮列表)，佔用連續內存，每項元素都是(數據+score)的方式連續存儲，按照score從小到大排序。ziplist為了節省內存，每個元素佔用的空間可以不同，對於大數據(long long),就多用一些位元組存儲，而對於小的數據(short)，就少用一些位元組來存儲。因此查找的時候需要按順序遍歷。ziplist省內存但是查找效率低。

無序集合可以用整數集合(intset)或者字典實現

Redis的5.0版本中，放出一個新的數據結構Stream。其實也是一個隊列，沒一個不同的key對應的是不同的隊列，沒個隊列的元素，也就是消息，都有一個msgid，並且需要保證msgid是嚴格遞增的。在Stream當中，消息是默認持久化的，即便是Redis重啟，也能夠讀取到信息。
Stream的多播，與其它隊列系統相似，對不同的消費者，也有消費者Group這樣的概念，不同的消費組，可以消費通一個消息，對於不同的消費組，都維護一個Idx下標，表示這一個消費群組費到了哪裡，每次進行消費，都會更新一下這個下標，往後面一位進行偏移。

跳躍表是一種有序數據結構，它通過在每個節點中維持多個指向其它節點的指針，從而大道快速訪問節點的目的，具有以下性質：
1：有很多層結構組成
2：每一層都是一個有序的鏈表，排列順序為由高到低，都至少包含兩個鏈表節點，分別是前面的head節點和後面的nil節點
3：最底層的鏈表包含了所有的元素
4：如果一個元素出現在某一層的鏈表中，那麼在該層之下的鏈表也全部都會出現
5：鏈表中的每個節點都包含兩個指針，一個指向同一層的下一個鏈表節點，另一個指向下一層的通一個鏈表節點

多個跳躍表節點構成一個跳躍表

1：搜索，從最高層的鏈表節點開始，如果比當前節點要大和比當前層的下一個節點要小，那麼則往下找，也及時和當前層的下一層的節點下一個節點
2：插入，首先確定插入的層數，有一種方法是拋一個硬幣，如果是正面就累加，直到遇到反面為止，最後記錄正面的次數作為插入的層數，當確定插入的層數K後，則需要將新元素插入從底層到K層
3：刪除，在各個層中找到包含指定值得節點，然後將節點從鏈表中刪除即可，如果刪除以後只剩下頭尾兩個節點，則刪除這一層。

整數集合是Redis用於保存整數值集合的抽象數據類型，它可以保存int16_t、int32_t、int64_t的整數值，並且保證集合中不會出現重復元素。

整數集合的每個元素都是contents數組的一個數據項，他們按照從小到大的順序排列，並且不包含任何重復項。
length屬性記錄了contents數組的大小。
需要注意的是雖然contents數組聲明為int8_t類型，但是實際上contents數組並不保存任何int8_t類型的值，其真正類型由encoding來決定。

壓縮列表(ziplist)是Redis為了節省內存而開發的，是由一系列特殊編碼的連續內存塊組成的順序型數據結構，一個壓縮列表可以包含任意多個節點(entry)，每個節點可以保存一個位元組數組或一個整數值。
壓縮列表的原理：壓縮列表並不是對數據利用某種演算法進行壓縮的，而是將數據按照一定規則編碼在一塊連續的內存區域，目的是節省內存。

壓縮列表的每個節點構成如下：

『肆』 一、Redis基礎與高級數據結構

1.基本結構：ziplist、數組+鏈表（個數大於512或長度超過64）
2.擴容方式：為追求性能採用漸進式rehash策略，同時保留新舊2個hash結構
3.擴容原理：哈希擴容的時候會有卡頓，所有同時保留現有哈希和擴容縮容後的哈希，在原哈希沒有找到再另一個哈希再進行查找，在定時任務以及後續的hash操作指令中漸漸的將舊數組的元素遷移到新數組。

1.數據結構：intset、哈希的特殊結構，所有的value都是NULL（個數大於512）
intset結構，動態調整類型為uint16~uint64的數組

1.數據結構：ziplist、哈希（存儲key-value）+跳躍列表（提供排序）（個數大於512或長度超過64）
2.quicklist數據結構：

1.基本結構：位數組
2.使用場景：用戶的一年簽到記錄
3.基本操作：

1.基本結構：稀疏矩陣、HyperLogLog（2的14次方個桶用於調和平均，所以佔12KB）
2.使用場景：提供不精確的去重計數方案，標准誤差為0.81%，可以統計每天訪問系統的UV數據
3.基本操作：pfadd、pfcount、pfmerge（多個pf計數累加）

1.基本結構：位數組、無偏hash函數

2.使用場景：推薦演算法中的是否已經看過該文檔、郵件過濾、爬蟲記錄已經爬過的URL，會有一定誤判，但是不存在一定不存在，存在不一定一定存在。
3.基本使用：bf.add、bf.exists 、bf.mexists
4.參數調優：

1.演算法原理：GeoHash將二維的經緯度數據映射到一維的整數（反向從證書還原有損），所有的坐標都存儲在zset中，score是坐標52位整數，所以可以查看附件的元素（實際會復雜一些）

2.基本使用：geoadd、geodist（距離）、geopos（經緯度）、geohash（位置編碼）、georadiusbymemeber(位置附近)、georadius(經緯附近)
3.注意事項：

1.產生背景：為了取代ziplist，不會有級聯更新的問題，每個節點單獨存在
2.數據結構：

1.數據結構：與zset不同的是zset基於score進行排序，rax基於key進行排序（字典序），rax是基數樹radix tree的特殊結構，與基數樹不同的是節點可以進行壓縮存多個字元

2.使用場景：使用在Stream機構中用於存儲消息隊列

『伍』 redis源碼解讀：單線程的redis是如何實現高速緩存的

redis可能是最近幾年最火的緩存資料庫方案了，在各個高並發領域都有應用。

這篇文章，我們將從源代碼的角度來分析一下，為何如此一個高性能，高應用的緩存，會是單線程的方案，當然一個方案的高性能，高並發是多方面的綜合因素，其它的因素我們將在後續解讀。後續分析主要以LINUX操作系統為基礎，這也是redis應用最廣的平台。

單線程最大的受限是什麼？就是CPU，現在伺服器一般已經是多CPU，而單線程只能使用到其中的一個核。

redis作為一個網路內存緩存資料庫，在實現高性能時，主要有4個點。

1.網路高並發，高流量的數據處理。

一個非同步，高效，且對CPU要求不高的網路模型，這個模型主要是由OS來提供的，目前在LINUX最主流使用的是EPOLL，這個網上介紹很多，主要是基於事件驅動的一個非同步模型。

2.程序內部的合理構架，調用邏輯，內存管理。

redis在採用純C實現時，整體調用邏輯很短，但在內存方面，適當的合並了一些對象和對齊，比如sds等，在底層使用了內存池，在不同情況下使用的不太一樣。

但整體處理上沒有NGINX的內池設計巧妙，當然二者不太一樣，NGINX是基於請求釋放的邏輯來設計的，因此針對請求，可以一次申請大塊，分量使用，再最後統一釋放。

3.數據復制的代價，不管是讀取數據或是寫入數據，一般都是需要有數據復制的過程。

數據復制其實就是一次內存，真正的代價是在於存在大VALUE，當value值長度超過16KB時，性能會開始下降。因為單線程的原因，如果存在一個超大VALUE，比如20MB，則會因為這個請求卡住整個線程，導致後續的請求進不來，雖然後面的請求是能快速處理的小請求。

4.redis中數據結構中演算法的代價，有些結構在大數據量時，代價是很高的。

很多時間，大家忽略了演算法的運算代碼，因為像memcached等這類是完全的KV緩存，不存在什麼演算法，除了一個KEY的查找定位HASH演算法。

而redis不一樣，提供了不少高階的數據對象，這些對象具有上層的一些演算法能力，而這些能力是需要比如GEO模塊。

『陸』 redis做mysql的緩存

redis緩存其實就是把經常訪問的數據放到redis裡面，用戶查詢的時候先去redis查詢，沒有查到就執行sql語句查詢，同時把數據同步到redis裡面。redis只做讀操作，在內存中查詢速度快。

使用redis做緩存必須解決兩個問題，首先就是確定用何種數據結構存儲來自mysql的數據；確定數據結構之後就是需要確定用什麼標識來作為數據的key。
mysql是按照表存儲數據的，這些表是由若干行組成。每一次執行select查詢，mysql都會返回一個結果集，這個結果是由若干行組成的。redis有五種數據結構：列表list，哈希hash，字元串string，集合set，sorted set(有序集合)，對比幾種數據結構，string和hash是比較適合存儲行的數據結構，可以把數據轉成json字元串存入redis。

全量遍歷鍵： keys pattern keys *
有人說 KEYS 相當於關系性數據的庫的 select * ，在生產環境幾乎是要禁用的

不管上面說的對不對， keys 肯定是有風險的。那我們就換一種方案，在存數據的時候。把數據的鍵存一下，也存到redis裡面選hash類型，那麼取的時候就可以直接通過這個hash獲取所有的值，自我感覺非常好用！

『柒』 Redis數據結構和編碼

String/Hash/Set/Zset/List

redis會將常見的值放入一個共享對象中，避免了程序重新分配的麻煩，類似於jvm中的常量池。
預分配的對象如下：

redis內的refcount，如果為0，則表示可以回收。

Redis3.2之前

Redis3.2之後

整體存儲格式：

Redis在存儲集合時，如果集合內只包含整數且數目較少時，會採用IntSet來存儲。

在int16類型的集合內插入一個int32的數據：

當最大元素刪除後，是否需要降級？
不會，為了減少開銷

數據結構

ps： redis對於浮點數類型也是作為字元串保存的，在需要的時候再轉換為浮點數類型

從目前的版本（6.0）來看，List僅支持quickList（之前的版本有linked和ziplist這2種編碼）。

當同時滿足以下2個條件時，使用ziplist：

當同時滿足以下2個條件時，使用intset

tips：對於skipList的編碼格式，其實是同時採用了dict和skiplist的數據結構來存儲
說明：有序集合本身使用dict或skiplist其中一種都可以實現，如果單獨使用dict來實現，那麼查找可以達到O(1)的復雜度，但是每次范圍查詢排序需要進行額外操作；如果單獨使用skiplist，雖然可以使用范圍操作，但是查找復雜度卻是O(logn)，所以redis採用了2種數據結構混合。但雖然同時使用了2種數據結構，但數據其實只有1份，通過指針指向到對應地址。

當同時滿足以下2個條件，使用ziplist編碼：

參考文章： https://www.pdai.tech/md/db/nosql-redis/db-redis-x-redis-ds.html

『捌』 redis緩存原理

1、Redis是一種內存高速cache，如果使用redis緩存，那經常被訪問的內容會被緩存在內存中，需要使用的時候直接從內存調取，不知道比硬碟調取快了多少倍，並且支持復雜的數據結構，應用於許多高並發的場景中。
2、Redis支持主從同步。數據可以從主伺服器向任意數量的從伺服器上同步，從伺服器可以是關聯其他從伺服器的主伺服器。這使得Redis可執行單層樹復制。存檔可以有意無意的對數據進行寫操作。由於完全實現了發布/訂閱機制，使得從資料庫在任何地方同步樹時，可訂閱一個頻道並接收主伺服器完整的消息發布記錄。同步對讀取操作的可擴展性和數據冗餘很有幫助。zset是set的一個升級版本，他在set的基礎上增加了一個順序屬性，這一屬性在添加修改元素的時候可以指定，每次指定後，zset會自動重新按新的值調整順序。可以理解了有兩列的mysql表，一列存value，一列存順序。操作中key理解為zset的名字。
更多關於redis緩存原理，進入：https://www.abcgonglue.com/ask/66eab61616100681.html?zd查看更多內容

『玖』 基於redis做緩存分頁

在實際業務中我們會將一些熱數據緩存到redis裡面，這時候數據量比較大的話，我們就要對這些熱數據進行分頁，分頁的方式有2種：

第一：從redis拿出所有數據後，再做內存分頁（不推薦），熱點數據小的時候可以這樣做，性能相差不是很大，但是當數據量大的時候，分頁期間就會佔用大量內存，或撐爆；

第二：基於redis的數據結構做緩存分頁，這里又分2種

①：基於redis的list數據結構，直接通過list的數據結構，用range方法可以進行分頁，在數據量大的時候，性能也很可觀，但是當存在介面高並發訪問時，這個list可能會無限延長，且裡面的數據會存在很多重復，這就會影響到正常的業務（不是很推薦）；

②：基於redis的ZSet數據結構，通過Zset這個有序集合我們也可以做分頁，同樣也是用range方法，但是這里比較麻煩的是在初始化數據的時候Zset必須存放TypedTuple類型的數據，這個類型是一個value和score的鍵值對，具體可以查網路，這個score的生成比較麻煩我這邊測試時用的是當前數據在這個list的位置，然後Zset是根據這個score值來排序的，默認是從小到大；用這個的好處是，即使在高並發情況下Zset中也不會存在重復數據從而影響正常的業務；而且分頁效率也和list結構差不多；

③：用hash和Zset來一起實現；這個是問了一個朋友和得知的，Zset中存儲有序的id欄位，通過分頁後拿到id，然後再用id去hash中取，感覺應該效率相差不大的，只是中間多了層從hash結構取，還需要維護又一個hash；（為何這樣做我也不清楚）；

貼一張我測試list和ZSet的結果圖

『拾』 redis面試之數據結構

redis是面試中最常問的中間件，關於數據結構主要集中在列舉和用法。下面我們就數據結構和主要的使用方式做一個描述。

大家都知道redis的幾種數據結構，包括string （字元串),hash（哈希），list（列表），set（集合），zset（有序集合）。下面我們來列舉一下關於這幾種結構的常用命令和一些使用場景。

string是redis的最基本的數據類型。

string類型是二進制安全的，也就是說string里可以包含任何的數據類型。

string類型的值最大能存儲512MB

1、 普通的單值緩存

2、對象數據緩存(json格式)

3、分布式鎖的應用

4、計數器的使用，使用INCR和DECR

redis hash 是一個string類型的field(欄位)和value(值)的映射表，很適合存儲對象。

hash最適合的就是做對象緩存

list是redis的字元串列表，可以選擇將值插入到頭部或尾部。

1、 可以利用list的頭部尾部增刪屬性實現棧和隊列

2、 可以用來實現時間軸模型，根據時間依次插入數據，使用LPUSH插入和LRANGE獲取最近范圍的數據

set是redis的無序集合，是通過哈希表實現的，因此任何操作(添加、刪除和測試成員的存在性等)的時間復雜度是O(1)。(無論集合中包含多少元素，時間都是常量)

1、 可以根據set集合的不可重復的特性，統計一些像網站訪問IP啊，訪問用戶啊這些信息，無論訪問多少次，SADD加入的都只有一條。

2、 也可以使用SRANDMEMBER和SPOP獲取數據的隨機性 ，做一些抽獎的小程序等隨機功能

3、 作為集合，可以利用交並運算等計算一些復雜的邏輯關系，比如說人物關系之間的網路關系。

ZSet和set類似，都是字元串的非重復集合。不同之處在於，ZSet的每個成員都與分數相關，分數是用來進行排序的。然後可以使用分數來取一個范圍內的數

應用場景：

ZSet是有序的集合，可以使用它來做一個排行榜。