Redis字典實現、Hash鍵沖突以及漸進式rehash

本筆記參考《Redis設計與實現》 P24~ 37

目錄

  • Redis字典實現
    • 哈希表節點結構
    • 哈希表結構
    • 字典
  • 哈希算法
  • 解決hash沖突
  • rehash
  • 漸進式hash

Redis字典實現

哈希表節點結構

typedef struct dictEntry
{// 鍵void *key;// 值 : 可以是一個指針,或者是一個uint64/int64 的整數union {void *val;uint64_t u64;int64_t s64} v;// 指向下一個哈希表節點,形成鏈表 : 該指針可以將多個哈希值相同的鍵值對連接在一起,以此解決鍵沖突的問題。struct dictEntry *next;
} dictEntry;

哈希表結構

typedef struct dictht
{// 哈希表數據dictEntry **table;// 哈希表集合大小unsigned long size;// 哈希表大小掩碼,用于計算索引值// 總是等于 size - 1unsigned long sizemask;// 哈希表已有節點數量unsigned long used;
} dictht;

字典

typedef struct dict 
{// 類型特定函數dicType *type;// 私有數據void *privdata;// 哈希表dictht ht[2];// rehash 索引// 當rehash不在進行時, 值為-1int rehashidx;
} dict;

type屬性和privdata屬性針對不同類型的鍵值對,為多態字典而設置。
ht是包含兩個項的數組,每個元素都是一個dictht哈希表,一般情況下字典之是喲個ht[0],ht[1]會在對ht[0]進行rehash的時候使用。
rehashidx記錄了rehash目前的進度,如果目前沒有在進行rehash,值為-1。

哈希算法

  • 使用字典設置的哈希函數,計算key的hashvalue
    hash = dict->type->hashFunction(key);

  • 使用哈希表的sizemask屬性和哈希值,計算出索引值

  • 根據不同的情況,ht[x]可以是ht[0]或ht[1]
    index = hash & dict->ht[x].sizemask;

redis使用的是MurmurHash算法,優點是:輸入的鍵是有規律的時候,算法仍然能給出很好的隨機分布性,計算速度也快。

解決hash沖突

當有兩個或以上的key分配到了hash table數組的同一個index上,稱為發生了collision。
Redis采用鏈地址法解決沖突,每個hash table節點都有一個next指針,多個hash table節點可以用next指針構成一個單向鏈表。為了速度考慮,程序總是會將新節點插入到鏈表頭位置。

rehash

隨著操作不斷執行,哈希表保存的key value對會逐漸增加和減少。哈希表有一個統計參數load factor,即負載因子,公式如下:

# 負載因子 = 哈希表已經保存的節點數量 / 哈希表大小
load_factor = ht[0].used / ht[0].size;

為了維持負載因子在一個合理的范圍,程序會對哈希表的大小進行相應的擴展或收縮,條件如下:

  • 1、服務器目前沒有執行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的負載因子 >= 1
  • 2、服務器正在執行BGSAVE命令或者BGREWRITEAOF命令,且負載因子 >= 5
    在執行BGSAVE命令或者BGREWRITEAOF命令過程中,Redis需要創建當前服務器進程的子進程,大多的OS采用寫時復制技術優化子進程的使用效率,所以子進程存在期間,**服務器會提高執行擴展操作的負載因子,避免在子進程存在期間進行哈希表的擴展操作,避免不必要的內存寫入操作,最大限度節約內存。**當負載因子小于0.1時,程序自動對哈希表進行收縮操作。
    此時就會進行擴展收縮,規則如下:
    這里就是rehash(重新散列)操作了:
  • 1、為字典的ht[1]哈希表分配內存空間,空間大小取決于要執行的操作,以及ht[0]當前包含的鍵值對數量(ht[0].used)
    • 如果是擴展操作,ht[1]的大小為 >= ht[0].used * 2的 2的冪次方
    • 如果是收縮操作,ht[1]的大小為 >= ht[0].used 的 2的冪次方
  • 2、將保存在ht[0]中的所有鍵值對rehash到ht[1]上:即重新計算key的hashValue以及indexValue,然后將鍵值對放到ht[1]的指定位置
  • 3、當ht[0]包含的所有鍵值對都遷移到ht[1]之后,ht[0]變為空表,釋放ht[0],將ht[1]置為ht[0],在ht[1]重新分配一個空白的哈希表,為下一次rehash做準備

