redis数据结构之intset的实例详解

redis数据结构之intset的实例详解

在redis中,intset主要用于保存整数值,由于其底层是使用数组来保存数据的,因而当对集合进行数据添加时需要对集合进行扩容和迁移操作,因而也只有在数据量不大时redis才使用该数据结构来保存整数集合。其具体的底层数据结构如下:

typedef struct intset {

  // 编码方式
  uint32_t encoding;

  // 集合包含的元素数量
  uint32_t length;

  // 保存元素的数组
  int8_t contents[];

} intset;

整数集合主要有三个属性:encoding用于保存当前集合的编码,有16位,32位和64位三种;length保存了当前整数集合中保存的数据数量;contents属性则保存了具体的数据,其每个数据占用的位数由encoding属性指定。

这里主要需要进行说明的是redis的intset中数据是采用从小到大的顺序存储的,因而对于数据的查询可以采用二分法进行查询,具体的搜索代码如下:

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 */
  // 处理 is 为空时的情况
  if (intrev32ifbe(is->length) == 0) {
    if (pos) *pos = 0;
    return 0;
  } else {
    /* Check for the case where we know we cannot find the value,
     * but do know the insert position. */
    // 因为底层数组是有序的,如果 value 比数组中最后一个值都要大
    // 那么 value 肯定不存在于集合中,
    // 并且应该将 value 添加到底层数组的最末端
    if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
      if (pos) *pos = intrev32ifbe(is->length);
      return 0;
    // 因为底层数组是有序的,如果 value 比数组中最前一个值都要小
    // 那么 value 肯定不存在于集合中,
    // 并且应该将它添加到底层数组的最前端
    } else if (value < _intsetGet(is,0)) {
      if (pos) *pos = 0;
      return 0;
    }
  }

  // 在有序数组中进行二分查找
  // T = O(log N)
  while(max >= min) {
    mid = (min+max)/2;
    cur = _intsetGet(is,mid);
    if (value > cur) {
      min = mid+1;
    } else if (value < cur) {
      max = mid-1;
    } else {
      break;
    }
  }

  // 检查是否已经找到了 value
  if (value == cur) {
    if (pos) *pos = mid;
    return 1;
  } else {
    if (pos) *pos = min;
    return 0;
  }
}

此外,整数集合中具体还有两个需要说明的操作是升级和降级。升级指的是当向低编码的整数集合中添加位数较高的数值时,就会扩容并将整数集合中的所有元素都转换为高位数的编码格式,然后把新添加的元素插入到指定位置;降级指的是当将整数集合中唯一一个高位的元素删除时会将其余元素转换为低位数的编码格式,但是为了提升速率,redis中并不会为剩余元素重新分配内存并进行编码转换,而只是会将该高位元素给删除,并重新分配内存给剩余的元素,然后迁移数据。如图是inset保存数据的示例:

如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

时间: 2017-09-19

Redis 实现队列原理的实例详解

