关于「订单去重:过滤器只分流、不拒单,窗口分代与计数删除」,《布隆过滤器与基数估计》给出的定量结论是什么?

结论:第五章规定过滤器只分流、不拒单:查库量减少 0.987,而凭过滤器拒单三十天会拒错 4916 张真实订单;窗口用两代轮换,删除用计数过滤器,普通过滤器清零会让 0.3944 的有效订单读成没见过。

数据口径:示意网络中,各站独立访客相加是真实人数的 2.224 倍。 书中的站点、访客、订单与流量参数均为示意;全部计算由书中程序生成;本书是非个人化经营建议;访客统计只用匿名化、加密钥哈希的标识,不收集个人身份信息,须遵守所在地个人信息保护法规与站点隐私声明,法规只述大意,以上架前人工复核为准。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.987, 4916

keys held n600000; exact set of 64-bit keys = 4687.5 KB
bits/key k filter KB FP rate store lookups/day saved
64 439.5 0.05606 1221.1 0.939
86 585.9 0.02158 531.5 0.974
107 732.4 0.00819 263.9 0.987
128 878.9 0.00314 162.8 0.992
16 111171.9 0.00046 109.2 0.995
if the filter alone rejected orders, at 10 bits/key:
genuine orders refused per day163.9
chance of at least one refusal per day1.000000
refused per 30-day window4916
查看完整验算程序
# Chapter 5. p51: a Bloom filter may route orders, never reject them.
# Illustrative network: 100 sites, 20,000 new orders a day plus 100
# resubmissions (double clicks, client retries); a 30-day dedup window,
# so n = 600,000 order keys are held. Gate: "definitely new" from the
# filter goes straight through; "maybe seen" goes to the exact order
# store. FP rate from the closed form at the best integer k; the exact
# rate is slightly higher (p43), negligible at this size.
import math

NEW, DUP, DAYS = 20000, 100, 30
N = NEW * DAYS


def fp(c):
    k = min(range(1, 40), key=lambda j: (1 - math.exp(-j / c)) ** j)
    return k, (1 - math.exp(-k / c)) ** k


print("keys held n = %d; exact set of 64-bit keys = %.1f KB"
      % (N, N * 8 / 1024))
print("bits/key  k  filter KB   FP rate  store lookups/day  saved")
for c in (6, 8, 10, 12, 16):
    k, p = fp(c)
    look = DUP + p * NEW
    print("%8d %2d %10.1f %9.5f %18.1f %6.3f"
          % (c, k, c * N / 8 / 1024, p, look, 1 - look / (NEW + DUP)))
k, p = fp(10)
print("if the filter alone rejected orders, at 10 bits/key:")
print("  genuine orders refused per day: %.1f" % (p * NEW))
print("  chance of at least one refusal per day: %.6f"
      % (1 - (1 - p) ** NEW))
print("  refused per 30-day window: %.0f" % (p * NEW * DAYS))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《布隆过滤器与超对数对数基数估计、千字节内存统计百站独立访客与去重订单母典》第 5 章「订单去重:过滤器只分流、不拒单,窗口分代与计数删除」(版本 1.0.0). 5D Library. DOI 待发布

DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-294 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026294,
  author    = {Fan, Yafu},
  title     = {Bloom Filters and HyperLogLog Cardinality Estimation: Counting Unique Visitors and Deduplicating Orders across a Hundred Sites in Kilobytes},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

本书其他章节结论