redis源码剖析(5):基础数据结构inset

2024-04-27 22:48

本文主要是介绍redis源码剖析(5):基础数据结构inset,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

 

1、intset概述

2、inset分析

2.1 定义

2.2 新增元素

2.3 升级

2.4 总结


1、intset概述

       整数集合是 redis 对外数据结构set的底层实现之一,当集合元素不大于设定值并且元素都是整数时,就会用intset作为set的底层数据结构。

2、inset分析

2.1 定义

inset结构体定义如下:

typedef struct intset {uint32_t encoding;  // 编码方式,一个元素所需要的内存大小uint32_t length;    // 集合长度int8_t contents[];  // 集合数组
} intset;
  • encodinginset的编码方式,有3种编码方式,分别对应不同范围的整型:

      #define INTSET_ENC_INT16 (sizeof(int16_t))  // -32768~32767#define INTSET_ENC_INT32 (sizeof(int32_t))  // -2147483648~2147483647#define INTSET_ENC_INT64 (sizeof(int64_t))  // -2^63~2^63-1
    

    intset的编码是由最大的一个数决定的,如果有一个数是int64,那么整个inset的编码都是int64。

  • lengthinset的整数个数
  • contents整数数组

   intset的内存是连续的,所有的数据增删改查操作都是在内存地址偏移的基础上进行的,并且整数的保存也是有序的,一个保存了5个int16的intset的内存示意图如下:

intest

由于intset是在内存上直接操作赋值,并且所存储的值都超过了一个字节,所以需要考虑大小端的问题:

大端模式,是指数据的高字节保存在内存的低地址中,而数据的低字节保存在内存的高地址中,这样的存储模式有点儿类似于把数据当作字符串顺序处理:地址由小向大增加,而数据从高位往低位放;这和我们的阅读习惯一致。
小端模式,是指数据的高字节保存在内存的高地址中,而数据的低字节保存在内存的低地址中,这种存储模式将地址的高低和数据位权有效地结合起来,高地址部分权值高,低地址部分权值低。

     redis 的所有存储方式都是小端存储,在endianconv.h中有一段大小端的宏定义,如果当前cpu的字节序为大端就进行相应的转换:

#if (BYTE_ORDER == LITTLE_ENDIAN)
#define memrev16ifbe(p)
#define memrev32ifbe(p)
#define memrev64ifbe(p)
#define intrev16ifbe(v) (v)
#define intrev32ifbe(v) (v)
#define intrev64ifbe(v) (v)
#else
#define memrev16ifbe(p) memrev16(p)
#define memrev32ifbe(p) memrev32(p)
#define memrev64ifbe(p) memrev64(p)
#define intrev16ifbe(v) intrev16(v)
#define intrev32ifbe(v) intrev32(v)
#define intrev64ifbe(v) intrev64(v)
#endif

      在intset相关的源码中有很多intrev32ifbe之类的操作就是在进行大小端转换。大小端深入的一些知识点就不在这做详解,可以自行google或百度。

2.2 新增元素

      这里针对intset的新增元素的过程做一个解析,因为这个过程涉及到了intset的升级、查找和插入。
      首先看新增元素的主体函数:

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {    // 新增uint8_t valenc = _intsetValueEncoding(value);   // 获取对应value编码uint32_t pos;if (success) *success = 1;if (valenc > intrev32ifbe(is->encoding)) {  // 编码大于当前,升级新增/* This always succeeds, so we don't need to curry *success. */return intsetUpgradeAndAdd(is,value);   // 升级并新增} else {if (intsetSearch(is,value,&pos)) {  // 查找是否存在,pos为小于value的最大值的posif (success) *success = 0;return is;}is = intsetResize(is,intrev32ifbe(is->length)+1);   // 重新多申请一个空间if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);   // 如果没有找到pos是小于该数字的前一个, 将pos后数据后移一位}_intsetSet(is,pos,value);is->length = intrev32ifbe(intrev32ifbe(is->length)+1);return is;
}

       这个函数获取了value值对应的编码,这个编码是根据3种编码的数据范围确定的。如果待插入数据的编码大于当前intset的编码,就需要进行升级,这个先跳过,我们先看正常的新增流程。
为了确保intset元素的唯一性,再插入之前会进行一次查找,intsetSearch函数定义如下:

static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) { // 查找int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;int64_t cur = -1;/* The value can never be found when the set is empty */if (intrev32ifbe(is->length) == 0) {    // intset空值判断if (pos) *pos = 0;return 0;} else {if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {if (pos) *pos = intrev32ifbe(is->length);   // 如果value大于当前intset的最大值,将pos赋值为lengthreturn 0;} else if (value < _intsetGet(is,0)) {if (pos) *pos = 0;  // 如果value小于当前intset的最小值,将pos赋值为0return 0;}}while(max >= min) { // 二分查找mid = ((unsigned int)min + (unsigned int)max) >> 1; // (min+max)/2cur = _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;}
}

       上述函数的作用就是利用intset有序的特性,通过二分法对目标value进行查找,如果找到返回1,反之返回0,pos作为引用传入函数中,会被赋值为value在intset中对应的位置。
  intsetSearch中多次调用的_intsetGet是用来获取对应pos的value值的函数:

