亚洲视频二区_亚洲欧洲日本天天堂在线观看_日韩一区二区在线观看_中文字幕不卡一区

公告:魔扣目錄網為廣大站長提供免費收錄網站服務,提交前請做好本站友鏈:【 網站目錄:http://www.430618.com 】, 免友鏈快審服務(50元/站),

點擊這里在線咨詢客服
新站提交
  • 網站:51998
  • 待審:31
  • 小程序:12
  • 文章:1030137
  • 會員:747

列表類型可以存儲一組按插入順序排序的字符串,它非常靈活,支持在兩端插入、彈出數據,可以充當棧和隊列的角色。

> LPUSH fruit Apple
(integer) 1
> RPUSH fruit banana
(integer) 2
> RPOP fruit
"banana"
> LPOP fruit
"apple"

本文探討redis中列表類型的實現。

ziplist

使用數組和鏈表結構都可以實現列表類型。Redis中使用的是鏈表結構。下面是一種常見的鏈表實現方式adlist.h:

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

Redis內部使用該鏈表保存運行數據,如主服務下所有的從服務器信息。
但Redis并不使用該鏈表保存用戶列表數據,因為它對內存管理不夠友好:
(1)鏈表中每一個節點都占用獨立的一塊內存,導致內存碎片過多。
(2)鏈表節點中前后節點指針占用過多的額外內存。
讀者可以思考一下,用什么結構可以比較好地解決上面的兩個問題?沒錯,數組。ziplist是一種類似數組的緊湊型鏈表格式。它會申請一整塊內存,在這個內存上存放該鏈表所有數據,這就是ziplist的設計思想。

定義

ziplist總體布局如下:

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
  • zlbytes:uint32_t,記錄整個ziplist占用的字節數,包括zlbytes占用的4字節。
  • zltail:uint32_t,記錄從ziplist起始位置到最后一個節點的偏移量,用于支持鏈表從尾部彈出或反向(從尾到頭)遍歷鏈表。
  • zllen:uint16_t,記錄節點數量,如果存在超過216-2個節點,則這個值設置為216-1,這時需要遍歷整個ziplist獲取真正的節點數量。
  • zlend:uint8_t,一個特殊的標志節點,等于255,標志ziplist結尾。其他節點數據不會以255開頭。

entry就是ziplist中保存的節點。entry的格式如下:

<prevlen> <encoding> <entry-data>
  • entry-data:該節點元素,即節點存儲的數據。
  • prevlen:記錄前驅節點長度,單位為字節,該屬性長度為1字節或5字節。
    ① 如果前驅節點長度小于254,則使用1字節存儲前驅節點長度。② 否則,使用5字節,并且第一個字節固定為254,剩下4個字節存儲前驅節點長度。
  • encoding:代表當前節點元素的編碼格式,包含編碼類型和節點長度。一個ziplist中,不同節點元素的編碼格式可以不同。編碼格式規范如下:
    ① 00pppppp(pppppp代表encoding的低6位,下同):字符串編碼,長度小于或等于63(26-1),長度存放在encoding的低6位中。② 01pppppp:字符串編碼, 長度小于或等于16383(214-1),長度存放在encoding的后6位和encoding后1字節中。③ 10000000:字符串編碼,長度大于16383(214-1),長度存放在encoding后4字節中。④ 11000000:數值編碼, 類型為int16_t,占用2字節。⑤ 11010000:數值編碼,類型為int32_t,占用4字節。⑥ 11100000:數值編碼,類型為int64_t,占用8字節。⑦ 11110000:數值編碼,使用3字節保存一個整數。⑧ 11111110:數值編碼,使用1字節保存一個整數。⑨ 1111xxxx:使用encoding低4位存儲一個整數,存儲數值范圍為0~12。該編碼下encoding低4位的可用范圍為0001~1101,encoding低4位減1為實際存儲的值。⑩ 11111111:255,ziplist結束節點。注意第②、③種編碼格式,除了encoding屬性,還需要額外的空間存儲節點元素長度。第⑨種格式也比較特殊,節點元素直接存放在encoding屬性上。該編碼是針對小數字的優化。這時entry-data為空。

字節序

