<em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011
2021-06-01 09:32:01
此前我們學習了常見的Reids資料型別,這些資料型別都需要底層的資料結構的支援,現在我們來看看Redis常見的底層資料結構:dict、ziplist、quicklist。
dict就是「字典」的意思,它是Redis中的一種使用的非常多的底層的資料結構,除了hash會使用欄位之外,整個 Redis 資料庫的所有 key 和 value 也組成了一個全域性字典dict,還有帶過期時間的 key 也是一個字典expires(儲存在 RedisDb 資料結構中)。
Redis 中的字典相當於 JDK1.7中的 HashMap,內部實現也差不多類似,都是通過 「陣列 + 連結串列」 的鏈地址法來解決部分雜湊衝突,同時這樣的結構也吸收了兩種不同資料結構的優點。
和JDK1.7中的hashmap不同的是,Reids的字典結構內部包含兩個hashtable變數,通常情況下只有一個hashtable有值,另一個為空表,但是在字典擴容縮容時,需要分配新的hashtable,並且使用了一種叫做漸進式搬遷(rehash)的機制來提高dict的縮放效率,這時候兩個hashtable分別儲存舊的和新的 hashtable,待搬遷結束後,舊的將被刪除,新的 hashtable 取而代之。
正常情況下,當 hash 表中元素的個數等於陣列的長度時,就會開始擴容,擴容的新陣列是原陣列大小的2倍。不過如果 Redis 正在做 BGSAVE或者BGREWRITEAOF(持久化),為了減少記憶體佔用,Redis 儘量不去擴容,但是如果 hash 表非常滿了,達到了陣列長度的 5 倍了,這個時候就會強制擴容。
當 hash 表因為元素逐漸被刪除變得越來越稀疏時,Redis 會對 hash 表進行縮容來減少hash表的第一維陣列空間佔用。所用的條件是:元素個數低於陣列長度的10%,縮容不會考慮 Redis 是否在做 bgsave。
在擴容和收縮的時候,如果雜湊字典中有很多元素,一次性將這些鍵從ht0(正在使用的hashtable)全部rehash到ht1(另一個空的hashtable)的話,由於Redis是單執行緒模型,那麼可能會導致伺服器在一段時間內停止服務。所以,採用漸進式rehash的方式,資料的遷移並不是一步完成的,因此dict內部還有一個rehashidx屬性用來控制rehash,預設定為-1。
漸進式rehash採用的是一種分而治之的方式,它以bucket(桶)為基本單位進行漸進式的資料遷移,每步完成一個bucket的遷移,直至所有資料遷移完畢。這種方式將rehash的操作分攤在每一個的存取中,避免集中式rehash而帶來的龐大計算量。
在漸進式rehash的過程中,如果有刪除、修改、查詢操作,則會在兩個雜湊表ht[0]和ht[1]上進行,先操作ht[0],如果沒找到,再操作ht[1],則新增的資料則會被儲存在ht[1]中,ht[0]中包含的鍵值對數量會只減不增,並隨著 rehash 操作的執行而最終變成空表。
ziplist又名壓縮列表,見其名知其意,這種資料結構就比較節省記憶體空間,Redis中對於list(3.2版本之前)、hash、zset型別的資料,如果元素較少,並且每個列表項要麼就是小整數值,要麼就是長度比較短的字串,那麼Redis就會使用壓縮列表來儲存。
ziplist本身可以有序也可以無序。當作為list(3.2版本之前)和hash的底層實現時,節點之間沒有順序;當作為zset的底層實現時,節點之間會按照score大小順序排列,元素和score被分別儲存為兩個節點,元素在前,score在後。
ziplist的節省空間是相較於陣列而言的,ziplist和陣列一樣同樣採用一整塊連續的空間來儲存資料,陣列在實際儲存時,每一個元素所佔的實際大小是一樣的,並且是以最大的元素的大小為準,這樣就能進行快速的根據索引存取,而ziplist則允許每一個entry節點(對於陣列中的元素)所佔的實際大小不同,另外,節點之間沒有儲存前驅和後繼的指標,以此節約空間。
ziplist支援正序或者倒序的遍歷,往ziplist裡插入一個entry 時間複雜度 平均:O(n),最壞:O(n²),從ziplist裡刪除一個entry 時間複雜度 平均:O(n), 最壞:O(n²)。最壞為O(n²)是因為Redis連鎖更新導致的,但這種情況出現的概率不高。
ziplist和陣列類似,刪除和新增節點都可能涉及到其他節點位置的移動,因此只適用於元素資料量較少,並且每個列表項要麼就是小整數值,要麼就是長度比較短的字串的情況。
Redis的ziplist採用一系列特殊編碼的連續記憶體塊,一個壓縮列表出了在頭部包含一些整體資訊之外,剩下的部分可以包含任意多個節點(entry)。
整體結構如下:
ziplist的entry用於儲存正數或者字串(位元組陣列),且每個節點的長度都是不一樣的,因此節點的長度只能由這個節點自己來儲存,Redis的ziplist中,entry由三部分構成:
previous_entry_length用於記錄上一個節點的長度(位元組),為了方便反向遍歷ziplist,其本身的長度可能是8bit或者40bit。
content表示當前節點的值,可以是數位或字串(位元組陣列),encoding 表示當前節點資料的編碼規則,即data屬性的資料型別以及長度,其中encoding其中高2位用來區分整數節點和字串節點(高2位為11時是整數節點),根據值的型別不同,一共有九種編碼型別。
位元組陣列的encoding型別3種,encoding有8位元、16位元、40位三種長度,context的長度也是變化的:
encoding長度 | encoding格式 | content格式 |
---|---|---|
8bit | 高兩位固定00,後6位表示位元組陣列的長度 | 長度小於等於63(2^6-1)位元組的位元組陣列 |
16bit | 高兩位固定01,後14位元表示位元組陣列的長度。 | 長度小於等於16383(2^14-1)位元組的位元組陣列 |
40bit | 高兩位固定10,後38位元表示位元組陣列的長度。 | 長度小於等於4294967295(2^32-1)位元組的位元組陣列 |
整數值的encoding型別6種,固定長度8位元,高兩位固定11,表示整數,因此需要後兩位來表示不同的整數型別。整數型別的content的長度雖然也是可變的,但固定範圍內的整數長度一樣,也就是說content長度只有固定的幾種。
encoding長度 | encoding格式 | content格式 |
1bit | 1111xxxx,後四位用來表示content。 | 4bit長的無符號整數,即介於0至12之間,沒有content欄位,在encoding中儲存。 |
11111110 | 8bit,有符號整數。 | |
11000000 | 16bit,有符號整數。 | |
11110000 | 24bit,有符號整數。 | |
11010000 | 32bit,有符號整數。 | |
11100000 | 64bit,有符號整數。 |
Redis 的list在3.2版本之前在元素較少時實際上是採用ziplist結構,當連結串列entry資料超過512、或單個value 長度超過64,底層就會轉化成linkedlist編碼,而Redis3.2及其之後則採用quicklist結構代替ziplist和linkedlist。
ziplist儲存在一段連續的記憶體上,所以儲存和查詢效率很高,順序IO存取。但是,它不利於修改操作,插入和刪除操作需要頻繁的申請和釋放記憶體。特別是當ziplist長度很長的時候,一次realloc可能會導致大批次的資料拷貝,適用於儲存整數和短字串。
雙向連結串列linkedlist便於在表的兩端進行push和pop操作,在插入節點上覆雜度很低,但是它的記憶體開銷比較大。首先,它在每個節點上除了要儲存資料之外,還要額外儲存兩個prev 和 next指標(64 位元運算系統佔用 8 個位元組);其次,雙向連結串列的各個節點是單獨的記憶體塊,地址不連續,隨機IO存取,節點多了容易產生記憶體碎片,影響記憶體管理效率。
quickList將 linkedList 按段切分,每一段使用 zipList 來緊湊儲存,多個 zipList 之間使用雙向指標串接起來。
首先quickList就是一個標準的雙向連結串列的設定,有head 和tail節點,每個節點是一個quicklistNode節點,包含prev和next指標,內部還包含一個ziplist,使用ziplist來儲存資料,而ziplist實際上含有多個entry節點,儲存著資料。相當與一個quicklistNode節點儲存的是一片資料,而不再是一個資料。
quickList將二者的優點結合起來,在宏觀上是一個雙向連結串列結構,插入、刪除quicklistNode節點的成本很低,不需要移動其他節點的位置,而在微觀上,每一個quicklistNode節點又是一個個的ziplist,內部包含多個資料,ziplist記憶體連續,減少了記憶體碎片,同時由於每一個ziplist不是很大(大小可以設定),因此插入和刪除操作不會進行大量的資料移動。
相關文章:
https://redis.io/topics/data-types
https://redis.io/topics/data-types-intro
到此這篇關於Redis的底層資料結構之dict、ziplist、quicklist詳解的文章就介紹到這了,更多相關Redis底層資料結構內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com!
相關文章
<em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011
2021-06-01 09:32:01
综合看Anker超能充系列的性价比很高,并且与不仅和iPhone12/苹果<em>Mac</em>Book很配,而且适合多设备充电需求的日常使用或差旅场景,不管是安卓还是Switch同样也能用得上它,希望这次分享能给准备购入充电器的小伙伴们有所
2021-06-01 09:31:42
除了L4WUDU与吴亦凡已经多次共事,成为了明面上的厂牌成员,吴亦凡还曾带领20XXCLUB全队参加2020年的一场音乐节,这也是20XXCLUB首次全员合照,王嗣尧Turbo、陈彦希Regi、<em>Mac</em> Ova Seas、林渝植等人全部出场。然而让
2021-06-01 09:31:34
目前应用IPFS的机构:1 谷歌<em>浏览器</em>支持IPFS分布式协议 2 万维网 (历史档案博物馆)数据库 3 火狐<em>浏览器</em>支持 IPFS分布式协议 4 EOS 等数字货币数据存储 5 美国国会图书馆,历史资料永久保存在 IPFS 6 加
2021-06-01 09:31:24
开拓者的车机是兼容苹果和<em>安卓</em>,虽然我不怎么用,但确实兼顾了我家人的很多需求:副驾的门板还配有解锁开关,有的时候老婆开车,下车的时候偶尔会忘记解锁,我在副驾驶可以自己开门:第二排设计很好,不仅配置了一个很大的
2021-06-01 09:30:48
不仅是<em>安卓</em>手机,苹果手机的降价力度也是前所未有了,iPhone12也“跳水价”了,发布价是6799元,如今已经跌至5308元,降价幅度超过1400元,最新定价确认了。iPhone12是苹果首款5G手机,同时也是全球首款5nm芯片的智能机,它
2021-06-01 09:30:45