大廠經(jīng)典面試題:Redis為什么這么快?

有些小伙伴可能還會(huì)有疑問：哈希沖突鏈上的元素只能通過指針逐一查找再操作。當(dāng)往哈希表插入數(shù)據(jù)很多，沖突也會(huì)越多，沖突鏈表就會(huì)越長(zhǎng)，那查詢效率就會(huì)降低了。

為了保持高效，Redis 會(huì)對(duì)哈希表做rehash操作，也就是增加哈希桶，減少?zèng)_突。為了rehash更高效，Redis還默認(rèn)使用了兩個(gè)全局哈希表，一個(gè)用于當(dāng)前使用，稱為主哈希表，一個(gè)用于擴(kuò)容，稱為備用哈希表。

跳躍表

跳躍表是Redis特有的數(shù)據(jù)結(jié)構(gòu)，它其實(shí)就是在鏈表的基礎(chǔ)上，增加多級(jí)索引，以提高查找效率。跳躍表的簡(jiǎn)單原理圖如下:

• 每一層都有一條有序的鏈表，最底層的鏈表包含了所有的元素。
• 跳躍表支持平均 O（logN）,最壞 O（N）復(fù)雜度的節(jié)點(diǎn)查找，還可以通過順序性操作批量處理節(jié)點(diǎn)。

壓縮列表ziplist

壓縮列表ziplist是列表鍵和字典鍵的的底層實(shí)現(xiàn)之一。它是由一系列特殊編碼的內(nèi)存塊構(gòu)成的列表， 一個(gè)ziplist可以包含多個(gè)entry， 每個(gè)entry可以保存一個(gè)長(zhǎng)度受限的字符數(shù)組或者整數(shù)，如下：

• zlbytes ：記錄整個(gè)壓縮列表占用的內(nèi)存字節(jié)數(shù)
• zltail: 尾節(jié)點(diǎn)至起始節(jié)點(diǎn)的偏移量
• zllen : 記錄整個(gè)壓縮列表包含的節(jié)點(diǎn)數(shù)量
• entryX: 壓縮列表包含的各個(gè)節(jié)點(diǎn)
• zlend : 特殊值0xFF(十進(jìn)制255)，用于標(biāo)記壓縮列表末端

由于內(nèi)存是連續(xù)分配的，所以遍歷速度很快。。

合理的數(shù)據(jù)編碼

Redis支持多種數(shù)據(jù)基本類型，每種基本類型對(duì)應(yīng)不同的數(shù)據(jù)結(jié)構(gòu)，每種數(shù)據(jù)結(jié)構(gòu)對(duì)應(yīng)不一樣的編碼。為了提高性能，Redis設(shè)計(jì)者總結(jié)出，數(shù)據(jù)結(jié)構(gòu)最適合的編碼搭配。

Redis是使用對(duì)象（redisObject）來表示數(shù)據(jù)庫(kù)中的鍵值，當(dāng)我們?cè)?Redis 中創(chuàng)建一個(gè)鍵值對(duì)時(shí)，至少創(chuàng)建兩個(gè)對(duì)象，一個(gè)對(duì)象是用做鍵值對(duì)的鍵對(duì)象，另一個(gè)是鍵值對(duì)的值對(duì)象。

//關(guān)注公眾號(hào)：撿田螺的小男孩
typedef?struct?redisObject{
????//類型
???unsigned?type:4;
???//編碼
???unsigned?encoding:4;
???//指向底層數(shù)據(jù)結(jié)構(gòu)的指針
???void?*ptr;
????//...
?}robj;

redisObject中，type 對(duì)應(yīng)的是對(duì)象類型，包含String對(duì)象、List對(duì)象、Hash對(duì)象、Set對(duì)象、zset對(duì)象。encoding 對(duì)應(yīng)的是編碼。

• String：如果存儲(chǔ)數(shù)字的話，是用int類型的編碼;如果存儲(chǔ)非數(shù)字，小于等于39字節(jié)的字符串，是embstr；大于39個(gè)字節(jié)，則是raw編碼。
• List：如果列表的元素個(gè)數(shù)小于512個(gè)，列表每個(gè)元素的值都小于64字節(jié)（默認(rèn)），使用ziplist編碼，否則使用linkedlist編碼
• Hash：哈希類型元素個(gè)數(shù)小于512個(gè)，所有值小于64字節(jié)的話，使用ziplist編碼,否則使用hashtable編碼。
• Set：如果集合中的元素都是整數(shù)且元素個(gè)數(shù)小于512個(gè)，使用intset編碼，否則使用hashtable編碼。
• Zset：當(dāng)有序集合的元素個(gè)數(shù)小于128個(gè)，每個(gè)元素的值小于64字節(jié)時(shí)，使用ziplist編碼，否則使用skiplist（跳躍表）編碼