encoding屬性使用多個字節存儲節點元素長度,這種多字節數據存儲在計算機內存中或者進行網絡傳輸時的字節順序稱為字節序,字節序有兩種類型:大端字節序和小端字節序。

  • 大端字節序:低字節數據保存在內存高地址位置,高字節數據保存在內存低地址位置。
  • 小端字節序:低字節數據保存在內存低地址位置,高字節數據保存在內存高地址位置。

數值0X44332211的大端字節序和小端字節序存儲方式如圖2-1所示。

Redis核心原理與實踐--列表實現原理之ziplist

 

CPU處理指令通常是按照內存地址增長方向執行的。使用小端字節序,CPU可以先讀取并處理低位字節,執行計算的借位、進位操作時效率更高。大端字節序則更符合人們的讀寫習慣。
ziplist采取的是小端字節序。
下面是Redis提供的一個簡單例子:

Redis核心原理與實踐--列表實現原理之ziplist

 

  • [0f 00 00 00]:zlbytes為15,代表整個ziplist占用15字節,注意該數值以小端字節序存儲。
  • [0c 00 00 00]:zltail為12,代表從ziplist起始位置到最后一個節點([02 f6])的偏移量。
  • [02 00]:zllen為2,代表ziplist中有2個節點。
  • [00 f3]:00代表前一個節點長度,f3使用了encoding第⑨種編碼格式,存儲數據為encoding低4位減1,即2。
  • [02 f6]:02代表前一個節點長度為2字節,f5編碼格式同上,存儲數據為5。
  • [ff]:結束標志節點。
    ziplist是Redis中比較復雜的數據結構,希望讀者結合上述屬性說明和例子,理解ziplist中數據的存放格式。

操作分析

提示:本節以下代碼如無特殊說明,均在ziplist.h、ziplist.c中。

ziplistFind函數負責在ziplist中查找元素:

unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) {
    int skipcnt = 0;
    unsigned char vencoding = 0;
    long long vll = 0;

    while (p[0] != ZIP_END) {
        unsigned int prevlensize, encoding, lensize, len;
        unsigned char *q;
        // [1]
        ZIP_DECODE_PREVLENSIZE(p, prevlensize);
        // [2]
        ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
        q = p + prevlensize + lensize;

        if (skipcnt == 0) {
            // [3]
            if (ZIP_IS_STR(encoding)) {
                if (len == vlen && memcmp(q, vstr, vlen) == 0) {
                    return p;
                }
            } else {
                // [4]
                if (vencoding == 0) {
                    if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
                        vencoding = UCHAR_MAX;
                    }
                    assert(vencoding);
                }

                // [5]
                if (vencoding != UCHAR_MAX) {
                    long long ll = zipLoadInteger(q, encoding);
                    if (ll == vll) {
                        return p;
                    }
                }
            }

            // [6]
            skipcnt = skip;
        } else {
            skipcnt--;
        }

        // [7]
        p = q + len;
    }

    return NULL;
}

參數說明:

  • p:指定從ziplist哪個節點開始查找。
  • vstr、vlen:待查找元素的內容和長度。
  • skip:間隔多少個節點才執行一次元素對比操作。

【1】計算當前節點prevlen屬性長度是1字節還是5字節,結果存放在prevlensize變量中。
【2】計算當前節點相關屬性,結果存放在如下變量中:
encoding:節點編碼格式。
lensize:額外存放節點元素長度的字節數,第②、③種格式的encoding編碼需要額外的空間存放節點元素長度。
len:節點元素的長度。
【3】如果當前節點元素是字符串編碼,則對比String的內容,若相等則返回。
【4】當前節點元素是數值編碼,并且還沒有對待查找內容vstr進行編碼,則對它進行編碼操作(編碼操作只執行一次),編碼后的數值存儲在vll變量中。
【5】如果上一步編碼成功(待查找內容也是數值),則對比編碼后的結果,否則不需要對比編碼結果。zipLoadInteger函數從節點元素中提取節點存儲的數值,與上一步得到的vll變量進行對比。
【6】skipcnt不為0,直接跳過節點并將skipcnt減1,直到skipcnt為0才對比數據。
【7】p指向p + prevlensize + lensize + len(數據長度),得到下一個節點的起始位置。

