`nx_segbloom.nx` source

↩ module page · 225 lines · 10071 B
1// nx_segbloom.nx -- EVIDENCE FIRST: does a per-segment TERM BLOOM actually skip enough segments to
2// be worth wiring into the hot search path? MEASURES ONLY. It writes nothing, changes no live code
3// and touches no existing call site -- because the honest order is prove-the-win, then wire it.
4//
5// THE DEFECT IT TARGETS (measured 2026-08-06): /api/search costs a FIXED ~6.6s even for a query that
6// matches ZERO documents, against a 42ms control on the same daemon. ss_term (nx_seg_store:2441)
7// walks EVERY live segment and calls ss_terms_find on that segment's mmap'd terms block:
8//     while s < ns { let tb = h[5+8*s]; ss_terms_find(tb, h[6+8*s], term, outs) ... }
9// The blocks are already mapped, so the cost is ONE PAGE FAULT PER SEGMENT -- ~896 segments x ~8ms.
10// A resident bloom per segment answers "definitely not here" without touching the mapping at all,
11// so the fault never happens. Segments are IMMUTABLE in an append-only store, which is what makes
12// this sound: a per-segment term bloom is computed once and can never go stale.
13//
14// REUSE, NOT REINVENTION: the bloom is nx_sketch_bloom (v2, murmur3 + Kirsch-Mitzenmacher double
15// hashing, already used in production by nx_ingest_runner) and the bits/item + k constants are the
16// pre-computed FPR breakpoints from nx_bloom_capacity. Nothing here is a new filter.
17//
18//   nx_segbloom stat  <domain> [maxsegs]
19//   nx_segbloom probe <domain> <profile 1=10pct|2=1pct> <term> [maxsegs]
20// license_tier: ORIGINAL   No hw writes (Rule 26).   expect_exit: 0
21import "nx_seg_store.nx"
22import "nx_sketch_bloom.nx"
23import "nx_syscalls.nx"
24
25const SB_PATHCAP: i64 = 512
26const SB_SMALL: i64 = 64
27const SB_MAXSEGS: i64 = 8192
28// FPR breakpoints lifted from nx_bloom_capacity (bits-per-item Q10 -> whole bits, and k).
29const SB_BITS_10PCT: i64 = 5
30const SB_K_10PCT: i64 = 3
31const SB_BITS_1PCT: i64 = 10
32const SB_K_1PCT: i64 = 7
33
34func sb_slen(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } return n }
35func sb_w(s: *u8, n: i64) -> i64 { sys_write(1, s, n); return 0 }
36func sb_puts(s: *u8) -> i64 { sb_w(s, sb_slen(s)); return 0 }
37func sb_num(v: i64) -> i64 {
  let t: *u8 = sys_mmap(SB_SMALL)
  var m: i64 = v
  if m < 0 { sb_puts("-" as *u8); m = 0 - m }
  var k: i64 = 0
  if m == 0 { t[0] = 48 as u8; k = 1 }
  while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 }
  let o: *u8 = sys_mmap(SB_SMALL)
  var i: i64 = 0
  while i < k { o[i] = t[k - 1 - i]; i = i + 1 }
  sb_w(o, k)
  return 0
