用 showdist.rb 与 showfreq.rb 度量 SRANDMEMBER 的随机公平性：Valkey 集合随机采样工具解析

用 showdist.rb 与 showfreq.rb 度量 SRANDMEMBER 的随机公平性：Valkey 集合随机采样工具解析

【免费下载链接】placeholderkvA flexible distributed key-value database that is optimized for caching and other realtime workloads.项目地址: https://gitcode.com/GitHub_Trending/pl/placeholderkv

utils/srandmember/目录提供了两个 Ruby 脚本，用来统计并可视化SRANDMEMBER命令在不同频率下的返回分布，从而评估其随机抽取的"公平性"（fairness）。本文以 utils/srandmember/README.md 为主体，结合 t_set.c 与 hashtable.c 的底层实现，说明如何运行这两个脚本、如何解读输出，以及从源码层面理解该评估方法所验证的随机抽取策略。

背景：为什么要评估 SRANDMEMBER 的公平性

SRANDMEMBER用于从一个集合中随机返回一个或多个成员，是缓存、抽奖、AB 测试等场景的常用命令。如果一个集合的底层实现（例如哈希表）在遍历或抽样时存在系统性偏向，那么某些元素会被更频繁地返回，另一些则被"冷落"，即随机分布不均匀（unfair）。这种偏差在真实业务中可能表现为：部分缓存键被反复命中、抽样样本失真等。

utils/srandmember/目录的目的正是量化这种公平性：通过海量抽样统计每个元素被返回的次数，观察频率分布是否符合均匀随机模型的预期，从而验证SRANDMEMBER在各类编码（listpack、intset、hashtable）下是否表现公平。

说明：README 中引用的外部调查背景链接（theshfl.com/redis_sets）不在本文范围内，本仓库提供的可验证证据来自 utils/srandmember/ 目录脚本与 src/t_set.c 的实现。

两个工具脚本：用途与输出格式

目录包含两个脚本，对应两种互补的统计视角：

两者共享相同的实验方法：向 Redis/Valkey 写入 1000 个元素（整数 0~999），然后以 pipeline 方式批量执行SRANDMEMBER，最后统计频次。

运行方法

前置条件

• 本地运行中的 Redis 或 Valkey 服务（默认localhost:6379，可通过REDIS_URL等环境变量或修改脚本中的Redis.new参数指定连接）。
• Ruby 环境与redisgem（gem install redis）。

运行 showdist.rb

ruby utils/srandmember/showdist.rb

脚本逻辑（见 showdist.rb）：

1. 连接 Redis，select(9)切换到第 9 号数据库，del("myset")清空残留数据；
2. sadd("myset", (0..999).to_a)写入 1000 个整数元素；
3. 外层循环100 次，每次用 pipeline 连续发送1000 次srandmember("myset")，即总共执行10 万次随机抽取；
4. 统计每个元素被返回的总次数freq[ele]；
5. 再聚合为"次数 → 元素个数"的分布dist[count]；
6. 从最小次数到最大次数逐行输出次数 -> 星号数量的 ASCII 直方图。

运行 showfreq.rb

ruby utils/srandmember/showfreq.rb

逻辑与 showdist.rb 几乎一致，区别在于：

• 外层循环为500 次，同样每次 pipeline 1000 次抽取，即总共50 万次抽样，统计精度更高；
• 输出不画柱状图，而是逐元素打印元素编号 被返回次数两列数据（见 showfreq.rb），便于重定向到文件后用 gnuplot 绘图：

ruby utils/srandmember/showfreq.rb > freq.dat gnuplot -e "plot 'freq.dat' with points"

如何解读输出：公平性的判读

showdist.rb 的分布形态

在完全公平的随机模型下，每个元素被抽中的概率相等。若总抽样次数为 N、集合大小为 S，则每个元素的期望被返回次数约为N / S，实际观察值围绕该期望值呈近似泊松/正态分布。因此：

• 公平（fair）：柱状图呈现以期望次数为中心的单峰对称山丘，绝大多数元素的被返回次数集中在期望值附近，两侧对称衰减；
• 有偏（unfair）：柱状图出现明显的长尾或多峰，意味着部分元素被过度抽取、部分元素被冷落，即随机性存在系统性偏差。

以 10 万次抽样、1000 个元素为例，期望次数约为 100 次，公平实现应看到大部分星号集中在 100 附近。

showfreq.rb 的点图

500 次循环 × 1000 次 pipeline 共 50 万次抽样后，每个元素期望被返回约 500 次。将元素编号 vs 被返回次数绘成点图后，公平实现应呈现围绕 500 的窄带均匀散点，而非上下大幅波动的锯齿。该脚本以机器可读格式输出，正是为了方便使用 gnuplot 等工具做精细分析。

源码纵深：SRANDMEMBER 如何实现随机抽取

