搜尋
首頁資料庫mysql教程Redis内部数据结构详解之字典(dict)

Redis内部数据结构详解之字典(dict)

Jun 07, 2016 pm 03:22 PM
dictredis內部字典資料結構詳解

字典,简单说就是存储key-value键值数据,当然value=NULL那么就是集合了。字典通俗来说就是C++ STL中的map,STL中的map是用red-black tree实现的,因为map不仅能够保证key不重复,而且key还是按照字典序存储的,而Redis中的字典并不要求有序,因此为了降低编

字典,简单说就是存储key-value键值数据,当然value=NULL那么就是集合了。字典通俗来说就是C++ STL中的map,STL中的map是用red-black tree实现的,因为map不仅能够保证key不重复,而且key还是按照字典序存储的,而Redis中的字典并不要求有序,因此为了降低编码的难度使用哈希表作为字典的底层实现。Redis的字典是使用一个桶bucket,通过对key进行hash得到的索引值index,然后将key-value的数据存在桶的index位置,Redis处理hash碰撞的方式是链表,两个不同的key hash得到相同的索引值,那么就使用链表解决冲突。使用链表自然当存储的数据巨大的时候,字典不免会退化成多个链表,效率大大降低,Redis采用rehash的方式对桶进行扩容来解决这种退化。

Redis使用的hash算法有以下两种:

1. MurmurHash2 32 bit 算法:这种算法的分布率和速度都非常好,具体信息请参考 MurmurHash 的主页:http://code.google.com/p/smhasher/ 。
2. 基于djb算法实现的一个大小写无关散列算法:具体信息请参考
http://www.cse.yorku.ca/~oz/hash.html 。

字典数据结构

typedef struct dictEntry {//字典的节点
    void *key;
    union {//使用的联合体
        void *val;
        uint64_t u64;//这两个参数很有用
        int64_t s64;
    } v;
    struct dictEntry *next;//下一个节点指针
} dictEntry;

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key); //hash函数指针
    void *(*keyDup)(void *privdata, const void *key); //键复制函数指针
    void *(*valDup)(void *privdata, const void *obj); //值复制函数指针
    int (*keyCompare)(void *privdata, const void *key1, const void *key2); //键比较函数指针
    void (*keyDestructor)(void *privdata, void *key); //键构造函数指针
    void (*valDestructor)(void *privdata, void *obj); //值构造函数指针
} dictType;

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht { //字典hash table
    dictEntry **table;//可以看做字典数组,俗称桶bucket
    unsigned long size; //指针数组的大小,即桶的层数
    unsigned long sizemask;
    unsigned long used; //字典中当前的节点数目
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata; //私有数据
    dictht ht[2];   //两个hash table
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */ //rehash 索引
    int iterators; /* number of iterators currently running */ //当前该字典迭代器个数
} dict;
dict数据结构中声明了两个字典hashtable结构dictht,ht[1]在rehash时候使用,后面具体分析。

下图给出整个字典结构,图片来自Redis设计与实现一书:

\
 

上图ht[1]为空,说明当然字典没在Rehash状态。

字典的API函数

函数名称

作用

复杂度

dictCreate

创建一个新字典

O(1)

dictResize

重新规划字典的大小

O(1)

dictExpand

扩展字典

O(1)

dictRehash

对字典进行N步渐进式Rehash

O(N)

_dictRehashStep

对字典进行1步尝试Rehash

O(N)

dictAdd

添加一个元素

O(1)

dictReplace

替换给定key的value值

O(1)

dictDelete

删除一个元素

O(N)

dictRelease

释放字典

O(1)

dictFind

查找一个元素

O(N)

dictFetchValue

通过key查找value

O(N)

dictGetRandomKey

随机返回字典中一个元素

O(1)

创建新字典

通过dictCreate函数创建一个新字典dict *dictCreate(dictType *type, void *privDataPtr),一个空字典的示意图如下(图片来自Redis设计与实现一书): \上面已经提起过,ht[1]只在Rehash时使用。

字典添加元素

根据字典当前的状态,将一个key-value元素添加到字典中可能会引起一系列复制的操作:

如果字典未初始化(即字典的0号哈希表ht[0]的table为空),那么需要调用dictExpand函数对它初始化;

如果插入的元素key已经存在,那么添加元素失败;

如果插入元素时,引起碰撞,需要使用链表来处理碰撞;

如果插入元素时,引起程序满足Rehash的条件时,先调用dictExpand函数扩展哈希表的size,然后准备渐进式Rehash操作。

字典添加元素的流程图,来自Redis设计与实现一书

\

/* Expand or create the hash table */
int dictExpand(dict *d, unsigned long size)
{
    dictht n; /* the new hash table */
    unsigned long realsize = _dictNextPower(size); //得到需要扩展到的size

    /* the size is invalid if it is smaller than the number of
     * elements already inside the hash table */
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize * sizeof(dictEntry*));
    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    //准备渐进式rehash,rehash的字典table为0号
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_OK;

    // 如果哈希表为空,那么将它扩展为初始大小
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    /*如果哈希表的已用节点数 >= 哈希表的大小,并且以下条件任一个为真:
       1) dict_can_resize 为真
       2) 已用节点数除以哈希表大小之比大于 dict_force_resize_ratio
       那么调用 dictExpand 对哈希表进行扩展,扩展的体积至少为已使用节点数的两倍
    */
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

