Redis_第5章_ Redis原理篇
文章目錄
- Redis_第5章_ Redis原理篇
- Redis原理篇
-
- 1、原理篇-Redis資料結構
-
- 1.1 Redis資料結構-動态字元串
- 1.2 Redis資料結構-intset
- 1.3 Redis資料結構-Dict
- 1.4 Redis資料結構-ZipList
- 1.5 Redis資料結構-ZipList的連鎖更新問題
- 1.6 Redis資料結構-QuickList
- 1.7 Redis資料結構-RedisObject
- 1.8 Redis資料結構-String
- 1.9 Redis資料結構-List
- 2.0 Redis資料結構-Set結構
- 2.1、Redis資料結構-ZSET
- 2.2 、Redis資料結構-Hash
- 2、原理篇-Redis網絡模型
-
- 2.1 使用者空間和核心态空間
- 2.2.網絡模型-阻塞IO
- 2.3 網絡模型-非阻塞IO
- 2.4 網絡模型-IO多路複用
- 2.5 網絡模型-IO多路複用-select方式
- 2.6 網絡模型-IO多路複用模型-poll模式
- 2.7 網絡模型-IO多路複用模型-epoll函數
- 2.8、網絡模型-epoll中的ET和LT
- 2.9 網絡模型-基于epoll的伺服器端流程
- 2.10 、網絡模型-信号驅動
-
- 2.10.1 異步IO
- 2.10.2 對比
- 2.11 、網絡模型-Redis是單線程的嗎?為什麼使用單線程
- 2.12 、Redis的單線程模型-Redis單線程和多線程網絡模型變更
- 3、Redis通信協定-RESP協定
-
- 3.1、Redis通信協定-基于Socket自定義Redis的用戶端
- 3.2、Redis記憶體回收-過期key處理
- 3.3 Redis記憶體回收-記憶體淘汰政策
- 4、結束語
Redis原理篇
1、原理篇-Redis資料結構
1.1 Redis資料結構-動态字元串
我們都知道Redis中儲存的Key是字元串,value往往是字元串或者字元串的集合。可見字元串是Redis中最常用的一種資料結構。
不過Redis沒有直接使用C語言中的字元串,因為C語言字元串存在很多問題:
擷取字元串長度的需要通過運算
非二進制安全
不可修改
Redis建構了一種新的字元串結構,稱為簡單動态字元串(Simple Dynamic String),簡稱SDS。
例如,我們執行指令:
那麼Redis将在底層建立兩個SDS,其中一個是包含“name”的SDS,另一個是包含“虎哥”的SDS。
Redis是C語言實作的,其中SDS是一個結構體,源碼如下:
例如,一個包含字元串“name”的sds結構如下:
SDS之是以叫做動态字元串,是因為它具備動态擴容的能力,例如一個内容為“hi”的SDS:
假如我們要給SDS追加一段字元串“,Amy”,這裡首先會申請新記憶體空間:
如果新字元串小于1M,則新空間為擴充後字元串長度的兩倍+1;
如果新字元串大于1M,則新空間為擴充後字元串長度+1M+1。稱為記憶體預配置設定。
1.2 Redis資料結構-intset
IntSet是Redis中set集合的一種實作方式,基于整數數組來實作,并且具備長度可變、有序等特征。
結構如下:
其中的encoding包含三種模式,表示存儲的整數大小不同:
為了友善查找,Redis會将intset中所有的整數按照升序依次儲存在contents數組中,結構如圖:
現在,數組中每個數字都在int16_t的範圍内,是以采用的編碼方式是INTSET_ENC_INT16,每部分占用的位元組大小為:
encoding:4位元組
length:4位元組
contents:2位元組 * 3 = 6位元組
我們向該其中添加一個數字:50000,這個數字超出了int16_t的範圍,intset會自動更新編碼方式到合适的大小。
以目前案例來說流程如下:
- 更新編碼為INTSET_ENC_INT32, 每個整數占4位元組,并按照新的編碼方式及元素個數擴容數組
- 倒序依次将數組中的元素拷貝到擴容後的正确位置
- 将待添加的元素放入數組末尾
- 最後,将inset的encoding屬性改為INTSET_ENC_INT32,将length屬性改為4
源碼如下:
小總結:
Intset可以看做是特殊的整數數組,具備一些特點:
- Redis會確定Intset中的元素唯一、有序
- 具備類型更新機制,可以節省記憶體空間
- 底層采用二分查找方式來查詢
1.3 Redis資料結構-Dict
我們知道Redis是一個鍵值型(Key-Value Pair)的資料庫,我們可以根據鍵實作快速的增删改查。而鍵與值的映射關系正是通過Dict來實作的。
Dict由三部分組成,分别是:哈希表(DictHashTable)、哈希節點(DictEntry)、字典(Dict)
當我們向Dict添加鍵值對時,Redis首先根據key計算出hash值(h),然後利用 h & sizemask來計算元素應該存儲到數組中的哪個索引位置。我們存儲k1=v1,假設k1的哈希值h =1,則1&3 =1,是以k1=v1要存儲到數組角标1位置。
Dict由三部分組成,分别是:哈希表(DictHashTable)、哈希節點(DictEntry)、字典(Dict)
Dict的擴容
Dict中的HashTable就是數組結合單向連結清單的實作,當集合中元素較多時,必然導緻哈希沖突增多,連結清單過長,則查詢效率會大大降低。
Dict在每次新增鍵值對時都會檢查負載因子(LoadFactor = used/size) ,滿足以下兩種情況時會觸發哈希表擴容:
哈希表的 LoadFactor >= 1,并且伺服器沒有執行 BGSAVE 或者 BGREWRITEAOF 等背景程序;
哈希表的 LoadFactor > 5 ;
Dict的rehash
不管是擴容還是收縮,必定會建立新的哈希表,導緻哈希表的size和sizemask變化,而key的查詢與sizemask有關。是以必須對哈希表中的每一個key重新計算索引,插入新的哈希表,這個過程稱為rehash。過程是這樣的:
- 計算新hash表的realeSize,值取決于目前要做的是擴容還是收縮:
- 如果是擴容,則新size為第一個大于等于dict.ht[0].used + 1的2^n
- 如果是收縮,則新size為第一個大于等于dict.ht[0].used的2^n (不得小于4)
- 按照新的realeSize申請記憶體空間,建立dictht,并指派給dict.ht[1]
- 設定dict.rehashidx = 0,标示開始rehash
- 将dict.ht[0]中的每一個dictEntry都rehash到dict.ht[1]
- 将dict.ht[1]指派給dict.ht[0],給dict.ht[1]初始化為空哈希表,釋放原來的dict.ht[0]的記憶體
- 将rehashidx指派為-1,代表rehash結束
- 在rehash過程中,新增操作,則直接寫入ht[1],查詢、修改和删除則會在dict.ht[0]和dict.ht[1]依次查找并執行。這樣可以確定ht[0]的資料隻減不增,随着rehash最終為空
整個過程可以描述成:
小總結:
Dict的結構:
- 類似java的HashTable,底層是數組加連結清單來解決哈希沖突
- Dict包含兩個哈希表,ht[0]平常用,ht[1]用來rehash
Dict的伸縮:
- 當LoadFactor大于5或者LoadFactor大于1并且沒有子程序任務時,Dict擴容
- 當LoadFactor小于0.1時,Dict收縮
- 擴容大小為第一個大于等于used + 1的2^n
- 收縮大小為第一個大于等于used 的2^n
- Dict采用漸進式rehash,每次通路Dict時執行一次rehash
- rehash時ht[0]隻減不增,新增操作隻在ht[1]執行,其它操作在兩個哈希表
1.4 Redis資料結構-ZipList
ZipList 是一種特殊的“雙端連結清單” ,由一系列特殊編碼的連續記憶體塊組成。可以在任意一端進行壓入/彈出操作, 并且該操作的時間複雜度為 O(1)。
屬性 | 類型 | 長度 | 用途 |
---|---|---|---|
zlbytes | uint32_t | 4 位元組 | 記錄整個壓縮清單占用的記憶體位元組數 |
zltail | uint32_t | 4 位元組 | 記錄壓縮清單表尾節點距離壓縮清單的起始位址有多少位元組,通過這個偏移量,可以确定表尾節點的位址。 |
zllen | uint16_t | 2 位元組 | 記錄了壓縮清單包含的節點數量。 最大值為UINT16_MAX (65534),如果超過這個值,此處會記錄為65535,但節點的真實數量需要周遊整個壓縮清單才能計算得出。 |
entry | 清單節點 | 不定 | 壓縮清單包含的各個節點,節點的長度由節點儲存的内容決定。 |
zlend | uint8_t | 1 位元組 | 特殊值 0xFF (十進制 255 ),用于标記壓縮清單的末端。 |
ZipListEntry
ZipList 中的Entry并不像普通連結清單那樣記錄前後節點的指針,因為記錄兩個指針要占用16個位元組,浪費記憶體。而是采用了下面的結構:
- previous_entry_length:前一節點的長度,占1個或5個位元組。
- 如果前一節點的長度小于254位元組,則采用1個位元組來儲存這個長度值
- 如果前一節點的長度大于254位元組,則采用5個位元組來儲存這個長度值,第一個位元組為0xfe,後四個位元組才是真實長度資料
- encoding:編碼屬性,記錄content的資料類型(字元串還是整數)以及長度,占用1個、2個或5個位元組
- contents:負責儲存節點的資料,可以是字元串或整數
ZipList中所有存儲長度的數值均采用小端位元組序,即低位位元組在前,高位位元組在後。例如:數值0x1234,采用小端位元組序後實際存儲值為:0x3412
Encoding編碼
ZipListEntry中的encoding編碼分為字元串和整數兩種:
字元串:如果encoding是以“00”、“01”或者“10”開頭,則證明content是字元串
編碼 | 編碼長度 | 字元串大小 |
---|---|---|
|00pppppp| | 1 bytes | <= 63 bytes |
|01pppppp|qqqqqqqq| | 2 bytes | <= 16383 bytes |
|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| | 5 bytes | <= 4294967295 bytes |
例如,我們要儲存字元串:“ab”和 “bc”
ZipListEntry中的encoding編碼分為字元串和整數兩種:
- 整數:如果encoding是以“11”開始,則證明content是整數,且encoding固定隻占用1個位元組
編碼 | 編碼長度 | 整數類型 |
---|---|---|
11000000 | 1 | int16_t(2 bytes) |
11010000 | 1 | int32_t(4 bytes) |
11100000 | 1 | int64_t(8 bytes) |
11110000 | 1 | 24位有符整數(3 bytes) |
11111110 | 1 | 8位有符整數(1 bytes) |
1111xxxx | 1 | 直接在xxxx位置儲存數值,範圍從0001~1101,減1後結果為實際值 |
1.5 Redis資料結構-ZipList的連鎖更新問題
ZipList的每個Entry都包含previous_entry_length來記錄上一個節點的大小,長度是1個或5個位元組:
如果前一節點的長度小于254位元組,則采用1個位元組來儲存這個長度值
如果前一節點的長度大于等于254位元組,則采用5個位元組來儲存這個長度值,第一個位元組為0xfe,後四個位元組才是真實長度資料
現在,假設我們有N個連續的、長度為250~253位元組之間的entry,是以entry的previous_entry_length屬性用1個位元組即可表示,如圖所示:
ZipList這種特殊情況下産生的連續多次空間擴充操作稱之為連鎖更新(Cascade Update)。新增、删除都可能導緻連鎖更新的發生。
小總結:
ZipList特性:
- 壓縮清單的可以看做一種連續記憶體空間的"雙向連結清單"
- 清單的節點之間不是通過指針連接配接,而是記錄上一節點和本節點長度來尋址,記憶體占用較低
- 如果清單資料過多,導緻連結清單過長,可能影響查詢性能
- 增或删較大資料時有可能發生連續更新問題
1.6 Redis資料結構-QuickList
問題1:ZipList雖然節省記憶體,但申請記憶體必須是連續空間,如果記憶體占用較多,申請記憶體效率很低。怎麼辦?
答:為了緩解這個問題,我們必須限制ZipList的長度和entry大小。
問題2:但是我們要存儲大量資料,超出了ZipList最佳的上限該怎麼辦?
答:我們可以建立多個ZipList來分片存儲資料。
問題3:資料拆分後比較分散,不友善管理和查找,這多個ZipList如何建立聯系?
答:Redis在3.2版本引入了新的資料結構QuickList,它是一個雙端連結清單,隻不過連結清單中的每個節點都是一個ZipList。
為了避免QuickList中的每個ZipList中entry過多,Redis提供了一個配置項:list-max-ziplist-size來限制。
如果值為正,則代表ZipList的允許的entry個數的最大值
如果值為負,則代表ZipList的最大記憶體大小,分5種情況:
- -1:每個ZipList的記憶體占用不能超過4kb
- -2:每個ZipList的記憶體占用不能超過8kb
- -3:每個ZipList的記憶體占用不能超過16kb
- -4:每個ZipList的記憶體占用不能超過32kb
- -5:每個ZipList的記憶體占用不能超過64kb
其預設值為 -2:
以下是QuickList的和QuickListNode的結構源碼:
我們接下來用一段流程圖來描述目前的這個結構
總結:
QuickList的特點:
- 是一個節點為ZipList的雙端連結清單
- 節點采用ZipList,解決了傳統連結清單的記憶體占用問題
- 控制了ZipList大小,解決連續記憶體空間申請效率問題
- 中間節點可以壓縮,進一步節省了記憶體
1.7 Redis資料結構-SkipList
SkipList(跳表)首先是連結清單,但與傳統連結清單相比有幾點差異:
元素按照升序排列存儲
節點可能包含多個指針,指針跨度不同。
SkipList(跳表)首先是連結清單,但與傳統連結清單相比有幾點差異:
元素按照升序排列存儲
節點可能包含多個指針,指針跨度不同。
SkipList(跳表)首先是連結清單,但與傳統連結清單相比有幾點差異:
元素按照升序排列存儲
節點可能包含多個指針,指針跨度不同。
小總結:
SkipList的特點:
- 跳躍表是一個雙向連結清單,每個節點都包含score和ele值
- 節點按照score值排序,score值一樣則按照ele字典排序
- 每個節點都可以包含多層指針,層數是1到32之間的随機數
- 不同層指針到下一個節點的跨度不同,層級越高,跨度越大
- 增删改查效率與紅黑樹基本一緻,實作卻更簡單
1.7 Redis資料結構-RedisObject
Redis中的任意資料類型的鍵和值都會被封裝為一個RedisObject,也叫做Redis對象,源碼如下:
1、什麼是redisObject:
從Redis的使用者的角度來看,⼀個Redis節點包含多個database(非cluster模式下預設是16個,cluster模式下隻能是1個),而一個database維護了從key space到object space的映射關系。這個映射關系的key是string類型,⽽value可以是多種資料類型,比如:
string, list, hash、set、sorted set等。我們可以看到,key的類型固定是string,而value可能的類型是多個。
⽽從Redis内部實作的⾓度來看,database内的這個映射關系是用⼀個dict來維護的。dict的key固定用⼀種資料結構來表達就夠了,這就是動态字元串sds。而value則比較複雜,為了在同⼀個dict内能夠存儲不同類型的value,這就需要⼀個通⽤的資料結構,這個通用的資料結構就是robj,全名是redisObject。
Redis的編碼方式
Redis中會根據存儲的資料類型不同,選擇不同的編碼方式,共包含11種不同類型:
編号 | 編碼方式 | 說明 |
---|---|---|
OBJ_ENCODING_RAW | raw編碼動态字元串 | |
1 | OBJ_ENCODING_INT | long類型的整數的字元串 |
2 | OBJ_ENCODING_HT | hash表(字典dict) |
3 | OBJ_ENCODING_ZIPMAP | 已廢棄 |
4 | OBJ_ENCODING_LINKEDLIST | 雙端連結清單 |
5 | OBJ_ENCODING_ZIPLIST | 壓縮清單 |
6 | OBJ_ENCODING_INTSET | 整數集合 |
7 | OBJ_ENCODING_SKIPLIST | 跳表 |
8 | OBJ_ENCODING_EMBSTR | embstr的動态字元串 |
9 | OBJ_ENCODING_QUICKLIST | 快速清單 |
10 | OBJ_ENCODING_STREAM | Stream流 |
五種資料結構
Redis中會根據存儲的資料類型不同,選擇不同的編碼方式。每種資料類型的使用的編碼方式如下:
資料類型 | 編碼方式 |
---|---|
OBJ_STRING | int、embstr、raw |
OBJ_LIST | LinkedList和ZipList(3.2以前)、QuickList(3.2以後) |
OBJ_SET | intset、HT |
OBJ_ZSET | ZipList、HT、SkipList |
OBJ_HASH | ZipList、HT |
1.8 Redis資料結構-String
String是Redis中最常見的資料存儲類型:
其基本編碼方式是RAW,基于簡單動态字元串(SDS)實作,存儲上限為512mb。
如果存儲的SDS長度小于44位元組,則會采用EMBSTR編碼,此時object head與SDS是一段連續空間。申請記憶體時
隻需要調用一次記憶體配置設定函數,效率更高。
(1)底層實作⽅式:動态字元串sds 或者 long
String的内部存儲結構⼀般是sds(Simple Dynamic String,可以動态擴充記憶體),但是如果⼀個String類型的value的值是數字,那麼Redis内部會把它轉成long類型來存儲,從⽽減少記憶體的使用。
如果存儲的字元串是整數值,并且大小在LONG_MAX範圍内,則會采用INT編碼:直接将資料儲存在RedisObject的ptr指針位置(剛好8位元組),不再需要SDS了。
确切地說,String在Redis中是⽤⼀個robj來表示的。
用來表示String的robj可能編碼成3種内部表⽰:OBJ_ENCODING_RAW,OBJ_ENCODING_EMBSTR,OBJ_ENCODING_INT。
其中前兩種編碼使⽤的是sds來存儲,最後⼀種OBJ_ENCODING_INT編碼直接把string存成了long型。
在對string進行incr, decr等操作的時候,如果它内部是OBJ_ENCODING_INT編碼,那麼可以直接行加減操作;如果它内部是OBJ_ENCODING_RAW或OBJ_ENCODING_EMBSTR編碼,那麼Redis會先試圖把sds存儲的字元串轉成long型,如果能轉成功,再進行加減操作。對⼀個内部表示成long型的string執行append, setbit, getrange這些指令,針對的仍然是string的值(即⼗進制表示的字元串),而不是針對内部表⽰的long型進⾏操作。比如字元串”32”,如果按照字元數組來解釋,它包含兩個字元,它們的ASCII碼分别是0x33和0x32。當我們執行指令setbit key 7 0的時候,相當于把字元0x33變成了0x32,這樣字元串的值就變成了”22”。⽽如果将字元串”32”按照内部的64位long型來解釋,那麼它是0x0000000000000020,在這個基礎上執⾏setbit位操作,結果就完全不對了。是以,在這些指令的實作中,會把long型先轉成字元串再進行相應的操作。
1.9 Redis資料結構-List
Redis的List類型可以從首、尾操作清單中的元素:
哪一個資料結構能滿足上述特征?
- LinkedList :普通連結清單,可以從雙端通路,記憶體占用較高,記憶體碎片較多
- ZipList :壓縮清單,可以從雙端通路,記憶體占用低,存儲上限低
- QuickList:LinkedList + ZipList,可以從雙端通路,記憶體占用較低,包含多個ZipList,存儲上限高
Redis的List結構類似一個雙端連結清單,可以從首、尾操作清單中的元素:
在3.2版本之前,Redis采用ZipList和LinkedList來實作List,當元素數量小于512并且元素大小小于64位元組時采用ZipList編碼,超過則采用LinkedList編碼。
在3.2版本之後,Redis統一采用QuickList來實作List:
2.0 Redis資料結構-Set結構
Set是Redis中的單列集合,滿足下列特點:
- 不保證有序性
- 保證元素唯一
- 求交集、并集、差集
可以看出,Set對查詢元素的效率要求非常高,思考一下,什麼樣的資料結構可以滿足?
HashTable,也就是Redis中的Dict,不過Dict是雙列集合(可以存鍵、值對)
Set是Redis中的集合,不一定確定元素有序,可以滿足元素唯一、查詢效率要求極高。
為了查詢效率和唯一性,set采用HT編碼(Dict)。Dict中的key用來存儲元素,value統一為null。
當存儲的所有資料都是整數,并且元素數量不超過set-max-intset-entries時,Set會采用IntSet編碼,以節省記憶體
結構如下:
2.1、Redis資料結構-ZSET
ZSet也就是SortedSet,其中每一個元素都需要指定一個score值和member值:
- 可以根據score值排序後
- member必須唯一
- 可以根據member查詢分數
是以,zset底層資料結構必須滿足鍵值存儲、鍵必須唯一、可排序這幾個需求。之前學習的哪種編碼結構可以滿足?
- SkipList:可以排序,并且可以同時存儲score和ele值(member)
- HT(Dict):可以鍵值存儲,并且可以根據key找value
當元素數量不多時,HT和SkipList的優勢不明顯,而且更耗記憶體。是以zset還會采用ZipList結構來節省記憶體,不過需要同時滿足兩個條件:
- 元素數量小于zset_max_ziplist_entries,預設值128
- 每個元素都小于zset_max_ziplist_value位元組,預設值64
ziplist本身沒有排序功能,而且沒有鍵值對的概念,是以需要有zset通過編碼實作:
- ZipList是連續記憶體,是以score和element是緊挨在一起的兩個entry, element在前,score在後
- score越小越接近隊首,score越大越接近隊尾,按照score值升序排列
2.2 、Redis資料結構-Hash
Hash結構與Redis中的Zset非常類似:
- 都是鍵值存儲
- 都需求根據鍵擷取值
- 鍵必須唯一
差別如下:
- zset的鍵是member,值是score;hash的鍵和值都是任意值
- zset要根據score排序;hash則無需排序
(1)底層實作方式:壓縮清單ziplist 或者 字典dict
當Hash中資料項比較少的情況下,Hash底層才⽤壓縮清單ziplist進⾏存儲資料,随着資料的增加,底層的ziplist就可能會轉成dict,具體配置如下:
hash-max-ziplist-entries 512
hash-max-ziplist-value 64
當滿足上面兩個條件其中之⼀的時候,Redis就使⽤dict字典來實作hash。
Redis的hash之是以這樣設計,是因為當ziplist變得很⼤的時候,它有如下幾個缺點:
- 每次插⼊或修改引發的realloc操作會有更⼤的機率造成記憶體拷貝,進而降低性能。
- ⼀旦發生記憶體拷貝,記憶體拷貝的成本也相應增加,因為要拷貝更⼤的⼀塊資料。
- 當ziplist資料項過多的時候,在它上⾯查找指定的資料項就會性能變得很低,因為ziplist上的查找需要進行周遊。
總之,ziplist本來就設計為各個資料項挨在⼀起組成連續的記憶體空間,這種結構并不擅長做修改操作。⼀旦資料發⽣改動,就會引發記憶體realloc,可能導緻記憶體拷貝。
hash結構如下:
zset集合如下:
是以,Hash底層采用的編碼與Zset也基本一緻,隻需要把排序有關的SkipList去掉即可:
Hash結構預設采用ZipList編碼,用以節省記憶體。 ZipList中相鄰的兩個entry 分别儲存field和value
當資料量較大時,Hash結構會轉為HT編碼,也就是Dict,觸發條件有兩個:
- ZipList中的元素數量超過了hash-max-ziplist-entries(預設512)
- ZipList中的任意entry大小超過了hash-max-ziplist-value(預設64位元組)
2、原理篇-Redis網絡模型
2.1 使用者空間和核心态空間
伺服器大多都采用Linux系統,這裡我們以Linux為例來講解:
ubuntu和Centos 都是Linux的發行版,發行版可以看成對linux包了一層殼,任何Linux發行版,其系統核心都是Linux。我們的應用都需要通過Linux核心與硬體互動
使用者的應用,比如redis,mysql等其實是沒有辦法去執行通路我們作業系統的硬體的,是以我們可以通過發行版的這個殼子去通路核心,再通過核心去通路計算機硬體
計算機硬體包括,如cpu,記憶體,網卡等等,核心(通過尋址空間)可以操作硬體的,但是核心需要不同裝置的驅動,有了這些驅動之後,核心就可以去對計算機硬體去進行 記憶體管理,檔案系統的管理,程序的管理等等
我們想要使用者的應用來通路,計算機就必須要通過對外暴露的一些接口,才能通路到,進而簡介的實作對核心的操控,但是核心本身上來說也是一個應用,是以他本身也需要一些記憶體,cpu等裝置資源,使用者應用本身也在消耗這些資源,如果不加任何限制,使用者去操作随意的去操作我們的資源,就有可能導緻一些沖突,甚至有可能導緻我們的系統出現無法運作的問題,是以我們需要把使用者和核心隔離開
程序的尋址空間劃分成兩部分:核心空間、使用者空間
什麼是尋址空間呢?我們的應用程式也好,還是核心空間也好,都是沒有辦法直接去實體記憶體的,而是通過配置設定一些虛拟記憶體映射到實體記憶體中,我們的核心和應用程式去通路虛拟記憶體的時候,就需要一個虛拟位址,這個位址是一個無符号的整數,比如一個32位的作業系統,他的帶寬就是32,他的虛拟位址就是2的32次方,也就是說他尋址的範圍就是0~2的32次方, 這片尋址空間對應的就是2的32個位元組,就是4GB,這個4GB,會有3個GB分給使用者空間,會有1GB給核心系統
在linux中,他們權限分成兩個等級,0和3,使用者空間隻能執行受限的指令(Ring3),而且不能直接調用系統資源,必須通過核心提供的接口來通路核心空間可以執行特權指令(Ring0),調用一切系統資源,是以一般情況下,使用者的操作是運作在使用者空間,而核心運作的資料是在核心空間的,而有的情況下,一個應用程式需要去調用一些特權資源,去調用一些核心空間的操作,是以此時他倆需要在使用者态和核心态之間進行切換。
比如:
Linux系統為了提高IO效率,會在使用者空間和核心空間都加入緩沖區:
寫資料時,要把使用者緩沖資料拷貝到核心緩沖區,然後寫入裝置
讀資料時,要從裝置讀取資料到核心緩沖區,然後拷貝到使用者緩沖區
針對這個操作:我們的使用者在寫讀資料時,會去向核心态申請,想要讀取核心的資料,而核心資料要去等待驅動程式從硬體上讀取資料,當從磁盤上加載到資料之後,核心會将資料寫入到核心的緩沖區中,然後再将資料拷貝到使用者态的buffer中,然後再傳回給應用程式,整體而言,速度慢,就是這個原因,為了加速,我們希望read也好,還是wait for data也最好都不要等待,或者時間盡量的短。
2.2.網絡模型-阻塞IO
在《UNIX網絡程式設計》一書中,總結歸納了5種IO模型:
- 阻塞IO(Blocking IO)
- 非阻塞IO(Nonblocking IO)
- IO多路複用(IO Multiplexing)
- 信号驅動IO(Signal Driven IO)
- 異步IO(Asynchronous IO)
應用程式想要去讀取資料,他是無法直接去讀取磁盤資料的,他需要先到核心裡邊去等待核心操作硬體拿到資料,這個過程就是1,是需要等待的,等到核心從磁盤上把資料加載出來之後,再把這個資料寫給使用者的緩存區,這個過程是2,如果是阻塞IO,那麼整個過程中,使用者從發起讀請求開始,一直到讀取到資料,都是一個阻塞狀态。
具體流程如下圖:
使用者去讀取資料時,會去先發起recvform一個指令,去嘗試從核心上加載資料,如果核心沒有資料,那麼使用者就會等待,此時核心會去從硬體上讀取資料,核心讀取資料之後,會把資料拷貝到使用者态,并且傳回ok,整個過程,都是阻塞等待的,這就是阻塞IO
總結如下:
顧名思義,阻塞IO就是兩個階段都必須阻塞等待:
階段一:
- 使用者程序嘗試讀取資料(比如網卡資料)
- 此時資料尚未到達,核心需要等待資料
- 此時使用者程序也處于阻塞狀态
階段二:
- 資料到達并拷貝到核心緩沖區,代表已就緒
- 将核心資料拷貝到使用者緩沖區
- 拷貝過程中,使用者程序依然阻塞等待
- 拷貝完成,使用者程序解除阻塞,處理資料
可以看到,阻塞IO模型中,使用者程序在兩個階段都是阻塞狀态。
2.3 網絡模型-非阻塞IO
顧名思義,非阻塞IO的recvfrom操作會立即傳回結果而不是阻塞使用者程序。
階段一:
- 使用者程序嘗試讀取資料(比如網卡資料)
- 此時資料尚未到達,核心需要等待資料
- 傳回異常給使用者程序
- 使用者程序拿到error後,再次嘗試讀取
- 循環往複,直到資料就緒
階段二:
- 将核心資料拷貝到使用者緩沖區
- 拷貝過程中,使用者程序依然阻塞等待
- 拷貝完成,使用者程序解除阻塞,處理資料
- 可以看到,非阻塞IO模型中,使用者程序在第一個階段是非阻塞,第二個階段是阻塞狀态。雖然是非阻塞,但性能并沒有得到提高。而且忙等機制會導緻CPU空轉,CPU使用率暴增。
2.4 網絡模型-IO多路複用
無論是阻塞IO還是非阻塞IO,使用者應用在一階段都需要調用recvfrom來擷取資料,差别在于無資料時的處理方案:
如果調用recvfrom時,恰好沒有資料,阻塞IO會使CPU阻塞,非阻塞IO使CPU空轉,都不能充分發揮CPU的作用。
如果調用recvfrom時,恰好有資料,則使用者程序可以直接進入第二階段,讀取并處理資料
是以怎麼看起來以上兩種方式性能都不好
而在單線程情況下,隻能依次處理IO事件,如果正在處理的IO事件恰好未就緒(資料不可讀或不可寫),線程就會被阻塞,所有IO事件都必須等待,性能自然會很差。
就比如服務員給顧客點餐,分兩步:
- 顧客思考要吃什麼(等待資料就緒)
- 顧客想好了,開始點餐(讀取資料)
要提高效率有幾種辦法?
方案一:增加更多服務員(多線程)
方案二:不排隊,誰想好了吃什麼(資料就緒了),服務員就給誰點餐(使用者應用就去讀取資料)
那麼問題來了:使用者程序如何知道核心中資料是否就緒呢?
是以接下來就需要詳細的來解決多路複用模型是如何知道到底怎麼知道核心資料是否就緒的問題了
這個問題的解決依賴于提出的
檔案描述符(File Descriptor):簡稱FD,是一個從0 開始的無符号整數,用來關聯Linux中的一個檔案。在Linux中,一切皆檔案,例如正常檔案、視訊、硬體裝置等,當然也包括網絡套接字(Socket)。
通過FD,我們的網絡模型可以利用一個線程監聽多個FD,并在某個FD可讀、可寫時得到通知,進而避免無效的等待,充分利用CPU資源。
階段一:
- 使用者程序調用select,指定要監聽的FD集合
- 核監聽FD對應的多個socket
- 任意一個或多個socket資料就緒則傳回readable
- 此過程中使用者程序阻塞
階段二:
- 使用者程序找到就緒的socket
- 依次調用recvfrom讀取資料
- 核心将資料拷貝到使用者空間
- 使用者程序處理資料
當使用者去讀取資料的時候,不再去直接調用recvfrom了,而是調用select的函數,select函數會将需要監聽的資料交給核心,由核心去檢查這些資料是否就緒了,如果說這個資料就緒了,就會通知應用程式資料就緒,然後來讀取資料,再從核心中把資料拷貝給使用者态,完成資料處理,如果N多個FD一個都沒處理完,此時就進行等待。
用IO複用模式,可以確定去讀資料的時候,資料是一定存在的,他的效率比原來的阻塞IO和非阻塞IO性能都要高
IO多路複用是利用單個線程來同時監聽多個FD,并在某個FD可讀、可寫時得到通知,進而避免無效的等待,充分利用CPU資源。不過監聽FD的方式、通知的方式又有多種實作,常見的有:
- select
- poll
- epoll
其中select和pool相當于是當被監聽的資料準備好之後,他會把你監聽的FD整個資料都發給你,你需要到整個FD中去找,哪些是處理好了的,需要通過周遊的方式,是以性能也并不是那麼好
而epoll,則相當于核心準備好了之後,他會把準備好的資料,直接發給你,咱們就省去了周遊的動作。
2.5 網絡模型-IO多路複用-select方式
select是Linux最早是由的I/O多路複用技術:
簡單說,就是我們把需要處理的資料封裝成FD,然後在使用者态時建立一個fd的集合(這個集合的大小是要監聽的那個FD的最大值+1,但是大小整體是有限制的 ),這個集合的長度大小是有限制的,同時在這個集合中,标明出來我們要控制哪些資料,
比如要監聽的資料,是1,2,5三個資料,此時會執行select函數,然後将整個fd發給核心态,核心态會去周遊使用者态傳遞過來的資料,如果發現這裡邊都資料都沒有就緒,就休眠,直到有資料準備好時,就會被喚醒,喚醒之後,再次周遊一遍,看看誰準備好了,然後再将處理掉沒有準備好的資料,最後再将這個FD集合寫回到使用者态中去,此時使用者态就知道了,奧,有人準備好了,但是對于使用者态而言,并不知道誰處理好了,是以使用者态也需要去進行周遊,然後找到對應準備好資料的節點,再去發起讀請求,我們會發現,這種模式下他雖然比阻塞IO和非阻塞IO好,但是依然有些麻煩的事情, 比如說頻繁的傳遞fd集合,頻繁的去周遊FD等問題
2.6 網絡模型-IO多路複用模型-poll模式
poll模式對select模式做了簡單改進,但性能提升不明顯,部分關鍵代碼如下:
IO流程:
- 建立pollfd數組,向其中添加關注的fd資訊,數組大小自定義
- 調用poll函數,将pollfd數組拷貝到核心空間,轉連結清單存儲,無上限
- 核心周遊fd,判斷是否就緒
- 資料就緒或逾時後,拷貝pollfd數組到使用者空間,傳回就緒fd數量n
- 使用者程序判斷n是否大于0,大于0則周遊pollfd數組,找到就緒的fd
與select對比:
- select模式中的fd_set大小固定為1024,而pollfd在核心中采用連結清單,理論上無上限
- 監聽FD越多,每次周遊消耗時間也越久,性能反而會下降
2.7 網絡模型-IO多路複用模型-epoll函數
epoll模式是對select和poll的改進,它提供了三個函數:
第一個是:eventpoll的函數,他内部包含兩個東西
一個是:
1、紅黑樹-> 記錄的事要監聽的FD
2、一個是連結清單->一個連結清單,記錄的是就緒的FD
緊接着調用epoll_ctl操作,将要監聽的資料添加到紅黑樹上去,并且給每個fd設定一個監聽函數,這個函數會在fd資料就緒時觸發,就是準備好了,現在就把fd把資料添加到list_head中去
3、調用epoll_wait函數
就去等待,在使用者态建立一個空的events數組,當就緒之後,我們的回調函數會把資料添加到list_head中去,當調用這個函數的時候,會去檢查list_head,當然這個過程需要參考配置的等待時間,可以等一定時間,也可以一直等, 如果在此過程中,檢查到了list_head中有資料會将資料添加到連結清單中,此時将資料放入到events數組中,并且傳回對應的操作的數量,使用者态的此時收到響應後,從events中拿到對應準備好的資料的節點,再去調用方法去拿資料。
小總結:
select模式存在的三個問題:
- 能監聽的FD最大不超過1024
- 每次select都需要把所有要監聽的FD都拷貝到核心空間
- 每次都要周遊所有FD來判斷就緒狀态
poll模式的問題:
- poll利用連結清單解決了select中監聽FD上限的問題,但依然要周遊所有FD,如果監聽較多,性能會下降
epoll模式中如何解決這些問題的?
- 基于epoll執行個體中的紅黑樹儲存要監聽的FD,理論上無上限,而且增删改查效率都非常高
- 每個FD隻需要執行一次epoll_ctl添加到紅黑樹,以後每次epol_wait無需傳遞任何參數,無需重複拷貝FD到核心空間
- 利用ep_poll_callback機制來監聽FD狀态,無需周遊所有FD,是以性能不會随監聽的FD數量增多而下降
2.8、網絡模型-epoll中的ET和LT
當FD有資料可讀時,我們調用epoll_wait(或者select、poll)可以得到通知。但是事件通知的模式有兩種:
- LevelTriggered:簡稱LT,也叫做水準觸發。隻要某個FD中有資料可讀,每次調用epoll_wait都會得到通知。
- EdgeTriggered:簡稱ET,也叫做邊沿觸發。隻有在某個FD有狀态變化時,調用epoll_wait才會被通知。
舉個栗子:
- 假設一個用戶端socket對應的FD已經注冊到了epoll執行個體中
- 用戶端socket發送了2kb的資料
- 服務端調用epoll_wait,得到通知說FD就緒
- 服務端從FD讀取了1kb資料回到步驟3(再次調用epoll_wait,形成循環)
結論
如果我們采用LT模式,因為FD中仍有1kb資料,則第⑤步依然會傳回結果,并且得到通知
如果我們采用ET模式,因為第③步已經消費了FD可讀事件,第⑤步FD狀态沒有變化,是以epoll_wait不會傳回,資料無法讀取,用戶端響應逾時。
2.9 網絡模型-基于epoll的伺服器端流程
我們來梳理一下這張圖
伺服器啟動以後,服務端會去調用epoll_create,建立一個epoll執行個體,epoll執行個體中包含兩個資料
1、紅黑樹(為空):rb_root 用來去記錄需要被監聽的FD
2、連結清單(為空):list_head,用來存放已經就緒的FD
建立好了之後,會去調用epoll_ctl函數,此函數會會将需要監聽的資料添加到rb_root中去,并且對目前這些存在于紅黑樹的節點設定回調函數,當這些被監聽的資料一旦準備完成,就會被調用,而調用的結果就是将紅黑樹的fd添加到list_head中去(但是此時并沒有完成)
3、當第二步完成後,就會調用epoll_wait函數,這個函數會去校驗是否有資料準備完畢(因為資料一旦準備就緒,就會被回調函數添加到list_head中),在等待了一段時間後(可以進行配置),如果等夠了逾時時間,則傳回沒有資料,如果有,則進一步判斷目前是什麼事件,如果是建立連接配接時間,則調用accept() 接受用戶端socket,拿到建立連接配接的socket,然後建立起來連接配接,如果是其他事件,則把資料進行寫出
2.10 、網絡模型-信号驅動
信号驅動IO是與核心建立SIGIO的信号關聯并設定回調,當核心有FD就緒時,會發出SIGIO信号通知使用者,期間使用者應用可以執行其它業務,無需阻塞等待。
階段一:
- 使用者程序調用sigaction,注冊信号處理函數
- 核心傳回成功,開始監聽FD
- 使用者程序不阻塞等待,可以執行其它業務
- 當核心資料就緒後,回調使用者程序的SIGIO處理函數
階段二:
- 收到SIGIO回調信号
- 調用recvfrom,讀取
- 核心将資料拷貝到使用者空間
- 使用者程序處理資料
當有大量IO操作時,信号較多,SIGIO處理函數不能及時處理可能導緻信号隊列溢出,而且核心空間與使用者空間的頻繁信号互動性能也較低。
2.10.1 異步IO
這種方式,不僅僅是使用者态在試圖讀取資料後,不阻塞,而且當核心的資料準備完成後,也不會阻塞
他會由核心将所有資料處理完成後,由核心将資料寫入到使用者态中,然後才算完成,是以性能極高,不會有任何阻塞,全部都由核心完成,可以看到,異步IO模型中,使用者程序在兩個階段都是非阻塞狀态。
2.10.2 對比
最後用一幅圖,來說明他們之間的差別
2.11 、網絡模型-Redis是單線程的嗎?為什麼使用單線程
Redis到底是單線程還是多線程?
- 如果僅僅聊Redis的核心業務部分(指令處理),答案是單線程
- 如果是聊整個Redis,那麼答案就是多線程
在Redis版本疊代過程中,在兩個重要的時間節點上引入了多線程的支援:
- Redis v4.0:引入多線程異步處理一些耗時較舊的任務,例如異步删除指令unlink
- Redis v6.0:在核心網絡模型中引入 多線程,進一步提高對于多核CPU的使用率
是以,對于Redis的核心網絡模型,在Redis 6.0之前确實都是單線程。是利用epoll(Linux系統)這樣的IO多路複用技術在事件循環中不斷處理用戶端情況。
為什麼Redis要選擇單線程?
- 抛開持久化不談,Redis是純 記憶體操作,執行速度非常快,它的性能瓶頸是網絡延遲而不是執行速度,是以多線程并不會帶來巨大的性能提升。
- 多線程會導緻過多的上下文切換,帶來不必要的開銷
- 引入多線程會面臨線程安全問題,必然要引入線程鎖這樣的安全手段,實作複雜度增高,而且性能也會大打折扣
2.12 、Redis的單線程模型-Redis單線程和多線程網絡模型變更
當我們的用戶端想要去連接配接我們伺服器,會去先到IO多路複用模型去進行排隊,會有一個連接配接應答處理器,他會去接受讀請求,然後又把讀請求注冊到具體模型中去,此時這些建立起來的連接配接,如果是用戶端請求處理器去進行執行指令時,他會去把資料讀取出來,然後把資料放入到client中, clinet去解析目前的指令轉化為redis認識的指令,接下來就開始處理這些指令,從redis中的command中找到這些指令,然後就真正的去操作對應的資料了,當資料操作完成後,會去找到指令回複處理器,再由他将資料寫出。
3、Redis通信協定-RESP協定
Redis是一個CS架構的軟體,通信一般分兩步(不包括pipeline和PubSub):
用戶端(client)向服務端(server)發送一條指令
服務端解析并執行指令,傳回響應結果給用戶端
是以用戶端發送指令的格式、服務端響應結果的格式必須有一個規範,這個規範就是通信協定。
而在Redis中采用的是RESP(Redis Serialization Protocol)協定:
Redis 1.2版本引入了RESP協定
Redis 2.0版本中成為與Redis服務端通信的标準,稱為RESP2
Redis 6.0版本中,從RESP2更新到了RESP3協定,增加了更多資料類型并且支援6.0的新特性–用戶端緩存
但目前,預設使用的依然是RESP2協定,也是我們要學習的協定版本(以下簡稱RESP)。
在RESP中,通過首位元組的字元來區分不同資料類型,常用的資料類型包括5種:
單行字元串:首位元組是 ‘+’ ,後面跟上單行字元串,以CRLF( “\r\n” )結尾。例如傳回"OK": “+OK\r\n”
錯誤(Errors):首位元組是 ‘-’ ,與單行字元串格式一樣,隻是字元串是異常資訊,例如:“-Error message\r\n”
數值:首位元組是 ‘:’ ,後面跟上數字格式的字元串,以CRLF結尾。例如:“:10\r\n”
多行字元串:首位元組是 ‘$’ ,表示二進制安全的字元串,最大支援512MB:
如果大小為0,則代表空字元串:“$0\r\n\r\n”
如果大小為-1,則代表不存在:“$-1\r\n”
數組:首位元組是 ‘*’,後面跟上數組元素個數,再跟上元素,元素資料類型不限:
3.1、Redis通信協定-基于Socket自定義Redis的用戶端
Redis支援TCP通信,是以我們可以使用Socket來模拟用戶端,與Redis服務端建立連接配接:
public class Main {
static Socket s;
static PrintWriter writer;
static BufferedReader reader;
public static void main(String[] args) {
try {
// 1.建立連接配接
String host = "192.168.150.101";
int port = 6379;
s = new Socket(host, port);
// 2.擷取輸出流、輸入流
writer = new PrintWriter(new OutputStreamWriter(s.getOutputStream(), StandardCharsets.UTF_8));
reader = new BufferedReader(new InputStreamReader(s.getInputStream(), StandardCharsets.UTF_8));
// 3.送出請求
// 3.1.擷取授權 auth 123321
sendRequest("auth", "123321");
Object obj = handleResponse();
System.out.println("obj = " + obj);
// 3.2.set name 虎哥
sendRequest("set", "name", "虎哥");
// 4.解析響應
obj = handleResponse();
System.out.println("obj = " + obj);
// 3.2.set name 虎哥
sendRequest("get", "name");
// 4.解析響應
obj = handleResponse();
System.out.println("obj = " + obj);
// 3.2.set name 虎哥
sendRequest("mget", "name", "num", "msg");
// 4.解析響應
obj = handleResponse();
System.out.println("obj = " + obj);
} catch (IOException e) {
e.printStackTrace();
} finally {
// 5.釋放連接配接
try {
if (reader != null) reader.close();
if (writer != null) writer.close();
if (s != null) s.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
private static Object handleResponse() throws IOException {
// 讀取首位元組
int prefix = reader.read();
// 判斷資料類型标示
switch (prefix) {
case '+': // 單行字元串,直接讀一行
return reader.readLine();
case '-': // 異常,也讀一行
throw new RuntimeException(reader.readLine());
case ':': // 數字
return Long.parseLong(reader.readLine());
case '$': // 多行字元串
// 先讀長度
int len = Integer.parseInt(reader.readLine());
if (len == -1) {
return null;
}
if (len == 0) {
return "";
}
// 再讀資料,讀len個位元組。我們假設沒有特殊字元,是以讀一行(簡化)
return reader.readLine();
case '*':
return readBulkString();
default:
throw new RuntimeException("錯誤的資料格式!");
}
}
private static Object readBulkString() throws IOException {
// 擷取數組大小
int len = Integer.parseInt(reader.readLine());
if (len <= 0) {
return null;
}
// 定義集合,接收多個元素
List<Object> list = new ArrayList<>(len);
// 周遊,依次讀取每個元素
for (int i = 0; i < len; i++) {
list.add(handleResponse());
}
return list;
}
// set name 虎哥
private static void sendRequest(String ... args) {
writer.println("*" + args.length);
for (String arg : args) {
writer.println("$" + arg.getBytes(StandardCharsets.UTF_8).length);
writer.println(arg);
}
writer.flush();
}
}
3.2、Redis記憶體回收-過期key處理
Redis之是以性能強,最主要的原因就是基于記憶體存儲。然而單節點的Redis其記憶體大小不宜過大,會影響持久化或主從同步性能。
我們可以通過修改配置檔案來設定Redis的最大記憶體:
當記憶體使用達到上限時,就無法存儲更多資料了。為了解決這個問題,Redis提供了一些政策實作記憶體回收:
記憶體過期政策
在學習Redis緩存的時候我們說過,可以通過expire指令給Redis的key設定TTL(存活時間):
可以發現,當key的TTL到期以後,再次通路name傳回的是nil,說明這個key已經不存在了,對應的記憶體也得到釋放。進而起到記憶體回收的目的。
Redis本身是一個典型的key-value記憶體存儲資料庫,是以所有的key、value都儲存在之前學習過的Dict結構中。不過在其database結構體中,有兩個Dict:一個用來記錄key-value;另一個用來記錄key-TTL。
這裡有兩個問題需要我們思考:
Redis是如何知道一個key是否過期呢?
利用兩個Dict分别記錄key-value對及key-ttl對
是不是TTL到期就立即删除了呢?
惰性删除
惰性删除:顧明思議并不是在TTL到期後就立刻删除,而是在通路一個key的時候,檢查該key的存活時間,如果已經過期才執行删除。
周期删除
周期删除:顧明思議是通過一個定時任務,周期性的抽樣部分過期的key,然後執行删除。執行周期有兩種:
Redis服務初始化函數initServer()中設定定時任務,按照server.hz的頻率來執行過期key清理,模式為SLOW
Redis的每個事件循環前會調用beforeSleep()函數,執行過期key清理,模式為FAST
周期删除:顧明思議是通過一個定時任務,周期性的抽樣部分過期的key,然後執行删除。執行周期有兩種:
Redis服務初始化函數initServer()中設定定時任務,按照server.hz的頻率來執行過期key清理,模式為SLOW
Redis的每個事件循環前會調用beforeSleep()函數,執行過期key清理,模式為FAST
SLOW模式規則:
- 執行頻率受server.hz影響,預設為10,即每秒執行10次,每個執行周期100ms。
- 執行清理耗時不超過一次執行周期的25%.預設slow模式耗時不超過25ms
- 逐個周遊db,逐個周遊db中的bucket,抽取20個key判斷是否過期
- 如果沒達到時間上限(25ms)并且過期key比例大于10%,再進行一次抽樣,否則結束
- FAST模式規則(過期key比例小于10%不執行 ):
- 執行頻率受beforeSleep()調用頻率影響,但兩次FAST模式間隔不低于2ms
- 執行清理耗時不超過1ms
-
逐個周遊db,逐個周遊db中的bucket,抽取20個key判斷是否過期
如果沒達到時間上限(1ms)并且過期key比例大于10%,再進行一次抽樣,否則結束
小總結:
RedisKey的TTL記錄方式:
在RedisDB中通過一個Dict記錄每個Key的TTL時間
過期key的删除政策:
惰性清理:每次查找key時判斷是否過期,如果過期則删除
定期清理:定期抽樣部分key,判斷是否過期,如果過期則删除。
定期清理的兩種模式:
SLOW模式執行頻率預設為10,每次不超過25ms
FAST模式執行頻率不固定,但兩次間隔不低于2ms,每次耗時不超過1ms
3.3 Redis記憶體回收-記憶體淘汰政策
記憶體淘汰:就是當Redis記憶體使用達到設定的上限時,主動挑選部分key删除以釋放更多記憶體的流程。Redis會在處理用戶端指令的方法processCommand()中嘗試做記憶體淘汰:
淘汰政策
Redis支援8種不同政策來選擇要删除的key:
- noeviction: 不淘汰任何key,但是記憶體滿時不允許寫入新資料,預設就是這種政策。
- volatile-ttl: 對設定了TTL的key,比較key的剩餘TTL值,TTL越小越先被淘汰
- allkeys-random:對全體key ,随機進行淘汰。也就是直接從db->dict中随機挑選
- volatile-random:對設定了TTL的key ,随機進行淘汰。也就是從db->expires中随機挑選。
- allkeys-lru: 對全體key,基于LRU算法進行淘汰
- volatile-lru: 對設定了TTL的key,基于LRU算法進行淘汰
- allkeys-lfu: 對全體key,基于LFU算法進行淘汰
-
volatile-lfu: 對設定了TTL的key,基于LFI算法進行淘汰
比較容易混淆的有兩個:
- LRU(Least Recently Used),最少最近使用。用目前時間減去最後一次通路時間,這個值越大則淘汰優先級越高。
- LFU(Least Frequently Used),最少頻率使用。會統計每個key的通路頻率,值越小淘汰優先級越高。
Redis的資料都會被封裝為RedisObject結構:
LFU的通路次數之是以叫做邏輯通路次數,是因為并不是每次key被通路都計數,而是通過運算:
- 生成0~1之間的随機數R
- 計算 (舊次數 * lfu_log_factor + 1),記錄為P
- 如果 R < P ,則計數器 + 1,且最大不超過255
- 通路次數會随時間衰減,距離上一次通路時間每隔 lfu_decay_time 分鐘,計數器 -1
最後用一副圖來描述目前的這個流程吧
4、結束語
執行頻率預設為10,每次不超過25ms
FAST模式執行頻率不固定,但兩次間隔不低于2ms,每次耗時不超過1ms