NullReferenceException in Akka.Util.Internal.Collections.ImmutableAvlTreeBase`2.RotateLeft

[kantora]

Hello.
We've got strange error in our application.
I'll just post StackTrace here.

Akka.Util.Internal.Collections.ImmutableAvlTreeBase`2.RotateLeft(Node node):0
 Akka.Util.Internal.Collections.ImmutableAvlTreeBase`2.TryAdd(Node node, TKey key, TValue value, Node& newNode, AddOperation typeOfAdd):360
 Akka.Util.Internal.Collections.ImmutableAvlTreeBase`2.TryAdd(Node node, TKey key, TValue value, Node& newNode, AddOperation typeOfAdd):112
 Akka.Util.Internal.Collections.ImmutableAvlTreeBase`2.TryAdd(Node node, TKey key, TValue value, Node& newNode, AddOperation typeOfAdd):112
 Akka.Util.Internal.Collections.ImmutableAvlTreeBase`2.TryAdd(Node node, TKey key, TValue value, Node& newNode, AddOperation typeOfAdd):112
 Akka.Util.Internal.Collections.ImmutableAvlTreeBase`2.TryAdd(Node node, TKey key, TValue value, Node& newNode, AddOperation typeOfAdd):112
 Akka.Util.Internal.Collections.ImmutableAvlTreeBase`2.TryAdd(Node node, TKey key, TValue value, Node& newNode, AddOperation typeOfAdd):112
 Akka.Util.Internal.Collections.ImmutableAvlTreeBase`2.TryAdd(TKey key, TValue value, Node& newNode, AddOperation typeOfAdd):0
 Akka.Util.Internal.Collections.ImmutableTreeMap`2.AddOrUpdate(TKey key, TValue value):0
 Akka.Util.Internal.Collections.ImmutableTreeMap`2.Akka.Util.Internal.Collections.IImmutableMap<TKey,TValue>.AddOrUpdate(TKey key, TValue value):0
 Akka.Actor.Internal.NormalChildrenContainer.Reserve(String name):0
 Akka.Actor.ActorCell+<>c__DisplayClass53.<ReserveChild>b__52(IChildrenContainer c):0
 Akka.Util.Internal.InterlockedSpin.Swap[T](T& reference, Func`2 updater):15
 Akka.Actor.ActorCell.ReserveChild(String name):13
 Akka.Actor.ActorCell.MakeChild(Props props, String name, Boolean async, Boolean systemService):19
 Akka.Actor.ActorCell.ActorOf(Props props, String name, Boolean isAsync, Boolean isSystemService):20
 Akka.Actor.ActorCell.ActorOf(Props props, String name):0
 ODS.Core.Actors.OrdersSupervisor.GetOrCreateChild(String orderId) in .\ODS.Core\Actors\OrdersSupervisor.cs:145

GetOrCreateChild methods just creats child actor like this:

        protected virtual IActorRef GetOrCreateChild(string orderId)
        {
            var childName = GetChildKey(orderId);
            var childActor = Context.Child(childName);
            if (childActor.IsNobody())
            {
                Logger.Debug("{Type}:  Creating order actor {OrderId}", this.GetType().Name, orderId);
                childActor = Context.ActorOf(this.OrderGenerator(orderId, this.DataWorker), childName);
            }

            return childActor;
        }

Nither this.OrderGenerator nor childName could be null in this case (I've checked this several times).
But this only happened once this far...

[Aaronontheweb]

Putting some red labels on this one - smells like a potential bug to me.

Mind if I ask some additional questions?

• Is GetOrCreateChild being called from a continuation or Task?
• Does the actor who called this method already have children when this error occurs?
• Does it occur when you attempt to add the first child?

[kantora]

Sure.

Is GetOrCreateChild being called from a continuation or Task?

The receive method itself is synchronous, but we use TaskDispatcher for this kind of actors.

Does the actor who called this method already have children when this error occurs?

Yeah. Hundred or two. They are constantly adding and removing over time. Also they have there own children, that also can be added or removed.

Does it occur when you attempt to add the first child?

No, definitely not. This system was functioning for relatively long time, and that was the first and only time we faced this exception.

[rogeralsing]

Related to #1175 , we plan to replace the AVL tree to a Red/Black tree as the JVM impl

[kantora]

Ok, thanks.

[diegofrata]

I'm facing the same sporadically, usually over a 100 actors. My actor behaves a bit as @kantora, constantly adding and removing children. Had it happen three times yesterday at startup of my system, and then it stopped. So it's highly random, probably depends on the order things are added/removed.

[boekabart]

For us this bug is critical. Our application makes a lot of temporary actors, and every single run it would crash (at random times, but always within a minute or two).

[boekabart]

Root cause here is a bug in the ImmutableAvlTreeBase: Remove could return an unbalanced (height difference >1) tree node. When adding something below this, it auto-resolves. When adding something 'next' to this node, in some cases this would lead to the exception. All about the exact order in which keys are added/removed to the tree.
I've written unit tests that prove in 2 situations that the node (tree) is unbalanced after a remove, and written the fix as well, in PR #1645 .

[mattnischan]

Is there a reason that we're not using the BCL ImmutableDictionary here? It is standard now and is also an immutable AVL tree. Performance reasons?

[boekabart]

I tend to agree to try and use an 'off the shelf' implementation; this is not at all specific / core business to akka.net .

[rogeralsing]

@mattnischan back in the day when we discussed this, I dont think anyone of us knew that the immutable dict was an AVL tree. (#472)

If the ImmutableDictionary can be used instead, I definitely think we should replace the custom code with that.
I know there are some secial cases here, we use both AVL Tree and AVL Map in the codebase so we need to cover all of that if we would replace it.

[diegofrata]

What about the other talk about using a red-black tree? There is a issue
for that somewhere. I wouldn't replace it with another implementation of
AVL if the plan is to use something else.
Em sex, 15 de jan de 2016 às 18:18, Roger Johansson <
notifications@github.com> escreveu:

@mattnischan https://github.com/mattnischan back in the day when we
discussed this, I dont think anyone of us knew that the immutable dict was
an AVL tree. (#472 #472)

If the ImmutableDictionary can be used instead, I definitely think we
should replace the custom code with that.
I know there are some secial cases here, we use both AVL Tree and AVL Map
in the codebase so we need to cover all of that if we would replace it.

—
Reply to this email directly or view it on GitHub
#1202 (comment)
.

[mattnischan]

The performance differences between red-black and AVL are extremely slight and very use-case dependent. AVL is slightly better for reads due to more strict balance (less depth), and red-black slightly better for inserts due to fewer rotations. However, the rules for red-black rotations are slightly more expensive, so in mixed use scenarios (which these appear to be), I don't see a reason to favor one over the other.