合理的線程模型

單線程模型：避免了上下文切換

Redis是單線程的，其實(shí)是指Redis的網(wǎng)絡(luò)IO和鍵值對(duì)讀寫是由一個(gè)線程來完成的。但Redis的其他功能，比如持久化、異步刪除、集群數(shù)據(jù)同步等等，實(shí)際是由額外的線程執(zhí)行的。

Redis的單線程模型，避免了CPU不必要的上下文切換和競(jìng)爭(zhēng)鎖的消耗。也正因?yàn)槭菃尉€程，如果某個(gè)命令執(zhí)行過長(zhǎng)（如hgetall命令），會(huì)造成阻塞。Redis是面向快速執(zhí)行場(chǎng)景的內(nèi)存數(shù)據(jù)庫(kù)，所以要慎用如lrange和smembers、hgetall等命令。

什么是上下文切換？舉個(gè)粟子：

★

• 比如你在看一本英文小說，你看到某一頁(yè)，發(fā)現(xiàn)有個(gè)單詞不會(huì)讀，你加了個(gè)書簽，然后去查字典。查完字典后，你回來從書簽?zāi)抢锢^續(xù)開始讀，這個(gè)流程就很舒暢。
• 如果你一個(gè)人讀這本書，肯定沒啥問題。但是如果你去查字典的時(shí)候，別的小伙伴翻了一下你的書，然后溜了。你再回來看的時(shí)候，發(fā)現(xiàn)書不是你看的那一頁(yè)了，你得花時(shí)間找到你的那一頁(yè)。
• 一本書，你一個(gè)人怎么看怎么打標(biāo)簽都沒事，但是人多了翻來翻去，這本書各種標(biāo)記就很亂了。可能這個(gè)解釋很粗糙，但是道理應(yīng)該是一樣的。

”

I/O 多路復(fù)用

什么是I/O多路復(fù)用？

• I/O ：網(wǎng)絡(luò) I/O
• 多路 ：多個(gè)網(wǎng)絡(luò)連接
• 復(fù)用：復(fù)用同一個(gè)線程。
• IO多路復(fù)用其實(shí)就是一種同步IO模型，它實(shí)現(xiàn)了一個(gè)線程可以監(jiān)視多個(gè)文件句柄；一旦某個(gè)文件句柄就緒，就能夠通知應(yīng)用程序進(jìn)行相應(yīng)的讀寫操作；而沒有文件句柄就緒時(shí),就會(huì)阻塞應(yīng)用程序，交出cpu。

★

多路I/O復(fù)用技術(shù)可以讓單個(gè)線程高效的處理多個(gè)連接請(qǐng)求，而Redis使用用epoll作為I/O多路復(fù)用技術(shù)的實(shí)現(xiàn)。并且Redis自身的事件處理模型將epoll中的連接、讀寫、關(guān)閉都轉(zhuǎn)換為事件，不在網(wǎng)絡(luò)I/O上浪費(fèi)過多的時(shí)間。

”

虛擬內(nèi)存機(jī)制

Redis直接自己構(gòu)建了VM機(jī)制 ，不會(huì)像一般的系統(tǒng)會(huì)調(diào)用系統(tǒng)函數(shù)處理，會(huì)浪費(fèi)一定的時(shí)間去移動(dòng)和請(qǐng)求。

Redis的虛擬內(nèi)存機(jī)制是啥呢？

★

虛擬內(nèi)存機(jī)制就是暫時(shí)把不經(jīng)常訪問的數(shù)據(jù)(冷數(shù)據(jù))從內(nèi)存交換到磁盤中，從而騰出寶貴的內(nèi)存空間用于其它需要訪問的數(shù)據(jù)(熱數(shù)據(jù))。通過VM功能可以實(shí)現(xiàn)冷熱數(shù)據(jù)分離，使熱數(shù)據(jù)仍在內(nèi)存中、冷數(shù)據(jù)保存到磁盤。這樣就可以避免因?yàn)閮?nèi)存不足而造成訪問速度下降的問題。

”

Redis之VM機(jī)制: https://www.codenong.com/cs106843764/

一文揭秘單線程的Redis為什么這么快?: https://zhuanlan.zhihu.com/p/57089960

洞察|Redis是單線程的，但Redis為什么這么快？: https://zhuanlan.zhihu.com/p/42272979

跪求大家?guī)兔c(diǎn)個(gè)贊、在看、轉(zhuǎn)發(fā)，感謝！