Redis基礎(chǔ)與高級數(shù)據(jù)結(jié)構(gòu)
一彼硫、Redis基礎(chǔ)與高級數(shù)據(jù)結(jié)構(gòu)
二呛谜、Redis基礎(chǔ)原理
三、Redis拓展知識
一荞下、string
- 基本原理：字符數(shù)組伶选，動態(tài)字符串，預(yù)分配冗余空間減少內(nèi)存頻繁分配
- 擴容原理：長度<1MB時2倍擴容尖昏，長度>1MB時一次擴1MB仰税，字符串最大長度512MB
- 數(shù)據(jù)結(jié)構(gòu)：
- struct SDS<T> { T capacity; T len ; byte flags; byte[] content;}
- 長度特別短embstr結(jié)構(gòu)，長度超過44字節(jié)時raw的結(jié)構(gòu)
- embstr內(nèi)存上連續(xù)一次內(nèi)存分配抽诉，raw內(nèi)存上不連續(xù)二次內(nèi)存分配陨簇，Redis對象頭指針指向String內(nèi)存地址
- 44字節(jié)改變結(jié)構(gòu)：64-Redsi對象頭（16字節(jié)）-String對象頭（3字節(jié)）-字符串末尾NULL（1字節(jié)）=44字節(jié)
二、list
基本結(jié)構(gòu)：ziplist迹淌、quicklist（個數(shù)大于512或長度超過64）
-
ziplist數(shù)據(jù)結(jié)構(gòu)：
zlbytes zltail_offset zllengt entry ... entry zlend 總字節(jié)數(shù) 最后個元素到第一個的偏移量 元素個數(shù) 元素1 ... 元素n 列表結(jié)束符 - ziplist是一塊連續(xù)的空間河绽，元素之間緊挨著儲存
- entry的結(jié)構(gòu):struct entry{int<var> prevlen; int<var> encoding; optional byte[] content;},prevlen為前一個元素的長度，encodeing為編碼類型巍沙，用于標(biāo)識內(nèi)容類型和長度，如果對于小的整數(shù)來說荷鼠，encoding低位中就保存內(nèi)容句携，不用保存在content中
- entry中的prevlen，當(dāng)存儲的字符串長度小于254字節(jié)允乐，使用1字節(jié)表示長度矮嫉，
大于254個字節(jié)削咆，使用5個字節(jié)標(biāo)識長度，ziplist添加和刪除節(jié)點會引發(fā)聯(lián)機更新的問題
-
quicklist數(shù)據(jù)結(jié)構(gòu)：
- 之前采用linklist后由于指針大小和每次內(nèi)存單獨分配蠢笋，改用quicklist
- ziplist默認(rèn)長度為8KB拨齐，默認(rèn)不壓縮，可以配置使用LZF算法進行壓縮
三昨寞、hash
1.基本結(jié)構(gòu)：ziplist瞻惋、數(shù)組+鏈表（個數(shù)大于512或長度超過64）
2.擴容方式：為追求性能采用漸進式rehash策略，同時保留新舊2個hash結(jié)構(gòu)
3.擴容原理：哈希擴容的時候會有卡頓援岩，所有同時保留現(xiàn)有哈希和擴容縮容后的哈希歼狼，在原哈希沒有找到再另一個哈希再進行查找，在定時任務(wù)以及后續(xù)的hash操作指令中漸漸的將舊數(shù)組的元素遷移到新數(shù)組享怀。
四羽峰、set
1.數(shù)據(jù)結(jié)構(gòu)：intset、哈希的特殊結(jié)構(gòu)添瓷，所有的value都是NULL（個數(shù)大于512）
intset結(jié)構(gòu)梅屉，動態(tài)調(diào)整類型為uint16~uint64的數(shù)組
| encoding | length | value | value | ... | value |
|---|
五、zset
1.數(shù)據(jù)結(jié)構(gòu)：ziplist鳞贷、哈希（存儲key-value）+跳躍列表（提供排序）（個數(shù)大于512或長度超過64）
2.quicklist數(shù)據(jù)結(jié)構(gòu)：
- 最多64層坯汤，容納2的64次方個元素
- 插入元素采用隨機算法，理論上第一層概率為50%悄晃，第二層25%玫霎，以此類推，redis中晉升25%妈橄，因此跳躍列表會比較扁平
- source值一樣的時候會比較value的值
- rank的實現(xiàn)是因為在節(jié)點的指針中存放了一跳經(jīng)過的跨度
六庶近、位圖
1.基本結(jié)構(gòu)：位數(shù)組
2.使用場景：用戶的一年簽到記錄
3.基本操作：
- getbit、setbit眷蚓、bitcount（指定位置范圍）鼻种、bitpos（指定范圍內(nèi)）
- bitfield多個位操作set、get沙热、incrby（默認(rèn)配置會出現(xiàn)折返叉钥。也可以設(shè)置失敗或者飽和截斷）
七、HyperLogLog
1.基本結(jié)構(gòu)：稀疏矩陣篙贸、HyperLogLog（2的14次方個桶用于調(diào)和平均投队，所以占12KB）
2.使用場景：提供不精確的去重計數(shù)方案，標(biāo)準(zhǔn)誤差為0.81%爵川，可以統(tǒng)計每天訪問系統(tǒng)的UV數(shù)據(jù)
3.基本操作：pfadd敷鸦、pfcount、pfmerge（多個pf計數(shù)累加）
八、布隆過濾器
1.基本結(jié)構(gòu)：位數(shù)組扒披、無偏hash函數(shù)
2.使用場景：推薦算法中的是否已經(jīng)看過該文檔值依、郵件過濾、爬蟲記錄已經(jīng)爬過的URL碟案，會有一定誤判愿险，但是不存在一定不存在，存在不一定一定存在价说。
3.基本使用：bf.add辆亏、bf.exists 、bf.mexists
4.參數(shù)調(diào)優(yōu)：
- 使用bf.reserve設(shè)置key熔任、error_rate褒链、inital_size
- error_rate錯誤率，錯誤率越低空間越大
- inital_size預(yù)計元素個數(shù)疑苔，超了誤判率會變高
九甫匹、地理位置GeoHash（了解）
1.算法原理：GeoHash將二維的經(jīng)緯度數(shù)據(jù)映射到一維的整數(shù)（反向從證書還原有損），所有的坐標(biāo)都存儲在zset中惦费，score是坐標(biāo)52位整數(shù)兵迅，所以可以查看附件的元素（實際會復(fù)雜一些）
2.基本使用：geoadd、geodist（距離）薪贫、geopos（經(jīng)緯度）恍箭、geohash（位置編碼）、georadiusbymemeber(位置附近)瞧省、georadius(經(jīng)緯附近)
3.注意事項：
- 集群數(shù)據(jù)量不建議超過1MB扯夭，這樣遷移可能會卡頓
- 建議使用單機，Geo數(shù)據(jù)按照國家鞍匾、省等進行拆分
十交洗、listpack（了解）
1.產(chǎn)生背景：為了取代ziplist，不會有級聯(lián)更新的問題橡淑，每個節(jié)點單獨存在
2.數(shù)據(jù)結(jié)構(gòu)：
| total_bytes | size | entry | ... | entry | end |
|---|---|---|---|---|---|
| 總字節(jié)數(shù) | 元素個數(shù) | 元素1 | ... | 元素n | 列表結(jié)束符 |
- entry的結(jié)構(gòu):struct entry{int<var> encoding;optional byte[] content;int<var> length;},length為當(dāng)前元素的長度构拳，不再是前一個元素長度，由于在entry的末端梁棠，所以與ziplist相比可以直接計算最后一個元素的位置置森，encodeing為編碼類型，可以是1~5個字節(jié)中的任一長度
- 現(xiàn)在暫時應(yīng)用于Stream中符糊，并沒有完全的替換ziplist的結(jié)構(gòu)
十一凫海、基數(shù)樹 rax（了解）
1.數(shù)據(jù)結(jié)構(gòu)：與zset不同的是zset基于score進行排序使套，rax基于key進行排序（字典序）混聊，rax是基數(shù)樹radix tree的特殊結(jié)構(gòu)，與基數(shù)樹不同的是節(jié)點可以進行壓縮存多個字符
2.使用場景：使用在Stream機構(gòu)中用于存儲消息隊列
