Redis 增加intset的降级特性

84366992

　　Redis的数据结构非常丰富，比如实现了内存紧凑型的数据结构:intset、ziplist等. Redis 2.3.16版本只提供了数据升级功能(比如16bit->32bit等)。
　　然而这种存在一个问题就，增加1个大数据，然后删除此大数据后，那么可能存在内存浪费现象，比如：ADD N 个16bit的数据,再ADD 1个64bit的数据,
　　再删除此64bit的数据,那么浪费的空间大小为:N*(64-16)bits。不知道redis里面为什么没有增加降级功能，而且代码量和复杂度都不高，也许intset的
　　使用都是在数据规模小的时候才用吧。所以我增加了降级功能(degrade)。
　　思路：类似于升级功能，升级是通过判断添加的数据的编码和intset头中存储的当前编码来判断是否需要升级，因为intset是有序的(小->大)，所以此升
　　级的Value要么插在contents最后(length)，要么在最前(0).
　　同样的道理，检测是通过intset里面有多少个64bit的数据和32bit的数据来决策的。比如：intset里面此时有1个64bit的数据，有非0个32bit的数据，要
　　删除这个64bit的数据，那么就需要降级。所以在intset的结构里增加num64bit、 num32bit两个即可。(不增加num16bit的字段，不是可以通过length
　　算出来，而是根本不需要此字段，减少内存的消耗)。
　　修改inset.h和inset.c文件,具体如下：
　　1、intset.h
　　intset的结构中增加num64bit、 num32bit字段，用来判断是否需要降级.
　　而且在intset.c的功能代码中增加了调试日志代码，可通过编译宏来控制。





1 #ifndef DEGRADE
2     #define DEGRADE 1
3 #endif
4
5 #ifndef INTSET_DEBUG
6     #define INTSET_DEBUG
7 #endif
8
9 typedef struct intset {
10     uint32_t encoding;
11     uint32_t length;
12 #ifdef DEGRADE
13     uint32_t num64bit;
14     uint32_t num32bit;
15 #endif   
16     int8_t contents[];
17 } intset;
View Code 　　2、intset.c
　　(1)intsetNew
　　修改函数，初始化新增字段值0.





1 /* Create an empty intset. */
2 intset *intsetNew(void) {
3     intset *is = zmalloc(sizeof(intset));
4     is->encoding = intrev32ifbe(INTSET_ENC_INT16);
5     is->length = 0;
6 #ifdef DEGRADE
7     is->num32bit = 0;
8     is->num64bit = 0;
9 #endif // DEGRADE
10     return is;
11 }
View Code 　　
　　(2)_intsetSetTypeNum
　　新增函数，根据add和remove来增加和减少num64bit、 num32bit值。





1 #ifdef DEGRADE
2 static void _intsetSetTypeNum(intset* is,uint8_t enc,int change)
3 {
4     if(enc == INTSET_ENC_INT32)
5     {
6      is->num32bit = intrev32ifbe(intrev32ifbe(is->num32bit) + change);
7     }
8     else if(enc == INTSET_ENC_INT64)
9     {
10          is->num64bit = intrev32ifbe(intrev32ifbe(is->num64bit) + change);
11     }
12 }
13 #endif
View Code 　　
　　(3)intsetUpgradeAndAdd和intsetAdd
　　修改函数，升级增加和普通增加，需要增加num64bit、 num32bit值。





1 /* Upgrades the intset to a larger encoding and inserts the given integer. */
2 static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
3     uint8_t curenc = intrev32ifbe(is->encoding);
4     uint8_t newenc = _intsetValueEncoding(value);
5     int length = intrev32ifbe(is->length);
6     int prepend = value < 0 ? 1 : 0;
7
8     /* First set new encoding and resize */
9     is->encoding = intrev32ifbe(newenc);
10     is = intsetResize(is,intrev32ifbe(is->length)+1);
11
12     /* Upgrade back-to-front so we don't overwrite values.
13      * Note that the "prepend" variable is used to make sure we have an empty
14      * space at either the beginning or the end of the intset. */
15     while(length--)
16         _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
17
18     /* Set the value at the beginning or the end. */
19     if (prepend)
20         _intsetSet(is,0,value);
21     else
22         _intsetSet(is,intrev32ifbe(is->length),value);
23     is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
24 #ifdef DEGRADE
25     _intsetSetTypeNum(is,newenc,1);
26 #endif
27 #ifdef INTSET_DEBUG
28     redisLog(3,"after intsetUpgradeAndAdd func, num:%lld,lenght:%d,32bitnum:%d,64bitnum:%d,encoding:%d\n",
29              value,intrev32ifbe(is->length),intrev32ifbe(is->num32bit),intrev32ifbe(is->num64bit),
30              intrev32ifbe(is->encoding));
31 #endif
32     return is;
33 }
34
35 /* Insert an integer in the intset */
36 intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
37     uint8_t valenc = _intsetValueEncoding(value);
38     uint32_t pos;
39     if (success) *success = 1;
40
41     /* Upgrade encoding if necessary. If we need to upgrade, we know that
42      * this value should be either appended (if > 0) or prepended (if < 0),
43      * because it lies outside the range of existing values. */
44     if (valenc > intrev32ifbe(is->encoding)) {
45         /* This always succeeds, so we don't need to curry *success. */
46         return intsetUpgradeAndAdd(is,value);
47     } else {
48         /* Abort if the value is already present in the set.
49          * This call will populate "pos" with the right position to insert
50          * the value when it cannot be found. */
51         if (intsetSearch(is,value,&pos)) {
52             if (success) *success = 0;
53             return is;
54         }
55
56         is = intsetResize(is,intrev32ifbe(is->length)+1);
57         if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
58     }
59
60     _intsetSet(is,pos,value);
61     is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
62 #ifdef DEGRADE
63     _intsetSetTypeNum(is,valenc,1);
64 #endif
65
66 #ifdef INTSET_DEBUG
67     redisLog(3,"after intsetAdd func, num:%lld,lenght:%d,32bitnum:%d,64bitnum:%d,encoding:%d\n",
68              value,intrev32ifbe(is->length),intrev32ifbe(is->num32bit),intrev32ifbe(is->num64bit),
69              intrev32ifbe(is->encoding));
70 #endif
71     return is;
72 }
View Code 　　
　　(4)isDegradeAndRemove
　　新增函数，判断删除1个数据时，是否需要降级.





