漫话Redis源码之六十七

这里主要是摘要算法，我曾写过md5sum, sha, 虽然不懂数学原理。

void xorStringObjectDigest(unsigned char *digest, robj *o) {
    o = getDecodedObject(o);
    xorDigest(digest,o->ptr,sdslen(o->ptr));
    decrRefCount(o);
}
 
/* This function instead of just computing the SHA1 and xoring it
 * against digest, also perform the digest of "digest" itself and
 * replace the old value with the new one.
 *
 * So the final digest will be:
 *
 * digest = SHA1(digest xor SHA1(data))
 *
 * This function is used every time we want to preserve the order so
 * that digest(a,b,c,d) will be different than digest(b,c,d,a)
 *
 * Also note that mixdigest("foo") followed by mixdigest("bar")
 * will lead to a different digest compared to "fo", "obar".
 */
void mixDigest(unsigned char *digest, void *ptr, size_t len) {
    SHA1_CTX ctx;
    char *s = ptr;
 
    xorDigest(digest,s,len);
    SHA1Init(&ctx);
    SHA1Update(&ctx,digest,20);
    SHA1Final(digest,&ctx);
}
 
void mixStringObjectDigest(unsigned char *digest, robj *o) {
    o = getDecodedObject(o);
    mixDigest(digest,o->ptr,sdslen(o->ptr));
    decrRefCount(o);
}
 
/* This function computes the digest of a data structure stored in the
 * object 'o'. It is the core of the DEBUG DIGEST command: when taking the
 * digest of a whole dataset, we take the digest of the key and the value
 * pair, and xor all those together.
 *
 * Note that this function does not reset the initial 'digest' passed, it
 * will continue mixing this object digest to anything that was already
 * present. */