提示:由于源碼中部分函數太長,為了版面整潔,本書將其劃分為多個代碼段,并使用“// more”標志該函數后續還有其他代碼段,請讀者留意該標志。

下面看一下如何在ziplist中插入節點:

unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    ...
    // [1]
    if (p[0] != ZIP_END) {
        ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
    } else {
        unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
        if (ptail[0] != ZIP_END) {
            prevlen = zipRawEntryLength(ptail);
        }
    }

    // [2]
    if (zipTryEncoding(s,slen,&value,&encoding)) {
        reqlen = zipIntSize(encoding);
    } else {
        reqlen = slen;
    }

    // [3]
    reqlen += zipStorePrevEntryLength(NULL,prevlen);
    reqlen += zipStoreEntryEncoding(NULL,encoding,slen);

    // [4]
    int forcelarge = 0;
    nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
    if (nextdiff == -4 && reqlen < 4) {
        nextdiff = 0;
        forcelarge = 1;
    }

    // more
}

參數說明:

  • zl:待插入ziplist。
  • p:指向插入位置的后驅節點。
  • s、slen:待插入元素的內容和長度。

【1】計算前驅節點長度并存放到prevlen變量中。
如果p沒有指向ZIP_END,則可以直接取p節點的prevlen屬性,否則需要通過ziplist.zltail找到前驅節點,再獲取前驅節點的長度。
【2】對待插入元素的內容進行編碼,并將內容的長度存放在reqlen變量中。
zipTryEncoding函數嘗試將元素內容編碼為數值,如果元素內容能編碼為數值,則該函數返回1,這時value指向編碼后的值,encoding存儲對應編碼格式,否則返回0。
【3】zipStorePrevEntryLength函數計算prevlen屬性的長度(1字節或5字節)。
zipStoreEntryEncoding函數計算額外存放節點元素長度所需字節數(encoding編碼中第②、③種格式)。reqlen變量值添加這兩個函數的返回值后成為插入節點長度。
【4】zipPrevLenByteDiff函數計算后驅節點prevlen屬性長度需調整多少個字節,結果存放在nextdiff變量中。

假如p指向節點為e2,而插入前e2的前驅節點為e1,e2的prevlen存儲e1的長度。
插入后e2的前驅節點為插入節點,這時e2的prevlen應該存儲插入節點長度,所以e2的prevlen需要修改。圖2-2展示了一個簡單示例。

Redis核心原理與實踐--列表實現原理之ziplist

 

從圖2-2可以看到,后驅節點e2的prevlen屬性長度從1變成了5,則nextdiff變量為4。
如果插入節點長度小于4,并且原后驅節點e2的prevlen屬性長度為5,則這時設置forcelarge為1,代表強制保持后驅節點e2的prevlen屬性長度不變。讀者可以思考一下,為什么要這樣設計?
繼續分析__ziplistInsert函數:

unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    ...
    // [5]
    offset = p-zl;
    zl = ziplistResize(zl,curlen+reqlen+nextdiff);
    p = zl+offset;

    if (p[0] != ZIP_END) {
        // [6]
        memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);

        // [7]
        if (forcelarge)
            zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
        else
            zipStorePrevEntryLength(p+reqlen,reqlen);

        // [8]
        ZIPLIST_TAIL_OFFSET(zl) =
            intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
        // [9]
        zipEntry(p+reqlen, &tail);
        if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
        }
    } else {
        // [10]
        ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
    }

    // [11]
    if (nextdiff != 0) {
        offset = p-zl;
        zl = __ziplistCascadeUpdate(zl,p+reqlen);
        p = zl+offset;
    }

    // [12]
    p += zipStorePrevEntryLength(p,prevlen);
    p += zipStoreEntryEncoding(p,encoding,slen);
    if (ZIP_IS_STR(encoding)) {
        memcpy(p,s,slen);
    } else {
        zipSaveInteger(p,value,encoding);
    }
    // [13]
    ZIPLIST_INCR_LENGTH(zl,1);
    return zl;
}

