9 Replies Latest reply on Sep 17, 2007 8:51 AM by Manik Surtani

    Problems with NodeLocking algorithm

    Jacek Halat Newbie

      Problems with NodeLocking algorithm

      Hi all

      I?m fascinated with TreeCache and I think that this is a very good and powerful product. I?m trying to use it in my application where many concurrent puts/removes occurs ? and this is not easy task, because there are many unreasonable exceptions raised from TreeCache under heavy-load.

      Because my application must work 24/7 without any unreasonable exceptions raised form any component I do some investigation and found, that node locking algorithm used by TreeCache (when using Pessimistic locking scheme) is not good enough.

      Main ?work unit? in TreeCache is Node. Nodes have hierarchical structure like folders on disk. There is root node, root node has children, children have own children etc.
      If operation needs modify data in node, lock must be acquired. Physically locks are a part of Node.
      If we put data into /a/b/c/d node (on clear cache), first lock on / (root) node must be acquired. Then if / doesn?t contains a child, /a node must be created and lock must be acquired etc.
      If all required nodes from path are locked with correct lock type (RL, WL), target operation can be invoked.
      This is very simple and generally this works correctly in single-thread applications. But what happens when 2 threads are trying work on this same node?

      Scenario 1:
      There is /a node in cache.
      Thread-0 is trying put new value into /a node, Thread-1 is trying remove /a node.
      Both threads are in PessimistickLockInterceptor.lock() method, both treads have this same reference to /a node.
      Thread-1 is acquiring WL lock on /a node and wins, Thread-0 is waiting for WL on /a node.
      Now Thread-1 removes /a node from cache and until now / doesn?t contains /a node, but Thread-0 is still waiting for WL to /a node. Thread-1 commits transaction and release lock on /a node. Thread-0 acquired lock on /a. Because /a dosen?t exists in cache (was removed by Thread-1) this lock is invalid. This situation is handled by treecache properly, because he checks after lock acquisition if node still exists in cache

      do{
      lock(fqn, ctx.getGlobalTransaction(), lock_type, recursive, zeroLockTimeout ? 0 : lock_timeout, createIfNotExists, storeLockedNode, isRemoveData);
      }while (!cache.exists(fqn))
      

      But what happens if between lock method and condition check another thread creates /a node?

      Assume that Thread-0 is sleeping before loop condition check (this really happens in real-applications under heavy load). Thread-1 needs to put some data into previously removed /a node. Because / (root) dosen?t contains /a, new node /a is created, and WL on new node is acquired by Thread-1.

      Now we have situation, when 2 threads have WL on this same node! This is possible, because lock table is located into node, and both threads have another instance of /a node.
      Now Thread-1 is putting some data into /a node and commit operations, Thread-0 checks loop condition, and because /a node exists in cache, loop is released. Thread-0 is going into real _put operation. Now assume, that before invoke _put operation Thread-1 is removing again /a node. He can do this, because /a node from treecache hasn?t any information about WL lock (Thread-0 has WL, but in old node instance, different from instance form cache). Node /a is now removed from cache by Thread-1.
      And now if Thread-0 try invoke _put operation, he can?t find /a node, findNode returns null
      and NodeNotExistsException is raised.

      This issue was observed and reported as bug http://jira.jboss.com/jira/browse/JBCACHE-1164

      I think, that the simplest solution to this problem is to add additional condition to loop condition. Not only fqn exists condition should be checked, but node from cache with locked node should be compared. It?s easy to return locked node from lock() method and replace cache.exists with cache._get method and compare this 2 objects. If they are not this same object ? loop can be finished only if this objects are this same object. (or if result from lock method is null)

      I have changed this code and it look works correctly now.

      Scenario 2:
      Cache is clear. Thread-0 is trying to remove /a node. He checks / (root) and because there is no any children, no WL lock was created. Because no lock has been created, no information to current transaction table about removed node is added. (Treecache in pessimistic locking scheme doesn?t is marking only nodes as removed when real _remove operation is invoked. Nodes are really removed in commit phase). Tread-0 is going into real _remove operation. Assume that Thread-0 sleeps before _remove execution (simulate heavy-load). Now Thread-1 is trying to put new data into /a/b/c/d node. He must checks whole path /a/b/c/d. because / (root) doesn?t contains any children, /a is created and then /a/b etc. Now Thread-1 needs to check end loop condition, but assume, that before this operation Thread-0 invokes _remove operation. Node /a is marked as removed, Thread-0 commit transaction etc. because transaction table doesn?t contains any information about removed nodes node was not real removed from cache. But this node is still marked as removed!
      This is first problem in this scenario, this node is form now like ghost, because it still exists in cache, but is marked as removed.
      This issue was observed and reported as bug http://jira.jboss.com/jira/browse/JBCACHE-1168

      And we can see now next problem: Thread-1 needs to check end loop condition. Because exists method from cache default doesn?t returns nodes marked as removed, condition is true (!cache.exists), and again lock() method is called. Again / (root) is checked, but because getOrCreateChild doesn?t checks node for markAsRemoved condition, now Thread-1 looks, that / contains /a, /a contains /a/b etc. again WL on /a/b/c/d is acquired and again end loop condition is checked, again cache.exists returns false, again lock() is invoked etc. This loop never ends. Only chance to stop this is TimeoutException, but because Thread-1 has already owned all locks, there is no chance to TimeoutException to be thrown.

      This issue (endless loop) was observed and reported as bug http://jira.jboss.com/jira/browse/JBCACHE-1165
      I think, that because real _remove operation is always invoked (both when node is locked and when node doesn?t exists and no lock is acquired), the simplest solution is to set flag createIfNotExists=true on removeNodeMethod. I have added this condition and it look works correctly.
      To break infinitive loop (in another, yet unknown cases), I think that max time to spent in this loop can?t be greater than lock acquisition timeout, so in loop check condition should be added.

      Scenario 3:
      Cache is clear. Similar to scenario 2 but with small, but important difference. First starts Thread-1. Thread-1 is putting new data into /a/b/c/d. Because WL is acquired only on target node, on nodes /a /a/b and /a/b/c only RL is acquired. Assume, that Thread-1has acquired RL on /a/b/c. Assume that Thread-1 sleep for some time now (simulate heavy-load). Now Thread-0 starts and is trying to remove /a node. Thread-0 needs lock with WL /a and /a children?s. Thread-0 locks /a, /a/b, and /a/b/c with WL (he can do this, because Thread-1 has only RL) and because now /a/b/c node doesn?t contains any children (Thread-1 is sleeping). Thread-0 checks end loop condition and is going into real _remove operation. Now assume that Thread-0 is going to sleep and Thread-1 wakes up. Thread-1 create /a/b/c/d node and acquire WL on this node, and is going into real _put operation. Now if Thread-0 removes node /a/b/c/d before Thread-1 finds node /a/b/c/d, Thread-1 will throw NodeNotExistsException from _put operation, because for Thread-1 this node is locked but couldn?t be found in cache.

      I don?t known how this situation could be the best handled. The simplest solution is to acquire WL on node instead RL when node is created, but I have not yet tested this solution.

      I hope, that this information helps TreeCache team to solve problems with parallel work to fast as its possible, because now it?s impossible to use Treecache (in PessimistickLock mode) in multithread applications, where many concurrent put/remove operations from this same regions occurs.

      Jacek Halat

        • 1. Re: Problems with NodeLocking algorithm
          Brian Stansberry Master

          Thanks much for the excellent post and for opening the JIRAs.

          Manik's likely going to be off line for a few days, and he's the one best able to respond in detail. So if you don't hear more for a few days, that's probably why.

          Please have a look at http://www.jboss.com/index.html?module=bb&op=viewtopic&t=113634 for a discussion of medium-term changes in JBC locking. That's not the kind of short term solution you are (quite reasonably) looking for. But, your posts clearly show you as a community member with deep knowledge of JBC locking and valid inputs, so for sure we'd like any thoughts you have the new design.

          Re: your Scenario 3, wouldn't use of REPEATABLE_READ resolve this?

          • 2. Re: Problems with NodeLocking algorithm
            Jason Greene Master

            Jacek,

            You should be able to temporarily address these issues by enabling "lockParentForChildInsertRemove", This will force a write a lock on the parent node for insert/update. As brian suggests Scenario 3 can be addressed by using REPEATABLE_READ, although that will increase the possibility of lock contention.

            The new MVCC locking design that Brian refers to will move to FQN based locking, instead of node locking.

            -Jason


            • 3. Re: Problems with NodeLocking algorithm
              Jacek Halat Newbie

              Hi
              The simplest solutions are always the best ;) Yes, REPETEABLE_READ +lockParentForChildInsertRemove really resolves this issues.
              But now, it's impossible to parallel put data into 2 separates nodes :(
              i.e. cache has /a/b/c node

              Thread-0: put into /a/b/c/X
              Thread-1: put into /a/b/c/Y
              Both threads are trying create children into c node, but Thread-1 must waits for Thread-0....

              I have tried to use READ_COMMITED (for performance reasons) but looks that for now this is impossible without code modification.

              Jacek Halat

              • 4. Re: Problems with NodeLocking algorithm
                Jason Greene Master

                 

                "jacek187" wrote:
                Hi
                The simplest solutions are always the best ;) Yes, REPETEABLE_READ +lockParentForChildInsertRemove really resolves this issues.
                But now, it's impossible to parallel put data into 2 separates nodes :(
                i.e. cache has /a/b/c node

                Thread-0: put into /a/b/c/X
                Thread-1: put into /a/b/c/Y
                Both threads are trying create children into c node, but Thread-1 must waits for Thread-0....


                Right this is the primary issue with pessimistic locking (contention). The parent locking suggestion is just a workaround. We still want to look into the issues you describe, as even without locking the parent node, the changes should still be atomic. Manik was looking into one of the issues you opened, so I will ping him when he gets back.

                Further analysis and patches are always welcome. Feel free to join the developer forums and mailing list if you like.

                -Jason

                • 5. Re: Problems with NodeLocking algorithm
                  Jacek Halat Newbie

                  Hi
                  I found next problem with node locking and transaction timeouts.
                  On WebLogic (and on another application servers too) if transaction is timed-out and thread witch timed-out transaction is still working on request (i.e. is waiting on locks, reading file etc., important is that transactional method invocation has not ended before timeout) server is calling rollback on timed-out transaction in another, separate thread.

                  This give a chance to release used resources - db connections, locks etc.

                  Problem is, that sometimes treecache dosen't release acquired WL when timed-out transaction is rolledback in separate thread.

                  I have reported some moths ago similar bug http://jira.jboss.com/jira/browse/JBCACHE-923, now effects are identical, but scenario is more complicated.

                  Scenario4:
                  Cache has node /a.
                  new transaction is started. Transactional method is doing something on cache (i.e. /b node is created) (transaction is registered in InvocationContext) and waits until transaction has timed-out. Transaction has timed out (i smarked by container as rollBackOnly). Now method will modify /a node (until now no WL was acquired on this node). Warning about (not ACTIVE or PREPARING) current transaction status from getCurrentTransaction is printed, and null is passed as GlobalTransaction argument, but in InvocationContext is still transaction stored, so pessimistickLockIntercepotr still can use this transaction object.
                  This Thread has just acquired WL on node /a and now is trying to record this lock. Assume that thread sleeps now in recordNodeLock (simulate heavy-load), gtx is not null. Now container has decide to rollback this transaction. Rollback phase is executed. Most important from this operation is, that TransactionEntry from transactionTable is removed. Rollback phase is finished, Thread-0 can continue execution. Thread-0 is executing:
                  cache.getTransactionTable().addLock(gtx, lock);
                  but corresponding transactionEntry couldn't be found, because it was removed in rollback phase. Unfortunally only error is logged, and code execution is continued. Information about acquired WL is never used, and this lock never will be released.

                  This issue was observed in real application.
                  I think, that
                  * additional condition must be added - if acquiredLock can;t be recorded, he must be immediatly released and exception should be thrown.
                  * what is thew sense of continue cache opertions when transaction is marked as rollbackOnly? maybe immediatly exception should be thrown? (something like container)

                  Jacek Halat

                  • 6. Re: Problems with NodeLocking algorithm
                    Manik Surtani Master

                    First off, thanks for all the effort, Jacek.

                    The race condition between the locking and checking of node existence is a nasty bug. Adding a timer within the loop to break after a timeout is valuable too.

                    All this really stems from the fact that a Node owns the lock. This design flaw is being worked on (new MVCC locking design deals with a striped lock on the Fqn) so even if new nodes are created or destroyed, as long as they belong to the same Fqn the lock will apply.

                    I'm looking into the patches you sent me - I will definitely be using some of them in 1.4.1.SP5.

                    Regarding your scenario 3 though, I would try RepeatableRead and see if it really does impact your performance all that much.

                    • 8. Re: Problems with NodeLocking algorithm
                      Ken Kachnowich Newbie

                      Hi,

                      I am running a TreeCache in Jboss 4.0.5.ga and have run into locking issues also. Does LockParentForChildInsertRemove exist in this version? I added

                      true

                      but I get

                      org.jboss.deployment.DeploymentException: No Attribute found with name: LockParentForChildInsertRemove

                      Thanks,

                      Ken

                      • 9. Re: Problems with NodeLocking algorithm
                        Manik Surtani Master

                         

                        "khkachn" wrote:
                        Hi,

                        I am running a TreeCache in Jboss 4.0.5.ga and have run into locking issues also. Does LockParentForChildInsertRemove exist in this version? I added

                        <attribute name="LockParentForChildInsertRemove">true</attribute>

                        but I get

                        org.jboss.deployment.DeploymentException: No Attribute found with name: LockParentForChildInsertRemove

                        Thanks,

                        Ken


                        You will need to upgrade the version of JBoss Cache you have to the latest SP of 1.4.1.