redis中的數(shù)據(jù)結(jié)構(gòu)和編碼詳解

更新時(shí)間：2020年03月27日 08:52:27 作者：A__17

本文主要和大家分享幾種Redis數(shù)據(jù)結(jié)構(gòu)詳解，希望文中的案例和代碼，能幫助到大家。

redis中的數(shù)據(jù)結(jié)構(gòu)和編碼：

背景：

1>redis在內(nèi)部使用redisObject結(jié)構(gòu)體來(lái)定義存儲(chǔ)的值對(duì)象。
2>每種類型都有至少兩種內(nèi)部編碼，Redis會(huì)根據(jù)當(dāng)前值的類型和長(zhǎng)度來(lái)決定使用哪種編碼實(shí)現(xiàn)。
3>編碼類型轉(zhuǎn)換在Redis寫入數(shù)據(jù)時(shí)自動(dòng)完成，這個(gè)轉(zhuǎn)換過(guò)程是不可逆的，轉(zhuǎn)換規(guī)則只能從小內(nèi)存編碼向大內(nèi)存編碼轉(zhuǎn)換。

源碼：

值對(duì)象redisObject：

            typedef struct redisObject {
                unsigned type:4;                /* 對(duì)象類型 */
                unsigned encoding:4;            /* 內(nèi)部編碼 */
                unsigned lru:LRU_BITS;     /* lru time (relative to server.lruclock) */
                int refcount;                    /* 引用計(jì)數(shù)器，內(nèi)存回收機(jī)制就是基于該值實(shí)現(xiàn)的 */
                void *ptr;                        /* 若要存儲(chǔ)的是整數(shù)值則直接存儲(chǔ)數(shù)據(jù)，否則表示指向數(shù)據(jù)的指針 */
            } robj;

類型type：

說(shuō)明：查看當(dāng)前鍵的類型：type key

            #define OBJ_STRING 0     /*字符串對(duì)象*/
            #define OBJ_LIST 1        /*列表對(duì)象*/
            #define OBJ_SET 2        /*集合對(duì)象*/
            #define OBJ_ZSET 3        /*有序集合對(duì)象*/
            #define OBJ_HASH 4        /*哈希對(duì)象*/

編碼encoding；

說(shuō)明：查看當(dāng)前鍵的編碼：object encoding key

            #define OBJ_ENCODING_RAW 0             /*Raw representation 簡(jiǎn)單動(dòng)態(tài)字符串*/
            #define OBJ_ENCODING_INT 1             /*Encoded as integer long long類型整數(shù)*/
            #define OBJ_ENCODING_HT 2            /* Encoded as hash table 字典*/
            #define OBJ_ENCODING_ZIPMAP 3        /* Encoded as zipmap 壓縮map*/
            #define OBJ_ENCODING_LINKEDLIST 4     /* Encoded as regular linked list 雙端鏈表*/
            #define OBJ_ENCODING_ZIPLIST 5         /* Encoded as ziplist 壓縮列表*/
            #define OBJ_ENCODING_INTSET 6         /* Encoded as intset 整數(shù)集合*/
            #define OBJ_ENCODING_SKIPLIST 7     /* Encoded as skiplist 跳躍表*/
            #define OBJ_ENCODING_EMBSTR 8         /* Embedded sds string encoding embstr編碼的簡(jiǎn)單動(dòng)態(tài)字符串*/
            #define OBJ_ENCODING_QUICKLIST 9     /* 基于壓縮列表的雙端列表實(shí)現(xiàn)的快速表*/

最后被訪問(wèn)的時(shí)間lru：

            概念：記錄對(duì)象最后一次被訪問(wèn)的時(shí)間。
            說(shuō)明：
                1>查看當(dāng)前鍵的空閑時(shí)間(該命令不會(huì)更新lru字段)；object idletime key 。可以通過(guò)scan + object idletime key 來(lái)收集長(zhǎng)時(shí)間未被訪問(wèn)的數(shù)據(jù)，然后手動(dòng)清理。
                2>當(dāng)配置了maxmemory和maxmemory-policy=volatile-lru或者allkeys-lru時(shí)，若內(nèi)存超過(guò)了上限(maxmemory)后，則優(yōu)先回收長(zhǎng)時(shí)間沒有被訪問(wèn)的數(shù)據(jù)，從而回收內(nèi)存。

