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

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

    背景：

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

    源碼：

        值對象redisObject：

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

        類型type：

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

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

        編碼encoding；

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

            #define OBJ_ENCODING_RAW 0             /*Raw representation 簡單動態(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編碼的簡單動態(tài)字符串*/
            #define OBJ_ENCODING_QUICKLIST 9     /* 基于壓縮列表的雙端列表實(shí)現(xiàn)的 快速表*/

        最后被訪問的時間lru：

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

        引用計數(shù)器refcount：    

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

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

        字符串：
            int：存放整形值的字符串。
            embstr：存放字符的短字符串(大小不超過44個字節(jié))。
            raw：存放字符的長字符串(大小不超過44個字節(jié))。
           
            embstr和raw的比較：
                raw調(diào)用2次內(nèi)存分配函數(shù)，釋放時當(dāng)然也需要釋放兩次。
                embstr調(diào)用1次內(nèi)存分配函數(shù)，分配一塊連續(xù)的內(nèi)存，釋放時只需釋放一次。

        列表(list)：

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

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

                應(yīng)用：

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

            雙端鏈表(linkedlist)：

                優(yōu)點(diǎn)：元素的個數(shù)較多時，訪問元素的時間比壓縮列表更快一些。
                缺點(diǎn)：因?yàn)槭请p向鏈表，故維護(hù)了前置指針、后置指針等結(jié)構(gòu)，占用了更多的內(nèi)存，且內(nèi)存不是連續(xù)的，容易產(chǎn)生內(nèi)存碎片。
                說明：當(dāng)無法滿足ziplist的條件時，使用linkedlist作為列表的內(nèi)部實(shí)現(xiàn)。
                應(yīng)用：當(dāng)列表對象元素較多時，壓縮列表就會轉(zhuǎn)化為更適合存儲大量元素的雙端鏈表。
               
            注意：只能小內(nèi)存編碼向大內(nèi)存編碼轉(zhuǎn)換。(若當(dāng)元素增刪頻繁時，數(shù)據(jù)向壓縮編碼轉(zhuǎn)換是非常消耗CPU的，得不償失)

            快速列表(quicklist)：

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

        哈希(hash)：

            壓縮列表(ziplist)：

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

            哈希表(hashtable)：

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

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

            rehash：采用增量式重哈希：

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

        集合(set)：

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

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

        有序集合(zset)：

            說明：redis給有序集合中的每個元素設(shè)置一個分?jǐn)?shù)(score)作為排序的依據(jù)。
           
            壓縮列表(ziplist)：
                應(yīng)用：當(dāng)元素個數(shù)小于zset-max-ziplist-entries(默認(rèn)128個) 且 每個元素的值都小于zset-max-ziplist-value(默認(rèn)64字節(jié))時，使用ziplist作為有序集合的內(nèi)部實(shí)現(xiàn)。
               
            跳躍表(skiplist)：
                結(jié)構(gòu)：跳躍表通過在每個節(jié)點(diǎn)中(基于層和跨度等)維持多個指向其它節(jié)點(diǎn)的指針來實(shí)現(xiàn)快速訪問。
                    查找時間復(fù)雜度平均O(logn)、最壞O(n)。
                應(yīng)用：當(dāng)不滿足ziplist條件時，使用skiplist作為內(nèi)部實(shí)現(xiàn)。

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

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

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