Redis zipmap

概要
Redis zipmapはString->String Map data structure optimized for sizeです.名前に惑わされないでください.実際には圧縮操作をしていません.連続したkey value集合です.mapを維持するために必要な追加情報が少ないのが特徴です.最低3バイトで到着できます.しかし、このような結果は時間の複雑さo(N)であり、操作に便利さが必要である.だから相対的に定義上ZIPMAP_BIGLENは254しかありません(でも254に着いたら貯金しないわけではありませんが、貯金します).
データ構造
zipmapのデータ構造は特に簡単で、2バイトまで簡単で、最初のバイトの保存長さ、最後のバイトの保存終了フラグZIPMAP_BIGLEN.ZIPMAP_BIGLEN=254
zipmapの作成

unsigned char *zipmapNew(void) {
    unsigned char *zm = zmalloc(2);

    zm[0] = 0; /* Length */
    zm[1] = ZIPMAP_END;
    return zm;
}

そう簡単です.2バイトを割り当てるスペースは、先頭バイトが長さ0、末尾バイトが終了IDに設定されます.
データエンコーディング
挿入について話す前に、key->valueのデータに対してzipmapがどのように保存されているかを見てみましょう.ソースコードの紹介を参照Memory layout of a zipmap,for the map“foo”=>“bar”,“hello”=>“world”:“foo”“bar”“hello”“world”

zmlenこれは私たちの最初のバイトがkey valueを保存する対数です.ただしzmlen<=ZIPMAP_BIGLENが大きくなったら彼は言わない.

lenは、保存された文字列の長さを表します.最初のlenはkeyの長さです.2番目のlenはvalue文字列の長さです.lenは254未満のときに1バイトで表される.このバイトはlenを保存する長さです.lenが254より大きい場合.このときsizeof(unsigned int)+1を使用して保存します.最初のバイトがZIPMAP_に設定されている場合BIGLEN.後の4バイトは実際のストレージ長に使用されます.

free 1バイトで、keyに対応するvalueを変更した後に残りの空間を表す.新しいvalueが元のvalueのlenより長いときに発生します.ZIPMAPを受けるVALUE_MAX_FREEの制限.ZIPMAPより大きい場合VALUE_MAX_FREE時にresize

をトリガー

keyvalueキー値対に直接対するデータがなく、

に直接接続する.
lenの符号化
私たちのlenには2つの保存方法があるからです.まずlen関連の符号化と復号化を見てみましょう

/*    len       lenZIPMAP_BIGLEN  sizeof(unsigned int)+1)*/
#define ZIPMAP_LEN_BYTES(_l) (((_l) < ZIPMAP_BIGLEN) ? 1 : sizeof(unsigned int)+1)