void xorObjectDigest(redisDb *db, robj *keyobj, unsigned char *digest, robj *o) {
    uint32_t aux = htonl(o->type);
    mixDigest(digest,&aux,sizeof(aux));
    long long expiretime = getExpire(db,keyobj);
    char buf[128];
 
    /* Save the key and associated value */
    if (o->type == OBJ_STRING) {
        mixStringObjectDigest(digest,o);
    } else if (o->type == OBJ_LIST) {
        listTypeIterator *li = listTypeInitIterator(o,0,LIST_TAIL);
        listTypeEntry entry;
        while(listTypeNext(li,&entry)) {
            robj *eleobj = listTypeGet(&entry);
            mixStringObjectDigest(digest,eleobj);
            decrRefCount(eleobj);
        }
        listTypeReleaseIterator(li);
    } else if (o->type == OBJ_SET) {
        setTypeIterator *si = setTypeInitIterator(o);
        sds sdsele;
        while((sdsele = setTypeNextObject(si)) != NULL) {
            xorDigest(digest,sdsele,sdslen(sdsele));
            sdsfree(sdsele);
        }
        setTypeReleaseIterator(si);
    } else if (o->type == OBJ_ZSET) {
        unsigned char eledigest[20];
 
        if (o->encoding == OBJ_ENCODING_ZIPLIST) {
            unsigned char *zl = o->ptr;
            unsigned char *eptr, *sptr;
            unsigned char *vstr;
            unsigned int vlen;
            long long vll;
            double score;
 
            eptr = ziplistIndex(zl,0);
            serverAssert(eptr != NULL);
            sptr = ziplistNext(zl,eptr);
            serverAssert(sptr != NULL);
 
            while (eptr != NULL) {
                serverAssert(ziplistGet(eptr,&vstr,&vlen,&vll));
                score = zzlGetScore(sptr);
 
                memset(eledigest,0,20);
                if (vstr != NULL) {
                    mixDigest(eledigest,vstr,vlen);
                } else {
                    ll2string(buf,sizeof(buf),vll);
                    mixDigest(eledigest,buf,strlen(buf));
                }
 
                snprintf(buf,sizeof(buf),"%.17g",score);
                mixDigest(eledigest,buf,strlen(buf));
                xorDigest(digest,eledigest,20);
                zzlNext(zl,&eptr,&sptr);
            }
        } else if (o->encoding == OBJ_ENCODING_SKIPLIST) {
            zset *zs = o->ptr;
            dictIterator *di = dictGetIterator(zs->dict);
            dictEntry *de;
 
            while((de = dictNext(di)) != NULL) {
                sds sdsele = dictGetKey(de);
                double *score = dictGetVal(de);
 
                snprintf(buf,sizeof(buf),"%.17g",*score);
                memset(eledigest,0,20);
                mixDigest(eledigest,sdsele,sdslen(sdsele));
                mixDigest(eledigest,buf,strlen(buf));
                xorDigest(digest,eledigest,20);
            }
            dictReleaseIterator(di);
        } else {
            serverPanic("Unknown sorted set encoding");
        }
    } else if (o->type == OBJ_HASH) {
        hashTypeIterator *hi = hashTypeInitIterator(o);
        while (hashTypeNext(hi) != C_ERR) {
            unsigned char eledigest[20];
            sds sdsele;
 
            memset(eledigest,0,20);
            sdsele = hashTypeCurrentObjectNewSds(hi,OBJ_HASH_KEY);
            mixDigest(eledigest,sdsele,sdslen(sdsele));
            sdsfree(sdsele);
            sdsele = hashTypeCurrentObjectNewSds(hi,OBJ_HASH_VALUE);
            mixDigest(eledigest,sdsele,sdslen(sdsele));
            sdsfree(sdsele);
            xorDigest(digest,eledigest,20);
        }
        hashTypeReleaseIterator(hi);
    } else if (o->type == OBJ_STREAM) {
        streamIterator si;
        streamIteratorStart(&si,o->ptr,NULL,NULL,0);
        streamID id;
        int64_t numfields;
 
        while(streamIteratorGetID(&si,&id,&numfields)) {
            sds itemid = sdscatfmt(sdsempty(),"%U.%U",id.ms,id.seq);
            mixDigest(digest,itemid,sdslen(itemid));
            sdsfree(itemid);
 
            while(numfields--) {
                unsigned char *field, *value;
                int64_t field_len, value_len;
                streamIteratorGetField(&si,&field,&value,
                                           &field_len,&value_len);
                mixDigest(digest,field,field_len);
                mixDigest(digest,value,value_len);
            }
        }
        streamIteratorStop(&si);
    } else if (o->type == OBJ_MODULE) {
        RedisModuleDigest md = {{0},{0}};
        moduleValue *mv = o->ptr;
        moduleType *mt = mv->type;
        moduleInitDigestContext(md);
        if (mt->digest) {
            mt->digest(&md,mv->value);
            xorDigest(digest,md.x,sizeof(md.x));
        }
    } else {
        serverPanic("Unknown object type");
    }
    /* If the key has an expire, add it to the mix */
    if (expiretime != -1) xorDigest(digest,"!!expire!!",10);
}
 
/* Compute the dataset digest. Since keys, sets elements, hashes elements
 * are not ordered, we use a trick: every aggregate digest is the xor
 * of the digests of their elements. This way the order will not change
 * the result. For list instead we use a feedback entering the output digest
 * as input in order to ensure that a different ordered list will result in
 * a different digest. */
void computeDatasetDigest(unsigned char *final) {
    unsigned char digest[20];
    dictIterator *di = NULL;
    dictEntry *de;
    int j;
    uint32_t aux;
 
    memset(final,0,20); /* Start with a clean result */
 
    for (j = 0; j < server.dbnum; j++) {
        redisDb *db = server.db+j;
 
        if (dictSize(db->dict) == 0) continue;
        di = dictGetSafeIterator(db->dict);
 
        /* hash the DB id, so the same dataset moved in a different
         * DB will lead to a different digest */
        aux = htonl(j);
        mixDigest(final,&aux,sizeof(aux));
 
        /* Iterate this DB writing every entry */
        while((de = dictNext(di)) != NULL) {
            sds key;
            robj *keyobj, *o;
 
            memset(digest,0,20); /* This key-val digest */
            key = dictGetKey(de);
            keyobj = createStringObject(key,sdslen(key));
 
            mixDigest(digest,key,sdslen(key));
 
            o = dictGetVal(de);
            xorObjectDigest(db,keyobj,digest,o);
 
            /* We can finally xor the key-val digest to the final digest */
            xorDigest(final,digest,20);
            decrRefCount(keyobj);
        }
        dictReleaseIterator(di);
    }
}