引用計(jì)數(shù)器refcount：

概念：記錄當(dāng)前對(duì)象被引用的次數(shù)，當(dāng)refcount=0時(shí)，可以安全回收當(dāng)前對(duì)象空間。
說(shuō)明：獲取當(dāng)前對(duì)象引用：object refcount key

類型對(duì)應(yīng)的編碼：

        字符串：
            int：存放整形值的字符串。
            embstr：存放字符的短字符串(大小不超過(guò)44個(gè)字節(jié))。
            raw：存放字符的長(zhǎng)字符串(大小不超過(guò)44個(gè)字節(jié))。

            embstr和raw的比較：
                raw調(diào)用2次內(nèi)存分配函數(shù)，釋放時(shí)當(dāng)然也需要釋放兩次。
                embstr調(diào)用1次內(nèi)存分配函數(shù)，分配一塊連續(xù)的內(nèi)存，釋放時(shí)只需釋放一次。

列表(list)：

            壓縮列表(ziplist)：
                結(jié)構(gòu)：所有數(shù)據(jù)都是采用線性連續(xù)的內(nèi)存結(jié)構(gòu)(大致可類比數(shù)組)，目的是為了減少內(nèi)存的占用，追求空間和時(shí)間的平衡。
                    1>以O(shè)(1)時(shí)間復(fù)雜度入隊(duì)和出隊(duì)。
                    2>讀寫操作涉及復(fù)雜的指針移動(dòng)，最壞時(shí)間復(fù)雜度為O(n2)，故列表的元素不易太多。
                    3>新增刪除操作涉及內(nèi)存重新分配，加大了操作的復(fù)雜性。

優(yōu)點(diǎn)：占用內(nèi)存較少，且占用的是一塊連續(xù)的內(nèi)存，故加載的速度相對(duì)更快一些。
缺點(diǎn)：當(dāng)元素的個(gè)數(shù)較大時(shí)，訪問(wèn)元素的時(shí)間較長(zhǎng)。

應(yīng)用：

適合存儲(chǔ)小對(duì)象和長(zhǎng)度有限(即使O(n2)的復(fù)雜度也不會(huì)太大)的數(shù)據(jù)。
當(dāng)元素個(gè)數(shù)小于list-max-ziplist-entries(默認(rèn)512) 且所有元素值的大小都小于list-max-ziplist-value(默認(rèn)64字節(jié))時(shí)，使用ziplist作為列表的內(nèi)部實(shí)現(xiàn)。

雙端鏈表(linkedlist)：

                優(yōu)點(diǎn)：元素的個(gè)數(shù)較多時(shí)，訪問(wèn)元素的時(shí)間比壓縮列表更快一些。
                缺點(diǎn)：因?yàn)槭请p向鏈表，故維護(hù)了前置指針、后置指針等結(jié)構(gòu)，占用了更多的內(nèi)存，且內(nèi)存不是連續(xù)的，容易產(chǎn)生內(nèi)存碎片。
                說(shuō)明：當(dāng)無(wú)法滿足ziplist的條件時(shí)，使用linkedlist作為列表的內(nèi)部實(shí)現(xiàn)。
                應(yīng)用：當(dāng)列表對(duì)象元素較多時(shí)，壓縮列表就會(huì)轉(zhuǎn)化為更適合存儲(chǔ)大量元素的雙端鏈表。

            注意：只能小內(nèi)存編碼向大內(nèi)存編碼轉(zhuǎn)換。(若當(dāng)元素增刪頻繁時(shí)，數(shù)據(jù)向壓縮編碼轉(zhuǎn)換是非常消耗CPU的，得不償失)

快速列表(quicklist)：

結(jié)構(gòu)：一個(gè)雙向鏈表，鏈表的每一個(gè)節(jié)點(diǎn)都是一個(gè)ziplist，故quicklist結(jié)合了雙向鏈表和壓縮列表的優(yōu)點(diǎn)。
Redis3.2開始，列表采用quicklist進(jìn)行編碼。

哈希(hash)：

壓縮列表(ziplist)：

應(yīng)用：當(dāng)元素個(gè)數(shù)小于hash-max-ziplist-entries(默認(rèn)512) 且所有元素value的大小都小于hash-max-ziplist-value(默認(rèn)64字節(jié))時(shí)，使用ziplist作為哈希的內(nèi)部實(shí)現(xiàn)。

