int16 / int32 / int64 · 只升不降 · 二分

intset：全整数集合的定宽表示

SADD myset 1 2 3 之后 OBJECT ENCODING myset 报的是 intset，而不是 listpack 或 hashtable。这一条编码专给元素全是整数的集合，它的结构比前一页的 SDS 还简单：

typedef struct intset {
    uint32_t encoding;   /* 每个元素占几字节: 2 / 4 / 8 */
    uint32_t length;     /* 元素个数 */
    int8_t contents[];   /* 升序、无重复、定宽 */
} intset;

头部 8 字节，之后是一片定宽的整数。定宽这一条是整个设计的支点——它让 contents 能按下标寻址，于是「排好序」就能兑换成二分查找。

1 · 定宽带来的两项性质

contents 声明成 int8_t[] 只是为了拿到字节地址，真实宽度由 encoding 决定。取第 $i$ 个元素是一次乘加：((int16_t*)is->contents)[i]，或者 32 / 64 位的对应版本。

第一项性质是内存占用可以精确算出： $8 + \textit{encoding} \times \textit{length}$ 字节。512 个小整数占 1032 字节，每个元素摊到 2.02 字节。同样 512 个整数放进 hashtable 编码，每个元素要一个 dictEntry（三个指针，64 位机上 24 字节）、一个 robj（16 字节）加一个 SDS 头部，还有桶数组的份额，量级差二十倍以上。

第二项性质是有序性可以维护。插入前先二分定位，再把插入点之后的元素整体后移一格。intsetAdd 里对应 intsetResize 加 intsetMoveTail 两步。移动量是 $\textit{length} - \textit{pos}$ 个元素，头插最坏、尾插为零。

排好序的意义不止在查找。SRANDMEMBER、SPOP 之类的操作要随机取元素，定宽数组直接取下标；集合求交则可以对两个 intset 走归并式的双指针扫描。

2 · 只升不降的编码

encoding 有三档，取值就是元素宽度：INTSET_ENC_INT16 为 2、INTSET_ENC_INT32 为 4、INTSET_ENC_INT64 为 8。选哪一档由集合里绝对值最大的那个元素决定，分界处是各宽度的有符号极值：32767 与 32768 之间、2147483647 与 2147483648 之间，负侧对称。

新加的元素超出当前编码的表示范围时，整个集合必须重排到更宽的格子上。intsetUpgradeAndAdd 做三件事：改 encoding 字段、intsetResize 到新的总字节数、然后把已有元素逐个搬到新宽度的位置上。

搬的方向是从尾向头，注释写明了原因：Upgrade back-to-front so we don't overwrite values。原地扩宽时每个元素的新位置都在旧位置之后（第 $i$ 个元素从偏移 $2i$ 挪到 $4i$ 或 $8i$ ），从前往后写会覆盖掉还没读的数据。

图 2-1 · 逐个加入元素时的编码档次、逐元素字节占用与升级时的重排量。可加入跨越 32767 或 2147483647 的值触发升级，并删除它观察编码是否回落。

触发升级的值一定落在两端，intsetAdd 的注释也点了这件事：它超出了现有元素的值域，所以要么是新的最大值、要么是新的最小值。intsetUpgradeAndAdd 用一个 prepend 变量记下往哪一头放，全程不需要二分。

代价在于这条路是单向的。512 个小整数占 1032 字节；加进一个 5000000000 之后，513 个元素全部按 int64 存，占 4112 字节。把这个大整数再删掉，剩下 512 个元素仍是 int64 编码，占 4104 字节，是原来的 3.98 倍。降级需要重新扫一遍全部元素找出新的最大绝对值，Redis 没有做这件事——intsetRemove 只调 intsetMoveTail 与 intsetResize，一行都没碰 encoding。

警示 · 这条单向性会以一种不显眼的方式咬人：一个存放用户 ID 的 set，只要历史上误写过一个超过 32 位的值，此后就算把它删掉，这个 set 的每元素开销也永远是 8 字节。要恢复只能把整个 key 删掉重建。集合数量多的场景下，这笔账值得在写入侧就拦住。

3 · 二分查找与两处短路

intsetSearch 是定宽数组上的标准二分，返回是否命中；未命中时把应插入的位置写进 pos，供 intsetAdd 直接用。

进入循环之前有两处短路。空集直接返回 0；待查值大于末元素则 pos 取 length、小于首元素则 pos 取 0，两种情况都不进二分。这两处短路专为一种常见写法而设：SADD 按递增顺序批量灌入。每个新值都比现有最大值大，于是每一次插入都只做一次比较、零次元素移动。

图 3-1 · 在一个升序 intset 上二分查找，逐步标出探测到的下标与收缩的区间。可改集合规模与待查值，观察两处端点短路何时接管。

落进二分的情况下，探测次数是 $\lceil \log_2 n \rceil$ 量级。把 512 个元素的集合里所有可能的待查值扫一遍，实测最多探测 10 次、平均 8.62 次，与上界 $\lceil \log_2 512 \rceil + 1 = 10$ 完全贴合。

set-max-intset-entries 的出厂值是 512。这个数为何取 512 而不是别的，redis.conf 的注释只说了越界会转成 hashtable，没有给量级依据。按两侧代价推：查找那一头很宽松， $n = 512$ 时二分最多 10 次比较，且这些比较全落在一片 1 KB 出头的连续内存上；真正吃紧的是插入，intsetMoveTail 的搬迁量随 $n$ 线性增长，头插一个值要挪走全部 512 个元素。这段推理是本页的判断，不是文档结论。

4 · 参考文献

Sanfilippo, S. intset.c. redis/src/intset.c（Redis 7.4）：intsetUpgradeAndAdd 与 intsetSearch。
Redis. SADD / OBJECT ENCODING 命令手册与 set-max-intset-entries 配置说明。
Bentley, J. (1986). Programming Pearls (§4 编写正确的程序). Addison-Wesley：二分查找的边界条件。