static int _dictKeyIndex(dict *d, const void *key)
{
    unsigned int h, idx, table;
    dictEntry *he;

    /* Expand the hash table if needed */
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    /* Compute the key hash value */
    h = dictHashKey(d, key);//通过hash函数得到key所在的bucket索引位置
    //查找在现有字典中是否出现了该key
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        /* Search if this slot does not already contain the given key */
        he = d->ht[table].table[idx];
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return -1;
            he = he->next;
        }
        //如果系统没在rehash则不需要查找ht[1]
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;

    if (dictIsRehashing(d)) _dictRehashStep(d);// 尝试渐进式地 rehash 桶中一组元素

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    // 查找可容纳新元素的索引位置,如果元素已存在, index 为 -1
    if ((index = _dictKeyIndex(d, key)) == -1)
        return NULL;

    /* Allocate the memory and store the new entry */
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    // 决定该把新元素放在那个哈希表
    entry = zmalloc(sizeof(*entry));
    //头插法,插入节点
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

    /* Set the hash entry fields. */
    dictSetKey(d, entry, key);//关联起key
    return entry;
}

/* Add an element to the target hash table */
//添加一个元素
int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key);

    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);//关联起value
    return DICT_OK;
}

字典Rehash解析

Rehash的触发机制:当每次添加新元素时,都会对工作哈希表ht[0]进行检查,如果used(哈希表中元素的数目)与size(桶的大小)比率ratio满足以下任一条件,将激活字典的Rehash机制:ratio=used / size, ratio >= 1并且dict_can_resize 为真;ratio 大 于 变 量 dict_force_resize_ratio 。
Rehash执行过程:创建一个比ht[0].used至少两倍的ht[1].table;将原ht[0].table中所有元素迁移到ht[1].table;清空原来ht[0],将ht[1]替换成ht[0] 渐进式Rehash主要由两个函数来进行: _dictRehashStep:当对字典进行添加、查找、删除、随机获取元素都会执行一次,其每次在开始Rehash后,将ht[0].table的第一个不为空的索引上的所有节点全部迁移到ht[1].table; dictRehashMilliseconds:由Redis服务器常规任务程序(serverCron)执行,以毫秒为单位,在一定时间内,以每次执行100步rehash操作。

Rehash操作核心函数:

int dictRehash(dict *d, int n) {
    if (!dictIsRehashing(d)) return 0;

    while(n--) {
        dictEntry *de, *nextde;

        /* Check if we already rehashed the whole table... */
        if (d->ht[0].used == 0) {//已经完成
            zfree(d->ht[0].table);//释放ht[0].table
            d->ht[0] = d->ht[1]; //这里ht[0]与ht[1]都不是指针,直接赋值就替换了
            _dictReset(&d->ht[1]);//将ht[1].table设置为null
            d->rehashidx = -1;
            return 0;
        }

        /* Note that rehashidx can&#39;t overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned)d->rehashidx);
        //找到第一个不为空的数组
        while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
        //指向该链表头
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {//遍历链表
            unsigned int h;

            nextde = de->next;
            /* Get the index in the new hash table */
            //得到在ht[1]中的索引号,通过相应的hash函数
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;

            // 添加节点到 ht[1] ,调整指针,采用的是头插法
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;//设置为空
        d->rehashidx++;
    }
    return 1;
}

小结

Redis中的字典数据结构使用哈希表来实现,用来存储key-value键值元素;
字典使用两个哈希表,一般只使用ht[0],只有当Rehash时候才使用ht[0];
哈希表采用链表的方式解决键碰撞问题;
Redis的Rehash操作是渐进式的,服务器程序会主动Rehash,在查找、添加、删除元素等操作时也会在Rehash进行时执行一次rehash操作。

字典的内容实在太多,操作比较繁琐,应该是Redis中最复杂的底层数据结构了,本文分析的绝对不够深入,希望以后有时间再修改吧,暂时先这样。到目前为止,Redis六种内部数据结构,同时也是底层操作的实现讲解全部结束,后面的文章将进入五种基本数据类型指令的实现,字符串(String)、哈希表(Hash)、列表(List)、集合(Set)、有序集合(Sorted Set)的各种指令的实现。

我自己对Redis2.8.2源码的注释,有时间找个机会放出来。


最后感谢黄健宏(huangz1990)的Redis设计与实现及其他对Redis2.6源码的相关注释对我在研究Redis2.8源码方面的帮助。
陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
MySQL的位置:數據庫和編程MySQL的位置:數據庫和編程Apr 13, 2025 am 12:18 AM

