Generic algorithms on top of redb database

Hi, I need help with implementing some generic algorithms on top of redb database tables.

I have a redb database with 2 tables (but there will be more) and I need to be able to use the same algorithms on all tables.

Each redb table has wrapper struct implemented - NodeTable and FWUStateTable. To allow generic programming of the algorithms, I declared a few traits - TableOps, DatabaseTable, TableKey - and tried to implement the algorithms as TableOps functions.

But after 3 days, I still can't get generic types and lifetimes right, there is simply too much of them and they don't play together.

Subjectively there is also too many bounds defined on trait TableOps, and I suspect I do something totally wrong.

Could someone look at the repo here:

and give me some advice?

I'm a quite new to rust....

Thanks!

It'll be easier for people to see where to start if you post the errors you're receiving (cargo check output; not IDE screenshots) and the nearest code involved.

1 Like

Error messages vary a lot - it depends what "fixes" I try.

For current code it looks like:

error[E0597]: `rec_key` does not live long enough
   --> ptnet-mgrd/src/database/algo.rs:97:38
    |
97  |                         if table.get(&rec_key)?.is_some() {
    |                            ----------^^^^^^^^-
    |                            |         |
    |                            |         borrowed value does not live long enough
    |                            argument requires that `rec_key` is borrowed for `'static`
...
134 |     }
    |     - `rec_key` dropped here while still borrowed

error[E0597]: `rec_key` does not live long enough
   --> ptnet-mgrd/src/database/algo.rs:105:38
    |
105 |                         if table.get(&rec_key)?.is_none() {
    |                            ----------^^^^^^^^-
    |                            |         |
    |                            |         borrowed value does not live long enough
    |                            argument requires that `rec_key` is borrowed for `'static`
...
125 |             }
    |             - `rec_key` dropped here while still borrowed

error[E0597]: `rec_cbor` does not live long enough
   --> ptnet-mgrd/src/database/algo.rs:116:33
    |
116 |                 let rec_bytes = rec_cbor.as_slice();
    |                                 ^^^^^^^^^^^^^^^^^^^ borrowed value does not live long enough
117 |                 let prev_rec = table.insert(*rec.table_key(), rec_bytes)?;
    |                                ----------------------------------------- argument requires that `rec_cbor` is borrowed for `'static`
...
125 |             }
    |             - `rec_cbor` dropped here while still borrowed

But what's more important - I don't know if approach taken is sound.

If you look here:

You can see many ugly trait bounds - just too many for my taste.
I think I'm doing something absolutely wrong - could someone more experienced give me some guidance?

Thanks

I'm not sure exactly what's going on โ€” I'm not familiar with redb, and your code is quite complex โ€” but the problem here is almost certainly that you are overusing references where you should be using owned values. For example,

impl<'a> DatabaseTable<redb::TableDefinition<'static, &'static NodeAddress, &'static RawValue>> for NodeTable<'a> {

You're declaring the key and value to be &'static references. &'static references are either compile-time or leaked data. You almost certainly should have owned values instead of references there โ€” so that your database table can own its data!

impl<'a> DatabaseTable<redb::TableDefinition<'static, NodeAddress, RawValue>>  for NodeTable<'a> {

Now, this can't be responsible for the error message you posted, since this is not part of the trait declaration, but I think that you need to go through your codebase and think hard about whether each thing needs to be a reference, and about whether some lifetime needs to be 'static. Making a reference 'static is almost never what you want except when you're working with, for example, strings known to be string literals.

Another thing that can help is to try defining plain functions before you make them into extension traits. That is, write fn x_update_many() without making it part of a TableOps trait. Get that working first.

1 Like

I took a look at this but didn't get as far as untangling it.

Well...