漸進式hash

rehash的動作并不是一次性集中完成的,而是分多次漸進完成。
如果哈希表中村的鍵值對數量很多,一次性將鍵值對全部rehash到ht[1]的計算量十分龐大,可能會導致服務器在一段時間內停止服務。
漸進式rehash采取分而治之的方法,將rehash鍵值對所需要的計算工作分攤到每次對字典的CRUD操作上,從而避免了集中式rehash帶來的龐大計算量。
詳細步驟如下:
1、為ht[1]分配空間,讓字典同時持有ht[0]和ht[1]兩個哈希表
2、在字典中維護一個索引計數器:rehashidx,將值設置為0,表示rehash工作正式開始。
3、在rehash進行期間,每次對字典的CRUD操作,程序除了執行指定操作以外,順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對rehash到ht[1]上,當rehash操作完成后,程序將rehashidx值++
4、重復迭代操作執行后,ht[0]的數據全部rehash到ht[1]上,將rehashidx設為-1,表明rehash操作已經完成

需要注意的地方
在rehash的過程中,對于字典的刪除、查找、更新操作會在兩個哈希表上執行。如想要查找一個鍵,現在ht[0]中找,沒有找到再去ht[1]
對于insert操作來說,新添加到字典的鍵值對會一律保存到ht[1]中,不然還得多一次搬運。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/376958.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/376958.shtml
英文地址,請注明出處:http://en.pswp.cn/news/376958.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Java線程類void setContextClassLoader(ClassLoader loader)方法,帶示例

線程類void setContextClassLoader(ClassLoader loader) (Thread Class void setContextClassLoader(ClassLoader loader)) This method is available in package java.lang.Thread.setContextClassLoader(ClassLoader loader). 軟件包java.lang.Thread.setContextClassLoader(…

JPA概要

本文最新版已更新至:http://thinkinside.tk/2012/12/30/JPA.html JPA定義了Java ORM及實體操作API的標準。本文摘錄了JPA的一些關鍵信息以備查閱。 如果有hibernate的基礎,通過本文也可以快速掌握JPA的基本概念及使用。 Table of Contents 1 JPA概述2 實…

如何配置能讓fiddler抓去https的請求?

1、打開fiddler,>>Tools>>Fiddler Options, 打開如圖所示的HTTPS配置項:點擊Export Rppt Certifica to Desktop :桌面上多了一個證書:下面就是將證書導入:點擊開始-運行,輸入:mmc,…

Redis對象的refcount與lru屬性(內存回收、對象共享、空轉時長)

本筆記參考《Redis設計與實現》 P84~P88 內存回收 Redis在對象系統中使用reference counting技術實現了內存回收機制。程序可以通過跟蹤對象的引用計數信息,在適當的時候自動釋放對象并進行內存回收。 typedef struct redisObject {// ...// 引用計數int refcoun…

【閑聊】Baidu Map,excellent !!!Diaoyv island is China 's

【釣魚島】釣魚島是中國的!Diaoyu Islands are Chinas! 釣魚島は中國のアール! ————————————youngLaker轉載于:https://www.cnblogs.com/younglaker/archive/2012/12/31/2840190.html

08:vigenère密碼_密碼技術:Vigenére密碼,Playfair密碼,Hill密碼

08:vigenre密碼1)Vigenre密碼 (1) Vigenre Cipher) This technique is an example of Polyalphabetic Substitution technique which uses 26 Caesar ciphers make up the mono-alphabetic substitution rules which follow a count shifting mechanism from 0 to 25. That is,…

Redis的RDB文件與AOF文件

本筆記參考《Redis設計與實現》 P118 ~ P150 RDB文件 1、RDB文件用于保存和還原Redis服務器所有數據庫中的所有鍵值對數據 2、SAVE命令由服務器進程直接執行保存操作,該命令會阻塞服務器 3、BGSAVE命令由子進程執行保存操作,不會阻塞服務器 注意此時服…

eclipse擴容

eclipse擴容 -vmD:/jdk-6u17-windows-i586/jdk1.6.0_17/bin/javaw.exe-startupplugins/org.eclipse.equinox.launcher_1.3.0.v20120522-1813.jar-nlen_US--launcher.libraryplugins/org.eclipse.equinox.launcher.win32.win32.x86_1.1.200.v20120913-144807-productorg.eclipse…

