Struct ExistenceFilter

Source

pub struct ExistenceFilter { /* private fields */ }

Expand description

A .kvei existence filter.

Implementations§

Source §

impl ExistenceFilter

Source

pub fn open(path: impl AsRef<Path>) -> Result<ExistenceFilter>

Open and parse a .kvei file.

Unknown-but-structurally-valid encodings open successfully as FilterKind::Unsupported (match-all) rather than erroring, so a reader can fall back to the exact .bt search without special-casing the filter format.

Source

pub fn advise_random(&self) -> Result<()>

Advise the kernel that this .kvei is probed in random order. See KvReader::advise_random.

Source

pub fn mapped_bytes(&self) -> u64

Bytes this .kvei occupies when fully resident.

Source

pub fn preload(&self) -> u64

Read the whole .kvei into the page cache, returning once it is resident. See KvReader::preload_index.

Source

pub fn lock(&self) -> Result<()>

Pin the whole .kvei in RAM with mlock. See KvReader::lock_index for the caveats.

Source

pub fn unlock(&self) -> Result<()>

Release an mlock.

Source

pub fn kind(&self) -> FilterKind

Which encoding this filter turned out to be.

Examples found in repository ?

examples/inspect.rs (line 37)

15fn main() -> Result<(), Box<dyn std::error::Error>> {
16    let mut args = std::env::args().skip(1);
17    let kv_path = args
18        .next()
19        .expect("usage: inspect <path-to.kv> [salt-state.txt]");
20    let salt_path = args.next();
21
22    let t = Instant::now();
23    let mut r = KvReader::open(&kv_path)?;
24    println!("opened {kv_path} in {:?}", t.elapsed());
25    println!("  seg version      : v{}", r.seg().version());
26    println!("  words_count      : {}", r.seg().words_count());
27    println!("  empty_words      : {}", r.seg().empty_words_count());
28    println!("  key_count        : {}", r.key_count());
29    println!("  has .bt index    : {}", r.index().is_some());
30    if let Some(idx) = r.index() {
31        println!("    bt key_count   : {}", idx.key_count());
32        println!("    bt M           : {:?}", idx.m());
33    }
34    match r.existence_filter() {
35        Some(f) => println!(
36            "  .kvei kind       : {:?} (accelerating={})",
37            f.kind(),
38            f.is_accelerating()
39        ),
40        None => println!("  .kvei            : (none)"),
41    }
42
43    // First few (key, value) pairs.
44    println!("\nfirst pairs:");
45    let mut sample: Vec<(Vec<u8>, Vec<u8>)> = Vec::new();
46    for (i, kv) in r.iter().enumerate().take(5) {
47        let (k, v) = kv?;
48        println!(
49            "  [{i}] key={} ({} B)  value={} B",
50            hex(&k),
51            k.len(),
52            v.len()
53        );
54        sample.push((k, v));
55    }
56
57    // Round-trip a spread of real keys through get().
58    println!("\nround-trip lookups (spread across the file):");
59    let n = r.key_count();
60    let mut checked = 0u64;
61    let mut probe_keys: Vec<Vec<u8>> = Vec::new();
62    if let Some(idx) = r.index() {
63        let g_count = 12u64.min(n.max(1));
64        let mut g = r.seg().getter();
65        for s in 0..g_count {
66            let di = s * n / g_count;
67            if let Some(off) = idx.key_offset(di) {
68                g.reset(off);
69                probe_keys.push(g.next());
70            }
71        }
72    } else {
73        probe_keys = sample.iter().map(|(k, _)| k.clone()).collect();
74    }
75    let t = Instant::now();
76    for k in &probe_keys {
77        let got = r.get(k)?;
78        assert!(got.is_some(), "real key {} not found by get()", hex(k));
79        checked += 1;
80    }
81    let dt = t.elapsed();
82    println!(
83        "  {checked} keys all found; avg {:?}/lookup",
84        dt.checked_div(checked.max(1) as u32).unwrap_or_default()
85    );
86
87    // Cross-check: get() value equals the value that follows the key in iteration order.
88    for (k, v) in &sample {
89        assert_eq!(
90            r.get(k)?.as_deref(),
91            Some(v.as_slice()),
92            "value mismatch for {}",
93            hex(k)
94        );
95    }
96    println!("  values match sequential iteration ✓");
97
98    // Negative lookup: a key we are confident is absent.
99    let absent = b"\xff_erigon_seg_definitely_absent_key_\xff";
100    println!(
101        "\nnegative lookup for a synthetic key: {:?}",
102        r.get(absent)?.map(|v| v.len())
103    );
104
105    // Salt resolution + bloom acceleration.
106    if r.existence_filter()
107        .map(|f| f.is_accelerating())
108        .unwrap_or(false)
109    {
110        // (a) brute-force find.
111        let t = Instant::now();
112        let found = r.find_salt(num_cpus());
113        println!(
114            "\nfind_salt -> {:?}  (in {:?})",
115            found.map(|s| format!("{s:#010x}")),
116            t.elapsed()
117        );
118
119        // (b) known salt from the salt file, if provided.
120        let salt = match &salt_path {
121            Some(p) => salt_from_file(p),
122            None => None,
123        };
124        if let Some(s) = salt {
125            println!("salt-state.txt   -> {s:#010x}");
126            if let Some(f) = found {
127                assert_eq!(f, s, "brute-forced salt disagrees with salt file");
128            }
129        }
130        let chosen = salt.map(Salt::Known).unwrap_or(Salt::Find(num_cpus()));
131        let enabled = r.enable_bloom(chosen);
132        println!(
133            "enable_bloom     -> {enabled} (active salt = {:?})",
134            r.salt().map(|s| format!("{s:#010x}"))
135        );
136
137        if let (Some(s), Some(f)) = (r.salt(), r.existence_filter()) {
138            // Every real probe key must be reported present by the bloom.
139            let all_present = probe_keys
140                .iter()
141                .all(|k| f.contains_hash(murmur3_x64_128_h1(k, s)));
142            println!(
143                "bloom: all {} real probe keys reported present = {all_present}",
144                probe_keys.len()
145            );
146            assert!(
147                all_present,
148                "bloom false-negative on a real key (wrong salt?)"
149            );
150
151            // Timed lookups with bloom enabled (negatives short-circuit).
152            let t = Instant::now();
153            for k in &probe_keys {
154                let _ = r.get(k)?;
155            }
156            println!(
157                "  {} bloom-gated lookups in {:?}",
158                probe_keys.len(),
159                t.elapsed()
160            );
161        }
162    }
163
164    println!("\nOK");
165    Ok(())
166}

