正文

redis底層算法（redis底層數(shù)據(jù)如何實現(xiàn)）

發(fā)布時間：2023-03-13 10:15:29 稿源：創(chuàng)意嶺閱讀： 52 問大家

大家好！今天讓創(chuàng)意嶺的小編來大家介紹下關(guān)于redis底層算法的問題，以下是小編對此問題的歸納整理，讓我們一起來看看吧。

ChatGPT國內(nèi)免費在線使用，一鍵生成原創(chuàng)文章、方案、文案、工作計劃、工作報告、論文、代碼、作文、做題和對話答疑等等

只需要輸入關(guān)鍵詞，就能返回你想要的內(nèi)容，越精準(zhǔn)，寫出的就越詳細，有微信小程序端、在線網(wǎng)頁版、PC客戶端

官網(wǎng)：https://ai.de1919.com

本文目錄:

1、Redis高級用法與刪除方式
2、Redis哨兵模式的實現(xiàn)原理
3、redis 數(shù)據(jù)分區(qū)--一致性hash&&虛擬槽分區(qū)
4、Redis hash槽分配

redis底層算法（redis底層數(shù)據(jù)如何實現(xiàn)）

一、Redis高級用法與刪除方式

一、redis為什么這么快

1、完全基于內(nèi)存，絕大部分請求是純粹的內(nèi)存操作，非?？焖?。數(shù)據(jù)存在內(nèi)存中，類似于HashMap，HashMap的優(yōu)勢就是查找和操作的時間復(fù)雜度都是O(1)；

2、數(shù)據(jù)結(jié)構(gòu)簡單，對數(shù)據(jù)操作也簡單，Redis中的數(shù)據(jù)結(jié)構(gòu)是專門進行設(shè)計的；

3、采用單線程，避免了不必要的上下文切換和競爭條件，也不存在多進程或者多線程導(dǎo)致的切換而消耗 CPU，不用去考慮各種鎖的問題，不存在加鎖釋放鎖操作，沒有因為可能出現(xiàn)死鎖而導(dǎo)致的性能消耗；

4、使用多路I/O復(fù)用模型，非阻塞IO；

5、使用底層模型不同，它們之間底層實現(xiàn)方式以及與客戶端之間通信的應(yīng)用協(xié)議不一樣，Redis直接自己構(gòu)建了VM 機制，因為一般的系統(tǒng)調(diào)用系統(tǒng)函數(shù)的話，會浪費一定的時間去移動和請求；

以上幾點都比較好理解，下邊我們針對多路 I/O 復(fù)用模型進行簡單的探討：

（1）多路 I/O 復(fù)用模型

多路I/O復(fù)用模型是利用 select、poll、epoll 可以同時監(jiān)察多個流的 I/O 事件的能力，在空閑的時候，會把當(dāng)前線程阻塞掉，當(dāng)有一個或多個流有 I/O 事件時，就從阻塞態(tài)中喚醒，于是程序就會輪詢一遍所有的流（epoll 是只輪詢那些真正發(fā)出了事件的流），并且只依次順序的處理就緒的流，這種做法就避免了大量的無用操作。

這里“多路”指的是多個網(wǎng)絡(luò)連接，“復(fù)用”指的是復(fù)用同一個線程。采用多路 I/O 復(fù)用技術(shù)可以讓單個線程高效的處理多個連接請求（盡量減少網(wǎng)絡(luò) IO 的時間消耗），且 Redis 在內(nèi)存中操作數(shù)據(jù)的速度非?？?，也就是說內(nèi)存內(nèi)的操作不會成為影響Redis性能的瓶頸，主要由以上幾點造就了 Redis 具有很高的吞吐量。

采用單線程，避免了不必要的上下文切換和競爭條件，也不存在多進程或者多線程導(dǎo)致的切換而消耗 CPU，不用去考慮各種鎖的問題，不存在加鎖釋放鎖操作，沒有因為可能出現(xiàn)死鎖而導(dǎo)致的性能消耗；完全基于內(nèi)存，沒有磁盤IO的限制。在redis中對數(shù)據(jù)進行持久化的時候

resp通信協(xié)議

使用底層模型不同，它們之間底層實現(xiàn)方式以及與客戶端之間通信的應(yīng)用協(xié)議不一樣，Redis直接自己構(gòu)建了VM 機制，因為一般的系統(tǒng)調(diào)用系統(tǒng)函數(shù)的話，會浪費一定的時間去移動和請求；