node oauth2驗證_如何設置和使用護照OAuth Facebook身份驗證(第2部分)| Node.js

node oauth2驗證In my last article (How to set up and use passport OAuth Facebook Authentication (Section 1) | Node.js), we looked at another form of authentication called the OAuth authentication which involves sign in or signup using social media. 在我的上…

Python and Microsoft Word

國外網站看到的文章:Accessing Microsoft Word with Python follows the same syntax that we used for Excel. Let’s take a quick look at how to access Word.from time import sleep import win32com.client as win32RANGE range(3, 8)def word():word win32…

東哥讀書小記 之 《一個廣告人的自白》

掰著指頭一算,端午假期確實完成不少事情,過的太尼瑪充實鳥:去健身房2小時,且老夫的平板支撐終于能堅持超過1分鐘,普大喜奔有木有;給合租的室友買蛋糕過了個生日;去 去哪兒 參加W3ctech的技術交流…

Redis的文件事件與時間事件處理

目錄文件事件處理事件類型客戶端和服務端的通信過程時間事件處理執行器執行周期性事件作用事件的調度與執行文件事件處理 Redis基于Reactor模式開發了文件事件處理器。文件事件處理器以單線程方式運行,通過IO多路復用程序監聽多個套接字,實現了高性能網…

fisher-yates_使用Fisher-Yates隨機播放算法以O(n)時間隨機播放給定數組

fisher-yatesExample: 例: Say the input array is [1, 2 3, 4, 5 6, 7]After reshuffling it can be anything like[4, 3, 7, 2, 1, 5, 1]Our goal is that the reshuffling should be as random as possible. 我們的目標是,改組應盡可能地隨機。 The…

[分享]一些在 WPF/Silverlight 中應用 MVVM 模式時可能會有點用途的代碼

想來這個博客也已經有很久沒更新過了,新年新氣象,現在就開始寫新內容吧。 最初的起因 在最近的幾個月中我做的開發總是要跟 XAML 打交道,也就是 WPF 啊,Silverlight 啊,WF 啊這些。 在進行 WPF 和 Silverlight 開發的…

手機調用系統的拍照和裁剪功能,假設界面有輸入框EditText,在一些手機會出現點擊EditText會彈出輸入法,卻不能輸入的情況。...

1、拍照裁剪后 點擊EditText會彈出輸入法,卻不能輸入。可是點擊點一EdtiText就能夠輸入了,所以我就寫了一個看不見的EdtiText,切換焦點,這樣就攻克了這個奇怪的這問題,應該是android內部的問題。 這是網絡一個牛人留下…

Redis一個命令請求從發送到完成的步驟以及初始化服務器步驟

一個命令請求從發送到完成的步驟 如下: 1、客戶端將命令請求發送給服務器 當用戶在客戶端中鍵入一個命令請求時,客戶端會將這個命令請求轉換成協議格式,然后通過連接到服務器的套接字,將協議格式的命令請求發送給服務器。 2、服…

c打印行號和函數_使用C中的函數名稱,行號從任何函數打印錯誤消息

c打印行號和函數Sometimes, it is necessary to print some message on logic failure or anytime with the function name and line number, so that program can be debugged and fixed the issue. 有時,有必要在邏輯故障時或在任何時候使用功能名稱和行??號打印…

Linux SPI框架

水平有限,描述不當之處還請指出,轉載請注明出處http://blog.csdn.net/vanbreaker/article/details/7733476 Linux的SPI子系統采用主機驅動和外設驅動分離的思想,首先主機SPI控制器是一種平臺設備,因此它以platform的方式注冊進內…

dbms標識符無效_DBMS中的嵌套查詢,相關的嵌套查詢和集合比較運算符

dbms標識符無效嵌套查詢 (Nested Queries) A query embedded in a query. This type of relation is termed as Nested Query and the Embedded Query is termed as a subquery. 查詢中嵌入的查詢。 這種類型的關系稱為嵌套查詢,而嵌入式查詢稱為子查詢。 For exam…

重構——解決過長參數列表(long parameter list)

目錄1、Replace Param with Query2、Preserve Whole Object3、Introduce Param Object4、Remove Flag Argument5、Combine Functions into ClassReference當我們需要在超長函數中提煉子函數時,如果函數內有大量的參數和臨時變量,這將會對函數的提煉形成很…