Hi! I'm trying to use nebari storage in a very simple mode to keep a metrics data for a minute per key. my simple demo:

pub fn nebari_test() -> Result<(), anyhow::Error> {
    let path = "db.nebari";
    std::fs::remove_file(path);
    let state = nebari::tree::State::default();
    let context = nebari::Context::default();
    let mut tree = nebari::tree::TreeFile::<nebari::tree::Unversioned, nebari::io::fs::StdFile>::write(path, state, &context, None)?;
    
    let value = [0u8; 0].to_vec();
    
    let mut keys_count = 0;
    let mut keys_size = 0;
    let mut values_size = 0;
    
    let now = std::time::Instant::now();
    for hour in 0..24 {
        for minute in 0..60 {
            for metric in 0..50 {
                let metric = format!("metric_{metric}");
                let key = format!("{metric}:h{hour}:m{minute}");
                keys_size += key.as_bytes().len();
                values_size += value.len();
                tree.set(None, key, value.clone());
                keys_count += 1;
            }
        }
    }
    tree.commit();
    println!("elapsed:        {}s", now.elapsed().as_secs());
    println!("keys_count:     {}", keys_count);
    println!("keys_size:      {}", keys_size);
    use std::os::unix::fs::MetadataExt;
    let meta = std::path::Path::new(path).metadata()?;
    println!("file size:      {}", meta.size());
    Ok(())
}

On my macbook arm64 M1 Pro, nebari = "0.3.1" i have this result:

elapsed:        372s
keys_count:     72_000
keys_size:      1_167_600
file size:      4_961_529_211

After compacting the file size is ~2.8Мб, but compact consumes mut self, i can't compact tree every insert. I'm looking an embedded rust database for IoT devices with sdcard storage and 64Mb RAM. Nebari looks like a good solution, but why is it so slowly and the db file so huge? Could this be incorrect behavior?

for example, this test on another databases:

db          time       size
nebari      372s       4_961_529_211 bytes, 2_886_779 bytes after compacting
sled        17s       ~4_718_592 bytes
rocksdb     0.577s    ~2_752_134 bytes
jammdb      1.511s     8_912_896 bytes
siamesedb   4.311s    ~140Мб

We should add the ability to add extra stats to the BTree nodes. This would allow BonsaiDb and other consumers to latch onto the internal map/reduce functionality. For BonsaiDb, it would allow for multi-level view reduction that follows the tree, rather than the single-level cache that is currently implemented.

For this to work, Root will need to have ReducedIndex, and we will need to expose the serialization APIs.

Currently, the StdFileManager will keep files open forever, except for after a compaction process happens. This works fine for small setups, but in BonsaiDb, we want to support the thousands of databases without any issues.

We need to:

• Investigate raising the open file limit automatically
• Switch to an LRU cache for the open files in the StdFileManager, both readers and writers. Try to come up with a way to ensure that if we end up with many readers for a single file that we can expire individual readers in the cache.

Add the ability to compact a database in-place:

• Begin copying all live data from the existing file into a new database.
• Once caught up, use file renames to atomically swap the new file in place.
• Ensure that all existing readers/writers are closed so that new access will open the new file.

Once done, update the benchmarks to have all get-like benchmarks show off fragmented and compacted performance.

The violin charts start getting a bit useless when there are too many results to present, so I think we should split the groups from simply "gets" and "inserts" to:

• get-[random/sequential]/[engine]/[dataset size]: single record lookup by primary key. The benchmark argument will be the dataset size.
• get_multiple-[dataset size]-[random/sequential]/[engine]/[query size]: multi-record lookup by primary key. The benchmark argument will be the number of records requested in each iteration.
• insert-[random/sequential]/[engine]/[transaction size]: Insert transactions with transaction size records over and over. Each iteration adds to the existing database, but the database should be cleared at the start of the benchmark group.

Additionally, we should benchmark scan.

Refs #50

This implements our first fuzzer. It replicates the process that the bulik_compare_swap created, but in such a way that the fuzzer provides the batches. After a couple of hours across 8 cores, the fuzzer found a new bug. After fixing that bug (will be pushed in next commit to main), the fuzzer then ran for another 6 hours with no additional crashes. I'll be continuing to run it for the next day or two.

I'm not closing #50 because another fuzzer should be written that executes a wide variety of operations in a sequential manner. This test focuses on batching because that's where I discovered a bug this weekend. It would be nice to have some fuzzing validation against the remaining operations -- and it can be less restrictive due to not needing to be batched.

