正文

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

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

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

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

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

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

本文目錄:

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

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

一、Redis高級(jí)用法與刪除方式

一、redis為什么這么快

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

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

3、采用單線程，避免了不必要的上下文切換和競(jìng)爭(zhēng)條件，也不存在多進(jìn)程或者多線程導(dǎo)致的切換而消耗 CPU，不用去考慮各種鎖的問(wèn)題，不存在加鎖釋放鎖操作，沒(méi)有因?yàn)榭赡艹霈F(xiàn)死鎖而導(dǎo)致的性能消耗；

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

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

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

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

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

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

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

resp通信協(xié)議

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

二、高級(jí)用法

1、位圖

bitmap：體積小，10M可存儲(chǔ)8千萬(wàn)bit位，最大允許訪問(wèn)512M，可存儲(chǔ)40億bit位

2、布隆過(guò)濾器

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

3、GEO

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

4、HyperLogLog

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

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

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

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

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

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

的、并且是很小的。

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

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

但是，因?yàn)?HyperLogLog 只會(huì)根據(jù)輸入元素來(lái)計(jì)算基數(shù)，而不會(huì)儲(chǔ)存輸入元素本身，所以

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

提問(wèn)：為什么不使用redis替代MQ

1、redis無(wú)法對(duì)消息持久化存儲(chǔ)

2、redis沒(méi)有提供消息傳輸保障

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

三、刪除方式

1、被動(dòng)刪除：惰性刪除

客戶端訪問(wèn) key 的時(shí)候，redis 對(duì) key 的過(guò)期時(shí)間進(jìn)行檢查，如果過(guò)期了就立即刪除，不會(huì)給你返回任何東西。

2、主動(dòng)刪除：定期刪除

redis 會(huì)將每個(gè)設(shè)置了過(guò)期時(shí)間的 key 放入到一個(gè)獨(dú)立的字典中，以后會(huì)定期遍歷這個(gè)字典來(lái)刪除到期的 key。

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

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

5、LFU:這個(gè)緩存算法使用一個(gè)計(jì)數(shù)器來(lái)記錄條目被訪問(wèn)的頻率。通過(guò)使用LFU緩存算法，最低訪問(wèn)數(shù)的條目首先被移除。這個(gè)方法并不經(jīng)常使用，因?yàn)樗鼰o(wú)法對(duì)一個(gè)擁有最初高訪問(wèn)率之后長(zhǎng)時(shí)間沒(méi)有被訪問(wèn)的條目緩存負(fù)責(zé)。

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

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

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

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

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

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

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

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

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

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

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

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

這種方案的問(wèn)題是:

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

2.一致性hash算法

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

好處:

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

問(wèn)題:

3.虛擬槽算法

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

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

每一個(gè)實(shí)例會(huì)映射一部分范圍的槽.

特點(diǎn):

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

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

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

HashTags（面試）

Mset k1 v1 k2 v2 k3 v3

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

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

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

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

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

舉個(gè)簡(jiǎn)單的例子，假如對(duì)于用戶的信息進(jìn)行存儲(chǔ)，

redis:store:1001、redis:store:1002

那么通過(guò)hashtag的方式，

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

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

四、Redis hash槽分配

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

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

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

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

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

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