Details
Blocker 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 chetanm 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
Attachments
Issue Links
- is related to
-
OAK-1768 DocumentNodeBuilder.setChildNode() runs OOM with large tree
-
- Closed
-