二、高級用法

1、位圖

bitmap：體積小，10M可存儲8千萬bit位，最大允許訪問512M，可存儲40億bit位

2、布隆過濾器

由一串很長的二進制向量組成，可以將其看成一個二進制數(shù)組（里面存放的都為0或者1，初始默認值為0）。向里面添加元素時，會使用多個hash函數(shù)進行計算取模得出一個數(shù)組的下標(biāo)，每個hash都會算出不同的位置，再把這些位置都置為1，就完成了add操作

3、GEO

將指定的地理空間位置（經(jīng)緯度及名稱）添加到指定的key中，必須經(jīng)度在緯度之前。（場景：微信搖一搖；周邊餐飲；快遞距離等）

4、HyperLogLog

用來做基數(shù)統(tǒng)計的算法，HyperLogLog 的優(yōu)點是，在輸入元素的數(shù)量或者體積非常非常大時，計算基數(shù)所需的空間總是固定的、并且是很小的。

HyperLogLog 可以接受多個元素作為輸入，并給出輸入元素的基數(shù)估算值：

• 基數(shù)：集合中不同元素的數(shù)量。比如 {'apple', 'banana', 'cherry', 'banana', 'apple'} 的基數(shù)就是 3 。

• 估算值：算法給出的基數(shù)并不是精確的，可能會比實際稍微多一些或者稍微少一些，但會控制在合

理的范圍之內(nèi)。

HyperLogLog 的優(yōu)點是，即使輸入元素的數(shù)量或者體積非常非常大，計算基數(shù)所需的空間總是固定

的、并且是很小的。

在 Redis 里面，每個 HyperLogLog 鍵只需要花費 12 KB 內(nèi)存，就可以計算接近 2^64 個不同元素的基

數(shù)。這和計算基數(shù)時，元素越多耗費內(nèi)存就越多的集合形成鮮明對比。

但是，因為 HyperLogLog 只會根據(jù)輸入元素來計算基數(shù)，而不會儲存輸入元素本身，所以

HyperLogLog 不能像集合那樣，返回輸入的各個元素。

提問：為什么不使用redis替代MQ

1、redis無法對消息持久化存儲

2、redis沒有提供消息傳輸保障

3、redis協(xié)議支持較少

三、刪除方式

1、被動刪除：惰性刪除

客戶端訪問 key 的時候，redis 對 key 的過期時間進行檢查，如果過期了就立即刪除，不會給你返回任何東西。

2、主動刪除：定期刪除

redis 會將每個設(shè)置了過期時間的 key 放入到一個獨立的字典中，以后會定期遍歷這個字典來刪除到期的 key。

3、主動刪除：redis會周期性的隨機測試一批設(shè)置了過期時間的key并進行處理（redis-3.0.0中默認值是10，代表每秒鐘調(diào)用10次后臺任務(wù)）

4、LRU:這個緩存算法將最近使用的條目存放到靠近緩存頂部的位置。當(dāng)一個新條目被訪問時，LRU將它放置到緩存的頂部。當(dāng)緩存達到極限時，較早之前訪問的條目將從緩存底部開始被移除。這里會使用到昂貴的算法，而且它需要記錄“年齡位”來精確顯示條目是何時被訪問的。此外，當(dāng)一個LRU緩存算法刪除某個條目后，“年齡位”將隨其他條目發(fā)生改變。

5、LFU:這個緩存算法使用一個計數(shù)器來記錄條目被訪問的頻率。通過使用LFU緩存算法，最低訪問數(shù)的條目首先被移除。這個方法并不經(jīng)常使用，因為它無法對一個擁有最初高訪問率之后長時間沒有被訪問的條目緩存負責(zé)。

二、Redis哨兵模式的實現(xiàn)原理

Redis哨兵模式的實現(xiàn)原理。

關(guān)于哨兵的原理，關(guān)鍵是了解以下幾個概念：

定時任務(wù)：每個哨兵節(jié)點維護了3個定時任務(wù)。定時任務(wù)的功能分別如下：通過向主從節(jié)點發(fā)送info命令獲取最新的主從結(jié)構(gòu)；通過發(fā)布訂閱功能獲取其他哨兵節(jié)點的信息；通過向其他節(jié)點發(fā)送ping命令進行心跳檢測，判斷是否下線。

