深入剖析 redis 数据结构 intset
intset 和 dict 都是 sadd 命令的底层数据结构,当添加的所有数据都是整数时,会使用前者;否则使用后者。 特别的 ,当遇到添加数据为字符串,即不能表示为整数时,redis 会把数据结构转换为 dict,即把 intset 中的数据全部搬迁到 dict。 本片展开的是 ints
intset 和 dict 都是 sadd 命令的底层数据结构,当添加的所有数据都是整数时,会使用前者;否则使用后者。特别的,当遇到添加数据为字符串,即不能表示为整数时,redis 会把数据结构转换为 dict,即把 intset 中的数据全部搬迁到 dict。
本片展开的是 intset,dict 的文章可以参看之前写的《深入剖析 redis 数据结构 dict》。
intset 结构体
intset 底层本质是一个有序的、不重复的、整型的数组,支持不同类型整数。
typedef struct intset { // 每个整数的类型 uint32_t encoding; // intset 长度 uint32_t length; // 整数数组 int8_t contents[]; } intset;
encoding 能下面的三个值:分别是 16,32 和 64位整数:
/* Note that these encodings are ordered, so: * INTSET_ENC_INT16 <h3 id="intset-搜索">intset 搜索</h3> <p>intset 是有序的整数数组,可以用二分搜索查找。</p> <pre class="brush:php;toolbar:false">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) { 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 比最大元素还大 if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) { if (pos) *pos = intrev32ifbe(is->length); return 0; // value 比最小元素还小 } else if (value = min) { mid = (min+max)/2; cur = _intsetGet(is,mid); if (value > cur) { min = mid+1; } else if (value <h3 id="intset-插入">intset 插入</h3> <p>intset 实现中比较远有意思的是插入算法部分。</p> <pre class="brush:php;toolbar:false">/* Insert an integer in the intset */ intset *intsetAdd(intset *is, int64_t value, uint8_t *success) { uint8_t valenc = _intsetValueEncoding(value); uint32_t pos; if (success) *success = 1; /* Upgrade encoding if necessary. If we need to upgrade, we know that * this value should be either appended (if > 0) or prepended (if intrev32ifbe(is->encoding)) { /* This always succeeds, so we don't need to curry *success. */ return intsetUpgradeAndAdd(is,value); // 正常,分配内存,插入 } else { // intset 内部不允许重复 /* Abort if the value is already present in the set. * This call will populate "pos" with the right position to insert * the value when it cannot be found. */ if (intsetSearch(is,value,&pos)) { if (success) *success = 0; return is; } // realloc is = intsetResize(is,intrev32ifbe(is->length)+1); // 迁移内存,腾出空间给新的数据。intsetMoveTail() 完成内存迁移工作 if (pos length)) intsetMoveTail(is,pos,pos+1); } // 在腾出的空间中设置新的数据 _intsetSet(is,pos,value); // 更新 intset size is->length = intrev32ifbe(intrev32ifbe(is->length)+1); return is; } // 升级整数类型,譬如从 short->int。当插入数据的内存占用比原有数据大 // 的时候,会被调用 /* 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); // value0 尾插 int prepend = value 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)); // valuelength),value); // 更新 set size is->length = intrev32ifbe(intrev32ifbe(is->length)+1); return is; }
捣乱 2014-7-3
http://daoluan.net
原文地址:深入剖析 redis 数据结构 intset, 感谢原作者分享。

热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

热门话题

Redis集群模式通过分片将Redis实例部署到多个服务器,提高可扩展性和可用性。搭建步骤如下:创建奇数个Redis实例,端口不同;创建3个sentinel实例,监控Redis实例并进行故障转移;配置sentinel配置文件,添加监控Redis实例信息和故障转移设置;配置Redis实例配置文件,启用集群模式并指定集群信息文件路径;创建nodes.conf文件,包含各Redis实例的信息;启动集群,执行create命令创建集群并指定副本数量;登录集群执行CLUSTER INFO命令验证集群状态;使

如何清空 Redis 数据:使用 FLUSHALL 命令清除所有键值。使用 FLUSHDB 命令清除当前选定数据库的键值。使用 SELECT 切换数据库,再使用 FLUSHDB 清除多个数据库。使用 DEL 命令删除特定键。使用 redis-cli 工具清空数据。

使用 Redis 指令需要以下步骤:打开 Redis 客户端。输入指令(动词 键 值)。提供所需参数(因指令而异)。按 Enter 执行指令。Redis 返回响应,指示操作结果(通常为 OK 或 -ERR)。

要从 Redis 读取队列,需要获取队列名称、使用 LPOP 命令读取元素,并处理空队列。具体步骤如下:获取队列名称:以 "queue:" 前缀命名,如 "queue:my-queue"。使用 LPOP 命令:从队列头部弹出元素并返回其值,如 LPOP queue:my-queue。处理空队列:如果队列为空,LPOP 返回 nil,可先检查队列是否存在再读取元素。

使用Redis进行锁操作需要通过SETNX命令获取锁,然后使用EXPIRE命令设置过期时间。具体步骤为:(1) 使用SETNX命令尝试设置一个键值对;(2) 使用EXPIRE命令为锁设置过期时间;(3) 当不再需要锁时,使用DEL命令删除该锁。

Redis 使用哈希表存储数据,支持字符串、列表、哈希表、集合和有序集合等数据结构。Redis 通过快照 (RDB) 和追加只写 (AOF) 机制持久化数据。Redis 使用主从复制来提高数据可用性。Redis 使用单线程事件循环处理连接和命令,保证数据原子性和一致性。Redis 为键设置过期时间,并使用 lazy 删除机制删除过期键。

理解 Redis 源码的最佳方法是逐步进行:熟悉 Redis 基础知识。选择一个特定的模块或功能作为起点。从模块或功能的入口点开始,逐行查看代码。通过函数调用链查看代码。熟悉 Redis 使用的底层数据结构。识别 Redis 使用的算法。

Redis 作为消息中间件,支持生产-消费模型,可持久化消息并保证可靠交付。使用 Redis 作为消息中间件可实现低延迟、可靠和可扩展的消息传递。
