Repository: vercel/next.js
File: turbopack/crates/turbo-persistence/src/static_sorted_file_builder.rs (Rust)

Code before:
/// The aimed false positive rate for the AMQF
const AMQF_FALSE_POSITIVE_RATE: f64 = 0.01;

/// The maximum compression dictionary size for key and index blocks
const KEY_COMPRESSION_DICTIONARY_SIZE: usize = 64 * 1024 - 1;
/// The maximum bytes that should be selected as key samples to create a compression dictionary
const KEY_COMPRESSION_SAMPLES_SIZE: usize = 256 * 1024;
/// The minimum bytes that should be selected as keys samples. Below that no compression dictionary
/// is used.
const MIN_KEY_COMPRESSION_SAMPLES_SIZE: usize = 1024;
/// The bytes that are used per key entry for a sample.
const COMPRESSION_DICTIONARY_SAMPLE_PER_ENTRY: usize = 100;
/// The minimum bytes that are used per key entry for a sample.
const MIN_COMPRESSION_DICTIONARY_SAMPLE_PER_ENTRY: usize = 16;

/// Computes the number of hash bytes to store per entry based on max key length and entry count.
fn compute_hash_len(max_key_len: usize, entry_count: usize) -> u8 {
    if max_key_len <= 8 {
        0 // No hash needed, key data fits in 8 bytes
    } else if max_key_len > 128 {
        8 // Full hash for long keys
    } else {
        // Enough bytes to have good collision avoidance
        // log2(entry_count) bits + 8 bits margin, rounded up to bytes
        let bits_needed = (entry_count as f64).log2().ceil() as u32 + 8;
        bits_needed.div_ceil(8).min(8) as u8
    }
}

/// Trait for entries from that SST files can be created
pub trait Entry {
    /// Returns the hash of the key
    fn key_hash(&self) -> u64;
    /// Returns the length of the key
    fn key_len(&self) -> usize;
    /// Writes the key to a buffer
    fn write_key_to(&self, buf: &mut Vec<u8>);

    /// Returns the value
    fn value(&self) -> EntryValue<'_>;
}

/// Reference to a value
#[derive(Copy, Clone)]
pub enum EntryValue<'l> {
    /// Small-sized value. They are stored in shared value blocks.
    Small { value: &'l [u8] },
    /// Medium-sized value. They are stored in their own value block.
    Medium { value: &'l [u8] },
    /// Medium-sized value. They are stored in their own value block. Precompressed.
    MediumCompressed {

Review comment (performance):
i think this will pretty much always be 2 or 3 for realistic `entry_count` numbers

hash_len = 7: entry_count ≥ 2^41 (2,199,023,255,552 / ~2.2 trillion)
hash_len = 6: entry_count ≥ 2^33 (8,589,934,592 / ~8.6 billion)
hash_len = 5: entry_count ≥ 2^25 (33,554,432 / ~33.6 million)
hash_len = 4: entry_count ≥ 2^17 (131,072 / ~131k)
hash_len = 3: entry_count ≥ 2^9 (512)
hash_len = 2: entry_count ≥ 2^1 (2)
hash_len = 1: entry_count = 1


so it might be better to just pick `4` 

but of course in reality the max_key_len is always going to be <8 for TaskData and TaskMeta and >128 for ForwardTaskCache

so maybe this is more complex than we care about.

Static 'per family configuration' also makes a lot of sense to me rather than dyanmically changing strategies per key block.

Code after:
/// The aimed false positive rate for the AMQF
const AMQF_FALSE_POSITIVE_RATE: f64 = 0.01;

/// The maximum compression dictionary size for key and index blocks
const KEY_COMPRESSION_DICTIONARY_SIZE: usize = 64 * 1024 - 1;
/// The maximum bytes that should be selected as key samples to create a compression dictionary
const KEY_COMPRESSION_SAMPLES_SIZE: usize = 256 * 1024;
/// The minimum bytes that should be selected as keys samples. Below that no compression dictionary
/// is used.
const MIN_KEY_COMPRESSION_SAMPLES_SIZE: usize = 1024;
/// The bytes that are used per key entry for a sample.
const COMPRESSION_DICTIONARY_SAMPLE_PER_ENTRY: usize = 100;
/// The minimum bytes that are used per key entry for a sample.
const MIN_COMPRESSION_DICTIONARY_SAMPLE_PER_ENTRY: usize = 16;

/// Determines whether to store the hash per entry based on max key length.
fn use_hash(max_key_len: usize) -> bool {
    max_key_len > 32
}

/// Trait for entries from that SST files can be created
pub trait Entry {
    /// Returns the hash of the key
    fn key_hash(&self) -> u64;
    /// Returns the length of the key
    fn key_len(&self) -> usize;
    /// Writes the key to a buffer
    fn write_key_to(&self, buf: &mut Vec<u8>);

    /// Returns the value
    fn value(&self) -> EntryValue<'_>;
}

/// Reference to a value
#[derive(Copy, Clone)]
pub enum EntryValue<'l> {
    /// Small-sized value. They are stored in shared value blocks.
    Small { value: &'l [u8] },
    /// Medium-sized value. They are stored in their own value block.
    Medium { value: &'l [u8] },
    /// Medium-sized value. They are stored in their own value block. Precompressed.
    MediumCompressed {
        uncompressed_size: u32,
        block: &'l [u8],
    },
    /// Large-sized value. They are stored in a blob file.
    Large { blob: u32 },
    /// Tombstone. The value was removed.
    Deleted,
}