1 /**< want to delete value whose type is enc. */
2 static uint8_t isDegradeAndRemove(intset* is,uint64_t value, uint8_t *degradeEnc)
3 {
4
5     uint8_t enc = _intsetValueEncoding(value);
6     if(intrev32ifbe(is->length)>1&&intsetSearch(is,value,NULL))
7     {
8         if((enc == INTSET_ENC_INT64) && (intrev32ifbe(is->num64bit) == 1))
9         {
10             if(intrev32ifbe(is->num32bit)>0)
11             {
12                 if(degradeEnc)*degradeEnc = INTSET_ENC_INT32;
13                 return 1;
14             }
15             else
16             {
17                 if(degradeEnc)*degradeEnc = INTSET_ENC_INT16;
18                 return 1;
19             }
20         }
21         else if((enc == INTSET_ENC_INT32) && (intrev32ifbe(is->num32bit) == 1))
22         {
23             if(intrev32ifbe(is->num64bit) == 0)
24             {
25                 if(degradeEnc)*degradeEnc = INTSET_ENC_INT16;
26                 return 1;
27             }
28         }
29     }
30     return 0;
31 }
View Code 　　
　　(5)intSetDegradeAndRemove
　　新增函数，删除降级





1 static intset *intSetDegradeAndRemove(intset *is, int64_t value, uint8_t degradeEnc)
2 {
3     uint8_t curEnc = intrev32ifbe(is->encoding);
4     int length = intrev32ifbe(is->length);
5     uint8_t loop,temp,prepend = value>0?0:1;
6
7     //first:set the encode
8     is->encoding = intrev32ifbe(degradeEnc);
9 #if 0
10     if(!prepend)//delete +
11     {
12         for(loop=0;looplength),intrev32ifbe(is->num32bit),intrev32ifbe(is->num64bit),
36              intrev32ifbe(is->encoding));
37 #endif
38     
39     return is;
40
41 }
View Code 　　
　　(6)intsetRemove
　　修改函数，增加了删除降级代码和普通删除操作，需要减少num64bit、 num32bit值。





1 /* Delete integer from intset */
2 intset *intsetRemove(intset *is, int64_t value, int *success) {
3     uint8_t valenc = _intsetValueEncoding(value);
4     uint32_t pos;
5     if (success) *success = 0;
6
7 #ifdef DEGRADE
8     uint8_t degrade;
9     if(isDegradeAndRemove(is,value,&degrade))
10     {
11         if(success) *success = 1;
12         return intSetDegradeAndRemove(is,value,degrade);
13     }
14 #endif
15     if (valenc encoding) && intsetSearch(is,value,&pos)) {
16         uint32_t len = intrev32ifbe(is->length);
17
18         /* We know we can delete */
19         if (success) *success = 1;
20
21         /* Overwrite value with tail and update length */
22         if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
23         is = intsetResize(is,len-1);
24         is->length = intrev32ifbe(len-1);
25 #ifdef DEGRADE
26         _intsetSetTypeNum(is,valenc,-1);
27 #ifdef INTSET_DEBUG
28         redisLog(3,"after intsetRemove func, num:%lld,lenght:%d,32bitnum:%d,64bitnum:%d,encoding:%d\n",
29              value,intrev32ifbe(is->length),intrev32ifbe(is->num32bit),intrev32ifbe(is->num64bit),
30              intrev32ifbe(is->encoding));
31 #endif
32 #endif   
33     }
34     return is;
35 }
View Code 　　总结：刚学习redis，发现里面丰富的数据结构深深的吸引住了我，学习intset的时候，发现没有降级功能（当然redis对intset的entry使用做了限制，默认不超过512个），自己就手动加了这个功能。
　　也希望对redis的源码感兴趣的同学，能动手实践一下。抽空把在linux下的实验结果贴出来，可以明显看见内存是消耗是减少的，而且代码里面还增加了调试，可以看出数据编码和插入删除数据
　　的变化。
　　ps:其实5.23号写了这篇文章，今天修改了些内容，重新发布一下。