哈希表(hashtable)：

                優(yōu)點(diǎn)：讀寫時(shí)間復(fù)雜度O(1)
                缺點(diǎn)：占用內(nèi)存較多。
                應(yīng)用：當(dāng)無(wú)法滿足ziplist的條件時(shí)，hashtable作為哈希的內(nèi)部實(shí)現(xiàn)。

hash算法：與傳統(tǒng)hash算法類似，根據(jù)key計(jì)算得到在哈希表中的位置，采用單鏈表解決沖突，達(dá)到加載因子時(shí)進(jìn)行擴(kuò)展，進(jìn)而引發(fā)重哈希。

rehash：采用增量式重哈希：

                概念：在擴(kuò)容時(shí)不會(huì)一次性對(duì)所有的key進(jìn)行rehash，而是將key的rehash操作分散延遲到其它操作(哈希表的查找、更新、刪除)中。
                優(yōu)點(diǎn)：避免由于大量的key在同一時(shí)間段進(jìn)行rehash操作導(dǎo)致服務(wù)短暫無(wú)響應(yīng)的問(wèn)題。
                過(guò)程：在增量式的rehash過(guò)程中，會(huì)使用到兩張哈希表：
                    查找：先從老表中查找，再?gòu)男卤碇胁檎?，此外還會(huì)對(duì)一些key進(jìn)行rehash操作。
                    新增：新增的鍵值對(duì)添加到新表中。

集合(set)：

            整數(shù)集合(intset)：
                結(jié)構(gòu)：有序、不重復(fù)的整數(shù)集。
                    1>查找時(shí)間復(fù)雜度為O(logn)
                    2>插入時(shí)間復(fù)雜度為O(n)
                優(yōu)點(diǎn)：占用的內(nèi)存遠(yuǎn)小于hashtable，
                應(yīng)用：當(dāng)元素都是整數(shù) 且元素個(gè)數(shù)小于set-max-intset-entries(默認(rèn)512)時(shí)，使用intset作為集合的內(nèi)部實(shí)現(xiàn)。

哈希表(hashtable)：當(dāng)無(wú)法滿足intset的條件時(shí)，使用hashtable作為集合的內(nèi)部實(shí)現(xiàn)。

有序集合(zset)：

            說(shuō)明：redis給有序集合中的每個(gè)元素設(shè)置一個(gè)分?jǐn)?shù)(score)作為排序的依據(jù)。

            壓縮列表(ziplist)：
                應(yīng)用：當(dāng)元素個(gè)數(shù)小于zset-max-ziplist-entries(默認(rèn)128個(gè)) 且每個(gè)元素的值都小于zset-max-ziplist-value(默認(rèn)64字節(jié))時(shí)，使用ziplist作為有序集合的內(nèi)部實(shí)現(xiàn)。

            跳躍表(skiplist)：
                結(jié)構(gòu)：跳躍表通過(guò)在每個(gè)節(jié)點(diǎn)中(基于層和跨度等)維持多個(gè)指向其它節(jié)點(diǎn)的指針來(lái)實(shí)現(xiàn)快速訪問(wèn)。
                    查找時(shí)間復(fù)雜度平均O(logn)、最壞O(n)。
                應(yīng)用：當(dāng)不滿足ziplist條件時(shí)，使用skiplist作為內(nèi)部實(shí)現(xiàn)。

內(nèi)存優(yōu)化：

        場(chǎng)景：有海量key和value都比較小的數(shù)據(jù)，在redis中如何存儲(chǔ)才更省內(nèi)存。
        原理：通過(guò)大幅減少key的數(shù)量來(lái)降低內(nèi)存的消耗。
        實(shí)現(xiàn)：在客戶端通過(guò)分組將海量的key根據(jù)一定的策略映射到一組hash對(duì)象中，由于value較小，故hash類型的對(duì)象會(huì)使用占用內(nèi)存較小的ziplist編碼。
            eg：如存在100萬(wàn)個(gè)鍵，可以映射到1000個(gè)hash中，每個(gè)hash保存1000個(gè)元素。

以上就是redis中的數(shù)據(jù)結(jié)構(gòu)和編碼詳解的詳細(xì)內(nèi)容，更多關(guān)于redis中的數(shù)據(jù)結(jié)構(gòu)和編碼的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: