Simple test case:

#[test]
fn iter_column_while() {
    for n in 0..10000 {
        let dir = tempfile::TempDir::new().unwrap();
        let options = parity_db::Options::with_columns(dir.path(), 1);
        let db = parity_db::Db::open_or_create(&options).unwrap();

        let keys = vec![[0u8; 32], [1u8; 32], [2u8; 32], [3u8; 32], [4u8; 32]];

        let tx = keys.iter().map(|key| (0, key, Some(key.to_vec())));
        db.commit(tx).unwrap();

        for key in &keys {
            assert!(db.get(0, key).unwrap().is_some());
        }

        let mut keys_count = 0;
        db.iter_column_while(0, |_iter_state| {
            keys_count += 1;

            true
        })
            .unwrap();

        assert_eq!(keys_count, 5, "iteration {}", n);
    }
}

Fails with error like this:

---- object_mappings::tests::iter_column_while stdout ----
---- object_mappings::tests::iter_column_while stdout ----
thread 'object_mappings::tests::iter_column_while' panicked at 'assertion failed: `(left == right)`
  left: `4`,
 right: `5`: iteration 29', crates/subspace-farmer/src/object_mappings/tests.rs:152:9

Number of elements read can vary, for instance with these 5 keys, hashing disabled and salt set to zero iterator returns no elements at all:

0061277d94811d9d65f82e9d267ae62a00219382f109cb4ca806ee0f9d6c2eb5
0061277d94811d9d65f82e9d267ae62a00219382f109cb4ca806ee0f9d6c2eb8
0061277d94811d9d65f82e9d267ae62a00219382f109cb4ca806ee0f9d6c2eba
0061277d94811d9d65f82e9d267ae62a00219382f109cb4ca806ee0f9d6c2ebb
0061277d94811d9d65f82e9d267ae62a00219382f109cb4ca806ee0f9d6c2ece

If I change the configuration for a column from default (btree_index = false) to btree_index = true and the db already existed, will it automatically index that column when I open the db?

This pr adds possibility to go back with btree iterator.

Reviewing by commits would make more sense, as the first two ones are minor refactoring. The rest of commits propagate reverse iterator from bottom to the top.

There are some minor problems with this code though. It repeats itself a lot, because I started of with just negating invariants of next function. Also, there is clearly not enough of tests for that, will add them soon.

Here is one of our users reporting getting "Corruption: Missing btree entry at addr 45:61327" on ParityDb database. Keys and values are both 8 bytes in in one column and one 11 byte key with 8 bytes value in second column.

I suspect application was killed due to shutting down slowly by systemd, which is the type of interruption ParityDb claims to be handling:

Database is restored to consistent state if IO is interrupted at any point.

I don't have much more details at the moment, but I hope this is helpful.

This PR contains my initial indexing code. I create a draft PR as things starts to work properly and I am looking a bit more at the performances, but welcome initial feedback. The PR is a bit overly complex, but there is some perf/design I wanted to test so I added some abstraction to check that (not done yet).