Redis 实现队列原理的实例详解 场景说明: ·用于处理比较耗时的请求,例如批量发送邮件,如果直接在网页触发执行发送,程序会出现超时 ·高并发场景,当某个时刻请求瞬间增加时,可以把请求写入到队列,后台在去处理这些请求 ·抢购场景,先入先出的模式 命令: rpush + blpop 或 lpush + brpop rpush : 往列表右侧推入数据 blpop : 客户端阻塞直到队列有值输出 简单队列: simple.php $stmt = $pdo->prepare('select id, c

Linux Redis 的安装步骤详解

 Linux Redis 的安装步骤详解 前言: Redis 是一个开源(BSD许可)的,内存中的数据结构存储系统,它可以用作数据库.缓存和消息中间件. 它支持多种类型的数据结构,如 字符串(strings), 散列(hashes), 列表(lists), 集合(sets), 有序集合(sorted sets) 与范围查询, bitmaps, hyperloglogs 和 地理空间(geospatial) 索引半径查询. redis 是完全开源免费的,是一个高性能的key-value数据库.Re

redis数据类型_动力节点Java学院整理

Redis支持5种数据类型,它们描述如下: Strings - 字符串 Redis的字符串是字节序列.在Redis中字符串是二进制安全的,这意味着他们有一个已知的长度,是没有任何特殊字符终止决定的,所以可以存储任何东西,最大长度可达512兆. 例子 redis 127.0.0.1:6379> SET name "yiibai" OK redis 127.0.0.1:6379> GET name "yiibai" 在上面的例子使用Redis命令set和ge

redis集群搭建教程及遇到的问题处理

这里,在一个Linux虚拟机上搭建6个节点的redis伪集群,思路很简单,一台虚拟机上开启6个redis实例,每个redis实例有自己的端口.这样的话,相当于模拟出了6台机器了,然后在以这6个实例组建redis集群就可以了. 前提:redis已经安装,目录为/usr/local/redis-4.0.1 如不会,可以参考一下文章  windows下安装redis    Linux下安装redis redis集群是用的ruby脚本,所以要想执行该脚本,需要ruby环境..对应redis的源码src目

python脚本实现Redis未授权批量提权

前言 本文主要给大家介绍了关于redis未授权批量提权的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. 安装依赖 sudo easy_install redis 使用 redis python hackredis.py usage: hackredis.py [-h] [-l IPLIST] [-p PORT] [-r ID_RSAFILE] [-sp SSH_PORT] For Example: -----------------------------------

Redis集群搭建全记录

Redis集群是一个提供在多个Redis节点间共享数据的程序集. Redis集群中不支持处理多个keys的命令. Redis集群通过分区来提供一定程度的可用性.在某个节点宕机或者不可用的时候可以继续处理命令. Redis集群数据分片 在Redis集群中,使用数据分片(sharding)而不是一致性hash(consistency hashing)来实现,一个Redis集群包含16384个哈希槽(hash slot),数据库中的每个键都存在这些哈希槽中的某一个,通过CRC16校验后对16384取模

Redis 集群搭建和简单使用教程

前言 Redis集群搭建的目的其实也就是集群搭建的目的,所有的集群主要都是为了解决一个问题,横向扩展. 在集群的概念出现之前,我们使用的硬件资源都是纵向扩展的,但是纵向扩展很快就会达到一个极限,单台机器的Cpu的处理速度,内存大小,硬盘大小没办法一直满足需求,而且机器纵向扩展的成本是相当高的.集群的出现就是能够让多台机器像一台机器一样工作,实现了资源的横向扩展. Redis是内存型数据库,当我们要存储的数据达到一定程度时,单台机器的内存满足不了我们的需求,搭建集群则是一种很好的解决方案. 介绍安

redis集群搭建_动力节点Java学院整理

现在项目上用redis的话,很少说不用集群的情况,毕竟如果生产上只有一台redis会有极大的风险,比如机器挂掉,或者内存爆掉,就比如我们生产环境曾今也遭遇到这种情况,导致redis内存不够挂掉的情况,当然这些都是我们及其不能容忍的,第一个必须要做到高可靠,其次才是高性能,好了,下面我来逐一搭建一下. 一:Redis集群搭建 1. 下载 首先去官网下载较新的3.2.0版本,下载方式还是非常简单的,比如官网介绍的这样. $ wget http://download.redis.io/releases

Redis集群的搭建图文教程

redis集群的特点: 1.机器多,能够保证redis服务器出现问题后,影响较小 2.自备主从结构,自动的根据算法划分主从结构.动态的实现 3.能够根据主从结构自动的实现高可用 4.实现数据文件的备份 3.Redis集群的搭建步骤: 准备9台服务器 3主6从 一个主机下有2个子节点 7000-7008 2.拷贝redis.conf文件到文件夹中 cp redis.conf 7000/redis-7000.conf mkdir 7000 7001 7002 7003 7004 7005 7006

docker redis5.0 cluster集群搭建的实现

系统环境:ubuntu16.04LTS 本文是使用 6 个 docker 容器搭建单机集群测试,实际环境如果是多台,可对应修改容器数量.端口号和集群 ip 地址,每台机器都按下面步骤同样操作即可. 拉取redis官方镜像 docker pull redis:5.0 创建配置文件和数据目录 创建目录 mkdir ~/redis_cluster cd ~/redis_cluster 新建一个模板文件sudo vim redis_cluster.tmpl,填入如下内容: # redis端口 port

详解docker搭建redis集群的环境搭建

本文介绍了docker搭建redis集群的环境搭建,分享给大家,废话不多说,具体如下: 下载镜像 docker pull redis 准备配置文件 mkdir /home/docker/redis/ wget https://raw.githubusercontent.com/antirez/redis/3.0/redis.conf -O /home/docker/redis/redis.conf cd /home/docker/redis/ sed -i 's/# slaveof <maste

详解centos下搭建redis集群

必备的工具: redis-3.0.0.tar redis-3.0.0.gem (ruby和redis接口) 分析: 首先,集群数需要基数,这里搭建一个简单的redis集群(6个redis实例进行集群). 在一台服务器上操作,因此仅需要6个不同的端口号即可.分别是:7001.7002.7003.7004.7005.7006. 步骤: 1.上传redis-3.0.0.tar到服务器(自己指定自己的软件目录),解压redis-3.0.0.tar. 2.安装c语言环境(安装centos之后,自带c语言环

Docker快速搭建Redis集群的方法示例

什么是Redis集群 Redis集群是Redis提供的分布式数据库方案,集群通过分片(sharding)来进行数据共享,并提供复制和故障转移功能. 节点 一个Redis集群通常由多个节点(node)组成,在刚开始的时候,每个节点都是相互独立的,它们都处于一个只包含自己的集群当中,要组建一个真正可工作的集群,我们必须将各个独立的节点连接起来,构成一个包含多个节点的集群. 集群配置 配置文件 下载配置文件:https://raw.githubusercontent.com/antirez/redis

MongoDB学习以及集群搭建的实践全纪录

前言 最近一些变动,有一个老项目交由我们组负责维护,碰到这样的事情我的内心是崩溃的,但还得强颜欢笑,拍着胸脯说没问题.更悲哀的是,该项目中还使用了mongo,还是自己搭建的,没有交由DBA统一管理,无奈,只能赶鸭子上架,自己学习mongo了. 为什么使用集群架构? 主从:故障转移:无法实现,如果主机宕机,需要关闭slave并且按照master模式启动.无法解决单点故障 无法autofailover 不可以自动主从的切换 为了解决主从的问题,MongoDB3.0之后出现副本集,副本集解决了故障转移