Redis原理篇之数据结构

typedef struct intset {
    //编码方式,支持存放16位,32位,64位整数
    uint32_t encoding;
    //元素个数
    uint32_t length;
    //整数数组,保存集合数据
    int8_t contents[];
} intset;

/* Note that these encodings are ordered, so:
 * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
/* 2字节整数,范围类似java的short */
#define INTSET_ENC_INT16 (sizeof(int16_t))
/* 4字节整数,范围类似java的int */
#define INTSET_ENC_INT32 (sizeof(int32_t))
/* 8字节整数,范围类似java的long */
#define INTSET_ENC_INT64 (sizeof(int64_t))

/* Insert an integer in the intset */
intset *intsetAdd(
        //需要插入的intset
        intset *is,
        //需要插入的新元素
        int64_t value,
        //是否插入成功
        uint8_t *success) {
    //获取当前值编码
    uint8_t valenc = _intsetValueEncoding(value);
    //要插入的位置
    uint32_t pos;
    if (success) *success = 1;

    /* Upgrade encoding if necessary. If we need to upgrade, we know that
     * this value should be either appended (if > 0) or prepended (if < 0),
     * because it lies outside the range of existing values. */
    //判断编码是不是超过了当前intset的编码
    if (valenc > intrev32ifbe(is->encoding)) {
        /* This always succeeds, so we don't need to curry *success. */
        //超出编码,需要升级
        return intsetUpgradeAndAdd(is,value);
    } else {
        //不需要进行数组编码升级,只需要将元素插入到指定位置即可
        /* Abort if the value is already present in the set.
         * This call will populate "pos" with the right position to insert
         * the value when it cannot be found. */
        //在当前intset中查找值与value一样的元素的角标--使用二分查找法
        //如果找到了,说明元素已经存在,无需再次插入,那么pos就是该元素的位置
        //否则pos指向比value大的前一个元素
        if (intsetSearch(is,value,&pos)) {
            //如果找到了,则无需插入,直接结束并返回
            if (success) *success = 0;
            return is;
        }

        //数组扩容
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        //移动数组中pos之后的元素到pos+1,给新元素腾出空间
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }

    //插入新元素
    _intsetSet(is,pos,value);
    //重置元素长度
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

/* Upgrades the intset to a larger encoding and inserts the given integer. */
/* 插入的元素比当前数组编码要大,因此数组需要进行扩容,但是这个新元素具体是插入头部还是尾部不确定
 *  因为该元素可能是一个负数!!!
 * */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    //获取当intset编码
    uint8_t curenc = intrev32ifbe(is->encoding);
    //获取新编码
    uint8_t newenc = _intsetValueEncoding(value);
    //获取元素个数
    int length = intrev32ifbe(is->length);
    //判断新元素是大于0还是小于0,小于0插入队列头部,大于0插入队尾
    int prepend = value < 0 ? 1 : 0;

    /* First set new encoding and resize */
    //重置编码为新编码
    is->encoding = intrev32ifbe(newenc);
    //重置数组大小--扩容
    is = intsetResize(is,intrev32ifbe(is->length)+1);

    /* Upgrade back-to-front so we don't overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */
    //倒序遍历,逐个搬运元素到新的位置,_intsetGetEncoded按照旧编码方式查找旧元素
    while(length--)
        //_intsetSet按照新编码方式将取出的旧元素插入到数组中
        //length+prepend: 如果新元素为负数,那么prepend为1,即旧元素后移的过程中,还会在数组头部腾出一个新位置
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    /* Set the value at the beginning or the end. */
    //插入新元素,prepend决定是数组头部还是尾部
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    //修改数组长度
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

/* Search for the position of "value". Return 1 when the value was found and
 * sets "pos" to the position of the value within the intset. Return 0 when
 * the value is not present in the intset and sets "pos" to the position
 * where "value" can be inserted. */
//返回1表示元素存在,我们不需要进行任何操作
//如果返回0,表示元素还不存在
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    //初始化二分查找需要的min,max,mid
    int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
    //mid对应的值
    int64_t cur = -1;

    /* The value can never be found when the set is empty */
   //如果数组为空则不用找了
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
        /* Check for the case where we know we cannot find the value,
         * but do know the insert position. */
        //数组不为空,判断value是否大于最大值,小于最小值
        if (value > _intsetGet(is,max)) {
            //大于最大值,插入队尾
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        } else if (value < _intsetGet(is,0)) {
            //小于最小值,插入队尾
            if (pos) *pos = 0;
            return 0;
        }
    }

    //二分查找
    while(max >= min) {
        mid = ((unsigned int)min + (unsigned int)max) >> 1;
        cur = _intsetGet(is,mid);
        if (value > cur) {
            min = mid+1;
        } else if (value < cur) {
            max = mid-1;
        } else {
            break;
        }
    }

    if (value == cur) {
        if (pos) *pos = mid;
        return 1;
    } else {
        if (pos) *pos = min;
        return 0;
    }
}

