RFC: 1.0 stabilization

[cberner]

I'm planning to release version 1.0 soon, and am looking for feedback on the file format, API, and bug reports!

Please comment here, or file a separate issue if more appropriate. After releasing version 1.0, I'm going to try hard to avoid any file format changes, as putting in upgrade logic would be a maintenance burden.

Please note, I place a high value on keeping the code base simple, so while I'll give every feature suggestion serious consideration, please don't be offended when I (likely) reject it.

[Evrey]

Hey there!

Here’s a few bits and pieces i noticed. Some of them may be interesting enough to be added to v1.

User ID & User Version

How about adding a User ID and User Version to the database header? Stored as (u32, u32). That’s a quite handy SQLite feature i’m using all the time. The User ID is an app-specific magic number. While redb is only bothered with whether or not a file is an actual redb database file, an application is further interested in whether this redb file is also one with a schema and data it actually expects. Further, User Version is embeddable metadata with the intent to version the schema. This is used for automatic schema migrations within the app.

I suggest the following API changes to accomodate this (naming bikesheddable):

impl Database {
  // These two are just wrappers around tiny read transactions.
  fn user_id(&self) -> u32;
  fn user_version(&self) -> u32;

  // Merely reads the two header fields and then compares them against
  // the given parameters.
  fn check_user_metadata(&mut self, expected_id: u32, expected_version: u32)
  -> Result<NeedsMigration, Error>;

  // `steps` is a map of `version → migration`
  // This handy helper function assumes that versions are
  // monotonically incrementing in apps.
  fn migrate_to(&mut self, target_version: u32, steps: &[impl Migration])
  -> Result<(), Error> {
    assert!(target_version < steps.len());
    let user_id = self.user_id();
    
    loop {
      match self.check_user_metadata(user_id, self.user_version())? {
        NeedsMigration::None => return Ok(()),

        NeedsMigration::UpFrom { current_version }
          => if let Some(mig) = steps.get(current_version as usize) {
            let mut wtx = self.begin_write()?;
            wtx.set_durability(Durability::Paranoid);

            mig.up(&wtx, current_version)?;
            wtx.write_user_version(current_version + 1);

            wtx.commit()?;
          }
          else { return Err(Error::NoMigrationForVersion(current_version)); },

        NeedsMigration::DownFrom …
      }
    }
  }
}

enum NeedsMigration {
  None,
    UpFrom { current_version: u32 },
  DownFrom { current_version: u32 },
}

enum Error {
  …
  // Thrown by `check_user_metadata` and `migrate_to`.
  UserIdMismatch(u32),

  // Thrown if the database header’s user version would
  // overflow `steps` in `migrate_to`, i.e. when there is no
  // known migration for the reported version.
  NoMigrationForVersion(u32),
  …
}

impl WriteTransaction {
  // Exclusive access, mainly to prevent migrations from touching these.
  fn write_user_id(&mut self, user_id: u32);
  fn write_user_version(&mut self, user_version: u32);
}

impl ReadTransaction {
  fn user_id(&self) -> u32;
  fn user_version(&self) -> u32;
}

trait Migration {
  // Redundant `current_version` to help catch migration step ordering bugs.
  // `  up` goes `current_version → current_version+1`
  // `down` goes `current_version → current_version−1`
  fn   up(&self, &WriteTransaction, current_version: u32) -> Result<(), Error>;
  fn down(&self, &WriteTransaction, current_version: u32) -> Result<(), Error>;
}

impl<F> Migration for (F, F)
  where F: FnOnce(&WriteTransaction, u32) -> Result<(), Error>
{
  …
}

Table Name Types

I know this would be a very deep-running change, but i’d like to get rid of String for identifying tables. Ideally apps could be generic over table identifiers, with maybe keeping String as a default. I’d prefer identifying tables with a simple enum or maybe a fancy Uuid. Basically anything that is Clone+Eq+Sized.

Now, adding a RedbTableId generic parameter everywhere would just poison all the APIs and add further complications by requiring some kinda table ID type metadata in the DB header that now also has to be checked. But i have an idea for a »best of both worlds« solution:

Change all table names to u128.

Now everything that can be inlined into 16 bytes, or anything that can be hashed into 16 bytes, can be used as a table name. And the database engine can perform much cheaper table look-ups. Here’s pretty much what the user-visible API changes would be:

impl TableDefinition<'db, K, V> {
  pub const fn from_name(name: &str) -> Self {
    // `const fn` hash function required
    Self::from_u128(const_xxH3_128(name))
  }

  #[cfg(feature = "uuid")]
  pub const fn from_uuid(id: uuid::Uuid) -> Self {
    Self::from_u128(id.as_u128())
  }

  // and whatever more…

  // This here is the only strictly necessary function.
  // `from_name` just has to exist to tell developers that yes, it is
  // okay to use strings.
  // `from_uuid` just has to exist to tell developers who like UUID
  // that yes, they can even use UUID if they want to.
  // But they can also just use magic numbers like `0xC01D_C0FFEE`
  // or `as u128` any `#[repr(…)] enum`.
  pub const fn from_u128(id: u128) -> Self;
}