It's probably that one of these

    for<'t> &'t Key: std::borrow::Borrow<<&'t Key as redb::RedbValue>::SelfType<'t>>,
    for<'t> Key: std::borrow::Borrow<<&'t Key as redb::RedbValue>::SelfType<'t>>,
    for<'t> &'t [u8]: std::borrow::Borrow<<&'t Value as redb::RedbValue>::SelfType<'t>>

is causing the compiler to think it needs to borrow things for &'static, but that's beside the point of this reply.


There are indeed just too many trait bounds with nastily tangled lifetimes. Even if you got it to compile, it's not maintainable. If I saw something like this that I had to work with, I'd throw it out and write the concrete implementations that I needed instead, if at all feasible.

It's probably at least partially the fault of the redb crate (self described as beta quality), which is trying to be zero-copy and has quite a lot of complicated constraints on its own.

2 Likes

Prelude: This isn't anything I would expect someone starting out with Rust to be able to unravel or even follow easily. I feel the rebd API is designed in such a way that it is a challenging crate to use while learning (or just generally).

Below I get something to work but I'm not sure if it's of any use to you. The only thing it can work with is when the Value is &'static [u8] and when the Key is not a reference (or other lifetime carrying data structure).


OK, let me take another shot at working through this, without trying to maintain your current signatures. The first thing I see is that here:

pub trait TableOps<'a,Key,Value,Record: Clone> {
    fn x_update_many<'t,T>(&self, it: T, mode: UpdateMode) -> Result<(), Box<dyn std::error::Error>>
    where
        T: Iterator<Item = &'t Record> + Clone,
        Record: 't;

You're not using 'a at all in the trait, which is code smell. You use it as a bound in your blanket implementation:

    for<'t> T: DatabaseTable<redb::TableDefinition<'a, &'t Key, &'t Value>,Record=Record>,

And probably you added it due to some misleading compilier "help" (I saw it in passing but I'm not going to bother trying to recreate it). But if you click the source in the docs, you can see it's just a name. Nothing important and nothing worth creating fits in your code by adding an (invariant!) trait lifetime parameter.

So let's get rid of 'a on this trait.


The next step is to work with Key and Value instead of &Key and &Value instead of Key and Value. Type parameters can resolve to references if they need to.

After doing this and trimming the trait bounds down to something that looked reasonable, I was here:

impl<'a, T, Key, Value, Record> TableOps<Key, Value, Record> for T
where
    T: DatabaseTable<redb::TableDefinition<'a, Key, Value>, Record=Record>,
    Key: redb::RedbKey + 'static,
    Value: redb::RedbValue + 'static,
    Record: Serialize + Clone + TableKey<Key>,

and all the errors looked roughly like so:

error[E0277]: the trait bound `&Key: Borrow<<Key as RedbValue>::SelfType<'_>>` is not satisfied
   --> src/main.rs:155:45
    |
155 |                 let prev_rec = table.insert(rec_key, rec_bytes)?;
    |                                      ------ ^^^^^^^ the trait `Borrow<<Key as RedbValue>::SelfType<'_>>` is not implemented for `&Key`
    |                                      |
    |                                      required by a bound introduced by this call
    |
note: required by a bound in `Table::<'db, 'txn, K, V>::insert`
   --> src/main.rs:23:23
    |
21  |         pub fn insert<'a>(
    |                ------ required by a bound in this associated function
22  |             &mut self,
23  |             key: impl Borrow<K::SelfType<'a>>,
    |                       ^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `Table::<'db, 'txn, K, V>::insert`
help: consider extending the `where` clause, but there might be an alternative better way to express this requirement
    |
114 |     Record: Serialize + Clone + TableKey<Key>, &Key: Borrow<<Key as RedbValue>::SelfType<'_>>
    |                                              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

error[E0277]: the trait bound `&[u8]: Borrow<<Value as RedbValue>::SelfType<'_>>` is not satisfied
   --> src/main.rs:155:54
    |
155 |                 let prev_rec = table.insert(rec_key, rec_bytes)?;
    |                                      ------          ^^^^^^^^^ the trait `Borrow<<Value as RedbValue>::SelfType<'_>>` is not implemented for `&[u8]`
    |                                      |
    |                                      required by a bound introduced by this call
    |
note: required by a bound in `Table::<'db, 'txn, K, V>::insert`

Alright, let's look at this SelfType<'_> thing. From the docs:

SelfType<โ€™a> must be the same type as Self with all lifetimes replaced with โ€™a
[...]

impl RedbValue for &str {
    type SelfType<'a> = &'a str where Self: 'a;
}
impl RedbValue for f32 {
    type SelfType<'a> = f32 where Self: 'a;
}

So basically they're trying to abstract over something being borrowed or owned here. Then they use it in bounds like so:

pub fn get<'a>(&self, key: impl Borrow<K::SelfType<'a>>) -> Result<Option<AccessGuard<'_, V>>, Error>
    where K: 'a,