主觀下線：在心跳檢測的定時任務(wù)中，如果其他節(jié)點超過一定時間沒有回復(fù)，哨兵節(jié)點就會將其進行主觀下線。顧名思義，主觀下線的意思是一個哨兵節(jié)點“主觀地”判斷下線；與主觀下線相對應(yīng)的是客觀下線。

客觀下線：哨兵節(jié)點在對主節(jié)點進行主觀下線后，會通過sentinel is-master-down-by-addr命令詢問其他哨兵節(jié)點該主節(jié)點的狀態(tài)；如果判斷主節(jié)點下線的哨兵數(shù)量達到一定數(shù)值，則對該主節(jié)點進行客觀下線。

需要特別注意的是，客觀下線是主節(jié)點才有的概念；如果從節(jié)點和哨兵節(jié)點發(fā)生故障，被哨兵主觀下線后，不會再有后續(xù)的客觀下線和故障轉(zhuǎn)移操作。

選舉領(lǐng)導(dǎo)者哨兵節(jié)點：當(dāng)主節(jié)點被判斷客觀下線以后，各個哨兵節(jié)點會進行協(xié)商，選舉出一個領(lǐng)導(dǎo)者哨兵節(jié)點，并由該領(lǐng)導(dǎo)者節(jié)點對其進行故障轉(zhuǎn)移操作。

監(jiān)視該主節(jié)點的所有哨兵都有可能被選為領(lǐng)導(dǎo)者，選舉使用的算法是Raft算法；Raft算法的基本思路是先到先得：即在一輪選舉中，哨兵A向B發(fā)送成為領(lǐng)導(dǎo)者的申請，如果B沒有同意過其他哨兵，則會同意A成為領(lǐng)導(dǎo)者。選舉的具體過程這里不做詳細描述，一般來說，哨兵選擇的過程很快，誰先完成客觀下線，一般就能成為領(lǐng)導(dǎo)者。

三、redis 數(shù)據(jù)分區(qū)--一致性hash&&虛擬槽分區(qū)

1.節(jié)點區(qū)域分區(qū):

使用特定的數(shù)據(jù),如redis的鍵或用戶ID,再根據(jù)節(jié)點數(shù)量N使用公式:hash(key)%N計算出hash值,用來決定數(shù)據(jù)映射到哪一個節(jié)點上.

這種方案的問題是:

當(dāng)節(jié)點數(shù)量變化時,需要重新計算hash,會導(dǎo)致數(shù)據(jù)的重新遷移.

2.一致性hash算法

一致性hash算法實現(xiàn)思路是為系統(tǒng)中每一個節(jié)點分配一個token,范圍在0~2^32,這些token構(gòu)成一個hash環(huán).數(shù)據(jù)的讀寫執(zhí)行節(jié)點查找操作時,先根據(jù)key計算hash值,然后順時針找到第一個大于等于該hash的token節(jié)點.

好處:

這種方式最大的好處就是,在加入或刪除節(jié)點時,只影響hash環(huán)中相鄰的兩個節(jié)點,對其他節(jié)點無影響.

問題:

3.虛擬槽算法

使用分散度較好的hash函數(shù),將所有的數(shù)據(jù)映射到比如0~16383(2^14)范圍的槽中(slot).這個槽的數(shù)量一般遠遠大于實例的數(shù)量.

槽是集群數(shù)據(jù)管理和遷移的基本單位.采用大范圍槽的主要目的是為了方便數(shù)據(jù)拆分和集群擴展.

每一個實例會映射一部分范圍的槽.

特點:

1.解耦數(shù)據(jù)和節(jié)點之間的關(guān)系,簡化擴容和鎖容的難度

2.節(jié)點自身維護槽的映射關(guān)系,不需要客戶端或代理服務(wù)維護槽分區(qū)的元數(shù)據(jù).

3.支持節(jié)點,槽,鍵之間的映射查詢,用于數(shù)據(jù)路由,在線伸縮燈場景.

HashTags（面試）

Mset k1 v1 k2 v2 k3 v3

通過分片手段，可以將數(shù)據(jù)合理的劃分到不同的節(jié)點上，這本來是一件好事。但是有的時候，我們希望對相關(guān)聯(lián)的業(yè)務(wù)以原子性方式進行操作。舉個簡單的例子

