尧图网站建设 
Beads 哈希 ID 碰撞数学解析生日悖论公式、自适应长度缩放与碰撞兜底策略【免费下载链接】beadsBeads - A memory upgrade for your coding agent项目地址: https://gitcode.com/GitHub_Trending/beads1/beads本篇技术指南深入剖析 Beads 项目一个为编码 Agent 提供记忆增强的 issue 追踪工具中自适应哈希 ID 的碰撞概率数学原理。文章以仓库内 engdocs/COLLISION_MATH.md 为核心骨架结合internal/storage/domain/adaptive.go、internal/storage/issueops/helpers.go与internal/idgen/hash.go等源码实现完整讲解生日悖论公式、碰撞概率对照表、自适应长度缩放阈值max_collision_prob以及 30 次 nonce 兜底重试机制。读完本文你将掌握 Beads 如何在“短 ID 可读性”与“大规模防碰撞”之间动态权衡并能独立复算碰撞概率、按需定制缩放策略。为什么 Beads 需要碰撞数学Beads 使用基于 SHA-256 的哈希 ID 作为 issue 的稳定标识例如myproject-a3f2。与顺序计数器 ID 不同哈希 ID 天然支持多分支、多 Agent 并行创建而不发生序号分歧但代价是存在碰撞两个不同 issue 生成相同 ID的可能性。碰撞数学要回答三个问题给定数据库规模n与 ID 长度L碰撞概率是多少数据库增长到什么规模时必须加长 ID真发生碰撞时系统如何兜底生日悖论公式Beads 计算碰撞概率采用标准的生日悖论近似公式P(collision) ≈ 1 - e^(-n²/2N)其中n 数据库中 issue 的数量N 可能的 ID 总数 36^length小写字母数字字符集[a-z0-9]。该近似成立的前提是哈希输出在[a-z0-9]空间上近似均匀分布且样本量远小于空间大小。Beads 源码 internal/storage/domain/adaptive.go 中的ComputeAdaptiveLength正是这一公式的逐字实现func ComputeAdaptiveLength(numIssues int, cfg AdaptiveIDConfig) int { const base 36.0 for length : cfg.MinLength; length cfg.MaxLength; length { totalPossibilities : math.Pow(base, float64(length)) exponent : -float64(numIssues*numIssues) / (2.0 * totalPossibilities) prob : 1.0 - math.Exp(exponent) if prob cfg.MaxCollisionProbability { return length } } return cfg.MaxLength }从源码结构看该算法采用“从最小长度向上扫描”的策略从MinLength开始逐个长度计算碰撞概率找到第一个满足prob MaxCollisionProbability的长度即返回若扫描到MaxLength仍不满足则退回MaxLength即最大长度是安全上限宁可用更长 ID 也不放弃写入。碰撞概率对照表下表是原文档给出的完整碰撞概率数据行 数据库规模列 ID 字符长度DB Size4-char5-char6-char7-char8-char500.07%0.00%0.00%0.00%0.00%1000.30%0.01%0.00%0.00%0.00%2001.18%0.03%0.00%0.00%0.00%5007.17%0.21%0.01%0.00%0.00%1,00025.75%0.82%0.02%0.00%0.00%2,00069.60%3.25%0.09%0.00%0.00%5,00099.94%18.68%0.57%0.02%0.00%10,000100%56.26%2.27%0.06%0.00%关键结论4 字符 ID约 500 个 issue 以内安全碰撞风险 7%。5 字符 ID约 1,500 个 issue 以内安全碰撞风险 2%。6 字符 ID约 10,000 个 issue 以内安全碰撞风险 2%。7 字符 ID可支撑 100,000 issue碰撞风险可忽略。8 字符 ID可支撑数百万级 issue。注意表中 4-char 列在 10,000 规模时显示 100%这是四舍五入结果——真实概率为 99.99999%几乎必然发生碰撞因此 4 字符绝不适合大规模库。期望碰撞次数概率本身还不足以说明“实际撞几次”。期望碰撞次数用公式n²/(2N)近似原文档给出DB Size4-char5-char6-char7-char8-char1000.000.000.000.000.005000.070.000.000.000.001,0000.300.010.000.000.002,0001.190.030.000.000.005,0007.440.210.010.000.0010,00029.770.830.020.000.00示例5,000 个 issue 使用 4 字符 ID 时平均会遇到约 7 次哈希碰撞Beads 会自动以“1 nonce”重试生成。这一区分很关键碰撞概率衡量的是“这批 ID 里至少撞一次”的可能性而碰撞次数衡量实际发生的平均碰撞数。Beads 的阈值策略基于前者做长度决策而碰撞兜底逻辑处理后者。自适应长度缩放策略Beads 在 issue 创建时先统计当前库中该前缀下的 issue 数量再据此动态选择 ID 长度。当碰撞概率超过25%默认值可用max_collision_prob配置时自动增加 ID 长度。默认阈值25% 最大碰撞概率Database SizeID LengthCollision Probability at Max0-5004 chars7.17% at 500 issues501-1,5005 chars1.84% at 1,500 issues1,501-5,0005 chars18.68% at 5,000 issues5,001-15,0006 chars5.04% at 15,000 issues15,001继续按需缩放补充说明上表基于“碰撞概率不得超过 25%”的约束逐档推算。例如 4 字符在 500 个 issue 时概率仅 7.17%远低于 25%因此 0-500 区间都保持 4 字符而 5 字符在 1,500 个 issue 时概率约 1.84%直到 5,000 个 issue 才升到 18.68%——仍低于 25%故 501-5,000 区间继续用 5 字符随后才切换到 6 字符。为什么选 25%25% 阈值在三个目标间取得平衡可读性Readability小数据库保持短 ID如bd-a3f2便于口头交流与输入安全性Safety避免频繁触发碰撞重试减少写入路径的额外查询可扩展性Scalability数据库扩张时优雅加长无需人工干预。原文档特别强调即使碰撞概率高达 25%实际碰撞的期望次数依然很低每创建 1,000 个 issue 平均不到 1 次。这是因为 25% 概率对应“这批 ID 至少撞一次”的整体可能性分摊到单次创建上仍然稀有。替代阈值你可以用bd config set max_collision_prob value自定义阈值# 更保守最多允许 10% 碰撞概率 bd config set max_collision_prob 0.10 # 默认25% bd config set max_collision_prob 0.25 # 更激进允许 50% bd config set max_collision_prob 0.50保守10% 阈值DB SizeID Length0-2004 chars201-1,0005 chars1,001-5,0006 chars5,001继续缩放激进50% 阈值DB SizeID Length0-5004 chars501-2,0005 chars2,001-10,0006 chars10,001继续缩放从配置读取的实现位于 internal/storage/domain/db/config.go 的GetAdaptiveIDConfig依次读取max_collision_prob、min_hash_length、max_hash_length三个配置键任一解析失败如格式非法则静默回退到默认值同套逻辑在事务版本GetAdaptiveConfigTxinternal/storage/issueops/helpers.go中复现。相关测试见 internal/storage/domain/db/config_test.go覆盖“缺省键返回默认值”“覆盖生效”“非法值回退默认”三类场景。长度边界配置除碰撞概率外还可约束 ID 长度的上下限默认下限为 3上限为 8文档型指引通常建议 4 起步见 docs/core-concepts/adaptive-ids.md# 强制最短 5 字符保证所有 ID 长度一致 bd config set min_hash_length 5 # 允许更长的 ID支撑超大规模库 bd config set max_hash_length 10对应的默认常量可在 internal/storage/domain/adaptive.go 的DefaultAdaptiveConfig中确认MaxCollisionProbability: 0.25、MinLength: 3、MaxLength: 8。碰撞兜底解析当哈希 ID 真的发生碰撞时Beads 的生成器 GenerateIssueIDInTable 执行“长度 × nonce”两级重试以基准长度尝试不同 nonce10 次换基准长度 1 再试 10 次换基准长度 2 再试 10 次。共 30 次尝试全部失败才报错天文数字级别的小概率事件。以 4 字符基准长度为例bd-a3f2nonce 0——碰撞bd-a3f2nonce 1——再次碰撞bd-b7d4nonce 2——成功✓源码中每轮尝试都执行SELECT COUNT(*) FROM table WHERE id ?检查候选 ID 是否已存在命中则换下一个 nonce。nonce 被混入哈希输入见下文 ID 生成实现因此不同 nonce 产生完全不同的哈希值。ID 空间与数学性质ID 空间大小LengthPossible IDsNotation3 chars46,65636³4 chars1,679,61636⁴ ≈ 1.7M5 chars60,466,17636⁵ ≈ 60M6 chars2,176,782,33636⁶ ≈ 2.2B7 chars78,364,164,09636⁷ ≈ 78B8 chars2,821,109,907,45636⁸ ≈ 2.8T为什么用小写字母数字而非十六进制采用[a-z0-9]36 字符而非 hex16 字符的核心收益信息密度高4 字符字母数字 ≈ 6 字符十六进制的容量36⁴ ≈ 1.68M而 16⁶ ≈ 16.8M同一量级更可读bd-a3f2明显比bd-a3f2e1更短更顺眼更易输入与沟通短 ID 适合口头传达与命令粘贴。底层哈希编码实现在 internal/idgen/hash.goEncodeBase36把 SHA-256 摘要的截断字节转为 big.Int 后按 36 进制编码不足位用0左填充超出则截断保留低位。ID 生成函数 GenerateHashID 的输入为title|description|creator|timestamp|nonce拼接串SHA-256 后按目标长度截取字节4-char 取 3 字节 ≈ 24 位恰好略大于 36⁴保证 4 字符空间被完整覆盖最终输出prefix-shorthash格式。验证自行复算碰撞表原文档提供碰撞计算器用于验证上述表格go run scripts/collision-calculator.go输出包含不同数据库规模与 ID 长度下的碰撞概率、期望碰撞次数、推荐 ID 长度以及任意阈值下的自适应缩放策略。该脚本路径在当前仓库快照中未随包发布表格数据亦可直接用上文公式与源码逻辑自行复算核对。实现位置速查自适应长度算法域层internal/storage/domain/adaptive.go自适应长度算法事务层internal/storage/issueops/helpers.go哈希 ID 生成与 base36 编码internal/idgen/hash.go配置读取max_collision_prob/min_hash_length/max_hash_lengthinternal/storage/domain/db/config.go配置存储结构config表键值对形式例如INSERT INTO config (key, value) VALUES (max_collision_prob, 0.25)功能配置与使用指南docs/core-concepts/adaptive-ids.md全部配置项说明docs/reference/configuration.md最佳实践默认值即优25% 阈值在绝大多数场景下表现良好无需调整。主动归档定期删除/归档已关闭 issue保持库规模小ID 自然维持更短。一致性优先若希望所有 ID 等长设置min_hash_length。健康巡检周期性运行碰撞计算器观察库规模与当前长度档位是否接近阈值边界。理解迁移语义存量库默认沿用既有长度新 ID 才按自适应规则生成旧 ID 不受影响可参考 docs/core-concepts/adaptive-ids.md 的迁移章节。小结Beads 的自适应哈希 ID 是“概率论 工程兜底”的组合设计生日悖论公式决定何时加长 ID默认 25% 阈值30 次 nonce 重试兜底极端碰撞base36 编码兼顾信息密度与可读性。理解这套碰撞数学能帮你正确评估大规模场景下的 ID 安全边界并为自己的系统设计类比的短 ID 策略提供可复用的计算框架。【免费下载链接】beadsBeads - A memory upgrade for your coding agent项目地址: https://gitcode.com/GitHub_Trending/beads1/beads创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Beads 哈希 ID 碰撞数学解析：生日悖论公式、自适应长度缩放与碰撞兜底策略
Beads 哈希 ID 碰撞数学解析生日悖论公式、自适应长度缩放与碰撞兜底策略【免费下载链接】beadsBeads - A memory upgrade for your coding agent项目地址: https://gitcode.com/GitHub_Trending/beads1/beads本篇技术指南深入剖析 Beads 项目一个为编码 Agent 提供记忆增强的 issue 追踪工具中自适应哈希 ID 的碰撞概率数学原理。文章以仓库内 engdocs/COLLISION_MATH.md 为核心骨架结合internal/storage/domain/adaptive.go、internal/storage/issueops/helpers.go与internal/idgen/hash.go等源码实现完整讲解生日悖论公式、碰撞概率对照表、自适应长度缩放阈值max_collision_prob以及 30 次 nonce 兜底重试机制。读完本文你将掌握 Beads 如何在“短 ID 可读性”与“大规模防碰撞”之间动态权衡并能独立复算碰撞概率、按需定制缩放策略。为什么 Beads 需要碰撞数学Beads 使用基于 SHA-256 的哈希 ID 作为 issue 的稳定标识例如myproject-a3f2。与顺序计数器 ID 不同哈希 ID 天然支持多分支、多 Agent 并行创建而不发生序号分歧但代价是存在碰撞两个不同 issue 生成相同 ID的可能性。碰撞数学要回答三个问题给定数据库规模n与 ID 长度L碰撞概率是多少数据库增长到什么规模时必须加长 ID真发生碰撞时系统如何兜底生日悖论公式Beads 计算碰撞概率采用标准的生日悖论近似公式P(collision) ≈ 1 - e^(-n²/2N)其中n 数据库中 issue 的数量N 可能的 ID 总数 36^length小写字母数字字符集[a-z0-9]。该近似成立的前提是哈希输出在[a-z0-9]空间上近似均匀分布且样本量远小于空间大小。Beads 源码 internal/storage/domain/adaptive.go 中的ComputeAdaptiveLength正是这一公式的逐字实现func ComputeAdaptiveLength(numIssues int, cfg AdaptiveIDConfig) int { const base 36.0 for length : cfg.MinLength; length cfg.MaxLength; length { totalPossibilities : math.Pow(base, float64(length)) exponent : -float64(numIssues*numIssues) / (2.0 * totalPossibilities) prob : 1.0 - math.Exp(exponent) if prob cfg.MaxCollisionProbability { return length } } return cfg.MaxLength }从源码结构看该算法采用“从最小长度向上扫描”的策略从MinLength开始逐个长度计算碰撞概率找到第一个满足prob MaxCollisionProbability的长度即返回若扫描到MaxLength仍不满足则退回MaxLength即最大长度是安全上限宁可用更长 ID 也不放弃写入。碰撞概率对照表下表是原文档给出的完整碰撞概率数据行 数据库规模列 ID 字符长度DB Size4-char5-char6-char7-char8-char500.07%0.00%0.00%0.00%0.00%1000.30%0.01%0.00%0.00%0.00%2001.18%0.03%0.00%0.00%0.00%5007.17%0.21%0.01%0.00%0.00%1,00025.75%0.82%0.02%0.00%0.00%2,00069.60%3.25%0.09%0.00%0.00%5,00099.94%18.68%0.57%0.02%0.00%10,000100%56.26%2.27%0.06%0.00%关键结论4 字符 ID约 500 个 issue 以内安全碰撞风险 7%。5 字符 ID约 1,500 个 issue 以内安全碰撞风险 2%。6 字符 ID约 10,000 个 issue 以内安全碰撞风险 2%。7 字符 ID可支撑 100,000 issue碰撞风险可忽略。8 字符 ID可支撑数百万级 issue。注意表中 4-char 列在 10,000 规模时显示 100%这是四舍五入结果——真实概率为 99.99999%几乎必然发生碰撞因此 4 字符绝不适合大规模库。期望碰撞次数概率本身还不足以说明“实际撞几次”。期望碰撞次数用公式n²/(2N)近似原文档给出DB Size4-char5-char6-char7-char8-char1000.000.000.000.000.005000.070.000.000.000.001,0000.300.010.000.000.002,0001.190.030.000.000.005,0007.440.210.010.000.0010,00029.770.830.020.000.00示例5,000 个 issue 使用 4 字符 ID 时平均会遇到约 7 次哈希碰撞Beads 会自动以“1 nonce”重试生成。这一区分很关键碰撞概率衡量的是“这批 ID 里至少撞一次”的可能性而碰撞次数衡量实际发生的平均碰撞数。Beads 的阈值策略基于前者做长度决策而碰撞兜底逻辑处理后者。自适应长度缩放策略Beads 在 issue 创建时先统计当前库中该前缀下的 issue 数量再据此动态选择 ID 长度。当碰撞概率超过25%默认值可用max_collision_prob配置时自动增加 ID 长度。默认阈值25% 最大碰撞概率Database SizeID LengthCollision Probability at Max0-5004 chars7.17% at 500 issues501-1,5005 chars1.84% at 1,500 issues1,501-5,0005 chars18.68% at 5,000 issues5,001-15,0006 chars5.04% at 15,000 issues15,001继续按需缩放补充说明上表基于“碰撞概率不得超过 25%”的约束逐档推算。例如 4 字符在 500 个 issue 时概率仅 7.17%远低于 25%因此 0-500 区间都保持 4 字符而 5 字符在 1,500 个 issue 时概率约 1.84%直到 5,000 个 issue 才升到 18.68%——仍低于 25%故 501-5,000 区间继续用 5 字符随后才切换到 6 字符。为什么选 25%25% 阈值在三个目标间取得平衡可读性Readability小数据库保持短 ID如bd-a3f2便于口头交流与输入安全性Safety避免频繁触发碰撞重试减少写入路径的额外查询可扩展性Scalability数据库扩张时优雅加长无需人工干预。原文档特别强调即使碰撞概率高达 25%实际碰撞的期望次数依然很低每创建 1,000 个 issue 平均不到 1 次。这是因为 25% 概率对应“这批 ID 至少撞一次”的整体可能性分摊到单次创建上仍然稀有。替代阈值你可以用bd config set max_collision_prob value自定义阈值# 更保守最多允许 10% 碰撞概率 bd config set max_collision_prob 0.10 # 默认25% bd config set max_collision_prob 0.25 # 更激进允许 50% bd config set max_collision_prob 0.50保守10% 阈值DB SizeID Length0-2004 chars201-1,0005 chars1,001-5,0006 chars5,001继续缩放激进50% 阈值DB SizeID Length0-5004 chars501-2,0005 chars2,001-10,0006 chars10,001继续缩放从配置读取的实现位于 internal/storage/domain/db/config.go 的GetAdaptiveIDConfig依次读取max_collision_prob、min_hash_length、max_hash_length三个配置键任一解析失败如格式非法则静默回退到默认值同套逻辑在事务版本GetAdaptiveConfigTxinternal/storage/issueops/helpers.go中复现。相关测试见 internal/storage/domain/db/config_test.go覆盖“缺省键返回默认值”“覆盖生效”“非法值回退默认”三类场景。长度边界配置除碰撞概率外还可约束 ID 长度的上下限默认下限为 3上限为 8文档型指引通常建议 4 起步见 docs/core-concepts/adaptive-ids.md# 强制最短 5 字符保证所有 ID 长度一致 bd config set min_hash_length 5 # 允许更长的 ID支撑超大规模库 bd config set max_hash_length 10对应的默认常量可在 internal/storage/domain/adaptive.go 的DefaultAdaptiveConfig中确认MaxCollisionProbability: 0.25、MinLength: 3、MaxLength: 8。碰撞兜底解析当哈希 ID 真的发生碰撞时Beads 的生成器 GenerateIssueIDInTable 执行“长度 × nonce”两级重试以基准长度尝试不同 nonce10 次换基准长度 1 再试 10 次换基准长度 2 再试 10 次。共 30 次尝试全部失败才报错天文数字级别的小概率事件。以 4 字符基准长度为例bd-a3f2nonce 0——碰撞bd-a3f2nonce 1——再次碰撞bd-b7d4nonce 2——成功✓源码中每轮尝试都执行SELECT COUNT(*) FROM table WHERE id ?检查候选 ID 是否已存在命中则换下一个 nonce。nonce 被混入哈希输入见下文 ID 生成实现因此不同 nonce 产生完全不同的哈希值。ID 空间与数学性质ID 空间大小LengthPossible IDsNotation3 chars46,65636³4 chars1,679,61636⁴ ≈ 1.7M5 chars60,466,17636⁵ ≈ 60M6 chars2,176,782,33636⁶ ≈ 2.2B7 chars78,364,164,09636⁷ ≈ 78B8 chars2,821,109,907,45636⁸ ≈ 2.8T为什么用小写字母数字而非十六进制采用[a-z0-9]36 字符而非 hex16 字符的核心收益信息密度高4 字符字母数字 ≈ 6 字符十六进制的容量36⁴ ≈ 1.68M而 16⁶ ≈ 16.8M同一量级更可读bd-a3f2明显比bd-a3f2e1更短更顺眼更易输入与沟通短 ID 适合口头传达与命令粘贴。底层哈希编码实现在 internal/idgen/hash.goEncodeBase36把 SHA-256 摘要的截断字节转为 big.Int 后按 36 进制编码不足位用0左填充超出则截断保留低位。ID 生成函数 GenerateHashID 的输入为title|description|creator|timestamp|nonce拼接串SHA-256 后按目标长度截取字节4-char 取 3 字节 ≈ 24 位恰好略大于 36⁴保证 4 字符空间被完整覆盖最终输出prefix-shorthash格式。验证自行复算碰撞表原文档提供碰撞计算器用于验证上述表格go run scripts/collision-calculator.go输出包含不同数据库规模与 ID 长度下的碰撞概率、期望碰撞次数、推荐 ID 长度以及任意阈值下的自适应缩放策略。该脚本路径在当前仓库快照中未随包发布表格数据亦可直接用上文公式与源码逻辑自行复算核对。实现位置速查自适应长度算法域层internal/storage/domain/adaptive.go自适应长度算法事务层internal/storage/issueops/helpers.go哈希 ID 生成与 base36 编码internal/idgen/hash.go配置读取max_collision_prob/min_hash_length/max_hash_lengthinternal/storage/domain/db/config.go配置存储结构config表键值对形式例如INSERT INTO config (key, value) VALUES (max_collision_prob, 0.25)功能配置与使用指南docs/core-concepts/adaptive-ids.md全部配置项说明docs/reference/configuration.md最佳实践默认值即优25% 阈值在绝大多数场景下表现良好无需调整。主动归档定期删除/归档已关闭 issue保持库规模小ID 自然维持更短。一致性优先若希望所有 ID 等长设置min_hash_length。健康巡检周期性运行碰撞计算器观察库规模与当前长度档位是否接近阈值边界。理解迁移语义存量库默认沿用既有长度新 ID 才按自适应规则生成旧 ID 不受影响可参考 docs/core-concepts/adaptive-ids.md 的迁移章节。小结Beads 的自适应哈希 ID 是“概率论 工程兜底”的组合设计生日悖论公式决定何时加长 ID默认 25% 阈值30 次 nonce 重试兜底极端碰撞base36 编码兼顾信息密度与可读性。理解这套碰撞数学能帮你正确评估大规模场景下的 ID 安全边界并为自己的系统设计类比的短 ID 策略提供可复用的计算框架。【免费下载链接】beadsBeads - A memory upgrade for your coding agent项目地址: https://gitcode.com/GitHub_Trending/beads1/beads创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考