pub fn insert<'a>(
    &mut self,
    key: impl Borrow<K::SelfType<'a>>,
    value: impl Borrow<V::SelfType<'a>>
) -> Result<Option<AccessGuard<'_, V>>, Error>
where
    K: 'a,
    V: 'a,

Well, I think this is a pretty gnarly interface. Let's compare it to something a bit more typical:

pub fn get<Q>(&self, key: &Q) -> Option<&V>
where
    K: Borrow<Q> + Ord,
    Q: Ord + ?Sized,

And I'll note the implementations of Borrow that really matter:

// We'll be looking at these later too
impl<T: ?Sized> Borrow<T> for  T // owned-borrow
impl<T: ?Sized> Borrow<T> for &T // borrowed-borrow

So what do they gain by going through SelfType<'a>? Well, let's say K = &'static str. Then the relevant implementers of Borrow<&'static str> are &'static str and &&'static str. I didn't see their reasoning in the documentation, but I can only surmise that they wanted to also allow &'short str (and &&'short str). More technically, they wanted a covariant version of Borrow.

As it turns out, this is a tricky interface to work with generically.

Sidebar

Another difference is that they're not explicitly taking a reference like so:

pub fn get<'a>(&self, key: &impl Borrow<K::SelfType<'a>>) -> ...
//                         ^

But given the bounds, the only way they can use key here is to take a reference. There's no reason to pass an owned value here! This is the same misstep which is lamentably common with AsRef<str> and AsRef<Path> (even in, or perhaps more accurately due to, the standard library):

fn foo<P: AsRef<Path>>(path: P) { let path = path.as_ref(); ... }

You can pass a PathBuf to this function, and if you do so you might get an error suggesting you clone it because you're giving up ownership. But what you really want to do is pass &path_buf instead. There's no reason to give up ownership or clone. Example.

BTreeMap avoided this with insert, but redb did not.