static int64_t _intsetGet(intset *is, int pos) {    // 获取值return _intsetGetEncoded(is,pos,intrev32ifbe(is->encoding));
}static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) {    // 根据encode获取对应的值int64_t v64;int32_t v32;int16_t v16;if (enc == INTSET_ENC_INT64) {memcpy(&v64,((int64_t*)is->contents)+pos,sizeof(v64));memrev64ifbe(&v64); // 大小端转换return v64;} else if (enc == INTSET_ENC_INT32) {memcpy(&v32,((int32_t*)is->contents)+pos,sizeof(v32));memrev32ifbe(&v32);return v32;} else {memcpy(&v16,((int16_t*)is->contents)+pos,sizeof(v16));memrev16ifbe(&v16);return v16;}
}

      可以看到intset在获取值的时候都是通过地址偏移、内存拷贝,然后进行大小端转换处理完成的。

      继续之前的新增元素流程,当查不到对应value时,会在原有内存的基础上进行realloc,多申请一个intset->encoding的内存。由于intset的内存为连续,因此插入时,比value大的元素都要向后移动一个intset->encoding,也就是intsetMoveTail函数干的活:

static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) {    // 将数据后移void *src, *dst;uint32_t bytes = intrev32ifbe(is->length)-from;uint32_t encoding = intrev32ifbe(is->encoding);if (encoding == INTSET_ENC_INT64) {src = (int64_t*)is->contents+from;dst = (int64_t*)is->contents+to;bytes *= sizeof(int64_t);} else if (encoding == INTSET_ENC_INT32) {src = (int32_t*)is->contents+from;dst = (int32_t*)is->contents+to;bytes *= sizeof(int32_t);} else {src = (int16_t*)is->contents+from;dst = (int16_t*)is->contents+to;bytes *= sizeof(int16_t);}memmove(dst,src,bytes); // 由于移动前后地址会有重叠,因此要利用memmove进行内存拷贝 memcpy无法保障结果正确性
}

       由于移动的操作是在原有内存地址基础上进行的,因此在这里不能用memcpy进行内存拷贝,需要用memmove。在内存重叠的情况下,memcpy在拷贝的过程中,可能部分地址在被拷贝之前就被新的值覆盖了,导致拷贝这部分地址时拷贝的并不是我们期望的值。依旧是老套路,感兴趣自己去google或百度吧!
       最后的_intsetSet_intsetGet差不多,就不多讲了。

2.3 升级

      上面只介绍了intset普通的新增场景,那么当插入的value大于当前intset的encode时就需要对intset进行升级,以适应更大的值:

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) { // 升级并且添加新元素uint8_t curenc = intrev32ifbe(is->encoding);uint8_t newenc = _intsetValueEncoding(value);int length = intrev32ifbe(is->length);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));/* Set the value at the beginning or the end. */if (prepend)    // 小于0在集合头部_intsetSet(is,0,value);else    // 在集合尾部_intsetSet(is,intrev32ifbe(is->length),value);is->length = intrev32ifbe(intrev32ifbe(is->length)+1);return is;
}

        首先当需要对原有intset进行升级时,插入的元素一定是大于当前intset的最大值或者小于当前intset的最小值的,因此带插入的value一定是在首尾,只需判断其正负即可。
       升级的操作主要是将原本数据的内存地址大小进行一个统一的变更,从原intsetlength+prepend开始,一个一个扩展迁移。
       进行完扩展迁移之后把带插入的元素插入到头或尾即可。
       一个INTSET_ENC_INT16->INTSET_ENC_INT32的升级示例如下图:

intsetupgrade

2.4 总结

intset主要有以下特性:

  1. 内存连续,数值存储有序、无重复
  2. 有三种编码方式,通过升级的方式进行编码切换
  3. 不支持降级
  4. 小端存储

其他一些删除、随机获取value等api就不详细介绍了。老套路,源码在intset.hintset.c中。

这篇关于redis源码剖析(5):基础数据结构inset的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/941722

相关文章

Redis在windows环境下如何启动

《Redis在windows环境下如何启动》:本文主要介绍Redis在windows环境下如何启动的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Redis在Windows环境下启动1.在redis的安装目录下2.输入·redis-server.exe

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》:本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键

Python基础语法中defaultdict的使用小结

《Python基础语法中defaultdict的使用小结》Python的defaultdict是collections模块中提供的一种特殊的字典类型,它与普通的字典(dict)有着相似的功能,本文主要... 目录示例1示例2python的defaultdict是collections模块中提供的一种特殊的字

Redis实现延迟任务的三种方法详解

《Redis实现延迟任务的三种方法详解》延迟任务(DelayedTask)是指在未来的某个时间点,执行相应的任务,本文为大家整理了三种常见的实现方法,感兴趣的小伙伴可以参考一下... 目录1.前言2.Redis如何实现延迟任务3.代码实现3.1. 过期键通知事件实现3.2. 使用ZSet实现延迟任务3.3

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

Redis分片集群的实现

《Redis分片集群的实现》Redis分片集群是一种将Redis数据库分散到多个节点上的方式,以提供更高的性能和可伸缩性,本文主要介绍了Redis分片集群的实现,具有一定的参考价值,感兴趣的可以了解一... 目录1. Redis Cluster的核心概念哈希槽(Hash Slots)主从复制与故障转移2.

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,:本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