MySQL在數據庫和編程中的地位非常重要,它是一個開源的關係型數據庫管理系統,廣泛應用於各種應用場景。 1)MySQL提供高效的數據存儲、組織和檢索功能,支持Web、移動和企業級系統。 2)它使用客戶端-服務器架構,支持多種存儲引擎和索引優化。 3)基本用法包括創建表和插入數據,高級用法涉及多表JOIN和復雜查詢。 4)常見問題如SQL語法錯誤和性能問題可以通過EXPLAIN命令和慢查詢日誌調試。 5)性能優化方法包括合理使用索引、優化查詢和使用緩存,最佳實踐包括使用事務和PreparedStatemen

MySQL:從小型企業到大型企業MySQL:從小型企業到大型企業Apr 13, 2025 am 12:17 AM

MySQL適合小型和大型企業。 1)小型企業可使用MySQL進行基本數據管理,如存儲客戶信息。 2)大型企業可利用MySQL處理海量數據和復雜業務邏輯,優化查詢性能和事務處理。

幻影是什麼讀取的,InnoDB如何阻止它們(下一個鍵鎖定)?幻影是什麼讀取的,InnoDB如何阻止它們(下一個鍵鎖定)?Apr 13, 2025 am 12:16 AM

InnoDB通過Next-KeyLocking機制有效防止幻讀。 1)Next-KeyLocking結合行鎖和間隙鎖,鎖定記錄及其間隙,防止新記錄插入。 2)在實際應用中,通過優化查詢和調整隔離級別,可以減少鎖競爭,提高並發性能。

mysql:不是編程語言,而是...mysql:不是編程語言,而是...Apr 13, 2025 am 12:03 AM

MySQL不是一門編程語言,但其查詢語言SQL具備編程語言的特性:1.SQL支持條件判斷、循環和變量操作;2.通過存儲過程、觸發器和函數,用戶可以在數據庫中執行複雜邏輯操作。

MySQL:世界上最受歡迎的數據庫的簡介MySQL:世界上最受歡迎的數據庫的簡介Apr 12, 2025 am 12:18 AM

MySQL是一種開源的關係型數據庫管理系統,主要用於快速、可靠地存儲和檢索數據。其工作原理包括客戶端請求、查詢解析、執行查詢和返回結果。使用示例包括創建表、插入和查詢數據,以及高級功能如JOIN操作。常見錯誤涉及SQL語法、數據類型和權限問題,優化建議包括使用索引、優化查詢和分錶分區。

MySQL的重要性:數據存儲和管理MySQL的重要性:數據存儲和管理Apr 12, 2025 am 12:18 AM

MySQL是一個開源的關係型數據庫管理系統,適用於數據存儲、管理、查詢和安全。 1.它支持多種操作系統,廣泛應用於Web應用等領域。 2.通過客戶端-服務器架構和不同存儲引擎,MySQL高效處理數據。 3.基本用法包括創建數據庫和表,插入、查詢和更新數據。 4.高級用法涉及復雜查詢和存儲過程。 5.常見錯誤可通過EXPLAIN語句調試。 6.性能優化包括合理使用索引和優化查詢語句。

為什麼要使用mysql?利益和優勢為什麼要使用mysql?利益和優勢Apr 12, 2025 am 12:17 AM

選擇MySQL的原因是其性能、可靠性、易用性和社區支持。 1.MySQL提供高效的數據存儲和檢索功能,支持多種數據類型和高級查詢操作。 2.採用客戶端-服務器架構和多種存儲引擎,支持事務和查詢優化。 3.易於使用,支持多種操作系統和編程語言。 4.擁有強大的社區支持,提供豐富的資源和解決方案。

描述InnoDB鎖定機制(共享鎖,獨家鎖,意向鎖,記錄鎖,間隙鎖,下一鍵鎖)。描述InnoDB鎖定機制(共享鎖,獨家鎖,意向鎖,記錄鎖,間隙鎖,下一鍵鎖)。Apr 12, 2025 am 12:16 AM

InnoDB的鎖機制包括共享鎖、排他鎖、意向鎖、記錄鎖、間隙鎖和下一個鍵鎖。 1.共享鎖允許事務讀取數據而不阻止其他事務讀取。 2.排他鎖阻止其他事務讀取和修改數據。 3.意向鎖優化鎖效率。 4.記錄鎖鎖定索引記錄。 5.間隙鎖鎖定索引記錄間隙。 6.下一個鍵鎖是記錄鎖和間隙鎖的組合,確保數據一致性。

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
3 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳圖形設置
3 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您聽不到任何人,如何修復音頻
3 週前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解鎖Myrise中的所有內容
4 週前By尊渡假赌尊渡假赌尊渡假赌

熱工具

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。

WebStorm Mac版

WebStorm Mac版

好用的JavaScript開發工具

SecLists

SecLists

SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合,這些清單在安全評估過程中經常使用,而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表,幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上,他就可以存取所需的每種類型的清單。

Dreamweaver Mac版

Dreamweaver Mac版

視覺化網頁開發工具

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser是一個安全的瀏覽器環境,安全地進行線上考試。該軟體將任何電腦變成一個安全的工作站。它控制對任何實用工具的訪問,並防止學生使用未經授權的資源。