//哈希节点
typedef struct dictEntry {
    //键
    void *key;
    //值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    //下一个entry的指针
    struct dictEntry *next;
} dictEntry;

/* 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 {
    //entry数组,数组中保存的是指向entry的指针
    dictEntry **table;
    //哈希表的大小
    unsigned long size;
    //哈希表大小的掩码,总是等于size-1
    unsigned long sizemask;
    //entry的个数
    unsigned long used;
} dictht;

//字典
typedef struct dict {
    //dict类型,内置不同的hash函数
    dictType *type;
    //私有数据,在做特殊运算时使用
    void *privdata;
    //一个Dict包含两个哈希表,其中一个是当前数据,另一个一般为空,rehash时使用
    dictht ht[2];
    //rehash的进度,-1表示未开始
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    //rehash是否暂停,1则暂停,0则继续
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;

/* Expand the hash table if needed */
//如果需要的话就进行扩容
static int _dictExpandIfNeeded(dict *d)
{
    /* Incremental rehashing already in progress. Return. */
    //如果正在rehash,则返回ok
    if (dictIsRehashing(d)) return DICT_OK;

    /* If the hash table is empty expand it to the initial size. */
    //如果哈希表为空,则初始哈希表为默认大小4
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    /* If we reached the 1:1 ratio, and we are allowed to resize the hash
     * table (global setting) or we should avoid it but the ratio between
     * elements/buckets is over the "safe" threshold, we resize doubling
     * the number of buckets. */
    //d->ht[0].used >= d->ht[0].size: 说明哈希节点数量已经大于数组长度了,这个条件要满足
    //下面两个条件满足其中一个:
    //1.dict_can_resize: 当服务器执行BGSAVE或者BGREWRITERAO时,该值为假
    //2.d->ht[0].used/d->ht[0].size计算出来的就是负载因子
    //当负载因子大于5时,不管是否正在执行BGSAVE或者BGREWRITERAO,都会进行扩容
    //如果dict type 有expandAllowed函数,则会调用判断是否能够进行扩容
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio) &&
        dictTypeExpandAllowed(d))
    {
        //扩容带下为used+1,底层会对扩容大小进行判断,实际上找的是第一个大于等于used+1的2^n
        return dictExpand(d, d->ht[0].used + 1);
    }
    return DICT_OK;
}

/* Delete an element from a hash.
 * Return 1 on deleted and 0 on not found. */
//从hash中删除一个元素,删除成功返回1,没找到返回0
int hashTypeDelete(robj *o, sds field) {
    int deleted = 0;
    //底层采用压缩链表实现,这个暂时不管  
    if (o->encoding == OBJ_ENCODING_ZIPLIST) {
        unsigned char *zl, *fptr;

        zl = o->ptr;
        fptr = ziplistIndex(zl, ZIPLIST_HEAD);
        if (fptr != NULL) {
            fptr = ziplistFind(zl, fptr, (unsigned char*)field, sdslen(field), 1);
            if (fptr != NULL) {
                zl = ziplistDelete(zl,&fptr); /* Delete the key. */
                zl = ziplistDelete(zl,&fptr); /* Delete the value. */
                o->ptr = zl;
                deleted = 1;
            }
        }
    } 
    //底层采用hash实现
    else if (o->encoding == OBJ_ENCODING_HT) {
        //删除成功返回C_OK
        if (dictDelete((dict*)o->ptr, field) == C_OK) {
            deleted = 1;

            /* Always check if the dictionary needs a resize after a delete. */
            //删除成功后,检查是否需要重置DICT大小,如果需要则调用dictResize重置
            if (htNeedsResize(o->ptr)) dictResize(o->ptr);
        }

    } else {
        serverPanic("Unknown hash encoding");
    }
    return deleted;
}

