Multithreaded Graph Structure

[lyckligtax]

Hey there,
I'm struggling with interror mutability in an multithreaded environment.

I have a database struct that holds sets of elements which are interconnected for tree traversal:

pub struct Db<GranteeId: Key, ActionId: Key> {
    grantees: HashSet<Grantee<GranteeId, ActionId>>,
    actions: HashSet<Action<ActionId, GranteeId>>,
}

pub struct Grantee<GranteeId: Key, ActionId: Key> {
    pub key: GranteeId,
    interior: Rc<RefCell<GranteeInterior<GranteeId, ActionId>>>,
}

pub struct GranteeInterior<GranteeId: Key, ActionId: Key> {
    pub grantee_of: HashSet<Grantee<GranteeId, ActionId>>,
    pub grantees: HashSet<Grantee<GranteeId, ActionId>>,
    pub actions: HashSet<Action<ActionId, GranteeId>>,
}

pub struct Action<ActionId: Key, GranteeId: Key> {
    pub key: ActionId,
    interior: Rc<RefCell<HashSet<Grantee<GranteeId, ActionId>>>>,
}

This works flawless for single threaded applications
Multithreading is where the struggle begins. I know I need to wrap the Db-struct to share it across threads like this type async_db = Arc<RwLock<Db<GranteeId, ActionId>>>

Initially I thought this would work as is because the access would have been locked as is. But unfortunately I need to replace every Rc with Arc and RefCellwith RwLock because other wise it would not impl Send + Sync;

This looks like a lot of extra work. Is there a more elegant and performant way to do this? I figured, as they're all interior mutable, even a RwLock would allow to mutate it even if a lock was given.

I do not want to lock every Grantee/Action that I visit.

Would a Mutex work better?

[chrefr]

Mutex will work better for RefCell but not Rc because it is not even Send. Think of it this way: once a lock was granted, one could clone() the Rc and use it outside the mutex.

[lyckligtax]

I think I got my wording wrong here. And after some thought I think this is the better question:

I do have a graph structure with adjanced lists for parents and children as well as many roots as children. I do use the interior mutability pattern wih Rc<RefCell<Whatever>>> with great success.

I do know how to share a single node across threads by using Arc and RwLock but I do NOT know how to share the whole graph without wrapping each node

Wrapping each node into a Arc<RwLock<Whatever>> is expensive (because of the locking) and the whole graph is traversed very frequently.

Is there a better way to share a mutable graph over multiple threads?

[cuviper]

You could try something like dashmap, which is internally sharded to reduce lock contention, or im that uses copy-on-write.