Also I did use a lot of code from a different branch which explain I started with a separate file for the btree node storage. I wanted constant size node storage, which I am not convinced is interesting: Storage of big key is pretty costy (key is stored with value :(). So storing in value tables (or its own value tables) may end up being better (untested yet).

Also this expose a specific api: one column we can have both hash indexed and btree indexed contents. Specializing column to either hash indexed or btree indexed can be an option too (I could restore some migration optimization then).

• in column I did split write plan, there is still some code from a different branch where locked are used as parameter, not strictly needed. It is very slightly better for not recursively searching index when reindexing, but that is not really relevant.

• there is a race in tests, deadlock sometimes. I think it is from the logic of the db test (see TODO linked pr).

• key as trait is also something from a different branch, it could be replaced by just be an enum, or make specialized table function (for_parts is containing lot of logic).

Main open questions at this point of the PR:

• switch to column specialized for indexed content model?
• switch to variable size nodes stored in value tables?
• switch CommitSet back to something similar to master

Makes fuzzing way more deterministic

Allows a more careful model of which state are already  persisted and which state is not

Does also some refactoring of Db test related API to be able to call them from the fuzzer

First bug uncovered thanks to #113.

When a partial write happens after opening the database with a single BTree the iteration fails on the following db opening with 'range end index 8 out of range for slice of length 0' inside of Entry::read_slice nested in BTreeTable::btree_header.

Reproduction test (requires #113 and the enabeling of the instrumentation feature):

	#[test]
	fn test_from_fuzzer() {
		crate::set_number_of_allowed_io_operations(12);
		let tmp = tempdir().unwrap();
		let mut options = Options::with_columns(tmp.path(), 1);
		options.columns[0].btree_index = true;
		assert!(Db::open_or_create(&options).is_err()); //It's going to fail

		let db = Db::open_or_create(&options).unwrap();
		db.iter(0).unwrap(); //Read is panicking here
	}

Migrating from rocksdb to paritydb (here) I discovered that stack randomly overflows during BTreeIterator::{next, prev} calls.

Seems like rust compiler failed to optimize some recursive functions with no state with TCO (even in release mode). Looks like as all optimizations, TCO is also eventual and is not guaranteed in any way. More on the history of it in the compiler here.

So this pr basically rewrites recursive functions using loops so that we would guarantee that we will reuse memory and won't allocate stack frame.

Better to review pr commit by commit, and for the first one it would be helpful to ignore indentations.

This is a small refactor of iterator logic when switching backward/forward. Mainly removea bit of redundant code and makes that we do not return same value when changing iteration direction.

Currently draft as I need to reread it and clippy it, but @Tpt it may be interesting to run your fuzzer on this branch.

This PR extracts some changes I was using in https://github.com/cheme/parity-db/tree/fifo_and_set tests.

These allow stopping db in a given state to specifically test the commit overlay, log overlay or db file. The tests I added are not very useful for the current code base, but here as an example.

In https://github.com/paritytech/parity-db/commit/72b1e1d856731fac0f9f2520f2756f2019f183fb I did try to use it on the stress tests, but only work for small number of commit (I did not debug thoroughly as this was a bit expected from the way it is implemented). Not sure it is really useful to have (it did help me, but can be kept outside of master, same thing for the pr actually).

I'm trying to follow https://substrate.dev/docs/en/tutorials/create-your-first-substrate-chain/setup

but my build fails with:

$ cargo build --release
error: failed to download `parity-db v0.2.3`

Caused by:
  unable to get packages from source

Caused by:
  failed to parse manifest at `/home/bear/.cargo/registry/src/github.com-1ecc6299db9ec823/parity-db-0.2.3/Cargo.toml`

Caused by:
  failed to parse the version requirement `0.11	` for dependency `parking_lot`

Caused by:
  expected comma after minor version number, found '\t'

I downloaded parity-db==0.2.3 via cargo-download and found that Cargo.toml indeed has an extra \t on the parking_lot declaration:

# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
#
# When uploading crates to the registry Cargo will automatically
# "normalize" Cargo.toml files for maximal compatibility
# with all versions of Cargo and also rewrite `path` dependencies
# to registry (e.g., crates.io) dependencies
#
# If you believe there's an error in this file please file an
# issue against the rust-lang/cargo repository. If you're
# editing this file be aware that the upstream Cargo.toml
# will likely look very different (and much more reasonable)

[package]
edition = "2018"
name = "parity-db"
version = "0.2.3"
authors = ["Parity Technologies <[email protected]>"]
description = "Key-value database for the blockchain"
homepage = "https://substrate.dev"
license = "MIT OR Apache-2.0"
repository = "https://github.com/paritytech/parity-db/"
[profile.release]
lto = "fat"
codegen-units = 1
debug = true
panic = "abort"
[dependencies.blake2-rfc]
version = "0.2.18"

[dependencies.crc32fast]
version = "1.2.0"

[dependencies.fs2]
version = "0.4.3"

[dependencies.hex]
version = "0.4.2"

[dependencies.libc]
version = "0.2"

[dependencies.log]
version = "0.4.8"

[dependencies.memmap2]
version = "0.2"

[dependencies.parking_lot]
version = "0.11\t"

[dependencies.rand]
version = "0.8.2"
[dev-dependencies.env_logger]
version = "0.8.2"

Introduce a second level hash index. This will be used to store smart contract tries, child tries, etc. The main requirement here is that the sub-index can be dropped in amortized constant time.

API requirements: The hash column can be configured to use a second level index. All insert/get commands for such column accept two keys: K1 and K2 where K1 identifies the index, and K2 is the value key in that index. Additionally, there's a drop command that accepts a single key and deletes all values in the index identified by the key.

Implementation ideas are welcome. As far as I see it, the structure could be made similar to existing index with all values in a single index. Deletion could be done by background process, similar to re-indexing. When an index is dropped, it is added to the deletion queue. A background process checks all index entries and deletes any values that are in the indexes being dropped.

Under certain write workloads, when there's a lot of commits with a lot of small value insertions, the memory used by the index overlay can be blown by a factor of 10 or more when compared to the actual data inserted. There's a good example in #93. This is because the overlay keeps the whole index page in memory, even though only a single entry in the page may be modified. I can think of two ways to fix that:

1. Don't keep the whole page, but rather only modified entries.

2. Investigate existing mechanisms in linux to control page flushing for memory mapped files. If it is possible to control when exactly individual pages are flushed to disk, we don't need the overlay in the first place.

In any case, this is only worth fixing if the solution does not introduce any performance hits.

We use for now the GitHub action storage

Choices:

• on PR run for 2mns
• run a weekly fuzzing for 1h every sunday and then minimize artefacts and compute code coverage

Currently the fuzzers only write and read using a single thread and do not control the background threads concurrency. It might be nice to use a tool like loom to properly cover possible concurrency issues.

It should also make the debugging of bugs like #124 easier (no more reproduction issues).

After switching from rocksdb to parity db we discovered high memory usage on system allocator:

| | system | jemalloc | |-------|--------|----------| | btree | 5.93G | 4.34G | | kv | 7.27G | 5.49G |

Here is the code for reproducing the issue:

#[global_allocator]
static ALLOC: jemallocator::Jemalloc = jemallocator::Jemalloc;

fn main() {
    let batch_size = 1024 * 1024;
    let handles = (0..4)
        .map(|i| {
            let p = format!("some-path/{i}");
            let _ = std::fs::remove_dir_all(&p);
            let opts = parity_db::Options {
                path: p.into(),
                columns: vec![parity_db::ColumnOptions {
                    preimage: false,
                    btree_index: true,
                    uniform: false,
                    ref_counted: false,
                    compression: parity_db::CompressionType::NoCompression,
                    compression_threshold: 4096,
                }],
                sync_wal: true,
                sync_data: true,
                stats: false,
                salt: None,
            };
            std::thread::spawn(move || {
                let db = parity_db::Db::open_or_create(&opts).unwrap();

                for range in (0..100u64).map(|i| i * batch_size..(i + 1) * batch_size) {
                    db.commit(range.map(|i| (0, i.to_be_bytes(), Some(i.to_le_bytes().to_vec()))))
                        .unwrap();
                }
            })
        })
        .collect::<Vec<_>>();
    for handle in handles {
        handle.join().unwrap();
    }
}