理解评估目标后，再回到实现层验证脚本到底在测什么。SRANDMEMBER的入口是srandmemberCommand（src/t_set.c），不带 count 参数时直接调用setTypeRandomElement返回单个元素；带 count 参数时转入srandmemberWithCountCommand（src/t_set.c）。

不同编码的随机抽取路径

setTypeRandomElement（src/t_set.c）按集合的底层编码分三种路径：

• OBJ_ENCODING_HASHTABLE：调用hashtableFairRandomEntry（src/hashtable.c）抽取——这是公平性评估的核心关注点，见下文；
• OBJ_ENCODING_INTSET：调用intsetRandom按整数集合元素数取模随机；
• OBJ_ENCODING_LISTPACK：rand() % lpLength(lp)后lpSeek定位到随机下标。

带 count 参数的四种策略

SRANDMEMBER key count的实现（src/t_set.c）根据 count 符号、集合大小与编码动态选择策略：

1. CASE 1（负 count 或 count=1）：允许重复的随机抽样（负 count 表示可重复返回同一元素），每次独立调用setTypeRandomElement，需要按随机顺序返回；
2. CASE 2（count ≥ size）：直接返回整个集合；
3. CASE 3（count × 3 > size，SRANDMEMBER_SUB_STRATEGY_MUL）：把全部元素复制进临时哈希表后，用hashtableFairRandomEntry反复抽取并删除，直到剩下 count 个；
4. CASE 4（其余情况）：反复随机抽样并去重，直到凑齐 count 个唯一元素。

hashtable 的"公平随机"设计

哈希表实现中定义了两种采样常量（src/hashtable.c）：

#define FAIR_RANDOM_SAMPLE_SIZE (ENTRIES_PER_BUCKET * 10) #define WEAK_RANDOM_SAMPLE_SIZE ENTRIES_PER_BUCKET

hashtableRandomEntry（src/hashtable.c）采用"弱随机"策略：随机选桶并沿桶链采样WEAK_RANDOM_SAMPLE_SIZE个条目后随机取一。这种策略简单高效，但链越长，长链上的元素被抽中的概率越大，可能引入偏差。

hashtableFairRandomEntry（src/hashtable.c）则在哈希表较满（元素数 ≥ 桶数）时加大采样规模至FAIR_RANDOM_SAMPLE_SIZE，降低长链造成的偏差，从而"更公平"（more fair）；在极端稀疏场景下才退回弱采样以控制开销。也就是说，本仓库实现特意区分了"弱随机"与"公平随机"两条路径，SRANDMEMBER走的是公平路径——这正是 utils/srandmember/ 脚本能够验证的目标：确认setTypeRandomElement→hashtableFairRandomEntry这条调用链在长期抽样下不表现出系统性偏向。

用测试佐证脚本的统计对象

src/t_set.c 的单元测试覆盖了与脚本相同的统计视角（tests/unit/type/set.tcl），例如：

• r srandmember myset 0返回空数组、count越界报错等边界行为；
• 对随机元素做集合归属断言：set myset([r srandmember myset]) 1（tests/unit/type/set.tcl）；
• 大规模抽样验证：对指定size的集合执行srandmember myset $size并校验去重数量（tests/unit/type/set.tcl），确认 CASE 2/3/4 的结果总是 count 个唯一元素。

这些测试与utils/srandmember/脚本互补：测试保证正确性（返回的元素属于集合、数量正确），脚本保证统计质量（分布均匀、无系统性偏差）。

在项目中使用这套工具

1. 确保 Redis/Valkey 已启动，按需修改 showdist.rb 或 showfreq.rb 中的连接参数（如Redis.new(host: ..., port: ...)）与数据库编号；
2. 运行 showdist.rb 观察 ASCII 直方图是否呈单峰对称；
3. 运行 showfreq.rb 并重定向输出，用 gnuplot 绘制频次散点图做定量分析；
4. 若分布出现显著偏斜，可结合 src/t_set.c 的编码分支与 src/hashtable.c 的采样策略排查是哪种编码或采样路径引入偏差。

小结

• utils/srandmember/README.md 定义的评估方法：用 10 万~50 万次抽样统计元素返回频次，通过 showdist.rb 的分布形态与 showfreq.rb 的逐元素频次判定SRANDMEMBER是否公平；
• 源码证据表明随机抽取最终收敛到hashtableFairRandomEntry的公平采样路径（src/hashtable.c），并针对哈希表稀疏/稠密状态自适应调整采样规模；
• 该工具目录是验证"随机命令统计公平性"的轻量方案：无需改代码，仅凭两个 Ruby 脚本即可对任意编码的集合做长期抽样体检。

【免费下载链接】placeholderkvA flexible distributed key-value database that is optimized for caching and other realtime workloads.项目地址: https://gitcode.com/GitHub_Trending/pl/placeholderkv