/* len    ，     p ，         ， p       len        */
static unsigned int zipmapEncodeLength(unsigned char *p, unsigned int len) {
    if (p == NULL) {
        return ZIPMAP_LEN_BYTES(len);//        
    } else {
        if (len < ZIPMAP_BIGLEN) {
            p[0] = len;// len

key value符号化
keyの符号化保存方式のkey対valueの符号化はvalue対key->valueのキー値対の符号化はkeyvalueであり、彼らの間には間隔がなく直接接続されている.key-valueに必要な全長を取得します

static unsigned long zipmapRequiredLength(unsigned int klen, unsigned int vlen) {
    unsigned int l;

    l = klen+vlen+3;// 3 = klen vlen free(   klen vlen   1)
    if (klen >= ZIPMAP_BIGLEN) l += 4;
    if (vlen >= ZIPMAP_BIGLEN) l += 4;
    return l;
}

key valueの復号
keyの場合、klenを取得してからklenを保存するのに必要な長さklenlenを取得し、klenlenの長さをオフセットして保存したkey値を取得します.

unsigned char * p;//    key   
unsigned int klen = zipmapDecodeLength(p);
unsigned int klenlen = zipmapEncodeLength(NULL,klen);
unsigned char* key = p+klenlen;

valueでは基本的にkeyと一致しています.valueが実際に位置を保存する前に、1バイトのfreeの空間があるので、1バイト以上オフセットする必要があります.

unsigned char * p;//    value   
unsigned int vlen = zipmapDecodeLength(p);
unsigned int vlenlen = zipmapEncodeLength(NULL,vlen);
unsigned char* key = p+vlenlen+1;

検索
エンコードと保存方法を知ってから、検索操作を見てみましょう.

static unsigned char *zipmapLookupRaw(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned int *totlen) {
 /*1*/   unsigned char *p = zm+1, *k = NULL;//zm               
    unsigned int l,llen;

    while(*p != ZIPMAP_END) {//    
        unsigned char free;

        /* Match or skip the key */
 /*2*/  l = zipmapDecodeLength(p);//    
        llen = zipmapEncodeLength(NULL,l);//  length   
/*3*/   if (key != NULL && k == NULL && l == klen && !memcmp(p+llen,key,l)) {//k null      null    
            /* Only return when the user doesn't care
             * for the total length of the zipmap. */
            if (totlen != NULL) {//     
                k = p;
            } else {
                return p;//    
            }
        }
        p += llen+l; //               
        /* Skip the value as well */
/*4*/l = zipmapDecodeLength(p);//value   
        p += zipmapEncodeLength(NULL,l);//  value     
        free = p[0];
        p += l+1+free; /* +1 to skip the free byte */
    }
    if (totlen != NULL) *totlen = (unsigned int)(p-zm)+1;
    return k;
}

私たちの検索keyにとっては特に簡単です.1.2バイト目が保存された最初のkeyの開始であるため、受信したzmを1オフセットします.2.keyの値3を取得する.keyを比較すると、成功は見つかったことを表し、keyの長さをずらすことに成功せず、4.1つのvalueの長さをオフセットし、valueがオフセットするときはfreeが保存している空き長さとfree自体の1バイトの長さを忘れないように注意する必要があります.最後にtotlenが転送された場合は、すべてのデータを保存する必要がある長さを表します.
挿入

unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update) {
    unsigned int zmlen, offset;
    unsigned int freelen, reqlen = zipmapRequiredLength(klen,vlen);//  key value        
    unsigned int empty, vempty;
    unsigned char *p;

    freelen = reqlen;
    if (update) *update = 0;
/*1*/p = zipmapLookupRaw(zm,key,klen,&zmlen);//  key           
    if (p == NULL) {//    
        /* Key not found: enlarge */
   /*2*/zm = zipmapResize(zm, zmlen+reqlen);//    
        p = zm+zmlen-1;
        zmlen = zmlen+reqlen;

        /* Increase zipmap length (this is an insert) */
        if (zm[0] < ZIPMAP_BIGLEN) zm[0]++;
    } else {
        /* Key found. Is there enough space for the new value? */
        /* Compute the total length: */
        if (update) *update = 1;
        freelen = zipmapRawEntryLength(p);//      key value    
        if (freelen < reqlen) {//     
            /* Store the offset of this key within the current zipmap, so
             * it can be resized. Then, move the tail backwards so this
             * pair fits at the current position. */
      /*3*/  offset = p-zm;//    key value   
            zm = zipmapResize(zm, zmlen-freelen+reqlen);//      
            p = zm+offset;//       key value   

            /* The +1 in the number of bytes to be moved is caused by the
             * end-of-zipmap byte. Note: the *original* zmlen is used. */
            memmove(p+reqlen, p+freelen,zmlen - offset -freelen -1 );//      
            /*
                      keyvlaue      （        resize     ）   keyvalue     
             p = zm +offset       p     key value     
             reqlen key value           p+reqlen      key value     （p+reqlen-1   key value     ）
             freelen     key value    p+freelen            key value     
                    zm         ，      
             zmlen       ，p+reqlen           ，p+freelen          
             offset zm              freelen    kevalue   
             zmlen - offset -freelen            -1                  
             */
            zmlen = zmlen-freelen+reqlen;//     
            freelen = reqlen;//         
        }
    }

    /* We now have a suitable block where the key/value entry can
     * be written. If there is too much free space, move the tail
     * of the zipmap a few bytes to the front and shrink the zipmap,
     * as we want zipmaps to be very space efficient. */
    empty = freelen-reqlen;
    if (empty >= ZIPMAP_VALUE_MAX_FREE) {//       
        /* First, move the tail  bytes to the front, then resize
         * the zipmap to be  bytes smaller. */
    /*4*/offset = p-zm;
        memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));//    
        /*
                    resize       
         */
        zmlen -= empty;//  
        zm = zipmapResize(zm, zmlen);
        p = zm+offset;//
        vempty = 0;
    } else {
        vempty = empty;
      
    }

    /* Just write the key + value and we are done. */
    /* Key: */
    /*5*/
    p += zipmapEncodeLength(p,klen);//     
    memcpy(p,key,klen);//  key
    p += klen;
    /* Value: */
    p += zipmapEncodeLength(p,vlen);
    *p++ = vempty;//  free
    memcpy(p,val,vlen);
    return zm;
}