Source

pub fn is_accelerating(&self) -> bool

Whether this filter can actually exclude keys (i.e. is a supported bloom). When false, contains_hash always returns true.

Examples found in repository ?

examples/inspect.rs (line 38)

15fn main() -> Result<(), Box<dyn std::error::Error>> {
16    let mut args = std::env::args().skip(1);
17    let kv_path = args
18        .next()
19        .expect("usage: inspect <path-to.kv> [salt-state.txt]");
20    let salt_path = args.next();
21
22    let t = Instant::now();
23    let mut r = KvReader::open(&kv_path)?;
24    println!("opened {kv_path} in {:?}", t.elapsed());
25    println!("  seg version      : v{}", r.seg().version());
26    println!("  words_count      : {}", r.seg().words_count());
27    println!("  empty_words      : {}", r.seg().empty_words_count());
28    println!("  key_count        : {}", r.key_count());
29    println!("  has .bt index    : {}", r.index().is_some());
30    if let Some(idx) = r.index() {
31        println!("    bt key_count   : {}", idx.key_count());
32        println!("    bt M           : {:?}", idx.m());
33    }
34    match r.existence_filter() {
35        Some(f) => println!(
36            "  .kvei kind       : {:?} (accelerating={})",
37            f.kind(),
38            f.is_accelerating()
39        ),
40        None => println!("  .kvei            : (none)"),
41    }
42
43    // First few (key, value) pairs.
44    println!("\nfirst pairs:");
45    let mut sample: Vec<(Vec<u8>, Vec<u8>)> = Vec::new();
46    for (i, kv) in r.iter().enumerate().take(5) {
47        let (k, v) = kv?;
48        println!(
49            "  [{i}] key={} ({} B)  value={} B",
50            hex(&k),
51            k.len(),
52            v.len()
53        );
54        sample.push((k, v));
55    }
56
57    // Round-trip a spread of real keys through get().
58    println!("\nround-trip lookups (spread across the file):");
59    let n = r.key_count();
60    let mut checked = 0u64;
61    let mut probe_keys: Vec<Vec<u8>> = Vec::new();
62    if let Some(idx) = r.index() {
63        let g_count = 12u64.min(n.max(1));
64        let mut g = r.seg().getter();
65        for s in 0..g_count {
66            let di = s * n / g_count;
67            if let Some(off) = idx.key_offset(di) {
68                g.reset(off);
69                probe_keys.push(g.next());
70            }
71        }
72    } else {
73        probe_keys = sample.iter().map(|(k, _)| k.clone()).collect();
74    }
75    let t = Instant::now();
76    for k in &probe_keys {
77        let got = r.get(k)?;
78        assert!(got.is_some(), "real key {} not found by get()", hex(k));
79        checked += 1;
80    }
81    let dt = t.elapsed();
82    println!(
83        "  {checked} keys all found; avg {:?}/lookup",
84        dt.checked_div(checked.max(1) as u32).unwrap_or_default()
85    );
86
87    // Cross-check: get() value equals the value that follows the key in iteration order.
88    for (k, v) in &sample {
89        assert_eq!(
90            r.get(k)?.as_deref(),
91            Some(v.as_slice()),
92            "value mismatch for {}",
93            hex(k)
94        );
95    }
96    println!("  values match sequential iteration ✓");
97
98    // Negative lookup: a key we are confident is absent.
99    let absent = b"\xff_erigon_seg_definitely_absent_key_\xff";
100    println!(
101        "\nnegative lookup for a synthetic key: {:?}",
102        r.get(absent)?.map(|v| v.len())
103    );
104
105    // Salt resolution + bloom acceleration.
106    if r.existence_filter()
107        .map(|f| f.is_accelerating())
108        .unwrap_or(false)
109    {
110        // (a) brute-force find.
111        let t = Instant::now();
112        let found = r.find_salt(num_cpus());
113        println!(
114            "\nfind_salt -> {:?}  (in {:?})",
115            found.map(|s| format!("{s:#010x}")),
116            t.elapsed()
117        );
118
119        // (b) known salt from the salt file, if provided.
120        let salt = match &salt_path {
121            Some(p) => salt_from_file(p),
122            None => None,
123        };
124        if let Some(s) = salt {
125            println!("salt-state.txt   -> {s:#010x}");
126            if let Some(f) = found {
127                assert_eq!(f, s, "brute-forced salt disagrees with salt file");
128            }
129        }
130        let chosen = salt.map(Salt::Known).unwrap_or(Salt::Find(num_cpus()));
131        let enabled = r.enable_bloom(chosen);
132        println!(
133            "enable_bloom     -> {enabled} (active salt = {:?})",
134            r.salt().map(|s| format!("{s:#010x}"))
135        );
136
137        if let (Some(s), Some(f)) = (r.salt(), r.existence_filter()) {
138            // Every real probe key must be reported present by the bloom.
139            let all_present = probe_keys
140                .iter()
141                .all(|k| f.contains_hash(murmur3_x64_128_h1(k, s)));
142            println!(
143                "bloom: all {} real probe keys reported present = {all_present}",
144                probe_keys.len()
145            );
146            assert!(
147                all_present,
148                "bloom false-negative on a real key (wrong salt?)"
149            );
150
151            // Timed lookups with bloom enabled (negatives short-circuit).
152            let t = Instant::now();
153            for k in &probe_keys {
154                let _ = r.get(k)?;
155            }
156            println!(
157                "  {} bloom-gated lookups in {:?}",
158                probe_keys.len(),
159                t.elapsed()
160            );
161        }
162    }
163
164    println!("\nOK");
165    Ok(())
166}

