Redis 增加intset的降级特性
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,°rade))
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号写了这篇文章，今天修改了些内容，重新发布一下。
页:
[1]