【5】重新為ziplist分配內存,主要是為插入節點申請空間。新ziplist的內存大小為curlen+reqlen+nextdiff(curlen變量為插入前ziplist長度)。將p重新賦值為zl+offset(offset變量為插入節點的偏移量),是因為ziplistResize函數可能會為ziplist申請新的內存地址。
下面針對存在后驅節點的場景進行處理。
【6】將插入位置后面所有的節點后移,為插入節點騰出空間。移動空間的起始地址為p-nextdiff,減去nextdiff是因為后驅節點的prevlen屬性需要調整nextdiff長度。移動空間的長度為curlen-offset-1+nextdiff,減1是因為最后的結束標志節點已經在ziplistResize函數中設置了。
memmove是C語言提供的內存移動函數。
【7】修改后驅節點的prevlen屬性。
【8】更新ziplist.zltail,將其加上reqlen的值。
【9】如果存在多個后驅節點,則ziplist.zltail還要加上nextdiff的值。
如果只有一個后驅節點,則不需要加上nextdiff,因為這時后驅節點大小變化了nextdiff,但后驅節點只移動了reqlen。

提示:zipEntry函數會將給定節點的所有信息賦值到zlentry結構體中。zlentry結構體用于在計算過程中存放節點信息,實際存儲數據格式并不使用該結構體。讀者不要被tail這個變量名誤導,它只是指向插入節點的后驅節點,并不一定指向尾節點。

【10】這里針對不存在后驅節點的場景進行處理,只需更新最后一個節點偏移量ziplist.zltail。
【11】級聯更新。
【12】寫入插入數據。
【13】更新ziplist節點數量ziplist.zllen。

解釋一下以下代碼:

ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);

intrev32ifbe函數完成以下工作:如果主機使用的小端字節序,則不做處理。如果主機使用的大端字節序,則反轉數據字節序(數據第1位與第4位、第2位與第3位交換),這樣會將大端字節序數據轉化為小端字節序,或者將小端字節序數據轉化為大端字節序。
在上面的代碼中,如果主機CPU使用的是小端字節序,則intrev32ifbe函數不做任何處理。
如果主機CPU使用的是大端字節序,則從內存取出數據后,先調用intrev32ifbe函數將數據轉化為大端字節序后再計算。計算完成后,調用intrev32ifbe函數將數據轉化為小端字節序后再存入內存。

級聯更新

例2-1:
考慮一種極端場景,在ziplist的e2節點前插入一個新的節點ne,元素數據長度為254,如圖2-3所示。

Redis核心原理與實踐--列表實現原理之ziplist

 

插入節點如圖2-4所示。

Redis核心原理與實踐--列表實現原理之ziplist

 

插入節點后e2的prevlen屬性長度需要更新為5字節。
注意e3的prevlen,插入前e2的長度為253,所以e3的prevlen屬性長度為1字節,插入新節點后,e2的長度為257,那么e3的prevlen屬性長度也要更新了,這就是級聯更新。在極端情況下,e3后續的節點也要繼續更新prevlen屬性。
我們看一下級聯更新的實現:

unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;
    size_t offset, noffset, extra;
    unsigned char *np;
    zlentry cur, next;
    // [1]
    while (p[0] != ZIP_END) {
        // [2]
        zipEntry(p, &cur);
        rawlen = cur.headersize + cur.len;
        rawlensize = zipStorePrevEntryLength(NULL,rawlen);
              
        if (p[rawlen] == ZIP_END) break;
        // [3]
        zipEntry(p+rawlen, &next);
        
        if (next.prevrawlen == rawlen) break;
        // [4]
        if (next.prevrawlensize < rawlensize) {
            // [5]
            offset = p-zl;
            extra = rawlensize-next.prevrawlensize;
            zl = ziplistResize(zl,curlen+extra);
            p = zl+offset;

            // [6]
            np = p+rawlen;
            noffset = np-zl;

            if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {
                ZIPLIST_TAIL_OFFSET(zl) =
                    intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
            }

            // [7]
            memmove(np+rawlensize,
                np+next.prevrawlensize,
                curlen-noffset-next.prevrawlensize-1);
            zipStorePrevEntryLength(np,rawlen);

            // [8]
            p += rawlen;
            curlen += extra;
        } else {
            // [9]
            if (next.prevrawlensize > rawlensize) {
                zipStorePrevEntryLengthLarge(p+rawlen,rawlen);
            } else {
                // [10]
                zipStorePrevEntryLength(p+rawlen,rawlen);
            }
            // [11]
            break;
        }
    }
    return zl;
}

