Redis中的set和java中的set集合有相似之处,它的元素不会按照插入的向后顺序而存储,且元素是不允许重复的。set内部使用到了intset(整数集合)和hashtable(哈希表)两种方式来存储元素,如果set存储的元素是整数,且当元素个数小于512个会选择intset存储,目的是减少内存空间,遇到两种情况会发生变化,就是当存储的元素个数达到512(通过set-max-intset-entries 配置)或者添加了非整数值时如:‘b’,set会选择hashtable作为存储结构。
整数集合intset是用来存储整数的集合,且存储是按照小到大的顺序来存储(可以二分查找),intset目的是用来节省内存,当Redis集合类型的元素都是整数并且都处在64位有符号整数范围之内时,使用该结构体存储,我们看一下它的结构:查看源码
typedef struct intset{
//编码类型
uint32_t encoding;
//集合元素数量
uint32_t length;
//存储元素的数组
int8_t contents[];
} intset;
//下面是相关函数
intset *intsetNew(void);
intset *intsetAdd(intset *is, int64_t value, uint8_t *success);
intset *intsetRemove(intset *is, int64_t value, int *success);
uint8_t intsetFind(intset *is, int64_t value);
int64_t intsetRandom(intset *is);
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value);
uint32_t intsetLen(const intset *is);
size_t intsetBlobLen(intset *is);
int intsetValidateIntegrity(const unsigned char *is, size_t size, int deep);
解释:
编码 | 值 |
---|---|
INTSET_ENC_INT16 | 该方式每个元素占2个字节,存储 -32768 到 32767 |
INTSET_ENC_INT32 | 该方式每个元素占4个字节,存储 32767到2147483647 或 -2147483647 到 -32768 |
INTSET_ENC_INT64 | 该方式每个元素占8个字节,存储 2147483647 到 922337203684775807 或 -922337203684775808 到 -2147483648 |
intset会根据插入的值判断是否扩容,根据插入内容来修改encoding使用什么类型,从而决定contents每个元素的字节数,紧跟着对contents进行扩容。
假如我们添加这样的数据 sadd 1 2 3
,底层会执行intsetAdd函数,它会选择INTSET_ENC_INT16
类型 去存储,且按照元素大小顺序,它在intset中的结构是这样的
如果我们再执行 sadd 32999
会发生什么?32999是超过了INTSET_ENC_INT16
类型的存储大小,如果硬塞进去就会内存溢出。所以为了防止内存溢出,intset在添加新元素的时候会先判断是直接插入新元素还是先扩容过后再插入新元素,扩容流程如下:
intset升级源码如下:
/* Upgrades the intset to a larger encoding and inserts the given integer. */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
uint8_t curenc = intrev32ifbe(is->encoding);
uint8_t newenc = _intsetValueEncoding(value);
int length = intrev32ifbe(is->length);
/ * 判断新插入的值是小于 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. */
while(length--)
_intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
/ *如果插入的值小于 0 ,则插头部,否则插入尾部。* /
/* Set the value at the beginning or the end. */
if (prepend)
_intsetSet(is,0,value);
else
_intsetSet(is,intrev32ifbe(is->length),value);
/ *修改intset的长度,将其加1 */
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
流程图如下:
上面案例升级之后的效果如下:
这样设计的目的就是为了节约内存,通常情况下当我们存储的元素在 -32768 到 32767
之间,就使用更小的存储空间,INT16,当插入元素超过该范围就升级更大的内存空间去存储,我们可以任意的存储INT16,INT32,INT64类型的整数不用担心内存问题。
需要注意的是:intset是没有降级的概念,一旦存储了INT32类型的元素那么数组的元素一直都是INT32类型了。
下面来分析一下添加的详细流程: 见Set源码
void saddCommand(redisClient *c) {
robj *set;
int j, added = 0;
set = lookupKeyWrite(c->db,c->argv[1]);
/ *如果set是空的就创建一个set*/
if (set == NULL) {
set = setTypeCreate(c->argv[2]);
dbAdd(c->db,c->argv[1],set);
} else {
if (set->type != REDIS_SET) {
addReply(c,shared.wrongtypeerr);
return;
}
}
/ *将元素添加到集合中*/
for (j = 2; j < c->argc; j++) {
c->argv[j] = tryObjectEncoding(c->argv[j]);
/ *setTypeAdd中会进行编码转化 */
if (setTypeAdd(set,c->argv[j])) added++;
}
// 如果有添加成功
if (added) {
// 发送键修改信号
signalModifiedKey(c->db,c->argv[1]);
// 发送事件
notifyKeyspaceEvent(REDIS_NOTIFY_SET,"sadd",c->argv[1],c->db->id);
}
// 将数据库设为dirty
server.dirty += added;
// 返回添加数量
addReplyLongLong(c,added);
}
这里添加操作会判断set是否是空的,空的就创建一个set,然后执行setTypeAdd把元素依次添加到集合中,接着看setTypeAdd方法的源码
int setTypeAdd(robj *subject, robj *value) {
long long llval;
/ * 这里判断编码,是选择 HT (hash)存储还是选择 intset */
if (subject->encoding == REDIS_ENCODING_HT) {
/ * 将 value 作为键值为 NULL,把元素元素存储到字典中*/
if (dictAdd(subject->ptr,value,NULL) == DICT_OK) {
incrRefCount(value);
return 1;
}
/ * 这里判断encoding 是否为intset,如果是整数就可以 */
} else if (subject->encoding == REDIS_ENCODING_INTSET) {
/ * 判断对象的值可以编码为整数,使用 intset存储 ,否则使用hash*/
if (isObjectRepresentableAsLongLong(value,&llval) == REDIS_OK) {
uint8_t success = 0;
subject->ptr = intsetAdd(subject->ptr,llval,&success);
if (success) {
/ *添加成功 ,这里在判断长度是否大于 512 ,大于就进行转换成hash*/
/ * REDIS_SET_MAX_INTSET_ENTRIES 默认 512 */
if (intsetLen(subject->ptr) > server.set_max_intset_entries)
setTypeConvert(subject,REDIS_ENCODING_HT);
return 1;
}
/ * 如果对象的值不能编码为整数,转换为 HT 编码 然后再执行添加操作*/
} else {
setTypeConvert(subject,REDIS_ENCODING_HT);
redisAssertWithInfo(NULL,value,dictAdd(subject->ptr,value,NULL) == DICT_OK);
incrRefCount(value);
return 1;
}
/ *编码错误* /
} else {
redisPanic("Unknown set encoding");
}
/ *添加失败,元素已经存在* /
return 0;
}
setTypeAdd的流程是这样的
文章结束,希望对你有数帮助,喜欢的话别忘了给个好评
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/u014494148/article/details/114572417
内容来源于网络,如有侵权,请联系作者删除!