turbo_persistence/
meta_file.rs

1use std::{
2    cmp::Ordering,
3    fmt::Display,
4    mem::take,
5    ops::Deref,
6    path::{Path, PathBuf},
7    sync::{Arc, OnceLock},
8};
9
10use anyhow::{Context, Result, bail, ensure};
11use bitfield::bitfield;
12use byteorder::{BE, ReadBytesExt};
13#[cfg(feature = "mmap")]
14use fs_err::File;
15#[cfg(feature = "mmap")]
16use memmap2::{Mmap, MmapOptions};
17use zerocopy::{FromBytes, Immutable, IntoBytes, KnownLayout, Ref, big_endian as be};
18
19#[cfg(feature = "mmap")]
20use crate::mmap_helper::advise_mmap_for_persistence;
21use crate::{
22    AccessMode, Compression, FamilyConfig, QueryKey,
23    lookup_entry::LookupValue,
24    shard::ShardBits,
25    static_sorted_file::{BlockCache, SstLookupResult, StaticSortedFile, StaticSortedFileMetaData},
26};
27
28bitfield! {
29    #[derive(Clone, Copy, Default)]
30    pub struct MetaEntryFlags(u32);
31    impl Debug;
32    impl From<u32>;
33    /// The SST file was compacted and none of the entries have been accessed recently.
34    /// Only relevant for bottom files
35    pub cold, set_cold: 0;
36    /// The SST file was freshly written and has not been compacted yet.
37    pub fresh, set_fresh: 1;
38    /// The SST file is part of the bottom run of its shard.
39    pub bottom, set_bottom: 2;
40}
41
42impl MetaEntryFlags {
43    pub const FRESH: MetaEntryFlags = MetaEntryFlags(0b010);
44    pub const COMPACTED: MetaEntryFlags = MetaEntryFlags(0b000);
45    pub const COLD_BOTTOM: MetaEntryFlags = MetaEntryFlags(0b101);
46    pub const HOT_BOTTOM: MetaEntryFlags = MetaEntryFlags(0b100);
47}
48
49impl Display for MetaEntryFlags {
50    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
51        if self.fresh() {
52            f.pad_integral(true, "", "fresh")
53        } else if self.bottom() && self.cold() {
54            f.pad_integral(true, "", "cold bottom")
55        } else if self.bottom() {
56            f.pad_integral(true, "", "hot bottom")
57        } else {
58            f.pad_integral(true, "", "compacted")
59        }
60    }
61}
62
63/// Magic number identifying a `.meta` file.
64pub(crate) const META_FILE_MAGIC: u32 = 0xFE4ADA4A;
65
66/// On-disk layout of a single entry header in the `.meta` file.
67///
68/// Fields are big-endian to match the existing wire format written by [`MetaFileBuilder`].
69#[repr(C, packed)]
70#[derive(FromBytes, IntoBytes, Immutable, KnownLayout, Clone, Copy)]
71pub(crate) struct EntryHeader {
72    sequence_number: be::U32,
73    block_count: be::U16,
74    min_hash: be::U64,
75    max_hash: be::U64,
76    size: be::U64,
77    flags: be::U32,
78    entry_count: be::U32,
79    tombstone_count: be::U32,
80    amqf_end_offset: be::U32,
81}
82
83impl EntryHeader {
84    pub(crate) fn new(
85        sequence_number: u32,
86        block_count: u16,
87        min_hash: u64,
88        max_hash: u64,
89        size: u64,
90        flags: MetaEntryFlags,
91        entry_count: u32,
92        tombstone_count: u32,
93        amqf_end_offset: u32,
94    ) -> Self {
95        Self {
96            sequence_number: be::U32::new(sequence_number),
97            block_count: be::U16::new(block_count),
98            min_hash: be::U64::new(min_hash),
99            max_hash: be::U64::new(max_hash),
100            size: be::U64::new(size),
101            flags: be::U32::new(flags.0),
102            entry_count: be::U32::new(entry_count),
103            tombstone_count: be::U32::new(tombstone_count),
104            amqf_end_offset: be::U32::new(amqf_end_offset),
105        }
106    }
107}
108
109/// # Safety
110///
111/// `MetaEntry` stores a `FilterRef<'static>` with a transmuted lifetime that actually borrows
112/// from the parent [`MetaFile`]'s stable backing bytes. This is safe as long as an entry never
113/// outlives that backing: entries are only handed out by reference, and the one place that moves
114/// them ([`MetaFile::retain_entries`]) keeps them inside the same `MetaFile`.
115///
116/// For this reason this type should not implement Clone or Copy — a copy could outlive the
117/// `MetaFile` that owns the backing it points into.
118pub struct MetaEntry {
119    /// The metadata for the static sorted file.
120    sst_data: StaticSortedFileMetaData,
121    /// The size of the SST file in bytes.
122    size: u64,
123    /// The status flags for this entry.
124    flags: MetaEntryFlags,
125    /// The number of entries in the SST file.
126    entry_count: u32,
127    /// The number of tombstone entries in the SST file.
128    tombstone_count: u32,
129    /// Byte offset range of the raw AMQF data within the backing, used for carrying forward
130    /// serialized bytes during compaction without re-serializing.
131    amqf_data_offset: std::ops::Range<u32>,
132    /// The AMQF filter for this file, eagerly deserialized as a zero-copy [`qfilter::FilterRef`]
133    /// that borrows directly from the parent [`MetaFile`]'s memory-mapped file.
134    ///
135    /// The `'static` lifetime is transmuted — the actual borrow is from `MetaFile::backing`.
136    amqf: qfilter::FilterRef<'static>,
137    /// Compression recorded in this entry's meta file.
138    compression: Compression,
139    /// The static sorted file that is lazily loaded
140    sst: OnceLock<StaticSortedFile>,
141}
142
143// Safety: FilterRef is a read-only view into stable backing bytes which are Send+Sync.
144unsafe impl Send for MetaEntry {}
145unsafe impl Sync for MetaEntry {}
146
147impl MetaEntry {
148    pub fn sequence_number(&self) -> u32 {
149        self.sst_data.sequence_number
150    }
151
152    pub fn size(&self) -> u64 {
153        self.size
154    }
155
156    pub fn flags(&self) -> MetaEntryFlags {
157        self.flags
158    }
159
160    /// The number of entries in the SST file.
161    pub fn entry_count(&self) -> u32 {
162        self.entry_count
163    }
164
165    /// The number of tombstone entries (`KeyDeleted` and `KeyValueDeleted`) in the SST file.
166    pub fn tombstone_count(&self) -> u32 {
167        self.tombstone_count
168    }
169
170    pub fn amqf_size(&self) -> u32 {
171        self.amqf_data_offset.end - self.amqf_data_offset.start
172    }
173
174    pub fn amqf(&self) -> &qfilter::FilterRef<'static> {
175        &self.amqf
176    }
177
178    /// Returns the raw serialized AMQF bytes from the stable backing.
179    pub fn raw_amqf<'l>(&self, amqf_data: &'l [u8]) -> &'l [u8] {
180        &amqf_data[self.amqf_data_offset.start as usize..self.amqf_data_offset.end as usize]
181    }
182
183    fn sst(&self, meta: &MetaFile) -> Result<&StaticSortedFile> {
184        self.sst.get_or_try_init(|| {
185            StaticSortedFile::open(
186                &meta.db_path,
187                self.sst_data,
188                self.compression,
189                meta.access_mode,
190            )
191            .with_context(|| {
192                format!(
193                    "Unable to open static sorted file referenced from {:08}.meta",
194                    meta.sequence_number()
195                )
196            })
197        })
198    }
199
200    pub fn block_count(&self) -> u16 {
201        self.sst_data.block_count
202    }
203
204    /// Returns the SST metadata needed to open the file independently.
205    /// Used during compaction to avoid caching mmaps on the MetaEntry.
206    pub fn sst_metadata(&self) -> StaticSortedFileMetaData {
207        self.sst_data
208    }
209}
210
211/// The result of a lookup operation.
212pub enum MetaLookupResult {
213    /// The key was not found because it is out of the range of this SST file. But it was the
214    /// correct key family.
215    RangeMiss,
216    /// The key was not found because it was not in the AMQF filter. But it was in the range.
217    QuickFilterMiss,
218    /// The key was looked up in the SST file. It was in the AMQF filter.
219    SstLookup(SstLookupResult),
220}
221
222/// The result of a batch lookup operation.
223#[derive(Default)]
224pub struct MetaBatchLookupResult {
225    /// The key was not found because it is out of the range of this SST file. But it was the
226    /// correct key family.
227    #[cfg(feature = "stats")]
228    pub range_misses: usize,
229    /// The key was not found because it was not in the AMQF filter. But it was in the range.
230    #[cfg(feature = "stats")]
231    pub quick_filter_misses: usize,
232    /// The key was unsuccessfully looked up in the SST file. It was in the AMQF filter.
233    #[cfg(feature = "stats")]
234    pub sst_misses: usize,
235    /// The key was found in the SST file.
236    #[cfg(feature = "stats")]
237    pub hits: usize,
238}
239
240/// The key family and hash range of an SST file.
241#[derive(Clone, Copy)]
242pub struct StaticSortedFileRange {
243    pub min_hash: u64,
244    pub max_hash: u64,
245}
246
247impl StaticSortedFileRange {
248    /// Whether `hash` falls within this file's span. A lookup can skip the file entirely if not.
249    #[inline(always)]
250    pub fn contains(&self, hash: u64) -> bool {
251        hash >= self.min_hash && hash <= self.max_hash
252    }
253}
254
255enum MetaFileBacking {
256    #[cfg(feature = "mmap")]
257    Mmap(Mmap),
258    /// Heap bytes for [`AccessMode::File`].
259    ///
260    /// This is an `Arc<[u8]>` rather than a `Box<[u8]>` so that moving the backing into
261    /// [`MetaFile`] does not reborrow the bytes: a `Box` is a unique pointer, so the move
262    /// invalidates the `FilterRef`s that already borrow from it, which Miri reports as undefined
263    /// behavior under Stacked Borrows. An `Arc` moves its handle without retagging the allocation.
264    Bytes(Arc<[u8]>),
265}
266
267impl Deref for MetaFileBacking {
268    type Target = [u8];
269
270    fn deref(&self) -> &Self::Target {
271        match self {
272            #[cfg(feature = "mmap")]
273            MetaFileBacking::Mmap(mmap) => mmap,
274            MetaFileBacking::Bytes(bytes) => bytes,
275        }
276    }
277}
278
279/// # Safety
280///
281/// `entries` must be declared before `backing` so every borrowed `FilterRef` is dropped before
282/// its stable mmap or heap storage.
283pub struct MetaFile {
284    /// The database path
285    db_path: PathBuf,
286    /// The sequence number of this file.
287    sequence_number: u32,
288    /// The key family of the SST files in this meta file.
289    family: u32,
290    /// Compression recorded for this family.
291    compression: Compression,
292    /// Stored separately from [`MetaEntry`] so that lookups can operate over a denser data
293    /// structure that's hotter in cache.
294    hash_ranges: Box<[StaticSortedFileRange]>,
295    /// The entries of the file. Dropped before `backing` (field declaration order).
296    entries: Box<[MetaEntry]>,
297    /// The entries that have been marked as obsolete.
298    obsolete_entries: Vec<u32>,
299    /// The obsolete SST files.
300    obsolete_sst_files: Vec<u32>,
301    /// Byte offset within the backing where the AMQF data region starts.
302    /// Entry AMQF offsets and used-keys offsets are relative to this position.
303    amqf_data_start: u32,
304    /// The shards the SST files of this meta file were split with.
305    shard_bits: ShardBits,
306    /// The offset of the start of the "used keys" AMQF data relative to the AMQF data region.
307    start_of_used_keys_amqf_data_offset: u32,
308    /// The offset of the end of the "used keys" AMQF data relative to the AMQF data region.
309    end_of_used_keys_amqf_data_offset: u32,
310    /// The access mode inherited by referenced SST files.
311    access_mode: AccessMode,
312    /// Stable bytes backing the parsed filters. Must be declared after `entries`.
313    backing: MetaFileBacking,
314}
315
316impl MetaFile {
317    /// Opens a meta file using mmap or stable heap bytes according to `access_mode`.
318    pub fn open(
319        db_path: &Path,
320        sequence_number: u32,
321        family_configs: Option<&[FamilyConfig]>,
322        access_mode: AccessMode,
323    ) -> Result<Self> {
324        let filename = format!("{sequence_number:08}.meta");
325        let path = db_path.join(&filename);
326        Self::open_internal(
327            db_path.to_path_buf(),
328            sequence_number,
329            &path,
330            family_configs,
331            access_mode,
332        )
333        .with_context(|| format!("Unable to open meta file {filename}"))
334    }
335
336    fn open_internal(
337        db_path: PathBuf,
338        sequence_number: u32,
339        path: &Path,
340        family_configs: Option<&[FamilyConfig]>,
341        access_mode: AccessMode,
342    ) -> Result<Self> {
343        let backing = match access_mode {
344            #[cfg(feature = "mmap")]
345            AccessMode::Mmap => {
346                let file = File::open(path)?;
347                let mmap = unsafe { MmapOptions::new().map(file.file()) }
348                    .context("Failed to mmap meta file")?;
349                #[cfg(unix)]
350                mmap.advise(memmap2::Advice::Random)
351                    .context("Failed to advise mmap")?;
352                advise_mmap_for_persistence(&mmap)?;
353                MetaFileBacking::Mmap(mmap)
354            }
355            AccessMode::File => MetaFileBacking::Bytes(fs_err::read(path)?.into()),
356        };
357        // Parse the header from stable backing bytes via ReadBytesExt on &[u8].
358        let mut reader: &[u8] = &backing;
359        let magic = reader.read_u32::<BE>()?;
360        if magic != META_FILE_MAGIC {
361            bail!("Invalid magic number");
362        }
363        let family = reader.read_u32::<BE>()?;
364        let compression = match reader.read_u8()? {
365            value if value == Compression::Lz4 as u8 => Compression::Lz4,
366            value if value == Compression::Zstd3 as u8 => Compression::Zstd3,
367            value => bail!("Invalid compression algorithm {value}"),
368        };
369        let shard_bits = reader.read_u8()?;
370        let shard_bits = ShardBits::try_new(shard_bits)
371            .with_context(|| format!("Invalid shard bits {shard_bits}"))?;
372        if let Some(configs) = family_configs {
373            let configured = configs
374                .get(family as usize)
375                .with_context(|| format!("No configuration for family {family}"))?
376                .compression;
377            ensure!(
378                compression == configured,
379                "Compression configuration mismatch for family {family}: meta file uses \
380                 {compression:?}, runtime config uses {configured:?}"
381            );
382        }
383        let obsolete_count = reader.read_u32::<BE>()?;
384        let mut obsolete_sst_files = Vec::with_capacity(obsolete_count as usize);
385        for _ in 0..obsolete_count {
386            obsolete_sst_files.push(reader.read_u32::<BE>()?);
387        }
388
389        let count = reader.read_u32::<BE>()?;
390
391        // Compute where the AMQF data region starts so we can deserialize filters inline.
392        // Remaining header: count * ENTRY_HEADER_SIZE + used_keys_end_offset.
393        let header_so_far = (backing.len() - reader.len()) as u32;
394        let amqf_data_start =
395            header_so_far + count * (size_of::<EntryHeader>() as u32) + size_of::<u32>() as u32;
396        let amqf_data = &backing[amqf_data_start as usize..];
397
398        // Parse entries and eagerly deserialize AMQF filters as zero-copy FilterRefs.
399        let mut entries = Vec::with_capacity(count as usize);
400        let mut hash_ranges = Vec::with_capacity(count as usize);
401        let mut start_of_amqf_data_offset: u32 = 0;
402        for _ in 0..count {
403            let (header, rest): (Ref<&[u8], EntryHeader>, _) = Ref::from_prefix(reader)
404                .ok()
405                .context("Entry header out of bounds")?;
406            reader = rest;
407            let sst_data = StaticSortedFileMetaData {
408                sequence_number: header.sequence_number.get(),
409                block_count: header.block_count.get(),
410            };
411            let min_hash = header.min_hash.get();
412            let max_hash = header.max_hash.get();
413            let size = header.size.get();
414            let flags = MetaEntryFlags(header.flags.get());
415            let entry_count = header.entry_count.get();
416            let tombstone_count = header.tombstone_count.get();
417            let end_of_amqf_data_offset = header.amqf_end_offset.get();
418
419            let amqf_bytes = amqf_data
420                .get(start_of_amqf_data_offset as usize..end_of_amqf_data_offset as usize)
421                .expect("AMQF data out of bounds");
422            // Deserialize the filter borrowing from the stable backing, then erase the lifetime.
423            let amqf: qfilter::FilterRef<'_> =
424                postcard::from_bytes(amqf_bytes).with_context(|| {
425                    format!(
426                        "Failed to deserialize AMQF from {:08}.meta for {:08}.sst",
427                        sequence_number, sst_data.sequence_number
428                    )
429                })?;
430            // Safety: the backing is kept alive by MetaFile and is dropped after entries (field
431            // declaration order), so the borrow remains valid for the lifetime of the MetaEntry.
432            let amqf: qfilter::FilterRef<'static> = unsafe { std::mem::transmute(amqf) };
433
434            hash_ranges.push(StaticSortedFileRange { min_hash, max_hash });
435            entries.push(MetaEntry {
436                sst_data,
437                size,
438                flags,
439                entry_count,
440                tombstone_count,
441                amqf_data_offset: start_of_amqf_data_offset..end_of_amqf_data_offset,
442                amqf,
443                compression,
444                sst: OnceLock::new(),
445            });
446            start_of_amqf_data_offset = end_of_amqf_data_offset;
447        }
448
449        let start_of_used_keys_amqf_data_offset = start_of_amqf_data_offset;
450        let end_of_used_keys_amqf_data_offset = reader.read_u32::<BE>()?;
451
452        Ok(Self {
453            db_path,
454            sequence_number,
455            family,
456            compression,
457            hash_ranges: hash_ranges.into_boxed_slice(),
458            entries: entries.into_boxed_slice(),
459            obsolete_entries: Vec::new(),
460            obsolete_sst_files,
461            amqf_data_start,
462            shard_bits,
463            start_of_used_keys_amqf_data_offset,
464            end_of_used_keys_amqf_data_offset,
465            access_mode,
466            backing,
467        })
468    }
469
470    pub fn clear_cache(&mut self) {
471        for entry in self.entries.iter_mut() {
472            entry.sst.take();
473        }
474    }
475
476    pub fn prepare_sst_cache(&self) {
477        for entry in self.entries.iter() {
478            let _ = entry.sst(self);
479        }
480    }
481
482    pub fn sequence_number(&self) -> u32 {
483        self.sequence_number
484    }
485
486    /// The shards the SST files of this meta file were split with.
487    pub fn shard_bits(&self) -> ShardBits {
488        self.shard_bits
489    }
490
491    pub fn family(&self) -> u32 {
492        self.family
493    }
494
495    pub fn compression(&self) -> Compression {
496        self.compression
497    }
498
499    /// The on-disk size of this meta file in bytes (the length of its memory map).
500    pub fn byte_size(&self) -> u64 {
501        self.backing.len() as u64
502    }
503
504    pub fn entries(&self) -> &[MetaEntry] {
505        &self.entries
506    }
507
508    /// The hash ranges of this file's entries, in the same order as [`Self::entries`].
509    pub fn hash_ranges(&self) -> &[StaticSortedFileRange] {
510        &self.hash_ranges
511    }
512
513    /// The hash range of the entry at `index`.
514    pub fn hash_range(&self, index: u32) -> StaticSortedFileRange {
515        self.hash_ranges[index as usize]
516    }
517
518    /// The key family and hash range of the entry at `index`.
519    pub fn range(&self, index: u32) -> StaticSortedFileRange {
520        self.hash_range(index)
521    }
522
523    pub fn entry(&self, index: u32) -> &MetaEntry {
524        let index = index as usize;
525        &self.entries[index]
526    }
527
528    pub fn amqf_data(&self) -> &[u8] {
529        &self.backing[self.amqf_data_start as usize..]
530    }
531
532    /// The hashes of the keys that were read in the session that wrote this meta file, if it was
533    /// written by a commit.
534    pub fn deserialize_used_key_hashes_amqf(&self) -> Result<Option<qfilter::FilterRef<'_>>> {
535        if self.start_of_used_keys_amqf_data_offset == self.end_of_used_keys_amqf_data_offset {
536            return Ok(None);
537        }
538        let amqf = &self.amqf_data()[self.start_of_used_keys_amqf_data_offset as usize
539            ..self.end_of_used_keys_amqf_data_offset as usize];
540        Ok(Some(postcard::from_bytes(amqf).with_context(|| {
541            format!(
542                "Failed to deserialize used key hashes AMQF from {:08}.meta",
543                self.sequence_number
544            )
545        })?))
546    }
547
548    pub fn retain_entries(&mut self, mut predicate: impl FnMut(u32) -> bool) -> bool {
549        debug_assert_eq!(
550            self.entries.len(),
551            self.hash_ranges.len(),
552            "hash_ranges must stay parallel to entries"
553        );
554        let old_len = self.entries.len();
555        // Filter the two vectors as pairs so they cannot drift apart. Retaining them separately
556        // would leave a lookup indexing one by a position that means something else in the other.
557        //
558        // This rebuilds both vectors rather than compacting in place, which is the more expensive
559        // shape but a fine trade here: the callers are commit and compaction, never a lookup.
560        //
561        // Entries move between slots but never leave this `MetaFile`, so the `FilterRef`s they
562        // hold keep borrowing a mmap that is neither touched nor dropped.
563        let obsolete = &mut self.obsolete_entries;
564        let (entries, hash_ranges): (Vec<_>, Vec<_>) = take(&mut self.entries)
565            .into_iter()
566            .zip(take(&mut self.hash_ranges))
567            .filter(|(entry, _)| {
568                let retain = predicate(entry.sst_data.sequence_number);
569                if !retain {
570                    obsolete.push(entry.sst_data.sequence_number);
571                }
572                retain
573            })
574            .unzip();
575        self.entries = entries.into_boxed_slice();
576        self.hash_ranges = hash_ranges.into_boxed_slice();
577        old_len != self.entries.len()
578    }
579
580    pub fn obsolete_entries(&self) -> &[u32] {
581        &self.obsolete_entries
582    }
583
584    pub fn obsolete_sst_files(&self) -> &[u32] {
585        &self.obsolete_sst_files
586    }
587
588    /// Looks up a key in the SST file of the entry `entry_index`. The caller checks the hash range,
589    /// e.g. with [`crate::shard::ShardIndex`].
590    ///
591    /// If `FIND_ALL` is false, returns after finding the first match.
592    /// If `FIND_ALL` is true, returns all entries with the same key in the SST file
593    /// (useful for keyspaces where keys are hashes and collisions are possible).
594    pub(crate) fn lookup_entry<K: QueryKey, const FIND_ALL: bool>(
595        &self,
596        entry_index: u32,
597        key_hash: u64,
598        key: &K,
599        key_block_cache: &BlockCache,
600        value_block_cache: &BlockCache,
601    ) -> Result<MetaLookupResult> {
602        let entry = &self.entries[entry_index as usize];
603        if !entry.amqf.contains_fingerprint(key_hash) {
604            return Ok(MetaLookupResult::QuickFilterMiss);
605        }
606        Ok(MetaLookupResult::SstLookup(
607            entry.sst(self)?.lookup::<K, FIND_ALL>(
608                key_hash,
609                key,
610                key_block_cache,
611                value_block_cache,
612            )?,
613        ))
614    }
615
616    /// Looks up the keys of `cells` in the SST file of the entry `entry_index`, whose hash range is
617    /// `range`. Only cells without a result are looked up. `cells` must be sorted by key hash.
618    #[allow(clippy::too_many_arguments)]
619    pub(crate) fn batch_lookup_entry<K: QueryKey>(
620        &self,
621        entry_index: u32,
622        range: &StaticSortedFileRange,
623        keys: &[K],
624        cells: &mut [(u64, usize, Option<LookupValue>)],
625        empty_cells: &mut usize,
626        key_block_cache: &BlockCache,
627        value_block_cache: &BlockCache,
628    ) -> Result<MetaBatchLookupResult> {
629        debug_assert!(
630            cells.is_sorted_by_key(|(hash, _, _)| *hash),
631            "Cells must be sorted by key hash"
632        );
633        #[allow(unused_mut, reason = "It's used when stats are enabled")]
634        let mut lookup_result = MetaBatchLookupResult::default();
635        let start_index = cells
636            .binary_search_by(|(hash, _, _)| hash.cmp(&range.min_hash).then(Ordering::Greater))
637            .err()
638            .unwrap();
639        if start_index >= cells.len() {
640            #[cfg(feature = "stats")]
641            {
642                lookup_result.range_misses += 1;
643            }
644            return Ok(lookup_result);
645        }
646        let end_index = cells
647            .binary_search_by(|(hash, _, _)| hash.cmp(&range.max_hash).then(Ordering::Less))
648            .err()
649            .unwrap();
650        if start_index >= end_index {
651            #[cfg(feature = "stats")]
652            {
653                lookup_result.range_misses += 1;
654            }
655            return Ok(lookup_result);
656        }
657        let entry = &self.entries[entry_index as usize];
658        for (hash, index, result) in &mut cells[start_index..end_index] {
659            debug_assert!(range.contains(*hash), "Key hash out of range");
660            if result.is_some() {
661                continue;
662            }
663            if !entry.amqf.contains_fingerprint(*hash) {
664                #[cfg(feature = "stats")]
665                {
666                    lookup_result.quick_filter_misses += 1;
667                }
668                continue;
669            }
670            let sst_result = entry.sst(self)?.lookup::<_, false>(
671                *hash,
672                &keys[*index],
673                key_block_cache,
674                value_block_cache,
675            )?;
676            if let SstLookupResult::Found(mut values) = sst_result {
677                // find_all=false guarantees exactly one result
678                debug_assert!(values.len() == 1);
679                let Some(value) = values.pop() else {
680                    unreachable!()
681                };
682                *result = Some(value);
683                *empty_cells -= 1;
684                #[cfg(feature = "stats")]
685                {
686                    lookup_result.hits += 1;
687                }
688                if *empty_cells == 0 {
689                    return Ok(lookup_result);
690                }
691            } else {
692                #[cfg(feature = "stats")]
693                {
694                    lookup_result.sst_misses += 1;
695                }
696            }
697        }
698        Ok(lookup_result)
699    }
700}
turbo_persistence/meta_file.rs

turbo_persistence/
meta_file.rs
