I can't give you a complete solution as I never bothered to try to make a universal, thread-safe scene graph (a bit too ambitious given the teams and environments I worked with), but I think this answer will provide a huge potential puzzle piece.
Kill the Scene Root!
I don't use the concept of a "scene root". If I did, every single thing I insert to the scene would have to be inserted to the scene root and store all kinds of links with all kinds of shared data. I do have a tree component like this:
struct CTreeNode
{
// I often need bottom-up traversal where the user
// selects a child/leaf and then wants immediate access
// to its parent, so I store a parent link.
int parent;
int next_sibling;
int first_child;
};
... but I only use that and attach that to an entity when I genuinely need parenting, like in a bone or rigid body hierarchy. And the root of that is not the scene root, so there's little shared data. The root for a robot might be its pelvis/hips, not the root of the entire scene. We basically take this:
... and turn it into this:
And that might seem like it's just trading a "scene root child list" for a "flat scene list", but the second doesn't have to be a linked structure; it can be a totally different data structure and data type. You could use an unrolled list or tbb::concurrent_vector or something else very friendly for concurrency and memcpy and so forth if you're aiming to try to make these central data structures thread-safe. You don't have to get tunnel visioned on trying to make the entire tree and manipulations on a single node thread-safe if this flat "root child list" is stored in a separate data structure from the tree nodes.
Different Characteristics, Common Cases and Rare Cases
The root child list is very different in nature from the rest of the branches/children since it's usually going to store a massive list of analogical children and inserting/removing children would potentially be an extremely common case (possibly occurring every single frame), while the branches in the scene will often have much fewer children and may rarely ever need to modify the hierarchy. The average number of children the root node need could be in the range of hundreds of thousands to millions, while the average for everything else that needs to serve as a parent is 3. Those are radically different requirements.
There's very few reasons for a bone hierarchy to ever change. You might just load the skeletal data for a character and that's that, the parent/child relationships never change beyond that point. Meanwhile you might be inserting and removing elements to/from the scene many, many times per frame. When you have radically different use characteristics like that, it often helps to use a different data structure.
It makes things a lot easier if you don't try to use one node data structure to rule them all here and treat the "flat scene list" as a separate concept/data structure without an actual "scene root" because, again, the data structure and usage and common case/rare case characteristics are vastly different between the analogical scene root child list and, say, the children's children. Trying to cram that all into one analogical "node" structure for everything is likely to cause more grief than help, and especially if you're trying to multithread hierarchical manipulation and traversal.
Multithreading
And I think if you start with that concept of eliminating the idea of a scene root which every single thing in your scene/game world is parented to, it should help a whole lot if you are trying to multithread manipulations and access of the graph. That'll give you many independent graphs with little shared data instead of one graph with shared root data for everything.
Implicit Scene Root
If you want to actually do the analogical "whole scene transformation", you can special case that and multiply everything by a matrix without storing parent/child links for every single thing in your scene. If you need to display a scene outline in your level editor, again you can special case and pretend like the scene root exists by doing flat iteration over the entities in your scene that don't have a tree node component attached or have, say, -1 stored for the parent (which in my case indicates a root). You don't actually have to have a real root node for the entire scene and link everything to it and store all this extra shared data. You can deduce that implicitly that every entity without a tree node attached or with a null parent (or parent set to -1 if you use indices like me) is an immediate child of the analogical scene root (which isn't actually stored as a node in memory).
Caching Preorder Traversal
Another thing that mitigates cache misses since linked structure traversal is inherently not very cache-friendly usually is that I have a function which outputs a flat array of indices using preorder traversal of the tree (which, again, is a small tree with an entity in the scene as its root, not the entire massive scene as its root), and each set of child indices is sorted. I generally don't traverse the tree except to output this flat array of indices whenever the tree has changed. Since the indices are gathered using preorder traversal, you can update motion matrices in a straight sequential fashion over the resulting array while processing things in proper order (parents before children).
shared_ptr/weak_ptr
On the use of shared_ptr/weak_ptr, I generally don't bother and just refer to things by index when components depend on each other. Again with my tree node:
struct CTreeNode
{
int parent;
int next_sibling;
int first_child;
};
... the links just use plain old integers as indices to entities. What I do is when the node is destroyed (I can register destructors for a component type through the component registry -- can't use C++ dtors directly since the ECS uses a C API for interop with many different languages), I just update the links to exclude the node, removing it from its parent and setting the links of its children to -1 (null, i.e.).
Now I could see how shared_ptr might become very helpful in a multithreading context to ensure that the lifetime of a resource is extended until after a thread is finished processing it, but I always found the benefits of shared_ptr to often be outweighed by its cons (easy to introduce logical leaks by accident, expensive atomic ref counts, having to heap allocate everything including the ref counter, etc). Instead I often found it useful to just make sure all systems do their processing from a "process" callback/event, even systems running in other threads. If they try to destroy/remove any entity/component during these processing events, the removal is deferred until a small time slice (very short-lived lock) when systems are no longer processing.
I find that much easier to deal with and so much cheaper and just much more predictable to reason about when things should be destroyed in between system processing instead of at the granular level of all shared pointers to a resource being released whenever and from wherever (hard to predict when/where that will be in a complex codebase if you're using shared ownership a lot). I find it so much easier to have an explicit "removal" function I can count on to remove components and entities, but also knowing that's safe to use because it's not actually going to remove a component if systems are still being processed (in the same thread or other threads). If you can unify your codebase this way as opposed to having "rogue threads" storing their own persistent references to game state for who knows how long, life becomes so much easier.
Because in my cases at least, a scene entity/component should be removed when the user requests to remove it from the editor unless there are systems still processing, at which point it should be removed as soon as possible when they're not. Explicit removal is so much easier in these cases than implicit and hoping that every relevant part of your system will release those strong references soon after.
Another thing about shared_ptr in a team environment at least is that once you publicly expose a shared_ptr to something in some interface (using shared_ptr for implementation details is not nearly as problematic), you can't stop it from spreading. You can't prevent people (at least not forcefully, maybe with very careful standards) from storing more shared_ptrs to the same resource, including third party plugin developers writing code completely outside of your team's control, and it only takes one of them to be careless and forget to release the shared_ptr to extend a resource's lifetime far longer than appropriate, introducing logical leaks into your application, and I've had that happen a lot in the past where third parties ended up storing a shared_ptr to something expensive like a mesh, at which point it wasn't freed at the right time when the user requested to remove it (not even close). So I've always been weary about its usage, since it can easily be misused in horrific ways to the point where it can become impossible to reason about when anything will ever be freed and destroyed since code that's not even in your team's control could be extending the lifetime of objects way, way longer than they should persist.
