Redis系列文章
Redis（一）原理及基本命令（柔性數(shù)組）
Redis（二）網(wǎng)絡(luò)協(xié)議和異步方式（樂觀鎖&悲觀鎖）
Redis（三）存儲原理與數(shù)據(jù)模型（hash沖突、漸進式rehash）
Redis跳表
一、redis 存儲結(jié)構(gòu)
Redis是key-value的結(jié)構(gòu)，其中value包含：字典，雙向鏈表，壓縮列表，跳表，整數(shù)數(shù)組，動態(tài)字符串。
存儲轉(zhuǎn)換
其中redis中各value的數(shù)據(jù)結(jié)構(gòu)根據(jù)不同的情況有不同的自動存儲轉(zhuǎn)換。
鍵值存儲實現(xiàn)
redis 中 K-V 組織是通過字典來實現(xiàn)的，也就是hash表。key字符串經(jīng)過 hash 函數(shù)運算得到 64 位整數(shù)；
hash沖突
redis采用hash表存儲key-value就會遇到hash沖突的情況。常見的hash沖突解決方式有：
- 開鏈法：將hash沖突的value值用鏈表連接，每個hash結(jié)果的key值下面都連接一個鏈表。如果鏈表過長還可以將鏈表轉(zhuǎn)化為紅黑樹來優(yōu)化。
- rehash：即增加hash桶的大小。redis有兩個hash表，當hash表1沖突了，就會采用hash表2，而hash表2的hash桶大小通常是hash表1的2倍。
但是rehash時，將hash表1的數(shù)據(jù)復制到hash表2是一個龐大的工程，可能會造成redis線程阻塞，影響redis性能。因此redis有漸進式rehash的機制來解決這個問題。
漸進式rehash
漸進式rehash和rehash一樣，同樣需要將hash表1的數(shù)據(jù)復制到hash表2，但是這個復制過程不是一次性的，而是一步一步分塊轉(zhuǎn)移。
redis的漸進式有兩種規(guī)則：
- 分治的思想，將 rehash 分到之后的每步增刪改查的操作當中，即每次處理redis時，復制一個key；
- 在定時器中，最大執(zhí)行一毫秒 rehash ；每次復制100 個數(shù)組key槽位；
rehash 過程中如果入到增刪查改時會怎么做？
- 查：查找數(shù)據(jù)時，會先在hash表1中查找數(shù)據(jù)，如果沒找到就會在hash表2中去找。
- 增：新增數(shù)據(jù)時，只會增加到hash表2中，不會在hash表1做任何操作。
- 刪&改：在兩個表上都會操作。
redis除了擴容會有漸進式rehash，其實縮容時也會采用rehash。
但是在rehash階段，不會再發(fā)生擴容和縮容。必須等rehash結(jié)束。
大KEY
在 redis 實例中假如形成了很大的對象，比如一個很大的 hash 或很大的 zset，這樣的對象在擴容的時候，會一次性申請更大的一塊內(nèi)存，這會導致卡頓；如果這個大 key 被刪除，內(nèi)存會一次性回收，卡頓現(xiàn)象會再次產(chǎn)生；如果觀察到 redis 的內(nèi)存大起大落，極有可能因為大 key 導致的；
解決方法：文章來源：http://www.zghlxwxcb.cn/news/detail-573392.html
- 拆分value
- 壓縮value
- 刪除非熱點大key（可使用redis異步機制刪除）
跳表
Redis 中的有序集合(Sorted Set)是用跳表（Skip list）來實現(xiàn)的。跳表就是解決鏈表在有序節(jié)點場景下的查詢時間復雜度高問題。時間復雜度能達到O(logn)。
詳細內(nèi)容參考Redis跳表文章來源地址http://www.zghlxwxcb.cn/news/detail-573392.html
到了這里，關(guān)于Redis（三）存儲原理與數(shù)據(jù)模型（hash沖突、漸進式rehash）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