This commit also temporarily changes a few debug_asserts into asserts. This will be addressed in a follow up commit.

After optimizing count() in Bonsai after adding reduce() here, I looked at storing the view reductions in Nebari's indexes ( khonsulabs/bonsaidb#76). I realized that for BonsaiDb to be able to use a View's reduce function, the Reducer needs a self that can store the view.

The problem is, where does the reducer get instantiated and stored? Or is it better to refactor the reducer to be the Root itself?

Refs khonsulabs/bonsaidb#169

This introduces the AnyFile and AnyFileManager types which allow selecting whether to use MemoryFiles or StdFiles at runtime.

The last major feature for BonsaiDb that we need is to consume the new features implemented in #19 and #21 is the ability to compute a reduced value over a partial scan of a tree. Originally when implementing the underlying features, I envisioned "reduce" being a BonsaiDb views feature, not something that Nebari itself would offer. However, upon more thought, it definitely would be a great feature to have in this crate.

The API should look something like this:

impl TreeFile {
    fn reduce<R: RangeBounds<Buffer>>(&self, range: Buffer) -> Root::ReducedIndex {}
}

That signature is pseudo-code, and probably requires additional parameters.

Scanning a tree should offer a callback for each interior node that presents the index and an option of whether to scan the node or not.

This will enable BonsaiDb to query the "reduced" index values, and skip diving into the children nodes when a node is fully included.

BonsaiDb will want to have some files that are unencrypted purely for speed. The Vault for Roots will likely need to be None, and while accessing trees, the TreeRoot will need a way to have its own Vault to override whatever was set on the Roots level.

• [ ] transaction log caching needs to be replaced with LRUs
• [ ] When removing or overwriting an existing value, the GrainId of the value needs to be freed.
• [ ] Checkpointing needs to be updated to ensure readers will never have their "read" state freed. Currently Roots doesn't checkpoint at all, an TreeFile auto-checkpoints when not transactional.

Nebari should expand it's testing suite to include fuzz testing.

Personally I don't have any experience with it, but some pointers here:

• cargo-fuzz is commonly used for this task, their book is presumably a good introduction.
• Beyond the Borrow Checker: Differential Fuzzing is a blog-post/tutorial I stumbled on a while ago about fuzz testing in Rust that I liked.
• bolero is a front-end that might be easier to use then cargo-fuzz, they also have a book.

From Discord, @rrichardson discovered that the MemoryFile implementation is incredibly slower than the real-file based implementation, at least when consumed from BonsaiDb -- on the order of magnitude of 10 minutes vs 6 seconds for a particular importing operation.

Currently, TreeFiles store blobs/chunks in the same file that nodes are written to. When compacting a database, all of the blobs that are alive must be transferred to the new file.

Over time, this is a lot of wasted IOPS if your application is never deleting data. In this day and age, a common way to operate is to "store everything" and only delete once it becomes a problem.

The main idea of this issue is simple:

• Change all of the tree file operations to use a new trait ChunkStorage to write non-node chunks. This may require adding a new parameter to each operation.
• Allow specifying a ChunkStorage implementation when creating a TreeFile/Roots instance.
• If no ChunkStorage is specified, chunks should be written in-line like they are today.
• The ChunkStorage implementation can use 63 bits of information to note where the chunk is stored. The 64th bit will be used by Nebari to note that the chunk is stored externally.

The hard part will be compaction. Nebari doesn't keep track of chunks. The way compaction works currently is data is copied when its referenced, otherwise its skipped. To achieve the goal of "not rewriting everything", the ChunkStorage implementation needs to receive enough information to be able to determine on its own how to compact itself, or opt not to. At this time, I'm not sure of a good way to solve this.

More intelligent compaction can be achieved by using TreeFile to implement ChunkStorage. While this causes extra overhead, the TreeFile could return unique "chunk IDs" that are stable, but the actual location on disk can be moved around. This is where the idea of "tiered" storage comes in, as this TreeFile could do many things including:

• Embed statistics about read frequency of each key, allowing compaction to group frequently used data closer together, or moving infrequently accessed keys to slower storage.
• Subdivide storage into segments that can be defragmented independently.

• #35
• #40
• Consider allowing larger transaction payloads
• Add atomic upgrade
  • TransactionLog should expose a new error when the log format is the old format.
  • TransactionLog::repair should be added to rewrite transaction log to new file using new format, atomic swap to overwrite.
  • Add unit test upgrading an existing log file to the new format. Ensure testing one that contains out-of-order log entries.