2 hashmap references in ExpirableHashMap

Hi everyone,
I'm trying to create a fast expirable hashmap that performs a proactive removal of entries that expire. My idea was to encapsulate each value within an ExpirableEntry and have all the details that I need for the expiration there. Something like that:

struct ExpirableEntry<K, V> {
    key: K,
    pub value: V,
    timer: Timer,
    hashmap_ref: Weak<RefCell<HashMap<K, ExpirableEntry<K, V>>>>
}

pub struct ExpirableHashMap<K, V> {
    hashmap: Rc<RefCell<HashMap<K, ExpirableEntry<K, V>>>>
}

Timer takes care of calling a callback after a period of time with some arguments. So it will call a removal callback with the entry as an argument when expired. Something like this:

fn handle_entry_expiry<K, V>(entry: &ExpirableEntry<K, V>) 
where K: Hash + Eq,
{
    entry.hashmap_ref.borrow_mut().remove(&entry.key);
}

The thing is, as you can see the plan involves pointing from each value in the hashmap to the hashmap itself and I can't get it compile. My approach was to wrap the hashmap with Rc and clone it for every new pushed item, but I keep getting borrow errors or cannot return value referencing temporary value when trying to implement get for the for the ExpirableHashMap .

I'm new to Rust so I wonder if I chose the correct approach with this one and I fail on technicalities or I better use something completely different for this. Has anyone did something similar?

I would recommend you try some sort of approach where you only store a single Timer that you put in the ExpirableHashMap, and that this timer would then be able to remove the appropriate items. You can store the items in sorted order by expiry time using a BinaryHeap.

In general, callbacks work pretty poorly in Rust because Rust encourages single-ownership, and callbacks violate that.

I thought about that approach, the problem with that is I'm planning to have a lot of expirable hash maps, which means I will have to call cleanup for all of them every cycle, right?

You could use another BinaryHeap to keep track of when each map next has a key that expires. You may be able to find some inspiration in the mini-redis project, which also has a shared hash map with keys that expire. You can find its hash map implementation in src/db.rs.

1 Like

Ok, but that BinaryHeap will have to have reference to all maps, right? Wouldn't it mean that every key get will have to be done through it?

I would definitely not put references into the BinaryHeap. Either put the actual maps inside it, or use some sort of id.

2 Likes

I see, good idea. But I'm afraid it will require to perform extra actions for every lookup I will need to perform, no? If I understood it correctly, I will need to first fetch the hashmap from the BinaryHeap and then run another lookup.
Also, do you think it will be possible to use that approach if I'll have many key-value types?

You can avoid the extra lookup by storing some sort of ID instead.

Would it allow me to have different value types for each hashmap?

I'm sure you could make that work.

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.