49}
50func sb_cat(d: *u8, o: i64, s: *u8) -> i64 { var i: i64 = 0; while s[i] != (0 as u8) { d[o+i] = s[i]; i = i + 1 } return o + i }
51// prefix is built here rather than imported from the docportal module so this stays a leaf on
52// nx_seg_store alone -- the same reasoning nx_docportal_search_seg gives for inlining dp_prefix.
53func sb_prefix(domain: *u8, out: *u8) -> i64 {
  var o: i64 = 0
  o = sb_cat(out, o, "knowledge/store/dp-" as *u8)
  o = sb_cat(out, o, domain)
  o = sb_cat(out, o, "-pub-" as *u8)
  out[o] = 0 as u8
  return o
60}
61func sb_next_pow2(n: i64) -> i64 {
  var p: i64 = 64
  while p < n { p = p * 2 }
  return p
65}
66func sb_open(domain: *u8) -> *i64 {
  let prefix: *u8 = sys_mmap(SB_PATHCAP)
  sb_prefix(domain, prefix)
  sb_puts("=== nx_segbloom " as *u8); sb_puts(prefix); sb_puts(" ===\n" as *u8)
  // usemmap=1: identical open mode to the live docportal serve path, so the measurement is of the
  // production shape and not of a mode nothing actually runs.
  return ss_open2(prefix, 1)
73}
74func cmd_stat(domain: *u8, maxsegs: i64) -> i64 {
  let h: *i64 = sb_open(domain)
  if (h as i64) == 0 { sb_puts("REFUSED: shard absent or empty\n" as *u8); return 1 }
  var ns: i64 = h[0]
  sb_puts("  segments=" as *u8); sb_num(ns); sb_puts("\n" as *u8)
  if maxsegs > 0 { if ns > maxsegs { ns = maxsegs; sb_puts("  (capped to " as *u8); sb_num(ns); sb_puts(" segments for this run)\n" as *u8) } }
  var tot: i64 = 0
  var mn: i64 = 0 - 1
  var mx: i64 = 0
  var empty: i64 = 0
  var s: i64 = 0
  while s < ns {
      let c: i64 = ss_term_count(h, s)
      tot = tot + c
      if c == 0 { empty = empty + 1 }
      if mn < 0 { mn = c } else { if c < mn { mn = c } }
      if c > mx { mx = c }
      s = s + 1
  }
  sb_puts("  terms: total=" as *u8); sb_num(tot)
  sb_puts(" min=" as *u8); sb_num(mn)
  sb_puts(" max=" as *u8); sb_num(mx)
  if ns > 0 { sb_puts(" avg=" as *u8); sb_num(tot / ns) }
  sb_puts(" empty_segs=" as *u8); sb_num(empty); sb_puts("\n" as *u8)
  // projected resident cost -- the number that decides whether this is wirable at all
  sb_puts("  projected bloom bytes: 10pct=" as *u8); sb_num((tot * SB_BITS_10PCT) / 8)
  sb_puts("  1pct=" as *u8); sb_num((tot * SB_BITS_1PCT) / 8); sb_puts("\n" as *u8)
  return 0
102}
103func cmd_probe(domain: *u8, profile: i64, term: *u8, maxsegs: i64) -> i64 {
  let h: *i64 = sb_open(domain)
  if (h as i64) == 0 { sb_puts("REFUSED: shard absent or empty\n" as *u8); return 1 }
  var ns: i64 = h[0]
  if maxsegs > 0 { if ns > maxsegs { ns = maxsegs } }
  var bits: i64 = SB_BITS_10PCT
  var kk: i64 = SB_K_10PCT
  if profile == 2 { bits = SB_BITS_1PCT; kk = SB_K_1PCT }
  sb_puts("  segments=" as *u8); sb_num(ns)
  sb_puts("  profile=" as *u8); if profile == 2 { sb_puts("1pct" as *u8) } else { sb_puts("10pct" as *u8) }
  sb_puts(" (bits/term=" as *u8); sb_num(bits); sb_puts(" k=" as *u8); sb_num(kk); sb_puts(")\n" as *u8)
  let blooms: *i64 = sys_mmap(8 * SB_MAXSEGS) as *i64
  let tp: *i64 = sys_mmap(SB_SMALL) as *i64
  let tl: *i64 = sys_mmap(SB_SMALL) as *i64
  let dc: *i64 = sys_mmap(SB_SMALL) as *i64
  let t0: i64 = sys_now_us()
  var totbytes: i64 = 0
  var totterms: i64 = 0
  var s: i64 = 0
  while s < ns {
      let c: i64 = ss_term_count(h, s)
      var cap: i64 = sb_next_pow2(c * bits)
      if c == 0 { cap = 64 }
      let bf: *BloomS = nx_bloom_alloc(cap, kk)
      blooms[s] = bf as i64
      totbytes = totbytes + (cap / 8)
      totterms = totterms + c
      var i: i64 = 0
      while i < c {
          if ss_term_at(h, s, i, tp, tl, dc) == 1 {
              nx_bloom_insert(bf, tp[0] as *u8, tl[0])
          }
          i = i + 1
      }
      s = s + 1
  }
  let t1: i64 = sys_now_us()
  sb_puts("  built " as *u8); sb_num(totterms); sb_puts(" terms into " as *u8); sb_num(totbytes)
  sb_puts(" bloom bytes in " as *u8); sb_num((t1 - t0) / 1000); sb_puts(" ms\n" as *u8)
  // THE MEASUREMENT: how many segments would the bloom let us SKIP for this term?
  let tn: i64 = sb_slen(term)
  var maybe: i64 = 0
  s = 0
  while s < ns {
      let bf: *BloomS = blooms[s] as *BloomS
      if nx_bloom_contains(bf, term, tn) == 1 { maybe = maybe + 1 }
      s = s + 1
  }
  let skip: i64 = ns - maybe
  sb_puts("  term '" as *u8); sb_w(term, tn); sb_puts("': maybe=" as *u8); sb_num(maybe)
  sb_puts(" skip=" as *u8); sb_num(skip)
  if ns > 0 { sb_puts(" skip_rate=" as *u8); sb_num((skip * 1000) / ns); sb_puts(" permil" as *u8) }
  sb_puts("\n" as *u8)
  // GROUND TRUTH, not just the bloom's opinion. A bloom may only ever be a FALSE POSITIVE, never a
  // false negative -- so if ss_terms_find finds the term in a segment the bloom skipped, the whole
  // idea is unsound and must be reported as such rather than quietly averaged away.
  let outs: *i64 = sys_mmap(SB_SMALL) as *i64
  var truth: i64 = 0
  var unsound: i64 = 0
  s = 0
  while s < ns {
      let tb: *u8 = h[5 + 8 * s] as *u8
      var present: i64 = 0
      if h[6 + 8 * s] >= 8 { if ss_terms_find(tb, h[6 + 8 * s], term, outs) == 1 { present = 1 } }
      if present == 1 {
          truth = truth + 1
          let bf: *BloomS = blooms[s] as *BloomS
          if nx_bloom_contains(bf, term, tn) == 0 { unsound = unsound + 1 }
      }
      s = s + 1
  }
  sb_puts("  ground truth: segments actually holding the term=" as *u8); sb_num(truth)
  sb_puts("  false_negatives=" as *u8); sb_num(unsound); sb_puts("\n" as *u8)
  if unsound > 0 {
      sb_puts("verdict=UNSOUND (a bloom reported ABSENT for a segment that HOLDS the term -- do NOT wire)\n" as *u8)
      return 2
  }
  if truth > maybe { sb_puts("verdict=IMPOSSIBLE (truth exceeds maybe)\n" as *u8); return 2 }
  let fp: i64 = maybe - truth
  sb_puts("  false positives=" as *u8); sb_num(fp)
  if ns > 0 { sb_puts(" (" as *u8); sb_num((fp * 1000) / ns); sb_puts(" permil of segments)" as *u8) }
  sb_puts("\n" as *u8)
  sb_puts("verdict=SOUND  skip_rate=" as *u8)
  if ns > 0 { sb_num((skip * 1000) / ns) } else { sb_num(0) }
  sb_puts(" permil -- that fraction of per-segment page faults disappears\n" as *u8)
  return 0
189}
190func sb_atoi(s: *u8) -> i64 {
  var v: i64 = 0
  var i: i64 = 0
  var seen: i64 = 0
  while s[i] != (0 as u8) {
      let c: i64 = s[i] as i64
      if c >= 48 { if c <= 57 { v = v * 10 + (c - 48); seen = 1 } }
      i = i + 1
  }
  if seen == 0 { return 0 }
  return v
201}
202func main(argc: i64, argv: *i64) -> i64 {
  if argc < 3 {
      sb_puts("usage: nx_segbloom stat <domain> [maxsegs] | probe <domain> <profile 1|2> <term> [maxsegs]\n" as *u8)
      sys_exit(0); return 0
  }
  let verb: *u8 = argv[1] as *u8
  if sb_slen(verb) == 4 {
      if verb[0] == (115 as u8) { if verb[1] == (116 as u8) { if verb[2] == (97 as u8) { if verb[3] == (116 as u8) {
          var mx: i64 = 0
          if argc >= 4 { mx = sb_atoi(argv[3] as *u8) }
          let rc: i64 = cmd_stat(argv[2] as *u8, mx)
          sys_exit(rc); return rc
      } } } }
  }
  if argc >= 5 {
      var mx2: i64 = 0
      if argc >= 6 { mx2 = sb_atoi(argv[5] as *u8) }
      let rc: i64 = cmd_probe(argv[2] as *u8, sb_atoi(argv[3] as *u8), argv[4] as *u8, mx2)
      sys_exit(rc); return rc
  }
  sb_puts("usage: nx_segbloom stat <domain> [maxsegs] | probe <domain> <profile 1|2> <term> [maxsegs]\n" as *u8)
  sys_exit(2)
  return 2
225}
nx_segbloom.nx source

`nx_segbloom.nx` source