Something similar could happen to TypeName, for in its current design you cannot extract the text name back out of it anyway.

Sessions

Currently, Redb has two slots for active transaction commit slots. I propose adding a region of additional commit slots, each assigned a name. (Ideally, as suggested above, that »name« is a mere u128 internally.)

The idea is to add some kind of session API to the database connection. Here’s what it may look like:

impl Database {
  pub fn create_session(&self, id: u128) -> Result<Session<'_>, Error>;
  pub fn open_session(&self, id: u128) -> Result<Session<'_>, Error>;

  pub fn list_sessions(&self) -> impl Iterator<Item = u128>;
}

impl<'db> Session<'db> {
  // These transactions do not use the commit slots of the super header,
  // but alternative named commit slots.
  pub fn begin_read( &self) -> Result< ReadTransaction<'db>, Error>;
  pub fn begin_write(&self) -> Result<WriteTransaction<'db>, Error>;

  // Overrides the commit slots with the super header commit slots,
  // synchronising this session with the current main database state.
  pub fn pull_from_main(&mut self) -> Result<(), Error>;

  // Overrides the commit slots with the ones of another session.
  pub fn pull_from_session(&mut self, other_id: u128) -> Result<(), Error>;

  // Default on drop is to `save`. Just means the session commit slots
  // are kept on disk.
  pub fn save(self) -> Result<(), Error>;

  // Deletes the session from disk, turning its commit slots into a free
  // page. When scanning for free database pages, pages only pointed
  // at by this session are now also free.
  pub fn delete(self) -> Result<(), Error>;

  // Overrides the super header commit slots by this session’s
  // and also deletes this session.
  pub fn merge_into_main(self) -> Result<(), Error>;

  // Overrides the commit slots of the other session by this one’s,
  // then deletes this one.
  pub fn merge_into_session(self, other_id: u128) -> Result<(), Error>;
}

Why would that be useful? I can see two use-cases.

It would allow applications to selectively preserve some historical state, shall the user wish to. Like drafts of a project you can check out any time. Simply call db.create_session(…)?.save()? and historical data is preserved.

It allows for coarser rollback points when users of an app are expected to perform lots of small changes. Think of hitting Ctrl+S only, like, every 10 minutes in some app, or having an auto-save of 10 minutes. Until the user explicitly »saves«, the current app state is not really considered »done«. However, a user still does not want to lose progress on a sudden app crash.

An app may immediately db.create_session(…)? and start working from there on start. If there were any unsaved changes, then this session already exists and is opened. If the user wishes to discard these changes, the app simply .delete()?s the session and creates a new one, or it pull_from_main()?s for the same effect. When the user explicitly saves, the current session is merge_into_main()?ed. If the user wishes to keep the changes around for now but rather wants to work on the last »done« state, the session is merely save()?d, or alternatively merge_into_session()?ed into a new one followed by pull_from_main()?. db.list_sessions() can be used to automatically clean up old or otherwise no longer needed ones.

Semantically, a Database connection is also a session, just the default unnamed one. Given this, one could remove some API methods by defining that the default session is that of ID 0_u128. Depends on what makes the file format easier to design and on what causes fewer penalties for a sessionless usage scenario.

Error Changes

A bunch of current Error variants provide useless-to-the-app information despite being potentially handlable by said app.

Corrupted & TableTypeMismatch

I suggest completely removing these error variants in favour of these:

struct TableLayout {
  pub table_id  : u128,
  pub   key_type: Type,
  pub value_type: Type,
}
struct Type {
  pub name: TypeName, // Or TypeId or…
  pub align_log2: u8,
  pub byte_size: u32,
}

enum Error {
  …
  LayoutMismatch { expected: TableLayout, actual: TableLayout },
  DowngradeRequired(u8),
  …
}

Push message formatting into a method on that enum, don’t push Strings around. Too often have i had to use regex to extract error recovery information from error messages because error types don’t tell you anything useful. You never know when someone does find that data useful for error recovery.

TableDoesNotExist & TableAlreadyOpen

If the name change happens, then String → u128.

[Zenithsiz]

Hey, I've been recently using redb for a personal project (with more to come using it) and have been throughly enjoying it.

I do have a few suggestions relating to RedbValue, RedbKey and the usage of impl Borrow<...>.

impl Borrow<...>

I believe that accepting a impl Borrow<...> for comparing keys (during non-inserting operations such as get / range / drain / remove) can be very restrictive.