Source

pub fn contains_hash(&self, hash: u64) -> bool

ContainsHash: false ⇒ the key is definitely absent. hash is the murmur3 h1 of the key (see crate::murmur3_x64_128_h1). Always true for an empty or unsupported filter.

Examples found in repository ?

examples/inspect.rs (line 141)

15fn main() -> Result<(), Box<dyn std::error::Error>> {
16    let mut args = std::env::args().skip(1);
17    let kv_path = args
18        .next()
19        .expect("usage: inspect <path-to.kv> [salt-state.txt]");
20    let salt_path = args.next();
21
22    let t = Instant::now();
23    let mut r = KvReader::open(&kv_path)?;
24    println!("opened {kv_path} in {:?}", t.elapsed());
25    println!("  seg version      : v{}", r.seg().version());
26    println!("  words_count      : {}", r.seg().words_count());
27    println!("  empty_words      : {}", r.seg().empty_words_count());
28    println!("  key_count        : {}", r.key_count());
29    println!("  has .bt index    : {}", r.index().is_some());
30    if let Some(idx) = r.index() {
31        println!("    bt key_count   : {}", idx.key_count());
32        println!("    bt M           : {:?}", idx.m());
33    }
34    match r.existence_filter() {
35        Some(f) => println!(
36            "  .kvei kind       : {:?} (accelerating={})",
37            f.kind(),
38            f.is_accelerating()
39        ),
40        None => println!("  .kvei            : (none)"),
41    }
42
43    // First few (key, value) pairs.
44    println!("\nfirst pairs:");
45    let mut sample: Vec<(Vec<u8>, Vec<u8>)> = Vec::new();
46    for (i, kv) in r.iter().enumerate().take(5) {
47        let (k, v) = kv?;
48        println!(
49            "  [{i}] key={} ({} B)  value={} B",
50            hex(&k),
51            k.len(),
52            v.len()
53        );
54        sample.push((k, v));
55    }
56
57    // Round-trip a spread of real keys through get().
58    println!("\nround-trip lookups (spread across the file):");
59    let n = r.key_count();
60    let mut checked = 0u64;
61    let mut probe_keys: Vec<Vec<u8>> = Vec::new();
62    if let Some(idx) = r.index() {
63        let g_count = 12u64.min(n.max(1));
64        let mut g = r.seg().getter();
65        for s in 0..g_count {
66            let di = s * n / g_count;
67            if let Some(off) = idx.key_offset(di) {
68                g.reset(off);
69                probe_keys.push(g.next());
70            }
71        }
72    } else {
73        probe_keys = sample.iter().map(|(k, _)| k.clone()).collect();
74    }
75    let t = Instant::now();
76    for k in &probe_keys {
77        let got = r.get(k)?;
78        assert!(got.is_some(), "real key {} not found by get()", hex(k));
79        checked += 1;
80    }
81    let dt = t.elapsed();
82    println!(
83        "  {checked} keys all found; avg {:?}/lookup",
84        dt.checked_div(checked.max(1) as u32).unwrap_or_default()
85    );
86
87    // Cross-check: get() value equals the value that follows the key in iteration order.
88    for (k, v) in &sample {
89        assert_eq!(
90            r.get(k)?.as_deref(),
91            Some(v.as_slice()),
92            "value mismatch for {}",
93            hex(k)
94        );
95    }
96    println!("  values match sequential iteration ✓");
97
98    // Negative lookup: a key we are confident is absent.
99    let absent = b"\xff_erigon_seg_definitely_absent_key_\xff";
100    println!(
101        "\nnegative lookup for a synthetic key: {:?}",
102        r.get(absent)?.map(|v| v.len())
103    );
104
105    // Salt resolution + bloom acceleration.
106    if r.existence_filter()
107        .map(|f| f.is_accelerating())
108        .unwrap_or(false)
109    {
110        // (a) brute-force find.
111        let t = Instant::now();
112        let found = r.find_salt(num_cpus());
113        println!(
114            "\nfind_salt -> {:?}  (in {:?})",
115            found.map(|s| format!("{s:#010x}")),
116            t.elapsed()
117        );
118
119        // (b) known salt from the salt file, if provided.
120        let salt = match &salt_path {
121            Some(p) => salt_from_file(p),
122            None => None,
123        };
124        if let Some(s) = salt {
125            println!("salt-state.txt   -> {s:#010x}");
126            if let Some(f) = found {
127                assert_eq!(f, s, "brute-forced salt disagrees with salt file");
128            }
129        }
130        let chosen = salt.map(Salt::Known).unwrap_or(Salt::Find(num_cpus()));
131        let enabled = r.enable_bloom(chosen);
132        println!(
133            "enable_bloom     -> {enabled} (active salt = {:?})",
134            r.salt().map(|s| format!("{s:#010x}"))
135        );
136
137        if let (Some(s), Some(f)) = (r.salt(), r.existence_filter()) {
138            // Every real probe key must be reported present by the bloom.
139            let all_present = probe_keys
140                .iter()
141                .all(|k| f.contains_hash(murmur3_x64_128_h1(k, s)));
142            println!(
143                "bloom: all {} real probe keys reported present = {all_present}",
144                probe_keys.len()
145            );
146            assert!(
147                all_present,
148                "bloom false-negative on a real key (wrong salt?)"
149            );
150
151            // Timed lookups with bloom enabled (negatives short-circuit).
152            let t = Instant::now();
153            for k in &probe_keys {
154                let _ = r.get(k)?;
155            }
156            println!(
157                "  {} bloom-gated lookups in {:?}",
158                probe_keys.len(),
159                t.elapsed()
160            );
161        }
162    }
163
164    println!("\nOK");
165    Ok(())
166}