key valueを設定するには、次の手順に従います.

は、まずkeyを検索操作しながらzmlen 2を返す.検索されなかった場合、keyvalueに必要な空間3を直接割り当てる.本来あるものを検索すると、現在必要とされている空間と元の空間の大きさを判断し、現在の空間が元の空間より小さい場合は、再び大きなメモリ空間を割り当て、p+freelen後のデータをp+reqlenに移動する必要がありますが、コードでは最後尾のタグがresizeのときに設定されていることに注意してください.だから移動する時に1つの移動が少なくなった.従来の空間が必要な空間よりも大きく、freelen-reqlenの場合に許容される最大freesizeよりも大きい場合、小さな空間を再割り当てする必要があり、p+freelen後のデータをp+reqlenに移動することも必要であるが、コードでは最後尾のタグがresizeの場合に設定されているため、移動時に移動5が少なくなっていることに注意する必要がある.最後に新しいkeyvalueを新しい空間に符号化します.

削除

unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted) {
    unsigned int zmlen, freelen;
    unsigned char *p = zipmapLookupRaw(zm,key,klen,&zmlen);//  
    if (p) {
        freelen = zipmapRawEntryLength(p);//    keyvalue   
        memmove(p, p+freelen, zmlen-((p-zm)+freelen+1));//            
        zm = zipmapResize(zm, zmlen-freelen);

        /* Decrease zipmap length */
        if (zm[0] < ZIPMAP_BIGLEN) zm[0]--;

        if (deleted) *deleted = 1;
    } else {
        if (deleted) *deleted = 0;
    }
    return zm;
}

削除は相対的に簡単ですkeyが見つかったら、またはこのkeyvalueの空間を取って、keyvalueの後ろのデータを前に移動して、サイズを変更します.
まとめ
zipmapのデータ構造は比較的簡単です.keyvalueの符号化を理解するだけで、迅速に把握できます.挿入と削除に関連するメモリの移動は、ソースコードに最後のビットが移動していないことに注意してください.resizeで設定されているので.
使用場所
The Redis Hash type uses this data structure for hashes composed of a small number of elements, to switch to a hash table once a given number ofelements is reached. hashtableが特に小さいときに使用されます.hashtableは符号化の追加情報が大きいsizeof(struct dictEntry)=24なので、zipmapは少なくとも3つしか必要ありません.最大11個です.クエリ効率でデータ量が特に小さい場合にシーケンスクエリにかかる時間コストはo(N)であるが,Nは小さいので許容できる.これによりメモリを節約できます.メモリを節約する方法もたくさん見られます