Uploaded image for project: 'Jackrabbit Oak'
  1. Jackrabbit Oak
  2. OAK-2513

algorithm with O(n!) in mongoMk rebase - not finishing in years

    XMLWordPrintableJSON

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Blocker
    • Resolution: Fixed
    • Affects Version/s: 1.0.9, 1.0.11
    • Fix Version/s: 1.0.12, 1.1.7
    • Component/s: core
    • Labels:
      None
    • Environment:

      oak 1.0.9.r1646300 and 1.0.11 (see further details as to which stack is from which version below)

      Description

      In MongoMk/DocumentNodeStore there is an algorithm which is O(n!) meaning that even with few entries (eg 12 or 13 as witnessed) it would result in the order of billion operations (which consist of map.containsKey, map.put for example) - ie it would create an almost infinite loop.

      This situation is seen in DocumentNodeStore.merge() and DocumentNodeStore.readNode() where there is a branch with unsaved revisions (and as Chetan Mehrotra pointed out, oak only creates a branch for large commits).

      The assumption that it is an O(n!) algorithm are:

      • document.Branch.rebase() constructs a RebaseCommit() object, passing it the list of previous commits, adding the resulting commit to that list of previous commits
      • this constructs a list of RebaseCommit() objects, that each have the (n-1) previous objects
      • later in either document.Branch.applyTo() or isModified() it recursively goes through this list of previous commits - which since that list also consists of RebaseCommit objects and each of those consists (n-1) previous objects, results in n * (n-1) * (n-2) * (n-3) such recursions.
      • note that during the 'almost endless loop' there is no activity against the underlying eg mongod - but nevertheless does the cache.load() call keep a lock for the given amount of time (for the affected path at least)

      Since n! starts to get big already with a low digit (eg 8!=40,320) you could start seeing burst of rebase operations becoming slow quite soon.

      Attaching stacktraces where this has been witness and underlining the issue below.

      with oak 1.0.11:

         java.lang.Thread.State: RUNNABLE
      	at org.mapdb.BTreeMap.findChildren(BTreeMap.java:580)
      	at org.mapdb.BTreeMap.get(BTreeMap.java:607)
      	at org.mapdb.BTreeMap.containsKey(BTreeMap.java:1505)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$BranchCommitImpl.isModified(Branch.java:325)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:366)
      	at org.apache.jackrabbit.oak.plugins.document.Branch.getUnsavedLastRevision(Branch.java:242)
      	at org.apache.jackrabbit.oak.plugins.document.NodeDocument.getNodeAtRevision(NodeDocument.java:896)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.readNode(DocumentNodeStore.java:929)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore$3.call(DocumentNodeStore.java:706)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore$3.call(DocumentNodeStore.java:703)
      	at com.google.common.cache.LocalCache$LocalManualCache$1.load(LocalCache.java:4724)
      	at com.google.common.cache.LocalCache$LoadingValueReference.loadFuture(LocalCache.java:3522)
      	at com.google.common.cache.LocalCache$Segment.loadSync(LocalCache.java:2315)
      	at com.google.common.cache.LocalCache$Segment.lockedGetOrLoad(LocalCache.java:2278)
      	- locked <0x0000000552d56720> (a com.google.common.cache.LocalCache$StrongAccessEntry)
      	at com.google.common.cache.LocalCache$Segment.get(LocalCache.java:2193)
      	at com.google.common.cache.LocalCache.get(LocalCache.java:3932)
      	at com.google.common.cache.LocalCache$LocalManualCache.get(LocalCache.java:4721)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.getNode(DocumentNodeStore.java:703)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.readChildren(DocumentNodeStore.java:785)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore$4.call(DocumentNodeStore.java:733)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore$4.call(DocumentNodeStore.java:730)
      	at com.google.common.cache.LocalCache$LocalManualCache$1.load(LocalCache.java:4724)
      	at com.google.common.cache.LocalCache$LoadingValueReference.loadFuture(LocalCache.java:3522)
      	at com.google.common.cache.LocalCache$Segment.loadSync(LocalCache.java:2315)
      	at com.google.common.cache.LocalCache$Segment.lockedGetOrLoad(LocalCache.java:2278)
      	- locked <0x0000000552f25170> (a com.google.common.cache.LocalCache$StrongAccessEntry)
      	at com.google.common.cache.LocalCache$Segment.get(LocalCache.java:2193)
      	at com.google.common.cache.LocalCache.get(LocalCache.java:3932)
      	at com.google.common.cache.LocalCache$LocalManualCache.get(LocalCache.java:4721)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.getChildren(DocumentNodeStore.java:730)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeState.getChildNodeCount(DocumentNodeState.java:189)
      	at org.apache.jackrabbit.oak.spi.state.AbstractNodeState.equals(AbstractNodeState.java:344)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeState.equals(DocumentNodeState.java:127)
      	at org.apache.jackrabbit.oak.spi.state.AbstractNodeState.equals(AbstractNodeState.java:377)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeState.equals(DocumentNodeState.java:127)
      	at org.apache.jackrabbit.oak.spi.state.AbstractNodeState.equals(AbstractNodeState.java:377)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeState.equals(DocumentNodeState.java:127)
      	at org.apache.jackrabbit.oak.spi.state.AbstractRebaseDiff.childNodeDeleted(AbstractRebaseDiff.java:232)
      	at org.apache.jackrabbit.oak.plugins.memory.ModifiedNodeState.compareAgainstBaseState(ModifiedNodeState.java:389)
      	at org.apache.jackrabbit.oak.spi.state.AbstractRebaseDiff.childNodeChanged(AbstractRebaseDiff.java:219)
      	at org.apache.jackrabbit.oak.plugins.memory.ModifiedNodeState.compareAgainstBaseState(ModifiedNodeState.java:396)
      	at org.apache.jackrabbit.oak.spi.state.AbstractRebaseDiff.childNodeChanged(AbstractRebaseDiff.java:219)
      	at org.apache.jackrabbit.oak.plugins.memory.ModifiedNodeState.compareAgainstBaseState(ModifiedNodeState.java:396)
      	at org.apache.jackrabbit.oak.spi.state.AbstractRebaseDiff.childNodeChanged(AbstractRebaseDiff.java:219)
      	at org.apache.jackrabbit.oak.plugins.memory.ModifiedNodeState.compareAgainstBaseState(ModifiedNodeState.java:396)
      	at org.apache.jackrabbit.oak.spi.state.AbstractRebaseDiff.childNodeChanged(AbstractRebaseDiff.java:219)
      	at org.apache.jackrabbit.oak.plugins.memory.ModifiedNodeState.compareAgainstBaseState(ModifiedNodeState.java:396)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentRootBuilder.rebase(DocumentRootBuilder.java:134)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.rebase(DocumentNodeStore.java:1345)
      	at org.apache.jackrabbit.oak.core.MutableRoot.rebase(MutableRoot.java:223)
      	at org.apache.jackrabbit.oak.jcr.delegate.SessionDelegate.refresh(SessionDelegate.java:548)
      	at org.apache.jackrabbit.oak.jcr.delegate.SessionDelegate.perform(SessionDelegate.java:284)
      	at org.apache.jackrabbit.oak.jcr.session.ItemImpl.perform(ItemImpl.java:113)
      	at org.apache.jackrabbit.oak.jcr.session.ItemImpl.getName(ItemImpl.java:137)
      	at org.apache.jackrabbit.oak.jcr.session.PropertyImpl.getName(PropertyImpl.java:54)
      	at org.apache.sling.jcr.resource.JcrPropertyMap.cacheProperty(JcrPropertyMap.java:263)
      	at org.apache.sling.jcr.resource.JcrPropertyMap.read(JcrPropertyMap.java:352)
      	at org.apache.sling.jcr.resource.JcrPropertyMap.get(JcrPropertyMap.java:130)
      

      with oak 1.0.9.r1646300:

         java.lang.Thread.State: RUNNABLE
      	at org.mapdb.BTreeMap.findChildren(BTreeMap.java:580)
      	at org.mapdb.BTreeMap.get(BTreeMap.java:607)
      	at org.mapdb.BTreeMap.get(BTreeMap.java:589)
      	at org.apache.jackrabbit.oak.plugins.document.UnsavedModifications.put(UnsavedModifications.java:83)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$BranchCommitImpl.applyTo(Branch.java:288)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.applyTo(Branch.java:328)
      	at org.apache.jackrabbit.oak.plugins.document.Branch.applyTo(Branch.java:189)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.merge(DocumentNodeStore.java:1220)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStoreBranch.merge(DocumentNodeStoreBranch.java:73)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStoreBranch.merge(DocumentNodeStoreBranch.java:39)
      	at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch$Persisted$1.call(AbstractNodeStoreBranch.java:617)
      	at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch$Persisted$1.call(AbstractNodeStoreBranch.java:612)
      	at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch.withCurrentBranch(AbstractNodeStoreBranch.java:745)
      	at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch.access$300(AbstractNodeStoreBranch.java:53)
      	at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch$Persisted.merge(AbstractNodeStoreBranch.java:612)
      	at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch.merge(AbstractNodeStoreBranch.java:318)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStoreBranch.merge(DocumentNodeStoreBranch.java:131)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentRootBuilder.merge(DocumentRootBuilder.java:159)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.merge(DocumentNodeStore.java:1337)
      	at org.apache.jackrabbit.oak.core.MutableRoot.commit(MutableRoot.java:247)
      	at org.apache.jackrabbit.oak.jcr.delegate.SessionDelegate.commit(SessionDelegate.java:390)
      	at org.apache.jackrabbit.oak.jcr.delegate.SessionDelegate.save(SessionDelegate.java:536)
      

      and also with oak 1.0.9.r1646300:

         java.lang.Thread.State: RUNNABLE
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
      	at org.apache.jackrabbit.oak.plugins.document.Branch$RebaseCommit.isModified(Branch.java:335)
      	at org.apache.jackrabbit.oak.plugins.document.Branch.getUnsavedLastRevision(Branch.java:211)
      	at org.apache.jackrabbit.oak.plugins.document.NodeDocument.getNodeAtRevision(NodeDocument.java:882)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.readNode(DocumentNodeStore.java:929)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore$3.call(DocumentNodeStore.java:706)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore$3.call(DocumentNodeStore.java:703)
      	at com.google.common.cache.LocalCache$LocalManualCache$1.load(LocalCache.java:4724)
      	at com.google.common.cache.LocalCache$LoadingValueReference.loadFuture(LocalCache.java:3522)
      	at com.google.common.cache.LocalCache$Segment.loadSync(LocalCache.java:2315)
      	at com.google.common.cache.LocalCache$Segment.lockedGetOrLoad(LocalCache.java:2278)
      	- locked <0x0000000714588728> (a com.google.common.cache.LocalCache$StrongAccessEntry)
      	at com.google.common.cache.LocalCache$Segment.get(LocalCache.java:2193)
      	at com.google.common.cache.LocalCache.get(LocalCache.java:3932)
      	at com.google.common.cache.LocalCache$LocalManualCache.get(LocalCache.java:4721)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.getNode(DocumentNodeStore.java:703)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.readChildren(DocumentNodeStore.java:785)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore$4.call(DocumentNodeStore.java:733)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore$4.call(DocumentNodeStore.java:730)
      	at com.google.common.cache.LocalCache$LocalManualCache$1.load(LocalCache.java:4724)
      	at com.google.common.cache.LocalCache$LoadingValueReference.loadFuture(LocalCache.java:3522)
      	at com.google.common.cache.LocalCache$Segment.loadSync(LocalCache.java:2315)
      	at com.google.common.cache.LocalCache$Segment.lockedGetOrLoad(LocalCache.java:2278)
      	- locked <0x0000000714580700> (a com.google.common.cache.LocalCache$StrongAccessEntry)
      	at com.google.common.cache.LocalCache$Segment.get(LocalCache.java:2193)
      	at com.google.common.cache.LocalCache.get(LocalCache.java:3932)
      	at com.google.common.cache.LocalCache$LocalManualCache.get(LocalCache.java:4721)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.getChildren(DocumentNodeStore.java:730)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.diffImpl(DocumentNodeStore.java:1666)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.access$200(DocumentNodeStore.java:105)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore$7.call(DocumentNodeStore.java:1259)
      	at org.apache.jackrabbit.oak.plugins.document.MongoDiffCache.getChanges(MongoDiffCache.java:88)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.diffChildren(DocumentNodeStore.java:1254)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeState.compareAgainstBaseState(DocumentNodeState.java:260)
      	at org.apache.jackrabbit.oak.plugins.commit.MergingNodeStateDiff.merge(MergingNodeStateDiff.java:70)
      	at org.apache.jackrabbit.oak.plugins.commit.MergingNodeStateDiff.childNodeChanged(MergingNodeStateDiff.java:92)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeState.dispatch(DocumentNodeState.java:433)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeState.compareAgainstBaseState(DocumentNodeState.java:260)
      	at org.apache.jackrabbit.oak.plugins.commit.MergingNodeStateDiff.merge(MergingNodeStateDiff.java:70)
      	at org.apache.jackrabbit.oak.plugins.commit.MergingNodeStateDiff.merge(MergingNodeStateDiff.java:65)
      	at org.apache.jackrabbit.oak.plugins.commit.ConflictHook.processCommit(ConflictHook.java:53)
      	at org.apache.jackrabbit.oak.spi.commit.CompositeHook.processCommit(CompositeHook.java:60)
      	at org.apache.jackrabbit.oak.spi.commit.CompositeHook.processCommit(CompositeHook.java:60)
      	at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch$Persisted$1.call(AbstractNodeStoreBranch.java:615)
      	at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch$Persisted$1.call(AbstractNodeStoreBranch.java:612)
      	at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch.withCurrentBranch(AbstractNodeStoreBranch.java:745)
      	at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch.access$300(AbstractNodeStoreBranch.java:53)
      	at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch$Persisted.merge(AbstractNodeStoreBranch.java:612)
      	at org.apache.jackrabbit.oak.spi.state.AbstractNodeStoreBranch.merge(AbstractNodeStoreBranch.java:318)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStoreBranch.merge(DocumentNodeStoreBranch.java:131)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentRootBuilder.merge(DocumentRootBuilder.java:159)
      	at org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore.merge(DocumentNodeStore.java:1337)
      	at org.apache.jackrabbit.oak.core.MutableRoot.commit(MutableRoot.java:247)
      	at org.apache.jackrabbit.oak.jcr.delegate.SessionDelegate.commit(SessionDelegate.java:390)
      	at org.apache.jackrabbit.oak.jcr.delegate.SessionDelegate.save(SessionDelegate.java:536)
      

        Attachments

        1. OAK-2513-a.patch
          3 kB
          Chetan Mehrotra
        2. OAK-2513-b.patch
          3 kB
          Marcel Reutegger
        3. OAK-2513-test1.patch
          5 kB
          Chetan Mehrotra

          Issue Links

            Activity

              People

              • Assignee:
                chetanm Chetan Mehrotra
                Reporter:
                stefanegli Stefan Egli
              • Votes:
                0 Vote for this issue
                Watchers:
                2 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: