holt 0.2.1

An adaptive-radix-tree metadata storage engine for path-shaped keys, with per-blob concurrency and crash-safe persistence.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

//! `filesystem_meta` — holt as the inode table of a toy POSIX
//! filesystem. Keys are absolute paths; values are 32-byte packed
//! inodes (size + mtime + mode + uid + gid + nlink).
//!
//! Demonstrates the workload holt was built for: short
//! hierarchical keys, fixed-size values, dense per-prefix
//! density, point-lookup + atomic rename.

use holt::TreeBuilder;

/// 32 bytes — the shape the criterion `fs` bench also models.
#[repr(C, packed)]
#[derive(Debug, Clone, Copy)]
struct Inode {
    size: u64,
    mtime: u64,
    mode: u32,
    uid: u32,
    gid: u32,
    nlink: u32,
}

impl Inode {
    fn to_bytes(self) -> [u8; 32] {
        // SAFETY: `#[repr(C, packed)]` over plain integer fields
        // gives a stable 32-byte layout matching the bench's
        // `fs-metadata` scenario.
        unsafe { std::mem::transmute(self) }
    }

    fn from_bytes(b: &[u8]) -> Self {
        assert_eq!(b.len(), 32, "inode is 32 bytes");
        let mut buf = [0u8; 32];
        buf.copy_from_slice(b);
        // SAFETY: same shape as `to_bytes`.
        unsafe { std::mem::transmute(buf) }
    }
}

fn main() {
    println!("=== holt filesystem_meta example ===\n");

    // In-memory for the example so it doesn't litter cwd.
    let tree = TreeBuilder::new("scratch").memory().open().expect("open");

    // Populate a small directory tree.
    let now: u64 = 1_715_817_600;
    let entries: &[(&[u8], Inode)] = &[
        (
            b"/home/alice/notes.txt",
            Inode {
                size: 1024,
                mtime: now,
                mode: 0o644,
                uid: 1000,
                gid: 1000,
                nlink: 1,
            },
        ),
        (
            b"/home/alice/photos/sunset.jpg",
            Inode {
                size: 2_345_678,
                mtime: now - 3600,
                mode: 0o644,
                uid: 1000,
                gid: 1000,
                nlink: 1,
            },
        ),
        (
            b"/home/bob/.bashrc",
            Inode {
                size: 412,
                mtime: now - 86_400,
                mode: 0o600,
                uid: 1001,
                gid: 1001,
                nlink: 1,
            },
        ),
        (
            b"/etc/passwd",
            Inode {
                size: 2_048,
                mtime: now - 7 * 86_400,
                mode: 0o644,
                uid: 0,
                gid: 0,
                nlink: 1,
            },
        ),
    ];
    for (path, inode) in entries {
        tree.put(path, &inode.to_bytes()).unwrap();
    }
    println!("loaded {} inodes\n", entries.len());

    // Stat-style lookup.
    let path: &[u8] = b"/home/alice/photos/sunset.jpg";
    let bytes = tree.get(path).unwrap().expect("present");
    let i = Inode::from_bytes(&bytes);
    let size = i.size;
    let mode = i.mode;
    let nlink = i.nlink;
    println!(
        "stat {:?} -> size={size} mode={mode:o} nlink={nlink}",
        std::str::from_utf8(path).unwrap(),
    );

    // Atomic rename — `force=false` errors out if the destination
    // already exists (POSIX `rename(2)` allows overwrite, so a
    // real syscall layer would pass `true`).
    tree.rename(
        b"/home/alice/photos/sunset.jpg",
        b"/home/alice/photos/sunset-archived.jpg",
        false,
    )
    .unwrap();
    assert!(tree
        .get(b"/home/alice/photos/sunset.jpg")
        .unwrap()
        .is_none());
    assert!(tree
        .get(b"/home/alice/photos/sunset-archived.jpg")
        .unwrap()
        .is_some());
    println!("renamed: original path gone, new path present");

    // unlink.
    let prev = tree.delete(b"/home/bob/.bashrc").unwrap();
    println!(
        "unlink /home/bob/.bashrc -> previous {} bytes",
        prev.map(|v| v.len()).unwrap_or(0),
    );

    // Force durability on a persistent tree (no-op on memory).
    tree.checkpoint().unwrap();

    println!("\ndone");
}