我們在單節(jié)點上執(zhí)行MSET （m表示多個，一次向redis設(shè)置多個key和值）, 它是一個原子性的操作，我們要求所有給定的key要在同一時間內(nèi)被設(shè)置，不能出現(xiàn)某些指定的key被更新另一些指定的key沒有被更新的情況。但是在集群環(huán)境下，我們?nèi)匀豢梢詧?zhí)行MSET命令，但它的操作不在是原子操作，會存在某些指定的key被更新，而另外一些指定的key沒有改變，原因是多個key可能會被分配到不同的機器上。

所以，這里就會存在一個矛盾點，及要求key盡可能的分散在不同機器，又要求某些相關(guān)聯(lián)的key分配到相同機器。

這個也是在面試的時候會容易被問到的內(nèi)容。怎么解決呢？

從前面的分析中我們了解到，分片其實就是一個hash的過程，對key做hash取模然后劃分到不同的機器上。所以為了解決這個問題，我們需要考慮如何讓相關(guān)聯(lián)的key得到的hash值都相同呢？如果key全部相同是不現(xiàn)實的，所以怎么解決呢？在redis中引入了HashTag的概念，可以使得數(shù)據(jù)分布算法可以根據(jù)key的某一個部分進行計算，然后讓相關(guān)的key落到同一個數(shù)據(jù)分片；

舉個簡單的例子，假如對于用戶的信息進行存儲，

redis:store:1001、redis:store:1002

那么通過hashtag的方式，

redis:{store}:1001、redis:{store}:1002; 表示

當(dāng)一個key包含 {} 的時候，就不對整個key做hash，而僅對 {} 包括的字符串做hash。

四、Redis hash槽分配

Redis 集群中內(nèi)置了 16384 個哈希槽，當(dāng)需要在 Redis 集群中放置一個 key-value

時，redis 先對 key 使用 crc16 算法算出一個結(jié)果，然后把結(jié)果對 16384 求余數(shù)，這樣每個 key 都會對應(yīng)一個編號在 0-16383 之間的哈希槽，redis 會根據(jù)節(jié)點數(shù)量大致均等的將哈希槽映射到不同的節(jié)點。Redis 集群沒有使用一致性hash, 而是引入了哈希槽的概念。

Redis 集群有16384個哈希槽,每個key通過CRC16校驗后對16384取模來決定放置哪個槽.集群的每個節(jié)點負責(zé)一部分hash槽。這種結(jié)構(gòu)很容易添加或者刪除節(jié)點，并且無論是添加刪除或者修改某一個節(jié)點，都不會造成集群不可用的狀態(tài)。使用哈希槽的好處就在于可以方便的添加或移除節(jié)點。當(dāng)需要增加節(jié)點時，只需要把其他節(jié)點的某些哈希槽挪到新節(jié)點就可以了；當(dāng)需要移除節(jié)點時，只需要把移除節(jié)點上的哈希槽挪到其他節(jié)點就行了；在這一點上，我們以后新增或移除節(jié)點的時候不用先停掉所有的 redis 服務(wù)。

"用了哈希槽的概念，而沒有用一致性哈希算法，不都是哈希么？這樣做的原因是為什么呢？

"Redis Cluster是自己做的crc16的簡單hash算法，沒有用一致性hash。Redis的作者認為它的crc16(key) mod 16384的效果已經(jīng)不錯了，雖然沒有一致性hash靈活，但實現(xiàn)很簡單，節(jié)點增刪時處理起來也很方便。"為了動態(tài)增刪節(jié)點的時候，不至于丟失數(shù)據(jù)么？"節(jié)點增刪時不丟失數(shù)據(jù)和hash算法沒什么關(guān)系，不丟失數(shù)據(jù)要求的是一份數(shù)據(jù)有多個副本?！斑€有集群總共有2的14次方，16384個哈希槽，那么每一個哈希槽中存的key 和 value是什么？”當(dāng)你往Redis Cluster中加入一個Key時，會根據(jù)crc16(key) mod 16384計算這個key應(yīng)該分布到哪個hash slot中，一個hash slot中會有很多key和value。你可以理解成表的分區(qū)，使用單節(jié)點時的redis時只有一個表，所有的key都放在這個表里；改用Redis Cluster以后會自動為你生成16384個分區(qū)表，你insert數(shù)據(jù)時會根據(jù)上面的簡單算法來決定你的key應(yīng)該存在哪個分區(qū)，每個分區(qū)里有很多key。

以上就是關(guān)于redis底層算法相關(guān)問題的回答。希望能幫到你，如有更多相關(guān)問題，您也可以聯(lián)系我們的客服進行咨詢，客服也會為您講解更多精彩的知識和內(nèi)容。