armdb 0.15.1

sharded bitcask key-value storage optimized for NVMe
Documentation
//! Durable, publish-before-issue reservation of Bitcask file identifiers.

use std::fs;
use std::io::Write;
use std::path::{Path, PathBuf};

use crate::error::{DbError, DbResult};
use crate::io::direct;

pub(crate) const FILE_ID_RESERVE_WINDOW: u32 = 64;
pub(crate) const FILE_NAME: &str = "format.file-id";
pub(crate) const TMP_NAME: &str = "format.file-id.tmp";
const MAGIC: [u8; 4] = *b"AFI1";

pub(crate) fn write(dir: &Path, high: u32) -> DbResult<()> {
    let mut bytes = [0_u8; 12];
    bytes[..4].copy_from_slice(&MAGIC);
    bytes[4..8].copy_from_slice(&high.to_le_bytes());
    let crc = crc32fast::hash(&bytes[..8]).to_le_bytes();
    bytes[8..].copy_from_slice(&crc);
    let temp = dir.join(TMP_NAME);
    let mut file = fs::File::create(&temp)?;
    file.write_all(&bytes)?;
    file.sync_all()?;
    fs::rename(temp, dir.join(FILE_NAME))?;
    direct::sync_dir(dir)
}

pub(crate) fn read(dir: &Path) -> DbResult<u32> {
    let path = dir.join(FILE_NAME);
    let bytes = match fs::read(&path) {
        Ok(bytes) => bytes,
        Err(error) if error.kind() == std::io::ErrorKind::NotFound => return Ok(0),
        Err(error) => return Err(error.into()),
    };
    if bytes.len() != 12 || bytes[..4] != MAGIC {
        return Err(DbError::FormatMismatch(format!(
            "invalid file-id floor in {}",
            path.display()
        )));
    }
    let expected = u32::from_le_bytes(bytes[8..].try_into().expect("floor length checked"));
    if crc32fast::hash(&bytes[..8]) != expected {
        return Err(DbError::FormatMismatch(format!(
            "invalid file-id floor CRC in {}",
            path.display()
        )));
    }
    Ok(u32::from_le_bytes(
        bytes[4..8].try_into().expect("floor length checked"),
    ))
}

/// Reserves file-id windows durably before returning any identifier in them.
pub(crate) struct FileIdAllocator {
    dir: PathBuf,
    next: u32,
    reserved: u32,
}

impl FileIdAllocator {
    /// Resume above both the durable reservation and the files still on disk.
    pub(crate) fn open(dir: &Path, highest_on_disk: u32) -> DbResult<Self> {
        let reserved = read(dir)?;
        let next = highest_on_disk
            .max(reserved)
            .checked_add(1)
            .ok_or(DbError::Client("file_id space exhausted at open"))?;
        Ok(Self {
            dir: dir.to_path_buf(),
            next,
            reserved,
        })
    }

    /// Publish the next window before issuing its first id; never issue MAX.
    pub(crate) fn allocate(&mut self) -> DbResult<u32> {
        let id = self.next();
        if id == u32::MAX {
            return Err(DbError::Client("file_id space exhausted"));
        }
        if id > self.reserved() {
            let high = id
                .saturating_add(FILE_ID_RESERVE_WINDOW - 1)
                .min(u32::MAX - 1);
            write(&self.dir, high)?;
            self.reserved = high;
        }
        self.next += 1;
        Ok(id)
    }

    pub(crate) fn next(&self) -> u32 {
        self.next
    }
    pub(crate) fn reserved(&self) -> u32 {
        self.reserved
    }