參數說明:

  • p:p指向插入節點的后驅節點,為了描述方便,下面將p指向的節點稱為當前節點。

【1】如果遇到ZIP_END,則退出循環。
【2】如果下一個節點是ZIP_END,則退出。
rawlen變量為當前節點長度,rawlensize變量為當前節點長度占用的字節數。
p[rawlen]即p的后驅節點的第一個字節。
【3】計算后驅節點信息。如果后驅節點的prevlen等于當前節點的長度,則退出。
【4】假設存儲當前節點長度需要使用actprevlen(1或者5)個字節,這里需要處理3種情況。情況1:后驅節點的prevlen屬性長度小于actprevlen,這時需要擴容,如例2-1中的場景。
【5】重新為ziplist分配內存。
【6】如果后驅節點非ZIP_END,則需要修改ziplist.zltail屬性。
【7】將當前節點后面所有的節點后移,騰出空間用來修改后驅節點的prevlen。
【8】將p指針指向后驅節點,繼續處理后面節點的prevlen。
【9】情況2:后驅節點的prevlen屬性長度大于actprevlen,這時需要縮容。為了不讓級聯更新繼續下去,這時強制后驅節點的prevlen保持不變。
【10】情況3:后驅節點的prevlen屬性長度等于actprevlen,只要修改后驅節點prevlen值,不需要調整ziplist的大小。
【11】情況2和情況3中級聯更新不需要繼續,退出。
回到上面__ziplistInsert函數中為什么要設置forcelarge為1的問題,這樣是為了避免插入小節點時,導致級聯更新現象的出現,所以強制保持后驅節點的prevlen屬性長度不變。

從上面的分析我們可以看到,級聯更新下的性能是非常糟糕的,而且代碼復雜度也高,那么怎么解決這個問題呢?我們先看一下為什么需要使用prevlen這個屬性?這是因為反向遍歷時,每向前跨過一個節點,都必須知道前面這個節點的長度。
既然這樣,我們把每個節點長度都保存一份到節點的最后位置,反向遍歷時,直接從前一個節點的最后位置獲取前一個節點的長度不就可以了嗎?而且這樣每個節點都是獨立的,插入或刪除節點都不會有級聯更新的現象。基于這種設計,Redis作者設計另一種結構listpack。設計listpack的目的是取代ziplist,但是ziplist使用范圍比較廣,替換起來比較復雜,所以目前只應用在新增加的Stream結構中。等到我們分析Stream時再討論listpack的設計。由此可見,優秀的設計并不是一蹴而就的。
ziplist提供常用函數如表2-1所示。

函數

作用

ziplistNew

創建一個空的ziplist

ziplistPush

在ziplist頭部或尾部添加元素

ziplistInsert

插入元素到ziplist指定位置

ziplistFind

查找給定的元素

ziplistDelete

刪除給定節點

即使使用新的listpack格式,每插入一個新節點,也還可能需要進行兩次內存拷貝。
(1)為整個鏈表分配新內存空間,主要是為新節點創建空間。
(2)將插入節點所有后驅節點后移,為插入節點騰出空間。
如果鏈表很長,則每次插入或刪除節點時都需要進行大量的內存拷貝,這個性能是無法接受的,那么如何解決這個問題呢?這時就要用到quicklist了。

分享到:
標簽:Redis
用戶無頭像

網友整理

注冊時間:

網站:5 個   小程序:0 個  文章:12 篇

  • 51998

    網站

  • 12

    小程序

  • 1030137

    文章

  • 747

    會員

趕快注冊賬號,推廣您的網站吧!
最新入駐小程序

數獨大挑戰2018-06-03

數獨一種數學游戲,玩家需要根據9

答題星2018-06-03

您可以通過答題星輕松地創建試卷

全階人生考試2018-06-03

各種考試題,題庫,初中,高中,大學四六

運動步數有氧達人2018-06-03

記錄運動步數,積累氧氣值。還可偷

每日養生app2018-06-03

每日養生,天天健康

體育訓練成績評定2018-06-03

通用課目體育訓練成績評定