OK, let's connect that back to how you're trying to use it.

                let rec_key: &Key = rec.table_key(); // <--- (&Key)
                match mode {
                    UpdateMode::MustCreate => {
                        if table.get(rec_key)?.is_some() {
                // ...

                let rec_cbor = Vec::<u8>::new(); // serde_cbor::to_vec(rec)?;
                let rec_bytes = rec_cbor.as_slice(); // <--- (&[u8])
                let prev_rec = table.insert(rec_key, rec_bytes)?;

Your rec_key and rec_bytes are local borrows -- their lifetimes aren't nameable and are not something you can directly put a trait bound on. So from this it seems you do need some sort of higher-ranked bound -- those for<'t> things -- so that you can put a bound on something with an arbitrarily short, unnameable lifetime.

Now, if we slap this on the function, it compiles:

    for<'t> &'t Key: std::borrow::Borrow<Key::SelfType<'t>>,
    for<'t> &'t [u8]: std::borrow::Borrow<Value::SelfType<'t>>,

But I'm fairly certain this won't actually work when you try to use it. Let's say Key is f32 -- what are we saying? SelfType<'t> is f32, so:

for<'t> &'t f32: Borrow<f32>

Well, that works (borrowed-borrow). But what if Key is &'s str, where SelfType<'t> is &'t str?

for<'t> &'t &'s str: Borrow<&'t str>

That doesn't work! &'t &'s str implements Borrow<&'s str>, not Borrow<&'t str>.

And similarly, the &[u8] bound can never hold. So we need to change something for this to be usable.


Now what? The Key portion can work sometimes (e.g. f32), so let's ignore that for a minute. For &[u8], you could actually do this:

    for<'u, 't> &'u &'t [u8]: std::borrow::Borrow<Value::SelfType<'t>>,
// ...
                let prev_rec = table.insert(rec_key, &rec_bytes)?;
//                                                   ^

And now the lifetimes are in the right spot when Value is &'x [u8]:

for<'u, 't> &'u &'t [u8]: Borrow<&'t [u8]> // Yep!  borrowed-borrow

But now is a good time to remember the documentation on SelfType: aside from lifetimes, it must be the same as the implementor of RebdValue. So this whole thing can only work with Value = &'x [u8] for some 'x. And because of the 'static constraint on TableDefinition, that 'x must actually be 'static.

So this is what we actually have at this point:

impl<'a, T, Key, Record> TableOps<Key, &'static [u8], Record> for T
where
    T: DatabaseTable<redb::TableDefinition<'a, Key, &'static [u8]>, Record=Record>,
    Key: redb::RedbKey + 'static,
    Record: Serialize + Clone + TableKey<Key>,
    for<'t> &'t Key: std::borrow::Borrow<Key::SelfType<'t>>,

Spoilers: This is as far as I got, the rest of this post explores a dead-end.


Let's return to Key now. The bound we have works for all lifetime-less Keys, and maybe that's good enough? But perhaps it's not. Can we make it work with Key: &'static str for example, without making it less generic?

The for<'u, 't> we used for &[u8] only worked because we knew we were dealing with a reference. When we're dealing with Key = &'static str, the reference/lifetime is "hidden" in the generic and there's no way to write the same bound where the &str lifetime varies with 't (even though it's always 'static in Key). We need another way.

Ah, but -- we still have Key: 'static. So for any Key, we have Key = Key::SelfType<'static>. So this could work in place of the higher-ranked bound, as the compiler will understand that &Key: Borrow<SelfType::<'static>> because &Key: Borrow<Key> and those are the same thing. (Basically we are indirectly using the more typical pattern of Borrow.)

    Key: redb::RedbKey<SelfType::<'static> = Key> + 'static,
    // Or alternatively
    // for<'t> &'t Key: std::borrow::Borrow<Key::SelfType<'static>>,

But it doesn't work. Now what? Well, insert requires that the lifetime chosen is the same for both the key and the value. The bound we just added forces it to use 'static for that lifetime, which in turn forces your slice of bytes to be &'static [u8]. So this can't work either, without changing redb to use distinct lifetimes.

The bound does work for the key like we wanted wanted, but bites us elsewhere. You actually do need the covariant version of Borrow for the value portion of insert here.

At this point I give up on making Key more flexible.

OK, one more note. If it's plausiable to change your TableKey trait:

pub trait TableKey<K> {
    fn table_key<'k>(&self) -> &K::SelfType<'k>
    where
        K: redb::RedbKey + 'k;
}

Then you don't need the Borrow bound.

quinedot thank you for your analysis, it shed light into places where I was totally lost.

It definitelly looks like it's quite hard to write abstractions over redb interface.

I'm going to give it next try based on your input.

Thanks!

Got it .... :joy:

Trick was not to fight redb, but implement RedbKey+RedbValue for Key type and RedbValue for Value type.

By doing this, I got rid of all those &[u8] references and their lifetimes.

Will polish it some more, push to github.

In the end it turned out to be quite elegant :slight_smile:

Thanks for all help!

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.