htNeedsResize(dict *dict) {
    long long size, used;
    //哈希表大小--槽的数量就是数组长度
    size = dictSlots(dict);
    //entry数量
    used = dictSize(dict);
    //当哈希表大小大于4并且负载因子低于0.1,表示需要进行收缩
    return (size > DICT_HT_INITIAL_SIZE &&
            (used*100/size < HASHTABLE_MIN_FILL));
}

/* Resize the table to the minimal size that contains all the elements,
 * but with the invariant of a USED/BUCKETS ratio near to <= 1 */
int dictResize(dict *d)
{
    unsigned long minimal;
    //如果正在做bgsave或bgrewriteof或rehash,则返回错误
    if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
    //获取entry个数
    minimal = d->ht[0].used;
    //如果entry小于4,则重置为4
    if (minimal < DICT_HT_INITIAL_SIZE)
        minimal = DICT_HT_INITIAL_SIZE;
    //重置大小为minimal,其实是第一个大于等于minimal的2^n
    return dictExpand(d, minimal);
}

/* Expand or create the hash table,
 * when malloc_failed is non-NULL, it'll avoid panic if malloc fails (in which case it'll be set to 1).
 * Returns DICT_OK if expand was performed, and DICT_ERR if skipped. */
int _dictExpand(dict *d, unsigned long size, int* malloc_failed)
{
    if (malloc_failed) *malloc_failed = 0;

    /* the size is invalid if it is smaller than the number of
     * elements already inside the hash table */
    //如果当前entry数量超过了要申请的size大小,或者正在rehash,直接报错
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;
   //声明新的hash table
    dictht n; /* the new hash table */
    //扩容后的数组实际大小,第一个大于等于size的2^n次方
    unsigned long realsize = _dictNextPower(size);

    /* Rehashing to the same table size is not useful. */
    //计算得到的新数组大小与旧数组大小一致,返回错误信息
    if (realsize == d->ht[0].size) return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */
    //设置新的hash table的大小和掩码
    n.size = realsize;
    n.sizemask = realsize-1;
    if (malloc_failed) {
        n.table = ztrycalloc(realsize*sizeof(dictEntry*));
        *malloc_failed = n.table == NULL;
        if (*malloc_failed)
            return DICT_ERR;
    } else//为新的hash table分配内存: size*entrySize
        n.table = zcalloc(realsize*sizeof(dictEntry*));
    //新的hash table的used为0
    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. */
    //如果是第一次来,即进行哈希表的初始化,那么直接将
    //上面新创建的n赋值给ht[0]即可
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    //否则,需要rehash，此处需要把rehashidx设置为0
    //表示当前rehash的进度
    //在每次增删改查时都会触发rehash(渐进式hash下面会讲)
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

typedef struct quicklist {
    //头节点指针
    quicklistNode *head;
    //尾结点指针
    quicklistNode *tail;
    //所有zipList的entry的数量
    unsigned long count;        /* total count of all entries in all ziplists */
    //zipLists总数量
    unsigned long len;          /* number of quicklistNodes */
    //zipList的entry上限,默认值 -2 --8kb
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
    //首尾不压缩的节点数量
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    //内存重分配时的书签数量及数组,一般用不到
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

typedef struct quicklistNode {
    //前一个节点指针
    struct quicklistNode *prev;
    //下一个节点指针
    struct quicklistNode *next;
    //当前节点的ZipLisr指针
    unsigned char *zl;
    //当前节点的ZipList的字节大小
    unsigned int sz;             /* ziplist size in bytes */
    //当前节点的ZipList的entry个数
    unsigned int count : 16;     /* count of items in ziplist */
    //编码方式: 1.ziplist 2.lzf压缩模式
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    //数据容器类型(预留): 1. 其他 2. zipList
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    //是否被解压缩. 1.则说明被解压了,将来要重新压缩
    unsigned int recompress : 1; /* was this node previous compressed? */
    //测试用
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    //预留字段
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

//t_zset.c
typedef struct zskiplist {
    //头尾节点指针
    struct zskiplistNode *header, *tail;
    //节点数量
    unsigned long length;
    //最大的索引层级,默认为1
    int level;
} zskiplist;

//t_zset.c
typedef struct zskiplistNode {
    //节点存储的值--是sds类型
    sds ele;
    //节点分数--排序,查找用
    double score;
    //前一个节点指针--回退指针
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        //下一个节点指针
        struct zskiplistNode *forward;
        //索引跨度
        unsigned long span;
        //多级索引数组
    } level[];
} zskiplistNode;

/* Implements LPUSH/RPUSH/LPUSHX/RPUSHX. 
 * 'xx': push if key exists. */
//通用的列表插入命令处理
void pushGenericCommand(
    //封装客户端发送来的命令
    client *c, 
    //插入列表头部还是列表尾部
    int where, 
    //是否在Key存在的时候才进行插入操作,默认为false
    //即redis会帮我们自动创建不存在的key
    int xx) {
    int j;
   //redis命令为 lpush key dhy 123 456
   //这里argv[1]拿到的是key
   //redis默认有1-15个db数据库,c->db是去指定的数据库寻找这个key
   //拿到这个key对应的redisObject对象 
    robj *lobj = lookupKeyWrite(c->db, c->argv[1]);
    //该redisObject对象类型必须是OBJ_LIST才可以,如果不是直接返回
    if (checkType(c,lobj,OBJ_LIST)) return;
    //如果拿到的key为null
    if (!lobj) {
        //如果xx为true,说明当可以不存在的时候就不进行处理
        if (xx) {
            addReply(c, shared.czero);
            return;
        }
       //xx默认为false--redis会帮助我们创建一个quicklist对象
        lobj = createQuicklistObject();
        //设置quicklist对象中ziplist的属性
        //限制quicklist中每一个ziplist最大的大小,默认为-2,即8kb
        //是否压缩ziplist,默认为0,不开启压缩
        quicklistSetOptions(lobj->ptr, server.list_max_ziplist_size,
                            server.list_compress_depth);
        //执行向数据库db插入key的过程
        dbAdd(c->db,c->argv[1],lobj);
    }
    
    //lpush key dhy 123 456
    //从2开始是value集合
    //把value集合中的元素插入搭配list中
    for (j = 2; j < c->argc; j++) {
        listTypePush(lobj,c->argv[j],where);
        server.dirty++;
    }
    
    addReplyLongLong(c, listTypeLength(lobj));
    
    //发布事件
    char *event = (where == LIST_HEAD) ? "lpush" : "rpush";
    signalModifiedKey(c,c->db,c->argv[1]);
    notifyKeyspaceEvent(NOTIFY_LIST,event,c->argv[1],c->db->id);
}

robj *createQuicklistObject(void) {
    //创建一个quickList
    quicklist *l = quicklistCreate();
    //根据上面的quicklist创建一个redisObject
    robj *o = createObject(OBJ_LIST,l);
    //设置redisObj对象编码为quickList
    o->encoding = OBJ_ENCODING_QUICKLIST;
    return o;
}

robj *setTypeCreate(sds value) {
    //判断value是否是数值类型 long long
    if (isSdsRepresentableAsLongLong(value,NULL) == C_OK)
    //如果是整数类型,则采用Intset编码
        return createIntsetObject();
     //否在采用默认编码,也就是HT   
    return createSetObject();
}

robj *createIntsetObject(void) {
    //初始化INTSET并申请内存空间
    intset *is = intsetNew();
    //创建RedisObject
    robj *o = createObject(OBJ_SET,is);
    //指定编码为INTSET
    o->encoding = OBJ_ENCODING_INTSET;
    return o;
}

robj *createSetObject(void) {
    //初始化DICT类型
    dict *d = dictCreate(&setDictType,NULL);
    //创建redisObj
    robj *o = createObject(OBJ_SET,d);
    //设置编码为HT
    o->encoding = OBJ_ENCODING_HT;
    return o;
}

/* Add the specified value into a set.
 *
 * If the value was already member of the set, nothing is done and 0 is
 * returned, otherwise the new element is added and 1 is returned. */
int setTypeAdd(robj *subject, sds value) {
    long long llval;
    //如果已经是HT编码,则直接插入元素
    if (subject->encoding == OBJ_ENCODING_HT) {
        dict *ht = subject->ptr;
        dictEntry *de = dictAddRaw(ht,value,NULL);
        if (de) {
            dictSetKey(ht,de,sdsdup(value));
            dictSetVal(ht,de,NULL);
            return 1;
        }
    } 
    //编码为INTSET
    else if (subject->encoding == OBJ_ENCODING_INTSET) {
        //判断编码是否为整数
        if (isSdsRepresentableAsLongLong(value,&llval) == C_OK) {
        //是整数直接添加到intset里面
            uint8_t success = 0;
            subject->ptr = intsetAdd(subject->ptr,llval,&success);
            if (success) {
            //当intset元素数量超过set_max_intset_entries,则转为HT
                /* Convert to regular set when the intset contains
                 * too many entries. */
                if (intsetLen(subject->ptr) > server.set_max_intset_entries)
                    setTypeConvert(subject,OBJ_ENCODING_HT);
                return 1;
            }
        } else {
        //不是整数,转换为HT
            /* Failed to get integer from object, convert to regular set. */
            setTypeConvert(subject,OBJ_ENCODING_HT);

            /* The set *was* an intset and this value is not integer
             * encodable, so dictAdd should always work. */
            serverAssert(dictAdd(subject->ptr,sdsdup(value),NULL) == DICT_OK);
            return 1;
        }
    } else {
        serverPanic("Unknown set encoding");
    }
    return 0;
}

config get set_max_intset_entries

//zset结构
typedef struct zset {
    //Dict指针  
    dict *dict;
    //SkipList指针
    zskiplist *zsl;
} zset;

robj *createZsetObject(void) {
    zset *zs = zmalloc(sizeof(*zs));
    robj *o;
    //创建Dict
    zs->dict = dictCreate(&zsetDictType,NULL);
    //创建SkipList
    zs->zsl = zslCreate();
    //创建zset
    o = createObject(OBJ_ZSET,zs);
    //更改编码
    o->encoding = OBJ_ENCODING_SKIPLIST;
    return o;
}

void zaddGenericCommand(client *c, int flags) {
    ....
    /* Lookup the key and create the sorted set if does not exist. */
    //zadd添加元素时,先根据key找到zset,不存在则创建新的zset
    zobj = lookupKeyWrite(c->db,key);
    if (checkType(c,zobj,OBJ_ZSET)) goto cleanup;
    //判断键是否存在
    if (zobj == NULL) {//不存在
        if (xx) goto reply_to_client; /* No key + XX option: nothing to do. */
        if (server.zset_max_ziplist_entries == 0 ||
            server.zset_max_ziplist_value < sdslen(c->argv[scoreidx+1]->ptr))
        {
        //如果zset_max_ziplist_entries设置为了0就是禁用了ziplist编码
        //或者value大小超过了zset_max_ziplist_value ,采用HT+Skiplist
            zobj = createZsetObject();
        } else {
       //否则采用ziplist
            zobj = createZsetZiplistObject();
        }
        dbAdd(c->db,key,zobj);
    }
...
        int retval = zsetAdd(zobj, score, ele, flags, &retflags, &newscore);
...
}

robj *createZsetObject(void) {
//申请内存
    zset *zs = zmalloc(sizeof(*zs));
    robj *o;
//创建Dict
    zs->dict = dictCreate(&zsetDictType,NULL);
//创建SkipList
    zs->zsl = zslCreate();
    o = createObject(OBJ_ZSET,zs);
    o->encoding = OBJ_ENCODING_SKIPLIST;
    return o;
}

robj *createZsetZiplistObject(void) {
//创建ziplist
    unsigned char *zl = ziplistNew();
    robj *o = createObject(OBJ_ZSET,zl);
    o->encoding = OBJ_ENCODING_ZIPLIST;
    return o;
}

int zsetAdd(robj *zobj, double score, sds ele, int in_flags, int *out_flags, double *newscore) {
...
    /* Update the sorted set according to its encoding. */
    //判断编码方式
    if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {//是ziplist编码
        unsigned char *eptr;
         //判断当前元素是否已经存在,已经存在了则更新score即可   
        if ((eptr = zzlFind(zobj->ptr,ele,&curscore)) != NULL) {
             ....
            return 1;
        } else if (!xx) {
            /* Optimize: check if the element is too large or the list
             * becomes too long *before* executing zzlInsert. */ 
            zobj->ptr = zzlInsert(zobj->ptr,ele,score);
            //元素不存在,需要新增,则判断ziplist长度有没有超过限制大小
            //并且元素的大小有无超过限制
            if (zzlLength(zobj->ptr) > server.zset_max_ziplist_entries ||
                sdslen(ele) > server.zset_max_ziplist_value)
                //如果超过转换为HT+skipList编码
                zsetConvert(zobj,OBJ_ENCODING_SKIPLIST);
            if (newscore) *newscore = score;
            *out_flags |= ZADD_OUT_ADDED;
            return 1;
        } else {
            *out_flags |= ZADD_OUT_NOP;
            return 1;
        }
        //本身就是SkipList+HT编码，无需转换
    } else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
            ....
    } else {
        serverPanic("Unknown sorted set encoding");
    }
    return 0; /* Never reached. */
}

void hsetCommand(client *c) { //客户端相关命令和信息都被封装在了client中
    int i, created = 0;
    robj *o;
    //假设客户端命令为 hset user1 name Jack age 21        
    if ((c->argc % 2) == 1) {
        addReplyErrorFormat(c,"wrong number of arguments for '%s' command",c->cmd->name);
        return;
    }
    //判断hash的key是否存在,不存在就创建一个新的,默认采用ziplist编码
    if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
    //判断是否需要把ziplist转换Dict
    hashTypeTryConversion(o,c->argv,2,c->argc-1);

    for (i = 2; i < c->argc; i += 2)
    //执行插入操作
        created += !hashTypeSet(o,c->argv[i]->ptr,c->argv[i+1]->ptr,HASH_SET_COPY);

...
}

robj *hashTypeLookupWriteOrCreate(client *c, robj *key) {
    //查看key
    robj *o = lookupKeyWrite(c->db,key);
    if (checkType(c,o,OBJ_HASH)) return NULL;
    //不存在,则创建新的
    if (o == NULL) {
        o = createHashObject();
        dbAdd(c->db,key,o);
    }
    return o;
}

robj *createHashObject(void) {
    //默认采用ziplist编码,申请ziplist内存空间
    unsigned char *zl = ziplistNew();
    robj *o = createObject(OBJ_HASH, zl);
    o->encoding = OBJ_ENCODING_ZIPLIST;
    return o;
}

void hashTypeTryConversion(robj *o, robj **argv, int start, int end) {
    int i;
    //如果编码已经是HT了，那么直接返回,不需要进行编码转换  
    if (o->encoding != OBJ_ENCODING_ZIPLIST) return;
    
    //依次遍历命令中的field,value参数
    for (i = start; i <= end; i++) {
    //如果filed或者value超过hash_max_ziplist_value,则转换为HT
        if (sdsEncodedObject(argv[i]) &&
            sdslen(argv[i]->ptr) > server.hash_max_ziplist_value)
        {
            hashTypeConvert(o, OBJ_ENCODING_HT);
            break;
        }
    }
}

int hashTypeSet(robj *o, sds field, sds value, int flags) {
    int update = 0;
     //判断是否为ziplist编码
    if (o->encoding == OBJ_ENCODING_ZIPLIST) {
        unsigned char *zl, *fptr, *vptr;
       
        zl = o->ptr;
        //查询head指针
        fptr = ziplistIndex(zl, ZIPLIST_HEAD);
        //head不为空,说明ziplist不为空,开始查找key
        if (fptr != NULL) {
            fptr = ziplistFind(zl, fptr, (unsigned char*)field, sdslen(field), 1);
            //判断是否存在,如果已经存在则更新
            if (fptr != NULL) {
                /* Grab pointer to the value (fptr points to the field) */
                vptr = ziplistNext(zl, fptr);
                serverAssert(vptr != NULL);
                update = 1;

                /* Replace value */
                zl = ziplistReplace(zl, vptr, (unsigned char*)value,
                        sdslen(value));
            }
        }
         //不存在,则直接push
        if (!update) {
        //依次Push新的field和value到ziplist尾部
            /* Push new field/value pair onto the tail of the ziplist */
            zl = ziplistPush(zl, (unsigned char*)field, sdslen(field),
                    ZIPLIST_TAIL);
            zl = ziplistPush(zl, (unsigned char*)value, sdslen(value),
                    ZIPLIST_TAIL);
        }
        o->ptr = zl;

        /* Check if the ziplist needs to be converted to a hash table */
        //插入了新元素,检查list长度是否超出,超出转化为HT
        if (hashTypeLength(o) > server.hash_max_ziplist_entries)
            hashTypeConvert(o, OBJ_ENCODING_HT);
    } else if (o->encoding == OBJ_ENCODING_HT) {
    //HT编码,直接插入或覆盖
      ...
    } else {
        serverPanic("Unknown hash encoding");
    }

    /* Free SDS strings we did not referenced elsewhere if the flags
     * want this function to be responsible. */
    if (flags & HASH_SET_TAKE_FIELD && field) sdsfree(field);
    if (flags & HASH_SET_TAKE_VALUE && value) sdsfree(value);
    return update;
}