    #[cfg(test)]
    pub(crate) fn set_next(&mut self, id: u32) {
        self.next = id;
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::error::DbError;
    use std::fs;
    use tempfile::tempdir;

    #[test]
    fn file_id_allocate_publishes_ceiling_before_returning() {
        let dir = tempdir().unwrap();
        let mut ids = FileIdAllocator::open(dir.path(), 0).unwrap();
        assert_eq!(ids.allocate().unwrap(), 1);
        assert_eq!(read(dir.path()).unwrap(), 64);
    }

    #[test]
    fn file_id_window_boundaries() {
        let dir = tempdir().unwrap();
        let mut ids = FileIdAllocator::open(dir.path(), 0).unwrap();
        assert_eq!(ids.allocate().unwrap(), 1);
        fs::remove_file(dir.path().join(FILE_NAME)).unwrap();
        for id in 2..=64 {
            assert_eq!(ids.allocate().unwrap(), id);
            assert!(!dir.path().join(FILE_NAME).exists());
        }
        assert_eq!(ids.allocate().unwrap(), 65);
        assert_eq!(read(dir.path()).unwrap(), 128);
    }

    #[test]
    fn file_id_reopen_starts_above_ceiling_without_files() {
        let dir = tempdir().unwrap();
        let mut ids = FileIdAllocator::open(dir.path(), 0).unwrap();
        ids.allocate().unwrap();
        drop(ids);
        assert_eq!(
            FileIdAllocator::open(dir.path(), 0)
                .unwrap()
                .allocate()
                .unwrap(),
            65
        );
        assert_eq!(read(dir.path()).unwrap(), 128);
    }

    #[test]
    fn file_id_marker_below_highest_file_is_overtaken() {
        let dir = tempdir().unwrap();
        write(dir.path(), 10).unwrap();
        assert_eq!(
            FileIdAllocator::open(dir.path(), 100)
                .unwrap()
                .allocate()
                .unwrap(),
            101
        );
        assert_eq!(read(dir.path()).unwrap(), 164);
    }

    #[test]
    fn file_id_failed_publish_returns_no_id_and_advances_nothing() {
        let dir = tempdir().unwrap();
        let mut ids = FileIdAllocator::open(dir.path(), 0).unwrap();
        fs::create_dir(dir.path().join(TMP_NAME)).unwrap();
        assert!(ids.allocate().is_err());
        assert_eq!(ids.next(), 1);
        assert_eq!(ids.reserved(), 0);
        fs::remove_dir(dir.path().join(TMP_NAME)).unwrap();
        assert_eq!(ids.allocate().unwrap(), 1);
    }

    #[test]
    fn file_id_floor_publish_failure_preserves_the_durable_floor() {
        let dir = tempdir().unwrap();
        write(dir.path(), 7).unwrap();
        fs::create_dir(dir.path().join(TMP_NAME)).unwrap();
        assert!(write(dir.path(), 11).is_err());
        assert_eq!(read(dir.path()).unwrap(), 7);
    }

    #[test]
    fn file_id_stale_tmp_from_interrupted_publish_is_overwritten() {
        let dir = tempdir().unwrap();
        fs::write(dir.path().join(TMP_NAME), b"junk").unwrap();
        assert_eq!(
            FileIdAllocator::open(dir.path(), 0)
                .unwrap()
                .allocate()
                .unwrap(),
            1
        );
        assert_eq!(read(dir.path()).unwrap(), 64);
        assert!(!dir.path().join(TMP_NAME).exists());
    }

    #[test]
    fn file_id_ceiling_saturates_and_exhaustion_is_refused() {
        let dir = tempdir().unwrap();
        assert_eq!(
            FileIdAllocator::open(dir.path(), u32::MAX - 10)
                .unwrap()
                .allocate()
                .unwrap(),
            u32::MAX - 9
        );
        assert_eq!(read(dir.path()).unwrap(), u32::MAX - 1);
        write(dir.path(), u32::MAX - 1).unwrap();
        let mut ids = FileIdAllocator::open(dir.path(), 0).unwrap();
        assert_eq!(ids.next(), u32::MAX);
        assert!(matches!(ids.allocate(), Err(DbError::Client(_))));
        assert_eq!(read(dir.path()).unwrap(), u32::MAX - 1);
    }

    #[test]
    fn file_id_corrupt_marker_is_rejected() {
        let dir = tempdir().unwrap();
        fs::write(dir.path().join(FILE_NAME), b"garbage").unwrap();
        assert!(matches!(
            FileIdAllocator::open(dir.path(), 0),
            Err(DbError::FormatMismatch(_))
        ));
    }
}