A motivating example is if I have a key of type (T, U) and I want to get all values such that value.0 > t, I still need to supply a U.
If U has a minimum value I can pass in a (Bound::Excluded(t, U::MIN), Bound::Unbounded) and it works. But if U might not have a minimum value, or U::MIN might be expensive to create. (In my personal case, U is Vec<...>, which has a minimum value, but not a maximum)

I'd instead suggest replacing impl Borrow<...> and RedbKey::compare with a Comparable trait (similar to hashbrown::Equivalent):

pub trait Comparable<T: RedbValue>: RedbValue {
    fn compare(this: &[u8], other: &[u8]) -> Ordering;
}

This would allow me to pass in a (T, Wrapper::MIN), where (T, Wrapper): Comparable<(T, U)> implemented in such a way to compare Wrapper::MIN less than all Us.

I think this change wouldn't complicate the code much aside from declaring an extra type parameter on these functions to bound it with Comparable<K> (or the other way around, K: Comparable<...>)

RedbValue

I believe the design of RedbValue is more complicated than it needs to be. I'd suggest moving the lifetimes 'a to the trait itself and removing RedbValue::SelfType. You'd have to remove the RedbValue bounds from types, since they don't have a lifetime associated with them (which I think should be done regardless, see this SO question), and move them only to methods, where you have a 'a declared already.

I think this change would greatly simplify a lot of the bounds in most functions and types.

Final words

I'd actually be interesting in creating PRs for both of these suggestions. If nothing else, just so you can see how it would look like with these implemented, so you could decide whether or not it'd be worth it to make these changes.

[cberner]

@Zenithsiz

impl Borrow<...>

Your Comparable idea is an interesting one! I struggled with what type the parameter to get() and range() should be. There's some background in #452 and #448 . As long as it doesn't complicate the API for the basic case of primitive types, ya I'd be happy to look at a PR if you want to make one. At the moment you can't pass &Vec to a table of &[] which I find annoying -- the tests have to call .as_slice() all over the place, so if it fixed that constraint I'd see it is a big positive. One concern I have is that adding the type parameter to get() and range() might end up requiring users to explicitly annotate it with get::<&str>(...) or the like, but I think that can be avoided.

RedbValue

I'd love to simplify this, but I don't think your idea will work. If the lifetime is moved to the trait, let's call it 'trait_lifetime, then fn from_bytes<'a>(data: &'a [u8]) -> Self::SelfType<'a> will not be able to return the lifetime 'a because the function will need to return Self instead of Self::SelfType which has the lifetime 'trait_lifetime rather than 'a. If you know a way around that I'd love to hear it though!

[cberner]

@Evrey

Thanks for the detailed feedback! Thoughts & questions below:

User ID & User Version

I think this can be achieved by the user creating a table such as Table<(u32, u32), ()> with a single entry storing the user id & user version. Then all that migration functionality can be implemented in the application. Would that cover the same functionality you have mind? If so, I think I'll leave this feature out, as I'm aiming to minimize the API surface area of redb and am mostly modeling it after BtreeMap rather than more complex databases like sqlite.

Table Name Types

Why do you think String should be removed? I haven't benchmarked the difference in lookup cost, but it's almost certainly small. That lookup is only done in open_table (after that it's cached). And having a string allows nicer error messages and list_tables() to be provided.

Sessions

This is an interesting idea, and the coarser rollback points you bring up is similar to the request for persistent savepoints (#574). Would persistent savepoints cover your use case?

Error Changes

Good point! I should revisit all the variants of Error

[cberner]

@Zenithsiz ya, unfortunately I don't think the Comparable approach is going to work, as it will require lots of extra type annotations. See this branch, I made: https://github.com/cberner/redb/tree/comparable If you knkow a way around adding annotations to all the calls into get() lemme know!

The alternative that I would suggest for your use case is to add special values into the serialization format. Like prefix your Vec with a single byte, which is 0 for a normal value in which case it will compare the rest of the byte array, or 1 for the maximum value which is greater than all other Vec. I've done something similar with the multimap data types

[Zenithsiz]

@cberner Hm, I'm not capable of testing it right now, but maybe if instead of fn<Q: RedbComparable<K>>(..., key: impl Borrow<Q>), a fn<Q: RedbComparable<K>>(..., key: &Q) might work, since it removes a double indirection (impl Borrow -> Q -> K) and maybe rustc can then figure it out without type annotations?

Also another possible issue is that in BTree::get(), you get the bytes of Q and pass that on to other functions (e.g. get_helper) that (I assume), then compare them to the database bytes via normal byte comparison, which might not work, since Q doesn't necessarily serialize to a value that's byte-comparable to K. I think this is fixable by making these inner functions aware of <Q as RedbComparable<K>>::compare instead of comparing bytes?

[cberner]

Unfortunately I need the impl Borrow so that you can pass both K and &K

[Zenithsiz]

I was going to suggest implementing RedbComparable for both K and &K, but I don't think you can do that without specialization... I suppose for now it might not work then, unfortunately.

I also played around the idea of simplifying RedbValue, but I was unsuccessful. At a certain point I realized HRTs would be required to transform a T<'a> into T<'b> if not for that T::SelfType<'_> hack.

[cberner]

It used to use HRTBs and the number of hacks required was even worse ;( #366

[cberner]

I changed the Errors in #578

[Evrey]

Hello! =)

Would that cover the same functionality you have mind?

From the perspective of one specific app: Yes.

However, from the perspective of »any random app«, not quite. The neat thing about SQLite’s header-embedded meta data is that any app can make sense of it without knowing anything about the schema. App 1 can reject a .redb file immediately if its »user id« says it’s from App 2, without testing whether a specific table exists and whether that table contains the rows one expects. Additionally, many apps can now build on the same simple building blocks to automate schema verification and migration.

(I forgot, Migrate could also have a fn verify(&self, &ReadTransaction) -> bool where desired.)

I think it’d be helpful to add these as a standardised identification manner, but really it’s a matter of taste. And if you’d rather keep the API down to the absolute basics, then that’s a good enough reason for me to not standardised a »user id« and »user version«.

Would persistent savepoints cover your use case?

They do seem to be pretty much the same thing, so yes. Good to see there’s already an issue open for that. =)

Why do you think String should be removed?

That’s just me being me, which is why that section of my comment was full of »if«s. I come from a perspective where easy to avoid points of failure are preferrably avoided. That includes heap allocations for small pieces of data (e.g. String) everywhere, equality tests that aren’t cheaply consttime, etc. I favour numeric identifiers and resolving numeric IDs only as needed where needed, but it’s not like i would never use redb if it stayed with String. SQLite leans even heavier on allocating Strings everywhere after all. (Though also using specialised allocators for them.)

So to summarise: I think Strings »should« be just the default option out of many possible options. But i’m not making that a hard requirement.

I should revisit all the variants of Error

While at it, it may be worth considering breaking up Error. I know it’s much more annoying to program, for Rust turns that into an absolute boiler plate fest, but i’d love to see a specialised enum Error per fallible function, which has precisely the error variants that function can produce and no more. Then make them all impl Into<Error> to easily bubble up errors from multiple function calls.

SQLite, for example, has like a billion error and status codes, yet individual functions only throw a small subset of them at a time. Sometimes these functions even actually turn out to be infallible, but SQLite didn’t document that, and still had them return status codes. That makes it quite annoying for super diligent error handling and error recovery code, for you paranoidly have to expect everything to happen, even if it seems to make no sense.

I had similar pain working with UEFI crates. You get a lot of _ => unreachable!() or e => Err(e)?, in your error handling that shouldn’t have to exist.

[cberner]

an Error enum per function is an interesting idea. I kind of like that, although it does add some complexity. I'll think that over. Do you have any examples of high profile crates that have taken that approach? I'd be curious to see how it worked out.

[Evrey]

Off the cuff i only know myself doing the per-function error enums in Rust. And i blame that on Rust-the-language making that super tedious and annoying. If you instead look at Zig, there it’s super quick and easy to declare and use error code subsets, and thus Zig programmers do often have per-function error code sets.

[freopen]

I know it's a big stretch at this point, but would be cool to be able to store custom data in branch pages. For example what if each branch contains a value that is equal to f(list_of_children_values) where f() is an associative function that is set at the tree initialization. That allows us to find f(whole_tree) in O(1) time by looking at the root value and f(start_range..end_range) in O(ln(size)) time by a simple recursive algorithm.

Motivational example 1: We store a tree of customers, each customer could create a ticket with a date and a priority, it can close the ticket and change the priority. We want to find the oldest active ticket of the highest priority. Let's store (max_priority, min_timestamp, customer_id) in the branch and f(children) will select the highest priority ticket. Now the root always contains the most urgent ticket.

Motivational example 2: We store an online leaderboard for the game, players are sorted by the max level they achieved, players with the same level are sorted by the date they achieved that level. How can we find a placement for a given player? Let's store (level, date, player_id) -> 1 mapping in the separate tree and let's define f(children) = sum(children). Now the exact place of the player is equal to f(..(player.level, player.date, player.id)).

[cberner]

Interesting idea! Ya, I don't think I'll add that as I think the upside is too small to justify the added complexity. I experimented with B-epsilon trees which are vaguely similar (leaf values buffered in the branch pages), but ultimately decided they weren't worthwhile.